Computer Engineering and Applications 计算机工程与应用 2014，50（2） 237 改进变邻域搜索算法求解动态车辆路径问题 王仁民 1，闭应洲 1，2，刘阿宁 1，李 杰 1 WANG Renmin1, BI Yingzhou1，2, LIU Aning1, LI Jie1 1.广西师范学院 计算机与信息工程学院，南宁 530004 2.武汉大学 软件工程国家重点实验室，武汉 430072 1.College of Computer and Information Engineering, Guangxi Teachers Education University, Nanning 530004, China 2.State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China WANG Renmin, BI Yingzhou, LIU Aning, et al. Improved variable neighbourhood search algorithm for DVRP. Computer Engineering and Applications, 2014, 50（2）：237-241. Abstract：Due to the optimization problem of dynamic vehicle routing problem, an improved algorithm for DVRP （Dynamic Vehicle Routing Problem）is proposed. Based on analyzing local features of routing optimization problem, the method uses variable neighbourhood search heuristics to explore, and combines mutation mechanism to exploit. The dynamic routing blocks are inserted into vehicles according to neighbor priority principle. Experimental results show that the improved algorithm is effective. Key words：Dynamic Vehicle Routing Problem（DVRP）; variable neighbourhood search heuristics; mutation mecha- nism; neighbor priority principle 摘 要：针对动态车辆路径问题 DVRP（Dynamic Vehicle Routing Problem）的优化问题，提出一种改进算法。该算 法在分析路径寻优问题的局部特性的基础上，利用变邻域搜索算法 VNS（Variable Neighbourhood Search）对路径空 间进行“局部探索”，结合变异机制对路径空间进行“全局开采”，最后根据近邻优先原则将动态路径片段安插到适宜 的路径中。实验结果验证了算法的有效性。 关键词：动态车辆路径问题；变邻域搜索算法；变异机制；近邻优先原则 文献标志码：A 中图分类号：TP301.6 doi：10.3778/j.issn.1002-8331.1203-0055 1 引言 动态车辆路径问题是指，客户需求不是预先知道， 而是在访问客户的过程内实时出现 [1-2]。其主要解决客 户动态需求的收集与规划，如出租车呼叫服务、快递收 发等。动态车辆路径问题是静态车辆路径问题 SVRP （Static Vehicle Routing Problem）的扩展，是一种典型 的 NP-hard（Non-deterministic Polynomial hard）路径寻 优问题，除具有静态车辆路径问题的基本特点之外，还 存在如何处理动态需求的问题。 跳出“局部最优解”寻找“全局最优解”是路径寻优 问题的关键。文献[3]中将优化路径的搜索过程分为局 部“探索”（exploration）和全局“开采”（exploitation）两个 阶段，几乎所有的启发式算法都是在这两者之间寻求一 种平衡[4]。变邻域搜索算法[5-6]每次只接受具有改进的解 作为进一步优化的初始解，这种基于“压力”的搜索方式 具有很强的局部搜索能力，可作为有效的“探索”。在解 决因过度“探索”可能引起的局部最优问题，遗传算法中 的变异机制 [7]具有良好的全局开发能力，可用于算法全 局最优解的“开采”。基于以上分析，本文改进算法首先 采用节约里程算法（Savings algorithm）[8]快速构建初始 路径，然后利用变邻域搜索算法进一步优化，并结合变 异机制尽可能防止算法陷入局部最优，最后应用“近邻 基金项目：广西科技开发计划项目（No.桂科攻 11107006-7）；广西教育厅重点资助项目（No.201102ZD020）；2012 研究生教育创新 计划项目（No.20121106030703M03）。 作者简介：王仁民（1982—），男，硕士研究生，主要研究方向为智能计算；闭应洲（1967—），男，博士，教授，主要研究方向为智能计 算、智能信息处理；刘阿宁（1982—），女，硕士研究生，主要研究方向为智能计算；李杰（1986—），男，硕士研究生，主要 研究方向为图像处理。E-mail：edaofu@163.com 收稿日期：2012-03-02 修回日期：2012-06-28 文章编号：1002-8331（2014）02-0237-05 

238 2014，50（2） Computer Engineering and Applications 计算机工程与应用 优先原则”形成实时路径。 2 DVRP 问题模型 0 v v 1 0 动 态 车 辆 路 径 问 题 可 描 述 为 ：定 义 一 个 无 向 图 G(VE) 其 中 V ={v } 表 示 具 有 n 个 客 户 和 一 n 个仓库 (v ) 的集合，V 中的 n 值随时间动态增长；现有 载重量限制为 Q 的车 K 辆，对 V 中具有确定的时间窗 ) 及需求 d 的客户进行访问，每个客户必须且只能 (e 由一辆车访问，并要求总代价最小；最后，车辆访问客户 )(ij = 012n) 即为该动态 所形成边的集合 E(v e 0 l v i j 车辆路径问题的求解结果。为方便描述，现定义符号或 变量如下： K ：车辆数； k ：第 k 辆车； Q ：车的容量限制； d i ：客户 v ：第 i 个客户； 到 v ：车辆从 v v i t i 的需求量； ij c ij [e S i t i W X j i l ] ：v j 到 v i 的服务时间； i ：车辆从 v e i ：在 v i ：到达 v ：在 v ={10} ：路径从 v i 等待的时间； 的时间； i i ijk 的时间； 的距离成本； 的可服务时间窗； （3）和（4）表示所有 v （5）表示从 v 必须且只能访问一次；约束条件 的时间窗约束；约束条件（6）表示所 到 v i i j 有路径需满足系统时间周期；约束条件（7）表示 v 服务时间范围。 i 的可 动态车辆路径问题的描述中，将仓库的开闭时间称 为一个“工作日”（The working day），并根据客户规模 及工作日长度将工作日划分为“时间片”（time slice）[2，9]。 每一个时间片范围内，并不立即处理收集到的客户需 求，直到该时间片结束时才开始处理。 在动态车辆路径问题中，需求并不是预先全部确定 的，而是在一个工作日内随机到达。因此，动态车辆路 径问题的主要任务，是将客户动态需求合理地分配到已 存在的路径中，该过程可能会打乱以往的访问顺序。如 图 1，假 设 已 规 划 的 路 径 为 R1（R1={0，1，3，5}）和 R2 （R2={0，2，4}），现动态加入新的客户后，路径为 R1={0， 1，7，3，5}，R2={0，2，4，6}（实线表示已规划的路径，虚线 表示动态加入的路径）。 7 2 1 0 5 R1 3 4 6 R2 图 1 动态路径插入示意图 到 v j i 由第 k 辆车服务时为 1， 3 DVRP 配送策略 否则为 0； Y ik (e ={10} ：v l 0 0 由第 k 辆车服务时为 1，否则为 0； i ) ：系统工作周期，e 为系统开始服务时间，l 0 0 为系统停止服务时间。 根据以上描述，动态车辆路径问题的目标函数可定 义为： F = å n å n å K C i = 0 j = 0 k = 1 X ijk ij 其中，该目标函数需满足以下约束条件： n å l = 1 .y d i ik  Qk = 012K = 1j = 01n = 1i = 012n X ijk X ijk X ijk (t i + w + s i i + t ) = t j = 01n j ij X ijk (w i + s + t )  l k = 012K 0 ij i K å n å i = 0 k = 1 K å n å j = 0 k = 1 K å n å j = 0 k = 1 n å n å i = 0 e j = 1  t + w （7） 其中，约束条件（2）表示所有车辆容量受限；约束条件 i = 012n l  e i i i 动态车辆路径问题配送策略，可按以下方式进行： 对于每一个时间片，需求收集模块收集客户需求信息， 再将所收集的信息交路径规划模块处理，规划模块将处 理结果交配送服务模块执行，执行完之后将相关信息反 馈给信息收集模块。动态配送策略图如图 2 所示。 信息收集模块 路径规划模块 馈 反 息 信 配送服务模块 图 2 动态配送策略图 根据上述采取的配送策略，设计动态车辆路径问题  now = 0 时间片为 n。则动态车辆路径问题处理 的处理过程如下：设工作日长度为 T，当前时间为 T 初始时 T 过程可分为以下三个阶段： now Phase1：初始化。初始化参数及迭代次数。 Phase2：需求处理。在时间片 (T T now now + T/n) 内， （1） （2） （3） （4） （5） （6） 

王仁民，闭应洲，刘阿宁，等：改进变邻域搜索算法求解动态车辆路径问题 2014，50（2） 239 now 如 果 T = 0 则 收 集 该 时 间 片 内 到 达 的 需 求 ，如 果 ¹ 0 则执行上一个时间片路径规划并收集该时间片 T now 内到达的需求，直到该时间片结束，则调用优化算法进 行实时规划。 Phase3：结果保存。保存当前结果，并返回 Phase2， 直到所有需求都已处理或工作日结束。 4 算法实现 本章引入改进的变邻域搜索算法来解决 DVRP 的 优化问题。首先，采用节约里程算法（savings algorithm） 快速构建一个初始解；然后，调用变邻域搜索算法进行 优化，并引入变异机制防止算法陷入局部最优；最后，根 据“近邻优先原则”将路径片段分配给适宜的车辆。 4.1 节约里程算法 节约里程算法由 Clarke and Wright 提出，主要基于 “三角不等式”原理，广泛用于快速构建 VRP 问题的初 始解。节约里程算法简单有效，只需利用公式 s(ij) = d(0i) + d(0j)−d(ij) 计算出两两客户之间的节约值，并 在满足所有约束条件的情况下，根据节约值由大到小合 并路径，直到所有客户都已合并为止，如图 3。 i d（i，j） j d（0，i） d（i，0） d（0，j） d（j，0） 0 图 3 节约里程算法原理图 4.2 改进变邻域搜索算法 4.2.1 变邻域搜索算法 变 邻 域 搜 索 算 法 首 先 由 Hansen 和 Mladenovi´c 提 出，其基本思想是：在搜索过程中系统地改变邻域结构 集来拓展搜索范围，获得局部最优解，再基于此局部最 优解重新系统地改变邻域结构即拓展搜索范围找到另 一个局部最优解的过程 [10]。变邻域搜索算法具有执行 速度快、局部搜索能力强等特点。文献[11]中提出了三 种改进的邻域结构以实现局部搜索：inter_route insertion， inter_route swap 和 inter_route 2-opt，分 别 设 为 N（0）， N（1）和 N（2）。综合这三种邻域结构实现的局部搜索算 法如下： 步骤 1 输入初始路径 InitialList，设 i = 0 。  执 r 步骤 2 随机选择候选解中两辆车的路径 r 1 2 'r 行 N (i) 中的局部搜索算法，得到两辆车的新路径 r ' 。 1 2 ') ' r ) > Length(r 2 1 步骤 3 如果新解有改进，即 Leng th(r  r 1 2 则保存新解 r 1 'r ¬ r 1 2 ¬ r ' 。 2 步骤 4 i=i+1。 步骤 5 如果 i > 2 停止，否则，转到步骤 2。 4.2.2 变异机制 执行变邻域搜索算法之后，得到的动态路径片段具 有良好“基因块”的特点，但该动态路径片段可能只是局 部最优的路径。为解决可能造成的局部最优，文章引入 遗传算法中的变异机制，尽可能使算法跳出局部最优。 变异机制的具体操作：从执行 VNS 算法得到的路 径中，随机选择某个结点，在满足一定变异率及客户时 间窗等约束条件的情况下，将其变异为该时间片内的另 一个客户结点，并对变异后的新个体进行评估，保留更 优的结果。如当前时间片的客户集合为 A={1，2，3，4， ={1，4，7}， 5，6，7，8，9}，调用 VNS 算法之后的路径为 r 1 执行 ={3，6，9}，随机选择某条路径如 r 1 中的结点“7”变异为“8”，如图 4 所示。 ={2，5，8}，r r 2 变异操作后，r 1 3 r1 r1' r2' 1 1 2 4 4 5 7 8 7 图 4 变异机制图 4.3 近邻优先原则 此处的“近邻优先原则”是指：根据所有车辆当前位 置，将离车辆更邻近的头结点与之连接。根据最优路径 所具有的局部特性，可根据“近邻优先原则”分配动态路 径片段。操作方式如下：首先，获取所有车辆的当前信 息；然后，采用迭代法计算动态路径片段的第一个客户 与所有车辆当前所在位置的欧式距离，并保存最近的 值；最后，在不违背车辆载重量和时间窗等约束条件下， 将动态路径片段安插到最近的车辆路径中。 4.4 算法总体框架及伪代码 工作日开始前，需预先设置一些参数和处理可能存 在的静态客户需求。工作日开始后，每个时间片分别执 行以下操作：首先收集需求，然后使用节约里程算法快 速构建该时间片内的动态初始路径，接着调用变邻域搜 索算法进行优化，最后在不违背车辆载重量和客户时间 窗等约束条件下，根据“近邻优先原则”将该时间片内的 路径片段加入到合适的路径中。算法 1 和算法 2 中列出 了核心算法伪代码，其中，算法 1 为改进变邻域搜索算 法优化动态路径片段伪代码，算法 2 为全局算法高层视 图伪代码。 算法 1 ImpovedVNS（） 设置循环次数 N 令 N = 0 ； While N < N max 并获取初始路径 x ； max 

240 2014，50（2） Computer Engineering and Applications 计算机工程与应用 Repeat 表 2 ImprovedVNS-DVRP 与 GRASP-DVRP 实验结果 k = 0 ； k = Shake(k) ：//握手 x = Local Search(x k) ：//局部算法 Until k = 2 调用变异机制； 评估并保留改进解。 End while 算法 2 Overall algorithm 初始化。工作日长度 T 当前时间 T = 0 设置时间片数 now 量 n 设置 VNS 迭代次数 m 变异率及工作日 T 。 While T < T now 收集动态需求； While 迭代次数 i < m ImpovedVNS（）； End while ¬ T T now now + T/n ； 输出当前时间片的路径规划； 近邻优先原则插入路径片段； End while 输出最终路径； End While 5 实验结果及结论 实 验 基 于 christofides 和 fisher 问 题 集（http：//www. feu.de/WINF/inhalte/benchmark_data.htm），对 新 算 法 进 行模拟测试，并将实验结果与 Montemanni R 等人提出 的 ACS-DVRP[2]及 Resende 等人提出的 GRASP-DVRP[12] 进行了比较。为了方便对比，将本文提出的算法称为 “ImprovedVNS-DVRP”。 实验参数设置：VNS 局部搜索循环次数为 100，变 异率为 0.05。实验结果及对比见表 1、表 2 及图 5、图 6 所 示，其中 Best 表示 10 次中的最好结果，Avg 表示运行 10 次结果的平均值。 表 1 ImprovedVNS-DVRP 与 ACS-DVRP 实验结果 问题集 c50 c75 c100 c120 c150 c199 f71 ImprovedVNS-DVRP ACS-DVRP Best 528.56 835.28 828.79 Avg 535.64 856.46 832.54 Best Avg 631.30 681.86 1 009.38 1 042.39 973.26 1 066.16 1 107.53 1 153.78 1 416.45 1 525.15 1 029.95 1 066.36 1 345.73 1 455.50 1 325.33 1 375.26 1 771.04 1 844.82 255.75 286.18 311.18 348.69 从表 1、表 2 的实验结果，以及图 5、图 6 实验结果对 比可以得出：本文提出的 ImprovedVNS-DVRP 算法的最 优解和平均值均好于 Montemanni R 等及 Resende 等提 问题集 c50 c75 c100 c120 c150 c199 f71 ImprovedVNS-DVRP Best 528.56 835.28 828.79 Avg 535.64 856.46 832.54 GRASP-DVRP Best Avg 696.92 719.56 1 066.59 1 079.16 1 080.33 1 119.06 1 107.53 1 153.78 1 546.50 1 643.15 1 029.95 1 066.36 1 468.36 1 501.35 1 325.33 1 375.26 1 774.33 1 898.20 255.75 286.18 359.16 376.66 2 000 1 800 1 600 1 400 1 200 1 000 800 600 400 200 0 c50 c75 c100 c120 c150 c199 f71 问题集 ImprovedVNS-DVRP Best ImprovedVNS-DVRP Avg ACS-DVRP Best ACS-DVRP Avg 图 5 ImprovedVNS-DVRP 与 ACS-DVRP 对比 2 000 1 800 1 600 1 400 1 200 1 000 800 600 400 200 0 c50 c75 c100 c120 c150 c199 f71 问题集 ImprovedVNS-DVRP Best ImprovedVNS-DVRP Avg GRASP-DVRP Best GRASP-DVRP Avg 果 结 果 结 图 6 ImprovedVNS-DVRP 与 GRASP-DVRP 对比 出的算法实验结果。实验结果表明：新算法对解空间的 搜索范围更大，在满足约束条件的情况下，改进算法组 合尽可能多的可行解，并在此基础上不断改进，因此， ImprovedVNS-DVRP 算法对求解动态车辆路径问题是 有效的。 6 结束语 传统的车辆调度一般采取两步过程，即计划-执行， 调度计划制定好以后就不再改变。随着 GPS、GIS 和各 种智能移动终端的广泛应用，使得物流公司有条件对它 们的车队进行实时动态管理，从而提高物流效率，取得 更好的效益。动态的原因来自客户的需求是动态的，道 路交通状况也是动态的，如果考虑车辆的故障，那么车 辆的能力也是动态的。在本文的研究中，只考虑了新的 客户请求，下一步研究中将进一步研究更复杂的动态车 辆路径问题，满足智能物流的需要。 参考文献： [1] Montemanni R，Gambardella L M，Rizzoli A E，et al.A new algorithm for a dynamic vehicle routing problem based on ant colony system[C]//2nd International Work- 

王仁民，闭应洲，刘阿宁，等：改进变邻域搜索算法求解动态车辆路径问题 2014，50（2） 241 shop on Freight Transportation and Logistics，2003. [2] Montemanni R，Gambardella L M，Rizzoli A E，et al. Ant colony optimisation for vehicle routing problem from theory to applications[J].Optimize，2005，9（1）：1-50. [3] Kemenade C H M.Building block filtering and mixing， SEN2R9837[R].Amsterdam：Centre for Mathematics and Computer Science，1998. [4] 闭应洲，陆建波，丁立新，等.基于有导向变异算子的 GM-EA 算法[J].计算机应用研究，2010，27（4）：1249-1251. [5] Hansen P，Mladenovi´c N.Variable neighborhood search[M]. Berlin：Springer，2005：211-238. [6] Hansen P，Mladenovi´c N，Pérez J A M.Variable neigh- borhood search：methods and applications[J].Ann Oper Res，2010，175：367-407. [7] Brimberg P，Ladenovic N，Urosevic D.Local and vari- able neighborhood search for the k-cardinality sub- graph problem[J].Journal of Heuristics，2008，14：501-517. [8] Clarke G，Wright J W.Scheduling of vehicles from a to a number of delivery points[J].Oper central depot Res，1964，12：568-581. [9] Kilby P，Prosser P，Shaw P.Dynamic VRPS：a study of scenarios，Technical Report APES-06-1998[R].Glasgow， Scotland：University of Strathclyde，1998. [10] 董伟.一个改进的变邻域搜索方法求解 k-card 问题[J].山 东科学，2011，24（1）：93-96. [11] Lei Hongtao，Laporte G，Guo Bo.A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service time[EB/OL]. [2011-10-20].http：//www.springerlink.com/content/n37kw- 766158x18j4/fulltext.pdf. [12] Recende M G C，Rebeiro C C.Greedy randomized adap- search procedures[J].Handbook of Metaheuristic， tive 2003：219-249. （上接 225 页） [9] Hasegawa M，Yoshioka S，Matsui K.Position sensorless control of interior permanent magnet synchronous motors using unknown input observer for high-speed drives[J]. IEEE Transactions on Industry Applications，2009，45： 938-946. [10] 陈海舰，仲丽云.基于 SVPWM 的永磁同步电动机控制系 [13] 裴乐.基于 DSP 的同步电机矢量控制系统的研制[J].电力 电子技术，2011，45（2）：72-74. [14] 杨 金 辉 ，戴 瑜 兴 ，易 龙 强.基 于 DSP 的 SVPWM 与 载 波 PWM 的统一性研究[J].电子学报，2010，38（7）：1647-1654. [15] 王艾萌，张丽，李和明.高性能永磁同步电机伺服控制系 统的设计与应用[J].华北电力大学学报，2011，38（4）：13-17. J，Koczara W.Poles position identification [16] Wisniewski 统设计[J].工矿自动化，2011（6）：46-49. of the permanent magnet motor by the PIPCRM com- [11] 祁超，王庆章，赵耀，等.基于 FPGA 的三相 SVPWM 调制 算法的实现[J].南开大学学报：自然科学版，2011，44（4）： 26-30. [12] 魏昌洲.基于 DSP 的交流变频调速系统研究[D].南京：南 京航空航天大学，2005. bined with zero voltage vector[C]//IEEE International Symposium on Industrial Electronics（ISIE），2011：679-684. [17] 康伟，张丽霞，康忠健.电流型双向 PWM 整流器 SPWM 与 SVPWM 控制输出特性比较[J].电工技术学报，2011，26 （11）：39-44. （上接 236 页） [8] 张焕国，吕莎，李玮.C 均值算法的电信客户细分研究[J].计 算机仿真，2011，28（6）：185-188. （9）：1455-1458. [16] 周爱武，陈宝楼，王琰.K-Means 算法的研究与改进[J].计 算机技术与发展，2012，22（10）：101-105. [9] 张燕蓟.基于访问日志的聚类分析和个性化推荐应用研究[D]. [17] 韩凌波，王强，蒋正锋.一种改进的 k-means 初始聚类中心 南京：南京大学，2011. 选取算法[J].计算机工程与应用，2010，46（17）：150-152. [10] 樊宁.K 均值聚类算法在银行客户细分中的研究[J].计算 [18] 赖玉霞，刘建平.K-means 算法的初始聚类中心的优化[J]. 机仿真，2011，28（3）：369-372. 计算机工程与应用，2008，44（10）：147-149. [11] 钱雪忠，施培蓓，张明阳，等.基于均衡化函数的 k 均值优 [19] 李海涛.品牌可信度对消费者品牌选择偏好的影响研究[D]. 化算法[J].计算机工程，2008，34（14）：60-62. 成都：西南交通大学，2007：11-15. [12] Han Jiawei，Kamber M.数据挖掘：概念与技术[M].范明， 孟小峰，译.2 版.北京：机械工业出版社，2007. [13] Jain A K.Data clustering：50 years beyond K-means[J]. Pattern Recognition Letters，2010，31（8）：651-666. [14] 丁世飞，靳奉祥，赵相伟.现代数据分析与信息模式识别[M]. 北京：科学出版社，2013. [15] 张建民，姚亮，胡学钢.一种面向数据缺失问题的 K-means 改进算法[J].合肥工业大学学报：自然科学版，2008，31 [20] Robins D，Holmes J，Stansbury M.Consumer health infor- mation on the web：the relationship of visual design and perceptions of credibility[J].Journal of the Ameri- Information Science and Technology， can Society for ç 2010，61（1）：13-29. Y T，Yurdakul M.Development of a quick credibility scoring decision support system using fuzzy TOPSIS[J]. Expert Systems with Applications，2010，37（1）：567-574. [21] I