Resumen

La solución a un contexto dinámico del Problema de Encaminamiento de Vehículos Capacitados (CVRP) es un reto. Es necesario tomar decisiones de enrutamiento y reabastecimiento considerando la asignación de clientes a vehículos cuando la información se revela gradualmente a lo largo del horizonte temporal. El procedimiento para resolver este tipo de problemas se denomina reoptimización de rutas, que es la mejor opción para minimizar el coste de transporte esperado sin incurrir en fallos de demanda insatisfecha en una ruta. Este trabajo propone un algoritmo heurístico para la reoptimización de CVRP en el que el número de clientes aumenta. El algoritmo utiliza las métricas de rendimiento propuestas para reducir la dispersión de las rutas y minimizar su longitud. La solución inicial se genera utilizando el algoritmo de ahorro y luego se mejora utilizando la metaheurística de viajes Record-to-Record. Al incluir o reducir nuevos clientes en el sistema, se realiza una reoptimización que considera fijos los nodos y aristas visitados. La optimización del algoritmo se implementa jerárquicamente minimizando primero la dispersión y luego la distancia. A continuación, se ejecuta el procedimiento de búsqueda local para mejorar la solución. Se realiza una optimización clásica en todas las instancias utilizando la información de los clientes originales y nuevos para su posterior comparación con el fin de minimizar la distancia. La eficacia del algoritmo propuesto se validó utilizando casos reales de la literatura. Los resultados son prometedores y muestran la eficacia del método propuesto para resolver el problema considerado utilizando procedimientos de reoptimización con el fin de lograr buenos ratios de aproximación en tiempos de computación cortos.

• Materias:Planificación de la producción Infraestructura de transportes Ingeniería del transporte Seguridad del transporte Planificación de ruta Capacidad de tráfico
• Subjects:Production planning Transport infrastructure Transport engineering Transport safety Path planning Traffic capacity
• Palabras claves:algoritmo, nuevos clientes, problema capacitado de encaminamiento de vehículos, buenos coeficientes de aproximación, procedimiento de búsqueda local, tiempos de cálculo cortos, cvrp, clientes, distancia, información
• Keywords:algorithm, new customers, capacitated vehicle routing problem, good approximation ratios, local search procedure, short computing times, cvrp, customers, distance, information