Abstract The most common approaches to solve the variants of the well-known vehicle routing problem are based on metaheuristic hill-climbing search. The deficiency of these methods is slow local search based hill climbing that often is restricted to limited local neighborhood. In this paper we suggest a novel new two-phase metaheuristic that escapes the local minima with jumps of varying size, instead of step by step local hill climbing. The initial solution is first generated with a powerful ejection pool heuristic. The key idea of the improvement phase is to combine large neighborhood search with standard guided local search metaheuristic in a novel way, allowing improved search diversification and escape from local minima in more efficient way through jumps. The algorithm has been tested on the standard Gehring and Homberger benchmarks for the vehicle routing problem with time windows and the results indicate very competitive performance. We found 12 new and 43 matched best-known solutions and the best overall results for all problem sizes at comparable computation times.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Why to Climb If One Can Jump: A Hill Jumping Algorithm for the Vehicle Routing Problem with Time Windows


    Contributors:


    Publication date :

    2017-06-30


    Size :

    10 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English




    Why to Climb If One Can Jump: A Hill Jumping Algorithm for the Vehicle Routing Problem with Time Windows

    Mester, David / Bräysy, Olli / Dullaert, Wout | British Library Conference Proceedings | 2018


    Gaillon hill climb

    Engineering Index Backfile | 1903


    Hill to Climb

    Foran, Pat | IuD Bahn | 2009


    Clustering algorithm for a vehicle routing problem with time windows

    Thi Diem Chau Le / Duc Duy Nguyen / Judit Oláh et al. | DOAJ | 2022

    Free access

    Solving Vehicle Routing Problem with Time Windows by Genetic Algorithm

    Jiang, D. / Zhang, M. / Wang, F. et al. | British Library Conference Proceedings | 2002