Scheduling ASC and AGV considering direct, buffer, and hybrid modes for transferring containers. (English) Zbl 07765529
Summary: At automated container terminals (ACTs), automated stacking cranes (ASCs) and automated guided vehicles (AGVs) perform yard vertical loading/unloading and horizontal transport operations, respectively. The two operating devices transfer containers at the seaside. This paper studies an integrated scheduling problem of ASCs and AGVs considering direct, buffer, and hybrid modes for transferring containers. In direct mode, the two devices are synchronized at the pad to transfer containers from one device to the other. Buffer mode decouples the synchronized operations between ASCs and AGVs, allowing one device to temporarily store the container at buffer sites (i.e., AGV partners) for subsequent operations by the other. Supported by advanced positioning technology, direct mode speeds up the transferring operations and helps to reduce partner overflow. Therefore, the hybrid mode with a combination of pads and partners makes operations more flexible. We formulate the integrated scheduling problem as a multi-layer vehicle routing problem and connect them via precedence relationships and transfer constraints. Three continuous time integer programming models are developed to sequence the handling tasks under the minimization of the makespan. A relaxation model and the cutting-plane approach are proposed to derive a lower bound. To enhance the search capability, a genetic algorithm embedded with several neighborhood generation operators is developed to solve the problem. In addition, a flexible strategy with a task pool and a transfer mode selection mechanism is proposed for decoding individuals in the genetic algorithms into handling sequences. Numerical experiments show that the hybrid mode outperforms the direct and buffer modes by an average of 12.35% and 8.26%, respectively. The makespan gap between the lower bound and the proposed algorithm is 6.5% on average. In addition, AGV utilization is highest in the hybrid mode, and the fluctuations in the container arrival rate have minimal effect on the hybrid mode. Moreover, based on the results, the opportunity and risk of configuring a hybrid mode through technological upgrading are discussed.
MSC:
| 90Bxx | Operations research and management science |
Keywords:
automated container terminal; automated guided vehicles; automated stacking cranes; genetic algorithm; logistics managementReferences:
| [1] | Abou Kasm, O.; Diabat, A.; Cheng, T. C.E., The integrated berth allocation, quay crane assignment and scheduling problem: mathematical formulations and a case study, Ann. Oper. Res., 291, 1-2, 435-461 (2020) |
| [2] | Ahmed, E.; El-Abbasy, M. S.; Zayed, T.; Alfalah, G.; Alkass, S., Synchronized scheduling model for container terminals using simulated double-cycling strategy, Comput. Ind. Eng., 154 (2021) |
| [3] | Boysen, N.; Briskorn, D.; Meisel, F., A generalized classification scheme for crane scheduling with interference, Eur. J. Oper. Res., 258, 1, 343-357 (2017) · Zbl 1380.90108 |
| [4] | Briskorn, D.; Emde, S.; Boysen, N., Cooperative twin-crane scheduling, Discrete Appl. Math., 211, 1, 40-57 (2016) · Zbl 1349.90074 |
| [5] | Caballini, C.; Paolucci, M., A rostering approach to minimize health risks for workers: An application to a container terminal in the Italian port of Genoa, Omega, 95 (2020) |
| [6] | Cahyono, R. T.; Kenaka, S. P.; Jayawardhana, B., Simultaneous allocation and scheduling of quay cranes, yard cranes, and trucks in dynamical integrated container terminal operations, IEEE Trans. Intell. Transp. Syst., 23, 7, 8564-8578 (2022) |
| [7] | Cao, J. X.; Lee, D.-H.; Chen, J. H.; Shi, Q., The integrated yard truck and yard crane scheduling problem: benders’ decomposition-based methods, Trans. Res. E Logist. Transp. Rev., 46, 3, 344-353 (2010) |
| [8] | Carlo, H. J.; Vis, I. F.A.; Roodbergen, K. J., Transport operations in container terminals: literature overview, trends, research directions and classification scheme, Eur. J. Oper. Res., 236, 1, 1-13 (2014) · Zbl 1338.90003 |
| [9] | Chang, Y.; Zhu, X.; Yan, B.; Wang, L., Integrated scheduling of handling operations in railway container terminals, Transp. Lett., 11, 7, 402-412 (2019) |
| [10] | Chen, X.; He, S.; Zhang, Y.; Tong, L.; Shang, P.; Zhou, X., Yard crane and AGV scheduling in automated container terminal: A multi-robot task allocation framework, Transp. Res. C Emerging Technol., 114, 1, 241-271 (2020) |
| [11] | Chen, L.; Langevin, A.; Lu, Z. Q., Integrated scheduling of crane handling and truck transportation in a maritime container terminal, Eur. J. Oper. Res., 225, 1, 142-152 (2013) · Zbl 1292.90184 |
| [12] | Dell, R. F.; Royset, J. O.; Zyngiridis, I., Optimizing container movements using one and two automated stacking cranes, J. Ind. Manage. Optimizat., 5, 2, 285-302 (2009) · Zbl 1188.90175 |
| [13] | Dorndorf, U.; Schneider, F., Scheduling automated triple cross-over stacking cranes in a container yard, OR Spectr., 32, 3, 617-632 (2010) · Zbl 1200.90072 |
| [14] | Gharehgozli, A. H.; Laporte, G.; Yu, Y.; de Koster, R., Scheduling Twin Yard Cranes in a Container Block, Transp. Sci., 49, 3, 686-705 (2015) |
| [15] | Gharehgozli, A. H.; Vernooij, F. G.; Zaerpour, N., A simulation study of the performance of twin automated stacking cranes at a seaport container terminal, Eur. J. Oper. Res., 261, 1, 108-128 (2017) |
| [16] | Goodchild, A. V.; Daganzo, C. F., Crane double cycling in container ports: Planning methods and evaluation, Transp. Res. B Methodol., 41, 8, 875-891 (2007) |
| [17] | Grunow, M.; Gunther, H.-O.; Lehmann, M., Dispatching multi-load AGVs in highly automated seaport container terminals, OR Spectr., 26, 2, 211-235 (2004) · Zbl 1069.90032 |
| [18] | Han, X. L.; Wang, Q. Q.; Huang, J. W., Scheduling cooperative twin automated stacking cranes in automated container terminals, Comput. Ind. Eng., 128, 1, 553-558 (2019) |
| [19] | He, J. L.; Huan, Y. F.; Yan, W.; Wang, S. I.A., Integrated internal truck, yard crane and quay crane scheduling in a container terminal considering energy consumption, Expert Syst. Appl., 42, 5, 2464-2487 (2015) |
| [20] | Hsu, H.-P.; Tai, H.-H.; Wang, C.-N.; Chou, C.-C., Scheduling of collaborative operations of yard cranes and yard trucks for export containers using hybrid approaches, Adv. Eng. Inf., 48 (2021) |
| [21] | Hu, Q.; Corman, F.; Wiegmans, B.; Lodewijks, G., A tabu search algorithm to solve the integrated planning of container on an inter-terminal network connected with a hinterland rail network, Transp. Res. C Emerging Technol., 91, 1, 15-36 (2018) |
| [22] | Hu, Z.-H.; Sheu, J.-B.; Luo, J. X., Sequencing twin automated stacking cranes in a block at automated container terminal, Transp. Res. C Emerging Technol., 69, 1, 208-227 (2016) |
| [23] | Ji, S. W.; Luan, D.; Chen, Z. R.; Guo, D., Integrated scheduling in automated container terminals considering AGV conflict-free routing, Transp. Lett. Int. J. Transp. Res., 13, 7, 501-513 (2021) |
| [24] | Jonker, T.; Duinkerken, M. B.; Yorke-Smith, N.; de Waal, A.; Negenborn, R. R., Coordinated optimization of equipment operations in a container terminal, Flex. Serv. Manuf. J., 33, 2, 281-311 (2021) |
| [25] | Kaveshgar, N.; Huynh, N., Integrated quay crane and yard truck scheduling for unloading inbound containers, Int. J. Prod. Econ., 159, 1, 168-177 (2015) |
| [26] | Kim, K. H.; Bae, J. W., A Look-Ahead Dispatching Method for Automated Guided Vehicles in Automated Port Container Terminals, Transp. Sci., 38, 2, 224-234 (2004) |
| [27] | Kim, K. H.; Kim, K. Y., An optimal routing algorithm for a transfer crane in port container terminals, Transp. Sci., 33, 1, 17-33 (1999) · Zbl 1002.90508 |
| [28] | Kim, K. H.; Park, Y.-M.; Jin, M.-J., An optimal layout of container yards, OR Spectr., 30, 4, 675-695 (2008) · Zbl 1193.90145 |
| [29] | Kizilay, D.; Eliiyi, D. T., A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals, Flex. Serv. Manuf. J., 33, 1, 1-42 (2021) |
| [30] | Kizilay, D.; Hentenryck, P. V.; Eliiyi, D. T., Constraint programming models for integrated container terminal operations, Eur. J. Oper. Res., 286, 3, 945-962 (2020) · Zbl 1443.90183 |
| [31] | Kress, D.; Meiswinkel, S.; Pesch, E., Straddle carrier routing at seaport container terminals in the presence of short term quay crane buffer areas, Eur. J. Oper. Res., 279, 3, 732-750 (2019) · Zbl 1430.90098 |
| [32] | Lau, H. Y.K.; Zhao, Y., Integrated scheduling of handling equipment at automated container terminals, Int. J. Prod. Econ., 112, 2, 665-682 (2008) · Zbl 1152.90452 |
| [33] | Lee, D.-H.; Cao, Z.; Chen, J. H.; Cao, J. X., Load Scheduling of Multiple Yard Crane Systems in Container Terminal with Buffer Areas, Transp. Res. Rec., 2097, 1, 70-77 (2009) |
| [34] | Lee, B. K.; Kim, K. H., Optimizing the yard layout in container terminals, OR Spectr., 35, 2, 363-398 (2013) · Zbl 1263.90045 |
| [35] | Li, X.; Peng, Y.; Huang, J.; Wang, W.; Song, X., Simulation study on terminal layout in automated container terminals from efficiency, economic and environment perspectives, Ocean Coast. Manag., 213 (2021) |
| [36] | Lu, H.; Wang, S., A study on multi-ASC scheduling method of automated container terminals based on graph theory, Comput. Ind. Eng., 129, 1, 404-416 (2019) |
| [37] | Luo, J.; Wu, Y., Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals, Transp. Res. E Logist. Transp. Rev., 79, 1, 49-64 (2015) |
| [38] | Nossack, J.; Briskorn, D.; Pesch, E., Container dispatching and conflict-free yard crane routing in an automated container terminal, Transp. Sci., 52, 5, 1059-1076 (2018) |
| [39] | Qin, T.; Du, Y.; Chen, J. H.; Sha, M., Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel, Eur. J. Oper. Res., 285, 3, 884-901 (2020) · Zbl 1443.90191 |
| [40] | Shair, M. F.; Ullah, K. R.; Tariq, M., Technical efficiency comparison of container ports in Asian and Middle East region using DEA, Asian J. Shipp. Logist., 37, 1, 12-19 (2021) |
| [41] | Skinner, B.; Yuan, S.; Huang, S.; Liu, D.; Cai, B.; Dissanayake, G.; Lau, H.; Bott, A.; Pagac, D., Optimisation for job scheduling at automated container terminals using genetic algorithm, Comput. Ind. Eng., 64, 1, 511-523 (2013) |
| [42] | Steenken, D.; Voß, S.; Stahlbock, R., Container terminal operation and operations research – a classification and literature review, OR Spectr., 26, 1, 3-49 (2004) · Zbl 1160.90322 |
| [43] | Vis, I. F.A.; Carlo, H. J., Sequencing Two Cooperating Automated Stacking Cranes in a Container Terminal, Transp. Sci., 44, 2, 169-182 (2010) |
| [44] | Vis, I. F.A.; Harika, I., Comparison of vehicle types at an automated container terminal, OR Spectr., 26, 1, 117-143 (2004) · Zbl 1161.90315 |
| [45] | Vis, I. F.A.; Roodbergen, K. J., Scheduling of Container Storage and Retrieval, Oper. Res., 57, 2, 456-467 (2009) · Zbl 1181.90129 |
| [46] | Wang, K.; Zhen, L.; Wang, S.; Laporte, G., Column generation for the integrated berth allocation, quay crane assignment, and yard assignment problem, Transp. Sci., 52, 4, 812-834 (2018) |
| [47] | Wu, W.; Xing, Z.; Yue, H.; Su, H.; Pang, S., Petri-net-based deadlock detection and recovery for control of interacting equipment in automated container terminals, IET Intell. Transport Syst., 16, 6, 739-753 (2022) |
| [48] | Yan, B.; Jin, J. G.; Zhu, X.; Lee, D.-H.; Wang, L.; Wang, H., Integrated planning of train schedule template and container transshipment operation in seaport railway terminals, Transp. Res. E Logist. Transp. Rev., 142 (2020) |
| [49] | Yin, Y.-Q.; Zhong, M.; Wen, X.; Ge, Y.-E., Scheduling quay cranes and shuttle vehicles simultaneously with limited apron buffer capacity, Comput. Oper. Res.., 151 (2022) · Zbl 1542.90127 |
| [50] | Yue, L.; Fan, H.; Ma, M., Optimizing configuration and scheduling of double 40 ft dual-trolley quay cranes and AGVs for improving container terminal services, J. Clean. Prod., 292 (2021) |
| [51] | Zhang, Q.; Hu, W.; Duan, J.; Qin, J., Cooperative scheduling of AGV and ASC in automation container terminal relay operation mode, Math. Probl. Eng., 2021 (2021) |
| [52] | Zhang, L.; Zhou, Q.; Ding, H., Simulation and modeling algorithm for terminal container handling intelligent management based on internet of things and big data technology, Sci. Program., 2021 (2021) |
| [53] | Zhen, L.; Yu, S.; Wang, S.; Sun, Z., Scheduling quay cranes and yard trucks for unloading operations in container ports, Ann. Operat. Res., 273, 1-2, 455-478 (2016) · Zbl 1410.90101 |
| [54] | Zhong, M.; Yang, Y.; Dessouky, Y.; Postolache, O., Multi-AGV scheduling for conflict-free path planning in automated container terminals, Comput. Ind. Eng., 142 (2020) |
| [55] | Zhou, C.; Lee, B. K.; Li, H., Integrated optimization on yard crane scheduling and vehicle positioning at container yards, Transp. Res. E Logist. Transp. Rev., 138 (2020) |
| [56] | Zhuang, Z.; Zhang, Z.; Teng, H.; Qin, W.; Fang, H., Optimization for integrated scheduling of intelligent handling equipment with bidirectional flows and limited buffers at automated container terminals, Comput. Oper. Res., 145 (2022) · Zbl 1520.90139 |
| [57] | Zweers, B. G.; Bhulai, S.; van der Mei, R. D., Pre-processing a container yard under limited available time, Comput. Oper. Res., 123 (2020) · Zbl 1458.90161 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
