Algoritmos genéticos paralelos para resolver el problema de rutas de vehículos con ventanas de tiempo - Flores González, Maribel (Universidad Autónoma Metropolitana, 2018)
El problema de rutas de vehículos (VRP por sus siglas en inglés ), consiste en obtener las rutas de costo mínimo para la entrega de productos, a un conjunto de clientes que se encuentran dispersos geográficamente. Este problema es de gran interés por la comunidad científica por los beneficios que representa, y por los beneficios que brinda en el sector industrial, comercial y de servicio. El VRP tiene variantes que se clasifican de acuerdo a ciertas restricciones, una de ellas es el problema de rutas de vehículos con ventanas de tiempo (VRPTW, por sus siglas en inglé s), que es en el que enfocamos esta investigación. En este trabajo se presenta un modelo paralelo de un algoritmo genético, para resolver casos de prueba del VRPTW. Este algoritmo realiza una exploración en el espacio de búsqueda para encontrar soluciones que minimizan el número de rutas y la distancia recorrida, el cual es el objetivo del pro blema. Para la parte del modelo paralelo se utilizó el paradigma de paso de mensajes mediante la biblioteca MPI (Message Passing Interface). Los resultados obtenidos del algoritmo en paralelo para el VRPTW, se compararon con más de cincuenta casos de prue ba disponibles p ú blicamente (ver anexo tabla de resultados) . Las soluciones obtenidas son comparables en términos de calidad de la solución , y tiempo computacional respecto al desempeño de la versión secuencial.