¤ Π Vol 23, No. 4 Ap r. 2006 第 23卷第 4期 　　　 2006年 4月 　　 计算机应用与软件 Computer App lications and Software 基于改进遗传算法的车辆路径问题求解 姜 灵 敏 (广东外语外贸大学信息学院 　广东 广州 510420) 摘 　要 　　一直以来 ,车辆路径优化问题是物流系统中普遍受到关注的热点问题 ,也是一类算法比较复杂的问题 。结合使用遗传算 法和爬山法可以有效地提高解决这类复杂问题的效率 ,并可优化解的质量 。 关键词 　　车辆路径 　遗传算法 　爬山法 　优化 SOL V ING VEH ICL E RO UT ING PRO BL EM BASED O N AN IM PRO VED GENET IC AL GO R ITHM ( S chool of Inform a tion S cience and Technology, Guangdong U n iversity of Foreign S tud ies, Guangzhou Guangdong 510420, China) J iang L ingm in Abstract　　So far, the op tim ization of Vehicle Routing Problem in the logistics system iswidely awared of, and it s also a comp lex p roblem in calculationg. Combining with genetic algorithm s and mountain climbing algorithm we can solve this kind of p roblem effectively and can op ti m ize the result. Keywords　　Vehicle routing　Genetic algorithm s　Mountain climbing algorithm　Op tim ization 1　问题的描述 一直以来 ,车辆路径优化问题是物流系统中普遍受到关注 的热点问题 。车辆路径优化问题分为一般车辆路径问题和有时 间窗车辆路径问题两种 。 一般车辆路径问题是指有 q个货物需求点 ,已知每个需求 点的需求量及位置 ,至多用 k辆汽车从配送中心到达这批需求 点 ,每辆汽车载重量一定 ,安排汽车路线使运距最短 ,且满足每 条路线不超过汽车载重量和每个需求点的需求必须且只能由一 辆汽车来满足的约束条件 ,其目的是使总成本 (如距离 、时间 等 )为最小 。 有时间窗车辆路径问题 (Vehicle Routing Problem with Time W indow, VRPTW )是在上述一般车辆路径问题中加上了客户被 访问的时间窗约束 。它要求每项任务 i在时间范围 [ ai, bi ]内完 成 ,并可根据时间约束的严格与否 ,分为软时间约束的 VRP和 硬时间约束的 VRP。软时间约束的 VRP要求车辆尽可能在规 定时间范围内访问需求点 ,否则将产生等待或延迟损失 ,从而求 得成本最小的车辆路径 ;硬时间约束的 VRP要求车辆必须在给 定的时间范围内访问需求点 ,如果超出这个时间范围 ,所得到的 车辆路径为不可行解 [ 1 ] 。 2　车辆路径问题的数学模型 2. 1　一般车辆路径问题的数学模型 假定配送中心最多可用 K辆车对 q个货物需求点进行运输 配送 ,每部车辆的载重量为 bk ( k = 1, 2, …, K) ,每个需求点的需 求量为 di ( i = 1, 2, …, q) ,需求点 i到 j的运距为 cij,设 nk 为第 k 辆车所包含的需求点数 (若 nk = 0表示未启用第 k辆车 ) , 用集 合 R k 表示第 k条路径 ,其中的元素 rki表示需求点 rki在路径 k中 的顺序为 i (不包含配送中心 ) , 令 rk0 = rk ( nk + 1) = 0表示配送中 心 ,则有如下表示的车辆路径问题的数学模型 。 目标函数 : m inU = ∑ ∑ crk ( i- 1) rki + ∑ crknk rk ( n k +1) ·sign ( nk - 1) K nk k =1 i =1 K k =1 约束条件 : nk drki ≤ bk 　k = 1, 2, …, K ∑ 0 ≤ nk ≤ q　k = 1, 2, …, K i =1 K ∑ k =1 nk = q R k = { rki | rki ∈ { 1, 2, …, q} , i = 1, 2, …, nk } R k1 ∩ R k2 = 　 k1 ≠ k2 其中 : 　　sign ( nk - 1) = 1　nk ≥ 1 0　其它 ( 1) ( 2) ( 3) ( 4) ( 5) ( 6) ( 7) 式 ( 2)保证每条路径上的各需求点的总需求量不超过此路 径的配送车容量 ;式 ( 3)表明每条路径服务的需求点数不超过 总需求点数 ;式 ( 4)要求每个需求点都得到车辆的配送服务 ;式 ( 5)表示每条路径需求点的组成情况 ;式 ( 6)则限制每个需求点 的需求仅能由一个车辆来完成 [2 ]。 收稿日期 : 2004 - 07 - 05。姜灵敏 ,教授 ,主研领域 :计算机算法优 化与应用。 

Π 2. 2　有时间窗车辆路径问题的数学模型 [ 3 ] 以 si 表示车辆到达需求点 i的时刻 , ti 表示车辆在需求点 i 的等待时间 , tij表示车辆由需求点 i行驶到需求点 j的时间 , 则 有以下关系式 : ti =max{ ai - si, 0} aj ≤sj ≤bj 　j = 1, 2, …, q si + ti + tij = sj 　i, j = 0, 1, …, q　i≠j ( 8) ( 9) ( 10) 软时间窗 VRP指车辆如果不能在要求的时间范围内到达 , 则给予一定的惩罚 。若车辆在 aj 之前到达需求点 ,则车辆在此 等待 ,发生了机会成本损失 ,此时 tj 大于 0;若车辆在 bj 之后到 达需求点 ,则服务被延迟 ,须支付一定的罚金 。以 d表示车辆等 待损失的单位机会成本 , e表示车辆在要求时间之后到达所处 以的单位罚值 ,若车辆在 aj 之前到达需求点 j,则产生成本 d ( aj - sj ) ;若车辆在 bj之后到达需求点 j, 则处以罚款 e ( sj - bj ) , 得 到式 ( 11)所示软时间窗 VRP目标函数 。 m inU = ∑ ∑ crk ( i- 1) rki + ∑ crknk rk ( nk +1) ·sign ( nk - 1) + K nk i =1 k =1 q K k =1 q j =1 m ax ( aj - sj, 0) + e∑ 　　　d ∑ 硬时间窗 VRP指车辆必须在要求的时间范围内到达需求 点 ,即必须满足式 ( 10) ,若超出这个时间范围 , 则得到的解为不 可行解 。 m ax ( sj - bj, 0) ( 11) j =1 在式 ( 11) 中 ,若 d = e = M (M → ∞) ,则意味着时间窗约束 必须被满足 ,于是 ,可得硬时间窗的目标函数 。 m inU = ∑ ∑ crk ( i- 1) rki + ∑ crknk ·sign ( nk - 1) rk ( n k +1) K k =1 K nk k =1 i =1 q q j =1 max( aj - sj, 0) +M ∑ 　　　 +M ∑ 各变量的含义同软时间约束的 VRP。由于在该问题中时 间约束必须满足 ,因此应有 M →∞, 但为了便于计算机处理 , 取 M 为适当大的正数 ,于是问题转化为软时间约束的 VRP。 max ( sj - bj, 0) ( 12) j =1 3　应用改进遗传算法对车辆路径问题的求解 [4, 5 ] 车辆路径优化问题是一类具有 NP难性质 [6 ]的复杂问题 , 应用遗传算法求解有着比较显著的优势 [7 ]。从车辆路径优化 模型中可知 ,求解车辆路径问题的关键是合理确定车辆与各需 求点的关系 ,在满足车辆载重量 、时间和各需求点需求量的约束 条件下使得总费用最小 。下面是改进基本遗传算法求车辆路径 问题优化解的方法 。 3. 1　编 　码 染色体 (或个体 )由 1到 x的整数排列串构成 , 其中 x为车 辆数 K与需求点数 q的乘积 。我们可以将其记为 : 其中 : w j ∈{ 1, 2, …, x} , w j1 ≠w j2 　 g = (w1 , w2 , …, w j, …, w x ) ( 13) j1≠j2, j1, j2∈{ 1, 2, …, x}。 染色体中的元素 w j可以表示三个方面的含义 : ①对应需求点的编号为 : m =w j - w j - 1 q ·q (其中 [. ]表示取整 ,下同 ) ②对应的路径编号为 : k = w j - 1 q + 1 ( 14) ( 15) 　 96　　　 　　　 计算机应用与软件 2006年 ③确定需求点 m 是否由车辆 k配送以及确定需求点 m 在 路径 k中的顺序为 j。 3. 2　初始种群的产生 在满足编码方案的前提下 ,随机产生 L 个个体 ,构成初始种 群 。我们将其记为 : 3. 3　可行化过程 G0 = { g0 , g1 , …, gL } ( 16) 将染色体的编码向量映射为满足全部约束条件的可行解称 为可行化 。对于一般车辆路径问题 ,其过程如下 : ①需求点的需求条件满足的标志变量为 dzm = 0 (其中 m = 1, 2, …, q) ; ②令路径 k中的需求点数目 nk = 0;设汽车的载重量为 bk , 令 b′k = bk;路径 k所包含的需求点 R k = ;路径 k中除去配送 中心后的第 i个位置的需求点号为 rki = 0,即此时所有路径皆未 形成 。 (其中 k = 1, 2, …, K; i = 1, 2, …, q) ; ③令 j = 1; ④第 j次确定需求点 m 和路径 k间的关系 ,其中 : m =w j - w j - 1 q ·q　　k = w j - 1 q + 1 ⑤判断 dzm是否等于 0,若等于 0,表明需求点 m 的需求尚 未满足 ,转 ⑥继续判断 ,否则转 ⑦执行 ; ⑥判断需求点 m 的需求量 dm 是否小于或等于 k车辆所剩 余的载重量 b′k ,若成立 ,令 dzm = 1, bk = bk - dm , nk = nk + 1, rknk = m , R k = R k ∪{ m } ,然后转 ⑦执行 ;否则直接转 ⑦执行 ; ⑦ j = j + 1,判断 j是否等于 K ×q + 1, 若不相等 , 转 ④重复 上述过程 ;若相等 ,则表明该染色体中的 K ×q个元素已经判断 完毕 ,此时检查是否所有 dzm = 1成立 。若成立 , 说明在满足各 约束条件的情况下 ,所有的需求点均分配了一个路径 ,构成路径 集合 R T = { R1 , R2 , …, R K } ,即为染色体所对应的原车辆问题的 一个可行解 ;若不成立 ,说明此染色体表示的路径分配方案不满 足约束 ,为原车辆路径问题的一个不可行解 。 3. 4　性能评价 对当前代种群中的每一个染色体 gt ( t = 1, 2, …, L ) ,应用上 述的可行化过程 ,求得对应可行解 R Tt,代入目标函数 : K nk K i =1 k =1 k =1 ( 17) crknk ∑ crk ( i- 1) rk i + ∑ rk ( nk +1) ·sign ( nk - 1) U t = ∑ 即可求得其目标值 。若染色体对应的为非可行解 , 则赋予 目标函数一个很大的整数 U t =M , 我们将目标值的倒数定义为 对应于染色体 gt 的适应值 ft,用其作为个体的性能评价指标 ,指 导个体的进化和竞争 ,其值越大代表该个体的性能越优 ,即对应 的解越接近最优解 。 3. 5　判断及爬山搜索 判断迭代的次数是否达到某一预定值 ,若是 ,停止进化 , 选 性能最好的个体进行爬山搜索 ,以取得最优结果 ;否则 ,继续执 行 3. 6。 其中 ,爬山搜索的过程是 :对个体的每一位基因 , 分别在 1 ～x取值并填入该位置 ,为保证染色体中无相同基因 ,则用该基 因位的原值去代替该基因新值原来所在的位置 , 求得其对应的 适应值 ,最大适应度的染色体所对应的路径集合即为车辆路径 问题的全局最优 (或满意解 ) 。 3. 6　自然选择 将当前代种群的 L 个染色体按适应值 ft 由大到小排列 , 重 

2 2 2 　 第 4期 　　　 姜灵敏 :基于改进遗传算法的车辆路径问题求解 97　　　 排后的染色体 g1 的性能最优 ,计算当前代中的 L 个染色体的选 择概率 : 其中 : pt = q′( 1 - q) t - 1 　 ( t = 1, 2, …, L ) q′= q 1 - ( 1 - q) ′, q = 0. 08 ( 18) ( 19) 用轮盘赌法选择两个个体 。 3. 7　染色体的交叉重组 对于 3. 6中所选择的两个个体 ,按照交叉率 pc 进行交叉重 组 ,交叉规则采用部分交叉法 , 对交叉成功所产生的个体应用 3. 3所述方法对其进行可行性分析 , 按照 3. 4对求得其对应的 适应值 ,并与其父个体进行比较 , 选择四者中性能最好的两个 个体 。 3. 8　染色体的变异 对 3. 7中产生的两个染色体 ,以变异率 pm 对其基因进行变 异操作 ,采用的变异策略是 :首先将其值保存 ,然后重新分别在 1～x取值并填入该位置 , 为保证染色体中无相同基因 , 则用所 保存的值去代替该基因新值原来所在的位置 , 最后对所产生的 个体应用 3. 3所述方法对其进行可行性分析 ,求得其对应的适 应值 ,保留适应度最大的个体 。这种变异具有局部爬山能力 ,可 使染色体改良到它的局部极点 。 3. 9　循 　环 将当前代已执行遗传操作的染色体数目加 2, 判断其是否 小于种群大小 ,若小于 ,则返回 3. 6循环 ;否则 ,将当前代种群的 最优个体 g1 复制到下一代 ,这样可保证最优者生存 , 然后返回 3. 5循环 。 4　实例分析 设有 8个货物需求点和一个为这些需求点提供货物的配送 中心 ,各需求点对配送中心的需求量如表 1所示 ,配送中心只有 两辆汽车用于各需求点的货物配送 ,每辆车的载重量皆为 8000 千克 ,已知配送中心及各需求点的距离如表 2 (其中 0表示配送 中心 ) ,要求合理确定车辆和各需求点间的关系 , 在满足车辆载 重量和各需求点需求的约束条件下 ,安排车辆的行驶路径 ,使总 运行费用最少 ,即总运输里程最小 [ 5 ]。 表 1　需求点对配送中心的需求量表 (单位 :千克 ) 需求点 1 需求量 1000 2 3 4 5 6 7 8 2000 1000 2000 1000 4000 2000 2000 表 2　配送中心及各需求点的距离表 (单位 :千米 ) 需求点 0 0 1 2 3 4 5 6 7 8 0 80 120 150 180 400 200 320 160 1 80 0 130 80 200 100 150 220 200 2 120 130 0 150 200 200 150 150 150 3 150 80 150 0 200 100 180 180 300 4 180 200 200 200 0 200 150 150 200 5 400 100 200 100 200 0 140 180 150 6 200 150 150 180 150 140 0 140 200 7 320 220 150 180 150 180 140 0 200 8 160 200 150 300 200 150 200 200 0 根据前述方法建立车辆路径优化模型 ,采用改进遗传算法 学术期刊文摘 —科技快报 》, 1996. 进行求解 ,经过反复测试 ,确定每代的种群大小为 30,最大进化 代数为 100,交叉率为 0. 80,变异率为 0. 05时 [ 7 ] ,在 tu rboc2. 0环 境下编程求解 ,染争体 2 12 15 14 8 6 5 10 11 9 13 16 3 4 1 7的 适应度最高 ,即其所对应的变量值最低 ,说明选择该染色体所对 应的两辆车的车辆路径分别为 0 0时 , 费 用最省 。 0和 0 2 5 3 8 1 4 7 6 5　小 　结 遗传算法在车辆路径优化中应用比较普遍 ,为了验证本文 所提出的 GA与爬山法结合的算法的有效性 , 我们选取群体规 模 n = 30,群体进化的最大代数为 T = 100、染色体编码长度 L = 40、pc = 0. 75、pm = 0. 02, 分别用具有爬山能力的改进遗传算法 与爬山能力的遗传算法编程求解 。实验结果表明 , 采用 GA 与 具有局部搜索能力的爬山法相结合后 , 当前最佳个体适应值迅 速提高 ,在同等计算量情况下 ,效果比较显著 。 参 考 文 献 [ 1 ] Desrochers M. , Desrosiers J. , and Solomon M. , A New Op tim ization A lgorithm for the Vehicle Routing Problem with Time W indows. Opera tions Research, 1992, 40 (2) : 342～354. [ 2 ] Thangiah. S, Nygard K. and Juell P. Gideon, A Genetic A lgorithm System for Vehicle Routing with Time W indows. In: Proceedings of the Seventh Conference Florida: M iam i, 1991. Intelligence App lications. on A rtificial [ 3 ] Savelsbergh M. , Local Search for Routing Problem swith TimeW indows. Annals of Operations Research, 1985, 46 (4) : 285～305. [ 4 ] 李军 ,“车辆调度问题的分派启发式算法 [ J ] ”,《系统工程理论与实 践 》, 1999, (1) : 27～33. [ 5 ] 谢秉磊 ,“有时间窗约束旅行商问题的启发式遗传算法 [ J ] ”,《西南 交通大学学报 》, 2001, 36 (2) : 210～213. [ 6 ] Solomon M. , Desrosiers J. , Time W indow Constrained Routing and Scheduling Problem s: A Survey. Transportation Science, 1988, 22 ( 1 ) : 110～116. [ 7 ] 王小平、曹立明 ,遗传算法 —理论、应用与软件实现 [M ] ,西安 :西安 交通大学出版社 , 2002. (上接第 72页 ) 提高城市交通系统的运行效率 ,对于改善现有交通环境 、解决交 通拥堵及减少交通负荷等都有很重要的现实意义 。 参 考 文 献 [ 1 ] J. L. Peterson. . Petri Net Theory and the Modeling of System s. Prentice Hall, N. J. 1981. [ 2 ] R. Y. A l Jaar and A. Desrochers. Petri nets in automation and manufac turing. Technical Report RAL99, Rensselaer Polytechnic Institute, New York, 1987. [ 3 ] 黄海军 ,城市交通网络理论平衡分析理论与实践 ,北京 :人民交通出 版社 , 1994. 10. [ 4 ] 乐晓波、陈黎静 ,“Petri网应用综述 ”,《长沙交通学院学报 》, 2004. 6. 51～55. [ 5 ] 林闯 、魏丫丫 ,“随机进程代数与随机 Petri网 ”,《软件学报 》, 2002, 13 (2) : 203～213. [ 6 ] 范玉顺、杨建华 ,“FMS可靠性建模与分析的 Petri网方法 ”,《中国