考虑充电因素的自动化集装箱码头AGV任务分配模型.pdf

第 卷第 期运 筹 与 管 理 ，年 月 收稿日期：基金项目：国家自然科学基金资助项目（）作者简介：曾庆成（），通讯作者，男，山东沂南人，博士，教授，研究方向：港口与物流管理；李明泽（），男，辽宁朝阳人，博士研究生，研究方向：港口运作管理；云霄（），女，内蒙古包头人，硕士研究生，研究方向：物流系统优化。考虑充电因素的自动化集装箱码头 任务分配模型曾庆成，李明泽，云 霄（大连海事大学 航运经济与管理学院，辽宁 大连 ）摘要：自动化集装箱码头中，（自动引导车）负责衔接岸桥和场桥两个装卸作业设备，被认为是影响整体效率的关键环节之一。为刻画 充电特征，降低作业成本，提高自动化集装箱码头系统作业可靠性，本文通过时空网络图刻画 运输任务和充电过程，以运输成本最小为目标，构建任务分配优化与充电时机选择模型。为求解模型，基于分支定价算法框架设计求解方法，首先通过 原理将模型分解为基于路径的集合划分主问题和一个存在电量等资源约束的最短路径子问题，其次设计标号修正算法求解。实验结果表明，本文模型算法能够提高模型的求解质量，有效优化 作业顺序并选择合适的充电时机，提升 任务分配方案的可靠性，并进一步分析了最大电池容量、行驶距离的变化对 使用数量、充电次数以及码头作业效率的影响。关键词：自动化码头；自动导引车；任务分配；分支定价算法中图分类号：文章标识码：文章编号：（）：，（，）：，（），：；引言自动化集装箱码头具有绿色环保、人工成本低和可靠性高等优点，已经成为国内外港口发展的热点。年以来，我国先后投产了厦门远海、上海洋山四期、青岛新前湾等自动化集装箱码头。水平运输系统连接泊位作业与堆场作业，是制约自动化码头效率的关键环节之一。由于同时作业的 数量大，而且需要考虑与泊位作业、堆场作业之间协同，以及码头道路容量与作业环境的影响，调度一直是自动化码头运营系统需要解决的关键技术问题。近年来，任务分配、动态路径优化与实时控制方法等领域取得了研究突破，为提高自动化码头作业效率提供了依据。本文在已有研究的基础上，考虑 充电因素，构建 任务分配优化模型。其意义在于：（）充电是 运作中必不可少的环节，考虑充电因素进行 任务分配更符合实际；（）考虑充电因素进行 任务分配优化，可以减少充电浪费的空载距离、进而提高 作业效率、降低码头成本，有利于绿色港口建设；（）考虑充电因素加大了 任务分配模型的求解难度，为此设计了基于分支定价的求解算法，提高了模型的求解速度。文献综述随着自动化码头的发展，调度优化的研究受到国内外学者广泛关注，研究内容涉及 任务分配、路径规划、实时控制等。任务分配解决的关键问题是为每个任务箱分配 ，优化 作业序列 。典型研究如：霍凯歌和胡志华 、马越汇和胡志华 、周静娴和胡志华 针对任 务 分 配 建 立 数 学 规 划 模 型，分 别 考 虑 多 载 、不确定环境 以及时间窗限制 等情况，运用求解器、设计分支定界算法或启发式算法求解。路径规划是针对多 系统，对运输过程中出现的等待、路径冲突、死锁等问题进行解除 ，常见的研究方法有优化控制模型 及设置软时间窗 。实时控制广泛应用于 调度优化中，可以对 任 务 进 行 动 态 分 配 ，实 时 检 测、解 除 冲突 。如 等 分别提出在线学习算法方法对 调度策略实时更新。等 设第 期曾庆成，等：考虑充电因素的自动化集装箱码头 任务分配模型计隐式时空网络图，计算 无冲突路径，并用仿真验证。目前，考虑 充电因素的研究逐步增加。一些学者在 调度过程中考虑 电量因素，建立充电调度模型 ，。如，傅正堂等 研究了基于作业线的情况下，非饱和电量 的合理调配问题。张亚琦等 研究了充电与作业的集成调度问题，设计遗传算法进行求解。综上所述，已有文献大多将 看成集卡，不考虑充电因素；而考虑充电的文献，多以定性、仿真分析或启发式规则为主。本文在已有研究 ，的基础上，研究考虑充电因素的 任务分配问题，旨在提高 任务分配的效率与可靠性。模型 问题描述自动化集装箱码头 的主要作业范围包括岸桥交换区、水平运输区和场桥交换区。作业过程中，负责在岸桥交换区和场桥交换区中间运输作业任务箱，并提前到达交换区，否则岸桥和场桥将产生延迟，影响作业效率。任务分配就是在集装箱装卸作业顺序已知的前提下，为进出口任务箱分配 ，优化 作业任务序列，保证码头的作业效率。本质上是电动汽车，为解决 充电问题，部分自动化码头中建有充电站。充电过 程 需 要 一 定 成 本、时 间 和 空 载 距 离。在 调度中选择合理的时机进行充电，可以降低系统运输成本，增加 利用率。图 自动化码头运输系统示意图本文在岸桥的作业顺序和任务箱堆存位置已知的基础上，构建以 系统运行成本最小为目标的任务分配与充电时机选择模型，为每个作业任务箱分配 并决定充电时机，最终得到含有充电时机的调度方案。模型构建模型假设如下：）岸桥操作顺序和具体操作时间均已知；）、场桥以及岸桥每次只操作一个集装箱；）按照计划作业调度，如提前必须等待且不晚于计划时间到达；）充电站、缓存区容量无限制；）电量消耗与运行距离成一元线性关系；）不考虑 冲突与拥堵因素。本文将 运输过程和充电过程转化为时空网络图的形式，在此基础上建立数学模型进行求解。首先离散充电站的时空关系，为每一个作业任务生成一个虚拟充电任务，构造一个任务时空图（，）。图中参数定义为：表示图上节点，（，）。表示虚拟起始点；表示虚拟终点；表示进出口箱任务的集合，；表示充电任务的集合，。表示从任务 终点至任务 起点的调度时间。表示任务执行时间：对于 ，表示 的作业时间；对于 ，表示充电时间。表示任务开始时间点：代表 的开始时间；代表 的开始时间，可知 与其对应的充电任务满足 。代表任务结束时间，对 ，。表示图上弧的集合，包括 ），均存在 至 的弧；），均存在 至 的弧；），均存在 至 的弧；），若 ，存在 至 的弧；），均存在 至对应充电任务 的弧；），若 ，存在 至 的弧。示例见图 。图 底层时空网络示意图模型参数定义为：表示 行驶速度。表示 最大可用数量。表示 满电后最大运 筹 与 管 理 年第 卷行驶距离。表示网络图中点 到点 的图上距离，规定若 ，则 。表示 固定运行成本；表示 单位距离行驶成本；表示 单次充电成本。可知，图中弧上成本：）从 出发的弧，；）到达 的弧，；）图上其他弧，。决策变量：若某 从点 发后到达点 ，则 ，否则为 。表示在 点时累计行驶距离。得到模型如下：，（），（），（）（），（），（）（），（），（），（），（）其中，式（）为目标函数，表示最小化 系统整体运行成本；式（）（）保证网络图平衡；式（）计算前次充电后的累计行驶距离；式（）表示从充电站初始车站出发的弧的累计距离为零；式（）通过 最大 距 离 限 制 表 示 电 量 约 束；式（）表 示 最大 数 量 限 制；式（）（）定 义 变 量 取 值范围。模型分解本文基于 原理，将上述模型分解为基于路径的主问题和一个存在资源约束的最短路径子问题。（）主问题模型根据网络图可得到 的路径集合，问题转化为找到若干条路径完成作业任务并使总成本最小。为重写模型，参数如下：代表图中 的所有可行路径集合；代表路径 的成本；若路径 经过节点 ，则 为 ，否则为 。决策变量如下：若路径 存在最后解中，为 ，否则为 。于是，得到模型转化如下，称其为主问题（，）：（），（）（），（）其中，式（）为目标函数，最小化 系统整体运行成本；式（）保证每个装卸任务作业一次；式（）表示车辆最大数量限制；式（）定义变量取值范围。（）定价子问题模型令 表示约束（）的对偶价格，代表约束（）的对偶价格，则图上每条弧的检验数：）若 ，珋 ；）若 ，珋 。得到目标函数为寻求检验数最小的最短路径问题。模型如下：（，）珋 （）：（，），（）：（，）：（，），（）：（，），（）约束（）（），（）（）算法设计本文针对考虑充电因素的 任务分配模型，分解得到限制主问题和定价子问题。设计基于分支定价算法的求解算法，在分支定界的搜索框架中反复求解限制主问题和子问题，得到模型的精确解。算法流程本文基于分支定价算法，流程如下：根据岸桥装卸作业计划得到每个装卸任务的开始时间，生成时空网络图。贪婪算法求得初始解带入 中，作为根节点，加入搜索树，根节点求解得到模型下界。搜索节点，令节点目标值与当前下界进行对比。若小于下界，则将节点列池带入 中；若大于下界，则删除该节点。用 对当前主问题求解，得到和 带入子问题。标号修正算法求解子问题，得到珋 的路径集合，若集合不为空，转 ；否则转 。按照 从小至大的顺序将一定数量的路径作为列加入 中，转 。取主问题当前解，若此解为分数，则转 ；若为整数，则转 。删除该节点，运用分支规则对该解分支，得到两个分支节点，加入搜索树中。将此解目标值与当前上界进行比较，若目标值小于上界，则更新上界。第 期曾庆成，等：考虑充电因素的自动化集装箱码头 任务分配模型 若此时搜索树为空，输出当前最后解；若不为空，则转 。贪婪算法求初始解其中 表示当前节点位置，表示 在 点时的累计距离。其余符号定义如下：表示目前未完成任务集，表示可作业的后续任务集，算法流程如下：从起点 开始，令 为 ，为 。生成目前未完成任务集 ，令 为 中开始时间最早的任务，并更新 ，。从 点开始，根据电量限制生成 点的 ，若 ，转到 ；否则，令 为 中弧成本 最小的任务，转到 。若 到 点满足电量限制，则 为，转到 ；否则 返回上一节点，更新 ，转到 。更新 ，。若 满足电量限制，转到 ；否则转到 。返回上一节点，更新 ，。若此时距充电站满足电量限制则转到 ；否则转到 。进行充电，更新 ，令 为，转到 。若完成所有任务箱，则停止算法，检查车辆数；否则转到 。标号修正法对子模型，设计动态规划的标签修正算法进行求解。算法中符号定义如下：状态：（，珋），且 。其中 表示状态的节点，表示累计距离，珋 表示累计成本。拓展规则：对于（，珋），若满足 ，则 可从 点扩展至 点，记为 （，珋 ），其中珋 珋 珋。若 是充电节点，否则 。统治规则：对于同一节点 的两个标签，若 ，珋珋，则 统治，此时删除。参数如下：代表点 的状态集合；表示中对 点可扩展的状态集合；表示待检查节点集合；表示节点 在扩展规则下可扩展的后续节点集合；表示从点 扩展到点 的状态集合。算法流程如下：初 始 化：，其 余 各 点：，。判断 ，若 ，任取点 ，转到 ；否则转到 。判断，若，任取点 ，令转到 ；否则 ，转到 。若，任选状态 扩展到节点 得到 。令 ，转到 ；否则转到 。令，应用统治规则判断。若产生变化，则 。令 ，转到 。结束算法，得到子问题最优解。分支策略当根节点得到非整数解时，运用分支定界算法获得整数解。本文使用 标准分支规则：首先将基于路径的解转化为基于弧的解；其次对分数弧进行分支。算例分析 算法效率分析与比较为验证本文算法的有效性，充电时间假设为 个单位时间，其余数据由真实数据同比例缩小。在用 求解原模型时，线性化处理约束（）（）。结果如表 所示，从目标函数来看，两者求解结果趋近一致，但本文算法求解时间大大优于 ，证明本文算法可以达到目标要求。表 小规模算例求解结果 本文算法 （）（）（）注：其中 表示任务数量、表示目标值，即 运行成本、表示求解时间、（本文算法值 值）本文算法值 、“”表示不能在 小时内得到求解结果、表示两者求解时间差值（本文算法）。运 筹 与 管 理 年第 卷 算例分析（）大规模算例针对自动化码头实际作业情况，设定岸桥平均单箱操作时间为 ，服从正态分布。根据某码头得到实际距离信息，假设 参数如下：为 ，为 元 台，为 元 ，为 元 次。充 电采 用 更 换 电 池 的 方 式，取 为 。问题加入主问题的列数为作业任务数量的两倍，模型中最大车辆数 设为初始解得到的车辆数，具体实验如表 所示。为了清晰地展示本文所设计算法的效率，表 详细列出了计算过程中各环节的数据。表 大规模算例求解结果 问题规模 数量 （）总列数 注：其中 表示松弛问题的下界、表示分枝树中搜索的节点数量、总列数表示解的主问题列池中的列数、（本文算法值?松弛解求出的下界值）下界值 、表示根节点求解时间、表示算法总求解时间，其余名称与表 相同。当岸桥和场桥数量保持 （或 ）不变，随着任务数量从增加时，总成本随之增加。由案例 案例 得知，当任务数量不变，岸桥和场桥数量从 增加至 时，使用数量从 台增加至 台，总成本增加。即当问题规模越大、码头堆存情况越复杂，运行成本也越大。进一步分析，与堆场堆存情况相比，任务数量的增加，对总成本变化的影响较小。因 固定成本远大于充电成本和运输成本，故本文模型算法可以有效选择 数量最少的结果，也更符合码头的实际情况。随着任务箱数量或岸桥、场桥数量的增加，算法总求解时间迅速增加。总列数越多，列生成求解过程越复杂，求解时间越长。在分支阶段，每个节点上均要进行列生成求解。故本文算法复杂度与列生成过程和分支搜索的节点数成正相关，即主问题中列池的总列数越多、分支搜索的节点数越大，算法越复杂，求解时间也越长。最后，通过 值均为 可知，本文提出的分支策略有效。（）最大电池容量分析 最大电池容量是影响 充电时机最重要的因素，电池容量决定了 满电之后得最大运行距离。在 个装卸箱任务、两台岸桥、四台场桥的情况下，针对 最大距离进行灵敏度分析，结果如图 。可以得到：由于运行成本、充电成本小于固定成本，随着最大距离 的减小，算法优先增加充电任务；当最大距离继续减少到一定程度时，才会增加 数量。图 最大行驶距离的影响分析第 期曾庆成，等：考虑充电因素的自动化集装箱码头 任务分配模型 结论本文针对自动化集装箱码头 系统，提出一种优化作业顺序和充电时机的方法。通过构建时空网络图刻画 作业和充电过程，建立了以 系统运行成本最小为目标的任务分配与充电时机选择模型，并设计基于分支定价算法的方法求解模型，最终得到含有充电任务的调度方案。实验结果表明，时空网络图能有效刻画 任务分配和充电问题，基于分支定价算法可以快速、有效的求解模型，选择合理的充电时机，降低系统运行成本。最后，本 文 分 析 了 任 务 数 量 和 码 头 布 局 对 系统运行成本的影响，最大行驶距离对充电次数和数量的影响，为 作业调度提供了新的思路与想法。本文没有考虑缓存区容量限制以及因拥堵导致运输时间的不确定性，进一步的研究可以考虑缓存区容量以及 拥堵情况，使其更贴近实际。参考文献：霍凯歌，胡志华 基于遗传算法的自动化集装箱码头多载 调度 上海海事大学学报，（）：马越汇，胡志 华 不 确 定 环 境 下 自 动 化 集 装 箱 码 头 调度与配置问题 广西大学学报（自然科学版），（）：周静娴，胡志华 自动化集装箱码头 水平作业任务调度优化 大 连 海 事 大 学 学 报，（）：张素云，杨勇生，梁承姬，等 自动化码头多 路径冲突的优化控制研究 交通运输系统工程与信息，（）：杨勇生，崔佳羽，梁承姬，等 基于软时间窗的自动化集装箱码头 路径规划 广西大学学报（自然科学版），（）：，：，（）：傅正堂，胡志华，宗康 集装箱码头 电量非饱和状态下的调度优化 大连海事大学学报，（）：张亚琦，杨斌，胡志华，等 自动化码头 充电与作业的集 成 调 度 研 究 计 算 机 工 程 与 应 用，（）：运 筹 与 管 理 年第 卷