[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Enhancing online yard crane scheduling through a two-stage rollout memetic genetic programming

  • Regular Research Paper
  • Published:
Memetic Computing Aims and scope Submit manuscript

Abstract

Over the past decade, the surge in global container port throughput has heightened the demand for terminal efficiency, with the container yard operations being central to the overall port performance. However, the unpredictable arrival of external trucks poses significant challenges for yard cranes which must simultaneously schedule operations for both internal and external tasks. Traditional yard crane scheduling methods often rely on outdated assumptions that fail to account for the dynamic impact of external tasks. In response, container terminals increasingly model the yard crane scheduling as an online problem. A notable advancement in online scheduling is the online rollout method, which evaluates the decisions based on the potential outcomes of their future rollout schedules rather than immediate priorities. Although this method outperforms the previous approach, it faces two main issues: the rollout simulation is time consuming, and decisions based solely on objective value of rollout schedules may not align with long-term scheduling objectives. To overcome these limitations, we have developed a two-stage adaptive rollout decision model. In the first stage, less desirable tasks are dynamically filtered out to reduce the number of rollout simulations required, while the second stage employs a genetic programming evolved evaluation function to infuse more refined forward-looking insights into the scheduling process. This approach has proven to significantly enhance yard scheduling efficiency and performance, as confirmed by experimental validation. Given the dynamic nature of yard crane operations, we believe this method could be beneficially applied to other dynamic scheduling contexts.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Algorithm 1
Algorithm 2
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availibility

No datasets were generated or analysed during the current study.

References

  1. UNCTAD: Container Port Annual Throughput, 2010-2022. https://unctadstat.unctad.org/datacentre/dataviewer/US.ContPortThroughput

  2. Chen X, Bai R, Qu R, Dong H, Chen J (2020) A data-driven genetic programming heuristic for real-world dynamic seaport container terminal truck dispatching. In: 2020 IEEE congress on evolutionary computation (CEC), pp 1–8. https://doi.org/10.1109/CEC48606.2020.9185659

  3. Chu H-C (2011) Empirical method for predicting internal–external truck trips at a major port. J Transp Eng 137(7):496–508

    Article  Google Scholar 

  4. Bai R, Chen X, Chen Z-L, Cui T, Gong S, He W, Jiang X, Jin H, Jin J, Kendall G, Li J, Lu Z, Ren J, Weng P, Xue N, Zhang H (2023) Analytics and machine learning in vehicle routing research. Int J Prod Res 61(1):4–30

    Article  Google Scholar 

  5. Ng WC, Mak KL (2005) Yard crane scheduling in port container terminals. Appl Math Model 29(3):263–276. https://doi.org/10.1016/j.apm.2004.09.009

    Article  Google Scholar 

  6. Ng WC, Mak KL (2005) An effective heuristic for scheduling a yard crane to handle jobs with different ready times. Eng Optim 37(8):867–877. https://doi.org/10.1080/03052150500323849

    Article  MathSciNet  Google Scholar 

  7. Kumar M, S N, O (2008) Optimization of yard crane scheduling using particle swarm optimization with genetic algorithm operators (psogao). J Sci Ind Res 67

  8. Guo X, Huang SY, Hsu WJ, Low MYH (2011) Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information. Adv Eng Inf 25(3):472–484. https://doi.org/10.1016/j.aei.2011.02.002

    Article  Google Scholar 

  9. He J, Tan C, Zhang Y (2019) Yard crane scheduling problem in a container terminal considering risk caused by uncertainty. Adv Eng Inf 39:14–24. https://doi.org/10.1016/j.aei.2018.11.004

    Article  Google Scholar 

  10. Zheng F, Man X, Chu F, Liu M, Chu C (2019) A two-stage stochastic programming for single yard crane scheduling with uncertain release times of retrieval tasks. Int J Prod Res 57(13):4132–4147. https://doi.org/10.1080/00207543.2018.1516903

    Article  Google Scholar 

  11. Liu W, Zhu X, Wang L, Yan B, Zhang X (2021) Optimization approach for yard crane scheduling problem with uncertain parameters in container terminals. J Adv Transp 2021:1–15. https://doi.org/10.1155/2021/5537114

    Article  Google Scholar 

  12. Jakobović D, Marasović K (2012) Evolving priority scheduling heuristics with genetic programming. Appl Soft Comput 12(9):2781–2789. https://doi.org/10.1016/j.asoc.2012.03.065

    Article  Google Scholar 

  13. Gil-Gala FJ, Mencía C, Sierra MR, Varela R (2019) Evolving priority rules for on-line scheduling of jobs on a single machine with variable capacity over time. Appl Soft Comput 85:105782. https://doi.org/10.1016/j.asoc.2019.105782

    Article  Google Scholar 

  14. Chen X, Bai R, Qu R, Dong H (2023) Cooperative double-layer genetic programming hyper-heuristic for online container terminal truck dispatching. IEEE Trans Evol Comput 27(5):1220–1234. https://doi.org/10.1109/TEVC.2022.3209985

    Article  Google Scholar 

  15. Chen X, Bao F, Qu R, Dong J, Bai R (2023) Neural network assisted genetic programming in dynamic container port truck dispatching. In: 2023 IEEE 26th international conference on intelligent transportation systems (ITSC), pp 2246–2251. https://doi.org/10.1109/ITSC57777.2023.10422513

  16. Chen X, Bai R, Qu R, Dong J, Jin Y (2024) Deep reinforcement learning assisted genetic programming ensemble hyper-heuristics for dynamic scheduling of container port trucks. IEEE Trans Evolut Comput. https://doi.org/10.1109/TEVC.2024.3381042

    Article  Google Scholar 

  17. Jin J, Cui T, Bai R, Qu R (2023) Container port truck dispatching optimization using Real2Sim based deep reinforcement learning. Eur J Oper Res 315(1):161–175

    Article  MathSciNet  Google Scholar 

  18. Jin C, Bai R, Zhang H (2024) Evolving priority rules for online yard crane scheduling with incomplete tasks data. In: 2024 IEEE congress on evolutionary computation (CEC), pp 1–10. https://doi.org/10.1109/CEC60901.2024.10611875

  19. Đurasević M, Planinić L, Gala FJG, Jakobović D (2022) Novel ensemble collaboration method for dynamic scheduling problems. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO ’22, pp 893–901. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/3512290.3528807

  20. Đurasević M, Gil-Gala FJ, Planinić L, Jakobović D (2023) Collaboration methods for ensembles of dispatching rules for the dynamic unrelated machines environment. Eng Appl Artif Intell 122:106096. https://doi.org/10.1016/j.engappai.2023.106096

    Article  Google Scholar 

  21. Gil-Gala FJ, Đurasević M, Varela R, Jakobović D (2023) Ensembles of priority rules to solve one machine scheduling problem in real-time. Inf Sci 634:340–358. https://doi.org/10.1016/j.ins.2023.03.114

    Article  Google Scholar 

  22. Huang SY, Li Y, Guo X (2014) Yard crane dispatching to minimize vessel turnaround times in container terminals. In: Proceedings of the winter simulation conference 2014, pp 1747–1758. https://doi.org/10.1109/WSC.2014.7020024

  23. Huang SY, Li Y (2017) Yard crane scheduling to minimize total weighted vessel loading time in container terminals. Flex Serv Manuf J 29(3–4):689–720. https://doi.org/10.1007/s10696-017-9299-1

    Article  Google Scholar 

  24. Zhang Y, Bai R, Qu R, Tu C, Jin J (2022) A deep reinforcement learning based hyper-heuristic for combinatorial optimisation with uncertainties. Eur J Oper Res 300(2):418–427. https://doi.org/10.1016/j.ejor.2021.10.032

    Article  MathSciNet  Google Scholar 

  25. Tu C, Bai R, Aickelin U, Zhang Y, Du H (2023) A deep reinforcement learning hyper-heuristic with feature fusion for online packing problems. Expert Syst Appl 230:120568. https://doi.org/10.1016/j.eswa.2023.120568

    Article  Google Scholar 

  26. Jakobović D, Marasović K (2012) Evolving priority scheduling heuristics with genetic programming. Appl Soft Comput 12(9):2781–2789. https://doi.org/10.1016/j.asoc.2012.03.065

    Article  Google Scholar 

  27. Jaklinović K, Đurasević M, Jakobović D (2021) Designing dispatching rules with genetic programming for the unrelated machines environment with constraints. Expert Syst Appl 172:114548. https://doi.org/10.1016/j.eswa.2020.114548

    Article  Google Scholar 

  28. Bertsekas D (2013) Rollout algorithms for discrete optimization: a survey. Handb Combin Optim. https://doi.org/10.1007/978-1-4419-7997-1_8

    Article  Google Scholar 

  29. Đurasević M, Jakobović D (2020) Automatic design of dispatching rules for static scheduling conditions. Neural Comput Appl 33(10):5043–5068. https://doi.org/10.1007/s00521-020-05292-w

    Article  Google Scholar 

  30. Zheng F, Man X, Chu F, Liu M, Chu C (2018) Two yard crane scheduling with dynamic processing time and interference. IEEE Trans Intell Transp Syst 19(12):3775–3784. https://doi.org/10.1109/TITS.2017.2780256

    Article  Google Scholar 

  31. Kang J-G, Kim Y-D (2002) Stowage planning in maritime container transportation. J Oper Res Soc 53(4):415–426. https://doi.org/10.1057/palgrave.jors.2601322

    Article  Google Scholar 

  32. Torkjazi M, Huynh N, Shiri S (2018) Truck appointment systems considering impact to drayage truck tours. Transp Res Part E Logist Transp Rev 116:208–228. https://doi.org/10.1016/j.tre.2018.06.003

    Article  Google Scholar 

  33. Sun S, Zheng Y, Dong Y, Li N, Jin Z, Yu Q (2022) Reducing external container trucks’ turnaround time in ports: a data-driven approach under truck appointment systems. Comput Ind Eng 174:108787. https://doi.org/10.1016/j.cie.2022.108787

    Article  Google Scholar 

  34. Xi Y, Jang J (2013) Minimizing total weighted tardiness on a single machine with sequence-dependent setup and future ready time. Int J Adv Manuf Technol 67(1–4):281–294. https://doi.org/10.1007/s00170-013-4774-7

    Article  Google Scholar 

  35. Fernandez-Viagas V, Costa A (2021) Two novel population based algorithms for the single machine scheduling problem with sequence dependent setup times and release times. Swarm Evol Comput 63:100869. https://doi.org/10.1016/j.swevo.2021.100869

    Article  Google Scholar 

  36. Du J, Leung JY-T (1990) Minimizing total tardiness on one machine is np-hard. Math Oper Res 15(3):483–495. https://doi.org/10.1287/moor.15.3.483

    Article  MathSciNet  Google Scholar 

  37. Gil-Gala FJ, Sierra MR, Mencía C, Varela R (2021) Genetic programming with local search to evolve priority rules for scheduling jobs on a machine with time-varying capacity. Swarm Evol Comput 66:100944. https://doi.org/10.1016/j.swevo.2021.100944

  38. Giffler B, Thompson GL (1960) Algorithms for solving production-scheduling problems. Oper Res 8(4):487–503

    Article  MathSciNet  Google Scholar 

  39. Zhang F, Mei Y, Nguyen S, Zhang M (2022) Learning strategies on scheduling heuristics of genetic programming in dynamic flexible job shop scheduling. In: 2022 IEEE congress on evolutionary computation (CEC), pp 1–8. https://doi.org/10.1109/CEC55065.2022.9870243

  40. Langdon WB, Poli R, McPhee NF, Koza JR (2008) In: Fulcher, J., Jain, L.C. (eds.) Genetic programming: an introduction and tutorial, with a survey of techniques and applications, pp 927–1028. Springer, Berlin. https://doi.org/10.1007/978-3-540-78293-3_22

  41. Branke J, Nguyen S, Pickardt CW, Zhang M (2016) Automated design of production scheduling heuristics: a review. IEEE Trans Evol Comput 20(1):110–124. https://doi.org/10.1109/TEVC.2015.2429314

    Article  Google Scholar 

  42. Pfund M, Fowler JW, Gadkari A, Chen Y (2008) Scheduling jobs on parallel machines with setup times and ready times. Comput Ind Eng 54(4):764–782. https://doi.org/10.1016/j.cie.2007.08.011

    Article  Google Scholar 

  43. Yu D, Li D, Sha M, Zhang D (2019) Carbon-efficient deployment of electric Rubber–Tyred gantry cranes in container terminals with workload uncertainty. Eur J Oper Res 275(2):552–569. https://doi.org/10.1016/j.ejor.2018.12.003

    Article  MathSciNet  Google Scholar 

  44. Li W, Goh M, Wu Y, Petering MEH, de Souza R, Wu YC (2012) A continuous time model for multiple yard crane scheduling with last minute job arrivals. Int J Prod Econ 136(2):332–343. https://doi.org/10.1016/j.ijpe.2011.12.020

    Article  Google Scholar 

  45. Kim KH, Lee KM, Hwang H (2003) Sequencing delivery and receiving operations for yard cranes in port container terminals. Int J Prod Econ 84(3):283–292. https://doi.org/10.1016/S0925-5273(02)00466-8

    Article  Google Scholar 

  46. Chou F-D, Wang H-M, Chang T-Y (2008) Algorithms for the single machine total weighted completion time scheduling problem with release times and sequence-dependent setups. Int J Adv Manuf Technol 43(7–8):810–821. https://doi.org/10.1007/s00170-008-1762-4

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, University of Nottingham Ningbo China, Ningbo, 315100, China

    Chenwei Jin, Ruibin Bai, Yuyang Zhou & Leshan Tan

  2. International Business School Suzhou, Xi’an Jiaotong-Liverpool University, Suzhou, 215123, China

    Xinan Chen

Authors
  1. Chenwei Jin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ruibin Bai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yuyang Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xinan Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Leshan Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

C.J. wrote the main manuscript text and prepared all the figures R.B. modified all sections Y.Z. modified Section 2, 3, 4 X.C. modified Abstract and Introduction L.T. modified Section 4.4 All authors review the manuscript.

Corresponding author

Correspondence to Ruibin Bai.

Ethics declarations

Conflict of interest

The authors declare no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jin, C., Bai, R., Zhou, Y. et al. Enhancing online yard crane scheduling through a two-stage rollout memetic genetic programming. Memetic Comp. 16, 467–489 (2024). https://doi.org/10.1007/s12293-024-00424-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-024-00424-4

Keywords

Search

Navigation