基于量子遗传混合算法的泊位联合调度

2020-06-06刘朋青熊禾根

计算机应用 2020年3期

蔡芸，刘朋青，熊禾根

（1. 冶金装备及其控制教育部重点实验室（武汉科技大学），武汉430081；2. 机械传动与制造工程湖北省重点实验室（武汉科技大学），武汉430081）

（*通信作者电子邮箱:lpq13618640356@163.com）

0 引言

传统泊位或拖轮调度通常只考虑其单一调度，通常泊位调度以最小化总体船舶在港时间［1］、总体船舶服务成本［2］或提高经济绩效［3］为目标，拖轮调度以最小化作业时间［4］、节省燃油成本［5］为目标，问题求解算法较多，例如入侵野草算法［1］、多目标遗传算法［6］、包含动态学习的粒子群算法［7］等。

为了提高集装箱港口作业效率及顾客的服务满意度，必须合理地利用泊位、拖轮。拖轮和泊位联合调度有利于缩短船舶在港时间，提升港口服务效率。但是，目前针对拖轮及泊位联合调度的研究较少，问题模型通常含靠泊、离泊和泊位装卸服务三个作业阶段，优化目标为最小化船舶等待费用与拖轮服务费用［8］、最小化所有船舶中最晚完成靠泊时刻［9］等，联合调度求解方法常采用遗传与模拟退火的混合算法［8］、嵌入局部搜索功能的进化算法［9］、改进遗传算法［10］等。

由于船舶拖期，港口需要给付罚金，减小拖期时间可以降低船舶滞留成本，提高顾客满意度。为此，本文在已有研究基础上，分析了拖轮、泊位联合调度和岸桥分配问题中存在的相关约束，并建立相关问题模型，展开了基于量子遗传混合算法的泊位联合调度研究。

1 问题分析

泊位的联合调度问题可以分为三个阶段:第一阶段根据船舶的到港信息，对船舶分配拖轮、停靠泊位，由拖轮将船舶从锚地拖曳至泊位；第二阶段根据船舶的装卸量和岸桥的可调用情况，对靠泊船舶分配岸桥进行装卸作业；第三阶段安排拖轮将完成装卸的船舶拖曳出泊位。

在人工调度过程中，负责船舶靠离泊的拖轮调度、泊位调度和负责在泊位装卸货物的岸桥分配，通常相互独立进行，容易导致船舶和拖轮阻塞，或按计划靠泊后岸桥却不能立即到位，造成船舶既占用了泊位资源，又增加了船舶在港时间。如果将拖轮、泊位进行联合调度，就有利于使靠泊、装卸、离泊三阶段作业连贯有序地进行，降低船舶的在港时间，减少港口的作业成本同时提高客户的满意度。

拖轮和岸桥资源分配必须满足以下调度规则:

1）拖轮调度规则。拖轮调度要求是按照集装箱船舶的船长（不考虑装卸货物量）分配相应种类和数量的拖轮协助作业，具体配置规则如表1［5］所示。

表1 船舶类型与拖轮马力匹配原则Tab. 1 Matching principle of ship type and tugboat horsepower

2）岸桥调度规则。岸桥的分配与船舶的装卸量有关，当船舶装卸量小于200 箱时，安排1～2 台岸桥；装卸量在200～500箱时，安排2～3台岸桥；装卸量在500～1 000箱时，安排3～4台岸桥；装卸量大于1 000箱时，安排4～6台岸桥。

2 模型建立

2.1 模型假设

1）周期内到港船舶数据已知；

2）不考虑船舶在泊位间移泊；

3）拖轮与船舶之间是一种多对一的动态匹配关系；

4）各类型船舶与拖轮匹配关系和由不同拖轮组服务所需时间已知；

5）岸桥与船舶的匹配关系已知；

6）岸桥总数以及装卸速度已知。

2.2 数学模型

1）集合和参数。

计划周期内到港船舶的集合为N（N=｛1，2，…，n｝），用i表示到港船舶编号；港口泊位的集合为M（M=｛1，2，…，m｝），用j表示港口泊位编号；拖轮的集合为T（T=｛1，2，…，t｝），用u表示拖轮编号；拖轮u的马力值为TPu；船舶i的安全船长（含横向安全预留长度）为NLi；船舶i的安全水深（含纵向安全预留长度）为NDi；泊位j的长度为MLj；泊位j的水深为MDj；拖动船舶i所需的拖轮艘数为Qi；船舶i的装载箱量为Ii；船舶i的卸载箱量为Ei；岸桥的装卸速度为v；分配给船舶i的最小和最大岸桥数为；码头可用岸桥总数为C。船舶i的到港时刻为ai；船舶i的预计离港时刻为Di；船舶i开始被拖轮拖离锚地至泊位j的时刻为Aij；船舶i的在港时间为sti。

2）决策变量。

若船舶i在泊位j上作为第h艘船舶被服务，则就取值为1，否则取值为0；若船舶i由拖轮u拖曳至泊位j，则Yiju=1，否则取值为0；若船舶i由拖轮u拖离泊位j，则Y′iju=1，否则取值为0。

2.3 目标函数

在实际求解中，将两个目标加权求和转化为单目标进行计算:

因此目标函数为:

其中:加权系数C1、C2取值分别为0.7、0.3（咨询专家打分获得）。

2.4 约束条件

式（5）保证每个泊位上被服务的船舶数之和为到港船舶的总数；式（6）保证每条船舶必须在某个泊位被服务且只被服务一次；式（7）保证同一泊位同时最多停靠一艘船舶；式（8）保证船舶i到港后才被拖轮拖曳至泊位；式（9）保证停靠在泊位j的船i的长度应小于泊位j的长度；式（10）保证停靠在泊位j的船i的吃水深度小于泊位j的安全深度；式（11）保证同一拖轮同时最多服务于一艘船舶；式（12）保证同一时刻被调度用于助泊作业的拖轮数不超过港口总拖轮数；式（13）、式（14）保证船舶i配置的拖轮数等于匹配规则表内船舶i所需的拖轮数；式（15）保证分配给船舶i的岸桥数在最大和最小岸桥数的范围内；式（16）保证同一时刻在工作的岸桥数不超过港口总岸桥数；式（17）、式（18）、式（19）为决策变量。

3 混合算法设计

3.1 混合算法流程

拖轮和泊位联合调度目前多采用启发式算法或混合算法求解［8-9］，为了研究不同算法求解该类问题的效果，本文进行了量子遗传混合算法的应用研究。量子遗传算法（Quantum Genetic Algorithm，QGA）是一种结合量子计算与遗传算法的概率进化算法，相比遗传算法拥有更好的多样性特征以及全局寻优能力［11］。本文在保留交叉、变异遗传操作的基础上，采用动态调整量子门旋转角大小的策略取代固定旋转角策略，对量子门更新操作进行改进；为了获得更好的优化效果，将量子遗传算法与禁忌搜索（Tabu Search，TS）算法［12］进行串行混合，以量子遗传算法的优化解作为禁忌搜索算法的初始解，有效解决了TS对于初始解有较强依赖性的缺陷，防止搜索过程陷入局部最优，达到了更好的搜索效果。混合算法步骤如下:

1）初始化种群及各参数，随机生成m个个体，并对个体的染色体进行量子比特编码。

2）对染色体进行测量，得到对应的解。

3）对各确定解进行适应度评估，并记录最优解和对应的适应度；

4）判断是否满足量子遗传算法的终止条件:若满足终止条件，输出量子遗传算法的最优解，作为禁忌搜索的初始解，进入步骤7）；否则继续以下步骤5）。

5）对染色体进行交叉、变异遗传操作。

6）量子旋转门调整策略更新，利用动态量子旋转门更新种群，返回步骤3）。

7）选择候选解（选择当前最优解）。

8）判断是否满足禁忌搜索的终止条件:若满足，混合算法结束并输出结果；否则，继续以下步骤9）。

9）生成邻域候选解。

10）计算适应度函数值（解码）。

11）更新禁忌表，判断是否满足藐视规则:若满足，将满足藐视规则的解作为当前解，同时将其放在禁忌列表第一个位置，更新最优解；若不满足，确定候选解的质量，选取未被禁忌的最优解作为当前解，同时将其放在禁忌列表第一个位置。返回步骤7）。

3.2 混合算法的关键技术

3.2.1 染色体结构

针对本文调度问题，采用双染色体结构。第一条染色体采用实数编码，确定到港船舶的服务顺序；第二条染色体采用矩阵编码，确定港口资源的调度安排，其结构如下。:

其中:n为到港船舶的数量，Pb表示每艘到港船舶停靠泊位的编号，Pt表示每艘船舶靠泊使用的拖轮组的编号，P′t表示每艘船舶离泊使用的拖轮组的编号，Pq表示给每艘船舶分配的岸桥数量，种群中每个个体对应一个调度方案。

将实数编码转换为二进制编码后再进行量子比特编码，编码方式参考文献［13］，每个基因Xi的量子比特编码为（α，β），α、β的取值范围均为［0，1］，且满足:

每个基因Xi对应角度θi的取值范围在［0，π 2］，如图1所示。

图1 量子门更新示意图Fig. 1 Schematic diagram of quantum gate update

3.2.2 测量染色体

对种群中的各个染色体测量，获得一组确定的二进制解。每个基因对应0 或1 是根据量子比特的概率选择得到。具体测量的方法为:产生一个［0，π 2］内的随机数rand，若随机数小于θ，则测量结果为1；否则为0。

3.2.3 计算适应度

该问题的优化目标是最小化总体船舶在港时间和总拖期时间的加权和。因此，在该步骤设适应度函数为目标函数的相反数，即目标函数值越小的个体，其适应度值越大。解码时，若染色体违反约束条件（5）～（19），则该染色体无效；若染色体有效，则依据染色体及调度规则生成相应调度方案，计算出其个体适应度值，并记录最优个体及其适应度值。

3.2.4 遗传操作

在遗传算法中，通过对原有的两条染色体进行交叉操作，可能会得到更优异的子代染色体，这有利于种群的进化。本文采用两点交叉机制进行交叉操作，首先随机选择一对父代染色体，确定交叉基因的起止位置（两个染色体被选取位置相同），分别找出交叉基因在另一染色体中的位置，再将其余基因按顺序放入生成一对子代染色体。该方法的优势在于不会造成基因冲突，交叉操作如图2所示。

图2 交叉操作示意图Fig. 2 Schematic diagram of crossover operation

当种群在进化中陷入搜索空间中某个超平面时，通过变异操作可有助于摆脱这种困境。变异操作采用换位变异机制，随机选择一条染色体，确定两个变异基因，交换其位置，生成新的染色体。

3.2.5 动态量子门更新

与传统遗传算法不同，量子遗传算法的搜索寻优是在相位空间中利用量子门更新量子位概率幅实现［14］。本文量子门更新如图1 所示:θ′表示当前记录的最佳基因位，θ表示现在要进行更新的基因位，θ旋转Δθ角度后更新到θ′。旋转门的目的是朝着有利于进化的方向更新种群，1 表示逆时针旋转，-1 表示顺时针旋转，0 表示不旋转，因此旋转角旋转方向可表示为:

一般量子旋转门调整策略的角度是给定的，因而会给算法造成一定的限制。旋转角幅度太小，会导致算法收敛较慢，反之则会导致出现早熟。采用动态旋转角取代给定旋转角可解决这一问题［15］，本文设计一种旋转角动态选择策略:

其中:Δθ的取值区间为［0.001π，0.05π］，区间上的最小值用θmin表示，最大值用θmax表示，f′ =(fx-fmax)fx，fmax表示记录的最优个体的适应度值，fx表示当前个体的适应度值。因此，当fx与fmax的差值越小时，旋转角越小，该旋转角动态选择策略既可提高收敛速度，又可有效避免早熟现象。量子旋转门可表示为:

3.2.6 终止策略

设置最大迭代次数为混合算法的终止条件，当混合算法的迭代次数达到最大值时，停止迭代并输出最优解，若目标值小于给定阈值时，可提前终止迭代。禁忌搜索算法的终止策略为适应度值小于指定误差。

4 算例分析

4.1 算例数据

某港口人工调度的生产数据如表2所示。

表2 生产数据Tab. 2 Production data

该工作周期内总体船舶在港时间为80 h，总拖期时间为8.5 h。该港口泊位的总数为4，编号为1～4 号，泊位的长度分别为:200 m、300 m、300 m、400 m，泊位水深分别为:12 m、12 m、15 m、15 m；可用于入泊和离泊的拖轮共有6 艘，编号为1～6，马力值分别为1 200、2 600、3 200、3 400、3 400、4 000 匹；共有12 个岸桥可供使用，每个岸桥的装卸速度为40箱/h。

由于类型为S1的船舶在入泊和离泊都只需要一艘拖轮为其服务，所以1～6 号拖轮所需要的服务时间分别为0.6 h、0.5 h、0.4 h、0.3 h、0，3 h、0.3 h。拖轮马力越大，其拖拽同一类型的船舶所需要的时间越短，但是拖拽时间也是有一个下限的，所以所需要的时间不是一直减小的。不同类型的船舶使用不同类型的拖轮组合所需要的拖拽时间如表3所示。

表3 不同船舶类型由不同拖轮组合服务所需时间单位：hTab. 3 Time required for different ship types to be serviced by different tugboat combinations unit:h

4.2 参数选择

为验证混合算法的有效性，将混合算法与自适应遗传算法调度结果进行对比。自适应遗传算法采用自然数编码，染色体包含5 个子染色体，分别表示服务顺序、泊位编号、靠泊拖轮组、离泊拖轮组、岸桥数目。采用轮盘赌选择，交叉采用两点交叉法，变异采用换位变异。

混合算法参数的选择会影响到求优效果，为奠定调度应用研究的基础。本文将量子遗传混合算法用于Rastrigin's 函数和Schaffer函数，校验了混合算法的有效性并初步锁定了算法参数范围，根据实验结果的经验分析，本文确定自适应遗传算法的参数为:种群规模为20，交叉概率为0.8，变异概率为0.01，最大迭代次数为50。为进行有效对比，量子遗传混合算法的参数选择与自适应遗传算法保持一致，旋转角选择策略如式（23）所示。

4.3 结果分析

算法搜索过程如图3 所示，从图中可以看出，混合算法比遗传算法有更高的收敛精度，但是迭代次数较多。

图3 迭代优化曲线Fig. 3 Iterative optimization curves

图4、5 分别为混合算法和遗传算法的调度结果甘特图，横轴表示船舶在港时间跨度，纵轴表示泊位编号，甘特图反映了所有到港船舶入泊、装卸、离泊三个阶段所用的时间，其中T 表示拖轮编号，N 表示船舶编号，Q 表示分配岸桥数量。通过比较可以发现，在混合算法的调度方案下，第一艘船舶开始入泊到最后一艘船舶结束离泊的时间跨度为20.82 h，与遗传算法的调度方案相比减少了3.04 h，且相邻两个工作阶段的等待间隔明显减小，有效避免了港口资源不足时船舶出现等待的情况。

图4 混合算法调度结果Fig. 4 Scheduling result of hybrid algorithm

图5 遗传算法调度结果Fig. 5 Scheduling result of genetic algorithm

人工调度下总体船舶在港时间约为80 h，总拖期时间为8.5 h。遗传算法调度下最优解的总体船舶在港时间为68.1878 h，比人工调度减少了14.8%；总拖期时间为6.285 3 h，比人工调度减少了26.1%。混合算法调度下最优解的总体船舶在港时间为60.793 4 h，相比人工调度减少了24%，相比遗传算法减少了10.9%；总拖期时间为4.871 8 h，相比人工调度减少了42.7%，相比遗传算法减少了22.5%。两类调度算法均可有效节约船舶时间成本，但混合算法调度后节省的时间多于遗传算法，求解精度更高，其优化能力更强。