IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i4p974-986.html
   My bibliography  Save this article

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

    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.

    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.