IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v328y2026i1p91-104.html

A split-embedded metaheuristic for the heterogeneous inventory routing problem with batch size

Author

Listed:
  • Martino, Diego Perdigão
  • Lacomme, Philippe
  • Farias, Katyanne

Abstract

Handling transportation and inventory management simultaneously is a challenging problem. The most famous optimization problem in this domain, known as the Inventory Routing Problem (IRP), aims to determine the routes and quantities to be delivered by a set of vehicles to meet customer demands at a minimum total inventory and transportation cost. The vast majority of works carried out so far on the IRP consider a homogeneous fleet of vehicles. This paper addresses, instead, a new IRP variant that considers intrinsic characteristics of real supply chains, such as a period-dependent heterogeneous fleet of vehicles and batch sizes for the delivered quantities. We model the problem with a Mixed Integer Linear Programming (MILP) formulation and propose a Split-Embedded Metaheuristic with a Post-Optimization phase (SEMPO) to solve it. Extensive computational experiments are conducted on a set of 80 new benchmark instances with up to 183 customers and a challenging time horizon of up 7 to 28 time periods to evaluate the performance of our approaches. The proposed SEMPO algorithm provides high-quality solutions and faster convergence compared to the MILP formulation.

Suggested Citation

  • Martino, Diego Perdigão & Lacomme, Philippe & Farias, Katyanne, 2026. "A split-embedded metaheuristic for the heterogeneous inventory routing problem with batch size," European Journal of Operational Research, Elsevier, vol. 328(1), pages 91-104.
    • Handle: RePEc:eee:ejores:v:328:y:2026:i:1:p:91-104
    DOI: 10.1016/j.ejor.2025.05.044
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221725004424
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.05.044?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. Cheng, Chun & Yang, Peng & Qi, Mingyao & Rousseau, Louis-Martin, 2017. "Modeling a green inventory routing problem with a heterogeneous fleet," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 97(C), pages 97-112.
    2. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    3. Guy Desaulniers & Jørgen G. Rakke & Leandro C. Coelho, 2016. "A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem," Transportation Science, INFORMS, vol. 50(3), pages 1060-1076, August.
    4. Touzout, Faycal A. & Ladier, Anne-Laure & Hadj-Hamou, Khaled, 2022. "An assign-and-route matheuristic for the time-dependent inventory routing problem," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1081-1097.
    5. Oualid Guemri & Abdelghani Bekrar & Bouziane Beldjilali & Damien Trentesaux, 2016. "GRASP-based heuristic algorithm for the multi-product multi-vehicle inventory routing problem," 4OR, Springer, vol. 14(4), pages 377-404, December.
    6. Chung-Lun Li & Vernon Ning Hsu & Wen-Qiang Xiao, 2004. "Dynamic Lot Sizing with Batch Ordering and Truckload Discounts," Operations Research, INFORMS, vol. 52(4), pages 639-654, August.
    7. Archetti, Claudia & Speranza, M. Grazia & Boccia, Maurizio & Sforza, Antonio & Sterle, Claudio, 2020. "A branch-and-cut algorithm for the inventory routing problem with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 282(3), pages 886-895.
    8. Bertazzi, Luca & Coelho, Leandro C. & De Maio, Annarita & Laganà, Demetrio, 2019. "A matheuristic algorithm for the multi-depot inventory routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 524-544.
    9. Alvarez, Aldair & Cordeau, Jean-François & Jans, Raf & Munari, Pedro & Morabito, Reinaldo, 2020. "Formulations, branch-and-cut and a hybrid heuristic algorithm for an inventory routing problem with perishable products," European Journal of Operational Research, Elsevier, vol. 283(2), pages 511-529.
    10. 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.
    11. Yves Pochet & Laurence A. Wolsey, 1993. "Lot-Sizing with Constant Batches: Formulation and Valid Inequalities," Mathematics of Operations Research, INFORMS, vol. 18(4), pages 767-785, November.
    12. Claudia Archetti & Luca Bertazzi & Gilbert Laporte & Maria Grazia Speranza, 2007. "A Branch-and-Cut Algorithm for a Vendor-Managed Inventory-Routing Problem," Transportation Science, INFORMS, vol. 41(3), pages 382-391, August.
    13. George Kontoravdis & Jonathan F. Bard, 1995. "A GRASP for the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 7(1), pages 10-23, February.
    14. Haddad, Matheus Nohra & Martinelli, Rafael & Vidal, Thibaut & Martins, Simone & Ochi, Luiz Satoru & Souza, Marcone Jamilson Freitas & Hartl, Richard, 2018. "Large neighborhood-based metaheuristic and branch-and-price for the pickup and delivery problem with split loads," European Journal of Operational Research, Elsevier, vol. 270(3), pages 1014-1027.
    15. Zhang, Zhenzhen & Wei, Lijun & Lim, Andrew, 2015. "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 20-35.
    16. Archetti, Claudia & Christiansen, Marielle & Grazia Speranza, M., 2018. "Inventory routing with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 268(1), pages 314-324.
    17. Soysal, Mehmet & Bloemhof-Ruwaard, Jacqueline M. & Haijema, Rene & van der Vorst, Jack G.A.J., 2015. "Modeling an Inventory Routing Problem for perishable products with environmental considerations and demand uncertainty," International Journal of Production Economics, Elsevier, vol. 164(C), pages 118-133.
    18. POCHET, Yves & WOLSEY, Laurence A., 1993. "Lot-sizing with constant batches: formulation and valid inequalities," LIDAM Reprints CORE 1066, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. Gutierrez-Alcoba, Alejandro & Rossi, Roberto & Martin-Barragan, Belen & Embley, Tim, 2023. "The stochastic inventory routing problem on electric roads," European Journal of Operational Research, Elsevier, vol. 310(1), pages 156-167.
    20. Manousakis, Eleftherios & Repoussis, Panagiotis & Zachariadis, Emmanouil & Tarantilis, Christos, 2021. "Improved branch-and-cut for the Inventory Routing Problem based on a two-commodity flow formulation," European Journal of Operational Research, Elsevier, vol. 290(3), pages 870-885.
    21. Akbalik, Ayse & Rapine, Christophe, 2018. "Lot sizing problem with multi-mode replenishment and batch delivery," Omega, Elsevier, vol. 81(C), pages 123-133.
    22. Aksen, Deniz & Kaya, Onur & Sibel Salman, F. & Tüncel, Özge, 2014. "An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 239(2), pages 413-426.
    23. Hemmati, Ahmad & Hvattum, Lars Magnus & Christiansen, Marielle & Laporte, Gilbert, 2016. "An iterative two-phase hybrid matheuristic for a multi-product short sea inventory-routing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 775-788.
    24. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2014. "Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 103-120, February.
    25. Peres, Igor T. & Repolho, Hugo M. & Martinelli, Rafael & Monteiro, Nathália J., 2017. "Optimization in inventory-routing problem with planned transshipment: A case study in the retail industry," International Journal of Production Economics, Elsevier, vol. 193(C), pages 748-756.
    26. Claudia Archetti & Luca Bertazzi & Alain Hertz & M. Grazia Speranza, 2012. "A Hybrid Heuristic for an Inventory Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 101-116, February.
    Full references (including those not matched with items on IDEAS)

    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. Skålnes, Jørgen & Andersson, Henrik & Desaulniers, Guy & Stålhane, Magnus, 2022. "An improved formulation for the inventory routing problem with time-varying demands," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1189-1201.
    2. Diabat, Ali & Bianchessi, Nicola & Archetti, Claudia, 2024. "On the zero-inventory-ordering policy in the inventory routing problem," European Journal of Operational Research, Elsevier, vol. 312(3), pages 1024-1038.
    3. Manousakis, Eleftherios & Repoussis, Panagiotis & Zachariadis, Emmanouil & Tarantilis, Christos, 2021. "Improved branch-and-cut for the Inventory Routing Problem based on a two-commodity flow formulation," European Journal of Operational Research, Elsevier, vol. 290(3), pages 870-885.
    4. Avishan, Farzad & Dems, Amira & Adulyasak, Yossiri & Arslan, Okan & Cordeau, Jean-François, 2026. "Inventory routing with heterogeneous vehicles and hazardous material backhauling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 205(C).
    5. Skålnes, Jørgen & Ben Ahmed, Mohamed & Hvattum, Lars Magnus & Stålhane, Magnus, 2024. "New benchmark instances for the inventory routing problem," European Journal of Operational Research, Elsevier, vol. 313(3), pages 992-1014.
    6. Coelho, Leandro Callegari & De Maio, Annarita & Laganà, Demetrio, 2020. "A variable MIP neighborhood descent for the multi-attribute inventory routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    7. Cárdenas-Barrón, Leopoldo Eduardo & González-Velarde, José Luis & Treviño-Garza, Gerardo & Garza-Nuñez, Dagoberto, 2019. "Heuristic algorithm based on reduce and optimize approach for a selective and periodic inventory routing problem in a waste vegetable oil collection environment," International Journal of Production Economics, Elsevier, vol. 211(C), pages 44-59.
    8. 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.
    9. Cleder Marcos Schenekemberg & Thiago André Guimarães & Antonio Augusto Chaves & Leandro C. Coelho, 2024. "A Three-Front Parallel Branch-and-Cut Algorithm for Production and Inventory Routing Problems," Transportation Science, INFORMS, vol. 58(4), pages 687-707, July.
    10. Archetti, Claudia & Ljubić, Ivana, 2022. "Comparison of formulations for the Inventory Routing Problem," European Journal of Operational Research, Elsevier, vol. 303(3), pages 997-1008.
    11. 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.
    12. Mahmutoğulları, Özlem & Yaman, Hande, 2023. "A Branch-and-Cut Algorithm for the Inventory Routing Problem with Product Substitution," Omega, Elsevier, vol. 115(C).
    13. Najy, Waleed & Archetti, Claudia & Diabat, Ali, 2025. "A column generation-based matheuristic for an inventory-routing problem with driver-route consistency," European Journal of Operational Research, Elsevier, vol. 324(2), pages 382-397.
    14. Zhenzhen Zhang & Zhixing Luo & Roberto Baldacci & Andrew Lim, 2021. "A Benders Decomposition Approach for the Multivehicle Production Routing Problem with Order-up-to-Level Policy," Transportation Science, INFORMS, vol. 55(1), pages 160-178, 1-2.
    15. Alvarez, Aldair & Cordeau, Jean-François & Jans, Raf & Munari, Pedro & Morabito, Reinaldo, 2021. "Inventory routing under stochastic supply and demand," Omega, Elsevier, vol. 102(C).
    16. Claudia Archetti & Natashia Boland & Grazia Speranza, 2017. "A Matheuristic for the Multivehicle Inventory Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 377-387, August.
    17. Archetti, Claudia & Coelho, Leandro C. & Grazia Speranza, M., 2019. "An exact algorithm for the inventory routing problem with logistic ratio," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 131(C), pages 96-107.
    18. Jia, Menglei & Chen, Feng, 2023. "Upward scalable vehicle routing problem of automobile inbound logistics with pickup flexibility," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    19. Alvarez, Aldair & Cordeau, Jean-François & Jans, Raf & Munari, Pedro & Morabito, Reinaldo, 2020. "Formulations, branch-and-cut and a hybrid heuristic algorithm for an inventory routing problem with perishable products," European Journal of Operational Research, Elsevier, vol. 283(2), pages 511-529.
    20. Ziye Tang & Yang Jiao & R. Ravi, 2022. "Combinatorial Heuristics for Inventory Routing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 370-384, January.

    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:eee:ejores:v:328:y:2026:i:1:p:91-104. 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.