摘要：本文基于岸桥多作业线模式，在岸桥作业顺序已知的情况下，研究多箱区多场桥的优化调度问题。综合考虑场桥间的安全距离、走行时间等约束，构建以场桥作业时间最短为目标的调度优化模型，并提出基于场桥作业量均衡的改进遗传算法求解。数据实验表明，该模型能够在最小化场桥作业时间的同时，有效均衡场桥的作业量。

　　关键词：场桥调度;岸桥;作业顺序;改进遗传算法

　　集装箱运输的快速发展对集装箱码头作业效率提出了更高的要求，场桥作为码头前沿与堆场的连接点，是装卸过程的瓶颈环节，其效率会直接影响码头的整体作业效率。目前关于场桥调度优化的研究较多[1-4]，但大部分未考虑场桥作业均衡与移动时间，难以符合实际作业场景。因此，本文综合考虑了各场桥作业均衡与作业时间，研究岸桥多线作业模式下场桥调度优化问题，以得到更加实际与合理的场桥调度方案。

　　一、场景与问题描述

　　本文研究采用较为高效灵活的岸桥多线作业模式，在调度中多个岸桥同时工作，能够尽可能实现岸桥效率的最大化。本文解决的主要问题可描述为：在岸桥作业顺序、各个装卸任务位置已知的前提下，考虑场桥在箱区间的安全距离、走行路径等约束，以最小化场桥作业时间为目标，得到各场桥的作业顺序与最终调度方案。

　　二、场桥调度模型建立

　　1.前提假设

　　为建立合理的场桥调度优化模型，本文做出如下假设：(1)船舶靠泊、作业线的调度等情况已知;(2)每台场桥初始时刻位于要操作的第一个集装箱任务贝位，结束所有分配任务后位于最后一个集装箱任务贝位;(3)各作业线所负责的装船任务及其优先顺序已知，但不同作业线间无任务优先顺序限制。

　　2.参数及变量定义

　　输入变量：N为集装箱堆场中的任务数量;K为集装箱堆场中的场桥数量，其中k={1，2，…，k};I为作业线数(即岸桥数)，i={1，2，…，k};Ji为每个工作线中的任务数，其中j={1，2，…，Ji};Rij为任务数序号;bayij为任务Rij的贝位号;zomeij为任务Rij的区块号;optimeij为任务Rij的作业时间;Tstrait为场桥移动一个贝位的单位时间;Tturn为场桥转动一次的单位时间;baysafe为同箱区场桥间的安全作业距离;ngap为场桥作业量的不均衡底线。

　　状态变量：baykm为场桥k的第m个任务的贝位号;zomekm为场桥k的第m个任务的区块号;optimekm为场桥k的第m个任务作业时间;T(moving)km为场桥k在任务m-1和任务m间的移动时间，且当m=1时，T(moving)k1=0;Tk1为场桥k完成所有任务的作业时间。Xk (m-1，m)与Yk (m-1，m)为0、1变量，当场桥k的第m-1和m个任务在同一个zone区时，Xk (m-1，m)=1，否则Xk (m-1，m)=0;当场桥k的第m-1和m个任务在同一列时，Yk (m-1，m)=1，否则Yk (m-1，m)=0。

　　决策变量：

　　Mk场桥k的作业总数;m为场桥k分配的任务，其中m={1，2，…，Mk};Wijkm为0、1决策变量，当任务Rij由场桥k操作，且Rij是场桥k的第m个任务时，Wijkm=1，否则Wijkm=0。

　　3. 数学模型

　　综合考虑场桥作业时间和作业量均衡，建立基于岸桥作业顺序的场桥调度优化模型如下：

　　目标函数：

　　f=min(■(T(moving)km+Tk))　(1)

　　约束条件：

　　baykm=■■bayij×wijkm (2)

　　zonekm=■■zoneij×wijkm (3)

　　T(moving)km=

　　(baykm-bayk (m-1))×TstraitwhenXk (m-1，m)=1 Yk (m-1，m)=1(baykm-bayk (m-1)+2)×TstraitwhenXk (m-1，m)=1 Yk (m-1，m)=0(baykm-bayk (m-1)+2)×Tstrait+2TturnwhenXk (m-1，m)=0 Yk (m-1，m)=0min{baykm-bayk (m-1)，baykm-bayk (m-1)-2u}×Tstrait+2TturnwhenXk (m-1，m)=0 Yk (m-1，m)=1baykm≤u，bayk (m-1)≤umin{baykm-bayk (m-1)-2u，baykm-bayk (m-1)-4u}×Tstrait+2TturnwhenXk (m-1，m)=0 Yk (m-1，m)=1baykm≤u，bayk (m-1)≤u

　　(4)T(moving)k=■T(moving)km (5)

　　optimekm=■■optimeij×wijkm (6)

　　Tk=■optimekm (7)

　　■■wijkm=1，?坌i，j (8)

　　■■wijkm≤1，?坌k，m (9)

　　■■wijkm≥■■wij'km，?坌j，j' (10)

　　式(1)是目标函数，表示最小化所有场桥的作业时间。式(2)和式(3)计算场桥k第m个任务的bay和zone;式(4)计算场桥的移动时间;式(5)表示场桥k完成所有任务的总的移动时间;式(6)计算场桥k第m个任务的作业时间;式(7)计算场桥k完成所有任务的作业时间;式(8)和(9)表示每个任务被作业一次;式(10)表示同一作业线中的任务要按顺序完成;式(11)表示场桥间的安全距离。

　　三、算法设计

　　1. 染色体编码

　　为保证作业均衡，本文采用各场桥平均分配作业方法。如：任务数为N，场桥数为k，■=t…d，若d=0则每个场桥完成t个任务，基因长度为，前个基因上的任务由第一个场桥完成，以此类推。若d≠0，则每个场桥完成t+1个任务，基因长度为N+k-d，其中多余基因位用0代替。以2台场桥执行9个任务为例，得到染色体编码如图1。其中0为虚拟任务，由此可得到场桥1的作业序列为：[1-3-7-6-5]，场桥2的作业序列为：[4-9-2-8]。

　　图1 d10时染色体编码示意图

　　2. 初始种群的生成

　　本文采用随机方式产生M个不同的染色体构成初始种群，以保证初始种群中个体随机均匀分布在解空间内，使遗传算法不会在短时间内陷入局部最优。

　　3. 选择操作

　　本文采取轮盘赌选择策略与精英个体保留策略。进在化过程中保留适应度值最高的个体并直接作为子代之一，以避免在遗传操作中破坏较优个体。

　　四、算例分析

　　本文基础数据来自文献[5]。场桥最早可用时间均为0时刻，安全距离为2个贝位，转场时间为10min，移动一个贝位时间为0.2min。遗传算法求解参数为：种群大小200，迭代次数1000，交叉概率Pc=0.7，变异概率Pc=0.02。

　　实验求解耗时35.10s，迭代至604代时目标函数稳定且趋于收敛，结果见表1。为更直观对比本文与文献[5]方案，绘制场桥调度作业图见图2，整合两方案对比结果见表2。

　　表1 本文求解结果

　　图2 本文方案场桥调度图

　　表2 两方案主要指标对比

　　由图2、3与表3可知：在同时满足岸桥作业线中的任务优先级的情况下：文献[5]中的总完成时间较小，但3台场桥的完成时间相差很大，最早和最晚结束的场桥完工时间相差72min，完工时间的标准差为24.5。对比本文的调度方案，在总的完工时间仅增加6.4min情况下，3台场桥的完工时间标准差相对减少了69.96%，最大完工时间为129min，比文献[5]的减少了22.8min，同时因岸桥作业顺序而产生的额外等待时间也比文献[5]的结果减少15min。由此可见，与文献[5]相比，本文的算法更好地保障了场桥的作业均衡。

　　五、结论

　　本文研究了岸桥多线作业模式下多箱区场桥调度问题。以最小化场桥作业时间为目标，建立了整数规划模型，并提出基于场桥作业量均衡的遗传算法对模型求解。算例表明，通过该算法可以切实有效地求解场桥调度模型，得到合理可行的多场桥调度方案。C

　　(作者单位：章凯，中远海运科技(北京)有限公司;金懋，中国交通运输协会;康乃馨，国网北京物资公司;陈洪婷、纪寿文，北京交通大学)

　　参考文献

　　[1]Chen L , André Langevin. Multiple yard cranes scheduling for loading operations in a container terminal[J]. Engineering Optimization, 2011, 43(11):1205-1221.

　　[2]He J , Huang Y , Yan W . Yard crane scheduling in a container terminal for the trade-off between efficiency and energy consumption[J]. Advanced Engineering Informatics, 2015, 29(1):59-75.

　　[3] 初良勇,阮志毅,李淑娟.基于遗传算法的港口集装箱堆场场桥智能调度优化[J].中国航海,2018,41(01):48-52.

　　[4] 初良勇,李淑娟,阮志毅.多箱区多场桥调度优化模型及算法实现[J].上海海事大学学报,2017,38(01):37-42.

　　[5] Liang C J , Chen M , Gen M , et al. A multi-objective genetic algorithm for yard crane scheduling problem with multiple work lines[J]. Journal of Intelligent Manufacturing, 2014, 25(5):1013-1024.