IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v42y2020i1d10.1007_s00291-019-00568-7.html
   My bibliography  Save this article

A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes

Author

Listed:
  • Tânia Rodrigues Pereira Ramos

    (Instituto Superior Técnico (CEG-IST), Universidade de Lisboa
    ISCTE (BRU-ISCTE), Instituto Universitário de Lisboa)

  • Maria Isabel Gomes

    (Universidade Nova de Lisboa)

  • Ana Paula Barbosa-Póvoa

    (Instituto Superior Técnico (CEG-IST), Universidade de Lisboa)

Abstract

The multi-depot vehicle routing problem with inter-depot routes is studied in this paper, where vehicles may reset their capacity at any depot during the working day. Due to the complexity of this problem, exact approaches are limited to small-size applications. In order to overcome this limitation, we propose a matheuristic which integrates a mixed integer linear programming formulation with a set of relax-and-fix strategies. This solution approach is shown to be very efficient, and for the first time, large-size benchmarking instances are solved.

Suggested Citation

  • Tânia Rodrigues Pereira Ramos & Maria Isabel Gomes & Ana Paula Barbosa-Póvoa, 2020. "A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 75-110, March.
    • Handle: RePEc:spr:orspec:v:42:y:2020:i:1:d:10.1007_s00291-019-00568-7
    DOI: 10.1007/s00291-019-00568-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-019-00568-7
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00291-019-00568-7?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. Christos D. Tarantilis & Emmanouil E. Zachariadis & Chris T. Kiranoudis, 2008. "A Hybrid Guided Local Search for the Vehicle-Routing Problem with Intermediate Replenishment Facilities," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 154-168, February.
    3. Billy E. Gillett & Leland R. Miller, 1974. "A Heuristic Algorithm for the Vehicle-Dispatch Problem," Operations Research, INFORMS, vol. 22(2), pages 340-349, April.
    4. Crevier, Benoit & Cordeau, Jean-Francois & Laporte, Gilbert, 2007. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, Elsevier, vol. 176(2), pages 756-773, January.
    5. Brandao, Jose & Mercer, Alan, 1997. "A tabu search algorithm for the multi-trip vehicle routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 100(1), pages 180-191, July.
    6. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    7. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    8. Tu, Wei & Fang, Zhixiang & Li, Qingquan & Shaw, Shih-Lung & Chen, BiYu, 2014. "A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 61(C), pages 84-97.
    9. Cattaruzza, Diego & Absi, Nabil & Feillet, Dominique & Vidal, Thibaut, 2014. "A memetic algorithm for the Multi Trip Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 833-848.
    10. Angelelli, Enrico & Grazia Speranza, Maria, 2002. "The periodic vehicle routing problem with intermediate facilities," European Journal of Operational Research, Elsevier, vol. 137(2), pages 233-247, March.
    11. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    12. Schneider, M. & Stenger, A. & Hof, J., 2015. "An Adaptive VNS Algorithm for Vehicle Routing Problems with Intermediate Stops," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63500, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    13. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    14. Aristide Mingozzi & Roberto Roberti & Paolo Toth, 2013. "An Exact Algorithm for the Multitrip Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 193-207, May.
    15. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    16. Ibrahim Muter & Jean-François Cordeau & Gilbert Laporte, 2014. "A Branch-and-Price Algorithm for the Multidepot Vehicle Routing Problem with Interdepot Routes," Transportation Science, INFORMS, vol. 48(3), pages 425-441, 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. Fischer, Vera & Pacheco Paneque, Meritxell & Legrain, Antoine & Bürgy, Reinhard, 2024. "A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection," European Journal of Operational Research, Elsevier, vol. 315(1), pages 338-353.
    2. Lena Hörsting & Catherine Cleophas, 2023. "Integrating Micro-Depot Freight Transport in Existing Public Transport Services," SN Operations Research Forum, Springer, vol. 4(3), pages 1-35, September.
    3. 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.

    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. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    2. Markov, Iliya & Varone, Sacha & Bierlaire, Michel, 2016. "Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 256-273.
    3. Ramos, Tânia Rodrigues Pereira & Gomes, Maria Isabel & Barbosa-Póvoa, Ana Paula, 2014. "Planning a sustainable reverse logistics system: Balancing costs with environmental and social concerns," Omega, Elsevier, vol. 48(C), pages 60-74.
    4. 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.
    5. Sohrabi, Somayeh & Ziarati, Koorush & Keshtkaran, Morteza, 2020. "A Greedy Randomized Adaptive Search Procedure for the Orienteering Problem with Hotel Selection," European Journal of Operational Research, Elsevier, vol. 283(2), pages 426-440.
    6. Maximilian Schiffer & Grit Walther, 2018. "An Adaptive Large Neighborhood Search for the Location-routing Problem with Intra-route Facilities," Transportation Science, INFORMS, vol. 52(2), pages 331-352, March.
    7. Schiffer, Maximilian & Schneider, Michael & Laporte, Gilbert, 2018. "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, Elsevier, vol. 265(2), pages 517-532.
    8. Schneider, M. & Stenger, A. & Hof, J., 2015. "An Adaptive VNS Algorithm for Vehicle Routing Problems with Intermediate Stops," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63500, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    9. Ramos, Tânia Rodrigues Pereira & Gomes, Maria Isabel & Barbosa-Póvoa, Ana Paula, 2014. "Assessing and improving management practices when planning packaging waste collection systems," Resources, Conservation & Recycling, Elsevier, vol. 85(C), pages 116-129.
    10. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    11. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2018. "Vehicle routing problems with multiple trips," Annals of Operations Research, Springer, vol. 271(1), pages 127-159, December.
    12. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2016. "Vehicle routing problems with multiple trips," 4OR, Springer, vol. 14(3), pages 223-259, September.
    13. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    14. CASTRO, Marco & SÖRENSEN, Kenneth & GOOS, Peter & VANSTEENWEGEN, Pieter, 2014. "The multiple travelling salesperson problem with hotel selection," Working Papers 2014030, University of Antwerp, Faculty of Business and Economics.
    15. Zhang, Zhenzhen & Liu, Mengyang & Lim, Andrew, 2015. "A memetic algorithm for the patient transportation problem," Omega, Elsevier, vol. 54(C), pages 60-71.
    16. Julia Rieck & Jürgen Zimmermann & Matthias Glagow, 2007. "Tourenplanung mittelständischer Speditionsunternehmen in Stückgutkooperationen: Modellierung und heuristische Lösungsverfahren," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 17(4), pages 365-388, January.
    17. 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.
    18. 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.
    19. Mo, Pengli & Yao, Yu & D’Ariano, Andrea & Liu, Zhiyuan, 2023. "The vehicle routing problem with underground logistics: Formulation and algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).
    20. Rahma Lahyani & Leandro C. Coelho & Jacques Renaud, 2018. "Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 125-157, January.

    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:spr:orspec:v:42:y:2020:i:1:d:10.1007_s00291-019-00568-7. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.