《求解卸装一体化的车辆路径问题的混合启发式算法》由会员分享，可在线阅读，更多相关《求解卸装一体化的车辆路径问题的混合启发式算法（12页珍藏版）》请在金锄头文库上搜索。
1、求解卸装一体化的车辆路径问题的混合启发式算法摘 要: 提出一种结合蚁群系统（Ant Colony System, ACS）和变邻域下降搜索（Variable Neighborhood Descent, VND）的混合启发式算法 ACS_VND，求解卸装一体化车辆路径问题。利用基于插入的 ACS 解构造方法产生多个弱可行解，再逐个转换成强可行解，并选择其中最好的作为 VND 的初始解。在 VND 过程中使用三种不同的邻域结构：插入、交换 和 2-opt 依次对解进行迭代优化。 对 55 个规模为 22199 的 benchmark 算例的求解结果表明，算法 ACS_VND 能在较短时间内获得 5
2、2 个算例的已知最好解，并且更新了其中 44 个算例的已知最好解，求解性能优于现有算法。关键词: 卸装一体化车辆路径问题；混合启发式算法；蚁群系统；变邻域下降搜索；组合优化；NP 难1 引言 车辆路径问题（Vehicle Routing Problem, VRP）一直是运筹学、管理学、计算机科学等领域的研究热点问题，在现实生活中有着广泛的应用， 如物流配送、邮政投递、校车路径安排、铁路和飞机的调度等，是一个具有重要理论意义和实际应用价值的研究课题。近年来，逆向物流的发展使得 VRP 中另一形式的问题卸装一体化车辆路径问题（Vehicle Routing Problem with Simulta
3、neous Delivery and Pickup，VRPSDP）引起研究者的关注。卸装一体化车辆路径问题可简单描述如下：安排车辆为一定数量的客户送货，并从客户处收集一定数量的物品（如货物包装材料、垃圾等） 。每个客户的地理位置以及卸货、装货需求事先已知。要求在满足一定约束条件（如车辆容量限制等）的前提下，安排车辆满足客户需求使得总的车辆行程长度最短。VRP 自 1959 年由 Dantzig1提出后，几十年来已取得大量研究成果，然而关于 VRPSDP 的研究却非常少。1989 年 Min2针对一个图书馆配送的实例首次定义了该问题。以后的十年中，几乎没有关于该问题的讨论。逆向物流的兴起使得研究
4、者重新开始对该问题进行研究和探讨。文献2-5讨论了该问题的若干应用实例。由于VRP 是 NP 难问题，因此，VRPSDP 也是 NP 难的，而且比基本 VRP 问题更复杂，因此，对此类问题的求解方法研究主要集中在能在较短时间内给出较优解的启发式算法（heuristic ）和元启发式算法（metaheuristic） ，现已取得一定的研究成果，主要有构造性算法，如文献6中 Dethloff 提出的带有参数的插入法，文献7中的先聚类后插入算法；禁忌搜索，如文献8中 Crispim 等提出的基于禁忌搜索的混合算法，文献9 中 Tang Montan 等提出的基于四种邻域结构和两种搜索策略的禁忌搜索，
5、文献10中 Chen 和 Wu 提出一种基于“记录”和禁忌表的混合启发式算法。最近，Bianchessi 和 Righini 提出一些构造性算法、局部搜索算法以及禁忌搜索算法并加以比较，其中重点讨论了基于复合多邻域结构的禁忌搜索算法 11。Tang Montan 等 9给出一组测试算例解的下界，这些下界表明现有算法虽能在一定程度上解决 VRPSDP，但求解质量还有较大改进空间。蚁群优化（Ant Colony Optimization, ACO）是一种基于群体的元启发式算法，最初的灵感来源于真实蚂蚁搜寻食物的行为 12以信息素作为媒介间接进行信息交换。目前蚁群优化已经成功应用于多个 NP 难的组
6、合优化问题求解。变邻域搜索（Variable Neighborhood Search, VNS）最早由 Hansen 和 Mladenovi1314提出，其核心思想是：邻域结构定义了搜索空间的拓扑特性，不同的邻域结构对应搜索空间的不同区域。一般地，问题解空间中某个区域的特性不同于其它区域，因此，动态使用不同的邻域结构能够增加解的多样性。变邻域下降（Variable Neighborhood Descent, VND）是 VNS 的一种变形，它通过一种确定的方式来改变邻域结构的使用。根据文献14中对元启发式算法的分类，蚁群优化属于基于群体的算法，而变邻域下降搜索则是属于轨迹法。基于群体的元启发式
7、算法的优势在于善于发现搜索空间中的可能存在最优解的区域，而轨迹法的优势在于善于探索搜索空间中较好的区域。因此，将二者结合可以充分利用各自的优势，提高算法的搜索性能和效率。本文将蚁群优化中的一种蚁群系统（Ant Colony System, ACS）与 VND 相结合，提出一种混合启发式算法2 ACS_VND 用于求解 VRPSDP。利用 55 个 benchmark 测试算例进行实验，并与文献2以及文献611和中的算法求解结果比较，验证本文算法的有效性。2 卸装一体化车辆路径问题描述2.1 问题描述本文利用有向带权图 G 描述卸装一体化车辆路径问题：假设 ，其中， 是顶点集（0 表示配送中心，
8、其它表示客户） ； 是连接各顶点的弧集； 是权重矩阵，c ij 表示从客户 i 到客户 j 的距离。任意客户 都有一定卸货需求 di 与装货需求 pi。安排车辆为所有客户服务（假设所有车辆为同一车型，车辆最大容量为 Q） ，要求满足以下条件并使得车辆总行程长度最短：a) 每辆车都从仓库出发，并最终返回仓库；b) 每个客户都只被一辆车服务，且仅被服务一次；c) 任一车辆在行程过程中，载重始终不能超过 Q。2.2 解的可行性设 是 VRPSDP 问题的一个解，其中 ri 对应一条车辆路径。由 2.1 节中的 VRPSDP 问题描述可知，s 是 VRPSDP 问题的一个可行解的充分必要条件是：对任意
9、 ri，都满足1) ri 上所有客户的总的卸货需求 D(x)不超过 Q；2) ri 上所有客户的总的装货需求 P(x)不超过 Q；3) 车辆访问 ri 上任何客户之后载重都不超过 Q。若 都满足条件（1） （2） （3） ，则称 s 满足强可行性条件，是强可行解；若 都满足条件（1）（2） ，但 不满足条件（3） ，则称 s 满足弱可行性条件，是弱可行解。由于 Mosheiov3 已经证明，如果D(x) 和 P(x)都不超过车辆容量限制，则 ri 一定可以通过某种转化成为可行路径。因此，若 s 是弱可行解，则一定可以通过某种方式转化为强可行解。3 混合启发式算法 ACS_VND3.1 信息素初
10、始化首先使用最近邻启发式（Nearest Neighborhood Heuristic, NNH）构造一个强可行解 s0，并根据式（1）设定信息素初值。(1)其中，n 是客户数量。NNH 构造解的步骤如下：步骤 1：从尚未访问的客户节点中，选择距离配送中心最小的客户，开始一条新的车辆路径 r；步骤 2：若 V0 不为空，则从中选择距离 r 上最后一个客户最近的客户，作为下一个访问的节点；否则，转步骤 1，直到所有客户都已被访问。这里，将 V0 定义为尚未被访问，且加入 r 后，使得 r 仍能约束强可行性条件的所有客户节点的集合。3.2 构建可行解由于弱可行性条件检查比较简单，在算法 ACS_V
11、ND 的构建解阶段，首先产生一组弱可行解，然后转化成强可行解。在 ACS 解的构造方式的基础上，算法 ACS_VND 中使用一种基于插入的启发式方法构造弱可行解。首先，从配送中心 0 出发，随机选择一个客户，开始一条新的路径 r；然后，根据伪随机比例规则(2)(3) ，从 V1中选择客户 k 并将它插入到当前路径 r 上节点 i 与 j 之间，这里，V 1 是指满足以下条件的客户节点 k 的集合：k陈萍 等:求解卸装一体化车辆路径问题的混合启发式算法 3尚未被访问，且若 k 加入 r 仍能保证 r 满足弱可行性条件。 k 的定义如式(4)，它决定了客户 k 被选中的可能性大小，其中，i 和 j
12、 是当前路径 r 上的两个相邻的节点。 的定义如式(5)， ik 和 kj 是插入 k 后新增的两条弧(i, k)和 (k, j)上的信息素， ij 是删去的弧(i, j)上的信息素。 ijk 是启发式信息，定义如式 (6)，其中第一项考虑了客户与配送中心之间的距离，以避免距离仓库较远的客户插入得较晚，从而增加额外的代价；第二项表示将客户 k 插入到当前路径上客户 i 与客户 j 之间时增加的路径长度。， 是 和 ijk 的相对影响因子。不断地从 V1 中选择客户，直到 V1 为空，结束当前路径 r 的构造；若所有客户都已在当前解中，结束算法；否则，重新开始一条新的 r 并重复上述构造过程。为
13、取得利用历史信息和随机选择之间的平衡，算法 ACS_VND 中动态调整 q0 的大小，使其取值为 qmin 或 qmax。(2) S： (3)(4)(5)(6)算法 ACS_VND 中利用与文献10相同的方法将弱可行解转化成强可行解，即从头至尾逐个扫描每一条路径 r 上的客户，若访问当前客户后 r 不能满足强可行性条件，则跳过当前客户扫描下一个；否则，继续扫描下一个；最后，按照逆序将在第一次扫描中被跳过的客户逐个重新加入 r，即可得到一个强可行解。3.3 局部信息素更新根据式（7） ，利用构造的每一个解 s 进行局部信息素更新，其中，0 11 是信息素挥发系数， 0 是信息素初值。(7)3.4
14、 变邻域下降搜索变邻域下降搜索的基本步骤是：从初始解出发，选择一种邻域结构进行局部搜索，直到找到局部最优解；以当前局部最优解为初始解，使用另一种邻域结构继续进行局部搜索；当使用任何一种邻域结构都不能继续改进当前解时，结束 VND 过程。3.4.1 VND 过程算法 1 VND 过程 1: 输入初始解 s, 选择一组邻域结构 Nk，k = 1, , k max；令 p = 0；2: WHILE p kmax DO3: k = 1；4: WHILE k kmax DO5: 以 s 为初始解，在 Nk 定义的邻域中进行局部搜索，直到找到局部最优解 s*；6: IF f(s*) f(s) THEN 7
15、: s = s*；8: p = 0；9: ELSE10: p = p+1；4 11: END IF12: k = k+1；13: END WHILE14: END WHILE15: 输出 s，算法结束。3.4.2 邻域结构在使用变邻域下降搜索之前，需要定义一组邻域结构。算法 ACS_VND 中分别使用三种求解 VRP 问题时常用的邻域结构：插入（insert） 、交换（swap ）和 2-opt。1. 插入（insert）将解 s 中的某个客户 i 从当前位置 p1 移到 s 的另一个位置 p2（p 1 与 p2 可属于同一路径，也可属于不同路径） ，产生新解 。例如，解 s = 0 357012460 ，将客户 3 从当前的 2 号位置移到 4 号或 6 号位置，产生新解 = 057 3012460 或 =05 701 32460。当某条路径上没有客户节点时，删去该路径，从而使得车辆个数减少。例如，解 s = 0125 00 36470，删去空的子路径后，得到 s = 0125 036470。2. 交换（swap ）将解 s 中的客户 i 和 j 的位置互换（i 和 j 可属于同一路径，也可属于不同路径） ，产生新解 。例如，解 s = 0 3
