Joint Configuration and Scheduling Optimization of Dual-trolley Quay Crane and AGV for Container Terminal with Considering Energy Saving
-
摘要: 合理调度集装箱码头的装卸设备以减少生产过程中的能耗, 对实现其低碳绿色化发展具有重要意义. 针对集装箱码头向自动化发展过程中的双小车岸桥与AGV (Automated guided vehicle)联合配置及调度问题, 考虑AGV续航时间、双小车岸桥中转平台容量和堆场缓冲支架容量约束, 以岸桥的能耗最小为第一阶段模型的优化目标, 以AGV运输过程的能耗最小为第二阶段目标建立两阶段优化模型; 设计枚举法求解第一阶段模型, 改进遗传算法求解第二阶段优化模型. 以洋山四期自动化集装箱码头为例进行实验分析, 针对不同船舶在港总装卸时间和AGV配置原则进行实验, 验证了模型和算法的有效性, 结果表明以最小化能耗为目标的双小车岸桥与AGV联合调度可在岸桥主小车不延误的前提下, 显著减少AGV的配置数量.
-
关键词:
- 双小车岸桥配置与调度 /
- AGV配置与调度 /
- AGV续航时间 /
- 改进遗传算法
Abstract: Reasonable dispatching of equipment at the terminal can reduce energy consumption during loading and unloading, which have great significance for energy saving and emission reduction of China's terminals. The joint configuration and scheduling of dual-trolley quay crane and automated guided vehicle (AGV) for container terminals is studied, with considering the constraints of the AGV's endurance time, dual-trolley quay crane transfer platform capacity and yard buffer support capacity. Two-stage optimization model is established, which takes the minimum energy consumption of dual-trolley quay crane as the optimization target of the first stage, and the minimum energy consumption of AGV during the transportation as the second stage. Designing the enumeration method to solve the first-stage model. Improving the genetic algorithm to solve the second-stage optimization model. Taking the Yangshan Phase IV automated container terminal as an example for experimental analysis, the experiments were carried out on the different laytimes and AGV configuration principles. The validity of the model and algorithm was verified. The results showed that the joint dispatching of dual-trolley quay crane and AGV with the goal of minimizing energy consumption can significantly reduce the number of AGV configurations without delay of the quay crane. -
表 1 设备参数取值
Table 1 Equipment parameter value
参数 取值 ${\tau _1}\;/\min$ 1 ${\tau _2}\;/\min$ 2 ${\tau _3}\;/\min$ 1 ${\tau _4}\;/\min$ 3 ${\tau _5}\;/\min$ 5 ${v_1}\;/({\rm m} \cdot {\min ^{ - 1} })$ 210 ${v_0}\;/({\rm m} \cdot {\min ^{ - 1} })$ 350 ${C_1}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{台} } } \right)}^{ - 1} } } \right)$ 91.24 ${C_2}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{台} } } \right)}^{ - 1} } } \right)$ 70.18 ${C_3}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{台} } } \right)}^{ - 1} } } \right)$ 49.6 ${C_4}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{台} } } \right)}^{ - 1} } } \right)$ 49.6 ${C_5}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{辆} } } \right)}^{ - 1} } } \right)$ 21 ${C_6}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{辆} } } \right)}^{ - 1} } } \right)$ 14 ${C_7}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{辆} } } \right)}^{ - 1} } } \right)$ 9 表 2 岸桥调度方案比较
Table 2 Comparison of dual-trolley quay crane scheduling schemes
$k$ ${T_{Ik}}$ ${F_1}$ 调度方案 开始-完工时刻 2 4 709 11 507 QC1 B1-B6卸船作业 0 ~ 917 min B1-B18装船作业 924 ~ 3 789 min QC2 B7-B20卸船作业 0 ~ 3 787 min B19-B20装船作业 3 789 ~ 3 889 min 3 2 605 11 504 QC1 B1-B3卸船作业 0 ~ 640 min B1-B13装船作业 643 ~ 2 605 min QC2 B3-B10卸船作业 0 ~ 1 740 min B14-B18装船作业 1 743 ~ 2 546 min QC3 B11-B20卸船作业 0 ~ 2 323 min B19-B20装船作业 2 324 ~ 2 429 min 4 2 636 11 484 QC1 B1-B3卸船作业 0 ~ 640 min B1-B9装船作业 644 ~ 1 970 min QC2 B4-B5卸船作业 0 ~ 93 min B10-B11装船作业 98 ~ 395 min QC3 B6-B10卸船作业 0 ~ 1 646 min B12-B16装船作业 1 648 ~ 2 636 min QC4 B11-B20卸船作业 0 ~ 2 325 min B17-B20装船作业 2 331 ~ 2 468 min 表 3 AGV调度结果
Table 3 The scheduling results of AGV
AGV 集装箱作业序列 1 1→7→11→16→22→25→36→47→54→59→63→70→78→83→86→89→96→107→113→131→···→
3530→3537→3545→3548→3555→3562→3567→3572→3575→3580→3585→35882 2→5→8→13→17→18→21→27→31→37→48→58→61→67→74→80→82→90→94→98→115→···→
3336→3344→3348→3354→3355→3361→3367→3377→3382→3393→33983 3→4→9→14→20→23→29→32→40→44→46→49→56→62→72→85→87→92→102→114→···→
3747→3750→3751→3753→3754→3755→3757→3758→3760→3761→3762→3766→37674 6→10→12→24→34→38→42→51→60→64→69→73→76→84→88→93→99→100→105→110→···→
3653→3655→3658→3661→3664→3665→3668→3674→3677→3680→3687→3691→36975 15→19→26→33→43→75→95→109→112→118→122→125→130→141→146→150→154→162→···→
3538→3543→3551→3565→3569→3574→3578→3584→3592→3598→3605→3610→36146 28→35→39→45→50→53→55→65→71→79→91→97→101→104→108→120→123→133→136→···→
3742→3744→3746→3748→3749→3752→3756→3759→3763→3764→3765→3768→37697 30→41→52→57→66→68→77→81→103→106→111→117→121→138→142→167→170→185→···→
3702→3703→3707→3709→3710→3712→3716→3718→3721→3727→3730→3733→3738表 4 平均计算结果与下界的比较
Table 4 Comparison of average calculation results with lower boundary
实验 $N$ ${T_{{q_{\max }}}}$ ${f_1}$ ${A_1}$ ${f_2}$ ${A_2}$ ${f_2}^*$ $\underline {{f_2}} $ $GA{P_1}$ $GA{P_2}$ 1 240 187 763.9 6 197.73 6 333.55 190.13 3.85 % 43.00 % 2 408 290 1 287.7 6 339.07 6 612.01 335.98 0.91 % 45.10 % 3 829 575 2 558.7 6 706.81 6 1 160.60 671.08 5.05 % 42.18 % 4 1 129 790 3 467.6 6 1 005.11 6 1 749.47 861.65 14.27 % 50.75 % 5 1 505 1 102 4 613.5 6 1 379.94 6 2 114.89 1 190.34 13.74 % 43.72 % 6 1 976 1 391 6 045.9 6 2 323.14 7 2 996.72 1 927.88 17.01 % 35.67 % 7 2 419 1 642 7 394.4 7 2 492.07 8 3 634.97 2 191.91 12.04 % 39.70 % 8 2 649 1 792 8 091.6 8 2 789.62 8 3 941.74 2 571.83 7.81 % 34.75 % 表 5 不同船舶在港总装卸时间和不同AGV配置原则下调度结果比较
Table 5 The results of different allowable laytime and different AGV configuration principles
实验 ${t_f}/{\rm h}$ ${T_{ {q_{\max } } } }/{\rm h}$ K/台 ${f_1}/{\rm kW} \cdot {\rm h}$ $\min ({f_1} + {f_2})/{\rm kW} \cdot {\rm h}$ AGV配置原则一 AGV配置原则二 AGV配置原则三 V/辆 ${f_2}/{\rm kW} \cdot {\rm h}$ V/辆 ${f_2}/{\rm kW} \cdot {\rm h}$ V/辆 ${f_2}/{\rm kW} \cdot {\rm h}$ 9 48 46.46 3 11 499.1 15 374.6 7 3 875.5 6 4 417.4 9 4 198.1 10 44 43.28 3 11 505.3 15 362.3 7 3 857.0 6 4 030.4 9 4 168.6 11 40 37.9 4 11 482.7 15 308.1 10 3 825.4 9 3 847.2 12 3 977.6 12 36 35.23 4 11 483.8 15 136.8 9 3 653.0 7 3 659.6 12 3 806.2 13 32 32 4 11 487.3 15 097.5 9 3 610.2 9 3 610.2 12 3 879.0 表 6 考虑随机因素影响的实验设计
Table 6 Experimental design considering the influence of random factors
实验 实验内容 14 完全确定性系统. 在实验10中岸桥调度方案的基础上, ${\tau _2}$、${\tau _5}$、${v_0}$和${v_1}$均设为定值 15 在实验14的基础上, 每个集装箱的岸桥主小车作业时间设定为服从均值为${\tau _2}$的泊松分布 16 在实验15的基础上, AGV往返充电站时间设定为服从均值为${\tau _5}$负指数分布的类型 17 在实验16的基础上, AGV的空载速度、重载速度分别设定为服从均值为${v_0}$和${v_1}$的正态分布 表 7 考虑随机因素影响的实验结果
Table 7 Experimental results considering the influence of random factors
$A$ 实验14 实验15 实验16 实验17 $Del$ $\rho $ $f'_2$ $Del$ $\rho $ $f'_2$ $Del$ $\rho $ $f'_2$ $Del$ $\rho $ $f'_2$ 7 0 55.56 % 3 857.00 2.30 33.80 % 6 393.53 49.98 34.87 % 6 196.18 128.08 35.55 % 6 076.48 8 0 51.42 % 4 171.03 2.52 31.97 % 6 766.14 7.81 32.51 % 6 629.52 1.03 34.00 % 6 355.70 9 0 51.52 % 4 168.56 0 30.32 % 7 125.26 3.09 33.71 % 6 407.80 1.87 31.34 % 6 897.39 10 0 50.79 % 4 049.60 0 31.63 % 6 817.67 0 32.64 % 6 604.88 4.25 31.17 % 6 919.12 11 0 50.42 % 4 122.80 0 30.53 % 7 069.71 0 30.10 % 7 164.51 1.26 29.55 % 7 325.53 -
[1] 丁进良, 杨翠娥, 陈远东, 柴天佑. 复 杂工业过程智能优化决策系统的现状与展望. 自 动化学报, 2018, 44(11): 1931-1943Ding Jin-Liang, Yang Cui-E, Chen Yuan-Dong, Chai Tian-You. Research progress and prospects of intelligent optimization decision making in complex industrial process. Acta Automatica Sinica, 2018, 44(11): 1931-1943 [2] Sim J. A carbon emission evaluation model for a container terminal. Journal of Cleaner Production, 2018, 186(10): 526-533 [3] 郑松, 吴晓林, 王飞跃, 林东东, 郑蓉, 柯伟林, 池新栋, 陈德旺. 平 行系统方法在自动化集装箱码头中的应用研究. 自 动化学报, 2019, 45(3): 490-504Zheng Song, Wu Xiao-Lin, Wang Fei-Yue, Lin Dong-Dong, Zheng Rong, Ke Wei-Lin, Chi Xin-Dong, Chen De-Wang. Applying the parallel systems approach to automatic container terminal. Acta Automatica Sinica, 2019, 45(3): 490-504 [4] He J, Huang Y, Yan W. Yard crane scheduling in a container terminal for the trade-off between efficiency and energy consumption. Advanced Engineering Informatics, 2015, 29(1): 59-75 doi: 10.1016/j.aei.2014.09.003 [5] Chang D, He J, Bian Z. An investigation into berth and quay crane scheduling for container terminals based on knowledge. In: Proceedings of International Conference on Future Information Technology and Management Engineering. Changzhou, China: IEEE, 2010. 63−66 [6] He, J. Berth allocation and quay crane assignment in a container terminal for the trade-off between time-saving and energy-saving. Advanced Engineering Informatics, 2016, 30(3): 390-405 doi: 10.1016/j.aei.2016.04.006 [7] Chang, D, Fang T, Fan Y. Dynamic rolling strategy for multi-vessel quay crane scheduling. Advanced Engineering Informatics, 2017, 34(10): 60-69 [8] Zhang, Z, Zhang Z, Liu M, Lee C Y, Wang J. The quay crane scheduling problem with stability constraints. IEEE Transactions on Automation Science and Engineering, 2018, 15(3): 1399-1412 doi: 10.1109/TASE.2018.2795254 [9] Liu D, Ge Y E. Modeling assignment of quay cranes using queueing theory for minimizing CO2 emission at a container terminal. Transportation Research Part D: Transport and Environment, 2018, 61(6): 140-151 [10] Liang C, Fan L, Xu D, Ding Y, Gen M. Research on coupling scheduling of quay crane dispatch and configuration in the container terminal. Computers & Industrial Engineering, 2018, 125(11): 649-657 [11] Msakni M K, Diabat A, Rabadi G, Salem M A, Kotachi M. Exact methods for the quay crane scheduling problem when tasks are modeled at the single container level. Computers & Operations Research, 2018, 99(11): 218-233 [12] Kim K H, Park Y M. A crane scheduling method for port container terminals. European Journal of Operational Research, 2004, 156(3): 752-768 doi: 10.1016/S0377-2217(03)00133-4 [13] Nguyen S, Zhang M, Johnston M, Tan K C. Hybrid evolutionary computation methods for quay crane scheduling problems. Computers & Operations Research, 2013, 40(8): 2083-2093 [14] Kim K H, Bae J W. A look-ahead dispatching method for automated guided vehicles in automated port container terminals. Transportation Science, 2004, 38(2): 224-234 doi: 10.1287/trsc.1030.0082 [15] Choe R, Kim J, Ryu K R. Online preference learning for adaptive dispatching of AGVs in an automated container terminal. Applied Soft Computing, 2016, 38(1): 647-660 [16] Kim J, Choe R, Ryu K R. Multi-objective optimization of dispatching strategies for situation-adaptive AGV operation in an automated container terminal. In: Proceedings of Research in Adaptive and Convergent Systems. New York, USA: ACM, 2013. 1−6 [17] Xin J, Negenborn R R, Lodewijks G. Energy-aware control for automated container terminals using integrated flow shop scheduling and optimal control. Transportation Research Part C: Emerging Technologies, 2014, 44(7): 214-230 [18] Peng Y, Wang W, Liu K, Li X, Tian Q. The Impact of the allocation of facilities on reducing carbon emissions from a green container terminal perspective. Sustainability, 2018, 10(6): 1813 doi: 10.3390/su10061813 [19] Yang Y, Zhu X, Haghani A. Multiple equipment integrated scheduling and storage space allocation in rail–water intermodal container terminals considering energy efficiency. Transportation Research Record, 2019, 2673(3): 199-209 doi: 10.1177/0361198118825474 [20] Dkhil H, Yassine A, Chabchoub H. Optimization of container handling systems in automated maritime terminal. Advanced Methods for Computational Collective Intelligence. Berlin Heidelberg: Springer, 2013. 301−312 [21] Yang Y, Zhong M, Dessouky Y, Postolache O. An integrated scheduling method for AGV routing in automated container terminals. Computers & Industrial Engineering, 2018, 126(12): 482-493 [22] Singgih I K, Hong S, Kim K H. Flow path design for automated transport systems in container terminals considering traffic congestion. Industrial Engineering & Management Systems, 2016, 15(1): 19-31 [23] Legato P, Mazza R M, Trunfio R. Simulation-based optimization for discharge/loading operations at a maritime container terminal. OR Spectrum, 2010, 32(3): 543-567 doi: 10.1007/s00291-010-0207-2 [24] Xin, J, Negenborn R R, Corman F, Lodewijks, G. Control of interacting machines in automated container terminals using a sequential planning approach for collision avoidance. Transportation Research Part C: Emerging Technologies, 2015, 60(11): 377-396 [25] 原豪男, 郭戈. 交 通信息物理系统中的车辆协同运行优化调度. 自 动化学报, 2019, 45(01): 143-152Yuan Hao-Nan, Guo Ge. Vehicle cooperative optimization scheduling in transportation cyber physical systems. Acta Automatica Sinica, 2019, 45(01): 143-152 [26] Lee D H, Wang H Q, Miao L. Quay crane scheduling with non-interference constraints in port container terminals. Transportation Research Part E: Logistics and Transportation Review, 2008, 44(1): 124-135 doi: 10.1016/j.tre.2006.08.001 [27] 罗勋杰. 全 自动化集装箱码头水平运输方式对比. 水 运工程, 2016, 42(09): 76-82Luo Xun-Jie. Comparison of horizon transportation system of full automatic container terminal. Port &Waterway Engineering, 2016, 42(09): 76-82 [28] 陈超, 张哲, 曾庆成. 集 装箱码头混合交叉作业集成调度模型. 交 通运输工程学报, 2012, 12(03): 92-100Chen Chao, Zhang Zhe, Zeng Qing-Cheng. Integrated scheduling model of mixed cross-operation for container terminal. Journal of Traffic and Transportation Engineering. 2012, 12(03): 92-100 [29] 邢曦文, 毛钧, 张睿, 靳志宏. 基 于混合流水作业组织的集装箱码头装卸作业集成调度优化. 中 国管理科学, 2014, 22(10): 97-105Xin Xi-Wen, Mao Jun, Zhang Rui, Jin Zhi-Hong. Optimization of container loading/unloading integrated scheduling in a container terminal based on hybrid flowshop. Chinese Journal Of Management Science, 2014, 22(10): 97-105 [30] 韩晓龙, 樊加伟. 自 动化港口AGV调度配置仿真分析. 重 庆交通大学学报(自然科学版), 2016, 35(05): 151-154+164Han Xiao-Long, Fan Jia-Wei. Analysis of AGV dispatching and configuration simulation of automated container terminals. Journal Of Chongqing Jiaotong University (Natural Science). 2016, 35(05): 151-154+164