Th. Athanasopoulos

The Multi-Period Vehicle Routing Problem and ITS Applications, Ph. D. Dessetation, May, 2011

In this dissertation we investigate the Multi-Period Vehicle Routing Problem with Time Windows (MPVRPTW), in which orders are related to a period window (a set of service periods). Routing costs are minimized over a planning horizon, respecting period window, time window, and capacity constraints. We present a general model and an exact approach to solve this problem based on the column generation method. We also propose two novel, efficient techniques to speed up the column generation method for obtaining lower bounds. The proposed techniques exploit the multi-period setting in order to identify similarities within the subproblems and avoid solving all subproblems at each iteration. We evaluated the performance of the proposed methods systematically for various parameters, such as customer geographical distribution and period window patterns. In most cases, the new methods improve significantly the efficiency of convergence to the optimal solution of the relaxed problem, especially in the computationally expensive test cases with wide period windows.
Integer optimal solutions to the MPVRPTW are provided through a branch-and-price implementation. We propose two strategies that consider the multi-period characteristics of the problem, in addition to a simple pruning heuristic that speeds up the solution procedure and provides efficient results.
For solving the MPVRPTW in long-term horizons, we propose a rolling horizon framework. Initially, we discuss three theoretical statements that provide insights on the effects of the planning and implementation horizons in the final solutions. Subsequently, in order to apply rolling horizon routing, we propose significant modifications to the model and the solution approach for the MPVRP; these modifications concern the ability to postpone serving customers for later periods. We investigate two rolling horizon settings (quasi-static and dynamic) and we establish the recommended values for the planning and implementation horizons, under a wide range of parameters, such as customer geographical distribution and time window width.
Finally, we address a practical variation, which regards a hybrid service policy that includes (a) inflexible (pre-assigned to specific vehicles) and (b) flexible customer orders. For this case, we propose the necessary modifications to the MPVRP model and solution approach. Extensive experiments show that significant cost savings can be achieved by considering longer planning horizons in the planning process.