改进蚁群算法优化周期性车辆路径问题.pdf

第 卷 第 期运 筹 与 管 理 ， 年 月 收稿日期：- - 基金项目：国家自然科学基金青年基金项目（，）；教育部新世纪人才支持计划（- - ）；辽宁省优 秀人才支持计划（） 作者简介：于滨（- ），男，大连人，博士，副教授。 研究方向：智能公交，高性能计算。 改进蚁群算法优化周期性车辆路径问题 蔡婉君 ， 王晨宇 ， 于 滨， 杨忠振， 姚宝珍 （ 大连海事大学 交通运输管理学院，辽宁 大连 ； 大连理工大学 机械工程学院，辽宁 大连 ） 摘 要：周期性车辆路径问题（）是标准车辆路径问题（）的扩展， 将配送期由单一配送期延伸到 T（T ）期，因此， 需要优化每个配送期的顾客组合和配送路径。 由于 是一个内嵌 的问题，其 比标准 问题更加复杂，难于求解。 本文采用蚁群算法对 进行求解，并提出采用两种改进措施 多 维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。 最后，通过 个经典 算例对该算法进 行了数据实验，结果表明本文提出的改进蚁群算法求解 问题是可行有效的，同时也表明两种改进措施可 以显著提高算法的性能。 关键词：周期性车辆路径问题；蚁群算法；多维信息素；扫描法 中图分类号： 文章标识码： 文章编号：- （）- - Improved Ant Colony Algorithm for Period Vehicle Routing Problem - ， - ， ， - ， - （ Transportation Management College， Dalian Maritime University， Dalian ， P RChina； School of Automotive Engineering， Dalian University of Technology， Dalian ， P R China） Abstract： （） （）， - ， ， ， ， ， ， ， - （） ， ， （）， - ， ， ， ， ， ， ， Key words： ； ； - ； 引言 周期性的车辆路径问题（ ，）是车辆路径问题的重要拓展。 最早由 和 于 年发表的会议论文上提出来的。 是 在时间上的扩展，通常 解决一段时间（一天）内的路径优化问题，而 是在 天里完成对客户点的服务，服务次数要满 足客户点相应的需求。 实践中， 有着很强的应用价值，很多路径计划是按照一定的周期来制定的。 近年来，燃料成本上升以及供应链竞争的加剧，车辆送货也备受关注。 特别是，在很多情况下车辆要对固 定的一些客户进行周期性的配送服务，并且这些客户对周期内的服务次数有一定的要求，优化这些重复性 的操作会显著的节约成本。 周期性的服务在快递配送，原材料供应和超市配送等方面有着广泛的应用。 国外在周期性车辆路径问题领域的研究比较早，主要有： 和 是最早使用启发式算法 来求解 的研究； 等 提出启发式算法求解 ，其算法包含两个阶段，首先进行客户组合优 化，然后求解相应的路径； 等 针对具有 的废纸箱回收问题进行研究，并考虑问题的时间和 空间两个方面的相互作用，建立总的配送费用最小的目标函数，并运用一种改进的启发式算法对问题进行 求解； 等 运用由并行遗传算法和局部搜索算法组成的异步并行启发式算法求解 ； 等 提出了一个改进的启发式算法来求解将客户的服务频率作为决策变量的 问题模型；- 等通过一个嵌入式改进程序来建立一个简单有效的线路构建算法，并运用此算法对 进行求解； 和 通过一种信息素更新策略以提高蚁群算法的优化质量，并运用改进的蚁群算法求解 。 国内学者在 领域也进行了大量的研究，例如，在标准的 问题 - 、带时间窗的 问 题 以及多中心 问题 等，但是，目前对 方面的研究还比较少。 需要优化每个配送期的客户组合，并针对各配送期进行路径优化，因此， 是一个内嵌 的问题，其比单周期 更加复杂。 大量研究已经表明了模拟生物的启发式方法非常适合求解大规模的 组合优化问题。 蚁群算法（）是受自然界中蚁群觅食行为启发而提出的一种进化算法。 而且，很多研 究也已经证明了 算法在求解 问题的可行性 - 。 这些成功的研究，使本文选择了蚁群算法求解 问题，并提出几种改进策略来提高算法的性能，最后，通过一些经典的 实例对该算法及改进策 略进行了检验。 周期性车辆路径问题 周期性车辆路径问题（）是指在每个客户的需求量确定的情况下，在给定的时间周期内，以一定 的服务频率满足客户需求的问题。 实际过程中要求由配送中心发出的车辆在完成配送服务后最终返回配 送中心。 与 的最明显的区别是：在 中，同一天内配送中心必须一次性服务所有的客户；而 图 典型的周期性车辆路径问题 在 中，在同一天内不是对所有的客户都需要提供服 务，而且在 所规定的周期内，每个客户的服务次数不 是固定的，而是配送中心根据客户的需求来制定。 图 显示了一个服务周期为 天的 实例，C c，c，cN表示所有点的集合，其中，c表示配送中心， c，cN表示客户数；每个客户（ciC）相应的需求为 qi （qi）；d 表示客户的服务频率（d尘T）；L l， l（N ）N表示所有边的集合。 根据上述描述，建立周期性车辆路径问题模型如下： N i N j ，ji K k T d lijx d ijk （） 第 期 蔡婉君，等： 改进蚁群算法优化周期性车辆路径问题 K k N j x d ijk尘 K for i d ，T （a） N j x d ijk N j x d ijk尘 for i k ，K d ，T （b） K k N j ，jix d ijk for i ，N d ，T （c） K k N i ，ijx d ijk for j ，N d ，T （d） N i qi N j ，jix d ijk尘 Q for k ，K d ，T （e） 其中，K 表示车辆的总数；N 表示配送中心及客户的总数量；lij表示客户 i 到客户 j 之间的距离；qi表示 客户 i 的需求量；Q 表示车辆的容量；T 表示服务周期。 模型中的决策变量为：x d ijk 如果车辆于第 d 天经由顾客 i 至顾客 j 否则 上述模型中，目标（）：最小车辆总行程。 约束条件（a）：确保在 T 周期内每一配送期的车辆数不超过 总车辆数。 约束条件（b）：确保车辆从配送中心出发并回到配送中心。 （c） （d）：确保各客户在同一配送 期（天）只被同一车辆服务一次且最多一次。 约束条件（e）： 确保车辆每次所载的货物不超过其容量。 改进的蚁群算法（） 在自然界中，蚁群的“群集智能”行为引起了研究者的广泛关注，通过研究发现蚂蚁在运动过程中，能 够在它所经过的路径上留下一种蚂蚁能感知的化学物质，而蚂蚁在选择路径时倾向于选择该化学物质浓 度高的路径。 蚁群就是通过这种信息的交流找到一条从蚁巢到食物源的最短路径。 蚁群算法是一种受真 实蚁群觅食行为启发而提出的一种基于群集智能的模拟进化算法，已在一系列复杂的组合优化问题求解 中取得了成效。 2 1 构造方案 不同于单周期的 问题，它的解是由多个配送期内的线路组合起来构成的。 由于每个客户 可能在配送周期内被访问多次，而具体配送的日期也是不确定的，因此，采用传统单周期 的信息素表 示形式则很难区分客户在不同配送日期内的启发式信息。 本文提出一个多维的信息素矩阵来表示各配送 日期的客户间的信息素状况。 多维的信息素矩阵可以看成多个单维的信息素矩阵的组合，即为每个配送 日期设置一个单独的信息素矩阵。 每个客户在每个配送日期都有信息素信息，只是不同的配送日期，其信 息素浓度有所差别。 本文提出的算法就是通过这种方式来区分不同配送日期的客户最优的配送组合。 多 维信息素如图 所示。 图 多维信息素表现形式 2 2 转移规则 蚂蚁在运动过程中，会优先选择含“信息素”浓度较大的路径。 因此，蚂蚁在搜索路径时，其遵循的规则 通常是与各条路段上的信息素浓度和期望值有关，对于第 d 天的第 i 点的蚂蚁来说，选择 j 点的概率如下： 运 筹 与 管 理 年第 卷 p d i，j （ d i，j） （ d i，j） h臭tabu（ d i，j） （ d i，j） j 臭 tabu 其它 （） 式中， d i，j：第 d 天路段（i， j）的信息素的强度； d i，j：第 d 天路段（i， j）的期望值；表示信息素的相对重 要性（ 辰）， 表示启发信息的相对重要性（ 辰）；tabu：第 i 点蚂蚁的不可行节点的集合。 例如，线路已 经经过的点就是不可行点。 2 3 局部优化 蚁群算法是一种随机搜索算法，其容易陷入局部最优，而不一定是全局的最优或近优解。 因此，本文 采用局部搜索算法跳出局部最优点。 本文的局部优化包含两个阶段：一个是线路内局部优化，另一个是线 路间的局部优化。 线路内的局部优化主要是基于 法优化当前方案中所有线路内的各客户点的排 序优化，该方法已经在许多文献中详细阐述过 ，下面主要讨论线路间的局部优化。 如果一个优化方案中两条线路间存在交叉点，通常该方案存在改进的可能，因此，一种有效的局部优 化算法就是消除优化方案中的交叉现象 。 然而大部分研究在寻找交叉路段时通过枚举法来进行（即比 较所有的路段），这大大降低了算法的效率，特别是在求解大规模的 时，这种算法需要花费大量的计 算时间，从而降低算法的实用性。 本文所采用的线路间局部优化方法也是基于减少优化方案中的交叉现 象的思想。 同时为了提高局部优化算法的效率，本文又引入了一种扫描法来快速寻找优化方案中的交叉 现象。 具体步骤如下： Step 1 初始化。 本文提出的扫描法是基于客户点和配送中心间的角度进行的，因此，需要确定配送 中心和客户点的空间位置。 首先，以配送中心的坐标为原点建立一个坐标系，再根据坐标将客户点绘制到 这个二维空间上。 由于周期性 具有自身的特点，只有同一配送日期的线路间才能进行线路间局部优 化。 本文以图 中第一天的配送线路为例，得到图 所示的配送中心和客户的空间分布状况。 然后，对每 个客户点进行初始化，这个操作包括计算每个客户点的角度和其所属的线路，例如，客户 c的角度为 ，其所属线路，则其表示为（ ， ）。 图 在坐标系中初始化配送中心和客户位置 Step 2 选择可能交叉的线路。 首先将所有的客户点 按照角度大小进行排序，并同时记录线路编号，如图 所 示。 然后，从角度最小的客户点开始，依次扫描所有的客户 点所属的线路编号，观察线路编号的变化（例如，客户 c和 客户 c，线路编号从 变为 ），但是，如果变化后的编号为 已经扫描过的线路（例如，客户 c和客户 c，线路编号从 变化为 ），则认为出现“回退”现象。 扫描中如果一条线路 的客户点连续，没有出现回退现象则表明该线路与其他线 路都不存在交叉的可能（例如，线路），如果出现回退现象 表明线路间存在交叉的可能。 然后检查可能存在交叉现象 的线路是否满足禁忌表，如果满足则转到 判断是否两条线路存在交叉点，否则继续扫描。 如果扫描 到最后一个客户点仍然没有出现“回退”现象则转到 。 图 按角度进行客户排序 第 期 蔡婉君，等： 改进蚁群算法优化周期性车辆路径问题 Step 3 判断两条线路是否存在交叉。 在判断两条线路是否存在交叉点时，依次比较两条线路的所 有的路段，检测其是否存在交点。 判断两条线段是否相交的步骤如下： 假设存在两条路段 ab 和 cd，其中，路段 ab 的两个端点的坐标为：（x， y）和（x， y）；路段 cd 的两个 端点的坐标为：（v， w）和（v， w），如图 所示。 图 两线路示意图 ）如果 xx且 vv 先计算两条路段的斜率 和 ， （y y） （x x）（） （w w） （v v）（） 如果 ，则两条路段没有交点；否则两条路段可能存在 交点，还需要计算交点的坐标判断是否在两条路段内相交。 两 条路段交点的横坐标为 z： z （b b） （ ）（） b （x y x y） （x x）（） b （v w v w） （v v）（） 式中，b和 b为两个判断参数。 如果 z 在 x， x之间，且 z 在 v， v之间，则两条路段存在交点；否则两条路段内不相交。 ）如果 x x或 v v 如果 x x且 v v，则两条路段不相交。 如果x x且vv，令z x代入路段 cd 的直线方程，求得纵坐标Z，若Z 在w， w之间，两条路段 相交，否则两条路段不相交。 xx且 v v的情况类似。 在判断过程中，如果两条线路存在交叉点则转到 ，否则继续遍历。 如果遍历结束，两条线路不存 在交叉点，则转到 将两条线路加入禁忌表避免后续搜索重复判断。 Step 4 相交路段的局部优化。 遍历两条相交路段的四个端点的所有可行组合，寻找能最大程度缩 短配送距离的组合，如果该组合优于当前方案，则使用该组合替代当前方案，并使用 优化两条新的 线路，并转到 ；否则，转到 将两条路段加入禁忌表。 例如，两条相交路段 cc和 cc，其局部优 化的结果可能如图 所示。 图 一个线路间局部优化的实例 Step 5 更新禁忌表。 为了避免对已扫描过的无效的交叉线路和交叉路段的重复判断，本文建立了 两个禁忌表：交叉线路禁忌表和交叉路段的禁忌表。 禁忌对象的禁忌长度为 ，即在连续 次的扫描过程 中被禁的线路或路段不得选取作为判断是否相交的对象。 Step 6 终止判断。 若所有的线路间都不存在交叉现象或达到预设的最大迭代次数，则基于扫描法 的局部优化结束，否则转到 。 2 4 信息素更新策略 在蚁群算法完成一次循环后，更新蚂蚁走过路径上的信息素浓度是至关重要的。 在信息素更新时，为 了模拟信息素的蒸发现象，所有路径上信息素都按照统一的比例减少；用参数 （ 尘尘） 来表示信息素 的保留率，则 表示信息素的挥发率。 当蚁群算法完成一次循环后，各路径上的信息素更新可以采用 运 筹 与 管 理 年第 卷 如下方式： d i，j new d i，j old d i，j （，）（） 式中， d i，j new：第 d 天的路段（i， j）上信息素的数量；d i，j old：第 d 天的路段（i， j）上更新前的信息素的数 量； d i，j：第 d 天的路段（i， j）上信息素的增量，其计算公式如下： d i，j A L opt L current 蚂蚁第 d 天所走过边（i，j） （） 式中，A 是一个常量，L opt表示到目前为止的最优方案的线路长度；Lcurrent表示当前方案的线路长度。 表示惩罚系数。 由于 问题中，每个配送周期需要服务的客户组合是不确定的，蚁群算法在 求 解过程中，经常会出现某个配送日期需要的车辆数（线路数）超过配送中心配备的车辆数，这导致搜索方 案成为不可行方案。 通常可以采用两种途径解决不可行解的问题：一种是直接丢弃不可行解，另一种是考 虑该方案可能包含部分有效信息，而采用“弱”保存方式，即对该方案赋予较低的信息素增量。 本文采用 了第二种方式，对不可行方案通过惩罚系数来降低其信息素增量。 这里，如果解决方案满足车辆约束则 ；否则 。 实例研究 为了测试本文提出的改进蚁群算法的性能，我们采用了文献，中的 个 - 问题 对该算法进行了检验。 其 个经典实例的客户规模是 ，车辆数规模是 ，周期长度是 天。 实例的具体信息如表 所示。 对于传统蚁群算法来说，蚂蚁的初始位置是通过随机方式产生的，但这种方式有可能导致部分蚂蚁的初 始位置过于密集，由于蚂蚁在最初搜索过程中倾向于选择离当前位置较近的点 ，从而使得蚂蚁密集的地方局 部收敛过快，容易引起早熟现象 。 本文选择蚂蚁初始位置时，采用了“间隔分配法”原则，即根据客户点与 坐标轴的角度大小将客户点进行排序，然后按均匀间隔放置蚂蚁，使蚂蚁初始位置尽可能分布均匀，这样在 一定程度上可以避免蚂蚁在出发选择路径时不会过早地受到其他蚂蚁的影响 ，进而提高解的空间。 本文改进的蚁群算法（）使用 实现，运行环境为 处理器 上，内存为 的 平台。 通过大量实验，确定参数设置为： ， ，A ， ， 。 为了验证本文提出算法的性能，我们将 的计算结果与 算法 和 算法 进行了比较。 比 较结果如表 所示。 表1 经典实例的基本信息表 编号客户数车辆数周期车容量 n? n? n? n? n? n? n? n? ? 第 期 蔡婉君，等： 改进蚁群算法优化周期性车辆路径问题 表 2 计算结果比较 编号CGWCGL已知最优解IACO n nfl g n g n? n g n g n0 n g ? 注：来源：http： neo lcc uma es radi- aeb WebVRP 从表 可以看到，本文算法对 个实例的优化结果优于或达到已知最优解，其中，实例 和 的结果 优于已知最优解（线路信息见附表 和 ），实例 、 和 达到已知最优解，而对于实例 、，本文提 出的算法没有达到已知最优解。 与 和 算法相比， 算法在相对简单的问题（实例、）能 取得较好的优化效果，但是对于相对复杂的问题（实例 ） 的优化效果与 算法相当，不如 算法。 总体看，本文提出的 算法对于 来说，是一种非常有竞争力的算法。 本文提出的 算法中，主要包含两种改进策略：多维信息素更新策略和基于扫描法的局部优化方 法，为了具体分析两种策略的效果，我们构造了下面的测试。 为了检验多维信息素的效果，我们设计了单 维信息素矩阵的蚁群算法（ ）和多维信息素的蚁群算法（ ）。 为了检验扫描法引入的效 果，我们设计了带有多维信息素的遍历搜索法的局部优化（ ），该方法在进行局部优化时，不采 用扫描法搜索可能的交叉线路，而是遍历所有的线路。 表 显示了在相同条件下 算法和另外三种 算法的计算结果。 表3 四种蚁群算法性能比较 No ACO SP 长度时间（s） ACO MP 长度时间（s） ACO MPB 长度时间（s） IACO 长度时间（s） &? d ? p & dy pq &? dy pq &? d ? p &? dy q &? dy q &? d ? &? dy q :? d ? Ave? ? 3 从表 可以看出， 和 算法的优化质量明显优于 和 算法，表明采 用局部优化操作可以有效地使算法跳出局部最优，提高优化质量，而 和 算法的计算 时间要远远小于 和 算法，说明局部优化操作是一种比较耗时的计算。 算法的 性能约 优于 算法，说明采用单维信息素的蚁群算法求解 是非常困难的。 同时，相 比于 和 算法，采用多维信息素的 算法计算时间比较短，但优化的质