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

1.   模型建立

1.1   问题描述

集装箱船在特定泊位靠港后, 码头根据要求的船舶在港总装卸时间和船舶配积载信息配置及调度岸桥和AGV. 双小车岸桥因具有中转平台可以减少岸桥和AGV相互等待时间而被广泛应用于自动化集装箱码头, 如图1所示.

图 1  双小车岸桥示意图

Fig. 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运输流程示意图

Fig. 2  Automated container terminal layout and AGV transportation process

下载: 全尺寸图片 幻灯片

本文分两阶段研究单船作业面模式下双小车岸桥和AGV的联合配置和调度问题. 第一阶段根据待装卸集装箱数量和位置配置岸桥, 位于同一贝位的甲板箱或舱内箱的所有装或卸作业称为一个任务, 同一贝位中岸桥作业的先后顺序为先卸甲板箱再卸舱内箱, 先装舱内箱再装甲板箱. 如图3所示, 待装卸集装箱分布在6个不同的贝位, 贝位编号为1的32个集装箱的卸船作业为任务1, 自左向右按先卸船再装船的顺序依次编号, 可知岸桥的总装卸任务量为24, 如图4所示. 第二阶段根据所有作业该船的岸桥主小车和门架小车的计划作业时间调度和配置AGV, 调度过程中一个集装箱为一个作业单元, 并考虑AGV续航能力和往返换电站运输时间的约束. 由于岸桥延迟会产生较高损失, 所以AGV调度过程中需要保证AGV到达时间不会使岸桥主小车等待.

图 3  待装卸集装箱分布示意图

Fig. 3  Containers to be loaded and unloaded

下载: 全尺寸图片 幻灯片

图 4  岸桥任务编号示意图

Fig. 4  Task number of quay crane

下载: 全尺寸图片 幻灯片

本文研究基于以下假设: 1)所有岸桥在同一轨道上移动且作业效率、油耗等性能相同或服从同一分布类型; 2)岸桥从编号小的船贝到编号大的船贝顺序移动作业, 完成所分配的卸船任务后再从编号小的船贝到编号大的船贝开始装船作业; 3)不考虑AGV运输过程中的路径冲突等不确定因素; 4)箱区下均设有缓冲支架, 每个箱区有且仅有一台ARMG, 所有ARMG的工作能力、油耗等性能相同; 5)所有集装箱的箱型一致, 所有AGV的行驶速度、油耗等性能相同或服从同一分布类型.

1.2   第一阶段岸桥的配置与调度优化模型

第一阶段是为各岸桥分配装卸任务并安排作业的先后顺序, 以在规定的船舶总装卸时间内完成对所有任务的装卸作业, 优化的目标是岸桥能耗最小.

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)数学模型

目标函数:

约束条件:

式(1)为目标函数, 表示总能耗最小化, 总能耗包括岸桥作业能耗、岸桥移动能耗和干扰造成的等待能耗; 式(2)表示每个任务只能且必须分配一个岸桥为其作业; 式(3)和式(4)表示每个岸桥有且仅有一个开始任务和一个结束任务; 式(5)表示每个任务均有且仅有一个紧前任务和紧后任务; 式(6)任务$i$的作业时间; 式(7)表示岸桥总完工时间小于船舶在港总装卸时间; 式(8)表示若任务$i$和任务$j$不能同时被作业, 则岸桥$k$完成任务$i$并移动到安全距离后, 下一个岸桥才能开始作业任务$j$, 即船舶装卸过程中, 岸桥间始终保持安全距离; 式(9)表示岸桥$k$上一个任务的完成时刻与下一个任务的完成时刻之间的关系; 式(10)和(11)定义了变量类型及取值范围.

1.3   第二阶段AGV的配置与调度优化模型

第二阶段是为各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)数学模型

目标函数:

约束条件:

其中

式(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)分别表示参数的类型和取值范围.

2.   模型求解

2.1   第一阶段模型求解

第一阶段模型研究岸桥的配置和调度问题, 考虑任务优先级和岸桥间安全距离的约束将待装卸任务分配给各个岸桥. 该模型的求解结果直接影响第二阶段AGV的调度和配置, 需设计一种算法求第一阶段模型精确的最优解. 又因Lee^[26]证明了考虑岸桥间安全距离的岸桥调度问题属于NP完全问题, 无法在多项式时间内解决大规模问题, 故需设计一种策略减少计算量. 本文采用枚举算法(Enumeration algorithm, EA)求模型的最优解, 为减少计算量, 将位于同一贝位的甲板箱或舱内箱的所有装或卸作业视为一个任务, 第一个岸桥的起始点位置和最后一个岸桥的终点位置视为已知, 岸桥$k$的终点视为岸桥$k + 1$的起点, 岸桥之间不可跨越, 故可将问题简化为在任务集合$I$中为$k$个岸桥选择$2(k - 1)$个始终点. 算法复杂度为${\rm O}({n^{2k - 2}})$, 具体步骤如下:

1)将所有任务按装卸作业的先后顺序排列. 岸桥装卸顺序为: 同一岸桥, 装/卸船任务中编号较小的贝位早于编号较大的贝位, 卸船任务早于装船任务; 同一贝位, 卸船时甲板箱早于舱内箱, 装船时舱内箱早于甲板箱.

2)寻找不同岸桥配置方案下的最优调度方案. 考虑到岸桥的不可跨越性和岸桥间的安全距离, 列出不同配置方案中所有满足约束的岸桥调度方案, 并计算其目标函数值, 目标值最小的调度方案即为该岸桥配置方案下的最优调度方案.

3)确定最优的岸桥配置与调度方案. 在满足船舶在港总装卸时间的前提下, 比较不同岸桥配置数量下的最优目标值, 即可得到岸桥调度与配置的最优解.

2.2   第二阶段模型求解

由于第二阶段优化AGV运行能耗的同时考虑了AGV的充电时间和岸桥中转平台、场桥下缓冲支架的容量约束, 这增加了问题的非线性, 使得模型变得异常复杂, 无法使用CPLEX等软件求解. 本文根据问题特点改进遗传算法对模型求解, 具体步骤如下:

1)解的编码

采用矩阵编码的方式, 设计一个两行的染色体, 染色体的长度为待装卸集装箱数量, 染色体第一行的基因值表示集装箱作业序号, 第二行的基因值表示为每个集装箱分配的AGV. 由配积载图和第一阶段岸桥分配结果, 可知每个集装箱的作业岸桥序号、场桥序号. 假设某一时刻3台岸桥同时装卸集装箱, 6辆AGV参与运输集装箱, 其中作业顺序为27的集装箱, 由序号为7的场桥和序号为2的岸桥作业, 并分配给序号为1的AGV运输, 则染色体如图5所示:

图 5  染色体示意图

Fig. 5  The chromosome

下载: 全尺寸图片 幻灯片

2)生成初始种群

在式(13) ~ (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  目标函数求解流程图

Fig. 6  Solution flowchart

下载: 全尺寸图片 幻灯片

4)交叉与变异

为提高算法的局部搜索能力, 保证种群的多样性与质量, 根据问题特征设计了交叉和变异方式, 如图7所示. 将种群中所有个体分组, 随机选择8个个体为一组, 种群中适应度最高的个体为全局最优解, 每组中适应度最高的个体为局部最优解, 局部最优解直接保留至下一代. 采用两点交叉算子对染色体全局最优解和局部最优解进行交叉操作, 随机生成交叉点位, 交叉操作可产生4个新个体, 具体变化方式见图7(a). 采用基因倒置、基因互换和更新断点的方式对局部最优染色体变异, 产生其余三个新个体, 变异操作具体变化方式见图7(b)、(c)和(d), 每代的交叉变异操作均可产生新的个体.

图 7  交叉和变异

Fig. 7  Crossover and variation

下载: 全尺寸图片 幻灯片

5)不满足约束个体的处理

在基因变异的过程中, 导致岸桥主小车和场桥作业延误的个体序列, 其延误能耗设为无穷大, 则该个体的适应度值为无穷小, 不会遗传到下一代.

6)终止规则

当算法的迭代次数达到最大值时, 算法终止.

3.   算例分析

3.1   算例描述

本文以上海洋山港自动化集装箱码头为例, 研究某靠港船舶装卸作业过程. 码头整体布局和水平运输交通规则见图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  待装卸集装箱船

Fig. 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}\;/({\rm m} \cdot {\min ^{ - 1} })$	210
${v_0}\;/({\rm m} \cdot {\min ^{ - 1} })$	350
${C_1}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{台} } } \right)}^{ - 1} } } \right)$	91.24
${C_2}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{台} } } \right)}^{ - 1} } } \right)$	70.18
${C_3}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{台} } } \right)}^{ - 1} } } \right)$	49.6
${C_4}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{台} } } \right)}^{ - 1} } } \right)$	49.6
${C_5}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{辆} } } \right)}^{ - 1} } } \right)$	21
${C_6}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{辆} } } \right)}^{ - 1} } } \right)$	14
${C_7}\;/\left( { {\rm kW} \cdot {\rm h} \cdot { {\left( { {\rm h} \cdot{\text{辆} } } \right)}^{ - 1} } } \right)$	9

下载: 导出CSV 

| 显示表格

3.2   算例求解及结果分析

1)第一阶段岸桥调度与配置优化结果

采用Matlab 2016进行编程求解, 设船舶在港总装卸时间为44小时, 则码头需要配置和调度岸桥以在44小时内完成所有的装卸作业. 岸桥配置数量为2时, 如表2所示, 最小完工时间为4 709 min, 不能在要求的时间内完工; 岸桥配置数量为3和4时, 岸桥的完工时间、作业能耗, 每台岸桥的调度方案、开始和完工时间的详细求解结果如表 2所示, 配置3台岸桥的能耗接近于配置2台岸桥, 但可以在规定时间内完成装卸作业, 配置4台岸桥的能耗和时间均高于配置3台岸桥, 表明岸桥数量过多时岸桥之间存在干扰等待现象, 增加了额外的作业时间和作业能耗. 所以最优岸桥配置数量为3台, 最小岸桥作业能耗为11 505 ${\rm kw} \cdot {\rm 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}$	调度方案		开始-完工时刻
2	4 709	11 507	QC1	B1-B6卸船作业	0 ~ 917 min
				B1-B18装船作业	924 ~ 3 789 min
			QC2	B7-B20卸船作业	0 ~ 3 787 min
				B19-B20装船作业	3 789 ~ 3 889 min
3	2 605	11 504	QC1	B1-B3卸船作业	0 ~ 640 min
				B1-B13装船作业	643 ~ 2 605 min
			QC2	B3-B10卸船作业	0 ~ 1 740 min
				B14-B18装船作业	1 743 ~ 2 546 min
			QC3	B11-B20卸船作业	0 ~ 2 323 min
				B19-B20装船作业	2 324 ~ 2 429 min
4	2 636	11 484	QC1	B1-B3卸船作业	0 ~ 640 min
				B1-B9装船作业	644 ~ 1 970 min
			QC2	B4-B5卸船作业	0 ~ 93 min
				B10-B11装船作业	98 ~ 395 min
			QC3	B6-B10卸船作业	0 ~ 1 646 min
				B12-B16装船作业	1 648 ~ 2 636 min
			QC4	B11-B20卸船作业	0 ~ 2 325 min
				B17-B20装船作业	2 331 ~ 2 468 min

下载: 导出CSV 

| 显示表格

图 9  岸桥作业路线图

Fig. 9  Path to the dual-trolley quay cranes

下载: 全尺寸图片 幻灯片

2)第二阶段AGV调度与配置优化结果

第二阶段要为以上3 769个待装卸集装箱分配AGV, 基于第一阶段岸桥调度优化的求解结果, 采用Matlab编程求解不同AGV配置方案下的调度方案, 种群大小设为120, 最大迭代次数为1500次. 可得最优解为配置7辆AGV, AGV运行总能耗为3857${\rm kw} \cdot {\rm h}$, AGV利用率为55.5 %. AGV调度方案如表3所示.

表 3  AGV调度结果

Table 3  The scheduling results of AGV

AGV	集装箱作业序列
1	1→7→11→16→22→25→36→47→54→59→63→70→78→83→86→89→96→107→113→131→···→ 3530→3537→3545→3548→3555→3562→3567→3572→3575→3580→3585→3588
2	2→5→8→13→17→18→21→27→31→37→48→58→61→67→74→80→82→90→94→98→115→···→ 3336→3344→3348→3354→3355→3361→3367→3377→3382→3393→3398
3	3→4→9→14→20→23→29→32→40→44→46→49→56→62→72→85→87→92→102→114→···→ 3747→3750→3751→3753→3754→3755→3757→3758→3760→3761→3762→3766→3767
4	6→10→12→24→34→38→42→51→60→64→69→73→76→84→88→93→99→100→105→110→···→ 3653→3655→3658→3661→3664→3665→3668→3674→3677→3680→3687→3691→3697
5	15→19→26→33→43→75→95→109→112→118→122→125→130→141→146→150→154→162→···→ 3538→3543→3551→3565→3569→3574→3578→3584→3592→3598→3605→3610→3614
6	28→35→39→45→50→53→55→65→71→79→91→97→101→104→108→120→123→133→136→···→ 3742→3744→3746→3748→3749→3752→3756→3759→3763→3764→3765→3768→3769
7	30→41→52→57→66→68→77→81→103→106→111→117→121→138→142→167→170→185→···→ 3702→3703→3707→3709→3710→3712→3716→3718→3721→3727→3730→3733→3738

下载: 导出CSV 

| 显示表格

3)结果分析与对比

为了验证本文设计的第二阶段算法和模型的有效性, 基于混合流水线调度问题计算装卸完工时间的理论下界值^[29]. 计算公式为:

调度过程中不改变AGV的配置方案, 因此AGV的总运行时间至少为$\underline {{T_{{q_{\max }}}}} \times K$, 由此可知:

其中, $\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}$
1	240	187	763.9	6	197.73	6	333.55	190.13	3.85 %	43.00 %
2	408	290	1 287.7	6	339.07	6	612.01	335.98	0.91 %	45.10 %
3	829	575	2 558.7	6	706.81	6	1 160.60	671.08	5.05 %	42.18 %
4	1 129	790	3 467.6	6	1 005.11	6	1 749.47	861.65	14.27 %	50.75 %
5	1 505	1 102	4 613.5	6	1 379.94	6	2 114.89	1 190.34	13.74 %	43.72 %
6	1 976	1 391	6 045.9	6	2 323.14	7	2 996.72	1 927.88	17.01 %	35.67 %
7	2 419	1 642	7 394.4	7	2 492.07	8	3 634.97	2 191.91	12.04 %	39.70 %
8	2 649	1 792	8 091.6	8	2 789.62	8	3 941.74	2 571.83	7.81 %	34.75 %

下载: 导出CSV 

| 显示表格

表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}/{\rm h}$	${T_{ {q_{\max } } } }/{\rm h}$	K/台	${f_1}/{\rm kW} \cdot {\rm h}$	$\min ({f_1} + {f_2})/{\rm kW} \cdot {\rm h}$	AGV配置原则一		AGV配置原则二		AGV配置原则三
						V/辆	${f_2}/{\rm kW} \cdot {\rm h}$	V/辆	${f_2}/{\rm kW} \cdot {\rm h}$	V/辆	${f_2}/{\rm kW} \cdot {\rm h}$
9	48	46.46	3	11 499.1	15 374.6	7	3 875.5	6	4 417.4	9	4 198.1
10	44	43.28	3	11 505.3	15 362.3	7	3 857.0	6	4 030.4	9	4 168.6
11	40	37.9	4	11 482.7	15 308.1	10	3 825.4	9	3 847.2	12	3 977.6
12	36	35.23	4	11 483.8	15 136.8	9	3 653.0	7	3 659.6	12	3 806.2
13	32	32	4	11 487.3	15 097.5	9	3 610.2	9	3 610.2	12	3 879.0

下载: 导出CSV 

| 显示表格

从表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利用率

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

下载: 全尺寸图片 幻灯片

3.3   随机因素对结果影响分析

在实际生产调度过程中, 装卸调度系统的性能受诸多随机因素影响. 如, 不同堆存位置的集装箱, 岸桥作业时间不同; 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}$的正态分布

下载: 导出CSV 

| 显示表格

在各个实验中分别计算不同配置方案岸桥主小车的延迟时间$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$
7	0	55.56 %	3 857.00		2.30	33.80 %	6 393.53		49.98	34.87 %	6 196.18		128.08	35.55 %	6 076.48
8	0	51.42 %	4 171.03		2.52	31.97 %	6 766.14		7.81	32.51 %	6 629.52		1.03	34.00 %	6 355.70
9	0	51.52 %	4 168.56		0	30.32 %	7 125.26		3.09	33.71 %	6 407.80		1.87	31.34 %	6 897.39
10	0	50.79 %	4 049.60		0	31.63 %	6 817.67		0	32.64 %	6 604.88		4.25	31.17 %	6 919.12
11	0	50.42 %	4 122.80		0	30.53 %	7 069.71		0	30.10 %	7 164.51		1.26	29.55 %	7 325.53

下载: 导出CSV 

| 显示表格

由表7可知, 每个集装箱的岸桥作业时间、AGV往返充电站的时间和AGV的运行速度三种随机因素均对AGV的配置和调度结果产生了影响. 比较实验14和15可知, 同样的AGV配置数量下, 每个集装箱的岸桥作业时间服从泊松分布时, 较于岸桥作业时间确定的实验, 更可能使得岸桥主小车延迟, 通过增加AGV的配置数量, 可以减小这类随机因素的影响. 比较实验15和16可知, AGV往返充电站时间服从均值为负指数分布时, 较于充电时间确定的实验, 岸桥主小车延迟时间更长. 比较实验16和17可知, AGV的空载速度、重载速度服从正态分布时, 较于速度确定的实验, 可能产生较长的岸桥主小车延迟, 但增加AGV配置数量会使其利用率降低, 却不能消除岸桥延迟.

当确定性集装箱码头配置与调度系统中某一参数发生随机性变化时, 往往会产生岸桥主小车延迟, 可能导致船舶在港总装卸作业时间增加. 但AGV配置数量和调度方案的改变可能会减小随机性带来的影响, 提高系统性能.

4.   结论

本文对集装箱码头双小车岸桥与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联合调度问题将作为未来的研究方向.