Comparación de operadores genéticos para el problema de recogida y entrega multiobjetivo
Autores: Little, Connor; Choudhury, Salimur; Hu, Ting; Salomaa, Kai
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Comparación de operadores genéticos para el problema de recogida y entrega multiobjetivo
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Recogida
Entrega
Algoritmo genético
Multiobjetivo
Capacitado
Distancia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 19
Citaciones: Sin citaciones
El problema de recogida y entrega es un problema pertinente en nuestro mundo interconectado. Poder mover bienes y personas de manera eficiente puede llevar a reducciones en costos, emisiones y tiempo. En este trabajo, creamos un algoritmo genético para resolver el problema de recogida y entrega capacitado multiobjetivo, adaptando benchmarks comúnmente utilizados. El objetivo es minimizar la distancia total recorrida y el número de vehículos utilizados. Basándonos en NSGA-II, exploramos cómo diferentes mutaciones interruta e intrarruta afectan la solución final. Introducimos 6 operaciones interruta y 16 operaciones intrarruta y calculamos el hipervolumen medido para comparar directamente su impacto. También introducimos dos operadores de cruce diferentes especializados para este problema. Nuestra metodología pudo encontrar resultados óptimos en el 23% de las instancias en el primer benchmark y, en la mayoría de las otras instancias, pudo generar un frente de Pareto con a lo sumo un vehículo y +20% de la mejor distancia conocida. Con múltiples soluciones, permite a los usuarios elegir las rutas que mejor se adapten a sus necesidades.
Descripción
El problema de recogida y entrega es un problema pertinente en nuestro mundo interconectado. Poder mover bienes y personas de manera eficiente puede llevar a reducciones en costos, emisiones y tiempo. En este trabajo, creamos un algoritmo genético para resolver el problema de recogida y entrega capacitado multiobjetivo, adaptando benchmarks comúnmente utilizados. El objetivo es minimizar la distancia total recorrida y el número de vehículos utilizados. Basándonos en NSGA-II, exploramos cómo diferentes mutaciones interruta e intrarruta afectan la solución final. Introducimos 6 operaciones interruta y 16 operaciones intrarruta y calculamos el hipervolumen medido para comparar directamente su impacto. También introducimos dos operadores de cruce diferentes especializados para este problema. Nuestra metodología pudo encontrar resultados óptimos en el 23% de las instancias en el primer benchmark y, en la mayoría de las otras instancias, pudo generar un frente de Pareto con a lo sumo un vehículo y +20% de la mejor distancia conocida. Con múltiples soluciones, permite a los usuarios elegir las rutas que mejor se adapten a sus necesidades.