In this paper we address the Two-Echelon Vehicle Routing Problem (2E-VRP), an extension of the classical Capacitated VRP, where the delivery from a single depot to the customers is managed by routing and consolidating the freight through intermediate depots called satellites. We present a family of Multi-Start heuristics based on separating the depot-to-satellite transfer and the satellite-to-customer delivery by iteratively solving the two resulting routing subproblems, while adjusting the satellite workloads that link them. The common scheme on which all the heuristics are based consists in, after having found an initial solution, applying a local search phase, followed by a diversification; if the new obtained solutions are feasible, then local search is applied again, otherwise a feasibility search procedure is applied, and if it successful, the local search is applied on the newfound solution. Different diversification strategies and feasibility search rules are proposed. We present computational results on a wide set of instances up to 50 customers and 5 satellites and compare them with results from the literature, showing how the new methods outperform previous existent methods, both in efficiency and accuracy.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Multi-start heuristics for the Two-Echelon Vehicle Routing Problem



    Erscheinungsdatum :

    2011-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629




    The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics

    Perboli, G. / Tadei, R. / Vigo, D. | British Library Online Contents | 2011



    Heuristics for Multi-Vehicle Routing Problem Considering Human-Robot Interactions

    Chirala, Venkata Sirimuvva / Sundar, Kaarthik / Venkatachalam, Saravanan et al. | IEEE | 2023


    Two-echelon vehicle routing problem with time windows and mobile satellites

    Li, Hongqi / Wang, Haotian / Chen, Jun et al. | Elsevier | 2020