基于遗传算法的自动化集装箱码头双轨道吊协同调度优化研究

2018-09-26黄继伟韩晓龙

计算机应用与软件 2018年9期

黄继伟韩晓龙

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

0 引言

随着经济全球化进程的加快和世界经济贸易高速发展，集装箱港口得到迅猛发展，各集装箱港口吞吐量持续快速增长。为满足集装箱船舶大型化和航运联盟化的需求，安全、高效、环保、节能的自动化集装箱码头ACTs(Automated Container Terminalss)备受青睐。建设自动化集装箱码头成为全球各大港口的内在需求和发展趋势。

码头堆场作业是集装箱港口运作的重要部分。自动化集装箱码头的堆场各箱区一般配置两台相同的两端式自动化轨道吊ASCs(Automatic Stacking Cranes)。两台轨道吊共用相同的轨道且不可互相穿越通过。轨道吊是集装箱港口作业的瓶颈，双ASC的协同调度直接影响到港口整体运行效率。在自动化集装箱码头文献研究方面，文献[1]对堆场作业相关研究如装卸运输设备等进行了深入的概述，重点介绍了当前的行业趋势和发展状况，提出了堆场作业分类方法，并对2004年—2012年间发表的科研期刊论文进行了分类。文中还探讨了现有的堆场作业模式，最后根据集装箱码头行业的发展趋势指出新的研究点。码头堆场作业是集装箱港口运作的重要部分。在自动化集装箱码头中，自动化轨道吊ASCs的采用大幅提升了港口整体运行效率，轨道吊的调度策略直接影响到码头生产运营。文献[2]对集装箱码头的主要物流流程和运营情况的现有研究情况进行了详尽描述和分类，并对相关优化方法进行了全面调研。Vis等[3]将自动化集装箱码头堆场内集装箱的存取问题视为农村邮路问题的一个特例，并将该问题重新定义为一个不对称的Steiner旅行商问题，以重构方式在部分问题二分网络中的最优分配以及这些部分之间连接的动态规划组合来有效解决ASC调度问题以实现优化。文献[4]全面研究了自动化集装箱码头堆场不同领域的路线规划中的各种问题。提出了基于集装箱装卸问题的数学分析模型，并考虑箱区长度、作业流畅度及安全距离等因素，开发了一种基于遗传算法的最优路径规划方法。最后通过实验算例验证了该算法的有效性，为提高集装箱装卸效率探索出了一条新途径。文献[5]针对自动化码头并行式双ASC调度问题首次对双ASC优先级进行对比分析，并量化了所选优先级的影响，提出了14条双ASC优先规则，并通过仿真对完工时间进行了评估。最后将优先级规则与使用分支定界法求得的最优优先级进行比较，得到最优的单调度规则和调度规则组合。文献[6]就集装箱码头并行式双ASC在海侧完成进口集装箱存箱作业的调度问题进行了探索，考虑双ASC之间的作业干扰和ASC优先权问题，以总完工时间最小化为目标，提出了基础问题的复杂性证明，并引入和测试了高效的启发式算法。文献[7]探讨了由双ASC合作完成装卸任务对任务执行效果的影响，开发启发式算法求解并通过算例对算法性能进行评估。文献[8]也针对作业任务已分配完成的情况探讨了两端式和穿越式两种轨道吊配置的优先作业顺序问题，建立相应的图形模型并开发强多项式算法进行求解。

针对堆场存箱或取箱的单一类型作业问题，文献[9]探讨了单箱区内海陆侧集装箱存取作业的双ASC调度问题，以双ASC完工时间最小化为目标，建立整数规划模型并提出了两种算法对该问题进行求解。文献[10]就洋山四期自动化集装箱码头的双ASC协同调度问题进行了研究。通过分析任意两个任务之间的最小时间间隔来量化ASC之间的干扰，建立了三个数学模型，以最小化总完工时间对集装箱作业任务进行排程。设计精确算法和遗传算法来解决该问题，同时就所提出的模型和算法对实际自动化集装箱码头的管理理念和技术方面的应用进行了探讨。文献[11]针对堆场同一箱区内存箱或取箱的单一作业，考虑双起重机时空同步约束条件，以最小化作业总完成时间为目标建立双起重机调度混合整数规划模型，并设计遗传算法对大规模任务数量问题进行求解。算例分析结果表明，在大规模问题上遗传算法在解的质量上逐渐优于CPLEX算法且运算时间远小于CPLEX，证明了该双起重机调度模型与算法的有效性及合理性。

针对接力区或缓冲区的设计问题，文献[12]探索了自动化集装箱码头海陆侧接力区的设计对双自动化轨道吊作业性能的影响。以任务总完工时间或因作业干扰造成的ASC等待时间最小化为目标，通过变换堆场设计条件如ASC作业方式、接力区中集装箱对方位置以及接力区的有无、大小、数量等，并针对不同条件开发多种启发式方法进行求解。文献[13]通过对成对自动堆垛起重机在堆场实时调度问题的研究。建立了以最小化外集卡和船舶延时为目标的不对称的多旅行商模型，引入了接力、缓冲、干扰等关键约束，并利用并行实时调度策略对多组情景进行案例研究分析。结果表明设置主缓冲区以及接力区可以减少作业延时且海侧作业量较多时，增加缓冲区的容量可以更有效地增加作业效率。

现有研究多只针对堆场存箱或取箱操作的单一作业类型进行探讨，而对于单箱区内考虑存箱和取箱作业同时进行以及接力区的设计的研究相对较少。本文同时考虑进、出口箱的存取操作，以任务完成总时间最小化为目标，建立双轨道吊协同调度混合整数规划模型，有效避免ASC之间作业干扰，并用CPLEX和遗传算法对不同规模算例进行求解。

1 问题描述

目前，国际上自动化集装箱港口堆场多采用垂岸式布局，双ASC协同作业完成对进出于堆场的各种集疏港和装卸船的集装箱的装卸操作。堆场箱区布局如图1所示。当码头装卸任务下达后，分配到各箱区的集装箱需要在最短的时间内处理完毕，这对各箱区内设备的集装箱处理能力提出了更高的要求。两台相同的轨道吊在完成各自的装卸任务时往往发生作业干扰。若在箱区中设置接力区，使双ASC通过接力完成集装箱存取操作，即可大幅减少双ASC的作业干扰频率。因此，确定合适的接力区位置、有效避免双ASC作业干扰成为优化堆场作业、提高堆场作业效率的关键。

图1 自动化集装箱港口箱区布局示意图

为有效解决双ASC存取箱操作同时进行的协同调度干扰问题，采用以下任务拆分规则：箱区中设接力区(Handshake area)，接力区大小为1贝。凡需要跨越接力区才能完成的任务均以接力区为界限进行拆分，即每个符合要求的初始任务均拆分为两个子任务，并分别由海陆两侧SAC协作完成存取操作。同一箱区内海、陆侧两端各设有一个集装箱交接区，又称为I/O点(I/O point)，集港或疏港的外集卡与陆侧ASC在陆侧I/O点进行交接，对应的载有集装箱的自动导引车AGVs(Automated Guided Vehicles)与海侧ASC在海侧I/O点进行交接。各ASC只能在各自半箱区内作业，跨越半箱区的作业任务均需双ASC利用接力区合作完成，双ASC之间的作业干扰只发生在接力区。假设箱区长度为L贝位，贝位数为0的箱位为海侧ASC与AGV的交接点，贝位数为L+1的箱位为陆侧ASC与外集卡的交接点。海陆两侧ASC作业范围分别跨越半箱区，双ASC分别负责本侧集装箱的装卸作业。堆场作业任务主要分为存箱操作S型(Storage requests)和取箱操作R型(Retrieval requests)两种。将海侧ASC与AGV交接点和陆侧ASC与外集卡交接点均称为交接点，将存箱操作中集装箱的存放位置及取箱操作中集装箱的提取位置均称为目标点。故堆场ASC存箱和提箱作业过程均可简化为4个步骤，如表1所示。

表1 存箱和提箱操作步骤

引入时间-贝位坐标系，其中横轴为各任务的执行时刻，纵坐标为对应集装箱的位置，各操作步骤与图中各曲线段一一对应，如ASC无需移动即可完成存取操作则无对应线段。通过找到坐标中对应线段的分段函数图像交点可简明直观地描述出双ASC之间作业干扰是否发生或发生在何处。双ASC作业干扰问题转化为所有子任务的时间-贝位曲线不相交问题。

符合拆分规则的初始任务经拆分后，子任务之间的干扰只发生在接力区位置，这样可以有效避免双ASC在执行任务时的相互干扰。任意两个紧前紧后关系的子任务i、j在接力区位置的干扰状态均满足图2中4种模式的一种。任务i、j分别由不同的ASC执行，各子任务一经确定，除ASC完成上一任务后移动至下一任务的衔接作业状态不确定外，其余三个连续步骤均随之确定。线段斜率为非负时表示该步骤中ASC处于运动状态，且移动速率为恒值v；线段斜率为0时表示ASC正在执行存取操作，且各操作需固定作业时间τ。

(a) “TT”模式 (b) “ST”模式

每种干扰模式下子任务关系均可能存在两种情形，分别如图2 中虚、实线图形所示。子任务的开始和结束状态分别用“S”和“T”表示，根据ASC在接力区位置执行前后任务的操作步骤。将(a)两种情形定义为“TT”干扰模式，表示双ASC发生干扰时其在接力区位置分别执行的任务i、j均处于结束状态；同理，将(b)两种情形定义为“ST”干扰模式，表示双ASC发生干扰时其在接力区位置分别执行的任务i处于开始状态，任务j处于结束状态；将(c)两种情形定义为“TS”干扰模式，表示双ASC发生干扰时其在接力区位置分别执行的任务i处于结束状态，任务j处于开始状态；将(d)两种情形定义为“SS”干扰模式，表示双ASC发生干扰时其在接力区位置分别执行的任务i、j均处于开始状态。

2 模型建立

为简化流程同时不失一般性，根据问题作以下假设：(1) ASC在箱区两端装卸作业时无需等待；(2) 接力区存储空间足够大；(3) 双ASC匀速移动且速率相同；(4) 双ASC取箱和放箱的固定作业时间相同且为固定值；(5) 忽略ASC加速与减速及小车移动的影响。ASC装卸作业满足以下要求：(1) 双ASC之间需保持一定的安全距离，通常为一个贝位；(2) 双ASC不能同时对同一集装箱执行装卸任务，且拆分后的子任务有明显的先后顺序，即一台ASC将集装箱移动至接力点并安全退出后，另一ASC方能对该集装箱执行下一阶段的操作。

3 遗传算法

3.1 参数设置

某自动化集装箱港口垂岸式堆场采用两端式双ASC布置，两台同型号的轨道吊C1(即海侧ASC)和C2(即陆侧ASC)协同完成作业任务。箱区长度为39贝位，接力区初始位置为第20贝位，第0贝位表示海侧ASC与AGV的交接点，第40贝位为表示陆侧ASC与外集卡的交接点；双ASC匀速移动且速度相同，单位时间(设为1 s)内移动距离为1贝；ASC取箱和放箱的固定作业时间为3 s；两台轨道吊作业干扰只发生在接力区，双ASC间须保持安全距离1贝，显然在数值上有δ=1/v。

3.2 算法设计

遗传算法具有良好的全局搜索能力，它通过模仿自然界的选择与遗传的机理，利用迭代寻求全局最优，并利用其内在并行性，方便地进行分布式计算以加快求解速度，对作业调度类问题具有良好的适应性[14]。

3.2.1 选择

适应度函数由最小化 ASC 作业完工时间的目标函数转化而来，并采用比较经典的锦标赛选择方法选择个体。

3.2.2 编码与解码

在对任务序列进行编号时，初始任务规模为n，则任务i与n+i表示由同一初始任务i拆分而来的子任务，且i为紧前任务。例如当n=4(初始序列为0,1,2,3)时，若任务0,2,3需要被拆分，则子任务序列为(0,1,2,3,4,6,7)，如表2所示。当解码染色体时，由同一初始任务拆分得到的先出现的子任务实际被优先执行或在接力区享有优先权。

表2 任务编号示例

现有10个初始任务，根据任务拆分规则得到18个子任务，由两台ASC协作完成。染色体由两条组成，分别为任务段和ASC段，任务段中的基因分别对应各子任务，ASC编号由各子任务被执行的情况而定，C1需完成[0,2,3,6,9,11,14,17,18]，C2需完成[1,4,5,7,8,10,12,13,16]。染色体编码解码情况如图3所示。

图3 染色体编码解码示意图

3.2.3 交叉

交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力，在遗传算法中起关键作用。本文采用PMX交叉方法，首先随机选择一对父代染色体中几个基因的起止位置，然后交换这两组基因的位置，最后做冲突检测，根据交换的两组基因建立一个映射关系。所有冲突的基因经过映射，形成新一对没有冲突的子代基因。PMX交叉如图4所示。

图4 染色体PMX交叉示意图

3.2.4 变异

染色体包含任务段和ASC段，选择两组等位基因进行变换。变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力。变异运算示意图如图5所示。

图5 染色体变异示意图

3.3 结果分析

3.3.1 算法性能分析

设置6组不同规模的算例对两种算法的性能进行评估，假设接力区处于箱区中间位置(第20贝位)。遗传算法求解时参数设置为种群规模N=200，交叉概率cxpb=0.5，变异概率mutpb=0.1，迭代次数ngen=300，使用相同的参数运算10次取平均值。两种方法求解结果如表3所示。

表3 CPLEX与遗传算法求解不同规模算例性能结果对比

求解过程中，当算例规模较大时，CPLEX运行内存溢出，但仍可以找到可行解。由表3易知，两种算法性能对比发现，即使CPLEX的内存管理非常有效，但是求解较大规模的线性规划问题，内存不足仍然是需要考虑的问题之一，而遗传算法求解大规模算例具有独特优势。

3.3.2 双ASC作业干扰优化分析

当自动化集装箱码头的装卸任务下达后，分配到各箱区的集装箱需要在最短的时间内处理完毕，这对各箱区内设备的集装箱处理能力提出了更高的要求。两台相同的轨道吊在完成各自的装卸任务时往往发生作业干扰。若在箱区中设置接力区，使双ASC通过接力完成集装箱存取操作，即可大幅降低双ASC的作业干扰频率。因此，确定合适的接力区位置、有效避免双ASC作业干扰成为优化堆场作业、提高堆场作业效率的关键。针对第2组实例运用CPLEX和遗传算法对该问题进行求解，并评估两种方法对堆场设备协同调度的优化效果。当变换接力区位置时，求得的不同接力区位置对应的最小总完工时间结果如图6所示。

图6 CPLEX与GA求解结果对比

由图6可知，两种方法所求接力区最优位置均为第18贝位。CPLEX求得的最小总完工时间为218 s，双ASC在作业过程中未发生干扰，求解历时637.53 s；采用遗传算法，每组重复10次运算后取最优值，求得的最小总完工时间为225 s，双ASC在第151 s发生一次干扰，平均求解历时86.033 s。两种算法求得的双ASC作业轨迹分别如图7和图8所示。

图7 exB=18时CPLEX求解双ASC作业轨迹

图8 exB=18时GA求解双ASC作业轨迹

两种方法均找到了相同的最优接力区位置，生成的ASC作业计划不同，且CPLEX求得的解更优，避免了双ASC干扰问题。但遗传算法也有效降低了干扰的发生，并展示出了更高效的求解能力。如果统一采用表2所示的任务编号方式，则CPLEX求得的双ASC作业计划为：

C1：6—9—0—14—2—11—3—17—18

C2：4—5—1—10—7—12—8—13—16

遗传算法求得的双ASC作业计划为：

C1：6—0—9—3—17—11—2—14—18

C2：7—16—1—5—4—13—12—8—10

根据上述两种优化方法，只要给定任意的堆场既定作业任务，均可确定出最优的接力区位置，有效解决双ASC作业干扰问题，并生成各ASC的作业计划，使总完工时间最小。

3.3.3 遗传算法优化分析

当有集装箱船舶靠泊或集疏港相对集中时，自动化集装箱码头往往需要应对大规模的装卸任务。由3.3.1节可知遗传算法是求解该类问题非常有效的方法，因此，对遗传算法的参数设置进行优化也是高效准确求得最优解、快速得到堆场设备调度计划的重要内容。为更直观地反映收敛效果，选择初始任务规模为50的第4组实例进行研究。

当变换迭代次数时，设计50、100、200、300和500五个梯度求解，结果如图9所示。易知当迭代次数取300和500时收敛效果最佳，为提高运算效率，迭代次数取300为宜。同理，通过变换种群规模发现当种群规模为300时收敛效果更佳，结果如图10所示。

图9 不同迭代次数收敛曲线

图10 不同种群规模收敛曲线

对于提高遗传算法求解效率而言，交叉概率cxpb与变异概率mutpb的选取并不是相互无关和独立的，而是存在最优组合问题。针对不同类型的优化问题，所选取的变异率一般随交叉率的增大而呈减小趋势[15]。因此为提高求解效率，设置几组交叉率—变异率组合如表4所示。

表4 交叉率—变异率组合

取种群规模和迭代次数均为300，根据表3得出各交叉率—变异率组合的收敛图像如图11所示。易知当交叉概率为0.4、变异概率为0.1时收敛效果最佳。当接力区位置在箱区中间贝位(exB=20)时，在种群规模为300、交叉概率为0.4、变异概率为0.1条件下迭代300次得到完成该50个任务的最短完工时间为1 046 s，求解过程平均历时241.52 s。经优化，所得结果较表1更优，求解时间也大幅缩短，充分论证了该组遗传算法参数优化结果的有效性。该参数配置下收敛曲线如图12所示，双ASC作业轨迹如图13所示。

图11 不同交叉率—变异率组合收敛曲线

图12 最优参数配置下收敛曲线

图13 最优参数配置下双ASC作业轨迹图

4 结语

双轨道吊作业干扰是自动化集装箱码头堆场存取箱作业同时进行的核心问题，双ASC协同调度优化结果直接影响港口整体运营效率。本文考虑集装箱的堆存和取出两种作业同时进行的情况，设计既定任务下的任务拆分规则，以任务完成总时间最小化为目标，建立双轨道吊协同调度混合整数规划模型，并采用CPLEX和遗传算法对多组算例进行求解，主要结论如下：

(1) 通过评估不同规模任务下求解双ASC协同调度优化问题的算法性能，得出遗传算法更适合求解大规模设备调度问题。

(2) 变换接力区位置，用CPLEX和遗传算法两种方法求解均能找到最优接力区位置，并得到了两台ASC各自的作业计划，充分论证了所提出的模型和算法解决自动化集装箱港口双ASC作业干扰问题的有效性。

后续研究重点为自动化集装箱码头堆场接力区设计如时间窗条件下动态接力区设计等方面。