遗传算法求解VRP的种群初始化改进

Vol . 9No . 3第9卷第3期南京师范大学学报(工程技术版)

　　JOURNAL OF NANJ I N G NORMAL UN I V ERSI TY (ENGI N EER I N G AND TECHNOLOGY E D I TI O N ) 2009年9月Sep, 2009

遗传算法求解VRP 的种群初始化改进

徐　鹏

1, 2

, 王　雷, 张文义

11

(1. 河海大学交通学院, 江苏南京210098;

2. 河海大学海岸灾害及防护教育部重点实验室, 江苏南京210098)

[摘要]　传统的遗传算法求解VRP 时, 初始种群多半采取随机生成法形成染色体方案, 以致于迭代开始就可能形成许多不可行的方案, 要进行大量的计算后才能得到优化的方案, 这在很大程度上降低了算法的运算效率. 论文提出的遗传编码策略, 对初始种群给予基于知识型启发策略, 使得初始种群一开始就表现为一种较优的状态.

[关键词]　VRP, 初始种群, 遗传编码, 遗传算法, 改进遗传算法

[中图分类号]U 491. 2　[文献标识码]A 　[文章编号]167221292() 032Im prove m en t on I Geneti c

ith VRP

1, 2

Le i , Zhang W e nyi

11

1. of Traffic, Hohai University, Nanjing 210098, China;

Key of Coastal D isaster and Defence, Hohai University, Nanjing 210098, China )

Abstract:W traditi onal Genetic A lgorith m s (G A ) was app lied in VRP, most of the initial populati on generate the chr omos ome p r ogram by taking a random method, which leads t o a l ot of infeasible sche mes in the beginning, and a great deal of calculati ons before obtaining an op ti m ize one . This reduced the calculating efficiency of the algorith m t o the great extent . The genetic coding strategy, p r oposed by the paper, gives initial populati on a knowledge 2based heuristic strategy, which makes initial populati on a better perf or mance at the very start .

Key words:VRP, initial populati on, genetic coding, genetic algorith m, i m p r oved genetic algorith m

　　运输车辆的优化调度问题在国外被归结为车辆线路安排问题(Vehicle Routing Pr oble m , VRP ) , 由Da 2

[1]

ntzig 和Ram ser 于1959年首次提出. 由于该问题在交通运输、工业生产管理等领域具有广泛而重要的应用, 因此40多年来其研究得到很大重视. VRP 是一个典型的NP (非确定多项式) 难题, 其定义为:对一系列的装货点和(或) 卸货点, 组织合理的行车线路, 使车有序地通过, 在满足一定的约束条件(货物的需求量、车辆的容量限制、货物的送达时间、车辆的行驶时间等) 下, 达到一定的目标, 如里程最短、费用最少、使用车辆尽量少等.

遗传算法(Genetic A lgorith m s, G A s ) 是基于自然选择和自然遗传机制的搜索算法, 它是一种有效的解

[2]

决最优化问题的方法. 最早由美国M ichigan 大学的John Holland 等提出. 在John Holland 等人工作的基

[3]

础上, Goldberg 总结了统一的基本遗传算法. 基本遗传算法只使用选择、交叉、变异这3种基本遗传算子构成完备的算子集合, 其遗传进化操作过程简单、容易理解, 是其它遗传算法的基础, 它给各种遗传算法提供了一个基本框架. 与传统的优化算法往往直接对决策变量的实际值本身进行优化不同, 遗传算法以决策变量的某种形式的编码为运算对象, 这有利于在优化计算过程中借鉴生物学的染色体和基因的概念. 特别是对于无数值概念或很难有数值概念而只有代码概念的优化问题, 编码处理更显示了其独特的优越性.

[4]

La wrence J 最先将该方法用于VRP 问题的研究, 从此针对VRP 的遗传算法研究成为一个热点.

1　遗传编码

111　遗传编码

　　在遗传算法中, 编码是设计算法时的一个关键步骤. 所谓编码, 就是在遗传算法中如何描述问题的可

　收稿日期:2008204208.

基金项目:河海大学自然科学基金(2008429911) 资助项目. 通讯联系人:徐　鹏, 博士研究生, 讲师, 研究方向:智能交通系统、物流系统优化. E 2mail:r obinxp@sina . com

—70—

徐　鹏, 等:遗传算法求解VRP 的种群初始化改进

行解, 即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法. 编码方法很大

程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率. 一个好的编码方法, 可以使遗传运算简单地实现和执行. 而差的编码方法, 却可能使得遗传运算难以实现, 也可能会产生许多在可行解集合内无对应可行解的个体, 即无效解. 尽管有时产生无效解并非有害, 但会影响运行效率.

对于具体应用问题设计合理的编码方案, 是遗传算法的应用难点之一, 目前还没有一套既严密又完整

[5]

的指导理论及评价理论准则. 目前有许多种不同的编码方法, 大致可以分为三大类:

第一类:二进制编码方法. 二进制编码方法是遗传算法中最常见的一种编码方法, 它使用的编码集是二进制符号0和1所组成的二值符号集{0,1}, 它所构成的个体基因型是一个二进制编码符号串, 其长度与所解问题要求的精度有关. 二进制编码具有编码、解码操作简单易行, 交叉、变异遗传操作便于实现的优点, 有利于应用模式定理对算法进行分析.

第二类:浮点数编码方法. 对于一些多维、, 体, 存在着连续函数离散化时的映射误差, . 这些缺点, 浮点数编码应运而生. 所谓浮点数编码, 表示, 个体的编码长度等于其决策变量的个数.

第三类:符号编码方法. 、只有代码含义的符号集. , 如{a, b, c, …}; 也可以是一个数字符号表, 如自然数{1,2, 3, …}等. , 而且便于遗传算法与相关近似算法之间的混合使用.

112　VRP 李军等在前人应用遗传算法解决旅行商问题的基础上进行研究, 设计了求解车辆优化调度问题的基于自然数编码的遗传算法.

根据VRP 的具体特点, 采用自然数编码, 即符号编码. 物流中心用0表示, 用序数1到L 表示有货运要求的L 个货运节点, 完成这些货运任务需要的车辆数目为m , 用序号1到m 表示. VRP 的一条可行的线路编成长度为L +m+1的一个染色体:(0, i 11, i 12, …i 1x , 0, i 21, i 22, …, i 2y , 0, …, 0, i m 1, i m 2, …, i m z , 0) . 其中, i k j 表示第i k j 项任务, k 表示编号为k 的车, j 表示第k 辆车承担的第j 项货运任务. 通俗的解释染色体的结构就是:编号为1的车装货后从物流中心出发, 完成i 11, i 12, …, i 1x 后, 回到物流中心, 形成子路径1; 与此同时, 编号为2的车装货后从物流中心出发, 完成i 21, i 22, …, i 2y 后, 回到物流中心, 形成子路径2; 如此, 共有m 辆车, 一共完成L 项货运任务.

如染色体(0, 4, 5, 3, 0, 2, 8, 6, 0, 7, 1, 9, 0) 表示由3辆车完成9项货运任务, 其各行车线路如图1所示, 分别表示为:

子路径1:物流中心0→货运任务4→货运任务5→货运任务3→物流中心0; 子路径2:物流中心0→货运任务2→货运任务8→货运任务6→物流中心0; 子路径3:物流中心0→货运任务7→货运任务1→货运任务9→物流中心0

.

[6]

图1中染色体结构子路径内部是有序的, 若子路径1中的4、5货运任务互相交换位置, 会使目标函数改变数值; 但其子路径之间是无序的, 若子路径1和子路径2互换位置, 目标函数的数值不会发生改变. 因此, 在遗传迭代时, 要求重新整理子路径顺序, 而子路径间的顺序则不需要考虑.

2　基于启发策略的种群初始化

211　编码改进策略

　　在基本遗传算法中, 采用上节编码方式进行染色体随机交叉时, 会使许多相距较远的路径之间产生交叉, 从而得到大量的不可行解, 难以保证双亲的优良特性, 同时算法收敛性能大为降低. 因此, 有必要对算

—71—

南京师范大学学报(工程技术版) 　　　　　　　　　　　　　　　　　　　　　　　　　　　第9卷第3期(2009年)

法进行改进, 以适应大规模运算需要.

对于受自然的运行规律或者面向具体问题的经验、规则启发出来的方法, 人们常常称之为启发策略(Heuristic policy ) . 启发策略强调的是对解空间的最有希望的区域进行探测, 比如限定搜索邻域等. 由经验可知, 相距较近路径间产生交叉能得到比较优的解. 为适应交叉运算中邻近子路径间进行基因交叉, 本文对遗传编码结构提出改进策略, 首先计算出每条染色体中各子路径凸包质心, 然后按几何邻近排列一个子路径间的顺序, 即子路径内部有序, 子路径之间亦要求有序. 这种编码形式直接表现于遗传种群的初始化过程中

.

212　. 传统的遗传算法求解VRP 问题时, 初始种群多半采取随机生成法, 即从所有的配送点中随机选取点直到满足一定的条件或接近满足一定条件后停止, 形成一条子路径, 乃至形成一条染色体(一套配送方案) . 但这种方式使初始种群的形成过于随意, 以致于一开始就可能形成许多不可行的方案, 之后要进行大量的计算后才能得到优化的方案, 这样很大程度上降低了算法的运算效率. 本文以扫描法作为一种启发式策略对染色体种群进行初始化, 使得初始种群一开始就表现为一种较优状态.

扫描法求解VRP 初始种群的思路是:通过扫描法形成一套路径配送的完整方案, 将其作为遗传操作中的一条染色体; 重复这个过程, 得到种群数量为N 的染色体.

具体流程如下:

(1) 过配送中心与某配送点生成射线顺时针转动.

(2) 累计扇面覆盖的配送点需求量之和, 直至满足运量约束停止构成一个客户分群. (3) 采用节约插入算法将该客户群形成优化为一条有序的子路径

.

—72—

徐　鹏, 等:遗传算法求解VRP 的种群初始化改进

(4) 以原射线末位置为新射线的初始位重复上述过程. 直至形成一条包含所有子路径的染色体序列. (5) 将射线顺位偏移某一角度, 同样按以上方法产生第二染色体. 最终形成N /2条染色体的种群.

(6) 为保证种群多样性, 上述方法逆时针做同样操作, 再形成N /2条染色体.

以图1中基于自然数编码的一条染色体为例, 其子路径内部是一个路径优化的序列组合, 子路径之间同样按序列编号排列, 算法流程如图4所示.

3　算例分析

某物流中心0, 现有8项货物运输任务, 以1～8编号, 各货运节点的货物需求量g i (单位:条) , 各货运节点的卸货时间T i (单位:m in ) . 物流中心0的货运车辆的容量q 为2000条, 额定工作时间为7h, 货运车辆的平均行驶速度为50k m /h . 物流中心及各个货运节点间的最短距离(单位:k m ) 1, 节点需求及卸货时间见表2, 尝试安排车辆行驶线路, 使总费用最少.

表1　xy (i , j )

Table 1　The shortest pa of d ij

[**************]80

[**************]0

[***********]

[**************]50

[***********]00

[***********]075

[***********]00

[***********]100

[***********]01000

01678

表2　货运节点需求表

Table 2　The de mand of the fre i ght nods

货运节点i

G i /条T i /min

11003

21203

34504

43005

53503

65006

[5]

75005

8300515

　　本文选择启发式种群初始化策略的改进遗传算法与基本遗传算法果, 两种算法其他参数相同.

进行测试比对. 为保证比对效

xy (ij )

在算例中, 假设车辆的行驶时间和距离成正比, 则由i →j 的行驶时间t ij =

50

. 同时, 车辆的行驶费

用与距离成正比, 即c ij =c c 3xy (ij ) , c 1为行驶单位距离的费用. 群体规模取n =30, 交叉率pc =0195, 变异率p m =011.

λ、由于遗传算法搜索路径具有较大的随机性, 根据启发式算法的终止条件, 本文给定适当的参数ε、

Y, 只要算法满足下列条件之一, 就认为算法收敛:

(1) 计算每代群体中染色体适应度的方差, 当方差小于ε时, 认为算法收敛;

(2) 计算每代群体适应度的均值, 当均值与最佳染色体适应度的比值大于λ时, 认为算法收敛; (3) 由于计算时间和机器容量都是有限的, 代数不能无限长, 故迭代次数达到规定的Y 时, 停止计算.

通过扫描分群、子路径内和子路径间进行排序, 虽然初始时间增加了, 但迭代收敛时间明显减少, 表3列出了改进遗传算法和基本遗传算法之间性能比较. 另外, 本文还增加了节约插入算法、蚁群算法、爬山算

法与改进遗传算法进行比较参照, 其结果如表3所示.

通过表3的性能比较看出, 改进编码与初始化策略的算法平均时间较基本遗传算法有所减少. 这是由于前者迭代次数更少, 随着节点数量的增多, 在迭代上的时间开销将会更多, 则改进算法与基本遗传算法的时间差别将会更大. 最佳线路成本通过多步迭代, 两种算法基本相当, 但满意解率则改进遗传算法更加有效, 即在有限时间内改进遗传算法能更迅速地收敛到一个合理的目标. 与其他优化算法的比较方面, 节约插入算法收敛速度较快, 但容易陷入局部最优, 满意解率效低; 蚁群算法收敛速度慢, 易陷入局部最小

—73—

南京师范大学学报(工程技术版) 　　　　　　　　　　　　　　　　　　　　　　　　　　　第9卷第3期(2009年)

值; 爬山法虽然快速, 但容易导致无解, 其满意解率下降. 由此可见, 采用了基于启发策略的种群初始化操作有利于提供运算效率并获得满意解.

表3　算法性能比较

Table 3　The com par ison of the two a lgor ith m s

改进遗传算法基本遗传算法节约插入算法

平均运行时间/s

最佳线路成本/km

满意解率

3073095%

5074350%

3582045%

蚁群算法

5379055%

爬山算法

4084050%

　　本文成果已用于某县级市烟草配送, 该地目前共有烟草零售点2668个, 散布在全县各地. 因为需求分布的不均衡, 给日常配送线路的选择带来诸多问题. 此前的管理方法是:条固定线路, 不管该线路要货需求的多少, 每天都固定车辆来保障工作的完成. :根据每天不同的要货需求, 配送车辆尽量装满配送卷烟, ; , 给出车辆行驶的最优路径, , 最少. 采用改进型遗传算法解决此问题, , 运营成本降低, 烟草配送方案令人满意.

4par ison of tobacco send 2off and opti m i ze project

优化方案节省

15105

总里程/km

880777103

线路固定费用/元

[1**********]0

线路油耗总费用/元

[1**********]8

配送线路总耗时/h

[1**********]52

车辆平均利用率

65182%93172%

提高3219%

4　结论

(1) 在种群初始化过程中, 采用自然数编码方式, 通过顺向与逆向扫描法确定顾客分区, 保证了群体

的多样性, 有效控制遗传算法的早熟现象, 通过优化算法确定子路径内部和子路径之间的序列化, 从几何角度满足了各条子路径中任务节点的大致聚集, 从而使得种群表现为一种较优状态, 便于后续遗传运算的有效收敛, 体现为获得满意解的比例较随机生成初始群体有显著提高.

(2) 扇区扫描法适合传统的VRP 花瓣式路径形态, 即分配方案除了保证总费用最小外, 还大致保证各条路径费用差别不大, 体现效率优先、兼顾公平的思想. 但如果VRP 模型的目标函数只追求总路径费用的极小化, 则花瓣式形态并不一定是合理的选择, 则扇区扫描法就不能充分解决此类问题, 可以考虑人工干预的分区扫描方式替代.

[参考文献](References )

[1]Holland J H. Adap tati on in Nature and A rtificial Syste m s[M].Ca mbridge:M I T Press, 1992.

[2]Goldberg D E . Genetic A lgorith m s in Search[C ]//Op ti m izati on and M achine Learning . Addis on 2W esley, 1989:37240. [3]La wrence S, Mohammad A. Para metric experi m entati on with a genetic algorith m ic configurati on f or s olving the vehicle r outing p r oble m [C ]//Pr oceedings 2AnnualMeeting of the Decisi on Sciences I nstitute . Decis Sci I nst, 1996:4882490. [4]张玉俐, 樊建华, 徐建刚, 等. 车辆路径问题的改进遗传算法研究[J ].天津理工大学学报, 2006, 22(5) :79282.

Zhang Yuli, Fan J ianhua, Xu J iangang, et al . I m p r oved genetic algorith m research for vehicle r outing p r oble m [J ].Journal of

Tianjin University of Technol ogy, 2006, 22(5) :79282. (in Chinese )

[5]李军, 谢秉磊, 郭耀煌. 非满载车辆调度问题的遗传算法[J ].系统工程理论方法应用, 2000, 9(3) :2352239.

L i Jun, Xie B inglei, Guo Yaohuang . Genetic algorith m for vehicle scheduling p r oble m with non 2ful l oad [J ].System s Engi 2neering 2TheoryM ethodol ogy App licati ons, 2000, 9(3) :2352239. (in Chinese )

[6]汪祖柱, 程家兴, 方宏兵, 等. 车辆路径问题的混合优化算法[J ].运筹与管理, 2004, 13(6) :48252.

W ang Zuzhu, Cheng J iaxing, Fang Hongbing, et al . An hybrid op ti m izati on algorith m s olving vehicle r outing p r oblem s[J ].

Operati ons Research and M anage ment Science, 2004, 13(6) :48252. (in Chinese )

[责任编辑:严海琳]

—74—