logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro