IDEAS home Printed from https://ideas.repec.org/a/hin/jnlmpe/517467.html
   My bibliography  Save this article

A Hybrid GRASP+VND Heuristic for the Two-Echelon Vehicle Routing Problem Arising in City Logistics

Author

Listed:
  • Zheng-yang Zeng
  • Wei-sheng Xu
  • Zhi-yu Xu
  • Wei-hui Shao

Abstract

The two-echelon vehicle routing problem (2E-VRP) is a variant of the classical vehicle routing problem (VRP) arising in two-level transportation systems such as those encountered in the context of city logistics. In the 2E-VRP, freight from a depot is compulsorily delivered through intermediate depots, named satellites. The first echelons are routes that distribute freight from depot to satellites, and the second are those from satellites to customers. This problem is solved by a hybrid heuristic which is composed of a greedy randomized adaptive search procedure (GRASP) with a route-first cluster-second procedure embedded and a variable neighborhood descent (VND), called GRASP+VND hereafter. Firstly, an extended split algorithm in the GRASP continuously splits randomly generated permutations of all customers and assigns customers to satellites reasonably until a feasible assignment appears, and a complete 2E-VRP feasible solution is obtained by solving the first echelon problem subsequently and, secondly, a VND phase attempts to improve this solution until no more improvements can be found. The process above is iterated until the maximum number of iterations is reached. Computational tests conducted on three sets of benchmark instances from the literature show that our algorithm is both effective and efficient and outperforms the best existing heuristics for the 2E-VRP.

Suggested Citation

  • Zheng-yang Zeng & Wei-sheng Xu & Zhi-yu Xu & Wei-hui Shao, 2014. "A Hybrid GRASP+VND Heuristic for the Two-Echelon Vehicle Routing Problem Arising in City Logistics," Mathematical Problems in Engineering, Hindawi, vol. 2014, pages 1-11, April.
  • Handle: RePEc:hin:jnlmpe:517467
    DOI: 10.1155/2014/517467
    as

    Download full text from publisher

    File URL: http://downloads.hindawi.com/journals/MPE/2014/517467.pdf
    Download Restriction: no

    File URL: http://downloads.hindawi.com/journals/MPE/2014/517467.xml
    Download Restriction: no

    File URL: https://libkey.io/10.1155/2014/517467?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    2. Sebastián Dávila & Miguel Alfaro & Guillermo Fuertes & Manuel Vargas & Mauricio Camargo, 2021. "Vehicle Routing Problem with Deadline and Stochastic Service Times: Case of the Ice Cream Industry in Santiago City of Chile," Mathematics, MDPI, vol. 9(21), pages 1-18, October.
    3. Li, Jiliu & Xu, Min & Sun, Peng, 2022. "Two-echelon capacitated vehicle routing problem with grouping constraints and simultaneous pickup and delivery," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 261-291.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hin:jnlmpe:517467. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Mohamed Abdelhakeem (email available below). General contact details of provider: https://www.hindawi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.