考虑作业状态能耗的集装箱码头设备协调调度

代江涛，韩晓龙

上海海事大学 物流科学与工程研究院，上海 201306

交通运输产生的大量二氧化碳是全球环境的重大威胁，交通运输的能源消耗问题需要妥善处理。集装箱码头作为航运与陆运交通的枢纽，是交通产业的重要构成部分，降低集装箱码头能源消耗，推进建设绿色港口正逐渐得到重视。集装箱码头的装卸设备主要包括：岸桥（QC）、场桥（YC）、集卡（IT）。由于集装箱码头的各作业环节相互耦合，实现各设备的协调调度对于提高集装箱码头的服务水平以及降低其能源消耗尤其重要。

当前国内外对于集装箱码头各设备的调度问题已有较多研究。关于两种设备的调度问题，Cao 等[1]研究进口集装箱作业中集卡与QC的调度，构建了混合整数规划模型，并且用遗传算法和基于约翰逊规则的启发式算法进行求解，求解的精度得到提高；韩晓龙等[2]考虑集卡的动态性到达以及作业时间的不确定性，构建集卡与QC的协同调度模型，并且使用CHC算法（Cross generation Heterogeneous recombination Cataclysmic mutation，跨时代异物种重组大变异算法）进行求解；梁承姬等[3]考虑集装箱优先级及岸桥干扰等约束，构建以最小化最大完工时间为目标的数学模型，对比粒子群算法和遗传算法后得到遗传算法更具有效性的结论；卢毅勤等[4]考虑了YC和内集卡作业时的不确定性因素，建立堆场设备集成调度的优化模型，并设计了粒子群算法进行求解；杨勇生等[5]考虑了RMG（Rail Mounted Gantry，轨道式龙门吊）和AGV的任务分配约束，并以最小化卸船作业完工时间为目标建立了RMG和AGV的协同调度模型；梁承姬等[6]针对AGV和双小车岸桥的协同调度问题，设计了启发式算法和遗传算法求解所建立的以总完工时间最小为目标的混合整数规划模型；陈宁等[7]使用基于混合流水车间调度的方法解决AGV与双小车岸桥的联合调度，建立以作业时间最小为目标的三阶段混合整数规划模型并使用遗传算法求解；唐世科等[8]建立了带有时间窗约束的AGV与双小车岸桥的以总完工时间最小为目标的协调调度模型，并使用遗传算法求解；关于三种及以上设备的协调调度，曾庆成等[9]构建了QC、集卡以及龙门吊的集成调度模型，并设计了神经网络算法和模拟退火算法为基础的混合优化算法进行求解；Homayouni 等[10]使用遗传算法对自动化集装箱码头协同调度问题进行求解，比较模拟退火算法得出集装箱任务增加时，遗传算法的求解效率比模拟退火算法更优；吴远焰等[11]设计了一种改进的遗传算法解决自动化码头中三种核心设备的调度问题，通过不同规模的数值仿真以及与CPLEX求解结果的对比证明其所设计的遗传算法可以找到高质量的近似最优解；Lau 等[12]以最小化AGV的总行程时间、QC的操作延迟时间和自动化场桥（AYC）的总行程时间为目标构建了混合整数规划模型，并采用多层遗传算法和遗传最大匹配算法进行求解；栾晨等[13]抽象双循环模式下的QC、AGV 和YC 协调调度问题为混合整数规划模型，并使用基于启发式的自适应遗传算法求解；Yang等[14]针对QC、AGV和YC的集成调度问题，设计了一种基于预防性拥塞规则的通用算法进行求解；马越汇等[15]综合考虑自动化集装箱码头的各种不确定性因素，构建了以最小化QC、AGV、龙门吊和堆场作业最晚结束时间为目标的模型；秦琴等[16]基于缓冲有限的柔性流水车间调度理论解决双小车岸桥、AGV、缓冲支架和自动化轨道吊的协调调度问题，建立优化模型并设计初始解由NEH启发式算法产生的遗传算法进行求解。

以上关于集装箱码头各设备协调调度的研究仅从时间角度考虑调度的优化，而实际作业过程中能耗因素也是影响作业调度的一大重要因素。

集装箱码头在各设备能耗方面的研究相对较少，He等[17]集成粒子群优化算法（PSO）以及遗传算法，并使用仿真优化方法实现了最小化所有船舶的总出发延误以及全部任务的总能耗最小的目标；He等[18]转化YC调度问题为具有软时间窗（VRPSTW）的车辆路径问题，构建了最小化总任务完成时间以及YC总能耗的双目标混合整数规划模型，并使用融合粒子群算法和遗传算法的优化算法进行求解；范厚明等[19]在AGV 与双小车岸桥的调度问题中，考虑双小车岸桥中转平台的容量、AGV的续航时间以及堆场缓冲支架容量的约束建立了两阶段优化模型，并使用枚举法和改进遗传算法求解；严南南等[20]考虑集卡的能耗并构建集卡和QC协调调度的双目标模型，并用遗传算法进行求解；郭婵婵等[21]结合混合流水车间的思想，以最小化装卸设备总作业时间和机械能耗为目标构建了包含QC、YC和集卡的双目标集成调度优化模型，并且采用基于遗传算法和模拟退火算法的混合算法进行求解。艾立红等[22]考虑作业过程中QC、YC 的平均能耗以及AGV 的不同作业状态下的能耗，以最小化总作业时间和总作业能耗为目标建立了多目标混合整数规划模型，并使用遗传算法求解；Yang等[23]以最小化能耗和最小化总作业时间为目标，基于混合流水车间调度问题构建并求解了QC、内集卡和YC的双目标优化模型。

现有集装箱码头设备协调调度的能耗相关研究中，针对装卸作业过程产生的能耗仅考虑了集卡的不同作业状态下的能耗不同，却没有考虑作业过程中岸桥和场桥在不同作业状态下的单位时间平均能耗不同，未对岸桥和场桥进行作业状态划分，未考虑岸桥或场桥在作业过程中可能存在等待集卡的情况。本文针对集装箱码头中岸桥、场桥和集卡的调度问题，分析三种设备在作业过程中可能出现的各种作业状态，划分集卡的作业状态为空载行驶状态、负载行驶状态和等待状态；划分岸桥、场桥的作业状态为装卸集装箱状态和等待状态。量化各设备不同作业状态下的不同能耗，建立最小化总完工时间和总作业能耗的多目标混合整数规划模型。使用改进自适应遗传算法求解模型并将结果分别与CPLEX和传统遗传算法的求解结果作对比以验证算法的优秀性，最后改变作业时间目标和能耗目标的权重进行求解以作进一步分析。

1 模型构建

1.1 问题描述

在集装箱码头的装卸作业过程中各设备之间往往会出现衔接不及时的情况，这样会造成各设备出现等待情况。如卸船作业过程中若集卡不能及时到达指定岸桥处则岸桥需要等待集卡，相反若集卡到达岸桥处时岸桥还未准备好开始任务则集卡需要等待岸桥。

本文综合分析装卸作业过程中各设备可能出现的作业状态，量化各设备不同作业状态下的作业时间，以计算各设备不同作业状态下的能耗。本文使用权重系数法给时间目标和能耗目标分配权重，总目标为实现装卸作业的总完工时间最小以及总作业能耗最小。

模型假设：（1）不考虑岸桥和场桥翻箱；（2）场桥在计划期间仅服务内部的集卡；（3）集卡的路径规划不作考虑。

1.2 符号定义

1.2.1 模型参数

Q表示岸桥集合，q∈Q；

Y表示场桥集合，y∈Y；

V表示集卡集合，v∈V；

J表示集装箱任务集合，J1表示进口箱任务集合，J0表示出口箱任务集合，J1⋃J0=J；

θu、θl、θw分别表示集卡处于空载行驶状态、负载行驶状态及等待状态时的单位时间平均能耗（unit/s）；

αl、αw分别表示岸桥处于装卸集装箱状态及等待状态时的单位时间平均能耗（unit/s）；

βl、βw分别表示场桥处于装卸集装箱状态及等待状态时的单位时间平均能耗（unit/s）；

tvii′表示集卡v从任务i的终点移动至任务i′的起点所用时间；

tqii′表示任务i和i′都由岸桥q作业时岸桥q从任务i的终点移动到任务i′的起点所用时间；

tyii′表示任务i和i′位于同一箱区且都由场桥y作业时场桥y从任务i的终点移动到任务i′的起点所用时间；

δ表示岸桥作业一个集装箱所用时间；

ε表示场桥作业一个集装箱所用时间；

Tvi表示集卡v作业任务i时从任务i的起始节点行进到其终点所用时间；

M表示一个足够大的正数；

φi∈{0 ,1}，φi=1 表示进口箱任务，否则表示出口箱任务。

1.2.2 辅助决策变量

sqi、tqi分别表示岸桥q作业任务i的开始时刻与结束时刻；

syi、tyi分别表示场桥y作业任务i的开始时刻与结束时刻；

svi、tvi分别表示集卡v作业任务i的开始时刻与结束时刻。

各设备作业任务i的开始时刻与结束时刻定义为：svi为集卡v到达任务i起始节点时刻，tvi为集卡v完成任务i的集装箱交接时刻；任务i为进口箱任务时，sqi为岸桥q在船舶上的提箱时刻，tqi为岸桥q与集卡交接的时刻，syi为场桥y就绪与集卡交接集装箱的时刻，tyi为场桥y完成集装箱装卸的时刻；任务i为出口箱任务时，sqi为岸桥q就绪与集卡交接集装箱的时刻，tqi为岸桥q完成集装箱装卸的时刻，syi为场桥y在堆场的提箱时刻，tyi为场桥y与集卡的交接时刻。

1.2.3 决策变量

γqvi表示在作业任务i时集卡v到达岸桥q处的时刻；

ηyvi表示在作业任务i时集卡v到达场桥y处的时刻；

∂qvi表示在作业任务i时岸桥q等待集卡v所用的时间；

ψyvi表示在作业任务i时场桥y等待集卡v所用的时间

；表示在作业任务i时集卡v等待场桥y所用的时间；

avii′∈{0 ,1}，任务i和i′都由同一集卡v作业并且i于i′前完成则avii′=1，否则avii′=0；

bqii′∈{0 ,1}，任务i和i′都由同一岸桥q作业并且i于i′前完成则bqii′=1，否则bqii′=0；

cyii′∈{0 ,1}，任务i和i′都由同一场桥y作业并且i于i′前完成则cyii′=1，否则cyii′=0；

kvi′∈{0 ,1}，任务i′为集卡v的开始任务则kvi′=1，否则kvi′=0；

pvi∈{0 ,1}，任务i为集卡v的结束任务则pvi=1，否则pvi=0；

kqi′∈{0 ,1}，任务i′为岸桥q的开始任务则kqi′=1，否则kqi′=0；

pqi∈{0 ,1}，任务i为岸桥q的结束任务则pqi=1，否则pqi=0；

kyi′∈{0 ,1}，任务i′为场桥y的开始任务则kyi′=1，否则kyi′=0；

pyi∈{0 ,1}，任务i为场桥y的结束任务则pyi=1，否则pyi=0。

1.3 能耗模型

式（1）和（2）分别为考虑装卸集装箱状态及等待状态能耗的岸桥、场桥在整个作业过程中的总能耗；式（3）为集卡在任务节点间空载行驶状态产生的能耗、运输集装箱即负载行驶状态产生的能耗及在岸桥侧、场桥侧等待状态下产生的能耗之和，即集卡在整个作业过程中的总能耗。

1.4 数学模型

下述的所有表达式中除在式中特别标注外，∀i,i′∈J,i≠i′，v∈V，q∈Q，y∈Y。

式（4）为目标函数之一，目标为使岸桥、场桥、集卡装卸作业总完工时间最小；式（5）为另一个目标函数，目标为使各设备的总能耗最小。

式（6）～（11）表示岸桥、场桥、集卡作业集装箱任务时，每个任务仅能被作业一次。

式（12）和（13）表示岸桥、场桥、集卡开始作业或者结束作业一次并且仅一次。

式（14）～（16）表示岸桥、场桥、集卡作业任务i的开始时刻与结束时刻的关系，岸桥、场桥结束作业时刻应不早于开始作业时刻与装卸一个集装箱所需时间之和，集卡结束作业时刻应不早于开始作业时刻与其在任务节点间运输集装箱时间之和。

式（17）表示当集卡v结束作业任务i后继续作业任务i′，并且i′为出口箱任务时集卡v到达场桥y处的时刻应不早于集卡v结束作业任务i的时刻与集卡v在任务节点i和i′间移动所用的时间之和；式（18）表示当集卡v完成任务i后继续作业任务i′，并且i′是进口箱任务时集卡v到达岸桥q处时刻应不早于集卡v结束作业任务i时刻与集卡v在任务i和i′间移动所用的时间之和。

式（19）表示任务i为进口箱任务时集卡v到达场桥y处时刻应不早于岸桥q结束任务i时刻与集卡v在任务i的开始节点与结束节点之间的行驶时间之和；式（20）表示任务i为出口箱任务时集卡v到达岸桥q处时刻应不早于场桥y结束任务i时刻与集卡v在任务i的开始节点与结束节点之间的行驶时间之和。

式（21）表示当任务i和i′都由岸桥q作业，且岸桥q结束作业i后紧接着作业i′时，岸桥q开始作业i′的时刻应不早于其结束作业i的时刻与其在任务节点i和i′间的移动时间之和；式（22）表示当任务i和i′都位于同一箱区且都由场桥y作业，且场桥y结束作业i后紧接着作业i′时，场桥y开始作业i′的时刻应不早于其结束作业i的时刻与其在任务节点i和i′间的移动时间之和。

式（23）～（26）表示任务i为进口箱任务时各设备等待时间的约束，岸桥q等待集卡v的时间应该不小于集卡v到达岸桥q处时刻与岸桥q就绪交接集装箱的时刻之差，场桥y等待集卡v的时间应该不小于集卡v到达场桥y处时刻与场桥y作业任务i的开始时刻之差，集卡v等待岸桥q的时间应该不小于岸桥q就绪交接集装箱的时刻与集卡v到达岸桥q处时刻之差，集卡v等待场桥y的时间应该不小于场桥y作业任务i的开始时刻与集卡v到达场桥y处时刻之差；式（27）～（30）表示任务i为出口箱任务时各设备等待时间的约束。

式（31）～（33）表示各决策变量的约束。

2 算法设计

本文所建模型的求解计算难度比较大，属于NP 难问题。针对研究问题和所建模型的特点，遗传算法较适合于本文的求解。遗传算法的迭代过程中染色体变异的概率Pm和染色体交叉的概率Pc对求解结果有较大影响，若二者过大则容易在迭代初期破坏适应度高的染色体个体；若二者过小则在迭代后期不易产生新个体，使得算法陷入局部最优解，造成早熟。针对这一问题本文采用改进自适应遗传算法进行求解，其中关于Pm和Pc的改进主要由以下调整公式体现：

式（34）和（35）中，fmax表示种群个体的最大适应度值；favg表示种群个体的平均适应度值；f′表示进行交叉操作的两个个体中的较大适应度值；f表示进行变异操作的个体的适应度值；Pc1表示最大交叉概率，设置为Pc1=0.9；Pc2表示最小交叉概率，设置为Pc2=0.6；Pm1表示最大变异概率，设置为Pm1=0.1；Pm2表示最小变异概率，设置为Pm2=0.01。

算法流程如图1所示。

图1 算法流程图Fig.1 Algorithm flow chart

2.1 染色体编码

本文使用双层实数编码方法，如图2所示。染色体由两层组成：第一层为集装箱编号（数字顺序即为作业顺序），第二层为分配给该集装箱任务的IT编号。假设10 个集装箱任务有1 台QC、3 台YC 和6 辆IT 作业。已知YC 的作业计划：YC1 于堆场1 作业集装箱1、3、8；YC2于堆场2作业集装箱2、4、5；YC3于堆场3作业集装箱6、7、9、10。则各装卸设备的作业顺序为：QC：5→3→7→6→1→9→8→10→2→4；YC1：3→1→8；YC2：5→2→4；YC3：7→6→9→10；IT1：5→10；IT2：6→2；IT3：8→4；IT4：3→1；IT5：9；IT6：7。

图2 染色体编码示例Fig.2 Chromosome coding example

2.2 种群初始化

通过随机生成来确保种群具有多样性：第一层为集装箱编号的随机序列（permutation），第二层中每个基因为IT编号的随机抽样，如图3所示。

图3 种群初始化染色体示例Fig.3 Chromosome example of initial population

2.3 适应度函数

本文采取权重系数法给各目标分配权重以将多目标规划问题转化成单目标规划问题，设置目标函数f1的权重系数为x，则f2的权重系数为1-x。因为目标为求最小值，所以适应度函数为：

2.4 遗传操作

2.4.1 选择

使用随机通用采样（Stochastic Universal Sampling）方法来选择父代个体，此方法通过随机选择一次即可选定N个父代个体。首先依据个体的适应度值求出各个体的被选概率，接着求出各个体被选的期望个数，然后构造出一个轮盘，转动一次轮盘，N条指针所指个体被选作父体进行次代演化。

2.4.2 交叉

分别在两个父代染色体随机选择两个相同位置的基因，并将其中间部分作为交叉部分，如图4 所示。交叉所得子代染色体中可能会存在集装箱编号缺失或重复的情况，故要进行子代染色体修补操作：逐个检测子代染色体的基因，删除重复的集装箱编号并补充为所缺失的编号随机值，如图5所示。

图4 染色体交叉Fig.4 Chromosome cross

图5 修补所得子代染色体Fig.5 Progeny chromosome after repaired

2.4.3 变异

随机选择某一染色体的某一基因，依据变异因子判断是否变异。进行变异操作时若变异染色体的第一行则变异后还需修补，而修补前后该基因的编号相同，故变异染色体第一行没有意义，只需变异染色体第二行。变异方式为将该染色体第二行某一基因的值替换为不同于原值的IT编号的随机抽样值，如图6所示。

图6 染色体变异Fig.6 Chromosome variation

3 案例分析

3.1 参数设置

假设有1艘船舶，集装箱码头有2台QC、6台YC及12辆IT，所需作业的集装箱数根据算例设置，各QC、YC所需作业的集装箱任务已知，各设备的作业顺序以及各集装箱的作业IT由算法随机生成。集装箱码头各设备的参数设定如表1，通常各装卸设备作业时间以s 为单位，但是为了计算方便表中各设备的能耗参数单位使用unit/min。

表1 参数设置Table 1 Parameter settings

本文使用MATLAB编码算法求解以检验模型和算法的有效性。算法的相关设置为：种群规模为100，最大迭代次数为200，最大交叉概率为0.9，最小交叉概率为0.6，最大变异概率为0.1，最小变异概率为0.01。

3.2 算法性能分析

设置5组规模不同的算例评估算法的性能，当不考虑能耗即x=1 时的CPLEX 和算法的求解结果如表2，其中算法求解结果为10 次运行结果的平均值，误差为算法所求比较于CPLEX 所求的f1和f2的误差平均值的绝对值。如图7 为集装箱数为50 时的一次算法求解结果，算法在迭代118次时收敛，由于未考虑能耗目标，故最优解为最小总完工时间，为5 813 s。

图7 规模为50及时间权重为1的一次算法收敛图Fig.7 One algorithm convergence diagram of 50 containers while x=1

表2 CPLEX与算法求解结果对比Table 2 Results comparison of CPLEX and the algorithm

由表2可知，集装箱数为20、50、80时遗传算法的求解结果与CPLEX 的求解结果误差较小，在可接受范围内，可知遗传算法具有有效性。而当集装箱数上升至100 时CPLEX 的求解结果不如遗传算法的求解结果优秀，且运行时间较长；当集装箱数达到150 个时CPLEX虽然可以得到可行解，但运行时间远超过遗传算法，求解精度也与遗传算法相差较大。对比可知本文设计的遗传算法比CPLEX 有更高的求解效率，且求解效果较好，求解大规模算例的优势更大。

使用传统遗传算法对模型进行求解并与本文采用的算法求解结果对比，结果如表3所示。

表3 两种算法的求解结果对比Table 3 Results comparison of two algorithms

由表中数据分析可知，相较于传统的遗传算法，本文所采用的算法在求解速度上有一定的优势，且求解效果更好。

3.3 算法结果分析

为研究最小总完工时间和最小总作业能耗与权重系数x的关系，变化x的值进行求解分析，其中x的值人为规定，且以固定值递减。

当设置x为0.88，集装箱数为50 时算法收敛效果如图8。运行10次算法取其平均值，求得最小总完工时间为6 471 s，比不考虑能耗时增长了672 s。而最小总能耗为1 832 unit，比不考虑能耗时减少了115 unit。推测可能由于提高了能耗目标在总目标中的权重，使得为了减少能耗作业顺序发生了改变，导致作业时间增加；此外为了降低能耗作业顺序的改变可能导致集卡在任务节点间空载行驶和负载行驶时的时间减少，但延长了集卡在各任务节点处的等待时间，从而导致总作业能耗降低而总完工时间却延长了。

图8 规模为50及时间权重为0.88的算法收敛图Fig.8 Algorithm convergence diagram of 50 containers while x=0.88

为进一步研究权重系数x对最小总完工时间和最小总作业能耗的影响，设置不同的x值并进行求解。运行算法10次取平均值，求解结果如表4所示。

表4 变化权重系数x 的算法结果Table 4 Results of the algorithm under different x

为更清晰地反映算法求解所得数据的变化情况，将以上数据绘制成折线图，如图9、图10所示。

图9 总完工时间走势图Fig.9 Line chart of operation time

图10 总作业能耗走势图Fig.10 Line chart of energy consumption

表4中的算法结果是全部解集的部分解，由表中数据和图9、图10分析可知当权重系数x的值逐渐减小即能耗目标所占权重逐渐增大时，最小总完工时间逐渐增大，而最小总作业能耗逐渐降低，说明能耗和作业时间是两个相互冲突的目标，即在追求低能耗时可能会牺牲作业效率。所得结果中没有同时使总完工时间和总作业能耗都达到最小的解，决策者应该确定一个合理的权重值，同时兼顾效率和能耗，码头拥堵时为提高作业效率则可以适当降低能耗所占权重，设置较大的x值；码头空闲时为了节约能源则可以适当提高能耗所占权重，设置较小的x值。

4 结论

相较于已有研究，本文进一步考虑了岸桥、场桥在实际作业过程中会出现的两种作业状态，即装卸集装箱状态及等待状态，并且考虑集卡的三种作业状态即负载行驶状态、空载行驶状态及等待状态，在岸桥、场桥和集卡的协调调度问题中量化各设备在不同作业状态下的能耗，建立了考虑作业状态能耗的集装箱码头设备协调调度模型，并使用MATLAB 编码改进自适应遗传算法求得了模型的近似解。从求解结果可知，集装箱码头装卸设备作业时总完工时间与总作业能耗与其在目标函数中的权重有关，能耗所占权重越高则装卸设备的总完工时间越长，但是总作业能耗越小，因此考虑作业状态能耗相较于不考虑能耗时的设备协调调度更贴合集装箱码头实际作业情况，可以帮助决策者更好地权衡作业时间和能耗目标。本文对于多目标规划问题采取权重系数法给各目标函数分配权重以转化为单目标规划问题进行求解，但模型中各目标函数的权重分配对求解结果有较大影响，如何合理分配各目标函数在总目标中的权重是以后需要研究的课题。