An Enhanced Branch and Price Algorithm for the Time-Dependent Vehicle Routing Problem with Time Windows

GONZALO LERA ROMERO; JUAN JOSÉ MIRANDA BRONT; SOULIGNAC, FRANCISCO

Sevilla

Workshop; VeRoLog 2019; 2019

EURO - The Association of European Operational Research Societies

In this paper we implement a branch and price (BP) algorithm for a time dependent vehicle routing problem with time windows in which the goal is to minimize the total route duration (DM-TDVRPTW). The travel time between two customers depends on the departure time and, thus, it need not remain fixed along the planning horizon. We propose several improvements to the exact labeling algorithm by Dabia et al.\ (Branch and price for the time-dependent vehicle routing problem with time windows, Transp. Sci. 2013; 47(3):380--396) for solving the pricing problem, while we provide a tailored implementation for the dominance tests that relies on efficient data structures for storing the enumerated labels. Computational results show that the proposed techniques are effective for accelerating the column generation step. The obtained BP algorithm is able to solve benchmark instances with up to 100 customers, being able to solve all the instances with 25 customers. Furthermore, heuristic adaptations are able to find good quality solutions in reasonable computing times, showing its potential to be applied in practice.