Simple heuristics and local search procedures are important components of metaheuristics for vehicle routing problems (VRP). This chapter presents a few classical heuristics before explaining the principles of local search, taking the capacitated VRP (CVRP) as the main example. Many constructive methods for the CVRP are obtained by modifying a traveling salesman problem (TSP) heuristic to build several routes. Two fruitful techniques can improve solution quality of simple heuristics, before resorting to local search. The first one is the best of method. The second technique is randomization. This idea is to introduce some randomness into the decisions of the original deterministic heuristic. The chapter also gives the general structure of a local search, presents classical moves and discusses important issues such as feasibility tests, genericity, multiple neighborhoods, very constrained problems, complex moves and acceleration techniques.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Simple Heuristics and Local Search Procedures


    Contributors:


    Publication date :

    2016-03-30


    Size :

    23 pages




    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English




    Simulated Route Decision Behaviour: Simple Heuristics and Adaptation

    Klugl, F. / Bazzan, A. L. C. | British Library Conference Proceedings | 2004


    Keeping Procedures Simple

    Parry, D. | British Library Online Contents | 1996


    OPTIMAL SEARCH PROCEDURES

    Posner, E. C. | NTRS | 1963



    Models and Tabu Search Heuristics for the Berth-Allocation Problem

    Cordeau, Jean-François | Online Contents | 2005