Un heurístico de búsqueda local iterada para el problema de enrutamiento de vehículos de múltiples viajes con múltiples ventanas de tiempo
Autores: Wu, Yinghui; Du, Haoran; Song, Huixin
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Un heurístico de búsqueda local iterada para el problema de enrutamiento de vehículos de múltiples viajes con múltiples ventanas de tiempo
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Problema de enrutamiento de vehículos de múltiples viajes
Ventanas de tiempo
Ventana de tiempo de servicio
Modelo de programación lineal entera mixta
Heurística de búsqueda local iterativa
Algoritmo de inserción codicioso de Solomon
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
Este documento estudia el problema de enrutamiento de vehículos de múltiples viajes con múltiples ventanas de tiempo, que extiende el problema de enrutamiento de vehículos de múltiples viajes al decidir no solo la secuencia de clientes que cada vehículo atiende, sino también la ventana de tiempo de servicio de cada cliente. También requiere que el tiempo de servicio de entrega esté dentro de las ventanas de tiempo seleccionadas y que la demanda total de los clientes atendidos por el vehículo en cada viaje no exceda la capacidad máxima de carga. Para resolver el problema estudiado, desarrollamos un modelo de programación lineal entera mixta con el objetivo de minimizar la distancia total de viaje de los vehículos y diseñamos una heurística de búsqueda local iterativa personalizada. Dentro del marco de la búsqueda local iterativa, se diseña un algoritmo de inserción codicioso de Solomon mejorado adecuado para múltiples ventanas de tiempo y escenarios de múltiples viajes para generar la solución inicial, y también se desarrollan operadores de búsqueda local como Or-opt y Relocate, así como operaciones de perturbación de intercambio aleatorio. Los resultados del experimento demuestran la efectividad del modelo y algoritmo propuestos y confirman que al proporcionar a los clientes la opción de múltiples ventanas de tiempo, los transportistas pueden planificar de manera flexible las rutas de vehículos y seleccionar ventanas de tiempo de servicio apropiadas, reduciendo así el número de vehículos utilizados y la distancia total recorrida y mejorando el éxito de la entrega.
Descripción
Este documento estudia el problema de enrutamiento de vehículos de múltiples viajes con múltiples ventanas de tiempo, que extiende el problema de enrutamiento de vehículos de múltiples viajes al decidir no solo la secuencia de clientes que cada vehículo atiende, sino también la ventana de tiempo de servicio de cada cliente. También requiere que el tiempo de servicio de entrega esté dentro de las ventanas de tiempo seleccionadas y que la demanda total de los clientes atendidos por el vehículo en cada viaje no exceda la capacidad máxima de carga. Para resolver el problema estudiado, desarrollamos un modelo de programación lineal entera mixta con el objetivo de minimizar la distancia total de viaje de los vehículos y diseñamos una heurística de búsqueda local iterativa personalizada. Dentro del marco de la búsqueda local iterativa, se diseña un algoritmo de inserción codicioso de Solomon mejorado adecuado para múltiples ventanas de tiempo y escenarios de múltiples viajes para generar la solución inicial, y también se desarrollan operadores de búsqueda local como Or-opt y Relocate, así como operaciones de perturbación de intercambio aleatorio. Los resultados del experimento demuestran la efectividad del modelo y algoritmo propuestos y confirman que al proporcionar a los clientes la opción de múltiples ventanas de tiempo, los transportistas pueden planificar de manera flexible las rutas de vehículos y seleccionar ventanas de tiempo de servicio apropiadas, reduciendo así el número de vehículos utilizados y la distancia total recorrida y mejorando el éxito de la entrega.