IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v57y2023i2p482-511.html

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
    ---><---

    References listed on IDEAS

    as
    1. Rafael E. Aleman & Xinhui Zhang & Raymond R. Hill, 2009. "A ring-based diversification scheme for routing problems," International Journal of Mathematics in Operational Research, Inderscience Enterprises Ltd, vol. 1(1/2), pages 163-190.
    2. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1994. "A Tabu Search Heuristic for the Vehicle Routing Problem," Management Science, INFORMS, vol. 40(10), pages 1276-1290, October.
    3. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    4. Leonardo Berbotto & Sergio García & Francisco Nogales, 2014. "A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem," Annals of Operations Research, Springer, vol. 222(1), pages 153-173, November.
    5. J. M. Belenguer & M. C. Martinez & E. Mota, 2000. "A Lower Bound for the Split Delivery Vehicle Routing Problem," Operations Research, INFORMS, vol. 48(5), pages 801-810, October.
    6. Pedro Munari & Martin Savelsbergh, 2022. "Compact Formulations for Split Delivery Routing Problems," Transportation Science, INFORMS, vol. 56(4), pages 1022-1043, July.
    7. Thibaut Vidal & Teodor Gabriel Crainic & Michel Gendreau & Nadia Lahrichi & Walter Rei, 2012. "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, INFORMS, vol. 60(3), pages 611-624, June.
    8. Claudia Archetti & M. Grazia Speranza & Martin W. P. Savelsbergh, 2008. "An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 42(1), pages 22-31, February.
    9. U Derigs & B Li & U Vogel, 2010. "Local search-based metaheuristics for the split delivery vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(9), pages 1356-1364, September.
    10. Moshe Dror & Pierre Trudeau, 1990. "Split delivery routing," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(3), pages 383-402, June.
    11. Fred Glover & Jin-Kao Hao, 2011. "The case for strategic oscillation," Annals of Operations Research, Springer, vol. 183(1), pages 163-173, March.
    12. Chen, Yuning & Hao, Jin-Kao & Glover, Fred, 2016. "A hybrid metaheuristic approach for the capacitated arc routing problem," European Journal of Operational Research, Elsevier, vol. 253(1), pages 25-39.
    13. C Archetti & M G Speranza, 2004. "Vehicle routing in the 1-skip collection problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(7), pages 717-727, July.
    14. Archetti, Claudia & Bianchessi, Nicola & Speranza, M. Grazia, 2014. "Branch-and-cut algorithms for the split delivery vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 685-698.
    15. Yuichi Nagata & Shigenobu Kobayashi, 2013. "A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 346-363, May.
    16. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "A unified solution framework for multi-attribute vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 658-673.
    17. Jianli Shi & Jin Zhang & Kun Wang & Xin Fang, 2018. "Particle Swarm Optimization for Split Delivery Vehicle Routing Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(02), pages 1-42, April.
    18. Moshe Dror & Pierre Trudeau, 1989. "Savings by Split Delivery Routing," Transportation Science, INFORMS, vol. 23(2), pages 141-145, May.
    19. Gizem Ozbaygin & Oya Karasan & Hande Yaman, 2018. "New exact solution approaches for the split delivery vehicle routing problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 85-115, March.
    20. Michael Schneider & Maximilian Löffler, 2019. "Large Composite Neighborhoods for the Capacitated Location-Routing Problem," Service Science, INFORMS, vol. 53(1), pages 301-318, February.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Weibo Lin & Zhu He & Shibiao Jiang & Fuda Ma & Zhouxing Su & Zhipeng Lü, 2026. "Alkaid-SDVRP: An Efficient Open-Source Solver for the Vehicle Routing Problem with Split Deliveries," INFORMS Journal on Computing, INFORMS, vol. 38(1), pages 150-164, January.
    2. Archetti, C. & Coelho, L.C. & Speranza, M.G. & Vansteenwegen, P., 2026. "Beyond fifty years of vehicle routing: Insights into the history and the future," European Journal of Operational Research, Elsevier, vol. 330(2), pages 355-372.
    3. Mette Gamst & Richard Martin Lusby & Stefan Ropke, 2024. "Exact and Heuristic Methods for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 58(4), pages 741-760, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mette Gamst & Richard Martin Lusby & Stefan Ropke, 2024. "Exact and Heuristic Methods for the Split Delivery Vehicle Routing Problem," Transportation Science, INFORMS, vol. 58(4), pages 741-760, July.
    2. Bortfeldt, Andreas & Yi, Junmin, 2020. "The Split Delivery Vehicle Routing Problem with three-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 282(2), pages 545-558.
    3. Leonardo Berbotto & Sergio García & Francisco Nogales, 2014. "A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem," Annals of Operations Research, Springer, vol. 222(1), pages 153-173, November.
    4. Jianli Shi & Jin Zhang & Kun Wang & Xin Fang, 2018. "Particle Swarm Optimization for Split Delivery Vehicle Routing Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(02), pages 1-42, April.
    5. Weibo Lin & Zhu He & Shibiao Jiang & Fuda Ma & Zhouxing Su & Zhipeng Lü, 2026. "Alkaid-SDVRP: An Efficient Open-Source Solver for the Vehicle Routing Problem with Split Deliveries," INFORMS Journal on Computing, INFORMS, vol. 38(1), pages 150-164, January.
    6. Berbotto, Leonardo & García, Sergio & Nogales, Francisco J., 2011. "A vehicle routing model with split delivery and stop nodes," DES - Working Papers. Statistics and Econometrics. WS ws110906, Universidad Carlos III de Madrid. Departamento de Estadística.
    7. Luis Gouveia & Markus Leitner & Mario Ruthmair, 2023. "Multi-Depot Routing with Split Deliveries: Models and a Branch-and-Cut Algorithm," Transportation Science, INFORMS, vol. 57(2), pages 512-530, March.
    8. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    9. Pedro Munari & Martin Savelsbergh, 2022. "Compact Formulations for Split Delivery Routing Problems," Transportation Science, INFORMS, vol. 56(4), pages 1022-1043, July.
    10. Isaac Balster & Teobaldo Bulhões & Pedro Munari & Artur Alves Pessoa & Ruslan Sadykov, 2023. "A New Family of Route Formulations for Split Delivery Vehicle Routing Problems," Transportation Science, INFORMS, vol. 57(5), pages 1359-1378, September.
    11. Han, Anthony Fu-Wha & Chu, Yu-Ching, 2016. "A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 11-31.
    12. Gizem Ozbaygin & Oya Karasan & Hande Yaman, 2018. "New exact solution approaches for the split delivery vehicle routing problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 85-115, March.
    13. Toni Pacheco & Rafael Martinelli & Anand Subramanian & Túlio A. M. Toffolo & Thibaut Vidal, 2023. "Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman Problem," Transportation Science, INFORMS, vol. 57(2), pages 463-481, March.
    14. Schneider, Michael & Schwahn, Fabian & Vigo, Daniele, 2017. "Designing granular solution methods for routing problems with time windows," European Journal of Operational Research, Elsevier, vol. 263(2), pages 493-509.
    15. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2016. "An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 95-123.
    16. Lavigne, Carolien & Inghels, Dirk & Dullaert, Wout & Dewil, Reginald, 2023. "A memetic algorithm for solving rich waste collection problems," European Journal of Operational Research, Elsevier, vol. 308(2), pages 581-604.
    17. Michael Drexl, 2014. "A Generic Heuristic for Vehicle Routing Problems with Multiple Synchronization Constraints," Working Papers 1412, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 04 Nov 2014.
    18. Jeffrey W. Ohlmann & Michael J. Fry & Barrett W. Thomas, 2008. "Route Design for Lean Production Systems," Transportation Science, INFORMS, vol. 42(3), pages 352-370, August.
    19. Nicola Bianchessi & Stefan Irnich, 2016. "Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows," Working Papers 1620, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    20. Archetti, C. & Coelho, L.C. & Speranza, M.G. & Vansteenwegen, P., 2026. "Beyond fifty years of vehicle routing: Insights into the history and the future," European Journal of Operational Research, Elsevier, vol. 330(2), pages 355-372.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    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: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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.