2.793

                    2018影響因子

                    (CJCR)

                    • 中文核心
                    • EI
                    • 中國科技核心
                    • Scopus
                    • CSCD
                    • 英國科學文摘

                    留言板

                    尊敬的讀者、作者、審稿人, 關于本刊的投稿、審稿、編輯和出版的任何問題, 您可以本頁添加留言。我們將盡快給您答復。謝謝您的支持!

                    姓名
                    郵箱
                    手機號碼
                    標題
                    留言內容
                    驗證碼

                    考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化

                    范厚明 郭振峰 岳麗君 馬夢知

                    范厚明, 郭振峰, 岳麗君, 馬夢知. 考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化. 自動化學報, 2020, 45(1): 1?15. doi: 10.16383/j.ass.c190626
                    引用本文: 范厚明, 郭振峰, 岳麗君, 馬夢知. 考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化. 自動化學報, 2020, 45(1): 1?15. doi: 10.16383/j.ass.c190626
                    Fan Hou-Ming, Guo Zhen-Feng, Yue Li-Jun, Ma Meng-Zhi. Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving. Acta Automatica Sinica, 2020, 45(1): 1?15. doi: 10.16383/j.ass.c190626
                    Citation: Fan Hou-Ming, Guo Zhen-Feng, Yue Li-Jun, Ma Meng-Zhi. Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving. Acta Automatica Sinica, 2020, 45(1): 1?15. doi: 10.16383/j.ass.c190626

                    考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化


                    DOI: 10.16383/j.ass.c190626
                    詳細信息
                      作者簡介:

                      大連海事大學交通運輸工程學院教授, 博士. 主要研究方向為交通運輸系統規劃與設計, 戰略管理與系統規劃. 本文通訊作者.Email: fhm468@163.com

                      大連海事大學交通運輸工程學院博士研究生. 主要研究方向為交通運輸規劃與管理;Email: guozhenfeng_dl@126.com

                      大連海事大學交通運輸工程學院碩士研究生. 主要研究方向為物流工程.E-mail: Yuelj11@163.com

                      大連海事大學交通運輸工程學院講師, 博士. 主要研究方向為交通運輸系統規劃與設計, 戰略管理與系統規劃.E-mail: mengzhi1440@126.com

                    • 基金項目:  國家自然科學基金(61473053); 遼寧省重點研發計劃指導計劃(2018401002)資助

                    Joint Configuration and Scheduling Optimization of Dual-trolley Quay Crane and AGV for Container Terminal with Considering Energy Saving

                    More Information
                    • Fund Project:  National Natural Science Foundation of China (61473053), the Key Research Plan Guidance Plan of Liaoning Province (2018401002)
                    • 摘要: 合理調度集裝箱碼頭的裝卸設備以減少生產過程中的能耗, 對實現其低碳綠色化發展具有重要意義. 針對集裝箱碼頭向自動化發展過程中的雙小車岸橋與AGV聯合配置及調度問題, 考慮AGV續航時間、雙小車岸橋中轉平臺容量和堆場緩沖支架容量約束, 以岸橋的能耗最小為第一階段模型的優化目標, 以AGV運輸過程的能耗最小為第二階段目標建立兩階段優化模型; 設計枚舉法求解第一階段模型, 改進遺傳算法求解第二階段優化模型. 以洋山四期自動化集裝箱碼頭為例進行實驗分析, 針對不同船舶在港總裝卸時間和AGV配置原則進行實驗, 驗證了模型和算法的有效性, 結果表明以最小化能耗為目標的雙小車岸橋與AGV聯合調度可在岸橋主小車不延誤的前提下, 顯著減少AGV的配置數量.
                    • 圖  1  雙小車岸橋示意圖

                      Fig.  1  The dual-trolley quay crane

                      圖  2  碼頭布局和AGV運輸流程示意圖

                      Fig.  2  Automated container terminal layout and AGV transportation process

                      圖  3  待裝卸集裝箱分布示意圖

                      Fig.  3  Containers to be loaded and unloaded

                      圖  4  岸橋任務編號示意圖

                      Fig.  4  Task number of quay crane

                      圖  5  染色體示意圖

                      Fig.  5  The chromosome

                      圖  6  目標函數求解流程圖

                      Fig.  6  Solution flowchart

                      圖  7  交叉和變異

                      Fig.  7  Crossover and variation

                      圖  8  待裝卸集裝箱船

                      Fig.  8  The ship of containers to be loaded and unloaded

                      圖  9  岸橋作業路線圖

                      Fig.  9  Path to the dual-trolley quay cranes

                      圖  10  不同AGV配置數量下各實驗的AGV利用率

                      Fig.  10  AGV utilization rate of each experiment under different configurations

                      表  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}/[m \cdot {\min ^{ - 1}}]$210
                      ${v_0}/[m \cdot {\min ^{ - 1}}]$350
                      ${C_1}/\left[ {kw \cdot h \cdot { {\left( {h \cdot{\simfont\text{臺} } } \right)}^{ - 1} } } \right]$91.24
                      ${C_2}/[kw \cdot h \cdot {(h \cdot {\simfont\text{臺} })^{ - 1} }]$70.18
                      ${C_3}/[kw \cdot h \cdot {(h \cdot {\simfont\text{臺} })^{ - 1} }]$49.6
                      ${C_4}/[kw \cdot h \cdot {(h \cdot {\simfont\text{臺} })^{ - 1} }]$49.6
                      ${C_5}/[kw \cdot h \cdot {(h \cdot {\simfont\text{輛} })^{ - 1} }]$21
                      ${C_6}/[kw \cdot h \cdot {(h \cdot {\simfont\text{輛} })^{ - 1} }]$14
                      ${C_7}/[kw \cdot h \cdot {(h \cdot{\simfont\text{輛} })^{ - 1} }]$9
                      下載: 導出CSV

                      表  2  岸橋調度方案比較

                      Table  2  Comparison of dual-trolley quay crane scheduling schemes

                      $k$${T_{Ik}}$${F_1}$調度方案開始-完工時刻
                      24 70911 507QC1B1- B6卸船作業0?917 min
                      B1-B18裝船作業924?3 789 min
                      QC2B7-B20卸船作業0?3 787 min
                      B19-B20裝船作業3 789?3 889 min
                      32 60511 504QC1B1-B3卸船作業0?640 min
                      B1-B13裝船作業643?2 605 min
                      QC2B3-B10卸船作業0?1 740 min
                      B14-B18裝船作業1 743?2 546 min
                      QC3B11-B20卸船作業0?2 323 min
                      B19-B20裝船作業2 324?2 429 min
                      42 63611 484QC1B1-B3卸船作業0?640 min
                      B1-B9裝船作業644?1 970 min
                      QC2B4-B5卸船作業0?93 min
                      B10-B11裝船作業98?395 min
                      QC3B6-B10卸船作業0?1 646 min
                      B12-B16裝船作業1 648?2 636 min
                      QC4B11-B20卸船作業0?2 325 min
                      B17-B20裝船作業2 331?2 468 min
                      下載: 導出CSV

                      表  3  AGV調度結果

                      Table  3  The scheduling results of AGV

                      AGV集裝箱作業序列
                      11→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→3588
                      22→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→3398
                      33→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→3767
                      46→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→3697
                      515→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→3614
                      628→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→3769
                      730→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
                      下載: 導出CSV

                      表  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}$
                      1240187763.96197.736333.55190.133.85 %43.00 %
                      24082901 287.76339.076612.01335.980.91 %45.10 %
                      38295752 558.76706.8161 160.60671.085.05 %42.18 %
                      41 1297903 467.661 005.1161 749.47861.6514.27 %50.75 %
                      51 5051 1024 613.561 379.9462 114.891 190.3413.74 %43.72 %
                      61 9761 3916 045.962 323.1472 996.721 927.8817.01 %35.67 %
                      72 4191 6427 394.472 492.0783 634.972 191.9112.04 %39.70 %
                      82 6491 7928 091.682 789.6283 941.742 571.837.81 %34.75 %
                      下載: 導出CSV

                      表  5  不同船舶在港總裝卸時間和不同AGV配置原則下調度結果比較

                      Table  5  The results of different allowable laytime and different AGV configuration principles

                      實驗${t_f}/h$${T_{{q_{\max }}}}/h$K/臺${f_1}/kw \cdot h$$\min ({f_1} + {f_2})/kw \cdot h $AGV配置原則一AGV配置原則二AGV配置原則三
                      V/輛${f_2}/kw \cdot h$V/輛${f_2}/kw \cdot h$V/輛${f_2}/kw \cdot h$
                      94846.46311 499.115 374.673 875.564 417.494 198.1
                      104443.28311 505.315 362.373 857.064 030.494 168.6
                      114037.9411 482.715 308.1103 825.493 847.2123 977.6
                      123635.23411 483.815 136.893 653.073 659.6123 806.2
                      133232411 487.315 097.593 610.293 610.2123 879.0
                      下載: 導出CSV

                      表  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}$的正態分布
                      下載: 導出CSV

                      表  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$
                      7055.56 %3 857.002.3033.80 %6 393.5349.9834.87 %6 196.18128.0835.55 %6 076.48
                      8051.42 %4 171.032.5231.97 %6 766.147.8132.51 %6 629.521.0334.00 %6 355.70
                      9051.52 %4 168.56030.32 %7 125.263.0933.71 %6 407.801.8731.34 %6 897.39
                      10050.79 %4 049.60031.63 %6 817.67032.64 %6 604.884.2531.17 %6 919.12
                      11050.42 %4 122.80030.53 %7 069.71030.10 %7 164.511.2629.55 %7 325.53
                      下載: 導出CSV
                      360彩票
                    • [1] 丁進良, 楊翠娥, 陳遠東, 柴天佑. 復雜工業過程智能優化決策系統的現狀與展望. 自 動化學報, 2018, 44(11): 1931?1943

                      1 Ding 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] 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?504

                      3 Zheng 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] 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] 6 H e, 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 24 X in, 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(1): 143?152

                      25 Yuan Hao-Nan, Guo Ge. Vehicle cooperative optimization scheduling in transportation cyber physical systems. Acta Automatica Sinica, 2019, 45(1): 143?152
                      [26] 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(9): 76?82

                      27 Luo Xun-Jie. Comparison of horizon transportation system of full automatic container terminal. Port &Waterway Engineering, 2016, 42(9): 76?82
                      [28] 陳超, 張哲, 曾慶成. 集裝箱碼頭混合交叉作業集成調度模型. 交 通運輸工程學報, 2012, 12(03): 92?100

                      28 Chen 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?105

                      29 Xin 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(5): 151?154+164

                      30 Han 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(5): 151?154+164
                    • [1] 項前, 周亞云, 呂志軍. 資源約束項目的改進差分進化參數控制及雙向調度算法[J]. 自動化學報, doi: 10.16383/j.aas.c170728
                      [2] 陸志強, 劉欣儀. 考慮資源轉移時間的資源受限項目調度問題的算法[J]. 自動化學報, doi: 10.16383/j.aas.2017.c160834
                      [3] 王秀英, 馮惠, 任志考, 周艷平. 面向煉鋼—連鑄調度過程的兩階段優化模型與算法[J]. 自動化學報, doi: 10.16383/j.aas.2016.c160005
                      [4] 黃敏, 付亞平, 王洪峰, 朱兵虎, 王興偉. 設備帶有惡化特性的作業車間調度模型與算法[J]. 自動化學報, doi: 10.16383/j.aas.2015.c131067
                      [5] 王利, 高憲文, 王偉, 王琦. 基于模型的子空間聚類與時間段蟻群算法的合同生產批量調度方法[J]. 自動化學報, doi: 10.3724/SP.J.1004.2014.01991
                      [6] 金弟, 劉杰, 楊博, 何東曉, 劉大有. 局部搜索與遺傳算法結合的大規模復雜網絡社區探測[J]. 自動化學報, doi: 10.3724/SP.J.1004.2011.00873
                      [7] 楊建軍, 劉揚, 魏立新, 戰 紅. 多源注水系統泵站優化調度的雙重編碼混合遺傳算法[J]. 自動化學報
                      [8] 羅家祥, 唐立新. 帶釋放時間的并行機調度問題的ILS & SS算法[J]. 自動化學報
                      [9] 楊海軍, 李敏強. 有限群體遺傳算法的動力性[J]. 自動化學報
                      [10] 丁建立, 陳增強, 袁著祉. 遺傳算法與螞蟻算法融合的馬爾可夫收斂性分析[J]. 自動化學報
                      [11] 唐立新, 吳亞萍. 混合流水車間調度的遺傳下降算法[J]. 自動化學報
                      [12] 楊煜普, 歐海濤. 基于再勵學習與遺傳算法的交通信號自組織控制[J]. 自動化學報
                      [13] 劉民, 吳澄, 尹文君. 帶特殊工藝約束的并行機器生產線調度問題的一種遺傳算法[J]. 自動化學報
                      [14] 孫瑞祥, 屈梁生. 遺傳算法優化效率的定量評價[J]. 自動化學報
                      [15] 劉民, 吳澄. 解決并行多機提前/拖后調度問題的混合遺傳算法方法[J]. 自動化學報
                      [16] 謝濤, 張育林. 基于遺傳算法與Shannon熵的故障監控參數優選[J]. 自動化學報
                      [17] 唐立新, 楊自厚. 熱軋實施計劃中最優倒垛問題的整數規劃模型及遺傳算法[J]. 自動化學報
                      [18] 程鵬. 線性特征系統的標準形與極點配置[J]. 自動化學報
                      [19] 王躍云, 金鐘驥, 張鐘俊. 廣義系統的反饋控制與極點配置方法[J]. 自動化學報
                      [20] 王翼. 極點配置問題算法的改進[J]. 自動化學報
                    • 加載中
                    計量
                    • 文章訪問數:  1868
                    • HTML全文瀏覽量:  1530
                    • 被引次數: 0
                    出版歷程
                    • 收稿日期:  2019-09-03
                    • 錄用日期:  2019-12-15
                    • 網絡出版日期:  2020-01-04

                    考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化

                    doi: 10.16383/j.ass.c190626
                      基金項目:  國家自然科學基金(61473053); 遼寧省重點研發計劃指導計劃(2018401002)資助
                      作者簡介:

                      大連海事大學交通運輸工程學院教授, 博士. 主要研究方向為交通運輸系統規劃與設計, 戰略管理與系統規劃. 本文通訊作者.Email: fhm468@163.com

                      大連海事大學交通運輸工程學院博士研究生. 主要研究方向為交通運輸規劃與管理;Email: guozhenfeng_dl@126.com

                      大連海事大學交通運輸工程學院碩士研究生. 主要研究方向為物流工程.E-mail: Yuelj11@163.com

                      大連海事大學交通運輸工程學院講師, 博士. 主要研究方向為交通運輸系統規劃與設計, 戰略管理與系統規劃.E-mail: mengzhi1440@126.com

                    摘要: 合理調度集裝箱碼頭的裝卸設備以減少生產過程中的能耗, 對實現其低碳綠色化發展具有重要意義. 針對集裝箱碼頭向自動化發展過程中的雙小車岸橋與AGV聯合配置及調度問題, 考慮AGV續航時間、雙小車岸橋中轉平臺容量和堆場緩沖支架容量約束, 以岸橋的能耗最小為第一階段模型的優化目標, 以AGV運輸過程的能耗最小為第二階段目標建立兩階段優化模型; 設計枚舉法求解第一階段模型, 改進遺傳算法求解第二階段優化模型. 以洋山四期自動化集裝箱碼頭為例進行實驗分析, 針對不同船舶在港總裝卸時間和AGV配置原則進行實驗, 驗證了模型和算法的有效性, 結果表明以最小化能耗為目標的雙小車岸橋與AGV聯合調度可在岸橋主小車不延誤的前提下, 顯著減少AGV的配置數量.

                    English Abstract

                    范厚明, 郭振峰, 岳麗君, 馬夢知. 考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化. 自動化學報, 2020, 45(1): 1?15. doi: 10.16383/j.ass.c190626
                    引用本文: 范厚明, 郭振峰, 岳麗君, 馬夢知. 考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化. 自動化學報, 2020, 45(1): 1?15. doi: 10.16383/j.ass.c190626
                    Fan Hou-Ming, Guo Zhen-Feng, Yue Li-Jun, Ma Meng-Zhi. Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving. Acta Automatica Sinica, 2020, 45(1): 1?15. doi: 10.16383/j.ass.c190626
                    Citation: Fan Hou-Ming, Guo Zhen-Feng, Yue Li-Jun, Ma Meng-Zhi. Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving. Acta Automatica Sinica, 2020, 45(1): 1?15. doi: 10.16383/j.ass.c190626
                    • 集裝箱船大型化發展對集裝箱碼頭前沿作業提出了更高的要求, 一方面要求提高碼頭裝卸效率和服務水平, 另一方面要求降低成本并減少能耗, 推動集裝箱碼頭綠色低碳發展. 以人工操作為主體的集裝箱碼頭因不能及時準確地裝卸過程, 導致生產效率降低和能耗增加[1]. 為了提高碼頭裝卸效率和服務水平, 早在1993年, 荷蘭鹿特丹港就開始建設運營自動化集裝箱碼頭, 接著倫敦港、川崎港、新加坡港、漢堡港、廈門遠海、上海洋山港等港口相繼建成自動化集裝箱碼頭. 經過二十多年的發展, 目前自動化碼頭技術已經逐漸成熟和完善, 特別是為了適應節能環保要求, 已將早期使用的內燃機驅動的設備轉換為電力驅動, 岸邊作業采用雙小車岸橋進行船舶裝卸作業, 水平運輸采用自動導引車(Automated guided vehicle, AGV), 堆場使用自動化軌道吊(Automated rail mounted gantry crane, ARMG),“雙小車岸橋+AGV+ARMG”的裝卸工藝系統被應用于大多數自動化集裝箱碼頭. Sim[2]指出碼頭裝卸作業的能耗在碼頭作業總能耗中占比48.3 %, 聯合優化雙小車岸橋與AGV的配置及調度以減少碼頭裝卸作業的能耗, 對集裝箱碼頭實現綠色低碳發展有重要意義.

                      已有學者對集裝箱碼頭裝卸作業能耗、岸橋和AGV的配置和調度等問題展開了研究. 鄭松等[3]將碼頭系統的管理和控制過程通過平行系統融合在一起, 以實現對港機設備的最優控制. He等[4]指出岸橋和AGV的配置和調度是裝卸作業過程中兩個密切相連的生產決策問題, 岸橋的配置和調度決定船舶作業時間, AGV的配置和調度影響岸橋和ARMG的取/放箱時間, 聯合優化裝卸設備的配置和調度, 降低自動化集裝箱碼頭裝卸作業過程中的能耗成為研究熱點問題. 岸橋把待卸船集裝箱從船上提起放到運輸工具上, 又把待裝船集裝箱放到船上, 是碼頭裝卸作業中重要的一環, 關于減少岸橋作業中能耗的問題, 部分學者從資源配置的角度出發, 研究碼頭現有泊位和岸橋的分配方案. 例如, Chang等[5]研究了一種泊位岸橋調度策略, 并通過實例分析驗證了策略的有效性和可靠性. He[6]以最小化船舶延誤和最小化作業能耗為目標, 構建了泊位分配和岸橋分配問題混合整數優化模型, 并基于集成仿真的優化方法探索解空間.

                      在已知泊位計劃下優化岸橋在港口所有船舶之間調度以實現裝卸船時間最短的研究方面, Chang等[7]研究了動態船舶到達條件下岸橋調度問題, 提出一種基于動態滾動策略的岸橋調度方法, 建立了以最小化港口所有船舶的裝卸作業時間和均衡岸橋作業時間為目標的優化模型, 采用遺傳算法求解, 得到各個船上集裝箱任務的最佳裝卸順序和完成時間. Zhang等[8]考慮了裝卸過程中船舶的縱向穩定性, 建立了具有穩定性約束的岸橋調度優化模型, 引入了一種基于滑動窗的啟發式算法以修復違反穩定性約束的岸橋調度序列, 并將模型求解結果與不考慮船舶穩定性的結果進行了比較和分析, 驗證了模型和算法的有效性.

                      部分學者從優化每個集裝箱裝卸作業時間的角度出發, 研究了岸橋調度對減少裝卸能耗和裝卸完工時間的作用. Liu等[9]研究了單船岸橋分配和調度問題, 以最小化卸載過程中二氧化碳排放量為目標建立了AGV排隊模型. Liang等[10]從岸橋任務調度和數量配置兩個方面研究了岸橋調度問題, 通過分析每個任務的最早可作業時刻和要求完工時刻, 建立了岸橋調度和配置的耦合模型, 并應用循環迭代的方法求解每個時間窗內岸橋配置和調度方案. Msakni等[11]針對碼頭岸橋調度問題, 以單個集裝箱為任務單位, 提出了增加割平面和基于圖的二分搜索算法求模型的精確解, 并通過對比不同規模任務下的岸橋調度結果, 驗證模型和算法的有效性. Kim等[12]考慮到任務的優先關系和岸橋間安全距離, 建立了岸橋調度的混合整數規劃模型, 提出了一種基于分支定界的貪婪隨機自適應算法求解該模型. Nguyen等[13]分別采用遺傳算法和遺傳規劃算法求解岸橋裝卸過程中集裝箱的優先級, 使所求得的調度方案能在不確定環境下達到相對穩定的岸橋完工時間.

                      AGV在自動化集裝箱碼頭中作為水平運輸工具從岸橋下接收卸船集裝箱送至堆場, 在堆場接收待裝船集裝箱送至岸橋. 雖然AGV的能耗只占碼頭作業總能耗的1.04 %, 但是它的調度和配置對岸橋和場橋的作業能耗產生很大影響. 關于減少AGV作業中能耗的問題, 部分學者研究了AGV的調度策略, Kim等[14]以減少自動化集裝箱碼頭因船舶作業延誤產生的能耗為目標調度AGV, 求解最優的AGV配置調度方案. Choe等[15]提出了OnPL(Online preference learning)算法, 通過更新偏好函數動態地調整AGV的調度策略. Kim等[16]研究了多標準調度策略下自動化集裝箱碼頭AGV調度, 基于不同的場景對問題仿真模擬得到AGV的調度方案. 部分學者從岸橋和AGV協同調度的角度出發, Xin等[17]將集裝箱碼頭的集裝箱運輸作業看作是由連續時間的低級形態和動態離散事件的高級形態這兩部分組成, 提出了一種分層控制結構, 在岸橋和AGV的數量已知的條件下, 最小化上層岸橋作業完工時間和下層AGV的能耗. Peng等[18]量化了碼頭作業中設備的配置對總碳排放量的影響, 建立了基于復雜排隊網絡的仿真模型, 優化岸橋、場橋和AGV的配比. Yang等[19]基于混合流車間調度問題(HFSS), 以最小化總作業時間和最小能耗為目標, 提出并求解了岸橋、內集卡和場橋裝卸作業的雙目標聯合優化模型. Dkhil等[20]針對自動化集裝箱碼頭岸橋、AGV和場橋的作業問題, 提出了以最小化岸橋完工時間和最小化AGV配置數量為目標的優化模型, 并采用Cplex求解. Yang等[21]研究了同時裝卸作業的岸橋、場橋和AGV的集成調度, 設計了基于預防性擁塞規則的通用算法模擬處理自動化集裝箱碼頭裝卸作業.

                      部分學者考慮了AGV運輸過程中的不確定環境的影響, Singgih等[22]研究了自動化集裝箱碼頭AGV運輸路徑規劃問題, 考慮了AGV在運輸過程中因交通擁堵導致的等待時間, 以最小化運輸時間和等待時間為目標構建整數規劃模型, 應用改進Dijkstra算法求解. Legato等[23]考慮岸橋裝卸效率不恒定時岸橋和車輛的調度問題, 以最小化岸橋等待時間和AGV路徑沖突導致的擁堵時間為目標構建優化模型, 采用模擬退火算法求解模型, 并通過仿真實驗確定適用于實例的算法參數. Xin等[24]提出了一種無沖突調度算法, 用于生成AGV的無碰撞軌跡及岸橋、場橋的時刻表, 降低AGV運行的平均距離.

                      從現有研究中可以看出, 岸橋裝卸作業中產生的能耗在碼頭作業總能耗中占較大比重, AGV到達岸橋下的時間影響岸橋裝卸作業能耗. 已有關于減少碼頭裝卸作業能耗的研究中 (1)多以最小化作業岸橋的完工時間為目標, 沒有考慮要求船舶在港總裝卸時間對岸橋配置的影響. 實際調度過程中需要在保證所有車輛準時到達岸橋下的前提下, 規劃出能耗最低的運輸方案[25]. (2)大多針對為卸船階段或裝卸同步階段下岸橋和AGV的調度, 忽略了裝卸作業的各個階段的聯系. (3)為了避免岸橋延遲給碼頭帶來的損失, AGV的配置數量較多, 增加了不必要的運輸能耗, AGV的利用率較低. (4)在AGV調度過程中忽略了可續航時間對調度的影響, 不符合實際碼頭作業情況, 現實中AGV在耗盡電量前需駛往換電站更換電池或充電, 此過程中AGV不可使用. (5)缺乏對緩沖區的研究, 雙小車岸橋的緩沖平臺可以減少岸橋和AGV相互等待能耗, 堆場的緩沖區可以減少AGV在堆場的等待能耗. 因此, 本文對考慮能耗節約的雙小車岸橋與AGV聯合配置及調度問題進行研究, 保證岸橋主小車不延誤等待, 在運輸過程中AGV續航時間、雙小車岸橋中轉平臺容量和堆場緩沖支架容量約束下, 研究雙小車岸橋與AGV聯合配置及調度優化問題具有重要的理論與實際價值.

                      本文架構如下: 1 模型建立, 該部分構建了考慮能耗節約的集裝箱碼頭雙小車岸橋與AGV聯合配置及調度優化模型. 2 模型求解, 該部分進行了算法設計, 分別應用枚舉算法和遺傳算法求解岸橋調度的最優解并AGV調度的滿意解. 3 算例分析, 該部分采用實例驗證了模型及其算法的有效性. 4 結論, 該部分總結了研究成果并提出了未來研究方向.

                      • 集裝箱船在特定泊位靠港后, 碼頭根據要求的船舶在港總裝卸時間和船舶配積載信息配置及調度岸橋和AGV. 雙小車岸橋因具有中轉平臺可以減少岸橋和AGV相互等待時間而被廣泛應用于自動化集裝箱碼頭, 如圖1所示.

                        圖  1  雙小車岸橋示意圖

                        Figure 1.  The dual-trolley quay crane

                        在岸橋裝船過程中, AGV從箱區的緩沖支架上取裝船集裝箱至岸橋的門架小車下方, 岸橋門架小車將集裝箱從AGV上抓起放至中轉平臺, 岸橋主小車空閑時再將中轉平臺上的集裝箱吊起裝至船上; 岸橋卸船過程中, 主小車放卸船箱到中轉平臺, 門架小車從中轉平臺取箱放至AGV, 由其運送到該箱所在箱區, 待箱區的緩沖支架空閑時將集裝箱放到緩沖支架上. 多個岸橋同時進行裝卸作業有利于加快船舶裝卸速度, 但由于岸橋不可跨越且兩兩之間需要保持安全距離, 配置過多岸橋會產生相互干擾而引起的額外等待時間, 不僅會影響船舶在港裝卸作業時間, 也會增加碼頭作業能耗.

                        在裝卸船過程中, AGV的配置和調度方案影響岸橋實際完工時間, 配置數量過少可能會出現岸橋主小車等待AGV, 導致岸橋作業延誤, 影響完工時間. 調度方案不合理使得運輸過程中岸橋門架小車等待AGV、AGV空載和等待能耗增加. 如圖2所示, 空載AGV在箱區6接收裝船集裝箱后, 根據集裝箱所屬船貝信息, 前往岸橋C下交付集裝箱. 交箱后的AGV可調往堆場箱區(路線2)作業下一個裝船任務, 也可調往岸橋B(路線3)或岸橋A(路線4)作業下一個卸船任務. 根據岸橋調度方案制定合理的AGV配置和調度方案, 能保證岸橋主小車不延誤的同時, 減少岸橋門架小車等待AGV的能耗、AGV在岸橋和場橋下的等待能耗、AGV的載箱能耗和空載能耗.

                        圖  2  碼頭布局和AGV運輸流程示意圖

                        Figure 2.  Automated container terminal layout and AGV transportation process

                        本文分兩階段研究單船作業面模式下雙小車岸橋和AGV的聯合配置和調度問題. 第一階段根據待裝卸集裝箱數量和位置配置岸橋, 位于同一貝位的甲板箱或艙內箱的所有裝或卸作業稱為一個任務, 同一貝位中岸橋作業的先后順序為先卸甲板箱再卸艙內箱, 先裝艙內箱再裝甲板箱. 如圖3所示, 待裝卸集裝箱分布在6個不同的貝位, 貝位編號為1的32個集裝箱的卸船作業為任務1, 自左向右按先卸船再裝船的順序依次編號, 可知岸橋的總裝卸任務量為24, 如圖4所示. 第二階段根據所有作業該船的岸橋主小車和門架小車的計劃作業時間調度和配置AGV, 調度過程中一個集裝箱為一個作業單元, 并考慮AGV續航能力和往返換電站運輸時間的約束. 由于岸橋延遲會產生較高損失, 所以AGV調度過程中需要保證AGV到達時間不會使岸橋主小車等待.

                        圖  3  待裝卸集裝箱分布示意圖

                        Figure 3.  Containers to be loaded and unloaded

                        圖  4  岸橋任務編號示意圖

                        Figure 4.  Task number of quay crane

                        本文研究基于以下假設: (1)所有岸橋在同一軌道上移動且作業效率、油耗等性能相同或服從同一分布類型; (2)岸橋從編號小的船貝到編號大的船貝順序移動作業, 完成所分配的卸船任務后再從編號小的船貝到編號大的船貝開始裝船作業; (3)不考慮AGV運輸過程中的路徑沖突等不確定因素; (4)箱區下均設有緩沖支架, 每個箱區有且僅有一臺ARMG, 所有ARMG的工作能力、油耗等性能相同; (5)所有集裝箱的箱型一致, 所有AGV的行駛速度、油耗等性能相同或服從同一分布類型.

                      • 第一階段是為各岸橋分配裝卸任務并安排作業的先后順序, 以在規定的船舶總裝卸時間內完成對所有任務的裝卸作業, 優化的目標是岸橋能耗最小.

                        1)集合、參數及狀態變量

                        $i$: 任務編號, $i = 1,2\cdots, I$;

                        $k$: 岸橋編號, $k = 1,2\cdots, K$;

                        $b$: 船舶貝位編號, $b = 1,2\cdots, B$;

                        ${N_i}$: 任務$i$中待裝卸的集裝箱數量;

                        ${l_i}$: 任務$i$所在貝位位置;

                        ${l_{Sk}}$: 岸橋$k$開始作業時刻所在的貝位位置;

                        ${l_{Fk}}$: 岸橋$k$完工時刻所在的貝位位置;

                        ${l_{saf}}$: 安全貝位距離;

                        $\psi $: 不能同時作業的任務集合, $ \psi = \left\{ \left. {(i,j)} \right|i,j \in I,\right.$  $\left. \left| {{l_j} - {l_i}} \right| \le{l_{saf}} \right\}$;

                        ${\tau _1}$: 岸橋沿船舶縱向移動一個貝位所需時間;

                        ${\tau _2}$: 岸橋主小車完成一次取/放箱作業所需時間;

                        ${C_1}$: 每臺岸橋單位時間的作業能耗;

                        ${C_2}$: 每臺岸橋單位時間的移動能耗;

                        ${C_3}$: 每臺岸橋單位時間的等待能耗;

                        ${t_F}$: 船舶在港總裝卸時間;

                        ${t_i}$: 任務$i$的作業時間;

                        ${T_{ik}}$: 岸橋$k$裝卸完任務$i$內所有集裝箱的完工時刻;

                        ${t_{ij}}$: 岸橋完成當前任務$i$后開始任務$j$前因其他岸橋  干擾需等待的時間;

                        2)決策變量

                        ${x_{ik}}$: 岸橋$k$作業任務$i$時為1, 否則為0;

                        ${z_{ijk}}$: 岸橋$k$作業完任務$i$后作業任務$j$時為1, 否則  為0;

                        3)數學模型

                        目標函數:

                        $$ \begin{split} \min {f_1} = &{C_1} \times \sum\limits_{i = 1}^I {\sum\limits_{k = 1}^K {{x_{ik}}{t_i}} } + \\ & {C_2} \times \sum\limits_{i = 1}^I {\sum\limits_{j = 1}^I {\sum\limits_{k = 1}^K {|{l_j} - {l_i}| \times {z_{ijk}}{\tau _1}} } } +\\ & {C_3} \times \sum\limits_{i = 1}^I {\sum\limits_{j = 1}^I {\sum\limits_{k = 1}^K {{z_{ijk}}{t_{ij}}} } } \end{split} $$ (1)

                        約束條件:

                        $$ \sum\limits_{k = 1}^K {{x_{ik}} = 1} \;\;\;\;\;\;\;\;\;\;\forall i \in I\hspace{70pt} $$ (2)
                        $$ \sum\limits_{S = 1}^I {{x_{Sk}}} = 1\;\;\;\;\;\forall k \in K\hspace{80pt} $$ (3)
                        $$ \sum\limits_{F = 1}^I {{x_{Fk}}} = 1\;\;\;\;\;\forall k \in K\hspace{80pt} $$ (4)
                        $$ \sum\limits_{j = 1}^I {{z_{ijk}} - } \sum\limits_{j = 1}^I {{z_{jik}}} = 0\;\;\;\;\;\;\;\;\forall i \in I,\forall k \in K $$ (5)
                        $$ {t_i} = {N_i} \times {\tau _2}\;\;\;\;\;\;\;\;\;\;\;\;\;\forall i \in I\hspace{95pt} $$ (6)
                        $$ \begin{split} &\displaystyle\sum\limits_{i = 1}^I {\displaystyle\sum\limits_{k = 1}^K {{x_{ik}}{t_i}} } + \displaystyle\sum\limits_{i = 1}^I {\displaystyle\sum\limits_{j = 1}^I {\displaystyle\sum\limits_{k = 1}^K {|{l_j} - {l_i}| \times {z_{ijk}}{\tau _1}} } }+ \\ &\quad \displaystyle\sum\limits_{i = 1}^I {\displaystyle\sum\limits_{j = 1}^I {\displaystyle\sum\limits_{k = 1}^K {{z_{ijk}}{t_{ij}}} } } \le {t_F}\;\forall i,j \in I,\forall k \in K \\[-15pt]\end{split}\hspace{30pt} $$ (7)
                        $$ {T_{ik}} + {l_{saf}}/{\tau _1}\; \le {T_{jk'}} - {t_j}\;\;\forall (i,j) \in \psi ,\forall k,k' \in K $$ (8)
                        $$ {T_{ik}} + |{l_j} - {l_i}| \times {\tau _1} + {t_j} + {t_{ij}} = {T_{jk}}\;\forall i,j \in I,\forall k \in K $$ (9)
                        $$ {x_{ik}},{z_{ijk}} \in \left\{ {1,0} \right\}\;\;\;\forall i,j \in I,\forall k \in K\hspace{50pt} $$ (10)
                        $$ {T_{ik}} \ge 0\;\;\;\;\;\forall i \in I,k \in K\hspace{95pt} $$ (11)

                        式(1)為目標函數, 表示總能耗最小化, 總能耗包括岸橋作業能耗、岸橋移動能耗和干擾造成的等待能耗; 式(2)表示每個任務只能且必須分配一個岸橋為其作業; 式(3)和式(4)表示每個岸橋有且僅有一個開始任務和一個結束任務; 式(5)表示每個任務均有且僅有一個緊前任務和緊后任務; 式(6)任務$i$的作業時間; 式(7)表示岸橋總完工時間小于船舶在港總裝卸時間; 式(8)表示若任務$i$和任務$j$不能同時被作業, 則岸橋$k$完成任務$i$并移動到安全距離后, 下一個岸橋才能開始作業任務$j$, 即船舶裝卸過程中, 岸橋間始終保持安全距離; 式(9)表示岸橋$k$上一個任務的完成時刻與下一個任務的完成時刻之間的關系; 式(10)和(11)定義了變量類型及取值范圍.

                      • 第二階段是為各AGV分配裝卸任務并安排作業的先后順序, 以保證每個岸橋主小車不延遲, 優化的目標為AGV的作業總能耗最小.

                        1)集合、參數及狀態變量

                        $L$: 裝船集裝箱集合;

                        $D$: 卸船集裝箱的集合;

                        $n$: 集裝箱編號, $n = 1,2,\cdots, N$;

                        $a$: AGV編號, $a = 1,2,\cdots, A$;

                        $c$: 場橋編號, $c = 1,2,\cdots, C$;

                        $T_{nk}^q$: 岸橋$k$主小車對第$n$個集裝箱的計劃作業時刻,    即岸橋$k$的主小車計劃從中轉平臺上提起裝船   箱或計劃將卸船箱放到中轉平臺的時刻;

                        $T_{nk}^Q$: 岸橋$k$主小車對第$n$個集裝箱的實際作業時刻;

                        ${T_{{q_{\max }}}}$: 岸橋主小車計劃作業最后一個集裝箱的時刻;

                        $T_{nk}^e$: 岸橋$k$的門架小車對第$n$個集裝箱的計劃作業   時刻, 即岸橋$k$的門架小車計劃從AGV上提   起第$n$個待裝船集裝箱的時刻或放下第$n$個待   卸船集裝箱到AGV的時刻;

                        $T_{nk}^E$: 岸橋$k$的門架小車對第$n$個集裝箱的實際作業   時刻;

                        ${T_{nc}}$: 場橋$c$作業集裝箱$n$的時刻, 即在緩沖支架取   裝船集裝箱$n$的時刻或放卸船集裝箱$n$到緩沖   支架上的時刻;

                        ${T_{na}}$: 第$a$輛AGV在箱區/岸橋下開始作業集裝箱$n$   的時刻;

                        $ET_{nk}^O$: 岸橋$k$的門架小車最早可在中轉平臺提/放   集裝箱$n$的時刻;

                        $LT_{nk}^O$: 岸橋$k$的門架小車最晚可在中轉平臺提/放   集裝箱$n$的時刻;

                        $ET_{nc}^G$: AGV在場橋$c$作業的箱區下最早可在緩沖   支架提/放集裝箱$n$的時刻;

                        $LT_{nc}^G$: AGV在場橋$c$作業的箱區下最晚可在緩沖   支架提/放集裝箱$n$的時刻;

                        ${t_{na}}$: 第$a$輛AGV從箱區(岸橋下)出發將集裝箱$n$   運輸到岸橋下(箱區)所用的時間;

                        ${t_{nn'}}$: AGV交付集裝箱$n$后前往下一個集裝箱所在   位置的空駛時間;

                        ${w_{nka}}$: 運載集裝箱$n$的第$a$輛AGV在岸橋$k$下的   等待時間;

                        ${w_{nca}}$: 運載集裝箱$n$的第$a$輛AGV在場橋$c$下的等   待時間;

                        ${C_4}$: 岸橋的門架小車等AGV時單位時間的等待   能耗;

                        ${C_5}$: 每輛AGV單位時間載箱移動能耗;

                        ${C_6}$: 每輛AGV單位時間的空載移動能耗;

                        ${C_7}$: 每輛AGV在岸橋或場橋下單位時間的等待   能耗;

                        ${p_1}$: 雙小車岸橋中轉平臺的容量;

                        ${p_2}$: 每個箱區緩沖支架的容量, 即每個箱區的緩沖   支架上可以同時放置集裝箱的數量;

                        ${\tau _3}$: 岸橋的門架小車完成一次取/放箱作業所需要   的平均時間;

                        ${\tau _4}$: 場橋完成一次取/放箱作業所需要的平均時間;

                        ${\tau _5}$: AGV往返充電站所需時間;

                        ${v_1}$: AGV載箱行駛速度;

                        ${v_0}$: AGV空載行駛速度;

                        2)決策變量

                        ${y_{na}}$: 集裝箱$n$被分配給車$a$時等于1, 否則等于0;

                        ${z_{nn'a}}$: 第$a$輛AGV運輸完集裝箱$n$后去運輸下一   個集裝箱$n'$時等于1, 否則等于0;

                        ${u_{na}}$: 當車$a$運輸完集裝箱$n$后剩余電量小于安全電   量時等于1, 否則等于0;

                        3)數學模型

                        目標函數:

                        $$ \begin{split} {f_2} =& \min {C_4} \times \displaystyle\sum\limits_{n = 1}^N {\displaystyle\sum\limits_{k = 1}^K {(T_{nk}^E - T_{nk}^e)} } +\\[-2pt] &{C_5} \times \displaystyle\sum\limits_{n = 1}^N {\displaystyle\sum\limits_{a = 1}^A {{y_{na}}{t_{na}}} } +\\[-2pt] &{C_6} \times \displaystyle\sum\limits_{n = 1}^N {\displaystyle\sum\limits_{n' = 1}^N {\displaystyle\sum\limits_{a = 1}^A {{z_{nn'a}}{t_{nn'}}} } } +\\[-2pt] &{C_7} \times (\displaystyle\sum\limits_{n = 1}^N {\displaystyle\sum\limits_{c = 1}^C {\displaystyle\sum\limits_{a = 1}^A {{w_{nca}}} } } +\\[-2pt] &\displaystyle\sum\limits_{n = 1}^N {\displaystyle\sum\limits_{k = 1}^K {\displaystyle\sum\limits_{a = 1}^A {{w_{nka}}} } } ) \end{split} $$ (12)

                        約束條件:

                        $$ \sum\limits_{a = 1}^A {{y_{na}}} = 1\;\;\;\;\;\;\,\,\,\,\,\,\,\,\,\,\,\;\forall n \in N\qquad\qquad\qquad\qquad $$ (13)
                        $$ \sum\limits_{S = 1}^N {{y_{Sk}}} = 1\;\;\;\;\; \forall k \in K\hspace{100pt} $$ (14)
                        $$ \sum\limits_{F = 1}^N {{x_{Fk}}} = 1\;\;\;\;\; \forall k \in K\hspace{100pt} $$ (15)
                        $$ T_{nk}^Q \le T_{nk}^q\;\;\;\;\;\;\;\;\; \;\forall n \in N\hspace{90pt} $$ (16)
                        $$ ET_{nk}^O \!=\! T_{nk}^e \!-\! {p_1} \!\times\! {\tau _2}\;,\;LT_{nk}^O = T_{nk}^e{\kern 1pt} \;\forall n \in L,\forall k \in K $$ (17)
                        $$ ET_{nk}^O \!=\! T_{nk}^e,\;LT_{nk}^O \!=\! T_{nk}^e \!+\! {p_1} \times {\tau _2}\;\;\forall n \in D,\forall k \in K $$ (18)
                        $$ ET_{nk}^O \le \;T_{nk}^E + \dfrac{1}{2}{\tau _3} \le LT_{nk}^O\;\;\;\;\;\forall n \in L,\forall k \in K $$ (19)
                        $$ ET_{nk}^O \le \;T_{nk}^E - \dfrac{1}{2}{\tau _3} \le LT_{nk}^O\;{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \forall n \in D,\forall k \in K\;\; $$ (20)
                        $$ \begin{split} &T_{nk}^E{\rm{ = max}}\{ {T_{na}} + {t_{na}}, T_{nk}^e\} \\ & \quad\forall n \in L,\forall k \in K,\forall a \in A \\ \end{split} \qquad\qquad\qquad\qquad\; $$ (21)
                        $$ T_{nk}^E \!=\! \max \{ {T_{na}},\;T_{nk}^e\} \;\forall n \!\in D,\forall k \in K,\forall a \in A\;\; $$ (22)
                        $$ T_{n'k}^e = T_{nk}^E + {\tau _3}\;\;\;\;\;\;\;{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \;\forall n,n' \in N,\forall k \in K\qquad\;\; $$ (23)
                        $$ \begin{split} ET_{nc}^G = & {T_{nc}}\;, LT_{nc}^G = {T_{nc}} + {p_2} \times {\tau _4}{\kern 1pt} \\ & \forall n \in L,\forall c \in C \end{split} \qquad\qquad\quad\; $$ (24)
                        $$ \begin{split} ET_{nc}^G =& {T_{nc}} - \;{p_2} \times {\tau _4}, LT_{nc}^G = {T_{nc}} \\ &\forall n \in D,\forall c \in C \end{split}\qquad\qquad\quad\; $$ (25)
                        $$ ET_{nc}^G \le \;{T_{na}} \le LT_{nc}^G\;{\kern 1pt} {\kern 1pt} {\kern 1pt} \forall n \in L,\forall a \in A,\forall c \in C $$ (26)
                        $$ \begin{split} &ET_{nc}^G \le \;{T_{na}} + {t_{na}} \le LT_{nc}^G\;\; \\ &\quad\forall n \in D,\forall a \in A,\forall c \in C \\ \end{split} \qquad\qquad\qquad\quad\;\; $$ (27)
                        $$ \begin{split} {w_{nka}} = &\max \{ T_{nk}^e - {T_{na}} - {t_{na}},0\} \\ & \forall n \in L,\forall k \in K,\forall a \in A \\ \end{split}\qquad\qquad\qquad\; $$ (28)
                        $$ \begin{split} {w_{nka}} = &\max \{ T_{nk}^e - {T_{na}},0\} \\ & \forall n \in D,\forall k \in K,\forall a \in A \\ \end{split} \qquad\qquad\qquad\;\; $$ (29)
                        $$ \begin{split} {w_{nca}} =& \max \{ ET_{nc}^G - {T_{na}},0\} \\ & \forall n \in L,\forall a \in A,\forall c \in C \\ \end{split} \qquad\qquad\qquad\;\;\; $$ (30)
                        $$ \begin{split} {w_{nca}} =& \max \{ ET_{nc}^G - {T_{na}} - {t_{na}},0\} \\ & \forall n \in D,\forall a \in A,\forall c \in C \\ \end{split} \qquad\qquad\quad\;\; $$ (31)
                        $$ \begin{split} &{T_{na}} + {t_{na}} + {w_{nka}} + {t_{nn'}} + {w_{n'ca}} + {\tau _5} \times {u_{na}} = {T_{n'a}}\; \\ &\quad \forall n \in L,n' \in L \\[-10pt] \end{split} $$ (32)
                        $$ \begin{split} &{T_{na}} + {t_{na}} + {w_{nka}} + {t_{nn'}} + {w_{n'ka}} + {\tau _5} \times {u_{na}} = {T_{n'a}}\; \\ &\quad \forall n \in L,n' \in D \\[-10pt] \end{split} $$ (33)
                        $$ \begin{split} &{T_{na}} + {t_{na}} + {w_{nca}} + {t_{nn'}} + {w_{n'ca}} + {\tau _5} \times {u_{na}} = {T_{n'v}}\; \\ &\quad\forall \;n \in D,n' \in L \\[-10pt] \end{split} $$ (34)
                        $$ \begin{split} &{T_{na}} + {t_{na}} + {w_{nca}} + {t_{nn'}} + {w_{n'ka}}\; + {\tau _5} \times {u_{na}} = {T_{n'a}}\; \\ &\quad\forall n \in D,n' \in D \\[-10pt] \end{split} $$ (35)
                        $$ \rho \; = \frac{{{{\rm{C}}_{Useful}}}}{{{{\rm{C}}_{Useless}}}}\qquad\qquad\qquad\qquad\qquad\qquad\qquad $$ (36)

                        其中,

                        $$\begin{split} {{\rm{C}}_{Useful}} = &{C_5} \times \sum\limits_{n = 1}^N {\sum\limits_{a = 1}^A {{y_{na}}{t_{na}}} } +\\ &{C_6} \times \sum\limits_{n = 1}^N {\sum\limits_{n' = 1}^N {\sum\limits_{a = 1}^A {{z_{nn'a}}{t_{nn'}}} } }\end{split}\qquad\qquad\;\;\; $$
                        $$ \begin{split} {{\rm{C}}_{Useless}} =& {C_5} \times \sum\limits_{n = 1}^N {\sum\limits_{a = 1}^A {{y_{na}}{t_{na}}} } +\\ &{C_6} \times \sum\limits_{n = 1}^N {\sum\limits_{n' = 1}^N {\sum\limits_{a = 1}^A {{z_{nn'a}}{t_{nn'}}} } } + \\ & {C_7} \times (\sum\limits_{n = 1}^N {\sum\limits_{c = 1}^C {\sum\limits_{a = 1}^A {{w_{nca}}} } } +\\ &\sum\limits_{n = 1}^N {\sum\limits_{k = 1}^K {\sum\limits_{a = 1}^A {{w_{nka}}} } } ) \end{split} \qquad\qquad $$
                        $$ {y_{na}},{z_{nn'a}},{u_{na}} \in \{ 0,1\} \;\;\;\forall n,n' \in N,\forall a \in A $$ (37)
                        $$ {T_{na}} \ge 0\;\;\;\;\;\;\forall n \in N,\forall a \in A\qquad\qquad\qquad\quad $$ (38)

                        式(12)為目標函數表示AGV運輸過程的能耗最小化, 即門架小車等待AGV的能耗、AGV的載箱能耗、AGV的空載能耗、AGV在岸橋和場橋下等待能耗之和最小化; 式(13)表示一個集裝箱由且僅由一輛AGV運輸; 式(14)和式(15)表示每個AGV有且僅有一個開始任務和一個結束任務; 式(16)表示岸橋主小車的實際作業時刻不晚于計劃作業時刻, 即保證岸橋主小車不延誤; 式(17)和式(18)分別表示岸橋門架小車放下裝船集裝箱到中轉平臺或從平臺取卸船集裝箱的時間窗; 式(19)和式(20)分別表示岸橋門架小車裝船或卸船時在中轉平臺的實際作業時刻應滿足時間窗約束; 式(21)和式(22)分別表示作業裝船集裝箱$n$或卸船集裝箱$n$時, 岸橋門架小車實際作業時刻與AGV到達時刻的關系; 式(23)表示更新后的門架小車計劃作業時刻; 式(24)和式(25)分別表示AGV運輸裝船箱或卸船箱時在緩沖支架的實際作業時刻應滿足時間窗約束; 式(26)和式(27)分別表示AGV在場橋$c$下取裝船箱或放卸船箱時滿足時間窗約束; 式(28)和式(29)分別表示AGV交付裝船集裝箱$n$或提取卸船集裝箱$n$時在岸橋門架小車下的等待時間; 式(30)和(31)分別表示AGV提取裝船集裝箱$n$或交付卸船集裝箱$n$時在場橋下的等待時間; 式(32)和式(33)分別表示AGV在送完裝船集裝箱$n$后, 開始作業下一個裝船集裝箱或卸船集裝箱的時間約束; 式(34)和式(35)分別表示AGV在送完卸船集裝箱$n$后, 開始作業下一個裝船集裝箱或卸船集裝箱的時間約束; 式(36)表示AGV的利用率, 即載箱能耗和空載能耗在總能耗中的占比. 式(37)和式(38)分別表示參數的類型和取值范圍.

                      • 第一階段模型研究岸橋的配置和調度問題, 考慮任務優先級和岸橋間安全距離的約束將待裝卸任務分配給各個岸橋. 該模型的求解結果直接影響第二階段AGV的調度和配置, 需設計一種算法求第一階段模型精確的最優解. 又因Lee [26]證明了考慮岸橋間安全距離的岸橋調度問題屬于NP完全問題, 無法在多項式時間內解決大規模問題, 故需設計一種策略減少計算量. 本文采用枚舉算法(Enumeration Algorithm, EA)求模型的最優解, 為減少計算量, 將位于同一貝位的甲板箱或艙內箱的所有裝或卸作業視為一個任務, 第一個岸橋的起始點位置和最后一個岸橋的終點位置視為已知, 岸橋$k$的終點視為岸橋$k + 1$的起點, 岸橋之間不可跨越, 故可將問題簡化為在任務集合$I$中為$k$個岸橋選擇$2(k - 1)$個始終點. 算法復雜度為$O({n^{2k - 2}})$, 具體步驟如下:

                        (1)將所有任務按裝卸作業的先后順序排列. 岸橋裝卸順序為: 同一岸橋, 裝/卸船任務中編號較小的貝位早于編號較大的貝位, 卸船任務早于裝船任務; 同一貝位, 卸船時甲板箱早于艙內箱, 裝船時艙內箱早于甲板箱.

                        (2)尋找不同岸橋配置方案下的最優調度方案. 考慮到岸橋的不可跨越性和岸橋間的安全距離, 列出不同配置方案中所有滿足約束的岸橋調度方案, 并計算其目標函數值, 目標值最小的調度方案即為該岸橋配置方案下的最優調度方案.

                        (3)確定最優的岸橋配置與調度方案. 在滿足船舶在港總裝卸時間的前提下, 比較不同岸橋配置數量下的最優目標值, 即可得到岸橋調度與配置的最優解.

                      • 由于第二階段優化AGV運行能耗的同時考慮了AGV的充電時間和岸橋中轉平臺、場橋下緩沖支架的容量約束, 這增加了問題的非線性, 使得模型變得異常復雜, 無法使用CPLEX等軟件求解. 本文根據問題特點改進遺傳算法對模型求解, 具體步驟如下:

                        1)解的編碼

                        采用矩陣編碼的方式, 設計一個兩行的染色體, 染色體的長度為待裝卸集裝箱數量, 染色體第一行的基因值表示集裝箱作業序號, 第二行的基因值表示為每個集裝箱分配的AGV. 由配積載圖和第一階段岸橋分配結果, 可知每個集裝箱的作業岸橋序號、場橋序號. 假設某一時刻3臺岸橋同時裝卸集裝箱,6輛AGV參與運輸集裝箱, 其中作業順序為27的集裝箱, 由序號為7的場橋和序號為2的岸橋作業, 并分配給序號為1的AGV運輸, 則染色體如圖5所示:

                        圖  5  染色體示意圖

                        Figure 5.  The chromosome

                        2)生成初始種群

                        在式(13)$\ \sim $(15)的約束下生成一定數量的個體, 其中每個個體的任務序列和AGV作業量利用隨機數生成, 所有的個體構成初始種群.

                        3)評價與選擇

                        根據每個個體的基因值, 計算目標函數值, 具體過程如下:

                        1)由公式(17)-(20)計算岸橋$k$的門架小車計劃提/放集裝箱$n$的時間窗$[ET_{nk}^O, LT_{nk}^O]$, 由公式(24)?(27)計算AGV在場橋$c$下計劃提/放集裝箱$n$的時間窗$[ET_{nc}^G, LT_{nc}^G]$.

                        2)對于裝船集裝箱$n$, 若空載AGV到達時間早于場橋最早放箱時間$ET_{nc}^G$, 則在場橋下等待; 若AGV到達時間晚于$LT_{nc}^G$, 表示箱區內的緩沖支架已全被占用, 則場橋需要等待AGV; 否則, AGV將從緩沖支架提箱前往岸橋$k$下; 若重載AGV到達時間早于$ET_{nk}^O - \dfrac{1}{2}{\tau _3}$, 則在岸橋下等待; 若AGV到達時間晚于$LT_{nk}^O - \dfrac{1}{2}{\tau _3}$, 則岸橋的主小車和門架小車均需等待AGV; 若AGV在時間窗$\left[T_{nk}^e, LT_{nk}^O - \dfrac{1}{2}{\tau _3}\right]$內到達, 則岸橋的門架小車等待, 由公式(22)和(23)更新$T_{nk}^E$; 否則, AGV交付集裝箱$n$后前往服務下一集裝箱$n'$.

                        3)對于卸船集裝箱$n$, 若空載AGV到達時間早于岸橋$k$的門架小車最早放箱時間$T_{nk}^e$, 則在場橋下等待; 若AGV到達時間晚于$LT_{nk}^O + \dfrac{1}{2}{\tau _3}$, 則岸橋的主小車和門架小車均需等待AGV;AGV在時間窗$[T_{nk}^e, LT_{nk}^O + \dfrac{1}{2}{\tau _3}]$內到達, 則岸橋的門架小車等待, 由公式(22)和(23)更新$T_{nk}^E$, AGV將從岸橋的門架小車下提箱前往場橋$c$下; 若重載AGV到達時間早于$ET_{nc}^G$, 則在場橋下等待; 若AGV到達時間晚于$LT_{nc}^G$, 則場橋需要等待AGV; 否則, AGV交付集裝箱$n$后前往服務下一集裝箱$n'$.

                        目標函數計算流程如圖6所示. 因為岸橋主小車和場橋的延遲會給碼頭作業帶來較大的損失, 故設岸橋主小車和場橋的延遲能耗為無窮大. 本文模型以最小化能耗為目標, 設目標函數的倒數為適應度值.

                        圖  6  目標函數求解流程圖

                        Figure 6.  Solution flowchart

                        4)交叉與變異

                        為提高算法的局部搜索能力, 保證種群的多樣性與質量, 根據問題特征設計了交叉和變異方式, 如圖7所示. 將種群中所有個體分組, 隨機選擇八個個體為一組, 種群中適應度最高的個體為全局最優解, 每組中適應度最高的個體為局部最優解, 局部最優解直接保留至下一代. 采用兩點交叉算子對染色體全局最優解和局部最優解進行交叉操作, 隨機生成交叉點位, 交叉操作可產生4個新個體, 具體變化方式見圖7(a). 采用基因倒置、基因互換和更新斷點的方式對局部最優染色體變異, 產生其余三個新個體, 變異操作具體變化方式見圖7(b)、(c)(d), 每代的交叉變異操作均可產生新的個體.

                        圖  7  交叉和變異

                        Figure 7.  Crossover and variation

                        5)不滿足約束個體的處理

                        在基因變異的過程中, 導致岸橋主小車和場橋作業延誤的個體序列, 其延誤能耗設為無窮大, 則該個體的適應度值為無窮小, 不會遺傳到下一代.

                        6)終止規則

                        當算法的迭代次數達到最大值時, 算法終止.

                      • 本文以上海洋山港自動化集裝箱碼頭為例, 研究某靠港船舶裝卸作業過程. 碼頭整體布局和水平運輸交通規則見圖2. AGV所在的QC 作業區共7條行車道, 每條車道寬4 m, 其中4條為裝卸車道, 3條為穿越車道, 裝卸車道成對布置, 并與穿越車道相間隔. 緩沖車道縱向27 m, 可雙向行駛, 堆場行駛區共有8條雙向車道, 且相鄰車道行駛方向相反; 箱區之間的距離為35米. AGV更換電池一次可續航480分鐘.

                        船上集裝箱的位置分布[26]圖8所示, 共20個待裝卸貝位. 碼頭裝卸作業采用“雙小車岸橋+AGV+ARMG”的生產方案, 岸橋、AGV的運輸速度及作業能耗等相關參數[27-28]表1. 堆場有9個箱區用于堆放待卸船集裝箱和待裝船集裝箱. 雙小車岸橋中轉平臺的容量為2, 兩岸橋安全作業間距設為1貝位; 每個箱區下緩沖支架的容量為4.

                        圖  8  待裝卸集裝箱船

                        Figure 8.  The ship of containers to be loaded and unloaded

                        表 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}/[m \cdot {\min ^{ - 1}}]$210
                        ${v_0}/[m \cdot {\min ^{ - 1}}]$350
                        ${C_1}/\left[ {kw \cdot h \cdot { {\left( {h \cdot{\simfont\text{臺} } } \right)}^{ - 1} } } \right]$91.24
                        ${C_2}/[kw \cdot h \cdot {(h \cdot {\simfont\text{臺} })^{ - 1} }]$70.18
                        ${C_3}/[kw \cdot h \cdot {(h \cdot {\simfont\text{臺} })^{ - 1} }]$49.6
                        ${C_4}/[kw \cdot h \cdot {(h \cdot {\simfont\text{臺} })^{ - 1} }]$49.6
                        ${C_5}/[kw \cdot h \cdot {(h \cdot {\simfont\text{輛} })^{ - 1} }]$21
                        ${C_6}/[kw \cdot h \cdot {(h \cdot {\simfont\text{輛} })^{ - 1} }]$14
                        ${C_7}/[kw \cdot h \cdot {(h \cdot{\simfont\text{輛} })^{ - 1} }]$9
                      • (1)第一階段岸橋調度與配置優化結果

                        采用Matlab2016進行編程求解, 設船舶在港總裝卸時間為44小時, 則碼頭需要配置和調度岸橋以在44小時內完成所有的裝卸作業. 岸橋配置數量為2時, 如表2所示, 最小完工時間為4 709 min, 不能在要求的時間內完工; 岸橋配置數量為3和4時, 岸橋的完工時間、作業能耗, 每臺岸橋的調度方案、開始和完工時間的詳細求解結果如表 2所示, 配置3臺岸橋的能耗接近于配置2臺岸橋, 但可以在規定時間內完成裝卸作業, 配置4臺岸橋的能耗和時間均高于配置3臺岸橋, 表明岸橋數量過多時岸橋之間存在干擾等待現象, 增加了額外的作業時間和作業能耗. 所以最優岸橋配置數量為3臺, 最小岸橋作業能耗為11 505 $kw \cdot h$, 完工時間為2 605 min. 該配置方案下最優的調度方案為: 卸船作業時, 岸橋1卸貝$1\sim 3 $、岸橋2卸貝$3\sim 10 $、岸橋3卸貝$11\sim 20 $; 裝船作業時, 岸橋1裝貝位$1\sim 13 $、岸橋2裝貝位$14\sim 18 $、岸橋3裝貝位$19\sim 20 $. 在此過程中, 岸橋1在第640 min結束卸船作業開始裝船, 岸橋3在第2 323 min時才結束卸船作業, 裝卸同步作業時間達1 683 min, 有利于減少AGV的空載能耗. 岸橋在貝位間的實時行走路徑如圖9所示. 由圖9可知岸橋作業路線無交點, 且任意時刻保持安全距離.

                        表 2  岸橋調度方案比較

                        Table 2.  Comparison of dual-trolley quay crane scheduling schemes

                        $k$${T_{Ik}}$${F_1}$調度方案開始-完工時刻
                        24 70911 507QC1B1- B6卸船作業0?917 min
                        B1-B18裝船作業924?3 789 min
                        QC2B7-B20卸船作業0?3 787 min
                        B19-B20裝船作業3 789?3 889 min
                        32 60511 504QC1B1-B3卸船作業0?640 min
                        B1-B13裝船作業643?2 605 min
                        QC2B3-B10卸船作業0?1 740 min
                        B14-B18裝船作業1 743?2 546 min
                        QC3B11-B20卸船作業0?2 323 min
                        B19-B20裝船作業2 324?2 429 min
                        42 63611 484QC1B1-B3卸船作業0?640 min
                        B1-B9裝船作業644?1 970 min
                        QC2B4-B5卸船作業0?93 min
                        B10-B11裝船作業98?395 min
                        QC3B6-B10卸船作業0?1 646 min
                        B12-B16裝船作業1 648?2 636 min
                        QC4B11-B20卸船作業0?2 325 min
                        B17-B20裝船作業2 331?2 468 min

                        圖  9  岸橋作業路線圖

                        Figure 9.  Path to the dual-trolley quay cranes

                        (2)第二階段AGV調度與配置優化結果

                        第二階段要為以上3769個待裝卸集裝箱分配AGV, 基于第一階段岸橋調度優化的求解結果, 采用matlab編程求解不同AGV配置方案下的調度方案, 種群大小設為120, 最大迭代次數為1 500次. 可得最優解為配置7輛AGV, AGV運行總能耗為3857$kw \cdot h$, AGV利用率為55.5 %. AGV調度方案如表3所示.

                        表 3  AGV調度結果

                        Table 3.  The scheduling results of AGV

                        AGV集裝箱作業序列
                        11→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→3588
                        22→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→3398
                        33→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→3767
                        46→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→3697
                        515→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→3614
                        628→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→3769
                        730→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

                        (3)結果分析與對比

                        為了驗證本文設計的第二階段算法和模型的有效性, 基于混合流水線調度問題計算裝卸完工時間的理論下界值[29]. 計算公式為:

                        $$\begin{split} \underline {{T_{{q_{\max }}}}} =& \max \Biggr(\Biggr(\sum\limits_{i = 1}^I {\sum\limits_{k = 1}^K {{x_{ik}}{t_i}} } +\\ &\sum\limits_{i = 1}^I {\sum\limits_{j = 1}^I {\sum\limits_{k = 1}^K {|{l_j} - {l_i}| \times {z_{ijk}}{\tau _1}} } } {\rm{\Biggr)/K}} + \\ & \min {t_{na}},\Biggr(\sum\limits_{n = 1}^N {\sum\limits_{a = 1}^A {{y_{na}}{t_{na}}} } + \\ &\sum\limits_{n = 1}^N {\sum\limits_{n' = 1}^N {\sum\limits_{a = 1}^A {{z_{nn'a}}{t_{nn'}}} } } \Biggr)/A + {\tau _2}\Biggr) \\ \end{split} $$

                        調度過程中不改變AGV的配置方案, 因此AGV的總運行時間至少為$\underline {{T_{{q_{\max }}}}} \times K$, 由此可知:

                        $$\begin{split} \underline {{f_2}} = &\sum\limits_{n = 1}^N {\sum\limits_{a = 1}^A {{y_{na}}{t_{na}}} } \times {C_5} + \\ &\sum\limits_{n = 1}^N {\sum\limits_{n' = 1}^N {\sum\limits_{a = 1}^A {{z_{nn'a}}{t_{nn'}}} } } \times {C_6} + \\ & \Biggr(\underline {{T_{{q_{\max }}}}} \times K - \sum\limits_{n = 1}^N {\sum\limits_{a = 1}^A {{y_{na}}{t_{na}}} } -\\ &\sum\limits_{n = 1}^N {\sum\limits_{n' = 1}^N {\sum\limits_{a = 1}^A {{z_{nn'a}}{t_{nn'}}} } } \Biggr) \times {C_7} \\ \end{split} $$

                        其中, $\underline {{f_2}} $表示第二階段的AGV作業能耗的下界值, 即重載能耗、空載能耗和等待能耗之和. 隨機生成圖8所示集裝箱船上各個貝位內待裝卸集裝箱的數量, 得到8組不同規模的算例, 其他參數設置不變, 將每組算例的程序運行10次計算結果的平均值, 將本文改進遺傳算法、傳統遺傳算法得到的目標函數值, 與基于混合流水線調度問題計算的理論下界值進行比較, 結果如表4所示.

                        表 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}$
                        1240187763.96197.736333.55190.133.85 %43.00 %
                        24082901 287.76339.076612.01335.980.91 %45.10 %
                        38295752 558.76706.8161 160.60671.085.05 %42.18 %
                        41 1297903 467.661 005.1161 749.47861.6514.27 %50.75 %
                        51 5051 1024 613.561 379.9462 114.891 190.3413.74 %43.72 %
                        61 9761 3916 045.962 323.1472 996.721 927.8817.01 %35.67 %
                        72 4191 6427 394.472 492.0783 634.972 191.9112.04 %39.70 %
                        82 6491 7928 091.682 789.6283 941.742 571.837.81 %34.75 %

                        表4中, ${f_1}$${A_1}$分別表示采用本文改進遺傳算法所得目標函數值和AGV配置數量; $f_2^*$${A_2}$分別表示傳統遺傳算法所得目標函數值和AGV配置數量. $GA{P_1} = ({f_2} - \underline {{f_2}} )/{f_2}$, $GA{P_2} = ({f_2}^{\rm{*}} - \underline {{f_2}} )/{f_2}^{\rm{*}}$, 分別表示本文算法與傳統遺傳算法所得結果與下界值的差距. 由表4可知, 本文算法所得滿意解優于傳統算法, 在問題規模較大的情況下, 本文算法性能較好.

                        為了進一步驗證本文調度策略的優越性, 對不同船舶在港總裝卸時間下岸橋的配置及調度、不同AGV配置原則下AGV的配置及調度進行實驗, 實驗中相關參數不變, 改變船舶在港總裝卸時間和AGV的配置原則, 其中, AGV配置原則一為AGV作業能耗最小, AGV配置原則二為AGV配置數量最少, AGV配置原則三為按1:3的比例配置岸橋和AGV[30]. 實驗結果如表5所示.

                        表 5  不同船舶在港總裝卸時間和不同AGV配置原則下調度結果比較

                        Table 5.  The results of different allowable laytime and different AGV configuration principles

                        實驗${t_f}/h$${T_{{q_{\max }}}}/h$K/臺${f_1}/kw \cdot h$$\min ({f_1} + {f_2})/kw \cdot h $AGV配置原則一AGV配置原則二AGV配置原則三
                        V/輛${f_2}/kw \cdot h$V/輛${f_2}/kw \cdot h$V/輛${f_2}/kw \cdot h$
                        94846.46311 499.115 374.673 875.564 417.494 198.1
                        104443.28311 505.315 362.373 857.064 030.494 168.6
                        114037.9411 482.715 308.1103 825.493 847.2123 977.6
                        123635.23411 483.815 136.893 653.073 659.6123 806.2
                        133232411 487.315 097.593 610.293 610.2123 879.0

                        表5可以看出, 船舶在港總裝卸時間影響岸橋的配置和調度, 對比實驗9和實驗10可知, 在港總裝卸時間越短, 為滿足要求需要配置岸橋數量越多; 對比實驗9和實驗10, 實驗11、12和實驗13可知, 岸橋配置數量相同的條件下, 在港總裝卸時間越短作業能耗越高.

                        圖10可以看出, 岸橋調度方案已知的條件下, 采用不同的AGV配置原則會產生不同的作業能耗, AGV的利用率也不同; 按1:3的比例配置岸橋和AGV(原則三)在產生很高作業能耗的同時降低了AGV的利用率, 在實驗9、10中AGV配置數量為9, 實驗11、12和13中AGV配置數量為12時, AGV利用率均偏低; 以最小化配置數量為原則調度AGV(原則二)時, 在雙小車岸橋的中轉平臺和堆場緩沖支架的解耦作用下, 實驗4中的岸橋和AGV的配置比例升至1:1.75時仍能保證岸橋作業不延遲. 雖然不存在岸橋主小車等待AGV的現象, 但門架小車等待時間較長導致作業能耗較高, AGV利用率偏低; 以最小化作業能耗為目標考慮岸橋和AGV的聯合調度(原則一), 可在岸橋不延遲的條件下, 優化AGV的調度作業使其利用率最大, 就實驗10而言, 采用此配置原則較原則二、三可分別為碼頭縮減4.5 %和8.08 %的AGV運行能耗.

                        圖  10  不同AGV配置數量下各實驗的AGV利用率

                        Figure 10.  AGV utilization rate of each experiment under different configurations

                      • 在實際生產調度過程中, 裝卸調度系統的性能受諸多隨機因素影響. 如, 不同堆存位置的集裝箱, 岸橋作業時間不同;AGV在充電站的排隊時間影響其往返時間;AGV送取箱過程中速度變化使得其到達目的地的時間變化. 以上隨機因素可能會導致岸橋主小車延誤, 影響完工時間. 本文分別圍繞每個集裝箱的岸橋作業時間、AGV往返充電站的時間、AGV的運行速度這三類隨機性因素展開實驗, 實驗設計如表6所示.

                        表 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}$的正態分布

                        在各個實驗中分別計算不同配置方案岸橋主小車的延遲時間$Del$、AGV的利用率$\rho $和運輸總能耗$f'_2$, 其中$f'_2 = {f_2} + {C_3} \times Dle$. 根據實驗輸出數據, 分析某一因素的隨機性對調度系統性能產生的影響. 實驗結果如表7所示.

                        表 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$
                        7055.56 %3 857.002.3033.80 %6 393.5349.9834.87 %6 196.18128.0835.55 %6 076.48
                        8051.42 %4 171.032.5231.97 %6 766.147.8132.51 %6 629.521.0334.00 %6 355.70
                        9051.52 %4 168.56030.32 %7 125.263.0933.71 %6 407.801.8731.34 %6 897.39
                        10050.79 %4 049.60031.63 %6 817.67032.64 %6 604.884.2531.17 %6 919.12
                        11050.42 %4 122.80030.53 %7 069.71030.10 %7 164.511.2629.55 %7 325.53

                        表7可知, 每個集裝箱的岸橋作業時間、AGV往返充電站的時間和AGV的運行速度三種隨機因素均對AGV的配置和調度結果產生了影響. 比較實驗14和15可知, 同樣的AGV配置數量下, 每個集裝箱的岸橋作業時間服從泊松分布時, 較于岸橋作業時間確定的實驗, 更可能使得岸橋主小車延遲, 通過增加AGV的配置數量, 可以減小這類隨機因素的影響. 比較實驗15和16可知, AGV往返充電站時間服從均值為負指數分布時, 較于充電時間確定的實驗, 岸橋主小車延遲時間更長. 比較實驗16和17可知, AGV的空載速度、重載速度服從正態分布時, 較于速度確定的實驗, 可能產生較長的岸橋主小車延遲, 但增加AGV配置數量會使其利用率降低, 卻不能消除岸橋延遲.

                        當確定性集裝箱碼頭配置與調度系統中某一參數發生隨機性變化時, 往往會產生岸橋主小車延遲, 可能導致船舶在港總裝卸作業時間增加. 但AGV配置數量和調度方案的改變可能會減小隨機性帶來的影響, 提高系統性能.

                      • 本文對集裝箱碼頭雙小車岸橋與AGV聯合配置及調度問題進行的研究中, 考慮了雙小車岸橋中轉平臺約束和箱區緩沖支架容量約束、AGV在運輸過程中續航時間的約束; 以岸橋的能耗最小為第一階段模型的優化目標, 以AGV運輸過程的能耗最小為第二階段目標建立兩階段優化模型, 采用EA算法求解岸橋主小車的作業時間; 在確保岸橋主小車作業不延誤前提下, 改進遺傳算法確定AGV的最優作業序列; 在此基礎上, 針對不同的要求船舶在港總裝卸時間和不同AGV配置原則下的岸橋和AGV配置和調度方案進行分析和對比, 以驗證模型和算法的有效性. 本文研究可以得到以下結論:

                        (1)本文所構建的兩階段調度優化模型能有效解決岸橋和AGV的聯合配置及調度問題, 所得岸橋和AGV的配置和調度方案能保證在船舶在港總裝卸時間內完成所有集裝箱的裝卸作業.

                        (2)船舶在港總裝卸時間影響岸橋的配置調度方案和作業能耗. 岸橋的作業效率是一定的, 因此要求在港總裝卸時間越短, 岸橋的配置數量越多; 在相同的岸橋配置方案下, 為了保證岸橋不等待, 在港總裝卸時間越短, 所需的AGV配置數量越多, AGV的作業能耗越大.

                        (3)本文研究單船作業面調度模式下, 考慮雙小車岸橋緩沖平臺和箱區緩沖支架的解耦作用以及AGV續航時間約束下的岸橋和AGV的配置與調度, 所得岸橋和AGV的最優配置比例約為1:2.33, 小于文獻[30]的研究中仿真所得最優比例1:3. 在岸橋的緩沖平臺和箱區緩沖支架的作用下, 針對上海洋山港的碼頭布局及現有岸橋的作業效率和AGV的運行速度來看, 若不考慮不確定環境及其它影響因素, 岸橋和AGV的配置比例降為1:1.75時仍可保證岸橋主小車不延遲, 但因AGV數量較少使得門架小車和場橋等待能耗, 故不一定能保證碼頭整體裝卸作業能耗最低.

                        本文的研究較符合實際自動化集裝箱碼頭船舶裝卸過程, 但本文還存在一些不足, 未考慮裝卸過程中不確定因素, 而實際作業過程中岸橋和AGV的故障、AGV行駛中路徑沖突和路徑擁堵等不確定情況會影響集裝箱的作業時間. 因此, 考慮不確定因素下的岸橋和AGV聯合調度問題將作為未來的研究方向.

                    WeChat 關注分享

                    返回頂部

                    目錄

                      /

                      返回文章
                      返回