IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v40y2018i1d10.1007_s00291-017-0494-y.html
   My bibliography  Save this article

Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem

Author

Listed:
  • Rahma Lahyani

    (Alfaisal University, College of Business
    Institut Supérieur de Gestion Industrielle)

  • Leandro C. Coelho

    (Interuniversity Research Center on Enterprise Network, Logistics and Transportation
    Université Laval
    Canada Research Chair in Integrated Logistics
    Groningen University)

  • Jacques Renaud

    (Interuniversity Research Center on Enterprise Network, Logistics and Transportation
    Université Laval)

Abstract

In this paper, we compare different formulations of the multi-depot fleet size and mix vehicle routing problem (MDFSMVRP). This problem extends the multi-depot vehicle routing problem and the fleet size and mix vehicle routing problem, two logistics problems that have been extensively studied for many decades. This difficult vehicle routing problem combines complex assignment and routing decisions under the objective of minimizing fixed vehicle costs and variable routing costs. We first propose five distinct formulations to model the MDFSMVRP. We introduce a three-index formulation with an explicit vehicle index and a two-index formulation in which only vehicle types are identified. Other formulations are obtained by defining aggregated and disaggregated loading variables. The last formulation makes use of capacity-indexed variables. For each formulation, we summarize known and propose new valid inequalities, including symmetry breaking, lexicographic ordering, routing, and rounded capacity cuts. We then implement branch-and-cut and branch-and-bound algorithms for these formulations, and we fed them into a general purpose solver. We compare the bounds provided by the formulations on a commonly used set of instances in the MDFSMVRP literature, containing up to nine depots and 360 customers, and on newly generated instances. Our in-depth analysis of the five formulations shows which formulations tend to perform better on each type of instance. Moreover, our results have considerably improved available lower bounds on all instances and significantly improved quality of upper bounds that can be obtained by means of currently available methods.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:orspec:v:40:y:2018:i:1:d:10.1007_s00291-017-0494-y
    DOI: 10.1007/s00291-017-0494-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-017-0494-y
    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-017-0494-y?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. Perl, Jossef & Daskin, Mark S., 1985. "A warehouse location-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 19(5), pages 381-396, October.
    2. 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.
    3. Campos, V. & Corberan, A. & Mota, E., 1991. "Polyhedral results for a vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 52(1), pages 75-85, May.
    4. Araque, J. & Hall, L. & Magnanti, T., 1990. "Capacitated trees, capacitated routing, and associated polyhedra," LIDAM Discussion Papers CORE 1990061, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. 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.
    6. Jean-Claude Picard & Maurice Queyranne, 1978. "The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling," Operations Research, INFORMS, vol. 26(1), pages 86-110, February.
    7. Salhi, S. & Sari, M., 1997. "A multi-level composite heuristic for the multi-depot vehicle fleet mix problem," European Journal of Operational Research, Elsevier, vol. 103(1), pages 95-112, November.
    8. Gouveia, Luis, 1995. "A result on projection for the vehicle routing ptoblem," European Journal of Operational Research, Elsevier, vol. 85(3), pages 610-624, September.
    9. Kulkarni, R. V. & Bhave, P. R., 1985. "Integer programming formulations of vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 20(1), pages 58-67, April.
    10. 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.
    11. Liu, Shuguang, 2013. "A hybrid population heuristic for the heterogeneous vehicle routing problems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 54(C), pages 67-78.
    12. Hanif D. Sherali & J. Cole Smith, 2001. "Improving Discrete Model Representations via Symmetry Considerations," Management Science, INFORMS, vol. 47(10), pages 1396-1407, October.
    13. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    14. Onur Can Saka & Sinan Gürel & Tom Van Woensel, 2017. "Using cost change estimates in a local search heuristic for the pollution routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(2), pages 557-587, March.
    15. Karaoglan, Ismail & Altiparmak, Fulya & Kara, Imdat & Dengiz, Berna, 2012. "The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach," Omega, Elsevier, vol. 40(4), pages 465-477.
    16. W. W. Garvin & H. W. Crandall & J. B. John & R. A. Spellman, 1957. "Applications of Linear Programming in the Oil Industry," Management Science, INFORMS, vol. 3(4), pages 407-430, July.
    17. Gillett, Billy E & Johnson, Jerry G, 1976. "Multi-terminal vehicle-dispatch algorithm," Omega, Elsevier, vol. 4(6), pages 711-718.
    18. Coelho, Leandro C. & Laporte, Gilbert, 2014. "Improved solutions for inventory-routing problems through valid inequalities and input ordering," International Journal of Production Economics, Elsevier, vol. 155(C), pages 391-397.
    19. Luis Gouveia, 1995. "A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem," Operations Research, INFORMS, vol. 43(1), pages 130-141, February.
    20. Michel Gendreau & Gilbert Laporte & Frédéric Semet, 1997. "The Covering Tour Problem," Operations Research, INFORMS, vol. 45(4), pages 568-576, August.
    21. Prodhon, Caroline & Prins, Christian, 2014. "A survey of recent research on location-routing problems," European Journal of Operational Research, Elsevier, vol. 238(1), pages 1-17.
    22. Bektaş, Tolga & Gouveia, Luis, 2014. "Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?," European Journal of Operational Research, Elsevier, vol. 236(3), pages 820-832.
    23. Salhi, Said & Rand, Graham K., 1993. "Incorporating vehicle routing into the vehicle fleet composition problem," European Journal of Operational Research, Elsevier, vol. 66(3), pages 313-330, May.
    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. Michiel A. J. uit het Broek & Albert H. Schrotenboer & Bolor Jargalsaikhan & Kees Jan Roodbergen & Leandro C. Coelho, 2021. "Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm," Operations Research, INFORMS, vol. 69(2), pages 380-409, March.
    2. Zhou, Yu & Meng, Qiang & Ong, Ghim Ping, 2022. "Electric Bus Charging Scheduling for a Single Public Transport Route Considering Nonlinear Charging Profile and Battery Degradation Effect," Transportation Research Part B: Methodological, Elsevier, vol. 159(C), pages 49-75.
    3. Brandão, José, 2020. "A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 284(2), pages 559-571.
    4. Schenekemberg, Cleder M. & Scarpin, Cassius T. & Pécora, José E. & Guimarães, Thiago A. & Coelho, Leandro C., 2021. "The two-echelon production-routing problem," European Journal of Operational Research, Elsevier, vol. 288(2), pages 436-449.
    5. Lin, Na & Akkerman, Renzo & Kanellopoulos, Argyris & Hu, Xiangpei & Wang, Xuping & Ruan, Junhu, 2023. "Vehicle routing with heterogeneous service types: Optimizing post-harvest preprocessing operations for fruits and vegetables in short food supply chains," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    6. Alvarez, Jose A. Lopez & Buijs, Paul & Deluster, Rogier & Coelho, Leandro C. & Ursavas, Evrim, 2020. "Strategic and operational decision-making in expanding supply chains for LNG as a fuel," Omega, Elsevier, vol. 97(C).
    7. Sun, Lijun & Zhang, Yuankai & Hu, Xiangpei, 2021. "Economical-traveling-distance-based fleet composition with fuel costs: An application in petrol distribution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    8. Darvish, Maryam & Archetti, Claudia & Coelho, Leandro C. & Speranza, M. Grazia, 2019. "Flexible two-echelon location routing problem," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1124-1136.

    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. Allahyari, Somayeh & Salari, Majid & Vigo, Daniele, 2015. "A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 756-768.
    2. Daniel Negrotto & Irene Loiseau, 2021. "A Branch & Cut algorithm for the prize-collecting capacitated location routing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 34-57, April.
    3. Fernando Afonso Santos & Geraldo Robson Mateus & Alexandre Salles da Cunha, 2015. "A Branch-and-Cut-and-Price Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem," Transportation Science, INFORMS, vol. 49(2), pages 355-368, May.
    4. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "Thirty years of heterogeneous vehicle routing," European Journal of Operational Research, Elsevier, vol. 249(1), pages 1-21.
    5. 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.
    6. Sahar Validi & Arijit Bhattacharya & P. J. Byrne, 2020. "Sustainable distribution system design: a two-phase DoE-guided meta-heuristic solution approach for a three-echelon bi-objective AHP-integrated location-routing model," Annals of Operations Research, Springer, vol. 290(1), pages 191-222, July.
    7. Li, Hongqi & Zhang, Lu & Lv, Tan & Chang, Xinyu, 2016. "The two-echelon time-constrained vehicle routing problem in linehaul-delivery systems," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 169-188.
    8. 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.
    9. Alvarez, Jose A. Lopez & Buijs, Paul & Deluster, Rogier & Coelho, Leandro C. & Ursavas, Evrim, 2020. "Strategic and operational decision-making in expanding supply chains for LNG as a fuel," Omega, Elsevier, vol. 97(C).
    10. Gläser, Sina, 2022. "A waste collection problem with service type option," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1216-1230.
    11. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    12. 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.
    13. Muren, & Wu, Jianjun & Zhou, Li & Du, Zhiping & Lv, Ying, 2019. "Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 87-102.
    14. Ricardo Fukasawa & Qie He & Yongjia Song, 2016. "A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem," Transportation Science, INFORMS, vol. 50(1), pages 23-34, February.
    15. Karaoglan, Ismail & Altiparmak, Fulya & Kara, Imdat & Dengiz, Berna, 2012. "The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach," Omega, Elsevier, vol. 40(4), pages 465-477.
    16. Karaoğlan, İsmail & Erdoğan, Güneş & Koç, Çağrı, 2018. "The Multi-Vehicle Probabilistic Covering Tour Problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 278-287.
    17. Arslan, Okan, 2021. "The location-or-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 1-21.
    18. Günther Zäpfel & Michael Bögl, 2016. "An adaptive structure of a hub-and-spoke system with direct and depot shipments in the case of volatile demand over time," Journal of Business Economics, Springer, vol. 86(7), pages 697-721, October.
    19. Roel G. van Anholt & Leandro C. Coelho & Gilbert Laporte & Iris F. A. Vis, 2016. "An Inventory-Routing Problem with Pickups and Deliveries Arising in the Replenishment of Automated Teller Machines," Transportation Science, INFORMS, vol. 50(3), pages 1077-1091, August.
    20. Menezes, Mozart B.C. & Ruiz-Hernández, Diego & Verter, Vedat, 2016. "A rough-cut approach for evaluating location-routing decisions via approximation algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 87(C), pages 89-106.

    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:40:y:2018:i:1:d:10.1007_s00291-017-0494-y. 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.