Optimizing the container truck paths with uncertain travel time in container ports
Abstract
The yard template problem in container ports determines the assignment of space to store containers for the vessels, which could impact container truck paths. Actually, the travel time of container truck paths is uncertain. This paper considers the uncertainty from two perspectives: (1) the yard congestion in the context of yard truck interruptions, (2) the correlation among adjacent road sections (links). A mixed-integer programming model is proposed to minimize the travel time of container trucks. The reliable shortest path, which takes the correlation among links into account is firstly discussed. To settle the problem, a Shuffled Complex Evolution Approach (SCE-UA) algorithm is designed to work out the assignment of yard template, and the A* algorithm is presented to find the reliable shortest path according to the port operator’s attitude. In our case study, one yard in Dalian (China) container port is chosen to test the applicability of the model. The result shows the proposed model can save 9% of the travel time of container trucks, compared with the model without considering the correlation among adjacent links.
Keyword : container port, yard template, reliable shortest path, SCE-UA algorithm
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Chan, K. S.; Lam, W. H. K.; Tam, M. L. 2009. Real-time estimation of arterial travel times with spatial travel time covariance relationships, Transportation Research Record: Journal of the Transportation Research Board 2121: 102–109. https://doi.org/10.3141/2121-11
Chang, D.; Jiang, Z.; Yan, W.; He, J. 2010. Integrating berth allocation and quay crane assignments, Transportation Research Part E: Logistics and Transportation Review 46(6): 975–990. https://doi.org/10.1016/j.tre.2010.05.008
Chang, T.-S.; Nozick, L. K.; Turnquist, M. A. 2005. Multiobjective path finding in stochastic dynamic networks, with application to routing hazardous materials shipments, Transportation Science 39(3): 383–399. https://doi.org/10.1287/trsc.1040.0094
Chen, A.; Ji, Z. 2005. Path finding under uncertainty, Journal of Advanced Transportation 39(1): 19–37. https://doi.org/10.1002/atr.5670390104
Chen, B. Y.; Lam, W. H. K.; Sumalee, A.; Li, Z.-L. 2012. Reliable shortest path finding in stochastic networks with spatial correlated link travel times, International Journal of Geographical Information Science 26(2): 365–386. https://doi.org/10.1080/13658816.2011.598133
Chen, B. Y.; Lam, W. H. K.; Sumalee, A.; Li, Q.; Tam, M. L. 2014. Reliable shortest path problems in stochastic time-dependent networks, Journal of Intelligent Transportation Systems: Technology, Planning, and Operations 18(2): 177–189. https://doi.org/10.1080/15472450.2013.806851
Chen, C.; Tian, Z.; Yao, B. 2019. Optimization of two-stage location–routing–inventory problem with time-windows in food distribution network, Annals of Operations Research 273(1–2): 111–134. https://doi.org/10.1007/s10479-017-2514-3
Chen, L.; Langevin, A.; Lu, Z. 2013. Integrated scheduling of crane handling and truck transportation in a maritime container terminal, European Journal of Operational Research 225(1): 142–152. https://doi.org/10.1016/j.ejor.2012.09.019
Chen, X.; Zhou, X.; List, G. F. 2011. Using time-varying tolls to optimize truck arrivals at ports, Transportation Research Part E: Logistics and Transportation Review 47(6): 965–982. https://doi.org/10.1016/j.tre.2011.04.001
Duan, Q.; Sorooshian, S.; Gupta, V. K. 1994. Optimal use of the SCE-UA global optimization method for calibrating watershed models, Journal of Hydrology 158(3–4): 265–284. https://doi.org/10.1016/0022-1694(94)90057-4
Fan, L.; Wilson, W. W.; Dahl, B. 2012. Congestion, port expansion and spatial competition for US container imports, Transportation Research Part E: Logistics and Transportation Review 48(6): 1121–1136. https://doi.org/10.1016/j.tre.2012.04.006
Han, Y.; Lee, L. H.; Chew, E. P.; Tan, K. C. 2008. A yard storage strategy for minimizing traffic congestion in a marine container transshipment hub, OR Spectrum 30(4): 697–720. https://doi.org/10.1007/s00291-008-0127-6
Hart, P. E.; Nilsson, N. J.; Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics 4(2): 100–107. https://doi.org/10.1109/TSSC.1968.300136
He, J.; Huang, Y.; Yan, W.; Wang, S. 2015. Integrated internal truck, yard crane and quay crane scheduling in a container terminal considering energy consumption, Expert Systems with Applications 42(5): 2464–2487. https://doi.org/10.1016/j.eswa.2014.11.016
Huang, B.; Wu, Q.; Zhan, F. B. 2007. A shortest path algorithm with novel heuristics for dynamic transportation networks, International Journal of Geographical Information Science 21(6): 625–644. https://doi.org/10.1080/13658810601079759
Jiang, X.; Lee, L. H.; Chew, E. P.; Han, Y.; Tan, K. C. 2012. A container yard storage strategy for improving land utilization and operation efficiency in a transshipment hub port, European Journal of Operational Research 221(1): 64–73. https://doi.org/10.1016/j.ejor.2012.03.011
Jin, J. G.; Lee, D.-H.; Hu, H. 2015. Tactical berth and yard template design at container transshipment terminals: A column generation based approach, Transportation Research Part E: Logistics and Transportation Review 73: 168–184. https://doi.org/10.1016/j.tre.2014.11.009
Kaveshgar, N.; Huynh, N. 2015. Integrated quay crane and yard truck scheduling for unloading inbound containers, International Journal of Production Economics 159: 168–177. https://doi.org/10.1016/j.ijpe.2014.09.028
Kim, K. H.; Bae, J. W. 1998. Re-marshaling export containers in port container terminals, Computers & Industrial Engineering 35(3–4): 655–658. https://doi.org/10.1016/S0360-8352(98)00182-X
Kim, K. H.; Kim, K. Y. 2007. Optimal price schedules for storage of inbound containers, Transportation Research Part B: Methodological 41(8): 892–905. https://doi.org/10.1016/j.trb.2007.02.001
Lee, D.-H.; Jin, J. G. 2013. Feeder vessel management at container transshipment terminals, Transportation Research Part E: Logistics and Transportation Review 49(1): 201–216. https://doi.org/10.1016/j.tre.2012.08.006
Lee, H. L.; Chew, E. P.; Tan, K. C.; Han, Y. 2006. An optimization model for storage yard management in transshipment hubs, OR Spectrum 28(4): 539–561. https://doi.org/10.1007/s00291-006-0045-4
Lu, Y.; Le, M. 2014. The integrated optimization of container terminal scheduling with uncertain factors, Computers & Industrial Engineering 75: 209–216. https://doi.org/10.1016/j.cie.2014.06.018
Maloni, M.; Paul, J. A. 2013. Evaluating capacity utilization options for US west coast container ports, Transportation Journal 52(1): 52–79. https://doi.org/10.5325/transportationj.52.1.0052
Meng, Q.; Wang, S.; Andersson, H.; Thun, K. 2014. Containership routing and scheduling in liner shipping: overview and future research directions, Transportation Science 48(2): 265–280. https://doi.org/10.1287/trsc.2013.0461
Moccia, L.; Cordeau, J.-F.; Monaco, M. F.; Sammarra, M. 2009. A column generation heuristic for a dynamic generalized assignment problem, Computers & Operations Research 36(9): 2670–2681. https://doi.org/10.1016/j.cor.2008.11.022
Moorthy, R.; Teo, C.-P. 2006. Berth management in container terminal: the template design problem, OR Spectrum 28(4): 495–518. https://doi.org/10.1007/s00291-006-0036-5
Nie, Y.; Wu, X. 2009. Shortest path problem considering on-time arrival probability, Transportation Research Part B: Methodological 43(6): 597–613. https://doi.org/10.1016/j.trb.2009.01.008
Nikolova, E. 2009. Strategic Algorithms. PhD Thesis. Massachusetts Institute of Technology, MA, US. 212 p. Available from Internet: https://dspace.mit.edu/handle/1721.1/54673
Nishimura, E.; Imai, A.; Janssens, G. K.; Papadimitriou, S. 2009. Container storage and transshipment marine terminals, Transportation Research Part E: Logistics and Transportation Review 45(5): 771–786. https://doi.org/10.1016/j.tre.2009.03.003
Nishimura, E.; Imai, A.; Papadimitriou, S. 2005. Yard trailer routing at a maritime container terminal, Transportation Research Part E: Logistics and Transportation Review 41(1): 53–76. https://doi.org/10.1016/j.tre.2003.12.002
Peng, Z.; Shan, W.; Jia, P.; Yu, B.; Jiang, Y.; Yao, B. 2020. Stable ride-sharing matching for the commuters with payment design, Transportation 47(1): 1–21. https://doi.org/10.1007/s11116-018-9960-x
Peng, Z.; Shan, W.; Guan, F.; Yu, B. 2016. Stable vessel-cargo matching in dry bulk shipping market with price game mechanism, Transportation Research Part E: Logistics and Transportation Review 95: 76–94. https://doi.org/10.1016/j.tre.2016.08.007
Roy, D.; Gupta, A.; De Koster, R. B. M. 2016. A non-linear traffic flow-based queuing model to estimate container terminal throughput with AGVs, International Journal of Production Research 54(2): 472–493. https://doi.org/10.1080/00207543.2015.1056321
Shan, W.; Yan, Q.; Chen, C.; Zhang, M.; Yao, B.; Fu, X. 2019. Optimization of competitive facility location for chain stores, Annals of Operations Research 273(1–2): 187–205. https://doi.org/10.1007/s10479-017-2579-z
Shao, H.; Lam, W. H. K.; Chan, K. S. 2004. The problem of searching the reliable path for transportation networks with uncertainty, in Proceeding of 9th Conference of the Hong Kong Society for Transportation Studies, Hong Kong, China, 226–234.
Vis, I. F. A.; De Koster, R. 2003. Transshipment of containers at a container terminal: an overview, European Journal of Operational Research 147(1): 1–16. https://doi.org/10.1016/S0377-2217(02)00293-X
Wang, S.; Liu, Z.; Bell, M. G. H. 2015. Profit-based maritime container assignment models for liner shipping networks, Transportation Research Part B: Methodological 72: 59–76. https://doi.org/10.1016/j.trb.2014.11.006
Yao, B.; Chen, C.; Song, X.; Yang, X. 2019a. Fresh seafood delivery routing problem using an improved ant colony optimization, Annals of Operations Research 273(1): 163–186. https://doi.org/10.1007/s10479-017-2531-2
Yao, B.; Chen, C.; Zhang, L.; Yu, B.; Wang, Y. 2019b. Allocation method for transit lines considering the user equilibrium for operators, Transportation Research Part C: Emerging Technologies 105: 666–682. https://doi.org/10.1016/j.trc.2018.09.019
Yu, B.; Wang, H.; Shan, W.; Yao, B. 2018. Prediction of bus travel time using random forests based on near neighbors, Computer-Aided Civil and Infrastructure Engineering 33(4): 333–350. https://doi.org/10.1111/mice.12315
Yu, B.; Wang, H.; Song, X.; Zhao, Z.; Tian, Z.; Yao, B. 2020. Optimising subordinate net points layout of express enterprise with SCE-UA algorithm, Proceedings of the Institution of Civil Engineers – Transport 173(1): 51–58. https://doi.org/10.1680/jtran.16.00092
Zeng, W.; Church, R. L. 2009. Finding shortest paths on real road networks: the case for A*, International Journal of Geographical Information Science 23(4): 531–543. https://doi.org/10.1080/13658810801949850
Zhang, C.; Liu, J.; Wan, Y.-W.; Murty, K. G.; Linn, R. J. 2003. Storage space allocation in container terminals, Transportation Research Part B: Methodological 37(10): 883–903. https://doi.org/10.1016/S0191-2615(02)00089-9
Zhang, M.; Batta, R.; Nagi, R. 2009. Modeling of workflow congestion and optimization of flow routing in a manufacturing/warehouse facility, Management Science 55(2): 267–280. https://doi.org/10.1287/mnsc.1080.0916
Zhen, L. 2016. Modeling of yard congestion and optimization of yard template in container ports, Transportation Research Part B: Methodological 90: 83–104. https://doi.org/10.1016/j.trb.2016.04.011
Zhen, L. 2015. Tactical berth allocation under uncertainty, European Journal of Operational Research 247(3): 928–944. https://doi.org/10.1016/j.ejor.2015.05.079
Zhen, L. 2013. Yard template planning in transshipment hubs under uncertain berthing time and position, Journal of the Operational Research Society 64(9): 1418–1428. https://doi.org/10.1057/jors.2012.108
Zhen, L.; Chew, E. P.; Lee, L. H. 2011. An integrated model for berth template and yard template planning in transshipment hubs, Transportation Science 45(4): 483–504. https://doi.org/10.1287/trsc.1100.0364
Zhen, L.; Yu, S.; Wang, S.; Sun, Z. 2019. Scheduling quay cranes and yard trucks for unloading operations in container ports, Annals of Operations Research 273(1–2): 455–478. https://doi.org/10.1007/s10479-016-2335-9