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
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
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.
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.