An enhanced branch and price algorithm for the time-dependent vehicle routing problem with time windows

GONZALO LERA-ROMERO; JUAN JOSÉ MIRANDA-BRONT; FRANCISCO J. SOULIGNAC

Buenos Aires

Workshop; Tercer workshop argentino de programación entera y combinatoria poliedral; 2018

Departamento de Computación, FCEN, Universidad de Buenos Aires

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.