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

A Two-stage Stochastic Programming for AGV scheduling with random tasks and battery swapping in automated container terminals

Author

Listed:
  • Li, Linman
  • Li, Yuqing
  • Liu, Ran
  • Zhou, Yaoming
  • Pan, Ershun

Abstract

Automated guided vehicle (AGV) is one of the main equipment for horizontal transportation in automated container terminals, and the optimization of AGV scheduling has become increasingly important. Existing scheduling systems tend to make decisions based on deterministic conditions, ignoring the dynamic changes and uncertainties of the terminal environment, such as the arrival of random tasks during AGV operations. In addition, the battery swapping process is neglected in most AGV scheduling studies, yet it is crucial to ensure the operation of AGVs. In this paper, we construct a two-stage stochastic programming model for the joint scheduling problem of battery swapping and task operation with random tasks. A double-threshold constraint for battery swapping decision-making is adopted. The results show that the double-threshold strategy is better for AGV utilization than the single-threshold one. Upon the solution method, a simulation-based ant colony optimization algorithm is proposed. Sample average approximation is used to calculate the expected cost, and two local search procedures are introduced to improve the quality of the solutions. In the cases of multiple instances and several random task samples with different arrival rates, our method was compared with three practical policies under a deterministic model. Computational results show that the scheduling scheme considering random tasks in advance is more robust and stable.

Suggested Citation

  • Li, Linman & Li, Yuqing & Liu, Ran & Zhou, Yaoming & Pan, Ershun, 2023. "A Two-stage Stochastic Programming for AGV scheduling with random tasks and battery swapping in automated container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    • Handle: RePEc:eee:transe:v:174:y:2023:i:c:s1366554523000984
    DOI: 10.1016/j.tre.2023.103110
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554523000984
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2023.103110?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. Mauro Birattari & Prasanna Balaprakash & Thomas Stützle & Marco Dorigo, 2008. "Estimation-Based Local Search for Stochastic Combinatorial Optimization Using Delta Evaluations: A Case Study on the Probabilistic Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 20(4), pages 644-658, November.
    2. Ran Liu & Yangyi Tao & Qiaoyu Hu & Xiaolei Xie, 2017. "Simulation-based optimisation approach for the stochastic two-echelon logistics problem," International Journal of Production Research, Taylor & Francis Journals, vol. 55(1), pages 187-201, January.
    3. Chrysanthos E. Gounaris & Wolfram Wiesemann & Christodoulos A. Floudas, 2013. "The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty," Operations Research, INFORMS, vol. 61(3), pages 677-693, June.
    4. Zou, Bipan & Xu, Xianhao & Gong, Yeming (Yale) & De Koster, René, 2018. "Evaluating battery charging and swapping strategies in a robotic mobile fulfillment system," European Journal of Operational Research, Elsevier, vol. 267(2), pages 733-753.
    5. Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
    6. Angeloudis, Panagiotis & Bell, Michael G.H., 2010. "An uncertainty-aware AGV assignment algorithm for automated container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(3), pages 354-366, May.
    7. Feifeng Zheng & Xiaoyi Man & Feng Chu & Ming Liu & Chengbin Chu, 2019. "A two-stage stochastic programming for single yard crane scheduling with uncertain release times of retrieval tasks," International Journal of Production Research, Taylor & Francis Journals, vol. 57(13), pages 4132-4147, July.
    8. Schiffer, Maximilian & Walther, Grit, 2018. "Strategic planning of electric logistics fleet networks: A robust location-routing approach," Omega, Elsevier, vol. 80(C), pages 31-42.
    9. Carlo, Héctor J. & Vis, Iris F.A. & Roodbergen, Kees Jan, 2014. "Transport operations in container terminals: Literature overview, trends, research directions and classification scheme," European Journal of Operational Research, Elsevier, vol. 236(1), pages 1-13.
    10. Chrysanthos E. Gounaris & Panagiotis P. Repoussis & Christos D. Tarantilis & Wolfram Wiesemann & Christodoulos A. Floudas, 2016. "An Adaptive Memory Programming Framework for the Robust Capacitated Vehicle Routing Problem," Transportation Science, INFORMS, vol. 50(4), pages 1239-1260, November.
    11. Li, Chen & Qi, Xiangtong & Song, Dongping, 2016. "Real-time schedule recovery in liner shipping service with regular uncertainties and disruption events," Transportation Research Part B: Methodological, Elsevier, vol. 93(PB), pages 762-788.
    12. Luo, Jiabin & Wu, Yue, 2015. "Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 79(C), pages 49-64.
    13. Singh, Nitish & Dang, Quang-Vinh & Akcay, Alp & Adan, Ivo & Martagan, Tugce, 2022. "A matheuristic for AGV scheduling with battery constraints," European Journal of Operational Research, Elsevier, vol. 298(3), pages 855-873.
    14. 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.
    15. Frank Schneider & Ulrich W. Thonemann & Diego Klabjan, 2018. "Optimization of Battery Charging and Purchasing at Electric Vehicle Battery Swap Stations," Transportation Science, INFORMS, vol. 52(5), pages 1211-1234, October.
    16. Michel Gendreau & Ola Jabali & Walter Rei, 2016. "50th Anniversary Invited Article—Future Research Directions in Stochastic Vehicle Routing," Transportation Science, INFORMS, vol. 50(4), pages 1163-1173, November.
    17. Felipe, Ángel & Ortuño, M. Teresa & Righini, Giovanni & Tirado, Gregorio, 2014. "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 71(C), pages 111-128.
    18. Xiang, Xi & Liu, Changchun & Miao, Lixin, 2017. "A bi-objective robust model for berth allocation scheduling under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 294-319.
    19. Bipan Zou & Xianhao Xu & Yeming Gong & René de Koster, 2018. "Evaluating battery charging and swapping strategies in a robotic mobile fulfillment system," Post-Print hal-02312110, HAL.
    20. 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).
    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. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert, 2019. "The electric vehicle routing problem with energy consumption uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 225-255.
    2. Timothy M. Sweda & Irina S. Dolinskaya & Diego Klabjan, 2017. "Adaptive Routing and Recharging Policies for Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1326-1348, November.
    3. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    4. Singh, Nitish & Dang, Quang-Vinh & Akcay, Alp & Adan, Ivo & Martagan, Tugce, 2022. "A matheuristic for AGV scheduling with battery constraints," European Journal of Operational Research, Elsevier, vol. 298(3), pages 855-873.
    5. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    6. Alexandre M. Florio & Nabil Absi & Dominique Feillet, 2021. "Routing Electric Vehicles on Congested Street Networks," Transportation Science, INFORMS, vol. 55(1), pages 238-256, 1-2.
    7. Basso, Rafael & Kulcsár, Balázs & Sanchez-Diaz, Ivan & Qu, Xiaobo, 2022. "Dynamic stochastic electric vehicle routing with safe reinforcement learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    8. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    9. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert, 2018. "Charge scheduling for electric freight vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 115(C), pages 246-269.
    10. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem, 2021. "Green vehicle routing problem: A state-of-the-art review," Post-Print hal-03182944, HAL.
    11. Hamid R. Sayarshad & Vahid Mahmoodian & Nebojša Bojović, 2021. "Dynamic Inventory Routing and Pricing Problem with a Mixed Fleet of Electric and Conventional Urban Freight Vehicles," Sustainability, MDPI, vol. 13(12), pages 1-16, June.
    12. Alp, Osman & Tan, Tarkan & Udenio, Maximiliano, 2022. "Transitioning to sustainable freight transportation by integrating fleet replacement and charging infrastructure decisions," Omega, Elsevier, vol. 109(C).
    13. Roel M. Post & Paul Buijs & Michiel A. J. uit het Broek & Jose A. Lopez Alvarez & Nick B. Szirbik & Iris F. A. Vis, 2018. "A solution approach for deriving alternative fuel station infrastructure requirements," Flexible Services and Manufacturing Journal, Springer, vol. 30(3), pages 592-607, September.
    14. Chen, Wanying & Gong, Yeming & Chen, Qi & Wang, Hongwei, 2024. "Does battery management matter? Performance evaluation and operating policies in a self-climbing robotic warehouse," European Journal of Operational Research, Elsevier, vol. 312(1), pages 164-181.
    15. Enrico Bartolini & Dominik Goeke & Michael Schneider & Mengdie Ye, 2021. "The Robust Traveling Salesman Problem with Time Windows Under Knapsack-Constrained Travel Time Uncertainty," Transportation Science, INFORMS, vol. 55(2), pages 371-394, March.
    16. Roberti, R. & Wen, M., 2016. "The Electric Traveling Salesman Problem with Time Windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 32-52.
    17. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    18. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    19. Alberto Ceselli & Ángel Felipe & M. Teresa Ortuño & Giovanni Righini & Gregorio Tirado, 2021. "A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies," SN Operations Research Forum, Springer, vol. 2(1), pages 1-33, March.
    20. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.

    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:174:y:2023:i:c:s1366554523000984. 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.