Route Minimization Heuristic for the Vehicle Routing Problem with Multiple Pauses

摘要

In this work we introduce the vehicle routing problem with multiple pauses, where the fleet is heterogeneous in terms of capacity and drivers availability. Each shift has a time intervalwhen the driver is available and a set of breaks that needs to be scheduled in the route during this shift. The objective is tominimize the number of vehicles and the travel distance. To tackle large instances,we develop a three-phase local search algorithm taking multiple breaks into account by introducing an ejection pool and randomized variable neighborhood descent as local improvement procedure. For effective break scheduling, we develop a special dynamic programming routine. Computational experiments are done on the data set provided by a delivery company situated in Novosibirsk, Russia. The instances contain 1000 customers and 30 vehicles. Experiments show effectiveness of our algorithm. It substantially reduces the fleet and travel distance.