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

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

Ciudad Autónoma de Buenos Aires

Workshop; MIPAR 2018; 2018

Departamento de Computación, FCEyN, UBA

Traditionally, most of the variations of the vehicle routing problem (VRP) assume that travel times (or distances, or costs) are time independent, meaning that they remain fixed along the planning horizon. However, in practice the problem is much more complex and the operations are heavily affected by the congestion, especially in large populated areas. The time dependent vehicle routing problem with time windows (DM-TDVRPTW) addresses a key aspect regarding the impact of congestion in terms of the feasibility and efficiency of a route, in particular related to the time in which a customer must be visited. In this paper, we build upon previous research by providing the details of a tailored implementation for an enhanced Branch and Price (BP) algorithm for the DM-TDVRPTW. We conduct an extensive set of experiments and the results show that our approach reduces the computational times dramatically and increases significantly the number of instances solved to optimality from a set of benchmark instances considered previously in the literature, suggesting its potential to be used in practice.