IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v57y2023i2p482-511.html
   My bibliography  Save this article

General Edge Assembly Crossover-Driven Memetic Search for Split Delivery Vehicle Routing

Author

Listed:
  • Pengfei He

    (Laboratoire d’Etude et de Recherche en Informatique d’Angers, Université d’Angers, 49045 Angers, France)

  • Jin-Kao Hao

    (Laboratoire d’Etude et de Recherche en Informatique d’Angers, Université d’Angers, 49045 Angers, France)

Abstract

The split delivery vehicle routing problem is a variant of the well-known vehicle routing problem, where each customer can be visited by several vehicles. The problem has many practical applications, but it is computationally challenging. This paper presents an effective memetic algorithm for solving the problem with a fleet of limited or unlimited vehicles. The algorithm features a general edge assembly crossover to generate promising offspring solutions from the perspective of assembling suitable edges and an effective local search to improve each offspring solution. The algorithm is further reinforced by a feasibility-restoring procedure, a diversification-oriented mutation, and a quality-and-distance pool updating technique. Extensive experiments on 324 benchmark instances indicate that our algorithm is able to update 143 best upper bounds in the literature and match the best results for 156 other instances. Additional experiments are presented to obtain insight into the roles of the key search ingredients of the algorithm. The method was ranked second in the SDVRP track at the 12th DIMACS Implementation Challenge on Vehicle Routing Problems.

Suggested Citation

  • Pengfei He & Jin-Kao Hao, 2023. "General Edge Assembly Crossover-Driven Memetic Search for Split Delivery Vehicle Routing," Transportation Science, INFORMS, vol. 57(2), pages 482-511, March.
    • Handle: RePEc:inm:ortrsc:v:57:y:2023:i:2:p:482-511
    DOI: 10.1287/trsc.2022.1180
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2022.1180
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2022.1180?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
    ---><---

    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:inm:ortrsc:v:57:y:2023:i:2:p:482-511. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.