集装箱港口岸桥动态分配与贝位调度研究

梁承姬，王丹丹

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

集装箱港口岸桥动态分配与贝位调度研究

梁承姬，王丹丹

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

为提高集装箱港口岸桥的利用率和对船舶的服务水平，针对多船各贝位的任务量，考虑船舶优先度、可作业岸桥数量、岸桥冲突和安全距离等因素，以船舶的在港时间最短为目标，建立了多船岸桥动态分配与贝位调度混合整数规划模型，通过不同规模的算例，分别用C#调用Cplex和C#对遗传算法编程求解。结果表明：该模型能有效地解决多船的岸桥分配与调度问题，且遗传算法求解时间更短、求解质量更高，进而验证了该模型和算法的有效性。

交通运输工程；岸桥动态分配；岸桥贝位调度；岸桥冲突；安全距离；遗传算法

0 引 言

集装箱港口作为现代物流的重要组成部分，在全球物流系统中起着重要的作用。随着竞争的加剧，各个港口都面临着提高服务质量、降低服务成本、增加吞吐量的压力。要想缓解这些压力，必须有效利用港口的各种资源，如泊位、岸桥、场桥、堆存、集卡等。岸桥是港口的昂贵资源，也是稀缺资源，它的有效利用对于港口的运作效率至关重要。岸桥资源计划分为岸桥分配计划(Quay Crane Allocation Problem, QCAP)和岸桥调度计划(Quay Crane Scheduling Problem, QCSP)，两者紧密联系，同时考虑岸桥分配和调度问题可以更加有效的利用岸桥资源。集装箱港口的岸桥分配与调度问题(Quay Crane Allocation and Scheduling Problem, QCASP)研究如何为集装箱船舶分配岸桥以及安排每台岸桥的任务操作顺序，使得在满足实际约束的情况下尽早完成每艘船舶的装卸操作。

对于单船的QCSP，K.H.Kim等[1]提出了分支定界算法和贪婪随机自适应搜索算法。L.Moccia等[2]在K.H.Kim[1]的基础上，设计了分支切割算法，改进了解的质量。M.Sammarra等[3]把单船的QCSP分解为两个子问题，在此基础上设计了一种禁忌搜索算法。C.Bierirth等[4]设计了一个基于分支定界的单向调度启发式算法，算例结果表明该算法能够在更短时间内产生比以往文献质量更好的解。杨明珠[5]也对该问题进行了研究，给出了一种改进的启发式算法。F.Meisel等[6]对目前已有的单船岸桥调度优化模型和算法进行了分析和评价。

对于多船的QCASP，很多学者都是联合泊位资源一起考虑的。R.Tavakkoli-Moghaddam[7]扩展了K.H.Kim[1]提出的单船岸桥调度模型，构建了同时考虑一组船舶的混合整数规划(Mixed Integer Programming ,MIP)模型，并设计了遗传算法求解该问题。Liang Chengji等[8]和Zhang Canrong等[9]研究了船舶的靠泊位置、作业时间以及分配给每艘船的岸桥数量，前者建立了作业时间、等待时间及延迟时间之和最小的优化模型，后者建立了成本最小的优化模型，考虑产生成本的因素是船舶靠泊位置、停泊时间和完成时间。Lee Der-horng等[10]建立了求船舶在港时间最小的MIP模型，并证明了该模型是完全NP问题。梁承姬等[11]研究了考虑泊位的多船QCAP，建立了泊位分配MIP模型和岸桥调度MIP模型，并用Gurobi软件进行求解。A.Imai等[12]研究了泊位和岸桥的协调分配问题，并运用遗传算法进行求解。

以上研究大多是将岸桥分配和岸桥调度分开考虑的，即使考虑岸桥分配与调度的协同，也只是考虑单船的贝位调度问题。为此，笔者将岸桥分配和调度问题结合起来，针对多船各个贝位的任务量动态地考虑岸桥分配和调度问题，提出了相应的优化模型和求解算法，以寻求港口岸边操作效率最高的岸桥分配和调度方案。

1 问题描述

船舶靠泊之后由岸桥进行集装箱的装卸操作，完成装卸操作之后离港，如图1。在该过程中，对于某一个确定的计划时段，如船舶的进港时间、最晚离港时间、最大装卸时间、船舶上每个贝位的装卸任务量都是已知的，且假定船舶按照进港时间在岸边依次从左到右靠泊。在为船舶分配岸桥以及安排每台岸桥的任务操作顺序时，不仅要考虑船舶的进港时间、最晚离港时间和船舶优先度，还要考虑可作业岸桥数量、岸桥冲突以及岸桥安全距离等因素。笔者研究的是对某一个计划期内(通常一个计划期为12 h)，对进港的所有船舶进行动态的岸桥分配和调度，在保证船舶按时离港的前提下最小化每艘船舶的在港时间。

图1 集装箱港口岸边示意Fig.1 The illustration of quay side at container terminal

2 模型的建立

2.1 模型假设

岸桥在其服务的船舶没有全部完成任务之前可以移动到另外一艘船舶；每台岸桥拥有相同的工作能力，且可以双向移动；所有的岸桥都位于一条水平轨道上，并且将其从左到右依次编号；考虑岸桥之间的安全距离，不考虑岸桥的移动时间；按进港先后顺序为船舶依次编号，并将所有船舶的所有贝位依次编号；根据船舶进港时间生成船舶优先度序列，即先进港的船舶优先度高，其中同时进港的船舶根据其离港时间产生优先度，即先离港的船舶优先度高；根据所有船舶的总任务量安排可作业的岸桥数量；每个贝位的任务量由整数时间表示，单位为h；每个贝位的任务可以由多台岸桥在不同时段完成。

2.2 集合、参数及决策变量的定义

集合：K为船舶集合，由k表示，k代表船舶序号；Jk为船舶k的贝位集合，由j表示；Q为岸桥集合，由q表示，q代表岸桥序号；T为时间集合，由t表示。

参数：lkj为船舶k的贝位j的位置序号；m为相邻岸桥所在贝位序号的最小差值，这里定义为最小安全距离；pkj为船舶k的贝位j的任务量;Dk为船舶k的最大装卸时间；wk为船舶k的优先度。

Lk为船舶k的进港时间与第一个进港船舶的进港时间之差，这里定义为相距时间。

决策变量：Xkjqt为若岸桥q在第t时段分配给了船舶k的第j贝位则为1，否则为0；fkjt为若船舶k的第j贝位在第t时段已全部完成任务则为1，否则为0；rkt为若船舶k在第t时段已全部完成任务则为1，否则为0。

2.3 目标函数和约束条件

(1)

(2)

(3)

(4)

∀q∈Q,∀t∈T

(5)

(6)

∀k∈K,∀j∈Jk,∀t∈T

(7)

fkjt≥rkt, ∀k∈K,∀j∈Jk,∀t∈T

(8)

(9)

∀k∈K,∀j∈Jk

(10)

Xkjqt,fkjt,rkt∈{0,1},

∀k∈K,∀j∈Jk,∀q∈Q,∀t∈T

(11)

目标函数(1)将最小化每艘船舶的在港时间之和,转换为最大化一个计划期内船舶离港之后的时间之和；约束条件(2)保证在任意一个时段一台岸桥最多只能停放在一个贝位上；约束条件(3)保证在任意一个时段任意一个贝位上最多只能停放一台岸桥；约束条件(4)保证在任意一个时段正在工作的岸桥总数量不能超过可用的岸桥数量；约束条件(5)保证在岸桥从左到右依次排序的情况下，相邻岸桥之间保持至少m贝位的安全距离；约束条件(6)保证所有的集装箱任务在计划时段内都必须完成；约束条件(7)定义了每一个贝位上的工作完成标志，当t时段船舶k的第j贝位上的任务全部完成时fkjt的值为1，此时在某一贝位上的所有岸桥的时间段总和要大于该贝位的任务量；约束条件(8)保证某一船舶的所有贝位上的任务全部完成时才表示该船舶操作完成；约束条件(9)确保所有船舶不超过其最晚离港时间离港；约束条件(10)确保任意船舶的任意贝位是在船舶进港之后开始操作的；约束条件(11)确保所有的决策变量都是0～1变量。

3 遗传算法的实现

遗传算法(Genetic Algorithm,GA)是一种高度并行、随机和自适应的优化算法，其编码技术与遗传操作较简单，优化不受限制性条件的约束，其已经在各个领域有了广泛的应用。由于问题的复杂性，考虑使用遗传算法来求解。

3.1 染色体编码

图2 染色体编码示意Fig.2 The illustration of chromosome coding

3.2 生成初始种群

生成初始种群有两种方法。一种是随机生成法，该方法有利于保持初始种群的多样性；另一种是启发式方法，它虽然可以生成质量较高的初始个体，但可能会导致局部最优解。笔者采用随机生成法生成初始种群，并且只允许可行解成为初始种群的一部分，具体规则如下：

2)每行中的整数顺序随机排列，但要保证每艘船舶的各个贝位要在进港之后开始作业以及在最晚离港时间之前结束作业；

3)每列中的整数按降序排列，即保证岸桥不跨越交叉，且每列中相邻整数的差值不能小于安全距离。

3.3 适应度计算和父代选择

根据目标函数，目标函数值大的给予高适应度值。采用轮盘赌方式产生与种群相同数量的染色体为父代。

3.4 遗传操作

3.4.1 交叉操作

采用修补交叉，它基于均匀交叉。即首先生成一个二进制字符串矩阵，其中1和0的个数相等。如果在该二进制字符串矩阵中的值为1则子代相应位置的基因值取父代1相应位置的基因值，然后根据子代已有的基因值划去父代2的一部分基因值，再用父代2剩余的基因值依次填满子代剩余的基因位置。如图3为交叉操作的过程。

图3 交叉操作示意Fig.3 The illustration of crossover operation

3.4.2 变异操作

采用交换变异，其变异操作过程如图4。

图4 变异操作示意Fig.4 The illustration of mutation operation

3.5 结束规则

通过以上规则产生的新的子代将会替代旧种群中适应度值最小的染色体，该过程中将保持种群规模，且迭代到最大迭代次数时终止迭代。

4 算例与结果分析

为了更好地理解和验证笔者所提出的模型和算法的有效性，编制了不同规模的算例。设定遗传算法的交叉概率是0.9，变异概率是0.2，最大迭代次数是500次，种群规模是150。运行环境为Intel(R) Core(TM) i5处理器、内存4G、硬盘500G的个人计算机，使用C#_2010对遗传算法编程并计算。

4.1 两艘船舶的输入数据与结果分析

船舶数量为2，可用的岸桥数量为3，安全距离为1，其它输入数据见表1和表2。计算结果如图5，可以看出该结果既满足模型中船舶的约束也满足岸桥的约束，且能够使每艘船舶在最晚离港时间之前尽早离港。图6所示是将结果用岸桥和时间的坐标显示，坐标里的数字代表贝位编号。

表1 船舶任务量数据Table 1 The task data of every vessel

表2 船舶时间数据Table 2 The time data of every vessel

图5 两艘船舶的贝位-时间甘特图Fig.5 Bay & time Gantt chart of double vessels

图6 两艘船舶的岸桥-时间甘特图Fig.6 Quay crane & time Gantt chart of double vessels

4.2 5艘船舶的输入数据与结果分析

船舶数量为5，可用的岸桥数量为7，安全距离为1，其它输入数据见表3和表4。计算结果如图7所示，可以看出该结果既满足模型中船舶的约束也满足岸桥的约束，且能够使每艘船舶在最晚离港时间之前尽早离港。图8是将结果用岸桥和时间的坐标显示，坐标里的数字代表贝位编号。

表3 船舶任务量数据Table 3 The task data of every vessel

表4 船舶时间数据Table 4 The time data of every vessel

图7 5艘船舶的贝位-时间甘特图Fig.7 Bay & time Gantt chart of five vessels

图8 5艘船舶的岸桥-时间甘特图Fig.8 Quay crane & time Gantt chart of five vessels

4.3 不同规模的算例结果比较

为了验证笔者设计的遗传算法求解该模型的有效性，使用C#_2010编程并调用Cplex求解作为对比。问题规模从小规模扩展到实际问题的规模，其中每艘船舶的贝位数以及每个贝位上的任务量是随机生成的。船舶的时间信息和可用的岸桥数量是根据问题的规模已知的。表5是不同算例规模的情形下两种方法的计算结果。对比可以看出：从能否求解来讲，在所有算例中遗传算法均求得了最优解，而当问题规模扩大到一定程度时Cplex无法求解；在计算时间方面，尽管在较小规模时遗传算法求解的时间稍长，但随着问题规模的扩大，其计算时间远远小于Cplex的求解时间，如图9；在求解质量方面，小规模问题时两者的求解结果一致，但随着问题规模的扩大，遗传算法的目标函数值(OFV)越来越优于Cplex。总之，遗传算法能够在合理的时间内求得最优解，相比Cplex求解时间较短，求解质量较高，体现了其有效性，且对于该问题的大规模问题，遗传算法更加有效。

图9 两种方法求解时间对比Fig.9 Comparison of computing time by two methods

表5 Cplex和GA求解不同规模的算例结果Table 5 The results of Cplex and GA by solving examples of different scales

5 结 语

对集装箱港口的岸桥分配与调度问题进行了研究。考虑了船舶和岸桥的实际因素，以船舶在港时间最短为目标建立了多船岸桥动态分配与贝位调度混合整数规划模型。设计了遗传算法进行求解，结果表明该模型可以有效解决岸桥的分配与调度问题。最后，通过不同规模的算例，分别用Cplex与遗传算法进行求解。结果表明遗传算法的求解时间更短，求解质量更高，随着问题规模的扩大其优越性更加明显。因此笔者提出的优化方法，可为解决大规模的多船情形下岸桥的统一优化问题提供科学合理的解决方案和决策依据。需提出的是，由于泊位计划影响岸桥的分配和调度，所以未来也可以考虑把泊位计划加入QCASP中，进而更加有效的优化集装箱港口的岸边操作。

[1] KIM K H,PARK Y M.A crane scheduling method for port container terminals[J].EuropeanJournalofOperationalResearch,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].NavalResearchLogistics,2006,53(1):45-59.

[3] SAMMARRA M,CORDEAU J F,LAPORTE G,et al.A tabu search heuristic for the quay crane scheduling problem[J].JournalofScheduling,2007,10(4/5):327-336.

[4] BIERWIRTH C,MEISEL F.A fast heuristic for quay crane scheduling with interference constraints[J].JournalofScheduling,2009,12(4): 345-360.

[5] 杨明珠.单船装卸作业的岸桥调度[J].计算机工程与应用,2011,47(10): 224-228. YANG Mingzhu.Quay crane scheduling method for single vessel[J].ComputerEngineeringandApplications,2011,47(10):224-228.

[6] MEISEL F,BIERWIRTH C.A unified approach for the evaluation of quay crane scheduling models and algorithms[J].Computers&OperationsResearch,2011,38(3):683-693.

[7] TAVAKKOLI-MOGHADDAM R,MAKUIA A,SALAHI S ,et al .An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports[J].Computers&IndustrialEngineering,2009,56(1):241-248.

[8] LIANG Chengji,HUANG Youfang,YANG Yang.A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning[J].Computers&IndustrialEngineering,2009,56(3):1021-1028.

[9] ZHANG Canrong,ZHENG Li,ZHANG Zhihai,et al.The allocation of berths and quay cranes by using a sub-gradient optimization technique[J].Computers&IndustrialEngineering,2010,58(1):40-50.

[10] LEE Der-horng,WANG Huiqiu.Integrated discrete berth allocation and quay crane scheduling in port container terminals[J].EngineeringOptimization,2010,42(8):747-761.

[11] 赵坤强,韩晓龙,梁承姬.连续泊位下集装箱港口泊位与桥吊协同调度优化研究[J].武汉理工大学学报,2011,33(11):60-65. ZHAO Kunqiang,HAN Xiaolong,LIANG Chengji.Berth and quay crane collaborative optimization research at continuous terminals[J].JournalofWuhanUniversityofTechnology,2011,33(11):60-65.

[12] IMAI A,CHEN H C,NISHIMURA E,et al.The simultaneous berth and quay crane allocation problem[J].TransportationResearchPartE:LogisticsandTransportationReview,2008,44(5):900-920.

Quay Crane Dynamic Allocation and Scheduling with Bay Research at Container Terminal

LIANG Chengji，WANG Dandan

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

In order to improve the quay crane’s efficiency and service level for vessels at container terminal, aiming at the heavy workload in every bay of multi-vessels, by considering such factors as ship priority, quantity of available quay crane, quay crane collision and safe distance, a mixed integer programming model on dynamic allocation of quay crane for vessels and scheduling and deployment of bay was establizhed in an attempt to minimize vessels’ staying time at container terminal. Through different scales of examples, the results obtained from Cplex and genetic algorithm programmed by C# respectively showed that the proposed model can effectively solve the problems of quay crane allocation and scheduling of multi-vessels and genetic algorithm has shorter computing time and higher quality solution thus verifying the effectiveness of this model and algorithm.

transportation engineering; quay crane dynamic allocation; quay crane scheduling with bay; quay crane collision; safe distance; genetic algorithm

10.3969/j.issn.1674-0696.2016.02.34

2014-10-27；

2014-12-29

国家自然科学基金项目(71471110，71301101)；中国博士后科学基金项目(2014M550084)

梁承姬(1970—)，女(朝鲜族)，吉林龙井人，教授，博士，主要从事集装箱港口物流方面的研究。E-mail：liangcj@shmtu.edu.cn。

王丹丹(1989—)，女，山西长治人，硕士研究生，主要从事集装箱港口设备资源优化方面的研究。E-mail：783964457@qq.com。

U694

A

1674-0696(2016)02-169-05