IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i4p974-986.html

AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-Scale Capacitated Vehicle Routing Problem

Author

Listed:
  • Vinícius R. Máximo

    (Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo (UNIFESP), São José dos Campos-SP 12247-014, Brazil)

  • Jean-François Cordeau

    (HEC Montreal, Montreal, Quebec H3T 2A7, Canada; GERAD, Montreal, Quebec H3T 2A7, Canada)

  • Mariá C. V. Nascimento

    (Divisão de Ciência da Computação (IEC), Instituto Tecnológico de Aeronáutica (ITA), São José dos Campos-SP 12228-900, Brazil)

Abstract

A recent study on the classical capacitated vehicle routing problem (CVRP) introduced an adaptive version of the widely used iterated local search paradigm, hybridized with a path-relinking (PR) strategy. The solution method, called adaptive iterated local search (AILS)-PR, outperformed existing meta-heuristics for the CVRP on benchmark instances. However, tests on large-scale instances suggest that PR is too slow, making AILS-PR less advantageous in this case. To overcome this challenge, this paper presents an AILS combined with mechanisms to handle large CVRP instances, called AILS-II. The computational cost of this implementation is reduced, whereas the algorithm also searches the solution space more efficiently. AILS-II is very competitive on smaller instances, outperforming the other methods from the literature with respect to the average gap to the best-known solutions. Moreover, AILS-II consistently outperforms the state of the art on larger instances with up to 30,000 vertices.

Suggested Citation

  • Vinícius R. Máximo & Jean-François Cordeau & Mariá C. V. Nascimento, 2024. "AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-Scale Capacitated Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 36(4), pages 974-986, July.
    • Handle: RePEc:inm:orijoc:v:36:y:2024:i:4:p:974-986
    DOI: 10.1287/ijoc.2023.0106
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2023.0106
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2023.0106?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. Jan Christiaens & Greet Vanden Berghe, 2020. "Slack Induction by String Removals for Vehicle Routing Problems," Transportation Science, INFORMS, vol. 54(2), pages 417-433, March.
    2. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    3. Máximo, Vinícius R. & Nascimento, Mariá C.V., 2021. "A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1108-1119.
    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. Mirbeygishahabad, Mohammadjalal & Najafi, Mehdi & Zolfagharinia, Hossein, 2025. "From imperfection to advantage: Quantifying the benefits of imperfect advance load information for multi-truck carriers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 201(C).

    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. 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.
    2. Zhou, Fangting & Lischka, Attila & Kulcsár, Balázs & Wu, Jiaming & Haghir Chehreghani, Morteza & Laporte, Gilbert, 2025. "Learning for routing: A guided review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 202(C).
    3. Schaumann, Sarah K. & Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2023. "Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics," European Journal of Operational Research, Elsevier, vol. 311(1), pages 88-111.
    4. Martin Simensen & Geir Hasle & Magnus Stålhane, 2022. "Combining hybrid genetic search with ruin-and-recreate for solving the capacitated vehicle routing problem," Journal of Heuristics, Springer, vol. 28(5), pages 653-697, December.
    5. Máximo, Vinícius R. & Nascimento, Mariá C.V., 2021. "A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1108-1119.
    6. Yang, Kai & Zhang, Zhenzhen & Zhao, Jingyi & Liang, Zhe, 2025. "A neighborhood-based matheuristic for the vehicle routing problem with delivery options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 203(C).
    7. Bernardino, Raquel & Paias, Ana, 2024. "The family capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 314(3), pages 836-853.
    8. Débora P. Ronconi & João L. V. Manguino, 2025. "GRASP and VNS approaches for a vehicle routing problem with step cost functions," Annals of Operations Research, Springer, vol. 350(1), pages 37-62, July.
    9. Sheng Liu & Zhixing Luo, 2023. "On-Demand Delivery from Stores: Dynamic Dispatching and Routing with Random Demand," Manufacturing & Service Operations Management, INFORMS, vol. 25(2), pages 595-612, March.
    10. Jumbo, Olga & Moghaddass, Ramin, 2022. "Resource optimization and image processing for vegetation management programs in power distribution networks," Applied Energy, Elsevier, vol. 319(C).
    11. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    12. Babagolzadeh, Mahla & Zhang, Yahua & Abbasi, Babak & Shrestha, Anup & Zhang, Anming, 2022. "Promoting Australian regional airports with subsidy schemes: Optimised downstream logistics using vehicle routing problem," Transport Policy, Elsevier, vol. 128(C), pages 38-51.
    13. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    14. Truden, Christian & Hewitt, Mike, 2026. "Multi-objective, multi-attribute fleet sizing in a dynamic and stochastic environment: A data-driven approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 207(C).
    15. Tianlu Zhao & Yongjian Yang & En Wang, 2020. "Minimizing the average arriving distance in carpooling," International Journal of Distributed Sensor Networks, , vol. 16(1), pages 15501477198, January.
    16. Long Wang & Jiongzhi Zheng & Zhengda Xiong & Kun He, 2026. "Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem and its Variants," Journal of Heuristics, Springer, vol. 32(1), pages 1-32, March.
    17. Dessouky, Maged M & Shao, Yihuan E, 2017. "Routing Strategies for Efficient Deployment of Alternative Fuel Vehicles for Freight Delivery," Institute of Transportation Studies, Working Paper Series qt0nj024qn, Institute of Transportation Studies, UC Davis.
    18. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    19. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    20. Coelho, V.N. & Grasas, A. & Ramalhinho, H. & Coelho, I.M. & Souza, M.J.F. & Cruz, R.C., 2016. "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints," European Journal of Operational Research, Elsevier, vol. 250(2), pages 367-376.

    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:orijoc:v:36:y:2024:i:4:p:974-986. 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.