基于作业均衡的集装箱码头岸桥作业调度优化

乐美龙，徐根龙，文洪蕊

(上海海事大学 物流研究中心，上海 201306)

基于作业均衡的集装箱码头岸桥作业调度优化

乐美龙，徐根龙，文洪蕊

(上海海事大学 物流研究中心，上海 201306)

为了提高集装箱码头资源配置的均衡性，进而提高作业人员任务分配的均衡性以及岸桥设备资源的利用率，提出了基于集装箱码头岸桥作业均衡调度优化问题。以集装箱码头岸桥作业集装箱量和作业时间两个均衡调度为目标，建立集装箱码头岸桥作业均衡的岸桥调度优化模型，并设计遗传算法来求解。通过对3种目标的结果进行比较，得出在岸桥调度过程中考虑岸桥作业量均衡有助于提高岸桥的利用率，减少岸桥无效作业时间，从而提升码头整体作业能力。

交通运输工程；集装箱码头；作业均衡；岸桥；调度优化；遗传算法

0 引 言

随着经济全球化进程加快，集装箱码头在国际物流和国民经济中的战略性地位越来越突出，成为了国际物流多式联运中不可或缺的重要节点。岸桥，作为码头前沿岸边的装卸设备，由于其设备昂贵且较为稀缺，其装卸作业能力直接决定了集装箱货物的吞吐能力以及码头整体作业能力。

近年来，国内外众多学者针对岸桥调度展开深入研究：C．F．DAGANZO[1]假设岸桥可以自由移动，以船舱为任务单位，研究了多艘船舶岸桥调度问题；K．H．KIM等[2]在考虑岸桥间的安全距离以及任务的优先作业顺序等因素下，建立了一个混合整数规划模型，并采用分支界定方法进行求解；P．LEGATO等[3]在岸桥调度模型考虑了单个岸桥的平均作业速率、准备时间和岸桥的交货期、安全需求等因素；S．H．CHUNG等[4]基于任务优先级和岸桥互不干涉因素情况下建立模型，并采用改进型遗传算法进行求解。在岸桥任务重新分配过程中，S．H．CHUNG等[5]提出了在考虑岸桥不同加载条件下工作量平衡分配问题，建立模糊理论控制引导下的数学模型；曾庆成等[6]在岸桥调度模型充分考虑船舶任务优先顺序、岸桥作业的安全距离以及岸桥的转移时间等因素；周鹏飞等[7]针对船舶抵港时间随机性，建立了面向随机环境的泊位-岸桥调度模型；曾庆成等[8]在泊位分配-装卸桥调度中运用干扰管理方法，从船舶等待成本、码头作业成本、以及计划偏离度等3个方面度量扰动；范志强等[9]考虑了岸桥作业不可相互交叉以及安全距离等约束，建立了岸桥调度双目标混合整数规划模型；此外，范志强[10]还分析了以箱组为任务对象QCSP 与以整贝为任务对象QCSP 的异同，指出前者更能均衡各岸桥作业负荷；徐远琴等[11]分析了集装箱码头中的集卡与岸桥、场桥联合调度问题，建立了以等待岸桥、场桥作业时间与集卡运输时间之和最小为目标的联合调度优化模型；高超锋等[12]研究了多个岸桥并行作业中相互干扰而影响岸桥工作效率问题，分析了岸桥工时和惩罚成本的影响。

从以上学者的研究中可见，岸桥调度中主要以船舶在港时间最小化或岸桥作业时间最小化为目标，这求解过程中往往会导致岸桥作业任务分配不均衡的现象。基于此，笔者重点探讨基于岸桥作业量的均衡岸桥调度优化问题，提出了一个以岸桥作业量均衡以及作业时间最小化为目标的多目标岸桥调度问题，并设计遗传算法进行求解。通过具体算例来验证该调度模型对实际中的集装箱码头设备资源调度均衡性的效果与优势。

1 问题描述

岸桥调度(QCSP)是指在确定船舶靠泊位置和分配岸桥数量后，在考虑每台岸桥的作业任务量、开始作业时间、结束作业时间、各个任务间的作业次序等信息对所服务船舶上的任务安排特定岸桥进行装卸服务，以确保船舶任务能够在规定的时间内完成。

笔者主要研究基于单船任务分配量均衡的岸桥调度优化问题。如图1，所需要作业的集装箱分布在船舶的不同贝位上。由于在港时间的长短往往取决于船舶最后一个集装箱装卸完工的时间长短，为了使船舶在港时间尽可能的短，必须遵循多台岸桥并行作业、船舶任务分配均衡性的原则，使得服务于同一艘船舶的所有岸桥完工时间尽可能地接近或相等，这样在保证船舶在最短时间内完成所有的装卸任务的同时，可以避免或减少岸桥设备资源闲置或浪费的现象。

图1 岸桥调度问题概述Fig.1 QC scheduling problem

国内集装箱码头中，岸桥通常为轨道式岸桥，受电缆坑和电缆长度的限制，每台岸桥必须在固定的轨道上进行移动和作业，不可交叉跨越，且相邻岸桥在作业过程中要相隔至少一个贝位的安全距离。如图1中，当岸桥2和岸桥3同时在贝位上作业时，岸桥2作业的贝位号必须要比岸桥3所作业的贝位号大，否则将导致岸桥交叉作业。

2 模型建立

2.1 模型假设

笔者在得到一天(24 h)的所有船舶的岸桥和泊位分配计划表后，针对单艘船舶建立一个混合整数规划模型，并期望在完成所有装卸作业任务后，实现每台岸桥作业量均衡。对模型假设如下：

1)岸桥的装卸速度相同，即不同的岸桥作业同一个任务所需的作业时间相同；

2)一台岸桥一次只能作业一个贝位上的任务，并且岸桥在作业中不会发生突然故障；

3)为了使多目标单位的统一性，笔者将所考虑的岸桥作业量转化为岸桥的作业时间。

2.2 参数定义

参数具体符号定义如下：

2.3 决策变量

为建立岸桥调度数学模型引入决策变量如下：

2.4 数学模型

在对参数和决策变量的定义后，笔者基于岸桥作业量均衡情况下建立了岸桥多目标混合整数规划模型。

目标函数：

(1)

(2)

(3)

约束条件：

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

ci+Tj≤cj, ∀i,j∈φ

(13)

(14)

(15)

(16)

Zij+Zji=1,ifdQ<1, ∀i,j∈φ

(17)

(18)

∀i,j∈Ω,li

(19)

(20)

(21)

Tk,ci≥0, ∀i∈Ω,∀k∈Q

(22)

(23)

3 遗传算法求解

基于建立的混合整数规划模型，笔者将通过设计遗传算法分别以岸桥作业完成时间最小化、以作业量最均衡、作业量最均衡且作业完成时间最小化为目标进行岸桥调度优化，并对3种目标所生成的调度方案进行比较，以验证模型可行性。

3.1 染色体的设计及初始解的生成

染色体设计方法采用交互式的编码方式(图2)：假设有2台岸桥，10个作业任务。在每台岸桥上，每条染色体代表岸桥所分配作业任务顺序的一个可能方案，包含两个数量的基因值以及两部分不同的编码体系。在第1部分中，每个基因表示一个任务，基因的序列表示任务从左往右进行作业的顺序，基因值随机产生，而且不会被其他基因复制；在第2部分，每个基因表示对应于第1部分相应位置所作业的岸桥，其基因值基于所作业的岸桥数量随机产生。

图2 染色体设计Fig.2 Chromosome design

由图2可以知道，岸桥1分配了5个任务，其作业顺序依次为6，9，2，8和1；岸桥2所分配任务的作业顺序为4，7，10，3，5。这样在所提到的遗传算法中，随机生成了初始解。

3.2 适应度函数的计算及选择操作

目标函数是基于岸桥作业量均衡的情况下最小化任务的最大完工时间。鉴于该模型是一个多目标混合整数规划模型，因此在求解过程中采用帕累托[13]最优解的方法通过引入加权系数来将多目标函数标准化为一个单目标函数，以此来表示染色体的适应度函数。

g=1,2

(24)

(25)

适应度函数的权重设置如式(26)：

(26)

染色体适应度函数计算为

F(ak)=ω1·f1+ω2·f2

(27)

同时，在选择操作上，采纳轮盘赌的方法进行选择操作。

3.3 遗传运算

遗传运算主要包括交叉(crossover)操作和变异(mutation)操作两个部分，这是实现遗传算法的精髓，也是变化最多的地方。

3.3.1 交叉操作

笔者根据M．GEN等[14]所提到有序交叉法来处理所需作业的任务序列，具体的交叉步骤如下：

第1步：在第一父代的第1部分随机选择部分染色体，与此同时在该父代的第2部分的对应位置选择相应染色体。

第2步：将该染色体拷贝，然后放入子代所对应位置。

第3步：删除来自于第二父代所存在的与子代相同的基因(如本例中删除父代2的相应与子代1重复的7，10，2，3)，剩余的基因根据第二父代从左到右的作业顺序放入到子代空缺的位置。

第四步：重复1～3的步骤来复制第二个子代。

图3用一个例子演示了顺序交叉的做法。

3.3.2 变异操作

变异的目的是防止种群被局限于局部最优，笔者使用的变异方法是随机选择两个元素然后交换它们的位置，具体以图4为例。

图4 变异操作的说明Fig.4 Variation operation instruction

3.4 算例实验及结果分析

为了验证上述模型及算法的有效性，笔者以一艘小规模的集装箱船舶装卸操作为例对岸桥进行调度研究。遗传算法参数如表1。

表1 遗传算法参数设置

3.4.1 数据输入

假设一艘小规模集装箱船舶靠岸，船舶上共有9个贝位需要进行集装箱装卸操作，各贝位的集装箱量以及贝位间任务优先级等具体信息如表2。

表2 已知的任务信息

现分配3台岸桥至该船舶，3台岸桥的最早可用时间均为0时刻，并且各岸桥的单机作业效率相同。已知岸桥在单个贝位的移动时间t=0.004 h，岸桥1的初始位置在贝位16，岸桥2初始位置在贝位12，岸桥3的初始位置在贝位10，岸桥首个任务距离信息以及两两任务距离信息如表3及表4。

表3 岸桥首个任务距离

注：单位距离为一个贝位距离。

表4 两两任务距离

(续表4)

dij123456789105543201234466543101233776542101228876532101199876432100109876432100

注：单位距离为一个贝位距离。

3.4.2 岸桥调度模型结果与分析

根据3.2小节所提出的权系数处理方法，对于以作业量最均衡以及作业量最均衡且作业完成时间最小化为目标的多目标优化。根据式(26)使用MATLAB得到两个权系数为：ω1=0.24，ω2=0.86。由算例2的信息数据并考虑岸桥移动情况，分别以岸桥作业完成时间最小化和以作业量最均衡以及作业量最均衡且作业完成时间最小化为目标进行岸桥调度优化，3种不同目标所生成的调度方案及各岸桥具体作业情况如表5。

表5 不同目标下生成的调度方案及岸桥作业结果

(续表5)

方案目标岸桥作业顺序作业时间Tk/h等待时间Tw/h移动时间tk/h完工时间Ck/h3岸桥作业量最均衡&作业完成时间最小化QC-19—8—1010.80.0000.01210.812QC-26—311.64.3840.04016.024QC-37—1—4—5—212.01.5400.08413.624

分别对3种目标所生成的调度方案的岸桥作业完成时间和岸桥作业时间进行比较，如图5。

图5 不同目标下各岸桥作业完成时间及作业时间Fig.5 QC operation time and completion time with different targets

在以作业完成时间最小化为目标的调度方案中，3台岸桥的最大完工时间为12.84 h，各岸桥间作业完成时间的标准差仅为0.998 h，波动性较小。同时从图5(a)可见，岸桥在等待和移动时间浪费上比较少。但从图5(b)可见，相比其他两种目标的方案，岸桥作业时间却参差不齐，由于各岸桥间作业量分配不均衡导致任务最大完工时间增加；在以作业量最均衡为目标的调度方案中，岸桥作业时间标准差为0.189 h，3台岸桥间作业量分配趋于一致，但由于各岸桥作业完成时间的波动性较大最终导致任务最大完工时间增加，为18.12 h。而且从图6可以看出各岸桥间移动、等待时间相差较大，特别是岸桥2和岸桥3在作业过程中等待时间分别长达4.84和6.46 h，岸桥在无效作业时间上浪费较大；在以作业完成时间最小化和作业量最均衡多目标的调度方案中，岸桥间最大完工时间为16.024 h，岸桥作业标准差为0.499 h，在两个目标之间寻求一定的平衡点，一定程度上减少了岸桥无效作业时间，有效提高了岸桥的作业效率。

图6 不同目标下各岸桥移动等待时间Fig.6 QC moving and waiting time with different targets

此外，从图5中数据可以得到该多目标方案的作业完成时间比以作业量最均衡为目标的调度方案结果减少了近11.57%，岸桥的作业时间标准差比以作业完成时间最小化为目标的调度方案结果减少了近33.8%。因此，在岸桥调度中考虑岸桥的作业均衡性是有必要的,从长远的角度来看，极大地提高了岸桥资源的整体利用率，减少了岸桥无效作业时间，从而提升码头整体作业能力。

4 结 语

笔者研究了基于贝位任务岸桥单船调度优化问题，建立一个基于岸桥作业均衡的船舶完工时间最小化的多目标混合整数规划问题，并设计遗传算法进行求解。鉴于该两个目标已统一为相同的单位量纲，因此通过设定相应权重ω1，ω2将多目标问题转化为单目标线性问题。并通过实例分别对以岸桥作业完成时间最小化为目标、作业量最均衡为目标、作业量最均衡且作业完成时间最小化为目标的3种目标结果进行比较分析，得出在岸桥调度过程中，考虑岸桥作业量均衡有助于提高岸桥的利用率，减少岸桥无效作业时间，从而有效缩短船舶在港时间，降低码头经营运作成本，提高港口的整体运作效率和服务水平。但在集装箱码头调度问题中，基于单船的岸桥调度并不能保证码头作业整体的优化，因此下一步将对岸桥、集卡、场桥联合调度优化问题展开深入研究。

[1] DAGANZO C F. The crane scheduling problem[J].TransportationResearchPartB:Methodological,1989,23(3):159-175.

[2] KIM K H,PARK Y M. A crane scheduling method for port container terminals[J].EuropeanJournalofOperationalResearch,2004,156:752-768.

[3] LEGATO P,TRUNFIO R,MEISEL F. Modeling and solving rich quay crane scheduling problems[J].Computers&OperationsResearch,2012,39(9):2063-2078.

[4] CHUNG S H，CHOY K L. A modified genetic algorithm for quay crane scheduling operations[J].ExpertSystemswithApplications,2012,39(4):4213-4221.

[5] CHUNG S H,CHAN F T S. A workload balancing genetic algorithm for the quay crane scheduling problem[J].InternationalJournalofProductionResearch,2013,51(16)：4820-4834.

[6] 曾庆成，高宇．集装箱码头装卸桥调度优化模型与算法[J]．计算机工程与应用，2006(32):217-219． ZENG Qingcheng,GAO Yu. Model and algorithm for quay crane scheduling in container terminals[J].ComputerEngineeringandApplications,2006(32):217-219.

[7] 周鹏飞，康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践，2008，28(1):161-169. ZHOU Pengfei，KANG Haigui. Study on berth and quay-crane allocation under stochastic environments in container terminal[J].SystemsEngineeringTheory&Practice,2008,28(1):161-169.

[8] 曾庆成，胡祥培，杨忠振．集装箱码头泊位分配-装卸桥调度干扰管理模型[J]．系统工程理论与实践，2010，30(11):2026-2035. ZENG Qingcheng,HU Xiangpei,YANG Zhongzhen. Model for disruption management of berth allocation & quay crane scheduling in container terminals[J].SystemsEngineeringTheory&Practice,2010,30(11):2026-2035.

[9] 范志强，乐美龙．最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法[J]．系统管理学报，2013，22(1):120-127. FAN Zhiqiang,LE Meilong. A genetic algorithm to minimize the makespan and waiting time for the bi-objective quay crane scheduling problem[J].JournalofSystems&Management,2013,22(1):120-127.

[10] 范志强．考虑任务优先约束的同类岸桥作业调度优化[J]．运筹与管理，2013，22(2):235-242. FAN Zhiqiang. Modeling and solving uniform quay crane scheduling problem with task precedence constraints[J].OperationsResearchandManagementScience,2013,22(2):235-242.

[11] 徐远琴，韩晓龙．集卡与岸桥及场桥联合调度模型优化[J]．重庆交通大学学报(自然科学版)，2013，32(2):318-320. XU Yuanqin,HAN Xiaolong. United scheduling model optimization of yard truck,quay crane and yard crane[J].JournalofChongqingJiaotongUniversity(NaturalScience),2013,32(2):318-320.

[12] 高超锋，胡志华.岸桥并行作业效率约束下泊位与岸桥集成分派[J].重庆交通大学学报(自然科学版)，2014，33(3):72-78. GAO Chaofeng,HU Zhihua. Berth-crane allocation constrained by parallel operation efficiency of quay cranes[J].JournalofChongqingJiaotongUniversity(NaturalScience),2014,33(3):72-78.

[13] 王昕昕.岸边集装箱起重机动态配置与贝位调度多目标问题研究[D].上海:上海海事大学，2014. WANG Xinxin.DynamicMulti-ObjectiveResearchonQCsSchedulingasedontheBayTask[D]. Shanghai:Shanghai Maritime University，2014.

[14] GEN M,CHENG R.GeneticAlgorithmsandEngineeringOptimization[M]. New York:John Wiley,1996.

Quay Crane Scheduling Optimization Considering Operation Balance at Container Terminal

LE Meilong, XU Genlong, WEN Hongrui

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306, P.R.China)

In order to improve the balance of resources allocation at container terminal, and then to improve the balance of the operators’ assigned tasks and the utilization rate of the quay crane resources, a quay crane allocation optimization problem, considering operation balance between quay cranes at container terminal, was proposed. A quay crane scheduling optimization model based on the quay crane operation balance at container terminal was established, in order to balance the quantities of the containers and the operational time of quay crane operation. And a genetic algorithm was designed to solve the model. By comparing the results of three different goals, it is concluded that considering the operation balance in the quay crane scheduling process is helpful to improve the utilization rate of quay crane and reduce the quay crane invalid operation time, so as to improve the whole operation capability of the container terminal.

traffic and transportation engineering; container terminal; operation balance; quay crane; scheduling optimization; genetic algorithm

10.3969/j.issn.1674-0696.2016.03.31

2015-12-24；

2015-03-14

国家自然科学基金项目(71171129，71471110)；上海市科委科研计划项目(111510501900，12dz1124802)；上海市教委科研项目(11YZ137))

乐美龙(1968—)，男，浙江宁波人，教授，博士，博士生导师，主要从事物流规划与管理，港航运作优化方面的研究。E-mail：lemeilong@126.com。

徐根龙(1989—)，男，浙江江山人，硕士研究生，主要从事岸桥调度优化方面的研究。E-mail：croger4463@163.com。

U691+3

A

1674-0696(2016)03-155-07