IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v246y2015i2p400-412.html
   My bibliography  Save this article

An integrative cooperative search framework for multi-decision-attribute combinatorial optimization: Application to the MDPVRP

Author

Listed:
  • Lahrichi, Nadia
  • Crainic, Teodor Gabriel
  • Gendreau, Michel
  • Rei, Walter
  • Crişan, Gloria Cerasela
  • Vidal, Thibaut

Abstract

We introduce the integrative cooperative search method (ICS), a multi-thread cooperative search method for multi-attribute combinatorial optimization problems. ICS musters the combined capabilities of a number of independent exact or meta-heuristic solution methods. A number of these methods work on sub-problems defined by suitably selected subsets of decision-set attributes of the problem, while others combine the resulting partial solutions into complete ones and, eventually, improve them. All these methods cooperate through an adaptive search-guidance mechanism, using the central-memory cooperative search paradigm. Extensive numerical experiments explore the behavior of ICS and its interest through an application to the multi-depot, periodic vehicle routing problem, for which ICS improves the results of the current state-of-the-art methods.

Suggested Citation

  • Lahrichi, Nadia & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter & Crişan, Gloria Cerasela & Vidal, Thibaut, 2015. "An integrative cooperative search framework for multi-decision-attribute combinatorial optimization: Application to the MDPVRP," European Journal of Operational Research, Elsevier, vol. 246(2), pages 400-412.
    • Handle: RePEc:eee:ejores:v:246:y:2015:i:2:p:400-412
    DOI: 10.1016/j.ejor.2015.05.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715003793
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.05.007?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. Bernard Gendron & Teodor Gabriel Crainic, 1994. "Parallel Branch-and-Branch Algorithms: Survey and Synthesis," Operations Research, INFORMS, vol. 42(6), pages 1042-1066, December.
    4. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    5. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    6. 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.
    7. Arthur M. Geoffrion, 1970. "Elements of Large-Scale Mathematical Programming Part I: Concepts," Management Science, INFORMS, vol. 16(11), pages 652-675, July.
    8. Richard Hartl & Geir Hasle & Gerrit Janssens, 2006. "Special issue on Rich Vehicle Routing Problems," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 14(2), pages 103-104, June.
    9. Homberger, Jorg & Gehring, Hermann, 2005. "A two-phase hybrid metaheuristic for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 162(1), pages 220-238, April.
    10. Éric Taillard & Philippe Badeau & Michel Gendreau & François Guertin & Jean-Yves Potvin, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 31(2), pages 170-186, May.
    11. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    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. Salman, F. Sibel & Yücel, Eda & Kayı, İlker & Turper-Alışık, Sedef & Coşkun, Abdullah, 2021. "Modeling mobile health service delivery to Syrian migrant farm workers using call record data," Socio-Economic Planning Sciences, Elsevier, vol. 77(C).
    2. Xue, Ning & Bai, Ruibin & Qu, Rong & Aickelin, Uwe, 2021. "A hybrid pricing and cutting approach for the multi-shift full truckload vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 292(2), pages 500-514.
    3. Cristina Ticala & Ioana Zelina & Camelia-M. Pintea, 2020. "Admissible Perturbation of Demicontractive Operators within Ant Algorithms for Medical Images Edge Detection," Mathematics, MDPI, vol. 8(6), pages 1-13, June.
    4. Alberto Santini & Michael Schneider & Thibaut Vidal & Daniele Vigo, 2023. "Decomposition Strategies for Vehicle Routing Heuristics," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 543-559, May.
    5. Schryen, Guido, 2020. "Parallel computational optimization in operations research: A new integrative framework, literature review and research directions," European Journal of Operational Research, Elsevier, vol. 287(1), pages 1-18.
    6. 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.

    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. 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.
    2. Benjamin C. Shelbourne & Maria Battarra & Chris N. Potts, 2017. "The Vehicle Routing Problem with Release and Due Dates," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 705-723, November.
    3. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    4. Manuel Ostermeier & Andreas Holzapfel & Heinrich Kuhn & Daniel Schubert, 2022. "Integrated zone picking and vehicle routing operations with restricted intermediate storage," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 795-832, September.
    5. A Ostertag & K F Doerner & R F Hartl & E D Taillard & P Waelti, 2009. "POPMUSIC for a real-world large-scale vehicle routing problem with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(7), pages 934-943, July.
    6. 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.
    7. Alan Lee & Martin Savelsbergh, 2017. "An extended demand responsive connector," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 25-50, March.
    8. Bulhões, Teobaldo & Hà, Minh Hoàng & Martinelli, Rafael & Vidal, Thibaut, 2018. "The vehicle routing problem with service level constraints," European Journal of Operational Research, Elsevier, vol. 265(2), pages 544-558.
    9. 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.
    10. Teodor Gabriel Crainic & Nicoletta Ricciardi & Giovanni Storchi, 2009. "Models for Evaluating and Planning City Logistics Systems," Transportation Science, INFORMS, vol. 43(4), pages 432-454, November.
    11. Sumanta Basu & Ghosh, Diptesh, 2008. "A review of the Tabu Search Literature on Traveling Salesman Problems," IIMA Working Papers WP2008-10-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    12. Thomas Borthen & Henrik Loennechen & Xin Wang & Kjetil Fagerholt & Thibaut Vidal, 2018. "A genetic search-based heuristic for a fleet size and periodic routing problem with application to offshore supply planning," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(2), pages 121-150, June.
    13. Mohamed Cissé & Semih Yalçindag & Yannick Kergosien & Evren Sahin & Christophe Lenté & Andrea Matta, 2017. "OR problems related to Home Health Care: A review of relevant routing and scheduling problems," Post-Print hal-01736714, HAL.
    14. Campelo, Pedro & Neves-Moreira, Fábio & Amorim, Pedro & Almada-Lobo, Bernardo, 2019. "Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector," European Journal of Operational Research, Elsevier, vol. 273(1), pages 131-145.
    15. Phuong Khanh Nguyen & Teodor Gabriel Crainic & Michel Toulouse, 2017. "Multi-trip pickup and delivery problem with time windows and synchronization," Annals of Operations Research, Springer, vol. 253(2), pages 899-934, June.
    16. Li, Gang & Balakrishnan, Anantaram, 2016. "Models and algorithms for network reduction," European Journal of Operational Research, Elsevier, vol. 248(3), pages 930-942.
    17. Puca Huachi Vaz Penna & Anand Subramanian & Luiz Satoru Ochi & Thibaut Vidal & Christian Prins, 2019. "A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet," Annals of Operations Research, Springer, vol. 273(1), pages 5-74, February.
    18. 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.
    19. Lahyani, Rahma & Khemakhem, Mahdi & Semet, Frédéric, 2015. "Rich vehicle routing problems: From a taxonomy to a definition," European Journal of Operational Research, Elsevier, vol. 241(1), pages 1-14.
    20. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2014. "Implicit depot assignments and rotations in vehicle routing heuristics," European Journal of Operational Research, Elsevier, vol. 237(1), pages 15-28.

    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:eee:ejores:v:246:y:2015:i:2:p:400-412. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.