logo móvil
Contáctanos

El problema de la ruta equilibrada en costos: una formulación matemática y análisis de complejidad

Autores: Ambrosino, Daniela; Cerrone, Carmine

Idioma: Inglés

Editor: MDPI

Año: 2022

Descargar PDF

Acceso abierto

Artículo científico
2022

El problema de la ruta equilibrada en costos: una formulación matemática y análisis de complejidad


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Introduce
Variante
Problema de la Ruta más Corta
Problema de la Ruta Equilibrada en Costos
Complejidad
NP-duro

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 30

Citaciones: Sin citaciones


Descripción
Este documento introduce una nueva variante del Problema de la Ruta más Corta (Shortest Path Problem) llamado Problema de la Ruta Equilibrada por Costos (Cost-Balanced Path Problem). Varios problemas reales pueden ser modelados como este o incluirlo como un subproblema. Demostramos varias propiedades relacionadas con la complejidad del problema. En particular, demostramos que el problema es NP-duro en su versión general, pero se vuelve resoluble en tiempo polinómico en una familia específica de instancias. Además, se propone una formulación matemática del problema, como un modelo de programación entera mixta, y se dan algunas restricciones adicionales para modelar requerimientos reales. Este documento valida el modelo propuesto y sus extensiones con pruebas experimentales basadas en instancias aleatorias. El análisis de los resultados de los experimentos computacionales muestra que el modelo propuesto y su extensión pueden ser utilizados para modelar muchas aplicaciones reales. Obviamente, debido a la complejidad del problema, la principal limitación del enfoque propuesto está relacionada con el tamaño de las instancias. Se requeriría un enfoque de solución heurística para instancias más grandes y complejas.

Otros recursos que podrían interesarte

Temas Virtualpro