单船岸桥分配与调度集成优化模型

单船岸桥分配与调度集成优化模型

作者：郑红星等

来源：《计算机应用》2015年第01期

摘要：针对集装箱码头泊位确定条件下的单船岸桥（QC）分配和调度问题，建立了线性规划模型。模型以船舶在泊作业时间最短为目标，考虑多岸桥作业过程中的干扰等待时间与岸桥间的作业量均衡，并设计了嵌入解空间切割策略的改进蚁群优化（IACO）算法进行模型求解。实验结果表明：与可用岸桥全部投放使用的方法相比，所提模型与算法求得结果平均能够节省31.86%的岸桥资源；IACO算法与Lingo求得的结果相比，船舶在泊作业时间的平均偏差仅为5.23%，但CPU处理时间平均降低了78.7%，表明了所提模型与算法的可行性和有效性。 关键词：岸桥分配和调度；整数线性规划；作业量均衡；干扰等待时间；船舶在泊作业时间；改进蚁群优化算法 中图分类号： F224； TP18 文献标志码：A 0 引言

在集装箱码头中，当待作业船舶靠泊后，该船的岸桥（Quay Crane， QC）分配与调度方案将直接影响船舶的在泊作业时间，这是当前研究集装箱码头的热点问题之一。

针对集装箱码头单船岸桥调度问题，国内外很多学者都对其进行了深入研究。其中Kim等[1]采用分支定界法（Branch and Bound， B&B）和贪婪随机适应性搜索算法（Greedy Randomized Adaptive Search Procedure， GRASP）对单船作业的岸桥调度问题进行了研究，最后验证了GRASP更有效；但是该文献中为船舶分配的岸桥数量最多为3台，有一定的局限性。Moccia等[2]采用B&B对单船岸桥调度问题进行了研究，考虑了集装箱任务的优先级和岸桥作业间互不干涉的约束；但该算法不适合求解大规模实例，适用性较差。Bierwirth等[3]针对文献[1]的不足，建立了岸桥调度整数规划模型并采用启发式算法进行求解；但并未考虑场桥间作业量的均衡此句不完整，请补充或作相应调整。。Nathan[4]也对文献[1]中模型进行了改进并利用遗传算法（Genetic Algorithm， GA）进行求解，创新性地使用新的程序设计来计算决策变量更加严密的上下界。Meisel等[5]提出岸桥调度模型和算法的评估平台，并给出了岸桥调度问题算例的生成方案。Legato等[6]在文献[3]的研究基础上改进了B&B，并考虑了岸桥工作效率的差异，但仅研究了单向岸桥移动问题。乐美龙等[7]考虑任务属性中的优先顺序及不可同时执行的要求，建立单船岸桥调度的混合线性整数规划模型，并将模型简化后利用启发式算法进行求解。Meisel[8]在计划的船舶在泊时间窗口内对岸桥分配问题进行了研究，但并没有考虑实际中超过该时间窗的岸桥分配问题。Legato等[9]采用模拟退火的方法来模拟仿真岸桥调度问题，并把船贝任务的装和卸分开研究，通过实例证明了方法的实用性。Chung等[10]在文献[1]

龙源期刊网 http://www.qikan.com.cn

和文献[2]的基础上进行改进，采用GA求解岸桥调度模型，然后与B&B和禁忌搜索等算法进行对比验证了算法的优越性。Su等[11]首先提出按作业时间的优先级设计作业顺序；然后将局部搜索分别与GA和遗传程序设计（Genetic Programming，GP）结合形成混合遗传算法与混合遗传程序设计。文献[12-13]分别采用启发式算法对连续型泊位和离散型泊位的岸桥调度进行研究。但上述文献[9-13]都只研究岸桥数量固定的情况，并未考虑分配岸桥的数量是否合理。范志强等[14]建立了岸桥作业调度双目标混合整数规划模型，优化目标为最小化最大完工时间和等待时间。Diabat等 [15]则对船舶作业过程中岸桥的配置与调度进行了集成研究，但是文献[1-15]均未涉及到岸桥作业过程中的任务量均衡。

综上，现有文献对单船岸桥调度研究中主要存在以下两个问题：

1）对被选中岸桥分配的任务量均衡问题大多未涉及，而实际情况是当多个岸桥同时作业时，如果各岸桥的任务量分配不均衡，即便对岸桥作业路径优化也不会明显缩短船舶在泊作业时间。

2）在很多文献中都假设岸桥数量固定，而没有考虑岸桥数量是否合理。由于多台岸桥作业时需要保持一定的安全距离，且相互之间不能跨越交叉，因而会出现岸桥等待的状况，最终导致岸桥利用率较低，岸桥资源浪费严重。

针对现有文献的不足，考虑岸桥间的安全距离和不可跨越约束，以及岸桥的负载均衡，对单船岸桥分配与调度进行研究，建立以船舶在泊作业时间最短为目标的整数线性规划数学模型，同时提出改进蚁群优化（Improved Ant Colony Optimization， IACO）算法用于求解模型。 1 问题描述

本文研究的核心问题是：当到港船舶的泊位确定后，为保证船舶的船期，并尽可能地缩短船舶的在泊作业时间，综合船舶和相应岸桥的信息，为船舶选配合理数量的作业岸桥并确定所选定岸桥的最优作业序列。

其中，船舶在泊作业时间主要由岸桥纯装卸作业时间、移动时间和干扰等待时间三部分组成。当岸桥的任务分配后，岸桥纯装卸作业时间为定值，相比之下岸桥的移动时间很短，因此干扰等待时间长度是衡量岸桥调度优劣的重要指标。本文中岸桥干扰等待时间是指多个岸桥在作业过程中，由于安全距离和不能跨越交叉造成岸桥等待的时间。如图1所示，假设岸桥作业的安全距离为1个船贝，岸桥1正在给船贝5作业，船贝6与船贝7相邻，当岸桥2要对船贝6作业时必须等到岸桥1作业完成移走后再开始，由此产生的等待时间即为岸桥干扰等待时间。

2 岸桥分配与调度集成模型 2.1 模型假设

龙源期刊网 http://www.qikan.com.cn

模型假设如下：

1）船舶的靠泊位置、靠泊时间、船舶的装卸箱量已知。

2）岸线上所有岸桥在同一条轨道上，岸桥的移动速度、作业效率相同。

3）岸桥对某船贝作业时，当该船贝上的所有集装箱都装卸完成后才能移动到其他船贝进行装卸。

4）不考虑装卸过程中船舶的稳性和等待集卡时间（即集卡数量充足）。

5）本文将岸线和船长均划分为以单位精度等于6m的刻度值。例如：L为岸线的长度，岸线刻度值为N=L/6（向上取整）。

其中：式（1）为目标函数，表示船舶在泊作业时间最短；式（2）保证任意时刻分配给船舶的岸桥数量满足最大最小值的；式（3）保证船舶作业岸桥之间不能有空闲岸桥；式（4）表示船舶停靠泊位时，对应岸线覆盖的岸桥数量等式约束；式（5）保证每个任务船贝只能分配一个且必须分配一个岸桥为其作业；式（6）保证为所有任务船贝均被岸桥服务；式（7）保证岸桥作业任务量的差距不大于不均衡底线；式（8）保证任意时刻为船舶服务岸桥数量不能大于已选配岸桥的总数；式（9）为岸桥与船贝的位置关系；式（10）表示船舶总任务量等于各有任务船贝的任务量之和；式（11）表示某台岸桥作业的第一个船贝开始作业的时间与船舶入泊时间的关系；式（12）表示某台岸桥完成两个连续任务时间的关系；式（13）表示船贝b被服务的开始时间与完成时间的等式关系；式（14）保证任意一个船贝由某台岸桥作业时最多有一个前续作业或后续作业；式（15）保证每台岸桥作业按照既定的顺序进行作业；式（16）～（17）保证岸桥移动时不能出现跨越且保持安全距离；式（18）表示某台岸桥执行下一个船贝任务的开始时间和上一个船贝任务的完成时间之间的等式约束；式（19）表示船舶离泊时间等于最晚装卸完成的船贝时刻。 3 改进的蚁群算法

遗传算法和蚁群算法是时效性较好的优化算法，对于城市规模在30以内的旅行商问题，用遗传算法便可以较好地求解，但是当城市数量在30～70时，蚁群算法效果较好[13]。本文将岸桥调度问题视为一个多旅行商问题（Multiple Traveling Salesman Problem， MTSP），有针对性地设计了改进的蚁群优化（IACO）算法用于搜寻问题的最优解。 3.1 确定各个蚁群路径的起点

本文设定蚂蚁总量等于船舶服务岸桥的整数倍，即IACO算法中蚂蚁被分成nqt个小群体，每个群体都有一个行走起点（各岸桥起始作业船贝）。

龙源期刊网 http://www.qikan.com.cn

为了确定各个起点，本文在保证约束式（15）的条件下，随机从所有任务船贝中挑出nqt个船贝作为各岸桥作业的起始贝位，即各蚁群路径起点。

若随机产生的各起点间距离小于安全距离，再重新随机产生，直到产生各起点间距离满足安全距离。

3.2 蚁群路径的生成（初始解的产生）

3.1节中已经确定了各个蚁群的行走起点，接下来需要确定其以后的巡访点，这样才能形成完整的路径，即各岸桥的作业路径。本文首先根据任务船贝分布建立一个距离矩阵Dmatrix；然后采用以下两个转移函数逐渐确定后续的点（任务船贝）。 任务船贝间的转移概率为：

p（k）=TAU（i，k）α·η（i，k）β； i∈tabu，k∈allow（20）

其中：p（k）为蚂蚁在船贝k处的概率值大小；TAU（i，k）为信息矩阵中第i行，第k列对应的数值。

蚂蚁在当前任务船贝i时访问下一个任务船贝j的概率为：

p（i， j）=TAU（i， j）α·η（i， j）β∑j∈allowTAU（i， j）α·η（i， j）β， j∈allow0，其他 （21）

式（20）～（21）中：TAU为信息素矩阵；tabu为禁忌表记录已访问的任务；allow为未访问任务的集合；α为信息重要度因子； β为启发式函数重要度因子；η表示一个矩阵，且矩阵中元素η（i， j）=1/Dmatrix（i， j）。 3.3 算法优化目标

算法的优化目标和数学模型的目标一致为船舶在泊时间最短，即所有任务船贝中最后被装卸箱子的完成时刻最早，即蚁群走完路径中各点时的时刻最早，表示如式（22）： min{max{btq+lengtq； q=1，2，…，nqt}}（22）

其中：btq表示岸桥q的开始作业时刻值，即蚁群q的开始行走时刻；lengtq为岸桥q的按照作业路径进行作业花费的时长，即蚁群q在路径上行走时长。 3.4 信息素更新

龙源期刊网 http://www.qikan.com.cn

当所有蚂蚁完成一次路径巡访，即完成一次搜索后需要进行信息素的更新。首先，计算各个蚁群的行走路径时长为lengtq（即各岸桥作业时长）；然后，记录当前迭代次数中的最优解；最后，根据式（23）～（24）对各个点（任务船贝）的信息素浓度进行更新： TAU（t+1）（i， j）=（1-ε）·TAU（t）（i， j）+ε·ΔTAU（i， j）； 0 ΔTAU（i， j）=∑qΔTAUq（i， j）（24）

式（23）表示第t+1次搜索中任务i与j之间的信息素浓度为第t次搜索中蚁群挥发剩下的信息素浓度与蚁群释放的信息素浓度之和。其中：ε表示信息素的挥发程度，TAU（t）（i， j）表示第t次搜索中任务i与j之间的信息素浓度，ΔTAU为一个矩阵，表示蚁群在任务间释放的信息素浓度矩阵，ΔTAUq（i， j）表示第q只蚂蚁在任务i与j之间释放的信息素浓度；式（24）表示蚁群任务i与j之间释放信息素浓度计算公式。 3.5 解空间切割策略

本文优化模型中要求相邻岸桥不能跨越且各岸桥负载要尽量均衡，蚁群初始行走的路径中的一些路径（解）可能不满足上述情况，故需要剔除此类不可行解。一个解空间切割策略被提出，具体步骤如下：

步骤1 按照路径（解）的目标值大小倒序地排列各解。

步骤2 采用模型中约束式（7）、（16）、（17）对所有路径集合（解空间）进行切割，而且按照顺序逐一删除。

步骤3 判断剩余解个数，若不为零转到步骤4；若剩余解个数为零则重新生成初始路径集。

步骤4 停止切割操作，转到后续主体算法。 3.6 IACO算法的终止条件

当IACO算法的迭代次数达到预设的上限，计算终止，输出最优解及最优目标值。 4 数值实验 4.1 实验实例

本文以国内某集装箱码头为例，岸线长度为1200m（200贝），某集装箱船船长为300m，岸线上有7台岸桥，岸桥的移动速度为1贝/min（6m/min），装卸速度为1TEU/min。船舶入泊时刻为1：00，靠泊位置为船上第一个船贝的对应岸线贝号为60，设定岸桥间作业的

龙源期刊网 http://www.qikan.com.cn

不均衡底线为300，即岸桥间所作任务差额最大为300个，该船最大与最小岸桥需求量分别为6台和2台。各台岸桥初始位置见表1，存在任务的船贝及箱量见表2。 4.2 算法的参数取值

IACO算法的参数包括：蚂蚁数量、交叉率、最大迭代次数、信息素挥发因子、启发式函数重要程度因子、信息素重要程度因子。为了确定最优的各项参数取值，本文在Intel Core i5-2450M 2.50GHz（Giga Hertz）的处理器，4GB内存的PC（Personal Computer）上进行Matlab 7.6.0编程求解上述案例。

蚂蚁数量设置为配置的岸桥数的1，2，3倍；交叉率设置为0.05，0.1，0.15；最大迭代次数设置为100，150，200；信息素挥发因子设置为0.05，0.1，0.2；启发式函数重要程度因子设置为1，5，8；信息素重要程度因子为0.8，1，1.5。

为了确定最佳的蚂蚁数量，本文令迭代数、交叉率、信息素挥发因子、启发函数重要程度因子和信息素重要程度因子分别等于150，0.1，0.1，1和0.8，只改变蚂蚁数量去确定备选值中的最优值。图2展示了不同蚂蚁数量情况下算法的目标值收敛曲线。从图2中可以看出当蚂蚁数量为岸桥数量的2倍时收敛值最小，因此确定IACO算法中蚂蚁数量为配置岸桥数的2倍；为确定最佳的交叉率，本文令迭代数、蚂蚁数量、信息素挥发因子、启发函数重要程度因子和信息素重要程度因子分别等于150，2倍，0.1，1和0.8。图3为不同交叉率下算法目标值的收敛曲线。从图3中可以看出交叉率为0.1时收敛值最小，因此确定IACO算法中交叉率等于0.1。

同理，其余算法参数的确定也按照上述方法对比确定，从而最终确定IACO算法的各项参数取值为：蚂蚁数量为岸桥数2倍；交叉率为0.1；最大迭代次数为150；信息素挥发因子为0.1；启发函数重要程度因子为5；信息素重要程度因子为1。 4.3 实验结果

采用4.1节实验数据和4.2节算法参数取值，在Intel Core i5-2450M 2.50GHz的处理器，4GB内存的PC上进行Matlab 7.6.0编程求解，仅用2.24s求得近似最优值为952min，即船舶在泊时间为952min。同时求得配置的岸桥数为4台，各台岸桥的作业路径及任务开始完成时间信息见表3，然后结合表1中各台岸桥初始位置信息，绘制出各台岸桥的作业路径如图4所示，其中QC表示岸桥（Quay Crane）。

为了验证本文设计的IACO算法优于传统蚁群优化（Ant Colony Optimization， ACO）算法，采用相同算法参数设置分别进行了实验。两种算法的收敛效果如图5所示，从图5可以看出IACO算法在求解准确性和收敛速度两方面都优于传统ACO算法。

为了进一步验证算法的有效性和稳定性，本文采用7个不同规模的实验进行分析，每个规模下选用2个算例，其中各船贝箱量在区间[100，200]随机产生。

龙源期刊网 http://www.qikan.com.cn

针对上述算例，分别采用本文算法和Lingo12.0进行求解，实验结果如表4（max一列表示船舶能配置的最大岸桥数量）所示，其中每一个规模下实验结果为实验10次所取的最优值。图6为目标收敛值随着实验规模变化的曲线。

从表4可以看出，不同的任务规模下，相比所有岸桥全部投入使用的方法，本文模型与算法求得结果平均能够节约31.86%的岸桥资源；采用IACO算法求得的最优值同Lingo给出的最优值之间的平均偏差仅为5.23%，但CPU处理时间平均节省了3.8倍但CPU处理时间平均降低了78.7%节约不能用“倍”来描述，是否可以改为“平均节省了78.7%”？请明确。；而且从图6中可以看出，当任务船贝数小于40时最优值偏差较大，大于40时最优值偏差较小。 5 结语

本文在分析岸桥实际作业特点的基础上，重点考虑岸桥作业过程中的干扰等待时间与作业量均衡，建立了单船作业岸桥配置与调度优化的数学模型，并设计了改进的蚁群算法进行求解。从实例分析可以看出，本文建立的模型和设计的改进蚁群算法，对集装箱码头的岸桥配置与作业序列优化问题有很好的求解效果，可为港口方制定完善实用的泊位作业计划提供一定的指导。

本文研究了连续泊位下单船岸桥配置及调度问题，未来将在此基础之上进一步深入研究多船同时作业时的岸桥配置和调度问题。 参考文献：

[1]KIM K H， PARK Y-M. A crane scheduling method for port container terminals [J]. European Journal of Operational Research， 2004， 156 （3）： 752-768.

[2]MOCCIA L， CORDEAU J F， GAUDIOSO M， et al. A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal [J]. Naval Research Logistics， 2006， 53 （1）： 45-59.

[3]BIERWIRTH C， MEISEL F. A fast heuristic for quay crane scheduling with interference constraints [J]. Journal of Scheduling， 2009， 12（4）： 345-360.

[4]NATHAN N. An efficient genetic algorithm for solving the quay crane scheduling problem [J]. Expert Systems with Applications， 2012， 39 （2）： 13108-13117.

[5]MEISEL F， BIERWIRTH C. A unified approach for the evaluation of quay crane scheduling models and algorithms [J]. Computers & Operations Research， 2011， 38（3）： 683-693. [6]LEGATO P， TRUNFIO R， MEISEL F. Modeling and solving rich quay crane scheduling problems [J]. Computers & Operations Research， 2012， 39（9）： 2063-2078.

龙源期刊网 http://www.qikan.com.cn

[7]LE M， ZHAO Y， LIU X. Shore-mounted gantry crane scheduling for single vessel under time window-using mathematical programming and rule heuristic algorithm [J]. Computer

Engineering and Applications， 2014， 50（9）： 242-248.（乐美龙，赵彦营，刘秀玲.时间窗下单船岸桥调度——基于数学规划和规则的启发式算法[J].计算机工程与应用，2014，50（9）：242-248.）

[8]MEISEL F. The Quay crane scheduling problem with time windows [J]. Naval Research Logistics， 2011， 58（7）： 619-636.

[9]LEGATO P， MAZZA R M， TRUNFIO R. Simulation-based optimization for

discharge/loading operations at a maritime container terminal [J]. OR Spectrum， 2010， 32（3）： 3-67.

[10]CHUNG S H， CHOY K L. A modified genetic algorithm for quay crane scheduling operations [J]. Expert Systems with Applications， 2012， 39（4）： 4213-4221.

[11]SU N， ZHANG M， JOHNSTON M， et al. Hybrid evolutionary computation methods for quay crane scheduling problems [J]. Computers & Operations Research， 2013， 40（8）： 2083-2093.

[12]LU Z， HAN X， XI L， et al. A heuristic for the quay crane scheduling problem based on contiguous bay crane operations [J]. Computers & Operations Research， 2012， 39（12）： 2915-2928.

[13]CHEN J， LEE D-H， CAO J. Heuristics for quay crane scheduling at indented berth [J]. Transportation Research Part E： Logistics and Transportation Review， 2011， 47（6）： 1005-1020.

[14]FAN Z， LE M. A genetic algorithm to minimize the makespan and waiting time for the bi-objective quay crane scheduling problem [J]. Journal of Systems and Management， 2013， 22（1）： 120-127.（范志强，乐美龙.最小化最大完工时间与等待时间的岸桥作业调度双目标优化及其遗传算法[J].系统管理学报，2013，22（1）：120-127.）

[15]DIABAT A， THEODOROU E. An integrated quay crane assign-ment and scheduling problem [J]. Computers & Industrial Engineering， 2014， 73： 115-123.

[16]CAI G， DONG E. Comparison and analysis of generation algorithm and ant colony optimization on TSP [J]. Computer Engineering and Applications， 2007， 43（10）： 96-98.（蔡光跃，董恩清.遗传算法和蚁群算法在求解TSP问题上的对比分析[J].计算机工程与应用，2007，43（10）：96-98.）

龙源期刊网 http://www.qikan.com.cn