·453· 齐小刚，等：多中心维修任务分配研究现状1111 第3期 群算法对多无人机进行了任务分配：Jia等6创基于 33路径规划 遗传算法对异物无人机进行了任务分配；Keiser 维修任务分配确定任务承担者，路径规划确 等62首创并使用多维列表规划来获取任务之间 定完成路径。任务划分是维修任务分配的基础， 的匹配方案，从而更好地全局最优化任务分配的 路径规划是其重点。维修任务规划是寻找最佳分 解；Khouadjia等s结合DAPSO算法、VNS算法 配方案的问题。二者相互结合，相互影响，共同 对动态的需求问题进行了车辆送货的任务分配。 决定分配的最终结果。 Jia等6设计并应用了一个计算机辅助系统 装备维修任务路径规划可抽象为车辆规划最 来解决军械维修中的任务分配，但没有对典型案 短路线遍历所有目标点的问题，此即为车辆路径 例进行分析。Yuan等6的关于任务分配构建了模 问题(vehicle routing problem,VRP)。VRP随约束 型，并以蒙特卡洛法研究了石油装备维修。李龙 的增加而发展。文献[73]研究了有车辆负载能力 跃等6对多波目标分配反导进行了研究，关于分 上限约束的VRP问题。文献[74]研究了电动车 配导弹-目标的模型由此建立，但未考虑不确定性 辆的VRP,考虑电容量的约束，并将规划结果与 与可靠性等因素。曾家友等61对分配舰载导弹 燃油汽车进行了对比。文献[75]详细分析了VRP 的目标进行了研究，考虑了价值收益、效费比优 中的最优速度、垃圾倾倒、长距离运输问题，区分 先级排序等问题；Yang等s在遗传算法中引入随 了时间安排原则。文献[76]考虑了无冲突VRP 机移民、二元论等，可用于动态任务分配问题。 以解决后勤运输路径规划的冲突和死锁问题。文 3.2.2常用典型算法简介及对比 献[77]对多配送中心动态VRP给予了优化，采用 局部搜索算法是一种重要的求解组合优化问 智能优化可解决VRP这种NP问题。文献[78]使 题的启发式算法，由于简单且易于理解，其已受 用改进遗传聚类解决了多中心配送VRP问题。 到越来越广泛的重视。常见有2-0pt、2-0pt*等6。 文献[79]使用并行模拟退化来解决同时发送和取 模拟退火算法的思想最早由Metropolis等于 货的VRP问题。文献[80]采用变邻域下降算法 1953年提出，后由Krikpatrick69于2002年第一次 来求解两级VRP问题。文献57]使用混合遗传 用于求解组合优化问题。此算法以一定概率选择 算法来解决存在车辆租借、共享等条件的多个中 邻域中的劣质解以克服其他算法易陷入局部最优 心配送的VRP问题。并行运算、可全局搜索的蚁 的缺陷和对初值的依赖。 群算法衍生出了混合蚁群算法⑧)、量子蚁群算 20世纪60年代，Holland0提出了遗传算法， 法81、蚁群系统]和最大-最小蚂蚁系统(max 随机生成初始种群，通过选择、交叉、变异产生更 min ant system,MMAS)等。解决离散时间最佳 适应环境的个体以得到优化解。我国遗传算法 路径规划的方法—MMAS可进一步改进。VRP 从20世纪末开始研究且迅速膨胀。罗雄等对 和装备维修任务路径规划问题均选择最佳路径以 遗传算法解决柔性作业、车间调度问题进行了综 实现某一目标，但是又存在一定差异： 述。刘国强四根据任务分配特点，采用多目标遗 1)决策目标不同：VRP追求路径（时间）最小 传算法解决了维修任务分配问题。 化，任务路径规划则追求维修效益最大化。 上述启发式算法对比如表3所示。 2)约束条件不同：VRP及其衍生问题多以车 表3启发式算法间的对比 辆的载重、最大航程、存储容量等为约束，且此问 Table 3 Comparison of heuristic algorithms 题中车辆一般要经过所有服务点；而任务路径规 算法 搜索策略 影响因素 适应范围 划是解决作战时维修的问题，不必接受所有维修 在当前解邻域中搜 任务。 局部 受初始解、 局部搜索能 索其他解，若更优 搜索 邻域等因 则替换当前解。 力、求精 4结束语 算法 重复搜索。 素影响。 能力强。 综上所述，已有的工作对维修任务分配问题 模拟 采用Metro-polis原则， 退火 以冷却参数控制算法 受初始解、 局部搜索能 进行了深入研究，但在装备维修任务分配的模型 算法 进程，可以在多项式 Metro-polis接 力、全局搜索 和算法方面还存在一定的不足，有待进一步开 时间内找到近似解。 受原则影响。 能力强。 展，具体表现如下： 遗传 通过群体的遗传（选 受遗传策 1)目前关于装备维修任务分配的研究甚少， 算法 择、交叉、变异)实现 全局搜索 略的影响。 能力强。 装备维修保障任务品种多、约束多，资源有限时， 进化性探索。 能使系统体系平稳运行的装备优先修复。现研究群算法对多无人机进行了任务分配；Jia 等 [61] 基于 遗传算法对异物无人机进行了任务分配；Keiser 等 [62] 首创并使用多维列表规划来获取任务之间 的匹配方案，从而更好地全局最优化任务分配的 解；Khouadjia 等 [63] 结合 DAPSO 算法、VNS 算法 对动态的需求问题进行了车辆送货的任务分配。 Jia 等 [64] 设计并应用了一个计算机辅助系统 来解决军械维修中的任务分配，但没有对典型案 例进行分析。Yuan 等 [65] 关于任务分配构建了模 型，并以蒙特卡洛法研究了石油装备维修。李龙 跃等[66] 对多波目标分配反导进行了研究，关于分 配导弹-目标的模型由此建立，但未考虑不确定性 与可靠性等因素。曾家友等[67] 对分配舰载导弹 的目标进行了研究，考虑了价值收益、效费比优 先级排序等问题；Yang 等 [68] 在遗传算法中引入随 机移民、二元论等，可用于动态任务分配问题。 3.2.2 常用典型算法简介及对比 局部搜索算法是一种重要的求解组合优化问 题的启发式算法，由于简单且易于理解，其已受 到越来越广泛的重视。常见有 2-Opt、2-Opt*等 [63]。 模拟退火算法的思想最早由 Metropolis 等于 1953 年提出，后由 Krikpatrick[69] 于 2002 年第一次 用于求解组合优化问题。此算法以一定概率选择 邻域中的劣质解以克服其他算法易陷入局部最优 的缺陷和对初值的依赖。 20 世纪 60 年代，Holland[70] 提出了遗传算法， 随机生成初始种群，通过选择、交叉、变异产生更 适应环境的个体以得到优化解。我国遗传算法 从 20 世纪末开始研究且迅速膨胀。罗雄等[71] 对 遗传算法解决柔性作业、车间调度问题进行了综 述。刘国强[72] 根据任务分配特点，采用多目标遗 传算法解决了维修任务分配问题。 上述启发式算法对比如表 3 所示。 表 3 启发式算法间的对比 Table 3 Comparison of heuristic algorithms 算法 搜索策略 影响因素 适应范围 局部 搜索 算法 在当前解邻域中搜 索其他解，若更优 则替换当前解， 重复搜索。 受初始解、 邻域等因 素影响。 局部搜索能 力、求精 能力强。 模拟 退火 算法 采用Metro-polis原则， 以冷却参数控制算法 进程，可以在多项式 时间内找到近似解。 受初始解、 Metro-polis接 受原则影响。 局部搜索能 力、全局搜索 能力强。 遗传 算法 通过群体的遗传(选 择、交叉、变异)实现 进化性探索。 受遗传策 略的影响。 全局搜索 能力强。 3.3 路径规划 维修任务分配确定任务承担者，路径规划确 定完成路径。任务划分是维修任务分配的基础， 路径规划是其重点。维修任务规划是寻找最佳分 配方案的问题。二者相互结合，相互影响，共同 决定分配的最终结果。 装备维修任务路径规划可抽象为车辆规划最 短路线遍历所有目标点的问题，此即为车辆路径 问题 (vehicle routing problem, VRP)。VRP 随约束 的增加而发展。文献 [73] 研究了有车辆负载能力 上限约束的 VRP 问题。文献 [74] 研究了电动车 辆的 VRP，考虑电容量的约束，并将规划结果与 燃油汽车进行了对比。文献 [75] 详细分析了 VRP 中的最优速度、垃圾倾倒、长距离运输问题，区分 了时间安排原则。文献 [76] 考虑了无冲突 VRP 以解决后勤运输路径规划的冲突和死锁问题。文 献 [77] 对多配送中心动态 VRP 给予了优化，采用 智能优化可解决 VRP 这种 NP 问题。文献 [78] 使 用改进遗传聚类解决了多中心配送 VRP 问题。 文献 [79] 使用并行模拟退化来解决同时发送和取 货的 VRP 问题。文献 [80] 采用变邻域下降算法 来求解两级 VRP 问题。文献 [57] 使用混合遗传 算法来解决存在车辆租借、共享等条件的多个中 心配送的 VRP 问题。并行运算、可全局搜索的蚁 群算法衍生出了混合蚁群算法[81] 、量子蚁群算 法 [82] 、蚁群系统[83] 和最大–最小蚂蚁系统 (max￾min ant system, MMAS)[84] 等。解决离散时间最佳 路径规划的方法−MMAS 可进一步改进。VRP 和装备维修任务路径规划问题均选择最佳路径以 实现某一目标，但是又存在一定差异： 1) 决策目标不同：VRP 追求路径 (时间) 最小 化，任务路径规划则追求维修效益最大化。 2) 约束条件不同：VRP 及其衍生问题多以车 辆的载重、最大航程、存储容量等为约束，且此问 题中车辆一般要经过所有服务点；而任务路径规 划是解决作战时维修的问题，不必接受所有维修 任务。 4 结束语 综上所述，已有的工作对维修任务分配问题 进行了深入研究，但在装备维修任务分配的模型 和算法方面还存在一定的不足，有待进一步开 展，具体表现如下： 1) 目前关于装备维修任务分配的研究甚少， 装备维修保障任务品种多、约束多，资源有限时， 能使系统体系平稳运行的装备优先修复。现研究 ·453· 齐小刚，等：多中心维修任务分配研究现状 1111 第 3 期