2010 Msc. Thesis Title:  Single Vehicle Routing With Predefined Sequence and Multiple Depot Returns: The Case of Two Depots

This thesis examines three interesting cases of the single vehicle routing problem with a predefined client sequence and two load replenishment depots. The cases studied vary with respect to the inventory availability at each depot. Given the location and demand of the clients, we seek the minimum cost route, which includes optimal load replenishment at the depots in order to fully satisfy the client demand. For each case, two solution approaches have been developed: i) A Dynamic Programming algorithm, which obtains the optimal solution for all cases, and ii) a Labeling Algorithm that obtains the optimal solution for the first two cases, and efficient solutions for the third, and most complex, one. The computational efficiency of the two algorithms is studied by solving a wide range of problem instances.

Keywords: Single Vehicle Routing; Multiple Depot Routing, Dynamic Programming for the VRP, Labeling Algorithm for the VRP