IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v323y2025i1p276-296.html
   My bibliography  Save this article

A rolling horizon heuristic approach for a multi-stage stochastic waste collection problem

Author

Listed:
  • Spinelli, Andrea
  • Maggioni, Francesca
  • Ramos, Tânia Rodrigues Pereira
  • Barbosa-Póvoa, Ana Paula
  • Vigo, Daniele

Abstract

In this paper we present a multi-stage stochastic optimization model to solve an inventory routing problem for the collection of recyclable municipal waste. The objective is the maximization of the total expected profit of the waste collection company. The decisions are related to the selection of the bins to be visited and the corresponding routing plan in a predefined time horizon. Stochasticity in waste accumulation is modeled through scenario trees generated via conditional density estimation and dynamic stochastic approximation techniques. The proposed formulation is solved through a rolling horizon approach, providing a rigorous worst-case analysis on its performance. Extensive computational experiments are carried out on small- and large-sized instances based on real data provided by a large Portuguese waste collection company. The impact of stochasticity on waste generation is examined through stochastic measures, showing the importance of adopting a stochastic model over a deterministic formulation when addressing a waste collection problem. The performance of the rolling horizon approach is evaluated, demonstrating that this heuristic provides cost-effective solutions in short computational time. Managerial insights related to different geographical configurations of the instances and varying levels of uncertainty are finally discussed.

Suggested Citation

  • Spinelli, Andrea & Maggioni, Francesca & Ramos, Tânia Rodrigues Pereira & Barbosa-Póvoa, Ana Paula & Vigo, Daniele, 2025. "A rolling horizon heuristic approach for a multi-stage stochastic waste collection problem," European Journal of Operational Research, Elsevier, vol. 323(1), pages 276-296.
    • Handle: RePEc:eee:ejores:v:323:y:2025:i:1:p:276-296
    DOI: 10.1016/j.ejor.2024.11.041
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724009329
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.11.041?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. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. Wang, Yong & Luo, Siyu & Fan, Jianxin & Zhen, Lu, 2024. "The multidepot vehicle routing problem with intelligent recycling prices and transportation resource sharing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    3. Cavagnini, Rossana & Bertazzi, Luca & Maggioni, Francesca, 2022. "A rolling horizon approach for a multi-stage stochastic fixed-charge transportation problem with transshipment," European Journal of Operational Research, Elsevier, vol. 301(3), pages 912-922.
    4. Elbek, Maria & Wøhlk, Sanne, 2016. "A variable neighborhood search for the multi-period collection of recyclable materials," European Journal of Operational Research, Elsevier, vol. 249(2), pages 540-550.
    5. Zhou, Jian & Li, Hui & Gu, Yujie & Zhao, Mingxuan & Xie, Xuehui & Zheng, Haoran & Fang, Xinghua, 2021. "A novel two-phase approach for the bi-objective simultaneous delivery and pickup problem with fuzzy pickup demands," International Journal of Production Economics, Elsevier, vol. 234(C).
    6. Francesca Maggioni & Elisabetta Allevi & Marida Bertocchi, 2014. "Bounds in Multistage Linear Stochastic Programming," Journal of Optimization Theory and Applications, Springer, vol. 163(1), pages 200-229, October.
    7. 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).
    8. Edoardo Fadda & Luca Gobbato & Guido Perboli & Mariangela Rosano & Roberto Tadei, 2018. "Waste Collection in Urban Areas: A Case Study," Interfaces, INFORMS, vol. 48(4), pages 307-322, August.
    9. Bertazzi, Luca & Maggioni, Francesca, 2018. "A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach," European Journal of Operational Research, Elsevier, vol. 267(2), pages 555-569.
    10. 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.
    11. 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.
    12. N H Moin & S Salhi, 2007. "Inventory routing problems: a logistical overview," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1185-1194, September.
    13. Angelelli, Enrico & Grazia Speranza, Maria, 2002. "The periodic vehicle routing problem with intermediate facilities," European Journal of Operational Research, Elsevier, vol. 137(2), pages 233-247, March.
    14. Suresh Chand & Vernon Ning Hsu & Suresh Sethi, 2002. "Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography," Manufacturing & Service Operations Management, INFORMS, vol. 4(1), pages 25-43, September.
    15. 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.
    16. A Gruler & C Fikar & A A Juan & P Hirsch & C Contreras-Bolton, 2017. "Supporting multi-depot and stochastic waste collection management in clustered urban areas via simulation–optimization," Journal of Simulation, Taylor & Francis Journals, vol. 11(1), pages 11-19, February.
    17. Han, Jialin & Zhang, Jiaxiang & Guo, Haoyue & Zhang, Ning, 2024. "Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm," European Journal of Operational Research, Elsevier, vol. 316(3), pages 958-975.
    18. Francesca Maggioni & Michal Kaut & Luca Bertazzi, 2009. "Stochastic optimization models for a single-sink transportation problem," Computational Management Science, Springer, vol. 6(2), pages 251-267, May.
    19. 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.
    20. Vera C. Hemmelmayr & Karl F. Doerner & Richard F. Hartl & Daniele Vigo, 2014. "Models and Algorithms for the Integrated Planning of Bin Allocation and Vehicle Routing in Solid Waste Management," Transportation Science, INFORMS, vol. 48(1), pages 103-120, February.
    21. R. Baldacci & E. Hadjiconstantinou & A. Mingozzi, 2004. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation," Operations Research, INFORMS, vol. 52(5), pages 723-738, October.
    22. Florio, Alexandre M. & Gendreau, Michel & Hartl, Richard F. & Minner, Stefan & Vidal, Thibaut, 2023. "Recent advances in vehicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price-and-cut," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1081-1093.
    23. 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.
    24. Tran, Trung Hieu & Nguyen, Thu Ba T. & Le, Hoa Sen T. & Phung, Duc Chinh, 2024. "Formulation and solution technique for agricultural waste collection and transport network design," European Journal of Operational Research, Elsevier, vol. 313(3), pages 1152-1169.
    25. 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)

    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. Christina Hess & Alina G. Dragomir & Karl F. Doerner & Daniele Vigo, 2024. "Waste collection routing: a survey on problems and methods," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 32(2), pages 399-434, June.
    2. 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).
    3. Cavagnini, Rossana & Bertazzi, Luca & Maggioni, Francesca, 2022. "A rolling horizon approach for a multi-stage stochastic fixed-charge transportation problem with transshipment," European Journal of Operational Research, Elsevier, vol. 301(3), pages 912-922.
    4. Han, Jialin & Zhang, Jiaxiang & Guo, Haoyue & Zhang, Ning, 2024. "Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm," European Journal of Operational Research, Elsevier, vol. 316(3), pages 958-975.
    5. 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.
    6. 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.
    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. 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.
    9. Gambella, Claudio & Maggioni, Francesca & Vigo, Daniele, 2019. "A stochastic programming model for a tactical solid waste management problem," European Journal of Operational Research, Elsevier, vol. 273(2), pages 684-694.
    10. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    11. Mahmutoğulları, Özlem & Yaman, Hande, 2023. "A Branch-and-Cut Algorithm for the Inventory Routing Problem with Product Substitution," Omega, Elsevier, vol. 115(C).
    12. Shuihua Han & Yudi Mo & Linlin Chen & Zongwei Luo & Cyril R. H. Foropon & H. M. Belal, 2025. "A multi-period closed-loop supply chain network design with circular route planning," Annals of Operations Research, Springer, vol. 348(3), pages 1195-1233, May.
    13. Gläser, Sina, 2022. "A waste collection problem with service type option," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1216-1230.
    14. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    15. 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.
    16. Pamela C. Nolz, 2021. "Optimizing construction schedules and material deliveries in city logistics: a case study from the building industry," Flexible Services and Manufacturing Journal, Springer, vol. 33(3), pages 846-878, September.
    17. Zajac, Sandra & Huber, Sandra, 2021. "Objectives and methods in multi-objective routing problems: a survey and classification scheme," European Journal of Operational Research, Elsevier, vol. 290(1), pages 1-25.
    18. Gläser, Sina & Stücken, Mareike, 2021. "Introduction of an underground waste container system–model and solution approaches," European Journal of Operational Research, Elsevier, vol. 295(2), pages 675-689.
    19. Markov, Iliya & Varone, Sacha & Bierlaire, Michel, 2016. "Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 256-273.
    20. Markov, Iliya & Bierlaire, Michel & Cordeau, Jean-François & Maknoon, Yousef & Varone, Sacha, 2018. "A unified framework for rich routing problems with stochastic demands," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 213-240.

    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:323:y:2025:i:1:p:276-296. 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.