Implementación de un algoritmo metaheurístico para la solución de un problema de programación de transporte terrestre internacional

Abstract

Resumen: Este trabajo se enfoca en dar solución a un problema real de planificación de transportes o ruteo de vehículos, definido gracias al aporte de una empresa colombiana del sector de servicios de transporte por carretera. El problema consiste en realizar la programación de operaciones de transporte internacional entre dos países, Colombia y Venezuela, para un horizonte de tiempo con múltiples variantes; entre ellas podemos resaltar: una flota heterogénea de vehículos y tráileres, múltiples depots (clientes), restricciones de ventanas de tiempo en los depots, diversas modalidades de servicio, entre otras. El objetivo es obtener una programación de recursos (vehículos y tráileres) para la atención de la demanda de solicitudes de servicios de transportes en un horizonte de tiempo, minimizando la distancia recorrida en estado vacío de los vehículos para el periodo. La solución se realizó a través de la implementación de la metaheurística Recocido Simulado (SA, Simulated Annealing), la cual se probó iniciando con soluciones factibles generadas por dos algoritmos heurísticos; el primero se basa en la heurística clásica conocida como el vecino más cercano y el segundo genera soluciones de forma aleatoria. Los resultados del Recocido Simulado usando las soluciones generadas con el primer algoritmo, no mostraron una mejora frente a dicha solución inicial, contrario a lo hallado con el uso de las soluciones del segundo método, donde se alcanzó hasta cerca de un 50% de mejora

Abstract: This work focuses on finding a solution to a real problem of transport planning or vehicle routing, which has been defined with the collaboration of a Colombian company from the road transport service industry. The problem consists of scheduling the international transport operations between two countries, Colombia and Venezuela, over a time horizon, with multiple variants; such as: a heterogeneous fleet of vehicles and trailers, multiple depots (customers), time windows constraints in the depots, various service modalities, among others. The goal is to schedule the resources (vehicles and trailers) in order to meet the demand for transport service requests on a given time horizon, minimizing the distance traveled by the vehicles while empty. A solution to the problem is given by a Simulated Annealing (SA) Metaheuristic, which was tested by using two types of heuristics to generate the initial feasible solution; the first one is based on the classic “Nearest Neighbor” heuristic, while the second one generates random feasible solutions. The results of the Simulated Annealing using the first algorithm to generate the initial solution did not show any improvement over it, contrary to what was found by using the second method, which obtained up to around 50% of improvement