The Vehicle Routing Problem with Time Windows: Minimizing Route Duration (Q4030786)

The vehicle routing problem (VRP) is considered, seen as a travelling salesman problem (TSP) with time windows. The objective is to minimize route duration while serving each customer within the predefined time interval (time window). The author generalizes and extends the edge-exchange improvement method of the TSP and shows that applied to the VRP problem with time windows it does not increase the computing complexity. The key issues in the proposed algorithm are: the lexicographic search strategy in edge exchanges and the choice of the set of global variables to test the feasibility and profitability of actual exchange. A theorem is proved enabling the calculation of the forward slack time (i.e. the maximum possible delay of the departure time of a vertex which does not yet affect feasibility of the path). Also some numerical examples are discussed, showing the robustness of the method.