A variable neighborhood tabu search algorithm for the Vehicle Routing Problem with Multiple Time Windows
Maaike Hoogeboom  1@  , Wout Dullaert  1@  , David Lai  1@  , Daniele Vigo  2@  
1 : VU University Amsterdam  -  Website
Main building VU University Amsterdam De Boelelaan 1105 1081 HV Amsterdam The Netherlands -  Netherlands
2 : Università di Bologna  (UNIBO)  -  Website
Via Zamboni, 33 - 40126 Bologna -  Italy

In the Vehicle Routing Problem with Multiple Time Windows (VRPMTW) every customer has to be served in one of its k time windows. Our objective is to minimize the total duration (total travel time + total waiting time) by selecting an optimal combination of time windows and determining vehicle routes. Existing efficient metaheuristic developed for the VRP with Time Windows often involve insertion and removal of customers from the vehicle routes of the current solution. In the presence of multiple time windows, local search operations used for the VRPTW become more challenging: for a vehicle route of n customers there could be k^n possible combinations of time windows. In this research we present a polynomial time algorithm to efficiently determine the optimal time window combination whenever a neighborhood operation is applied.

To check if a solution is feasible and to calculate the minimal route duration, we introduce Forward and Backward Start Intervals. These intervals represent the start times of servicing a customer such that the preceding (following) customers in the route are all served in one of their time windows. A variable neighborhood tabu search algorithm is developed and compared to best-known solutions on VRPMTW instances from the literature. At the conference we will show detailed computational results and we will examine the trade-off between minimizing the total duration and minimizing the travel time.


Online user: 1