IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v211y2019icp44-59.html
   My bibliography  Save this article

Heuristic algorithm based on reduce and optimize approach for a selective and periodic inventory routing problem in a waste vegetable oil collection environment

Author

Listed:
  • Cárdenas-Barrón, Leopoldo Eduardo
  • González-Velarde, José Luis
  • Treviño-Garza, Gerardo
  • Garza-Nuñez, Dagoberto

Abstract

This paper develops a general heuristic algorithm to solve the selective and periodic inventory routing problem (SPIRP) in a waste vegetable oil collection environment. In the past, the SPIRP has been formulated and solved via a valid set of inequalities and an adaptive large-neighborhood search algorithm. The proposed algorithm is based on a reduce and optimize approach (ROA) and a new inequality. The ROA always solves the problem using a small feasible subset containing a near-optimal solution. Two available sets of benchmark instances are tested and solved: (a) in the first set with 36 instances, the new algorithm improves the reported solution in 94.44% of the instances; (b) in the second set with 54 instances, the results show that the proposed algorithm finds a better solution than the previously published ones in 92.59% of the cases. In a third set composed of 24 very large instances, the proposed heuristic algorithm always finds better solutions than the CPLEX MIP solver. Finally, the computational results show that the proposed algorithm obtains, on average, a solution within 1.99%, 2.86%, and 7.41% of optimality for the first, second, and third set of instances, respectively. Also, the computational experiments show that the heuristic algorithm is effective and efficient in instances with up to 300 source nodes.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:proeco:v:211:y:2019:i:c:p:44-59
    DOI: 10.1016/j.ijpe.2019.01.026
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527319300349
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2019.01.026?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. Oded Berman & Richard C. Larson, 2001. "Deliveries in an Inventory/Routing Problem Using Stochastic Dynamic Programming," Transportation Science, INFORMS, vol. 35(2), pages 192-213, May.
    2. Ann Melissa Campbell & Martin W. P. Savelsbergh, 2004. "A Decomposition Approach for the Inventory-Routing Problem," Transportation Science, INFORMS, vol. 38(4), pages 488-502, November.
    3. Bektas, Tolga & Laporte, Gilbert, 2011. "The Pollution-Routing Problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1232-1250, September.
    4. Lars Magnus Hvattum & Arne Løkketangen & Gilbert Laporte, 2009. "Scenario Tree-Based Heuristics for Stochastic Inventory-Routing Problems," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 268-285, May.
    5. Daniel Adelman, 2003. "Price-Directed Replenishment of Subsets: Methodology and Its Application to Inventory Routing," Manufacturing & Service Operations Management, INFORMS, vol. 5(4), pages 348-371, May.
    6. Iassinovskaia, Galina & Limbourg, Sabine & Riane, Fouad, 2017. "The inventory-routing problem of returnable transport items with time windows and simultaneous pickup and delivery in closed-loop supply chains," International Journal of Production Economics, Elsevier, vol. 183(PB), pages 570-582.
    7. Thierry Benoist & Frédéric Gardi & Antoine Jeanjean & Bertrand Estellon, 2011. "Randomized Local Search for Real-Life Inventory Routing," Transportation Science, INFORMS, vol. 45(3), pages 381-398, August.
    8. Raa, Birger & Aghezzaf, El-Houssaine, 2009. "A practical solution approach for the cyclic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 192(2), pages 429-441, January.
    9. Mirzapour Al-e-hashem, S.M.J. & Rekik, Yacine, 2014. "Multi-product multi-period Inventory Routing Problem with a transshipment option: A green approach," International Journal of Production Economics, Elsevier, vol. 157(C), pages 80-88.
    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. Krikke, Harold & le Blanc, Ieke & van Krieken, Maaike & Fleuren, Hein, 2008. "Low-frequency collection of materials disassembled from end-of-life vehicles: On the value of on-line monitoring in optimizing route planning," International Journal of Production Economics, Elsevier, vol. 111(2), pages 209-228, February.
    12. Oğuz Solyalı & Haldun Süral, 2011. "A Branch-and-Cut Algorithm Using a Strong Formulation and an A Priori Tour-Based Heuristic for an Inventory-Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 335-345, August.
    13. D Ronen, 2002. "Marine inventory routing: shipments planning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(1), pages 108-114, January.
    14. Anton J. Kleywegt & Vijay S. Nori & Martin W. P. Savelsbergh, 2004. "Dynamic Programming Approximations for a Stochastic Inventory Routing Problem," Transportation Science, INFORMS, vol. 38(1), pages 42-70, February.
    15. S. Michel & F. Vanderbeck, 2012. "A Column-Generation Based Tactical Planning Method for Inventory Routing," Operations Research, INFORMS, vol. 60(2), pages 382-397, April.
    16. Schultmann, Frank & Zumkeller, Moritz & Rentz, Otto, 2006. "Modeling reverse logistic tasks within closed-loop supply chains: An example from the automotive industry," European Journal of Operational Research, Elsevier, vol. 171(3), pages 1033-1050, June.
    17. 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.
    18. Anton J. Kleywegt & Vijay S. Nori & Martin W. P. Savelsbergh, 2002. "The Stochastic Inventory Routing Problem with Direct Deliveries," Transportation Science, INFORMS, vol. 36(1), pages 94-118, February.
    19. 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.
    20. J Mar-Ortiz & B Adenso-Diaz & J L González-Velarde, 2011. "Design of a recovery network for WEEE collection: the case of Galicia, Spain," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(8), pages 1471-1484, August.
    21. 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.
    22. Guerrero, W.J. & Prodhon, C. & Velasco, N. & Amaya, C.A., 2013. "Hybrid heuristic for the inventory location-routing problem with deterministic demand," International Journal of Production Economics, Elsevier, vol. 146(1), pages 359-370.
    23. Zhao, Qiu-Hong & Wang, Shou-Yang & Lai, K.K., 2007. "A partition approach to the inventory/routing problem," European Journal of Operational Research, Elsevier, vol. 177(2), pages 786-802, March.
    24. Seyed Mohammad Javad Mirzapour Al-E-Hashem & Yacine Rekik, 2014. "Multi-product multi-period inventory routing problem with a transshipment option : A green approach," Post-Print hal-02313081, HAL.
    25. Moin, N.H. & Salhi, S. & Aziz, N.A.B., 2011. "An efficient hybrid genetic algorithm for the multi-product multi-period inventory routing problem," International Journal of Production Economics, Elsevier, vol. 133(1), pages 334-343, September.
    26. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    27. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2014. "Optimization-Based Adaptive Large Neighborhood Search for the Production Routing Problem," Transportation Science, INFORMS, vol. 48(1), pages 20-45, February.
    28. Bailing Liu & Hui Chen & Yanhui Li & Xiang Liu, 2015. "A Pseudo-Parallel Genetic Algorithm Integrating Simulated Annealing for Stochastic Location-Inventory-Routing Problem with Consideration of Returns in E-Commerce," Discrete Dynamics in Nature and Society, Hindawi, vol. 2015, pages 1-15, March.
    29. Roar Grønhaug & Marielle Christiansen & Guy Desaulniers & Jacques Desrosiers, 2010. "A Branch-and-Price Method for a Liquefied Natural Gas Inventory Routing Problem," Transportation Science, INFORMS, vol. 44(3), pages 400-415, August.
    30. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    31. 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.
    32. AGHEZZAF, El-Houssaine & RAA, Birger & VAN LANDEGHEM, Hendrik, 2006. "Modeling inventory routing problems in supply chains of high consumption products," LIDAM Reprints CORE 1786, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    33. Daniel Adelman, 2004. "A Price-Directed Approach to Stochastic Inventory/Routing," Operations Research, INFORMS, vol. 52(4), pages 499-514, August.
    34. 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.
    35. 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.
    36. 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.
    37. Patrick Jaillet & Jonathan F. Bard & Liu Huang & Moshe Dror, 2002. "Delivery Cost Approximations for Inventory Routing Problems in a Rolling Horizon Framework," Transportation Science, INFORMS, vol. 36(3), pages 292-300, August.
    38. Yu, Yugang & Chen, Haoxun & Chu, Feng, 2008. "A new model and hybrid approach for large scale inventory routing problems," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1022-1040, September.
    39. T R P Ramos & R C Oliveira, 2011. "Delimitation of service areas in reverse logistics networks with multiple depots," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1198-1210, July.
    40. Aghezzaf, El-Houssaine & Raa, Birger & Van Landeghem, Hendrik, 2006. "Modeling inventory routing problems in supply chains of high consumption products," European Journal of Operational Research, Elsevier, vol. 169(3), pages 1048-1063, March.
    41. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    42. Raa, Birger, 2015. "Fleet optimization for cyclic inventory routing problems," International Journal of Production Economics, Elsevier, vol. 160(C), pages 172-181.
    43. 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.
    44. Awi Federgruen & Paul Zipkin, 1984. "A Combined Vehicle Routing and Inventory Allocation Problem," Operations Research, INFORMS, vol. 32(5), pages 1019-1037, October.
    45. Vishal Gaur & Marshall L. Fisher, 2004. "A Periodic Inventory Routing Problem at a Supermarket Chain," Operations Research, INFORMS, vol. 52(6), pages 813-822, December.
    46. 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. Soysal, Mehmet & Koç, Çağrı & Çimen, Mustafa & İbiş, Merve, 2023. "Managing returnable transport items in a vendor managed inventory system," Socio-Economic Planning Sciences, Elsevier, vol. 86(C).
    2. Erfan Babaee Tirkolaee & Alireza Goli & Selma Gütmen & Gerhard-Wilhelm Weber & Katarzyna Szwedzka, 2023. "A novel model for sustainable waste collection arc routing problem: Pareto-based algorithms," Annals of Operations Research, Springer, vol. 324(1), pages 189-214, May.
    3. Olmez, Omer Berk & Gultekin, Ceren & Balcik, Burcu & Ekici, Ali & Özener, Okan Örsan, 2022. "A variable neighborhood search based matheuristic for a waste cooking oil collection network design problem," European Journal of Operational Research, Elsevier, vol. 302(1), pages 187-202.

    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. 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.
    2. 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.
    3. Jafarian, Ahmad & Asgari, Nasrin & Mohri, Seyed Sina & Fatemi-Sadr, Elham & Farahani, Reza Zanjirani, 2019. "The inventory-routing problem subject to vehicle failure," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 254-294.
    4. Song, Ruidian & Zhao, Lei & Van Woensel, Tom & Fransoo, Jan C., 2019. "Coordinated delivery in urban retail," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 122-148.
    5. Yves Crama & Mahmood Rezaei & Martin Savelsbergh & Tom Van Woensel, 2018. "Stochastic Inventory Routing for Perishable Products," Transportation Science, INFORMS, vol. 52(3), pages 526-546, June.
    6. Sonntag, Danja R. & Schrotenboer, Albert H. & Kiesmüller, Gudrun P., 2023. "Stochastic inventory routing with time-based shipment consolidation," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1186-1201.
    7. Divsalar, Ali & Vansteenwegen, Pieter, 2016. "A two-phase algorithm for the cyclic inventory routing problemAuthor-Name: Chitsaz, Masoud," European Journal of Operational Research, Elsevier, vol. 254(2), pages 410-426.
    8. 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).
    9. Ahmed Kheiri, 2020. "Heuristic Sequence Selection for Inventory Routing Problem," Transportation Science, INFORMS, vol. 54(2), pages 302-312, March.
    10. Ali Ekici & Okan Örsan Özener & Gültekin Kuyzu, 2015. "Cyclic Delivery Schedules for an Inventory Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 817-829, November.
    11. Zhouxing Su & Zhipeng Lü & Zhuo Wang & Yanmin Qi & Una Benlic, 2020. "A Matheuristic Algorithm for the Inventory Routing Problem," Transportation Science, INFORMS, vol. 54(2), pages 330-354, March.
    12. 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.
    13. 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.
    14. Timajchi, Ali & Mirzapour Al-e-Hashem, Seyed M.J. & Rekik, Yacine, 2019. "Inventory routing problem for hazardous and deteriorating items in the presence of accident risk with transshipment option," International Journal of Production Economics, Elsevier, vol. 209(C), pages 302-315.
    15. 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.
    16. Rau, Hsin & Budiman, Syarif Daniel & Widyadana, Gede Agus, 2018. "Optimization of the multi-objective green cyclical inventory routing problem using discrete multi-swarm PSO method," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 120(C), pages 51-75.
    17. Bertazzi, Luca & Chua, Geoffrey A. & Laganà, Demetrio & Paradiso, Rosario, 2022. "Analysis of effective sets of routes for the split-delivery periodic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 298(2), pages 463-477.
    18. Mohd Kamarul Irwan Abdul Rahim & El-Houssaine Aghezzaf & Veronique Limère & Birger Raa, 2016. "Analysing the effectiveness of vendor-managed inventory in a single-warehouse, multiple-retailer system," International Journal of Systems Science, Taylor & Francis Journals, vol. 47(8), pages 1953-1965, June.
    19. Jin-Hwa Song & Martin Savelsbergh, 2007. "Performance Measurement for Inventory Routing," Transportation Science, INFORMS, vol. 41(1), pages 44-54, February.
    20. Hadi Jahangir & Mohammad Mohammadi & Seyed Hamid Reza Pasandideh & Neda Zendehdel Nobari, 2019. "Comparing performance of genetic and discrete invasive weed optimization algorithms for solving the inventory routing problem with an incremental delivery," Journal of Intelligent Manufacturing, Springer, vol. 30(6), pages 2327-2353, August.

    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:proeco:v:211:y:2019:i:c:p:44-59. 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/ijpe .

    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.