Data-driven distributionally robust optimization for AGV scheduling problem in automated container terminals

LI Mingze, ZENG Qingcheng, LI Xingchun

Systems Engineering - Theory & Practice ›› 2025, Vol. 45 ›› Issue (4) : 1375-1388.

PDF(452 KB)
中国科学院数学与系统科学研究院期刊网
PDF(452 KB)
Systems Engineering - Theory & Practice ›› 2025, Vol. 45 ›› Issue (4) : 1375-1388. DOI: 10.12011/SETP2023-0810

Data-driven distributionally robust optimization for AGV scheduling problem in automated container terminals

  • LI Mingze, ZENG Qingcheng, LI Xingchun
Author information +
History +

Abstract

Automated guided vehicles (AGVs) are a key factor in determining the operational efficiency of automated container terminals. AGVs often face travel time uncertainties due to congestion, conflicts, weather, and other factors, resulting in quay and yard crane delays that reduce operational efficiency. In this paper, we introduce a distributionally robust method based on Wasserstein distance using historical travel data. We construct a data-driven model to manage the risk of waiting at quay cranes and yard cranes and to determine the task allocation scheme for AGVs with minimal operating costs. To solve the model, we first use conditional value-at-risk to approximate the distributionally robust chance constraints. Its closed-form solution is obtained by duality theory and analytic transformation, which are then transformed into a practical form. Secondly, exact branch-and-cut algorithms, along with heuristic algorithms and corresponding acceleration strategies, are designed for problems of varying sizes in automated container terminals. Experimental results demonstrate that the distributionally robust optimization method effectively captures the uncertainties in AGV travel times. Compared to the sample average approximation, the model and solution proposed in this paper can reduce the risk of waiting at quay cranes and yard cranes by 60%, significantly enhancing the robustness of the allocation scheme.

Key words

automated container terminals / AGV scheduling / uncertainty travel time / distributionally robust optimization / Wasserstein distance

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
LI Mingze, ZENG Qingcheng, LI Xingchun. Data-driven distributionally robust optimization for AGV scheduling problem in automated container terminals. Systems Engineering - Theory & Practice, 2025, 45(4): 1375-1388 https://doi.org/10.12011/SETP2023-0810

References

[1] Yang Z M, Li C H, Zhao Q C. Dynamic time estimation based AGV dispatching algorithm in automated container terminal[C]// 2018 37th Chinese Control Conference (CCC). New York: IEEE, 2018: 7868-7873.
[2] 张亚琦, 杨斌, 胡志华, 等. 自动化码头AGV充电与作业的集成调度研究 [J]. 计算机工程与应用, 2017, 53(18): 257-262.
Zhang Y Q, Yang B, Hu Z H, et al. Research of AGV charging and job integrated scheduling at automated container terminal[J]. Computer Engineering and Applications, 2017, 53(18): 257-262.
[3] 王志刚, 胡伟新. 考虑AGV路径冲突的自动化集装箱码头装卸设备的协同调度 [J]. 工业工程与管理, 2023, 28(6): 80-92.
Wang Z G, Hu W X. Cooperative scheduling of loading and unloading equipment in automated container terminal considering AGV path conflict[J]. Industrial Engineering and Management, 2023, 28(6): 80-92.
[4] 王里, 王超, 安利峰, 等. 港口ART自动驾驶系统设计和应用 [J]. 港口科技, 2022(8): 5-10.
Wang L, Wang C, An L F, et al. Design and application of port ART autonomous driving system[J]. Science & Technology of Ports, 2022(8): 5-10.
[5] 冷典典, 杜鹏, 陈建廷, 等. 面向自动化集装箱码头的AGV行驶时间估计 [J]. 计算机科学, 2022, 49(9): 208-214.
Leng D D, Du P, Chen J T, et al. Automated container terminal oriented travel time estimation of AGV[J]. Computer Science, 2022, 49(9): 208-214.
[6] Angeloudis P, Bell M G H. An uncertainty-aware AGV assignment algorithm for automated container terminals[J]. Transportation Research Part E: Logistics and Transportation Review, 2010, 46(3): 354-366.
[7] 马越汇, 胡志华. 不确定环境下自动化集装箱码头AGV调度与配置问题 [J]. 广西大学学报(自然科学版), 2016, 41(2): 589-597.
Ma Y H, Hu Z H. The dispatching and scheduling problems of AGVs at automated container terminals under uncertainty conditions[J]. Journal of Guangxi University (Nat Sci Ed), 2016, 41(2): 589-597.
[8] 徐卉. 考虑不确定因素的自动化集装箱码头岸桥与AGV联合调度优化 [D]. 大连: 大连海事大学, 2023.
Xu H. Optimization of combined dispatching of quay cranes and AGVs for automated container terminal considering uncertainties[D]. Dalian: Dalian Maritime University, 2023.
[9] Jian W T, Zhu J S, Zeng Q C. An optimization model of integrated AGVs scheduling and container storage problems for automated container terminal considering uncertainty[J]. Symmetry, 2021, 13(10). doi: 10.3390/sym13101904.
[10] 朱禹仲. 考虑拥堵的自动化码头ALV调度与堆存位置分配优化模型 [D]. 大连: 大连海事大学, 2019.
Zhu Y Z. Optimization model of ALV task dispatching and container location considering congestion at automated terminal[D]. Dalian: Dalian Maritime University, 2019.
[11] 冯春, 陈木泉, 蒋雪. 随机充电需求下城市电动汽车充电站选址优化 [J]. 计算机仿真, 2022, 39(11): 193-198.
Feng C, Chen M Q, Jiang X. Location optimization of urban electric vehicle charging station under random charging demand[J]. Computer Simulation, 2022, 39(11): 193-198.
[12] Sun B, Zhai G, Li S, et al. Multi-resource collaborative scheduling problem of automated terminal considering the AGV charging effect under COVID-19[J]. Ocean & Coastal Management, 2023, 232: 106422.
[13] 李林蔓, 李雨青, 王孟雅, 等. 基于启发式规则的自动化码头换电式AGV调度优化方法 [J]. 运筹与管理, 2023, 32(10): 9-15.
Li L M, Li Y Q, Wang M Y, et al. Optimization method for power-changing AGV scheduling of automatic terminal based on heuristic rules[J]. Operations Research and Management Science, 2023, 32(10): 9-15.
[14] Zhang H, Qi L, Luan W, et al. Double-cycling AGV scheduling considering uncertain crane operational time at container terminals[J]. Applied Sciences, 2022, 12(10). doi: 10.3390/app/12104820.
[15] Zhang H, Qi L, Ma H. A method for AGV double-cycling scheduling at automated container terminals[M]// Intelligent Information Processing XI, 2022: 495-507.
[16] 霍凯歌, 张亚琦, 胡志华. 自动化集装箱码头多载AGV调度问题研究 [J]. 大连理工大学学报, 2016, 56(3): 244-251.
Huo K G, Zhang Y Q, Hu Z H. Research on multi-AGV scheduling problem in automated container terminals[J]. Journal of Dalian University of Technology, 2016, 56(3): 244-251.
[17] 霍凯歌, 胡志华. 基于遗传算法的自动化集装箱码头多载AGV调度 [J]. 上海海事大学学报, 2016, 37(3): 7-12.
Huo K G, Hu Z H. Multi-AGV scheduling in automated container terminals based on genetic algorithm[J]. Journal of Shanghai Maritime University, 2016, 37(3): 7-12.
[18] Wang Z H, Zeng Q C. A branch-and-bound approach for AGV dispatching and routing problems in automated container terminals[J]. Computers & Industrial Engineering, 2022, 166: 107968.
[19] Yue L, Fan H. Dynamic scheduling and path planning of automated guided vehicles in automatic container terminal[J]. IEEE/CAA Journal of Automatica Sinica, 2022, 9(11): 2005-2019.
[20] Gong L, Huang Z, Xiang X, et al. Real-time AGV scheduling optimisation method with deep reinforcement learning for energy-efficiency in the container terminal yard[J]. International Journal of Production Research, 2024, 62: 7722-7742.
[21] Chen C, Hu Z H, Wang L. Scheduling of AGVs in automated container terminal based on the deep deterministic policy gradient (DDPG) using the convolutional neural network (CNN)[J]. Journal of Marine Science and Engineering, 2021, 9(12): 1439.
[22] 贾石岩, 王泽浩, 张旭, 等. 基于偏好函数与深度信念网络的自动化码头AGV实时调度算法 [J]. 中国航海, 2020, 43(1): 121-127.
Jia S Y, Wang Z H, Zhang X, et al. Real-time scheduling algorithm for AGV in automated container terminals based on preference function and deep belief net[J]. Navigation of China, 2020, 43(1): 121-127.
[23] Yang M, Bian Y, Ma L, et al. Research on traffic control algorithm based on multi-AGV path planning[C]// 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2021: 697-702.
[24] Cao Y, Yang A, Liu Y, et al. AGV dispatching and bidirectional conflict-free routing problem in automated container terminal[J]. Computers & Industrial Engineering, 2023, 184: 109611.
[25] 张素云, 杨勇生, 梁承姬, 等. 自动化码头多AGV路径冲突的优化控制研究 [J]. 交通运输系统工程与信息, 2017, 17(2): 83-89.
Zhang S Y, Yang Y S, Liang C J, et al. Optimal control of multiple AGV path conflict in automated terminals[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(2): 83-89.
[26] Li Q, Pogromsky A, Adriaansen T, et al. A control of collision and deadlock avoidance for automated guided vehicles with a fault-tolerance capability[J]. International Journal of Advanced Robotic Systems, 2016, 13(2): 64.
[27] Zhou P, Lin L, Kim K H. Anisotropic Q-learning and waiting estimation based real-time routing for automated guided vehicles at container terminals[J]. Journal of Heuristics, 2023, 29(2): 207-228.
[28] Hu H, Yang X, Xiao S, et al. Anti-conflict AGV path planning in automated container terminals based on multi-agent reinforcement learning[J]. International Journal of Production Research, 2023, 61(1): 65-80.
[29] 樊伟, 范英, 谭忠富, 等. 基于多层利益共享的虚拟电厂参与电碳市场分布鲁棒优化模型 [J]. 系统工程理论与实践, 2024, 44(2): 661-683.
Fan W, Fan Y, Tan Z F, et al. Distributionally robust optimization model for virtual power plant participation in electricity carbon market based on multi-layer benefit sharing[J]. Systems Engineering — Theory & Practice, 2024, 44(2): 661-683.
[30] 徐婉迪, 罗俊, 范薇薇. 不确定环境下并网型光储微电网的容量规划 [J]. 系统工程理论与实践, 2022, 42(4): 981-1000.
Xu W D, Luo J, Fan W W. Capacity planning of grid-connected PV-and-storage microgrid under uncertainty[J]. Systems Engineering — Theory & Practice, 2022, 42(4): 981-1000.
[31] 王浩, 甘蜜, 魏力飞, 等. 面向山区铁路工程物流基地选址的分布鲁棒优化模型 [J]. 铁道学报, 2024, 46(1): 103-112.
Wang H, Gan M, Wei L F, et al. Distributionally robust optimization model for logistics facility location in mountainous railway projects[J]. Journal of the China Railway Society, 2024, 46(1): 103-112.
[32] 代文强, 陈琳, 章潇月. 道路容量不确定情形下可靠应急疏散路径规划问题 [J]. 系统工程理论与实践, 2022, 42(9): 2486-2495.
Dai W Q, Chen L, Zhang X Y. Reliable emergency evacuation route planning under road capacity uncertainty[J]. Systems Engineering — Theory & Practice, 2022, 42(9): 2486-2495.
[33] 黎俊, 王曙明. 基于截断需求的分布鲁棒报童问题 [J]. 系统工程理论与实践, 2022, 42(5): 1260-1276.
Li J, Wang S M. Distributionally robust newsvendor problem with censored demand[J]. Systems Engineering — Theory & Practice, 2022, 42(5): 1260-1276.
[34] 金小丹, 周泓. 需求分布未知下的供应链融资及鲁棒订购策略 [J]. 系统工程理论与实践, 2021, 41(5): 1263-1271.
Jin X D, Zhou H. Joint supply chain finance and robost order decision with unknown distribution of demand[J]. Systems Engineering — Theory & Practice, 2021, 41(5): 1263-1271.
[35] 竺如洁, 韦化, 白晓清. 多源动态最优潮流的分布鲁棒优化方法 [J]. 中国电机工程学报, 2020, 40(11): 3489-3498.
Zhu R J, Wei H, Bai X Q. Distributionally robust optimization of multi-energy dynamic optimal power flow[J]. Proceedings of the CSEE, 2020, 40(11): 3489-3498.
[36] Wang Z H, Zeng Q V, Li X C, et al. A branch-and-price heuristic algorithm for the ART and external truck scheduling problem in an automated container terminal with a parallel layout[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 184: 103464.
[37] Esfahani P M, Kuhn D. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations[J]. Mathematical Programming, 2018, 171(1-2): 115-166.
[38] Laporte G, Louveaux F, Mercure H. The vehicle routing problem with stochastic travel times[J]. Transportation Science, 1992, 26(3): 161-170.
[39] Ben-Tal A, Teboulle M, Ben-Tal A, et al. Expected utility, penalty functions, and duality in stochastic nonlinear programming[J]. Management Science, 1986, 32(11): 1445-1466.
[40] Nemirovski A, Shapiro A. Convex approximations of chance constrained programs[J]. SIAM Journal on Optimization, 2007, 17(4): 969-996.
[41] Xie W J. On distributionally robust chance constrained programs with Wasserstein distance[J]. Mathematical Programming, 2021, 186(1): 115-155.

Funding

National Key R&D Program of China (2023YFE0113200); National Natural Science Foundation of China (72203029)
PDF(452 KB)

345

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉