Un algoritmo genético mejorado para el problema de enrutamiento de vehículos dividido basado en la granularidad con entrega y recogida simultáneas
Autores: Liu, Yuxin; Qin, Zihang; Liu, Jin
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Un algoritmo genético mejorado para el problema de enrutamiento de vehículos dividido basado en la granularidad con entrega y recogida simultáneas
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Problema de enrutamiento de vehículos divididos
Entrega y recogida simultáneas
SVRPSDP
GSVRPSDP
Algoritmo híbrido genético-simulado
Habilidades de búsqueda global
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 28
Citaciones: Sin citaciones
El Problema de Enrutamiento de Vehículos Divididos con Entrega y Recogida Simultánea (SVRPSDP) consta de dos subproblemas, es decir, el Problema de Enrutamiento de Vehículos con Entrega y Recogida Simultánea (VRPSDP) y el Problema de Enrutamiento de Vehículos con Entrega Dividida (SDVRP). En comparación con los subproblemas, SVRPSDP está mucho más cerca de la realidad. Sin embargo, algunos factores realistas aún son ignorados en SVRPSDP. Por ejemplo, los envíos están integrados y no pueden ser infinitamente subdivididos. Por lo tanto, este documento investiga el Problema de Enrutamiento de Vehículos Divididos basado en Granularidad con Entrega y Recogida Simultáneas (GSVRPSDP). Las características de GSVRPSDP son que las demandas de los clientes se dividen en envíos individuales y se considera tanto el volumen como el peso de cada envío. Para resolver GSVRPSDP eficientemente, se propone un algoritmo híbrido Genético-Simulado (GA-SA), en el cual el Recocido Simulado (SA) se inserta en el marco del Algoritmo Genético (GA) para mejorar las capacidades de búsqueda global de los individuos. Los resultados experimentales indican que GA-SA puede lograr costos totales de rutas más bajos en comparación con los metaalgoritmos tradicionales, como GA, SA y Optimización por Enjambre de Partículas (PSO), con una reducción de más del 10%. En el análisis adicional, se calcula la utilización del espacio y la capacidad de los vehículos, que alcanzan el 86,1% y el 88,9%, respectivamente. Estos valores son mucho más altos que los logrados por GA (71,2% y 74,8%, respectivamente) y PSO (60,9% y 65,7%, respectivamente), confirmando aún más la efectividad de GA-SA. Y la superioridad de la entrega y recogida simultáneas se demuestra al comparar con la entrega y recogida separadas. Específicamente, los costos de la entrega y recogida separadas son más de un 80% más altos que los de la entrega y recogida simultáneas.
Descripción
El Problema de Enrutamiento de Vehículos Divididos con Entrega y Recogida Simultánea (SVRPSDP) consta de dos subproblemas, es decir, el Problema de Enrutamiento de Vehículos con Entrega y Recogida Simultánea (VRPSDP) y el Problema de Enrutamiento de Vehículos con Entrega Dividida (SDVRP). En comparación con los subproblemas, SVRPSDP está mucho más cerca de la realidad. Sin embargo, algunos factores realistas aún son ignorados en SVRPSDP. Por ejemplo, los envíos están integrados y no pueden ser infinitamente subdivididos. Por lo tanto, este documento investiga el Problema de Enrutamiento de Vehículos Divididos basado en Granularidad con Entrega y Recogida Simultáneas (GSVRPSDP). Las características de GSVRPSDP son que las demandas de los clientes se dividen en envíos individuales y se considera tanto el volumen como el peso de cada envío. Para resolver GSVRPSDP eficientemente, se propone un algoritmo híbrido Genético-Simulado (GA-SA), en el cual el Recocido Simulado (SA) se inserta en el marco del Algoritmo Genético (GA) para mejorar las capacidades de búsqueda global de los individuos. Los resultados experimentales indican que GA-SA puede lograr costos totales de rutas más bajos en comparación con los metaalgoritmos tradicionales, como GA, SA y Optimización por Enjambre de Partículas (PSO), con una reducción de más del 10%. En el análisis adicional, se calcula la utilización del espacio y la capacidad de los vehículos, que alcanzan el 86,1% y el 88,9%, respectivamente. Estos valores son mucho más altos que los logrados por GA (71,2% y 74,8%, respectivamente) y PSO (60,9% y 65,7%, respectivamente), confirmando aún más la efectividad de GA-SA. Y la superioridad de la entrega y recogida simultáneas se demuestra al comparar con la entrega y recogida separadas. Específicamente, los costos de la entrega y recogida separadas son más de un 80% más altos que los de la entrega y recogida simultáneas.