An Enhanced Branch and Price Algorithm for the Time-Dependent Vehicle Routing Problem with Time Windows
Gonzalo Lera Romero  1@  , Juan Jose Miranda Bront  2, 3@  , Francisco Soulignac  3, 4, 5@  
1 : Instituto de Investigación en Ciencias de la Computación (ICC), CONICET-Universidad de Buenos Aires  (ICC)
2 : Universidad Torcuato Di Tella
3 : Consejo Nacional de Investigaciones Científicas y Técnicas  (CONICET)
4 : Departamento de Ciencia y Tecnología, Universidad Nacional de Quilmes
5 : Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires

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.

Online user: 1 RSS Feed