Abstract 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 interval when the driver is available and a set of breaks that needs to be scheduled in the route during this shift. The objective is to minimize 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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Route Minimization Heuristic for the Vehicle Routing Problem with Multiple Pauses

    Khmelev, Alexey | British Library Conference Proceedings | 2015


    Vehicle Routing Problem for Emissions Minimization

    Figliozzi, Miguel | Transportation Research Record | 2010


    Vehicle Routing Problem for Emissions Minimization

    Figliozzi, Miguel | Online Contents | 2010


    A GA Based Heuristic for the Vehicle Routing Problem with Multiple Trips

    Salhi, S. / Petch, R. J. | British Library Online Contents | 2007


    Reoptimization Heuristic for the Capacitated Vehicle Routing Problem

    Rodrigo Linfati / John Willmer Escobar | DOAJ | 2018

    Free access