IDEAS home Printed from https://ideas.repec.org/a/spr/ijsaem/v15y2024i5d10.1007_s13198-023-02040-w.html
   My bibliography  Save this article

Multi-trip multi-compartment vehicle routing problem with backhauls

Author

Listed:
  • Sukhpal

    (Faculty of Mathematical Sciences, University of Delhi)

  • Kaushal Kumar

    (Faculty of Mathematical Sciences, University of Delhi)

Abstract

The Multi-Trip Multi-Compartment Vehicle Routing Problem with Backhauls (MTMCVRPB) is a complex optimization problem that involves finding the most efficient routes for a heterogeneous fleet of multi-compartment vehicles to transport heterogeneous commodities simultaneously. The problem involves making deliveries and pickups while taking into account capacity constraints on compartments and other specific requirements such as limitation on route length. The MTMCVRPB aims to minimize the total cost of the routes, including the cost of vehicles, fuel and other expenses, while maximizing efficiency of vehicles and fulfilling the demand of customers. In order to address the MTMCVRPB, this article recommends a mixed integer linear programming formulation. The proposed model takes into consideration the demands of both linehaul and backhaul customers, ensuring that on each route linehaul deliveries are made before visiting any backhaul customer. The model was tested on randomly generated data sets and numerical experiments were performed to demonstrate effectiveness of the model. The proposed model can be beneficial for the industries such as grocery and food delivery, fuel distribution and garbage collection etc., as these represent some application areas of the model. This article also presents a saving based heuristic for the proposed model.

Suggested Citation

  • Sukhpal & Kaushal Kumar, 2024. "Multi-trip multi-compartment vehicle routing problem with backhauls," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 15(5), pages 1717-1734, May.
    • Handle: RePEc:spr:ijsaem:v:15:y:2024:i:5:d:10.1007_s13198-023-02040-w
    DOI: 10.1007/s13198-023-02040-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13198-023-02040-w
    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/s13198-023-02040-w?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

    for a different version of it.

    References listed on IDEAS

    as
    1. P. Senthil Kumar, 2020. "Algorithms for solving the optimization problems using fuzzy and intuitionistic fuzzy set," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 11(1), pages 189-222, February.
    2. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    3. Cornillier, Fabien & Boctor, Fayez F. & Laporte, Gilbert & Renaud, Jacques, 2008. "A heuristic for the multi-period petrol station replenishment problem," European Journal of Operational Research, Elsevier, vol. 191(2), pages 295-305, December.
    4. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    5. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2016. "The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates," Transportation Science, INFORMS, vol. 50(2), pages 676-693, May.
    6. 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.
    7. Samira Mirzaei & Sanne Wøhlk, 2019. "A Branch-and-Price algorithm for two multi-compartment vehicle routing problems," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(1), pages 1-33, March.
    8. P. Senthil Kumar, 2019. "Intuitionistic fuzzy solid assignment problems: a software-based approach," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 10(4), pages 661-675, August.
    9. Frank, Markus & Ostermeier, Manuel & Holzapfel, Andreas & Hübner, Alexander & Kuhn, Heinrich, 2021. "Optimizing routing and delivery patterns with multi-compartment vehicles," European Journal of Operational Research, Elsevier, vol. 293(2), pages 495-510.
    10. 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.
    11. Reil, Sebastian & Bortfeldt, Andreas & Mönch, Lars, 2018. "Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints," European Journal of Operational Research, Elsevier, vol. 266(3), pages 877-894.
    12. P. Senthil Kumar & R. Jahir Hussain, 2016. "Computationally simple approach for solving fully intuitionistic fuzzy real life transportation problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 7(1), pages 90-101, December.
    13. P.Senthil Kumar, 2018. "PSK Method for Solving Intuitionistic Fuzzy Solid Transportation Problems," International Journal of Fuzzy System Applications (IJFSA), IGI Global Scientific Publishing, vol. 7(4), pages 62-99, October.
    14. Goetschalckx, Marc & Jacobs-Blecha, Charlotte, 1989. "The vehicle routing problem with backhauls," European Journal of Operational Research, Elsevier, vol. 42(1), pages 39-51, September.
    15. Paolo Toth & Daniele Vigo, 1997. "An Exact Algorithm for the Vehicle Routing Problem with Backhauls," Transportation Science, INFORMS, vol. 31(4), pages 372-385, November.
    16. Henke, Tino & Speranza, M. Grazia & Wäscher, Gerhard, 2015. "The multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 246(3), pages 730-743.
    17. A. Mor & M. G. Speranza, 2022. "Vehicle routing problems over time: a survey," Annals of Operations Research, Springer, vol. 314(1), pages 255-275, July.
    18. P. Senthil Kumar, 2016. "PSK Method for Solving Type-1 and Type-3 Fuzzy Transportation Problems," International Journal of Fuzzy System Applications (IJFSA), IGI Global Scientific Publishing, vol. 5(4), pages 121-146, October.
    19. Coelho, Leandro C. & Laporte, Gilbert, 2015. "Classification, models and exact algorithms for multi-compartment delivery problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 854-864.
    20. Lahyani, Rahma & Coelho, Leandro C. & Khemakhem, Mahdi & Laporte, Gilbert & Semet, Frédéric, 2015. "A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia," Omega, Elsevier, vol. 51(C), pages 1-10.
    21. Alexander Hübner & Manuel Ostermeier, 2019. "A Multi-Compartment Vehicle Routing Problem with Loading and Unloading Costs," Service Science, INFORMS, vol. 53(1), pages 282-300, February.
    22. Xuping Wang & Wenping Fan & Hongxin Zhan & Zilai Sun, 2022. "Variable Neighborhood Descent for Multi-Compartment and Multi-Objective Vehicle Routing Problem in Refined Product Distribution," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 39(02), pages 1-32, April.
    23. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    24. P. Senthil Kumar, 2018. "A Simple and Efficient Algorithm for Solving Type-1 Intuitionistic Fuzzy Solid Transportation Problems," International Journal of Operations Research and Information Systems (IJORIS), IGI Global Scientific Publishing, vol. 9(3), pages 90-122, July.
    25. P. Senthil Kumar, 2020. "Intuitionistic fuzzy zero point method for solving type-2 intuitionistic fuzzy transportation problem," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 37(3), pages 418-451.
    26. Alinaghian, Mahdi & Shokouhi, Nadia, 2018. "Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search," Omega, Elsevier, vol. 76(C), pages 85-99.
    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. Melo, Rafael A. & Ribeiro, Celso C. & Urrutia, Sebastián & Vansteenwegen, Pieter, 2025. "A logic-based Benders decomposition approach for a fuel delivery problem with time windows, unsplit compartments, and split deliveries," European Journal of Operational Research, Elsevier, vol. 325(1), pages 100-117.

    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. P. Senthil Kumar, 2020. "Developing a New Approach to Solve Solid Assignment Problems Under Intuitionistic Fuzzy Environment," International Journal of Fuzzy System Applications (IJFSA), IGI Global Scientific Publishing, vol. 9(1), pages 1-34, January.
    2. Ostermeier, Manuel, 2024. "The supply of convenience stores: Challenges of short-distance routing within the constraints of working time regulations," European Journal of Operational Research, Elsevier, vol. 314(3), pages 997-1012.
    3. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    4. Gu, Wenjuan & Archetti, Claudia & Cattaruzza, Diego & Ogier, Maxime & Semet, Frédéric & Speranza, M. Grazia, 2024. "Vehicle routing problems with multiple commodities: A survey," European Journal of Operational Research, Elsevier, vol. 317(1), pages 1-15.
    5. P. Senthil Kumar, 2019. "PSK Method for Solving Mixed and Type-4 Intuitionistic Fuzzy Solid Transportation Problems," International Journal of Operations Research and Information Systems (IJORIS), IGI Global Scientific Publishing, vol. 10(2), pages 20-53, April.
    6. Abdelmalek Ouannou & Adil Brouri & Laila Kadi & Hafid Oubouaddi, 2022. "Identification of switched reluctance machine using fuzzy model," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 13(6), pages 2833-2846, December.
    7. Sohaib Dastgoshade & Hassan Hosseini-Nasab & Yahia Zare Mehrjerdi, 2024. "Investigating of transportation systems development for urban districts, costs and social equity: a case of Sanandaj, Kurdistan," OPSEARCH, Springer;Operational Research Society of India, vol. 61(1), pages 373-398, March.
    8. 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).
    9. Raj Kumar Bera & Shyamal Kumar Mondal, 2023. "Analyzing the nature of a transportation problem before and during COVID-19 pandemic in multi-fuzzy environment," OPSEARCH, Springer;Operational Research Society of India, vol. 60(4), pages 1659-1702, December.
    10. P. Senthil Kumar, 2019. "Intuitionistic fuzzy solid assignment problems: a software-based approach," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 10(4), pages 661-675, August.
    11. P. Senthil Kumar, 2020. "Algorithms for solving the optimization problems using fuzzy and intuitionistic fuzzy set," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 11(1), pages 189-222, February.
    12. Henriette Koch & Tino Henke & Gerhard Wäscher, 2016. "A Genetic Algorithm for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes," FEMM Working Papers 160004, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    13. Ostermeier, Manuel & Hübner, Alexander, 2018. "Vehicle selection for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 269(2), pages 682-694.
    14. Katrin Heßler & Stefan Irnich, 2023. "Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 50-65, January.
    15. Frank, Markus & Ostermeier, Manuel & Holzapfel, Andreas & Hübner, Alexander & Kuhn, Heinrich, 2021. "Optimizing routing and delivery patterns with multi-compartment vehicles," European Journal of Operational Research, Elsevier, vol. 293(2), pages 495-510.
    16. 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.
    17. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2019. "A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes," Annals of Operations Research, Springer, vol. 275(2), pages 321-338, April.
    18. Yan Cheng Hsu & Jose L. Walteros & Rajan Batta, 2020. "Solving the petroleum replenishment and routing problem with variable demands and time windows," Annals of Operations Research, Springer, vol. 294(1), pages 9-46, November.
    19. Martins, Sara & Ostermeier, Manuel & Amorim, Pedro & Hübner, Alexander & Almada-Lobo, Bernardo, 2019. "Product-oriented time window assignment for a multi-compartment vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 276(3), pages 893-909.
    20. Melo, Rafael A. & Ribeiro, Celso C. & Urrutia, Sebastián & Vansteenwegen, Pieter, 2025. "A logic-based Benders decomposition approach for a fuel delivery problem with time windows, unsplit compartments, and split deliveries," European Journal of Operational Research, Elsevier, vol. 325(1), pages 100-117.

    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:spr:ijsaem:v:15:y:2024:i:5:d:10.1007_s13198-023-02040-w. 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.