Desarrollo de un algoritmo metaheurístico para un sistema de ruteo de vehículos con tiempos de viaje estocásticos y ventanas de tiempo suave

Abstract

La presente investigación, describe la metodología para la construcción de un algoritmo que resuelva el problema de ruteo con tiempos de viaje estocástico y ventanas de tiempo de forma suave (VRPSTTW) implementando diversas técnicas de optimización y métodos estadísticos con el objetivo de reducir los costos utilizados en cada recorrido. Esto permitirá establecer un plan de ruta para todos los vehículos si se quiere abastecer a un número de clientes de una manera más precisa. Se tomó como referencia investigaciones previas que resolvieran alguna variante del VRP para establecer una metodología adecuada, así como las formulaciones matemáticas existentes del VRP descritas en la literatura. Para realizar la investigación, se utilizó el método de programación matemática en el campo de la investigación de operaciones. Este enfoque es especialmente adecuado para resolver problemas de optimización que demandan un alto procesamiento computacional debido a su complejidad combinatoria, implicando la maximización o minimización de una función objetivo sujeta a restricciones. Además, se empleó un diseño experimental para manipular las variables del algoritmo, permitiendo establecer ajustes, mejoras y obtener un mejor entendimiento del comportamiento de nuestras soluciones. Para la solución del VRPSTTW se plasmaron diversos diagramas de flujo que describen el proceso y marcan la pauta para las funciones establecidas, tomando como punto de partida la definición de nuestro tiempo de viaje estocástico. Aquí se realizó una captura robusta de la data histórica de tiempos de viaje y con técnicas estadísticas establecemos una variabilidad de tiempos con respecto a escenarios como lo son las horas punta de tráfico o los días laborables. Se dio uso de la metaheurística “Recocido Simulado” para resolver el problema del VRPSTTW, en base a la literatura existente sobre técnicas de optimización, a su vez respetando las restricciones de la formulación matemática respectiva. La implementación del algoritmo se realizó utilizando el lenguaje de programación Python, que es de código abierto. Para una interfaz amigable con el usuario, se empleó HTML, lo cual permite capturar con gran facilidad la formulación del problema a resolver. Esta interfaz maneja mapas en tiempo real, facilitando la digitación de coordenadas y el establecimiento de rutas, además de incluir un apartado que describe el plan de ruta. Después de construir el algoritmo, se procedió a su verificación, calibración y validación basada en los resultados, concluyendo que es un algoritmo robusto y confiable. Al determinar los valores óptimos de los factores del algoritmo, se observó que los resultados tienden a estabilizarse, mostrando soluciones óptimas y precisas en cada ejecución del mismo problema. Incluso cuando se realizan ligeras modificaciones en los valores de los factores dentro del margen de sus puntos óptimos, las soluciones siguen siendo consistentes. Durante las pruebas, se obtuvieron soluciones sin errores, lo que confirma la fiabilidad y precisión del algoritmo desarrollado.