A Real-World Multi-Depot, Multi-Period, and Multi-Trip Vehicle Routing Problem with Time Windows

Rich vehicle routing problems frequently arise in real-world applications. The related literature is trying to effectively address many of them, considering all their constraints and the need to solve large practical instances. In this paper, we handle a rich vehicle routing problem that emerges from an Italian service provider company operating in the delivery of pharmaceutical products. This problem is characterized by constraints that include multiple depots, periods, and trips, as well as specific time windows, customer-vehicle incompatibilities, and restrictions on vehicle working hours. To solve this problem, we propose a two-phase decomposition approach. In the first phase, we generate a set of trips that satisfy all problem constraints for a single period. Then, in the second phase, three algorithms based, respectively, on a greedy heuristic, a variable neighbourhood search metaheuristic, and a mixed integer linear programming model are tested to combine the generated trips into routes for the overall set of periods. Computational results on real-world instances show that the model hits the one-hour time limit for cases with more than 150 trips. The metaheuristic algorithm performs better in terms of objective function value. The greedy algorithm is faster but is outperformed by the other methods in terms of solution quality.