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

Capacity planning in logistics corridors: Deep reinforcement learning for the dynamic stochastic temporal bin packing problem

Author

Listed:
  • Farahani, Amirreza
  • Genga, Laura
  • Schrotenboer, Albert H.
  • Dijkman, Remco

Abstract

This paper addresses the challenge of managing uncertainty in the daily capacity planning of a terminal in a corridor-based logistics system. Corridor-based logistics systems facilitate the exchange of freight between two distinct regions, usually involving industrial and logistics clusters. In this context, we introduce the dynamic stochastic temporal bin packing problem. It models the assignment of individual containers to carriers’ trucks over discrete time units in real-time. We formulate it as a Markov decision process (MDP). Two distinguishing characteristics of our problem are the stochastic nature of the time-dependent availability of containers, i.e., container delays, and the continuous-time, or dynamic, aspect of the planning, where a container announcement may occur at any time moment during the planning horizon. We introduce an innovative real-time planning algorithm based on Proximal Policy Optimization (PPO), a Deep Reinforcement Learning (DRL) method, to allocate individual containers to eligible carriers in real-time. In addition, we propose some practical heuristics and two novel rolling-horizon batch-planning methods based on (stochastic) mixed-integer programming (MIP), which can be interpreted as computational information relaxation bounds because they delay decision making. The results show that our proposed DRL method outperforms the practical heuristics and effectively scales to larger-sized problems as opposed to the stochastic MIP-based approach, making our DRL method a practically appealing solution.

Suggested Citation

  • Farahani, Amirreza & Genga, Laura & Schrotenboer, Albert H. & Dijkman, Remco, 2024. "Capacity planning in logistics corridors: Deep reinforcement learning for the dynamic stochastic temporal bin packing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 191(C).
  • Handle: RePEc:eee:transe:v:191:y:2024:i:c:s1366554524003338
    DOI: 10.1016/j.tre.2024.103742
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554524003338
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.tre.2024.103742?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. Crainic, Teodor Gabriel & Gobbato, Luca & Perboli, Guido & Rei, Walter, 2016. "Logistics capacity planning: A stochastic bin packing formulation and a progressive hedging meta-heuristic," European Journal of Operational Research, Elsevier, vol. 253(2), pages 404-417.
    2. Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
    3. Dall'Orto, Leonardo Campo & Crainic, Teodor Gabriel & Leal, Jose Eugenio & Powell, Warren B., 2006. "The single-node dynamic service scheduling and dispatching problem," European Journal of Operational Research, Elsevier, vol. 170(1), pages 1-23, April.
    4. Ruibin Bai & Xinan Chen & Zhi-Long Chen & Tianxiang Cui & Shuhui Gong & Wentao He & Xiaoping Jiang & Huan Jin & Jiahuan Jin & Graham Kendall & Jiawei Li & Zheng Lu & Jianfeng Ren & Paul Weng & Ning Xu, 2023. "Analytics and machine learning in vehicle routing research," International Journal of Production Research, Taylor & Francis Journals, vol. 61(1), pages 4-30, January.
    5. Mauro Baldi & Teodor Crainic & Guido Perboli & Roberto Tadei, 2014. "Branch-and-price and beam search algorithms for the Variable Cost and Size Bin Packing Problem with optional items," Annals of Operations Research, Springer, vol. 222(1), pages 125-141, November.
    6. Zolfagharinia, Hossein & Haughton, Michael, 2016. "Effective truckload dispatch decision methods with incomplete advance load information," European Journal of Operational Research, Elsevier, vol. 252(1), pages 103-121.
    7. Giorgi Tadumadze & Simon Emde, 2022. "Loading and scheduling outbound trucks at a dispatch warehouse," IISE Transactions, Taylor & Francis Journals, vol. 54(8), pages 770-784, August.
    8. Baldi, Mauro Maria & Manerba, Daniele & Perboli, Guido & Tadei, Roberto, 2019. "A Generalized Bin Packing Problem for parcel delivery in last-mile logistics," European Journal of Operational Research, Elsevier, vol. 274(3), pages 990-999.
    9. Xiao Li & Hanchen Xu & Jinming Zhang & Hua-hua Chang, 2023. "Deep Reinforcement Learning for Adaptive Learning Systems," Journal of Educational and Behavioral Statistics, , vol. 48(2), pages 220-243, April.
    10. Powell, Warren B., 2019. "A unified framework for stochastic optimization," European Journal of Operational Research, Elsevier, vol. 275(3), pages 795-821.
    11. Baldi, Mauro Maria & Crainic, Teodor Gabriel & Perboli, Guido & Tadei, Roberto, 2012. "The generalized bin packing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(6), pages 1205-1220.
    12. Alves, Claudio & Valerio de Carvalho, J.M., 2007. "Accelerating column generation for variable sized bin-packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1333-1352, December.
    13. Martin Durbin & Karla Hoffman, 2008. "OR PRACTICE---The Dance of the Thirty-Ton Trucks: Dispatching and Scheduling in a Dynamic Environment," Operations Research, INFORMS, vol. 56(1), pages 3-19, February.
    14. Tadumadze, Giorgi & Emde, Simon, 2022. "Loading and scheduling outbound trucks at a dispatch warehouse," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 129007, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    15. Liang, Xuedong & Luo, Peng & Li, Xiaoyan & Wang, Xia & Shu, Lingli, 2023. "Crude oil price prediction using deep reinforcement learning," Resources Policy, Elsevier, vol. 81(C).
    16. Volodymyr Mnih & Koray Kavukcuoglu & David Silver & Andrei A. Rusu & Joel Veness & Marc G. Bellemare & Alex Graves & Martin Riedmiller & Andreas K. Fidjeland & Georg Ostrovski & Stig Petersen & Charle, 2015. "Human-level control through deep reinforcement learning," Nature, Nature, vol. 518(7540), pages 529-533, February.
    17. Dyckhoff, Harald, 1990. "A typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 44(2), pages 145-159, January.
    18. Kang, Jangha & Park, Sungsoo, 2003. "Algorithms for the variable sized bin packing problem," European Journal of Operational Research, Elsevier, vol. 147(2), pages 365-372, June.
    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. Baldi, Mauro Maria & Manerba, Daniele & Perboli, Guido & Tadei, Roberto, 2019. "A Generalized Bin Packing Problem for parcel delivery in last-mile logistics," European Journal of Operational Research, Elsevier, vol. 274(3), pages 990-999.
    2. Hu, Qian & Wei, Lijun & Lim, Andrew, 2018. "The two-dimensional vector packing problem with general costs," Omega, Elsevier, vol. 74(C), pages 59-69.
    3. Kallrath, Julia & Rebennack, Steffen & Kallrath, Josef & Kusche, Rüdiger, 2014. "Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges," European Journal of Operational Research, Elsevier, vol. 238(1), pages 374-389.
    4. Jiu, Song & Wang, Dan & Ma, Zujun, 2024. "Benders decomposition for robust distribution network design and operations in online retailing," European Journal of Operational Research, Elsevier, vol. 315(3), pages 1069-1082.
    5. Perboli, Guido & Brotcorne, Luce & Bruni, Maria Elena & Rosano, Mariangela, 2021. "A new model for Last-Mile Delivery and Satellite Depots management: The impact of the on-demand economy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    6. Hu, Qian & Lim, Andrew & Zhu, Wenbin, 2015. "The two-dimensional vector packing problem with piecewise linear cost function," Omega, Elsevier, vol. 50(C), pages 43-53.
    7. Lewis, R. & Song, X. & Dowsland, K. & Thompson, J., 2011. "An investigation into two bin packing problems with ordering and orientation implications," European Journal of Operational Research, Elsevier, vol. 213(1), pages 52-65, August.
    8. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    9. Ortmann, Frank G. & Ntene, Nthabiseng & van Vuuren, Jan H., 2010. "New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 306-315, June.
    10. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    11. Russo, Mauro & Sforza, Antonio & Sterle, Claudio, 2013. "An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem," International Journal of Production Economics, Elsevier, vol. 145(2), pages 451-462.
    12. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    13. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    14. Novas, Juan M. & Ramello, Juan Ignacio & Rodríguez, María Analía, 2020. "Generalized disjunctive programming models for the truck loading problem: A case study from the non-alcoholic beverages industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    15. B. S. C. Campello & C. T. L. S. Ghidini & A. O. C. Ayres & W. A. Oliveira, 2022. "A residual recombination heuristic for one-dimensional cutting stock problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 194-220, April.
    16. Igor Kierkosz & Maciej Luczak, 2014. "A hybrid evolutionary algorithm for the two-dimensional packing problem," 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. 22(4), pages 729-753, December.
    17. Anselmo Ramalho Pitombeira-Neto & Bruno de Athayde Prata, 2020. "A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(1), pages 178-192, April.
    18. Dell’Amico, Mauro & Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2019. "Mathematical models and decomposition methods for the multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(3), pages 886-899.
    19. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    20. E G Birgin & R D Lobato & R Morabito, 2010. "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(2), pages 306-320, February.

    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:transe:v:191:y:2024:i:c:s1366554524003338. 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/600244/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.