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.