Un fptas para problemas de camino más corto multiobjetivo dinámico
Autores: Maristany de las Casas, Pedro; Borndörfer, Ralf; Kraus, Luitgard; Sedeño-Noda, Antonio
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Un fptas para problemas de camino más corto multiobjetivo dinámico
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Camino más corto multiobjetivo
Dinámico
Costos
Variables
Planificación de vuelos
Vehículos eléctricos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 25
Citaciones: Sin citaciones
El problema de la Ruta más Corta Multicriterio Dinámica presenta costos multidimensionales que pueden depender de varias variables y no solo del tiempo; este escenario está motivado por aplicaciones de planificación de vuelos y el enrutamiento de vehículos eléctricos. Presentamos un algoritmo exacto para el caso FIFO y derivamos a partir de él un FPTAS tanto para los problemas de Ruta más Corta Multicriterio (MOSP) estáticos como, bajo suposiciones moderadas, para la variante del problema dinámico. El FPTAS resultante es computacionalmente eficiente y supera los límites de complejidad conocidos de otros FPTAS para problemas de MOSP.
Descripción
El problema de la Ruta más Corta Multicriterio Dinámica presenta costos multidimensionales que pueden depender de varias variables y no solo del tiempo; este escenario está motivado por aplicaciones de planificación de vuelos y el enrutamiento de vehículos eléctricos. Presentamos un algoritmo exacto para el caso FIFO y derivamos a partir de él un FPTAS tanto para los problemas de Ruta más Corta Multicriterio (MOSP) estáticos como, bajo suposiciones moderadas, para la variante del problema dinámico. El FPTAS resultante es computacionalmente eficiente y supera los límites de complejidad conocidos de otros FPTAS para problemas de MOSP.