基于改进遗传算法的自动化港口贝位两侧进出箱模式下场桥调度模型研究

叶军，罗浩铭，张先燏

（1.上海振华重工（集团）股份有限公司，上海 200125；2.上海交通大学机械与动力工程学院，上海 200240）

0 引言

目前我国在自动化集装箱港口核心技术智能化管理与控制系统领域刚刚起步，与发达国家相比经验与技术基础还相对薄弱，需要实现港口运营的数字化、信息化和智能化，以突破国外技术壁垒，打造自主品牌。

自动化港口设备智能管理与控制系统主要包括整体调度、集卡调度、流机调度和场桥调度4个部分，如图1 所示。其中场桥调度关系到集装箱在堆场中的运输效率，需要结合堆存管理、集卡、流机调度和总体调度等，在合适的时机需要选择合适的场桥，在调度过程中同时解决场桥间的协同作业问题，实现合理避让，以提高作业效率。

图1 自动化港口示意图Fig.1 Schematic diagram of the automated port

近年，国外学者研究了一些有关集装箱码头场桥调度问题的方案。He 等[1]研究了场桥调度与岸桥调度的综合问题，并将问题表述为混合整数编程模型（MIP），综合考虑了场桥、岸桥在运行过程中能量消耗。同时，整合了遗传算法和粒子群算法进行求解。Galle 等[2]将集装箱码头堆场中场桥调度问题与集装箱搬迁问题相结合，考虑了安排存储、检索和搬迁请求以及决定存储和搬迁位置等因素，提出了一个启发式的局部搜索方案来进行求解。Kim 等[3]研究了码头起重机的调度问题，建立了混合整数算法模型，该模型考虑了与起重机运行过程相关的各种约束，通过一种启发式搜索算法来获取最优解。Gharehgozli 等[4]研究了单场桥的调度问题，以场桥移动的时间作为目标函数，并应用了精确算法，为后续学者的研究提供了重要参考。Ma 等[5]考虑到了在实际场桥作业任务中的时间不确定性问题，并建立了两阶段的随机混合整数模型，对小规模的实例提出了一个整数L 型方法，对大规模的实例采用模拟退火算法进行求解，对场桥实际运作有较好的模拟与优化能力。Mark 等[6]研究相邻场桥之间的干扰问题，这种干扰会导致一台场桥的移动被相邻的场桥所阻挡，通过使场桥完成所有调度任务花费时间最短建立了相应数学模型，提出了一种新的混合优化算法，通过结合遗传算法和禁忌搜索方法（GATS）进行求解，在遗传算法的基础上将任务时间减少了20%。

国内也有很多学者针对场桥调度问题开展了相关研究。例如，针对进口箱堆场的拥塞问题，郑红星等[7]研究了两部场桥运作下的场桥调度问题，设计了相应数学优化模型，针对遗传算法中部分子代不可行的问题引入检测修复算子，自动修正任务编码序号来获得可行方案。初良勇等[8]对港口集装箱场桥的调度问题进行系统化研究。他们研究了整片箱区的调度优化模型，多方面考虑了轨道吊移动距离、时间以及场桥运行过程中产生的各种等待时间等因素，最终使模型更符合现实情况。由韩晓龙等[9]提出，以总用时最短为目标的场桥装载调度任务混合整数规划模型可通过启发式算法或模拟退火算法求解，研究表明，随着贝位数和集装箱种类的增多，使用模拟退火算法可节省更多时间。郑宇超等[10]同时考虑了场桥调度作业过程中的能源消耗与工作效率两方面的问题，通过转换场桥调度问题模型来进行求解，使得场桥调度模型求解结果更精确。尹延冬等[11]针对集卡到达时间不确定的问题，将由此产生的捣箱问题加入到数学模型中，构建了基于领域搜索的启发式算法，最后设计了多种算例实验验证了模型的有效性。

综上所述，当前已出现多种解决自动化集装箱港口场桥调度问题的方法。然而，场桥调度是NP 难问题，且集装箱在堆场中涉及复杂的作业流程，不同调度方案对总成本影响很大。因此，研究结合不同场景与不同调度策略来优化场桥调度方案具有重要意义。

1 问题描述

自动化集装箱港口作业任务基本由以下几种类型组成：岸桥的装船任务、卸船任务，闸口的进、提箱等任务，以及场桥的集装箱搬运任务。其中岸桥与场桥是集装箱港口码头中最关键的设备，承担了主要的集装箱搬运任务。岸桥的装、卸船任务在系统中被纳入桥机作业计划（CWP）中，由于需要保证船期即岸桥的作业效率，装、卸船任务的作业需要按照CWP 保证其执行效率。而对于进、提箱任务，码头一般对外集卡有最晚服务时间的承诺，相关设备如图2 所示。

图2 岸桥与场桥自动化设备与集成Fig.2 Automation equipment and integration for shore crane and yard crane

针对场桥的进、提箱任务通常采取的策略一般是场桥优先服务先到达的集卡，这种策略的优势在于能较好地避免部分集卡的等待时间过长，同时，也便于整体调度与管理。本文研究的场桥调度问题中场桥对于集卡的服务策略采用先到先得策略。

在集装箱码头中每一个集装箱所在的位置都有一个相应的编号，而编号包含了该集装箱所在的箱区、贝位、列、层4 种位置信息。场桥能在箱区中进行移动，完成处在不同位置集装箱的搬运任务。

本文研究的场桥搬运场景是建立在贝位两侧进出箱模式的基础上。贝位两侧进出箱模式是指集卡在进行集装箱装卸时，不只在单侧通道，而是在贝位两侧通道同时进行，如图3 所示。在这种情况下，集卡能通过选择不同的通道提前到达目标集装箱所在的位置，避免只存在单侧通道时，集卡需要等待前方集卡完成搬运任务后再到达指定位置的情况，导致集卡不能提前就位，如图4所示。而在贝位两侧进出箱模式下，场桥完成当前搬运任务后，只需移动到下一任务地点，无需等待集卡可能存在的移动时间，使得整体进、提箱任务完成的效率更高。

图3 贝位两侧进出箱模式示意图Fig.3 Double-side of bay mode of transporting container

图4 贝位单侧进出箱模式示意图Fig.4 Single-side of bay mode of transporting container

2 场桥调度模型

2.1 模型的假设条件

为了降低算法的复杂度同时使模型进行简化，设定一些假设条件来对模型进行约束。假设条件如下：

1）考虑1 台场桥情况下的调度情况；

2）所有待操作的任务均位于同一箱区的同一贝位；

3）集装箱所对应的集卡到达后再开始装卸。

2.2 参数设定

场桥调度模型中涉及的参数与相关变量符号如表1 所示。

表1 参数与相关变量Table 1 Parameters and related variables

2.3 目标函数的建立

目标函数如式（1）所示，指在每个任务周期内，完成所有场桥调度任务的时间最小化，最终使得单个任务调度内完成任务的效率最高。

2.4 约束条件

本文建立的模型是混合整数线性规划（Mixed Integer Linear Problem，MILP）模型，式（2）是对决策变量xij与yi之间的逻辑关系进行约束；式（3）是对每个场桥调度任务完成时间的约束；式（4）表示场桥从任务i 移动到任务j 时所花费距离；式（5）表示场桥在任务间移动时花费的时间；式（6）、式（7）通过约束关系确定了任务的相邻情况与任务之间的先后关系，通过设置这两类变量有助于定义简洁的约束方程；式（8）是对任务开始时间的约束，每一个任务至少是在集卡到达泊位后开始，该约束同时考虑了集卡到达箱区的时刻与集卡到达对应集装箱所在位置需要花费的时间，并且，由于本文的研究基于贝位两侧进出箱模式，不需要考虑邻近任务中集卡出现排队的情况。式（9）也是对任务开始时间的约束，场桥作业任务应该在上一个任务完成并且场桥移动到下一个任务位置后再开始；式（10）限制了参数fi，si的符号。

3 算法求解设计

因为场桥调度是NP 难问题，需要设计相应的启发式算法进行求解。本文中使用了遗传算法求解问题，该算法是一种经典的启发式算法。该算法从任何给定的初始种群开始，并通过模拟自然选择、交叉和变异等过程不断更新种群，以获得更优的解决方案。另外，本文在传统的遗传算法的基础上，增加了改进措施。传统遗传算法在每次更新候选集后并没有对子代的选择率、变异率进行调整，依然采用初始设置恒定的参数值。而在遗传算法实际迭代过程中，每代产生的新的种群特征存在差异。针对代际间的差异采取的策略是通过判断子代适应度的离散程度来选择合适的参数。算法流程框图如图5 所示。

图5 改进遗传算法程序框图Fig.5 Improved genetic algorithm program

3.1 染色体编码

图6 是一条染色体，其中的pi代表了单次场桥调度任务的编号，任务编号在染色体中所处的位置对应于场桥调度任务的先后顺序，例如第k个基因片段上的调度任务pi表示任务pi在第k 次场桥调度任务中进行。

图6 染色体编码Fig.6 Chromosome coding

3.2 染色体选择

对染色体进行选择的目的在于防止候选集不断膨胀，避免计算成本不断增加。本文中染色体选择采取的策略是精英策略，保留候选集中完成场桥调度任务总用时较小的子代，同时剔除适应度较大的子代。假设第k 轮迭代的种群大小为n，根据种群适应度的分布情况，选择随机选择的概率ρi和种群保留率γi，下一代初始种群的数量为nγi，通过选出适应度排在前nγi的染色体后，再对新的候选集中染色体按照随机选择概率ρi进行选择，如图7 所示。

图7 染色体选择Fig.7 Chromosome selection

3.3 染色体交叉

结合本文的编码方式，先选出候选集中的两个父代场桥调度方案，选择其中的一个基因片段pi，假设该基因片段分别位于染色体的第m、n 两个位置上，交换基因j 在两个片段上的位置，即交换任务j 在两个调度方案中的执行顺序。需要注意的是，由于基因j 在两个父代染色体上的位置都发生改变，对应于m～n 片段中间的基因片段位置也会同步相应调整，如图8 所示。

图8 染色体交叉Fig.8 Chromosome crossover

3.4 染色体变异

染色体变异的目的与染色体交叉相同，都是为了产生新的种群来寻找更优解。本文采取的染色体变异方式如图9 所示。选取一条父代染色体，交换i、j 两个基因片段之间所有基因片段的顺序，即使任务i 到任务j 之间的所有任务倒序，从而产生新的子代。为了使得算法跳出局部最优解的能力更强，在一次迭代过程中，允许一条染色体进行多次变异。

图9 染色体变异Fig.9 Chromosome mutation

3.5 染色体适应度计算

适应度的计算是对候选集中的调度方案进行评估，本文以式（1）作为适应度函数，通过提取候选集中每条染色体上的场桥调度方案信息，同时代入给定的场景信息，分别计算候选集中各染色体适应度。

4 案例验证

本文以某港口的运行数据为例，每次任务周期内安排20 项场桥调度任务。分别采用传统的遗传算法与改进后的遗传算法进行求解，同时迭代1 000 次，求解出的局部最优解随迭代次数变化如图10 所示。

图10 遗传算法改进前后对比Fig.10 Comparison of genetic algorithms before and after improvement

从最终改进前后求解出的局部最优解来看，改进后的遗传算法求解效果明显优于改进前，最终完成所有调度任务的用时减少了18.8%。从原理上分析，改进后的遗传算法针对代际间适应度表现的差异调整选择、变异的参数，能有效避免在选择、变异过程中丢失种群的多样性，在迭代过程中能减少候选集中结构相似、适应度相近染色体的产生，从而使求解过程中跳出局部最优解的概率增加。

通过仿真验证，本文采用的贝位两侧进出箱模式与改进的遗传算法在传统模型的基础上能有效提高场桥调度任务完成的效率、降低调度所需总时间，提高港口场桥调度效率。

5 结语

本文研究了自动化集装箱港口场桥调度问题。采用贝位两侧进出箱模式来避免场桥调度过程中集卡在单侧通道等待问题。另外，建立了场桥调度优化问题模型，并采用改进的遗传算法求解。分析了每次迭代过程中的适应度离散程度，并相应地调整选择、变异的参数。然后，参考了港口实际运行数据并代入到本文的模型中进行检验。最终案例分析表明，改进的遗传算法相对于传统的遗传算法有明显的改善，在避免迭代过程中局部最优解方面表现得更为出色。