Abordagens heurística e exata para o problema de roteamento de veículos com caminho mínimo dependente do tempo

Abstract

In urban logistics, customers are distributed across a geographical region that typically forms a dense graph. Travel times between customers are not constant and can vary throughout the day as traffic and congestion evolve. At the urban level, different paths can be used to connect two points, and the choice of paths depends on the departure time of vehicles from a given node in the graph. In the Time-Dependent Shortest Path and Vehicle Routing Problem (TDSPVRP), several time intervals with different congestion levels are considered. The goal is to design least-cost routes to meet customer demands using vehicles of the same capacity. In TDSPVRP, travel times between two customers are determined by solving a Time-Dependent Shortest Path Problem (TDSPP). This work presents a branch-and-cut algorithm and a heuristic approach called the Hybrid Population-based Ruin-and-Recreate (HyPRR) to solve a TDSPVRP. Additionally, a new ruin-and-recreate operator for the TDSPVRP is proposed based on a recently developed procedure from the vehicle routing literature. Furthermore, an efficient strategy is introduced to evaluate and store time intervals to avoid recalculating the costs of solutions associated with a TDSPP. The proposed algorithm was tested on real-world benchmark instances, and the results show that the developed method was capable of improving several best-known solutions in highly competitive computational times. Finally, experiments were conducted to measure the impact of the time interval evaluation and storage strategy on the algorithm’s efficiency.