岸桥故障下考虑邻近岸桥共享...的集装箱码头调度多目标优化_吴暖.pdf

第 卷第期计算机集成制造系统 年月 ：收稿日期：；修订日期：。；基金项目：辽宁省社会科学规划基金青年项目（）。：，（）岸桥故障下考虑邻近岸桥共享作业的集装箱码头调度多目标优化吴暖，吴迪，王诺（大连交通大学 交通运输工程学院，辽宁大连 ；大连海事大学 交通运输工程学院，辽宁大连 ）摘要：针对岸桥故障等原因引起的码头调度方案重新调整的实际问题，对邻近船舶采用岸桥共享作业的方法，以船舶作业时间最短和码头作业成本最低为目标建立多目标优化模型，利用混合式多点交叉和混合式单点变异方式改进 算法，并融入岸桥共享原则的邻域搜索策略。为寻找满足决策者偏好的调度方案，在兼顾船公司和港口方利益基础上，利用 前沿分布信息，采用 非劣解相对于各优化目标的偏向量化方法，得到了适合决策者偏好的最终方案。最后，以我国某集装箱码头为例验证了所提模型和算法的可行性；通过算法对比，显示改进后的算法更为有效。该研究成果可为提高港口管理水平提供决策依据。关键词：集装箱码头；岸桥故障；调度；多目标优化；算法中图分类号：文献标识码：，（，；，）：，（），：；计算机集成制造系统第 卷引言岸桥是集装箱码头装卸作业最主要的装卸设备，一旦在作业过程中发生故障，将会直接导致船舶装卸作业中断，延误船舶离港时间，严重影响港口的作业效率。因此，如何在岸桥发生故障后，迅速调整作业计划，尽可能减少对船舶航程的影响，降低码头作业成本确定符合港口和船公司利益的最终方案，对于提高码头管理水平具有重要意义。关于非正常情况下集装箱码头调度的优化，国内外学者已进行了诸多研究，如不确定环境下的泊位岸桥调度，集装箱码头的干扰应对调度，港口临时停产后恢复的应急调度等。关于码头作业系统中设备故障的影响，已有少数研究从不同角度进行过分析，如岸桥故障情况下单船装卸的多阶段再调度，基于前景理论的岸桥受干扰重调度等，但考虑以岸桥共享方式来降低设备故障影响的研究很少。实际中，码头调度会采用邻近泊位的岸桥共享作业方式以减少岸桥的启动数量实现降低成本的目的。岸桥出现故障后对船舶靠泊和码头作业的计划都会受影响，因而需兼顾港口和船公司的利益，建立多目标优化模型予以解决，求解时将多目标转换成单目标是最常用的求解方法，若直接求解多目标优化模型，则需额外补充决策偏好 ，或在 非劣解集中寻优，确定最终方案 。理论上，岸桥故障下的集装箱码头调度包含了泊位调度、岸桥分配等 问题，精确算法已无法满足求解要求，需利用启发式算法予以解决。对此，快速非支配排序遗传算法（，）具有收敛快、计算效果良好等优点，已成功应用于集装箱码头港口与泊位协同调度、多目标连续泊位分配 等优化中，但该算法收敛精度不佳，且算法编码无法直接满足岸桥共享的求解需求，因而还需要做进一步改进。综合以上研究特点和存在问题，本文针对岸桥故障的集装箱码头调度问题，从兼顾港口方和船公司共同利益出发，开展了岸桥故障下考虑邻近岸桥共享作业的集装箱码头调度多目标优化研究，主要工作包括：针对岸桥故障问题以最小化船舶作业时间和最小化码头作业成本为目标，建立多目标优化模型；针对研究问题和模型特点，以混合式多点交叉和混合式单点变异改进 算法，融入考虑岸桥共享作业的邻域搜索策略予以求解，得到 非劣解；利用 前沿分布信息，求解各 非劣解的偏向度，结合决策者偏好，得到满足决策者需求的最终方案。最后，以我国某集装箱码头为背景，验证了所提模型和算法的有效性。模型构建 问题描述及假设当岸桥发生故障时，其所服务船舶的作业便会受到影响，有可能因此延迟船舶离港时间，同时，后续到港船舶因前序延误船舶无法按时离港，也会受到影响。对于港口方，为抢回被耽误的时间，则可能需要“外借”邻近泊位的岸桥进行共享作业。岸桥共享作业是指岸桥在作业过程中，所作业船舶未离开泊位便接着移至临近泊位为其他船舶提供服务的作业过程。因为岸桥共享作业是一种接续过程，所以可以节省设备启动成本，但由于对不同船舶实行接续作业在时间上安排过于紧凑，容易耽误船期，降低船公司服务满意度，需要谨慎决策。本文面临的选择是：由于重新开动备用岸桥，港口需要付出额外的启封、开机、温车等启动成本，当出现岸桥故障影响生产时，是按照船公司的愿望立即调动备用岸桥补位尽快完成装卸作业，还是在满足船舶按时离港的前提下，利用已工作岸桥作业的时间差对不同船舶实现共享作业，以减少港口额外作业成本便成为港口面临的决策问题。对此，要同时兼顾船公司方和港口方的利益调整调度方案，就需构建多目标优化模型分析解决。为简化分析，本文作如下假设：各岸桥的作业互相独立，即故障岸桥不会影响其他岸桥的作业效率；船舶作业效率与配备的岸桥数量成正比；岸桥的调动不发生跨越；岸桥的启动时间和移动时间忽略不计。模型建立 符号定义为便于表达，有关参数变量定义如下：（）参数为调度期内船舶集合；为调度期时间集合；为调度期内岸桥集合；表示码头岸线长度；为船舶总量；为岸桥总量；第期吴暖 等：岸桥故障下考虑邻近岸桥共享作业的集装箱码头调度多目标优化、均为船舶编号，且，；为船舶原定到港时刻；为船舶期望离港时刻；为船舶原定靠泊位置；为船舶船长；为船舶的安全靠泊距离要求；为船舶到港装卸箱量；、分别为船舶可允许的最大、最小作业岸桥数量；为岸桥单位时间装卸量；为正常作业的岸桥编号，其集合为，即；为发生故障的岸桥编号，其集合为，即，有且；为调度期内的某一时刻，；为岸桥 发生故障的时间集合，；、分别为时刻岸桥和岸桥 的移动距离，；为船舶偏离最佳靠泊位置的单位作业成本；为岸桥的启动成本；为岸桥单位时间的作业成本；为岸桥移动成本；为足够大的常数。（）决策变量为船舶实际靠泊位置；为船舶实际作业开始时刻；为船舶实际作业完成时刻；、均为变量，若时刻岸桥、岸桥 正为船舶服务，则取值为，否则为；为变量，在时间维度上，船舶的实际作业完成时间早于船舶 的实际作业开始时间，即 时，否则 ；为变量，在位置维度上，船舶靠泊于船舶 左侧，即 时，否则 ；为变量，时刻新启动岸桥，此时取，否则；、均为变量，若时刻岸桥、岸桥 移动至船舶，则取值为，否则为。数学模型基于前文分析，当岸桥发生故障后，码头可考虑采用邻近岸桥共享作业的方式，综合权衡船公司和港口方的利益损失制定新的调度方案。（）考虑船公司利益，以作业时间最短为目标之一。考虑到集装箱班轮特点，船公司希望自身运输计划不受岸桥故障的影响，希望尽快完成装卸作业，故该目标可表达为：（）。（）（）考虑港口方利益，以作业成本最低为另一目标。由于岸桥发生故障后，港口方需要重新调整作业计划，其措施包括船舶移泊、增加作业设备、岸桥共享等，故该目标可表达为：（）（）。（）式中：第一项为船舶移泊的额外成本，第二项为设备启动成本，第三项综合装卸作业成本，第四项为岸桥移动成本。结合实际工况，其相关约束条件如下：，；（），；（）（），；（）（），；（），；（），；（），且；（），；（），；（），；（），；（）（），；（），或，。（）其中：式（）限制船舶作业时间，即到港后方可开始作业；式（）保障船舶在预期内离港；式（）式（）保证所有船舶在时间和位置维度上均无冲突；式（）限制船舶靠泊需在有效岸桥范围内；式（）保证无故计算机集成制造系统第 卷障条件下，任一时刻作业岸桥数量不超过岸桥总量；式（）保证岸桥故障后，作业岸桥数量不超过无故障岸桥数量；式（）和式（）保证一台岸桥在同一时刻只服务一条船舶；式（）限制船舶配备的岸桥数量；式（）保证船舶在完成装卸任务后才能离港；式（）限制参数取值。模型求解考虑到前文所建立的多目标优化模型特点，可利用改进的 算法直接求解，得到 非劣解集；为进一步兼顾船公司和港口方利益，利用 前沿的分布信息，采用最优解选择的方法，确 定 能 使 船 公 司 和 港 口 方 均 满 意 的 调 度方案。非劣解计算带精英策略的快速非支配排序遗传算法（）是在 算法基础上，引入了快速非支配排序、拥挤距离比较算子和精英选择策略。为求解本文模型，实现岸桥在作业过程中的移动和共享问题，还需进一步对算法进行改进，以便融入岸桥共享策略，提高算法运行效率。算法设计和改进结合 前 文 分 析，对 算 法 进 行 如 下改进：（）编码和解码考虑到数学模型中决策变量包含船舶靠泊顺序、位置 和 所需岸 桥情况，故将 染 色 体 长 度 设 定。为方便编码，各部分均采取整数编码，具体方法如下：设前位基因为船舶靠泊顺序，数值越小表明所对应船舶靠泊优先级越高，最大值为船舶总量；第 位基因为船舶的实际靠泊位置，最大值为岸线长度；第 位基因为船舶实际配备的岸桥数量，数值大小取决于可允许的最小、最大作业数量 和 。如图所示，计划期内靠泊条船舶，船舶靠泊的先后顺序为，其所对应的靠泊位置分别 为 、和 ，配备的岸桥数量分别为、和。（）初始种群为满足各决策变量的约束限制，保证初始解的可行性，在初始种群生成过程中，各层基因生成方式如下：前位基因以船舶数量为限，随机生成不重复的数列；第 位基因为船舶靠泊位置，在岸线长度范围内随机生成；第 位基因为岸桥数量，在可允许的最小、最大作业数量 和 范围内随机生成。（）遗传操作在 算法中，遗传操作包括选择、交叉和变异。在本文算法构建中，选择操作仍采用精英选择策略。为减少交叉、变异过程中产生的不可行解，对传统方式进行如下改进：）交叉操作。考虑到模型所对应的染色体取值特点，保证各船相关决策的联动性，交叉操作采用混合式多点交叉，即前位基因采用颠倒交叉点之间基因顺序的方式；第 位基因为保留传统两点交叉方式，具体操作如下：首先，在染色体长度范围内生成随机数和（其中），确定交叉点；其次，前位按颠倒交叉点范围内所有基因排序（如图），同时按传统两点交叉方式，交换父代的第 位基因（如图）。）变异操作。参照交叉操作，变异操作采用混合式单点变第期吴暖 等：岸桥故障下考虑邻近岸桥共享作业的集装箱码头调度多目标优化异方式，即第一层采取调换变异点与随机任一其他位置基因的方式；其余层采用传统单点变异操作方式，具体操作如下：首先，在染色体长度范围内生成随机数，确定为变异点，并生成另一个随机数（且，）；其次，前位交换和位置基因（如图），第 位按取值范围随机生成满足条件的基因替换原基因（如图）。（）邻近岸桥共享策略为降低码头作业成本，考虑相邻泊位岸桥对不同船舶装卸进行共享作业，对作业过程中的岸桥重新调度，为此，需在 算法基础上融入岸桥共享策略的邻域搜索，具体方法如下：）选择参与岸桥共享的船舶，即在所配备岸桥数量超过台的船舶中随机选择船舶；）判断相邻泊位船舶靠泊时间上是否满足共享条件，即判断船舶 靠泊相邻泊位的船舶到港时间是否早于船舶离港时间，若，则进入下一步，否则，结束搜索；）判断相邻泊位船舶靠泊位置是否满足共享条件，若在共享岸桥作业范围内，则实现岸桥在船舶和船舶 之间的共享。计算步骤综上分析，结合本文模型特点，合理设置染色体编码和解码，改进交叉、变异操作，融入岸桥共享策略的邻域搜索，实现多目标优化模型的求解，获得 非劣解集，具体计算步骤如下：步骤算法初始化，确定 算法基本参数，输入船舶信息，以及岸桥故障情况信息；步骤依据船舶信息，对染色体进行编码，随机生成初始种群；步骤对种群中所有个体进行非支配分层排序，并计算拥挤距离；步骤依据选择规则，在种群选择合适个体，利用本文所提出的混合式两点交叉和混合式单点变异方式进行交叉和变异，得到子种群；步骤选择合适船舶，对种群进行邻域搜索，考虑船舶的岸桥共享，得到新子种群；步骤合并种群和子代，利用精英策略确定下一代种群；步骤判断算法终止条件，若不满足条件，转步骤；步骤算法结束，得到 非劣解集。最优解选择利用上述改进 算法求解多目标模型后，可得到一组无法直接比较优劣的 非劣解。按前文分析，岸桥故障下需要寻求船公司和港口方的平衡，即在满足船舶按时离港的同时降低作业成本。依据文献 的求解思路，依托 前沿分布特征，得到各 非劣解对各优化目标的偏向度，结合决策者对于各优化目标的偏好，求解对各优化目标偏向度最接近，即偏向度差值最小的解，便是能使船公司和港口方均满意的调度方案，在满足船公司尽可能按时离港的前提下降低港口方作业成本。为便于分析，设得到的