2004车辆路径问题的双种群遗传算法求解方法

DOI ：10.13196/j.cims.2004.03.64.zhaoyw.011

第10卷第3期2004年3月计算机集成制造系统) CIMS

Computer Integrated Manufacturing Systems Vol. 10No. 3Mar. 2004

文章编号:1006-5911(2004) 03-0303-04

车辆路径问题的双种群遗传算法求解方法

赵燕伟1, 吴斌1, 蒋丽2, 董红召1, 王万良1

(1. 浙江工业大学机电学院, 浙江杭州 310014; 2. 杭州商学院, 浙江杭州 310032)

摘要:针对标准遗传算法在求解车辆路径问题中出现的早熟、收敛, 易陷入局部极值点的问题, 提出双种群遗传算法求解车辆路径问题的方法。在求解过程中, 初始化两个种群, 分别选择不同的交叉、变异概率, 在一次迭代完成后, 交换种群间的优秀个体所携带的遗传信息, 以打破种群内的平衡态, 跳出局部最优解。通过实验仿真, 将双种群遗传算法与其他各种启发式算法进行比较, 双种群遗传算法比标准遗传算法显著提高了全局收敛性能, 是解决车辆路径问题的有效方法。

关键词:车辆路径问题; 遗传算法; 计算智能; 物流中图分类号:TP14 文献标识码:A

0 引言

车辆路径问题(Vehicle Routing Problem, VRP) 是物流研究中的重要内容。该问题是物流配送系统中的常见问题, 如邮件的投送, 飞机、火车及公交的调度等。选择适当的行车路径, 可以加快客户需求的响应速度, 提高服务质量, 降低服务成本。车辆路径问题是由G. Dantzig 于1959年首先提出的。在物流服务网络中, 已知客户和配送中心的位置, 在车辆最大负载、客户需求的前提下, 设计车辆路径, 使其达到运输成本最少、时间最短等目标。VRP 是一个NP 完全问题, 对于此类问题, 只有当其规模较小时, 才能求其精确解。因此, 如何针对车辆路径问题的特点, 构造运算简单、性能优异的启发式算法, 不仅对物流系统, 而且对许多可以转化为车辆路径的组合优化问题都有十分重要的意义。

许多智能算法被用于求解车辆路径问题, 如禁忌搜索[1]、模拟退火[2]、蚁群算法[3]等。其中, 遗传算法是被研究最多的一种算法。但标准遗传算法容易陷入局部极值解, 出现/早熟收敛0现象。为此, 人

收稿日期:2003-04-21; 修订日期:2003-08-06。

们提出了多种改进方法, 如将遗传算子中的交叉算子进行改进, 应用单亲遗传算法启发式算法结合[6]等。

[4]

[5]

, 将遗传算法与

本文研究了双种群遗传算法(double populations genetic algorithm) 在车辆路径问题中的应用, 实验结果证明, 该算法是解决车辆路径问题的一种有效方法。

1 车辆路径问题的数学模型

对车辆路径问题可描述如下:假定配送中心最多可以用K 辆车对L 个商店进行运输配送, 每个车辆载重为b k (k =1, 2, , , k ) , 每个商店的需求为d i (i =1, 2, , , L) , 商店i 到商店j 的路径长度为c ij , 设n k 为第k 辆车所包含的商店数(若n k =0, 表示未启用第k 辆车) , 用集合R k 表示第k 条路径, 其中的元素r ki 表示商店在路径k 中的顺序为i (不包含配送中心) 。令r k 0=r k (n k +1) =0表示配送中心, 则车辆路径问题的数学模型为:

J =

k=1

E {E c r

i=1

k(i-1) k i

+c r kn r k (n -1) @

基金项目:国家863/CIMS主题资助项目(2002A A412610) ; 浙江省重大科技攻关项目(2003C11033) ; 浙江省科技计划项目(2004C33084) 。:(19-) , , , ,

304计算机集成制造系统) CIMS 第10卷

sign (n k -1) }

(1) (2) (3) (4)

定商店m =s j -

s j -

s. t.

i=1

E d r

s j -@L 与路径k =L

[b k , k =1, 2, 3, , , K

0[n k [L , k =1, 2, 3, , , K

k=1

j +1的关系([]表示取整数) , 即确定L

E n k =

商店m 是否由车辆k 配送, 以及商店m 在路径k 中的顺序的次序t(t 为路径k 中当前的商店数, 即n k 的当前值) 。随机产生两组染色体G A h 和G Bh (h =1, 2, , , n, 其中n 为一代种群中的个体数) , 染色体各不相同, 这就是第一代种群。

R k ={r ki |r ki I {1, 2, , , L },

i =1, 2, , , n k }R k 1H R k 2=É, P k 1X k 2

其中,

sign =

1, n k \10, 其他

(5) (6) (7)

在上式中, 不等式(2) 保证每条路径上的各商店的总需求量, 不超过该条路径配送车辆的载重量, 式(3) 表明每条路径服务的商店数不超过总商店数, 式(4)要求每个商店都得到车辆的配送服务, 式(5) 表示每条路径的商店组成, 式(6) 则限制每个商店的需求仅能由一辆车辆来完成。

212 解码过程

将染色体的编码向量映射为满足全部约束条件的可行解, 具体过程如下:

(1) 初始化各变量, 令商店需求条件满足的标志变量d zm =0(m =1, 2, , , L ) , 路径k 中各商店数目

n k =0, b c k =b k , R k =É(k =1, 2, , , L ) , 路径k 中除去配送中心后第i 个位置的商店为r ki =0(i =1, 2, , , L ) , 即此时所有路径均未形成。

(2) j =1。(3) 由s j 求取m =s j -s j -s j -@L 和k =L

2 车辆路径问题的双种群遗传算法求解

标准遗传算法是针对一个宏观的种群进行选择、交叉、变异三种操作, 类似于人类进化过程, 一群人随着时间的推移而不断地进化, 具备越来越多的优良品质。然而, 由于他们的生长、演化、环境和原始祖先的局限性, 经过相当长时间后, 将逐渐进化到某些特征相对优势的状态, 当一个种群进化到这种状态, 称之为平衡态, 这个种群的特性就不会再有很大的变化。

双种群遗传算法是一种并行遗传算法, 它使用多种群同时进化, 并交换种群之间优秀个体所携带的遗传信息, 以打破种群内的平衡态达到更高的平衡态, 跳出局部最优。

在操作时, 首先建立两个遗传算法群体, 即种群A 和种群B, 分别独立地进行选择、交叉、变异操作, 且交叉概率、变异概率不同。当每一代运行结束以后, 产生一个随机数num, 分别从A, B 中选出最优染色体和num 个染色体进行杂交, 以打破平衡态。

因为在双种群遗传算法中, 每一种群都是按照标准算法进行操作的, 所以下面关于适应度、选择、交叉和变异的介绍, 都是针对一个种群描述的。

s j -+1, 确定商店m 和路径k 的关系。L

(4) 判断d zm 是否等于0。若d zm 等于0, 则表明商店m 的需求尚未满足, 此时可判断商店m 的需求量

c c

d m

d m , n k =n k +1, r kn k =m, R k =R k G {r kn k }; 若不成立, 则转过程(5) 。若d zm 不等于0, 则直接转过程(5) 。

(5) j =j +1, 转过程(3) , 重复上述过程, 直到j =K @L +1。此时, 检查是否所有的d zm =1(m =1, 2, , , L ) 成立, 若成立, 说明在满足各约束条件的情况下, 所有的商店都分配了一条路径, 构成的路径集合R T ={R 1, R 2, , , R k }为染色体所对应的车辆路径问题的一个可行解; 若不成立, 说明此染色体表示的路径分配方案不满足约束, 为车辆路径问题的一个不可行解。

213 适应度计算

对种群中每一染色体G h =(h =1, , , L ) 解码, 求得对应的可行解。根据式(1) 求得目标函数值Z h ; 若染色体Z h 对应不可行解, 赋予其一个很大的

整数M 。令染色体的适应度函数为f h =1/Z h 。

211 染色体的构造方法

1K @L , (s 1, s 2, , s K @L j 214 选择

, 按f ,

第3期赵燕伟等:车辆路径问题的双种群遗传算法求解方法305

群中剩下的n -1个染色体用轮盘赌选择法产生。

215 交叉重组

对产生的新种群, 按照交叉概率p c , 采用PMX 交叉法则, 进行交叉重组。216 染色体变异

染色体按照变异概率p m , 进行变异操作。变异算子采用的策略如下:随机产生变异点j m (m =1, 2, , , K @L ) , 将染色体循环左移j m 个基因。例如, 染色体:[***********]21315; j m =3, 经变异操作后, 产生的染色体为:[***********]15127。217 种群交叉

将两个种群中的最优解取出, 再在每个种群中随机选取num 个染色体, 将这num+1个染色体互换, 进入对方种群。

行20次并加以比较, 其结果如表2所示。表2中, 第1组表示标准遗传算法(种群规模是60, 交叉概率是0. 8, 变异概率是0. 05) , 第2组表示双种群遗传算法(每个种群规模是30, 交叉概率分别是0. 7, 0. 8, 变异概率是0. 05和0. 1) 。两种算法均迭代50次。第1组的平均值是73. 25, 第2组的平均值是69. 575。从表中可以看出, 在参数(种群规模、交叉、变异概率) 大致相当的情况下, 双种群遗传算法比标准遗传算法更接近最优解。

表2 双种群遗传算法与标准遗传算法的比较

实验结果实(112

7571. 57273. 575

7372. 575. 573. 5

3 实验结果及分析

将上述算法用于求解有8个商店、1个配送中心、2辆车(每辆载重量都为8吨) 的物流配送系统的车辆路径问题, 商店与商店之间距离的具体数据如表1所示。求得问题的最优解是67. 5, 行车路径为(0-2-8-5-3-1-0, 0-6-7-4-0) , 与已知的最优结果一致。

表1 各个商店之间距离

距

2345678910

7069. 567. 57111

1269

6957267. 571. 56915

1673

商0

727375. 57271

7573. 571. 575

5697067. 556969. 571

012345678需求量(吨)

0467. 5920101680

406. 541057. 511101

66. 507. 510107. 57. 57. 52

7. 547. 5010599151

1010100107. 57. 5102

[1**********]7. 51

107. 57. 597. 5707104

16117. 597. 5970102

8107. 515107. 5101002

(3) 对于此问题, 根据文献[4]和[5]中的结果, 与本次实验的结果相比较。在文献[4]和[5]中都没有给出种群规模, 仅给出了迭代次数和交叉变异概率。在此, 都选取迭代50次的平均结果进行比较(见表3) 。

表3 几种遗传算法的比较

算法平均结果(距离)

改进交叉算子[4]69. 6

双种群遗传算法69. 575

单亲遗传算法[5]69. 3754

(4) 将双种群遗传算法应用到Christofieds 等人提出的E51k5问题, 计算结果与其他启发式算法比较, 如表4所示(第一列各种算法, 第二列为各种算法所得的最优结果) 。

从表4可以看出, 双种群遗传算法搜索到了比 (1) 当用双种群遗传算法, 每一个种群规模为50, 迭代次数为50, 交叉概率分别为0. 8和0. 7, 变异概率分别为0. 03和0. 05。最优结果的进化图, 如图1所示。

306

表4 启发式算法的比较

算法

节约法(Clarke&Wright . s Savings Algorithm) [8]

分配法(Fisher &J aikumar . s Generalized Ass ignment Heuristic)

[8]

计算机集成制造系统) CIMS 第10卷

结果(距离)

[***********]528

[10]

扫描法(Gillett &Miller . s Sweep Algorithm) [8]树搜索法(TreeSearch Algorithm) 禁忌搜索(TabuSearch Al gorithm) 蚁群算法(AntSys tem Algorithm) 模拟退火(SimulateAnnealing )

[8][8]

[3]

[9]

邻域搜索(LargeNeighborhood Search) 双种群遗传算法已知最优解

524524521

4 结论

对于VRP 问题, 采用标准遗传算法, 容易出现/早熟收敛0、陷入局部极值等情况。利用双种群遗传算法, 对两个种群进行交叉, 可以增加个体的多样性, 扩展解的搜索空间, 跳出局部极值解。通过和其他算法的比较, 结果表明, 双种群遗传算法是求解车辆路径问题的有效方法。参考文献:

[1] TAN K C, LEE L H, ZHU Q L, et al. Heusistic methods for vehicle

routing problem with time windows [D].Artificial Intelligent in Engi-neering, 2000. 281-295.

[2] BENT R, HEN TENRYCK P V. Two stage hybrid local search for the

vehicl e routing proble m with time windows [R].Brown Universit y Tech-nical Report, 2001.

[3] BER ND B, RICHAR D F H, CHRISTINE S. Applying the ant system

to the vehicle routing proble m [A].Meta -heuris tics -Advances and Trends in Local Search Paradigms for Opti mization [C].Boston:Kluw-er, 1997. 1-11.

[4] ZHANG Liping, CHAI Yueting. Improved genetic algorithm for vehicle

routing problem[J].Systems Engineering -Theory &Practics,2002, 22(8) :79-84(in Chines e) . [张丽萍, 柴跃廷. 车辆路径问题的改进遗传算法[J].系统工程理论与实践, 2002, 22(8) :79-84. ][5] X IA O Peng, LI Maoj un, ZHAN G Junping. Single relative genetic algo-rithm for vehicle routing problem [J]. Computing Technology and Au-tomai on, 2000, 19(1) :26-30(in Chines e) . [肖鹏, 李茂军, 张军平. 车辆路径问题的单亲遗传算法[J ].计算技术与自动化, 2000, 19(1) :26-30. ]

[6] POTVIN J, DUBE D, ROBILL AR D C. Hybrid approach to vehicle

routing us ing neural networks and genetic al gorithm[J].Applied Intel-ligence, 1996, 6(3):241-252.

[7] J IANG Dali , Y ANG Silong, DU Wen. A study on the genetic al gorit hm

for vehicle routing problem [J ].Sys tems Engineering -Theory&Practics,1999, 19(6) :40-46(in Chinese) . [姜大立, 杨四龙, 杜文. 车辆路径问题的遗传算法研究[J]. 系统工程理论与实践, 1999, 19(6):44-45. ]

[8] BRA M EL JB, SIMCHI -LEVI D. A location based heuristic for gener-al routing problems [J].Operations Research, 1995, 43:649-660. [9] MARINA KIS Y, MIGDALA S A. Heuris tic solutions of vehicle routing

problems in suppl y c hain management [DB /OL].http://neo.lcc. uma. es /radi-aeb /WebVRP/data/articles/HeurVRP. PS, 2001-07. [10] SHAW P. Us ing constraint programming and l ocal search method to

solve vehicle routing proble m [A].Proceedings of the Fourth Interna-tional Conference on Principles and Practice of Constraint Program-ming (CP . 98) [C].Springer -Verl ag, 1998. 417-431.

Double Populations Genetic Algorithm for Vehicle Routing Problem

Z HAO Yan -wei 1, W U Bin 1, JIANG Li 2, DONG Hong -zha o 1, WANG Wan -lian g 1

(1. Dep. of Mechanical Eng. , Zhejiang Univ. of Tech. , Hangzhou 310014, China; 2. Dep. of Computer Sci. , Hangzhou Univ. of Commerce, Hangzhou 310032, China)

A bstract:The standard Genetic Algorithm has been applied into Vehicle Routing Problem, and it has the common defects of early convergence and easily falling into local minimization. Acc ording to it, the double populations genetic algorithm is applied into Vehicle Routing Problems. During the course of optimization, two populations is initialization, each has its pr obability of crossover and mutation. After ever y iteration, the two populations exchange the better chromosome. It can br eak the balanc e of inter -population in the local minimization and escape the local minimization. According to compu-tational experiment result, the double populations algorithm find the optimal or nearly optimal solution effectively in com-parison with other meta -heuristic algorithms. So, it is an efficient method for Vehicle Routing Problem. Key words:vehicle routing problem; genetic algorithm; computation intelligence; logistics

R eceived 21Apr. 2003; accep ted 06Aug. 2003.

Fou ndati on item:Proj ect sup ported b y the Nation al High -Tech. R &DProgra m, Ch ina (GrantNo. 2002A A412610) ; p roject s upp orted by t he Key S &TTacklin g