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
  • [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.2017.c160834
    [2] 王秀英, 冯惠, 任志考, 周艳平. 面向炼钢—连铸调度过程的两阶段优化模型与算法[J]. 自动化学报, doi: 10.16383/j.aas.2016.c160005
    [3] 黄敏, 付亚平, 王洪峰, 朱兵虎, 王兴伟. 设备带有恶化特性的作业车间调度模型与算法[J]. 自动化学报, doi: 10.16383/j.aas.2015.c131067
    [4] 王利, 高宪文, 王伟, 王琦. 基于模型的子空间聚类与时间段蚁群算法的合同生产批量调度方法[J]. 自动化学报, doi: 10.3724/SP.J.1004.2014.01991
    [5] 金弟, 刘杰, 杨博, 何东晓, 刘大有. 局部搜索与遗传算法结合的大规模复杂网络社区探测[J]. 自动化学报, doi: 10.3724/SP.J.1004.2011.00873
    [6] 杨建军, 刘扬, 魏立新, 战 红. 多源注水系统泵站优化调度的双重编码混合遗传算法[J]. 自动化学报
    [7] 罗家祥, 唐立新. 带释放时间的并行机调度问题的ILS & SS算法[J]. 自动化学报
    [8] 杨海军, 李敏强. 有限群体遗传算法的动力性[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]. 自动化学报
  • 加载中
图(10) / 表(7)
计量
  • 文章访问数:  198
  • HTML全文浏览量:  121
  • PDF下载量:  7
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-09-03
  • 录用日期:  2019-12-15
  • 网络出版日期:  2020-01-04

考虑能耗节约的集装箱码头双小车岸桥与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)资助

摘要: 合理调度集装箱码头的装卸设备以减少生产过程中的能耗, 对实现其低碳绿色化发展具有重要意义. 针对集装箱码头向自动化发展过程中的双小车岸桥与AGV联合配置及调度问题, 考虑AGV续航时间、双小车岸桥中转平台容量和堆场缓冲支架容量约束, 以岸桥的能耗最小为第一阶段模型的优化目标, 以AGV运输过程的能耗最小为第二阶段目标建立两阶段优化模型; 设计枚举法求解第一阶段模型, 改进遗传算法求解第二阶段优化模型. 以洋山四期自动化集装箱码头为例进行实验分析, 针对不同船舶在港总装卸时间和AGV配置原则进行实验, 验证了模型和算法的有效性, 结果表明以最小化能耗为目标的双小车岸桥与AGV联合调度可在岸桥主小车不延误的前提下, 显著减少AGV的配置数量.

English Abstract

  • 集装箱船大型化发展对集装箱码头前沿作业提出了更高的要求, 一方面要求提高码头装卸效率和服务水平, 另一方面要求降低成本并减少能耗, 推动集装箱码头绿色低碳发展. 以人工操作为主体的集装箱码头因不能及时准确地装卸过程, 导致生产效率降低和能耗增加[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联合调度问题将作为未来的研究方向.

参考文献 (30)

目录

    /

    返回文章
    返回