Exact and Heuristic Solution Methods for a VRP with Time Windows and Variable Service Start Time

We consider a VRP with time windows in which the total cost of a solu- tion depends on the total duration of the vehicle routes, and the starting time for each vehicle is a decision variable. We first develop a Branch- and-Price (BP) algorithm considering the related pricing subproblem, an elementary shortest path problem with resource constraints (ESP- PRC). We discuss past, present and planned research on this exact so- lution methodology, based on a bidirectional dynamic programming approach for the ESPPRC, and on the design of a matheuristic.