Variable neighborhood search for a dynamic rich vehicle routing problem with time windows

Abstract

A Dynamic Rich Vehicle Routing Problem with Time Windows has been tackled as a real-world application, in which customers requests can be either known at the beginning of the planning horizon or dynamically revealed over the day. Several real constraints, such as heterogeneous fleet of vehicles, multiple and soft time windows and customers priorities, are taken into consideration. Using exact methods is not a suitable solution for this kind of problems, given the fact that the arrival of a new request has to be followed by a quick re-optimization phase to include it into the solution at hand. Therefore, we have proposed a metaheuristic procedure based on Variable Neighborhood Search to solve this particular problem. The computational experiments reported in this work indicate that the proposed method is feasible to solve this real-world problem and competitive with the best results from the literature. Finally, it is worth mentioning that the software developed in this work has been inserted into the fleet management system of a company in Spain.