An adaptive large neighborhood search heuristic for dynamic vehicle routing problems

The vehicle routing in real-life transportation, distribution and logistics may change with time, especially when there is existing technology that can produce real-time routing data. In this paper, a metaheuristic procedure based on an Adaptive Large Neighborhood Search (ALNS) algorithm is proposed to solve the Dynamic Vehicle Routing Problem (DVRP) with limited vehicles and hard-time windows. The ALNS involves ad hoc destroy/repair heuristics and a periodic perturbation procedure. In addition, an efficient feasibility check has been designed for inserting customer. By conducting several computational experiments with Lackner's benchmark, we show that the present approach can solve real-time problems within a very short time while improving the quality of the solution. The average number of vehicles is smaller than that of existing algorithms, the maximum average error of the vehicle traveling distance is reduced, and the average computation time remains the same.