IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v115y2023ics0305048322001591.html
   My bibliography  Save this article

A Branch-and-Cut Algorithm for the Inventory Routing Problem with Product Substitution

Author

Listed:
  • Mahmutoğulları, Özlem
  • Yaman, Hande

Abstract

The inventory routing problem arises in vendor managed systems, in which a supplier is responsible for replenishing inventories of products at a set of retailers and manages the logistics over a finite planning horizon with a fleet of capacitated vehicles. We consider this problem in the context of the distribution of two different quality products with one-way product substitution, where the high-quality product may be used to meet the demand for the low-quality product. The routes of vehicles and the quantities of products sent to each retailer in each period are determined in such a way that no stockouts occur and the total cost associated with inventory holding, substitution and transportation is minimized. In this study, we derive a mixed integer linear programming formulation for the problem, strengthen this formulation with valid inequalities and develop a branch-and-cut algorithm as an exact solution method. We conduct experiments using benchmark and randomly generated instances to analyze the effectiveness of our solution method and investigate the relationship between product substitution decisions and system costs under different demand, supply, vehicle capacity and substitution cost settings.

Suggested Citation

  • Mahmutoğulları, Özlem & Yaman, Hande, 2023. "A Branch-and-Cut Algorithm for the Inventory Routing Problem with Product Substitution," Omega, Elsevier, vol. 115(C).
    • Handle: RePEc:eee:jomega:v:115:y:2023:i:c:s0305048322001591
    DOI: 10.1016/j.omega.2022.102752
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048322001591
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2022.102752?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. Fokkema, Jan Eise & Land, Martin J. & Coelho, Leandro C. & Wortmann, Hans & Huitema, George B., 2020. "A continuous-time supply-driven inventory-constrained routing problem," Omega, Elsevier, vol. 92(C).
    2. Arthur Hsu & Yehuda Bassok, 1999. "Random Yield and Random Demand in a Production System with Downward Substitution," Operations Research, INFORMS, vol. 47(2), pages 277-290, April.
    3. Cárdenas-Barrón, Leopoldo E. & Melo, Rafael A., 2021. "A fast and effective MIP-based heuristic for a selective and periodic inventory routing problem in reverse logistics," Omega, Elsevier, vol. 103(C).
    4. 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.
    5. 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.
    6. Li, Yongjian & Chen, Jian & Cai, Xiaoqiang, 2007. "Heuristic genetic algorithm for capacitated production planning problems with batch processing and remanufacturing," International Journal of Production Economics, Elsevier, vol. 105(2), pages 301-317, February.
    7. Bertazzi, Luca & Bosco, Adamo & Laganà, Demetrio, 2015. "Managing stochastic demand in an Inventory Routing Problem with transportation procurement," Omega, Elsevier, vol. 56(C), pages 112-121.
    8. Yehuda Bassok & Ravi Anupindi & Ram Akella, 1999. "Single-Period Multiproduct Inventory Models with Substitution," Operations Research, INFORMS, vol. 47(4), pages 632-642, August.
    9. 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.
    10. M. W. Padberg & T. J. Van Roy & L. A. Wolsey, 1985. "Valid Linear Inequalities for Fixed Charge Problems," Operations Research, INFORMS, vol. 33(4), pages 842-861, August.
    11. Piñeyro, Pedro & Viera, Omar, 2010. "The economic lot-sizing problem with remanufacturing and one-way substitution," International Journal of Production Economics, Elsevier, vol. 124(2), pages 482-488, April.
    12. Padberg, M.W. & Van Roy, T.J. & Wolsey, L.A., 1985. "Valid linear inequalities for fixed charge problems," LIDAM Reprints CORE 656, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. 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.
    14. Christiansen, Marielle & Fagerholt, Kjetil & Flatberg, Truls & Haugen, Øyvind & Kloster, Oddvar & Lund, Erik H., 2011. "Maritime inventory routing with multiple products: A case study from the cement industry," European Journal of Operational Research, Elsevier, vol. 208(1), pages 86-94, January.
    15. Freeman, Nickolas & Mittenthal, John & Keskin, Burcu & Melouk, Sharif, 2018. "Sourcing strategies for a capacitated firm subject to supply and demand uncertainty," Omega, Elsevier, vol. 77(C), pages 127-142.
    16. Oğuz Solyalı & Jean-François Cordeau & Gilbert Laporte, 2012. "Robust Inventory Routing Under Demand Uncertainty," Transportation Science, INFORMS, vol. 46(3), pages 327-340, August.
    17. 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.
    18. R. Kipp Martin & Linus Schrage, 1985. "Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming," Operations Research, INFORMS, vol. 33(3), pages 505-526, June.
    19. Pochet, Y. & Wolsey, L. A., 1994. "Polyhedra for lot-sizing with Wagner-Whitin costs," LIDAM Reprints CORE 1129, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Anantaram Balakrishnan & Joseph Geunes, 2000. "Requirements Planning with Substitutions: Exploiting Bill-of-Materials Flexibility in Production Planning," Manufacturing & Service Operations Management, INFORMS, vol. 2(2), pages 166-185, January.
    21. 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).
    22. 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.
    23. Stephen A. Smith & Narendra Agrawal, 2000. "Management of Multi-Item Retail Inventory Systems with Demand Substitution," Operations Research, INFORMS, vol. 48(1), pages 50-64, February.
    24. G. R. Bitran & S. Dasu, 1992. "Ordering Policies in an environment of Stochastic Yields and Substitutable Demands," Operations Research, INFORMS, vol. 40(5), pages 999-1017, October.
    25. Walter J. Bell & Louis M. Dalberto & Marshall L. Fisher & Arnold J. Greenfield & R. Jaikumar & Pradeep Kedia & Robert G. Mack & Paul J. Prutzman, 1983. "Improving the Distribution of Industrial Gases with an On-Line Computerized Routing and Scheduling Optimizer," Interfaces, INFORMS, vol. 13(6), pages 4-23, December.
    26. Leandro C. Coelho & Jean-François Cordeau & Gilbert Laporte, 2014. "Thirty Years of Inventory Routing," Transportation Science, INFORMS, vol. 48(1), pages 1-19, February.
    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. Amira Saker & Amr Eltawil & Islam Ali, 2023. "Adaptive Large Neighborhood Search Metaheuristic for the Capacitated Vehicle Routing Problem with Parcel Lockers," Logistics, MDPI, vol. 7(4), pages 1-27, October.
    2. Fan, Jie & Ou, Jinwen, 2023. "On dynamic lot sizing with bounded inventory for a perishable product," Omega, Elsevier, vol. 119(C).

    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. 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.
    3. 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).
    4. 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.
    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. Shin, Hojung & Park, Soohoon & Lee, Euncheol & Benton, W.C., 2015. "A classification of the literature on the planning of substitutable products," European Journal of Operational Research, Elsevier, vol. 246(3), pages 686-699.
    7. 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.
    8. Feng, Yuqiang & Che, Ada & Tian, Na, 2024. "Robust inventory routing problem under uncertain demand and risk-averse criterion," Omega, Elsevier, vol. 127(C).
    9. 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.
    10. Alarcon Ortega, Emilio J. & Schilde, Michael & Doerner, Karl F., 2020. "Matheuristic search techniques for the consistent inventory routing problem with time windows and split deliveries," Operations Research Perspectives, Elsevier, vol. 7(C).
    11. 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).
    12. 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.
    13. 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).
    14. 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.
    15. Chiu, Agustín & Angulo, Gustavo & Larrain, Homero, 2024. "Optimizing the long-term costs of an Inventory Routing Problem using linear relaxation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 183(C).
    16. Rossi, Roberto & Tomasella, Maurizio & Martin-Barragan, Belen & Embley, Tim & Walsh, Christopher & Langston, Matthew, 2019. "The Dynamic Bowser Routing Problem," European Journal of Operational Research, Elsevier, vol. 275(1), pages 108-126.
    17. 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.
    18. 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.
    19. 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.
    20. Mirzapour Al-e-hashem, Seyed M.J. & Rekik, Yacine & Mohammadi Hoseinhajlou, Ebrahim, 2019. "A hybrid L-shaped method to solve a bi-objective stochastic transshipment-enabled inventory routing problem," International Journal of Production Economics, Elsevier, vol. 209(C), pages 381-398.

    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:jomega:v:115:y:2023:i:c:s0305048322001591. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.