基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题.pdf

收稿日期:修回日期:作者简介:武艳宇()男硕士生主要研究方向为空间覆盖选址:/基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题武艳宇 成 毅 葛 文(信息工程大学河南 郑州)摘要:覆盖推销员问题()是著名的旅行商问题的一个变体是 难问题 给定一组顶点和每个顶点相关联的预定覆盖半径 的目标是在顶点子集上找到一个最短长度的哈密顿回路使每个顶点被访问或者在被访问顶点的覆盖范围内 为提升搜索候选顶点集的质量提出一种基于多顶点替换的搜索策略并将该策略引入到迭代局部搜索算法解决 所提 算法通过扰动过程和改进过程的迭代探索邻域最优解其中扰动过程将搜索发散到未探索的区域改进过程提升解的质量 实验结果表明多顶点替换方法相比“移出重新插入”过程可以获得更高质量的候选顶点集 所提 算法在寻优的正确率上取得了不错的成效尽管运行速度与其他启发式算法相比有差距但可以在合理的运行时间内解决 关键词:覆盖推销员问题旅行商问题迭代局部搜索启发式算法中图分类号:.文献标识码:文章编号:().第 卷第 期 年 月信 息 工 程 大 学 学 报 .引言旅 行 商 问 题()是一个经典的组合优化问题 中要求推销员访问每个城市然而现实世界许多路径问题不需要所有城市都被访问旅行者可以只访问部分城市而未被访问城市的人群可以去附近被访问的城市获取服务 基于以上考虑 和 引入了 的一种变体 覆盖推销员问题()并将其定义为:给定一组城市和组内每个城市的预定覆盖距离 的目标是在城市子集中确定一个最短长度的哈密顿回路使每个不在回路中的城市被回路中城市覆盖 在应急规划、灾害管理和医疗服务配置等方面有广泛的应用 由于 是子集选择问题和排序优化问题的结合因此它是 难问题 一个可行的 解如图 所示图 实例下的一个可行解此外有许多与覆盖概念相关的组合优化问题可被视为 的变体 例如广义覆盖推销员问题()、广义旅 行 商 问 题()、环星问题()、覆盖旅行问题()、多车辆覆盖旅行问题()等 在这些问题中推销员不需要访问每个顶点只要确保未被访问的顶点都能够被回路中的顶点服务范围所覆盖即可 研究现状由于计算的复杂性现有文献中提出的求解 方法以启发式搜索为主 的启发式算法中大多通过改进回路中顶点组成和改进回路访问候选顶点集的顺序提升解的质量考虑到后类方法已有成熟的 算法解决因此 启发式算法主要是在提升算法对候选顶点集的搜索质量这方面做创新 和 提出的 启发式算法通过解决集合覆盖问题()求出具有最小顶点数的候选顶点集然后对候选顶点集进行排序 等提出两种解决 的局部搜索算法(和)使用了“移出重新插入”操作改进回路中的顶点组成该操作首先移出回路中的一些顶点然后将一些未访问顶点插入到回路使解可行 是迭代局部搜索算法通过扰动过程和改进过程的迭代探索邻域最优解 改进过程通过“移出重新插入”过程提升回路中的顶点组成首先移出回路中的单个顶点如果解仍可行则解的质量得到了改进否则将一个或者两个未访问的顶点插入到回路移出顶点的位置使解可行如果解的质量得到了提升就接受该替换操作此外 和 提出了一种解决 的基于整数线性规划()的启发式方法()使用启发式改进过程和基于 的改进过程探索邻域最优解启发式改进过程中使用了与 相似的“移出重新插入”过程改进回路中的顶点组成 基于 的改进过程首先移出回路中的部分顶点其次生成一些有潜力的顶点序列最后通过求解 模型确定顶点序列分配到回路的最佳位置 等提出了一种解决 的混合蚁群算法()该混合算法结合了蚁群算法和动态规划技术探索邻域最优解 的改进过程中通过两种操作改进回路中顶点组成:移出回路中的冗余顶点在解可行的前提下应用动态规划技术将回路中单个顶点替换为基数为 或 的顶点序列(序列的顶点在未访问的顶点集中选择)近来 等提出了一种解决 的多起点的迭代局部搜索算法()算法重启 多次每次重启都会生成新的初始解 当算法陷入局部最优解时从新的初始解开始搜索可以减少运算 通过移出回路中的冗余顶点改进回路的顶点组成此外算法还引入可变程度的扰动策略提升解的质量 等提出了两种解决 的混合启发式算法 第一种方法是基于人工蜂群算法()第二种方法是基于遗传算法()这两种方法都使用了以下方法改进回路的顶点组成:与 相 第 期武艳宇等:基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题似的“移出重新插入”过程在解可行的前提下将回路中单个顶点替换为基数为 的顶点序列(顶点从所有顶点中选择)或者替换为单个未被访问的顶点 此外 的交叉算子和变异算子通过复制父代的顶点给子代以形成可行的回路然后清理子代回路中的冗余顶点改进回路中顶点组成等设计了两个解决 的并行变邻域搜索启发式 算 法()算法使用了与 相似的“移出 重新插入”操作改进回路中的顶点组成 等提出了一种解决 的混合进化算法()的交叉过程和变异过程通过复制父代的顶点给子代形成了可行的尚需改进的回路 使用两阶段的禁忌搜索改进回路的顶点组成 第一阶段在回路逐个增加顶点使解可行第二阶段在回路可行的前提下移出回路中单个冗余节点或者将回路中单个顶点替换为未被访问的顶点综上 启发式算法中已有很多通过改进回路的顶点组成提升解的质量的方法 为提升算法对候选顶点集的搜索质量提出了一种基于多顶点替换的候选顶点集搜索策略并将该策略引入迭代局部搜索算法求解 问题建模给定一个有向图 ()其中:是必须被访问或者被覆盖的顶点集合()是弧的集合 代表弧()的长度 定义 为可以覆盖顶点 的顶点集合 定义以下变量:如果回路经过弧()其他情况.如果回路访问顶点 其他情况.的数学模型表示如下:()受到以下条件约束:()()()()()()式()是目标函数其为最小化回路长度 式()确保被回路中每个顶点只被访问一次 式()确保每个顶点被访问或者至少被回路中一个顶点覆盖 式()消除回路中的子环路 式()和式()定义了模型中的所有变量 迭代局部搜索算法迭代局部搜索()是一种单种群的启发式算法它通过迭代过程逐步提升解的质量 有许多令人满意的特性:简单、易于实现、健壮和高效提出的基于多顶点替换的寻优策略()如算法 所示 首先应用初始化解()的函数产生可行解其次应用改进过程提升解的质量包括使用多顶点替换过程()改进回路的顶点组成使用 算法的函数改进回路访问候选顶点集的顺序最后应用扰动过程()的函数将搜索发散到未探索的区域 算法通过改进过程和扰动过程的迭代探索邻域最优解算法 迭代局部搜索算法输入:最大迭代的次数:从解中移出顶点的数量:控制插入顶点的候选范围:插入到回路中的顶点数量 实例输出:.().().()()/函数输出回路解的路径长度/.().改进过程 方法通过两种改进操作提升解的质量:使用多顶点替换过程()将回路中多个连续的顶点替换为有潜力的顶点集合以改进回路解的顶点组成如算法 所示使用 信 息 工 程 大 学 学 报 年算法改进回路访问候选顶点集合的顺序算法 多顶点替换过程输入:可行解 输出:回路解 或.()/()为解 中顶点的数量/.()/移出 第 到第()位之间的顶点是移出的顶点的集合 是移出顶点后未被访问和未被覆盖的顶点的集合/.回路 是可行解.将距离每个顶点 的最近的 个顶点 汇总为集合.()/识别满足()和 条件的无序组合 并将组合汇总为集合 其中()输出集合 覆盖的顶点集合/.()/计算每个组合 以不同顺序插入到回路 中移出顶点的位置上的成本确定最小插入成本的组合及其顺序并将该组合以此顺序插入到回路 中移出顶点的位置上/.()时 方法在运行精度上有些许提升运 第 期武艳宇等:基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题行时间超出可接受的范围替换顶点的数量 比较合适 结束语作为 难问题当前覆盖推销员问题的解决仍以各类启发式算法为主此类算法大多通过改进回路中的顶点组成等方法来提升解的质量 为了提升对候选顶点集的搜索质量提出了基于多顶点替换的搜索策略 在中小型实例上的实验结果表明多顶点替换策略尽管运行时间相比 的“移出重新插入”过程有所增长但是可以获得更高质量的候选顶点集 引入多顶点替换策略的迭代局部搜索算法在寻优的正确率上取得了不错的成效尽管运行速度与其他启发式算法相比仍有差距但可以在合理的运行时间内解决 未来的工作中希望进一步降低算法的计算复杂度使得算法兼顾运行精度和运行速度并在大型案例上进一步测试算法的性能参考文献:.():.():.():.():.:.():.():.():.():.:.:.():.():.:.:.():.:.():.(编辑:李志豪)信 息 工 程 大 学 学 报 年