Computer Engineering and Applications 计算机工程与应用 2013，49（2） 5 多车场车辆路径问题的改进粒子群算法 王铁君 1，邬开俊 2 WANG Tiejun1, WU Kaijun2 1.西北民族大学 数学与计算机科学学院，兰州 730030 2.兰州交通大学 电子与信息工程学院，兰州 730070 1.School of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China 2.School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China WANG Tiejun, WU Kaijun. Study on multi-depots vehicle routing problem based on improved particle swarm optimiza- tion. Computer Engineering and Applications, 2013, 49（2）：5-8. Abstract：Multi-Depots Vehicle Routing Problem（MDVRP）is a kind of NP combination problem which possesses important practical value. In order to overcome PSO’s premature and slow convergence, a new improved algorithm is put forward, it adopts co-evolutionary thought and at the same time pattern search method is introduced while the search falling into local opti- mum. In this paper, a kind of new particles coding method is constructed and the solution algorithm is developed. The simula- tion results show that the algorithm has better optimal speed and optimal efficiency than GA and PSO, so it proves the algorithm used to optimize MDVRP is feasible and effective. Key words：vehicle routing problem; multi-depots; pattern search; Particle Swarm Optimization（PSO）; co-evolutionary 摘 要：多车场车辆路径问题是一类实用性很高的 NP 难解问题。针对标准粒子群算法易早熟、收敛速度慢的缺陷，提出 了一种新的改进算法，该算法采用协同进化思想，同时在搜索陷入局部最优的情况下引入了模式搜索方法。针对多车场 车辆路径问题构造了一种新的粒子编码方法，建立了相应的数学模型，并介绍了该算法的详细实现过程。仿真结果通过 和遗传算法和标准粒子群算法比较，表明该算法具有更好的寻优速度和寻优效率，从而证明了提出的算法用于优化多车 场车辆路径问题是可行和有效的。 关键词：车辆路径问题；多车场；模式搜索；粒子群优化；协同进化 文献标志码：A 中图分类号：TP301.6 doi：10.3778/j.issn.1002-8331.1207-0355 车 辆 路 径 问 题（Vehicle Routing Problem，VRP）是 Dantzig Z 和 Ramser J 于 1959 年首次提出[1]，是指对一系列 发货点（或收货点）组织适当的行车路线，要求在满足一定 约束条件前提下，达到一定的目标（诸如费用最小、路程最 短、消耗时间最少等）。 由于 VRP 已被证明是一个 NP 完全问题，而多车场车 辆 路 径 问 题（Multiple-Depot Vehicle Routing Problem， MDVRP）是基本车辆路径问题的延伸，它的实现比 VRP 问 题更加复杂。只有在问题规模较小时才有可能求得其精 确解，尤其对于大维数问题，很难求得最优解。近年来，遗 传算法、蚁群算法等启发式优化算法在解决这一类问题中 得到了较好的应用[2-4]，但由于这些算法普遍存在搜索时间 长、易于陷入局部最优解等问题。因此如何针对多车场车 辆路径问题的特点，构造运算简单，寻优效果优异的启发 式优化算法，对许多可转化为多车场车辆路径问题求解的 组合优化问题具有十分重要的意义。 粒子群算法（PSO）是新近出现的一种模仿鸟群找食飞 行的仿生算法[5]，有着个体数目少、计算简单、收敛速度快、 易于实现等优点，在车辆路径优化问题中已得到应用 [6-7]， 取得了非常不错的效果，但由于粒子群算法易于停滞、易 陷入局部最优等问题，故本文将粒子群算法和协同进化思 想结合起来，并将模式搜索方法嵌入粒子群算法中，提出 一种新的采用模式搜索的协同粒子群算法，并将该算法应 用于多车场车辆路径优化。通过实验证明，本算法在减少 基金项目：国家社科基金项目（No.12CGL004）；甘肃省教育厅科研项目（No.1118B-03）；西北民族大学中央高校基本业务费专项资金项目 （No.ZYZ2011080）。 作者简介：王铁君（1981）—），女，博士生，讲师，CCF 会员，研究领域：智能优化算法、车辆路径问题优化；邬开俊（1978—），男，博士生，副 教授，CCF 会员，研究领域：智能优化算法、应急物流。E-mail：wtj@mail.lzjtu.cn 收稿日期：2012-07-24 修回日期：2012-09-17 文章编号：1002-8331（2013）02-0005-04 CNKI 出版日期：2012-10-18 http://www.cnki.net/kcms/detail/11.2127.TP.20121018.1553.011.html 

6 2013，49（2） Computer Engineering and Applications 计算机工程与应用 计算时间和避免早熟现象方面均取得了很好的效果。 1 多车场车辆路径问题描述及数学模型 多车场车辆路径问题可描述为：有 M 个车场，分别拥 (m = 1 2 M ) 辆，现已知客户 i （这里用距离来代替运输成本）， ij 有容量为 q 的车辆为 K m 到客户 j 的运输距离为 d i 需要对 N 个客户进行货物分送，客户 i 的货物需求为 g i (i = 1 2 N ) ，且 g < q ，每个客户可以由任意一个车场 的车辆服务，但只能由一辆车服务一次，每辆车完成分送 任务后必须返回原车场，要求安排合适的车辆行驶路线， 使各车场的车辆能满足所有客户的需求的条件下，并使车 辆总的行驶距离最低。 设用户编号为 1，2，…，N ，车场编号为 N + 1 N + 2 N + M ，定义变量如式（1）所示： xmk ij = ì 1, 车场m的车辆k从客户i行驶到客户j í 0, 否则 î 从而得到多车场的车辆路径数学模型如式（2）： f =min å N + M å N + M å M å m K i = 1 j = 1 m = 1 k = 1 d xmk ij ij （1） （2） 约束条件设定如式（3）～式（8）所示： å N å  K K m xmk ij m ，i = m Î{N + 1 N + 2 N + M } （3） i = 1 k = 1 K å N + M å M å m i = 1 m = 1 å N + M å M å m j = 1 m = 1 k = 1 k = 1 K = 1 ，i Î{1 2 N } = 1 ，j Î{1 2 N } xmk ij xmk ij  1, i = m Î{N + 1,N + 2, N + M } N å i = 1 xmk ij N = å xmk ij j = 1 k Î{1 2 K } m  q, m Î{N + 1,N + 2, N + M } xmk ij k Î{1 2 K } m （4） （5） （6） （7） g N å i = 1 N + M i å j = 1 N + M å i = N + 1 xmk ij = 0,i = m Î{N + 1,N + 2, N + M } N + M = å xmk ij j = N + 1 k Î{1 2 K } m （8） 模型中，式（2）为目标函数，为车辆最低运输成本；式 （3）限定各车场派出车辆总数不超过该车场拥有的车辆 数；式（4）和式（5）保证每个客户只能被一辆车服务一次； 式（6）确保每个车辆都是从各自的车场出发并返回该车 场；式（7）表示每辆车的载重量不能超过它的载重能力；式 （8）确保车辆不能从一个车场行驶到另一个车场。 2 粒子群优化算法 2.1 标准 PSO 粒子群优化算法是人们受到真实世界中鸟群搜索食 物启发，由 Kennedy 和 Eberhart 于 1995 年提出的一套基于 群体理论的智能优化算法 [5]，其基本机理是通过群体之间 的信息共享和个体自身经验来修正个体行动，最终求取最 (x 优化问题的解。由 n 个粒子组成的群体对 D 维（就是每个 = 粒子的维数）空间进行搜索。第 i 个粒子位置表示为：X i , v ) ， ) 为第 i 个粒子目前为止搜索到的最优 iD  p ) 为整个粒子目前为止搜索到的 g2 ,x i1 i2  p = ( p p i1 位置，p ) ，对应的速度可以表示为 V iD  p i2  p = ( p g1 , x ,v i1 = (v gD iD i2 g i i 最优位置。粒子 i 在第 k +1 次迭代时第 d 维速度 vk + 1 位置 xk + 1 id 和 的更新公式如式（9）和式（10）所示。 = ωvk + c id 1 + vk + 1 - xk id - xk id ( pk gd ( pk id ) + c r 1 r ) 2 2 = xk id id id vk + 1 id xk + 1 id （9） （10） 为加速 式中，ω 是惯性权重，即保持原来速度的系数；c 1 常数，分别表示为粒子跟踪自己历史最优值的权重系数和 跟踪群体最优值的权重系数；r 为 0~1 之间的随机数。 1 2.2 协同粒子群优化算法 、c ，r 2 2 自然界中各生物种之间存在着彼此制约、彼此促进的 关系，这种关系称为协同进化 [8]。它借鉴了生态学的种群 协同理论，通过采用种群间的自动适应、自动调节原理来 提高各自和全局的性能。针对 PSO 算法收敛速度慢、易陷 入局部最优解的问题。本文采用协同粒子群优化算法，其 主要思想是：首先使 n 个子群独立进行搜索，每个子群根据 自己搜索到的最优点来修正群中粒子的位置和速度，比较 这些最优点，找出全局最优粒子，采用优胜劣汰的策略，用 全局最优粒子代替每个子群中的最差粒子，用全局最优粒 子作为指导信息来影响每个子群的进化，但又不改变每个 子群的行为方向，这样就达到了两个效果：一是使局部的 搜索性能大大提高；二是通过种群信息正反馈的引入，避 免了算法早熟的现象发生，从而使算法性能得到了较大的 改进。 2.3 模式搜索算法 模式搜索算法是由 Hooke 和 Jeeves 在 1961 年提出的[9]， 是一种求解优化问题的直接搜索方法，它由两部分组成， 一种是“探测移动”，目的是揭示目标函数变化规律，探测 函数的下降方向；另一种是“模式移动”，目的是利用发现 的函数变化规律沿着有利方向加速寻找更好的点。模式 搜索方法是先通过“探测移动”寻找最佳点信息，然后利用 “模式移动”沿着找到的最佳点信息前进，这两种移动操作 交替进行直到步长 δ 小于事先设定的某个正数 ε 为止。 2.3.1 探测移动 探 测 移 动 在 某 个 已 知 点 附 近 ，对 其 中 一 个 可 行 解 进行步长探测移 x Î R n ，分别对其 n 个正反坐标轴方向 e 动。如探测成功（至少有一个下降步），则进行模式移动， 否则，缩短步长 δ = 0.5δ 继续探测。直到 δ < ε 完成探测移 动，则认为找到了最优值。坐标轴方向 e 为一个单位向 = (0 0 1 0)T 。 量，其第 i 个值为 1，其余全部为 0，如 e 2.3.2 模式移动 3 i i 在第 t 步可行解 x(t) 模式移动后，得到 x(t + 1) ，如果 f (x(t + 1)) < f (x(t)) ，则按式（11）进行模式移动： x(t + 1) = x(t + 1) + (x(t + 1) - x(t)) （11） 

王铁君，邬开俊：多车场车辆路径问题的改进粒子群算法 2013，49（2） 7 3 采用模式搜索的协同粒子群求解多车场车辆 路径 3.1 粒子编码策略 粒子群优化算法的关键问题是粒子的位置与问题的 解相对应，本文构造一种新的粒子编码方式，用 3n 维的向 量 X 表示 m 个车场、l 辆车、n 个客户任务的车辆路径优 化问题。粒子的第一维 X 表示为服务客户的车场信息； 表示为服务客户的车辆信息；粒子的第三 粒子的第二维 X 维 X 3.2 粒子的解码策略 表示为各车辆的行驶距离。 r s t t t t 由于 X 表示为各车辆的行驶距离，要转换对于车辆 i 进行调整。调整函数可按照向 的行驶路径次序，必须对 X 元素的大小顺序来确定，即首先寻找车辆服务的需求 量 X 的大小，从小到大进行排序编 点 i ，然后按照 i 对应的 X 号，从而确定车辆 i 的行驶路径次序。例如，假设有 10 个 客户、2 个车场，分别有 2、3 辆车，若某粒子的位置向量 X 如表 1 所示，则调整后的位置向量 X 如表 2 所示。 t 表 1 调整前的位置向量 X 1 1 1 0.3 2 1 1 1.2 3 2 3 0.6 4 1 2 2.3 5 2 4 4.8 6 2 4 1.1 7 2 4 2.9 8 1 2 3.9 9 2 5 2.8 表 2 调整后的位置向量 X 1 1 1 1 2 1 1 2 3 2 3 1 4 1 2 1 5 2 4 3 6 2 4 1 7 2 4 2 8 1 2 2 9 2 5 2 10 2 5 1.7 10 2 5 1 客户 Xr Xs Xt 客户 Xr Xs Xt 那么对应的解路径为： 车场 1：车辆 1：1→2 车辆 2：4→8 车场 2：车辆 3：3 车辆 4：6→7→5 车辆 5：10→9 此粒子的编码与解码可以保证使每个客户都得到服 务，并限制每个客户仅能由某一辆车完成，使解的可行化 过程计算大大减少。 3.3 算法的过程描述 步骤 1 生成初始种群 X 1 。设置每个粒子群的规模 n ，最大迭代 和算法参数（惯性权重系数 ω 、加速因子 c 1 次数 N 和粒子的维数 D ）。 、c 2 max 步骤 2 对于第 G 代种群，并计算每个子群中粒子的适 应度值，并挑选出一个最优的个体 X G best 。 步 骤 3 将 第 G 代 种 群 分 成 s 个 大 小 相 等 的 子 种 群 ，Xˉ G 取代每个子群 2 ，并用全局最优粒子 X G best ，…，Xˉ G s Xˉ G 1 的最差粒子，生成新的子种群 Xˉ G 1 ，Xˉ G 2 ，…，Xˉ G s 。 步骤 5 对种群 Xˉ G + 1 进行模式搜索，得到模式搜索后 的种群 X G + 1 。 步骤 6 令 G = G + 1 ，判断当前迭代次数 G 是否达到迭 ，如不满足，返回步骤 2，否则，输出群体当前最 代次数 N 优解。 max 4 实验例证 为了验证算法的可行性，对一个计算机随机生成的 MDVRP 进行求解，客户和车场位置均分布在 10×10 的范 围内，客户位置和需求量见表 3，车场的位置和拥有的车辆 数见表 4，每辆车的最大载重量为 20。 表 3 客户信息 客户 位置 需求量 客户 位置 需求量 1 2 3 4 5 6 7 8 9 10 11 12 13 （3，1） （10，4） （1，8） （9，3） （5，4） （9，6） （0，2） （2，4） （6，7） （2，9） （6，6） （8，9） （5，10） 4 7 4 6 7 2 6 2 7 9 8 3 8 14 15 16 17 18 19 20 21 22 23 24 25 （8，7） （2，2） （4，0） （6，2） （8，0） （7，1） （5，2） （7，6） （5，5） （9，1） （2，0） （3，6） 3 5 3 5 1 3 5 8 4 4 11 5 表 4 车场信息 车场 位置 26 27 28 （3，3） （7，4） （4，8） 拥有车数量 5 5 5 = c 在本算例中，令粒子数 n = 100 ，s = 4 ，ω = 0.6，c 1 = 2.0 ，最大迭代次数为 1 500。分别用标准粒子群算法、遗传 算法和本文算法对该算例进行计算，求得该算例的最优调 度方案是 3 个车场的 7 辆车辆参与调度，每辆车的发车车 场、行驶路线及行驶距离如表 5 所示，目标函数随迭代次数 变化的曲线如图 1 所示。 2 表 5 车辆的发车车场、行驶路线及行驶距离 车场 26 26 27 27 27 28 28 合计 行驶路径 行驶路程 26→15→1→16→20→26 26→8→7→24→26 27→17→19→18→23→4→27 27→2→6→14→21→27 27→11→22→5→27 28→10→3→25→28 28→9→12→13→28 8.72 10.23 10.71 10.06 6.65 8.72 10.47 65.56 步骤 4 将生成的新的 s 个子群合并成一个新的种群 Xˉ G + 1 。 从仿真结果容易看出，本文所采用的算法能够快速准 确地求出多车场车辆路径问题的最优解，而且搜索到最优 

8 2013，49（2） Computer Engineering and Applications 计算机工程与应用 160 150 140 130 120 110 100 90 80 70 60 程 路 总 GA PSO 本文算法 0 500 1 000 1 500 迭代次数 图 1 算例的 GA、PSO 和本文算法性能比较 值的时间和效率均优于遗传算法和标准粒子群算法。这 是因为本文采用的 s 个子群同时进行优化，子群通过个体 替代相互传递信息，信息采取的是正反馈，同时算法在陷 入局部最优的情况下采用模式搜索方法，有效地防止了群 体的退化，提高了搜索效率。 5 结束语 针对粒子群算法可能出现早熟收敛的缺点，本文提出 了一种新的改进算法，该算法引入协同进化思想，同时在 粒 子 群 算 法 陷 入 局 部 最 优 的 情 况 下 引 入 了 模 式 搜 索 方 法。针对多车场车辆路径问题构造了一种新的编码方法， 建立了相应的优化模型和求解算法。通过实例验证，本文 （上接 4 页） 参考文献： [1] Kim H N，Ji A T，Ha T.Collaborative filtering based on colla- borative tagging for enhancing the quality of recommendation[J]. Electronic Commerce Research and Applications，2010，9： 73-83. [2] Hofman T.Collaborative filtering via Gaussian probabilistic latent semantic analysis[C]//Proceedings of International Conference on SIGIR’03.Toronto，Canada：[s.n.]，2003. [3] Koren Y，Bell R，Volinsky C.Matrix factorization techniques for recommender systems[J].IEEE Computer，2009，42（8）：30-37. [4] Shan H，Banerjee A.Generalized probabilistic matrix factori- zations for collaborative filtering[C]//Proceedings of the 2010 IEEE International Conference on Data Mining.Washington， DC，USA：[s.n.]，2010：1025-1030. [5] Blei D，Ng A，Jordan M.Latent dirichlet allocation[J].Journal of Machine Learning Research，2003，3：993-1022. [6] Steyvers M，Griffiths T.Probabilistic topic models[M]//Latent semantic analysis：a road to meaning.[S.l.]：Lawrence Erlbaum， 2006. [7] Monay F，Gatica-Perez D.Modeling semantic aspects for cross- media image indexing[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29（10）：1802-1817. [8] Bei D M，Laferty J D.Correlated topic models[C]//Advances Information Processing Systems 18.Cambridge， in Neural 提出的算法在时间和迭代次数方面远低于标准粒子群算 法，为多车场车辆路径优化提供了一种新的思路。 参考文献： [1] Dantzig G，Ramser J.The truck dispatching problem[J].Man- agement Science，1959，6：58-102. [2] 王晓博，李一军.多车场多车型装卸混合车辆路径问题研究[J]. 控制与决策，2009，24（12）：1769-1774. [3] 杨元峰.多车场多车型车辆路径问题的改进遗传算法[J].计算 机与现代化，2008（9）：10-13. [4] 陈美军，张志胜，陈春咏，等.多车场车辆路径问题的新型聚类 蚁群算法[J].中国制造业信息化，2008，37（11）：1-5. [5] Kennedy J，Eberhart R.Particle swarm optimization[C]//Pro- ceedings of IEEE International Conference on Neural Net- works.[S.l.]：IEEE Press，1995：1942-1948. [6] 刘志雄.基于粒子群算法的物流车辆优化调度研究[J].武汉科 技大学学报，2009，32（6）：615-618. [7] 张元标，吕广庆.基于混合粒子群算法的物流配送路径优化问 题研究[J].包装工程，2007，28（5）：10-12. [8] Lung R I，Dumitrescu D.A new collaborative evolutionary- swarm optimization technique[C]//Proceedings of the 2007 GECCO Conference Companion on Genetic and Evolutionary Computation.London：[s.n.]，2007：2817-2820. [9] Hooke R，Jeeves T A.Direct search solution of numerical and statistical problems[J].Ass Comput Mach，1961，8：212-229. MA：MIT Press，2006. [9] Hu Y，Koren Y，Volinsky C.Collaborative filtering for implicit feedback datasets[C]//Proceedings of the 2008 8th IEEE In- ternational Conference on Data Mining.Washington，DC，USA： [s.n.]，2008：263-272. [10] Pan R，Zhou Y，Cao B，et al.One-class collaborative filtering[C]// Proceedings of the 2008 8th IEEE International Conference on Data Mining.Washington，DC，USA：[s.n.]，2008：502-511. [11] Mimno D，Wallach H M，McCallum A.Gibbs sampling for logistic normal topic models with graph-based priors[C]// NIPS Workshop on Analyzing Graphs.Whistler，BC：[s.n.]， 2008. [12] Hofmann T.Latent semantic models for collaborative filtering[J]. ACM Transactions on Information Systems，2004，22（1）. [13] Yu Li，Liu Lu，Li Xuefeng.A hybrid collaborative filtering recom- method for multiple-interests and multiple-content mendation in E-commerce[J].Expert Systems with Applica- tions，2005，28：67-77. [14] Liu Duen-Ren，Shih Ya-Yueh.Hybrid approaches to product recommendation based on customer lifetime value and pur- chase preferences[J].The Journal of Systems and Software， 2005，77：181-191. [15] Zhang Fuguo.Research on recommendation list diversity of recommender systems[C]//International Conference on Man- agement of e-Commerce and e-Government.Nanchang，China： [s.n.]，2008：72-76.