Aasa: un algoritmo de división adaptativa a priori para el problema de enrutamiento de vehículos con entrega dividida
Autores: Torkzaban, Nariman; Gholami, Anousheh; Baras, John S.; Golden, Bruce L.
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Aasa: un algoritmo de división adaptativa a priori para el problema de enrutamiento de vehículos con entrega dividida
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Problema de enrutamiento de vehículos con entrega dividida
SDVRP
Problema de enrutamiento de vehículos capacitados
CVRP
Algoritmo de división adaptativa a priori
AASA
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 33
Citaciones: Sin citaciones
El problema de enrutamiento de vehículos con entrega dividida (SDVRP) es una variante relajada del problema de enrutamiento de vehículos capacitados (CVRP) donde se elimina la restricción de que cada cliente sea visitado exactamente una vez. En comparación con el CVRP, el SDVRP permite una reducción en el costo total de las rutas recorridas por los vehículos. Los métodos exactos para resolver el SDVRP son computacionalmente costosos. Además, la complejidad y la difícil implementación de los enfoques heurísticos de vanguardia dificultan su aplicación en escenarios de la vida real del SDVRP. En este documento, proponemos un enfoque fácilmente comprensible y efectivo para resolver el SDVPR basado en un algoritmo de división adaptativa a priori (AASA) que mejora el estado actual de la técnica en estrategia de división a priori en términos de precisión de la solución y complejidad temporal. En este enfoque, la demanda de los clientes se divide en valores de demanda más pequeños utilizando una regla de división con antelación. En consecuencia, la instancia original de SDVRP se convierte en una instancia de CVRP que se resuelve utilizando un solucionador de CVRP existente. Mientras que la regla de división a priori propuesta en la literatura es fija para todos los clientes independientemente de su demanda y ubicación, sugerimos una regla de división adaptativa que tiene en cuenta la distancia de los clientes al depósito y sus valores de demanda. Nuestros experimentos muestran que AASA puede generar soluciones comparables al estado del arte, pero mucho más rápido.
Descripción
El problema de enrutamiento de vehículos con entrega dividida (SDVRP) es una variante relajada del problema de enrutamiento de vehículos capacitados (CVRP) donde se elimina la restricción de que cada cliente sea visitado exactamente una vez. En comparación con el CVRP, el SDVRP permite una reducción en el costo total de las rutas recorridas por los vehículos. Los métodos exactos para resolver el SDVRP son computacionalmente costosos. Además, la complejidad y la difícil implementación de los enfoques heurísticos de vanguardia dificultan su aplicación en escenarios de la vida real del SDVRP. En este documento, proponemos un enfoque fácilmente comprensible y efectivo para resolver el SDVPR basado en un algoritmo de división adaptativa a priori (AASA) que mejora el estado actual de la técnica en estrategia de división a priori en términos de precisión de la solución y complejidad temporal. En este enfoque, la demanda de los clientes se divide en valores de demanda más pequeños utilizando una regla de división con antelación. En consecuencia, la instancia original de SDVRP se convierte en una instancia de CVRP que se resuelve utilizando un solucionador de CVRP existente. Mientras que la regla de división a priori propuesta en la literatura es fija para todos los clientes independientemente de su demanda y ubicación, sugerimos una regla de división adaptativa que tiene en cuenta la distancia de los clientes al depósito y sus valores de demanda. Nuestros experimentos muestran que AASA puede generar soluciones comparables al estado del arte, pero mucho más rápido.