车辆路径问题的遗传算法研究_姜大立
- 格式：pdf
- 大小：175.61 KB
- 文档页数：6
1999年6月系统工程理论与实践第6期 车辆路径问题的遗传算法研究⒇姜大立1 杨西龙1 杜 文2 周贤伟2(1.后勤工程学院自动化系,重庆400041)(2.西南交通大学运输系,四川成都610031)
摘要 在分析车辆路径问题的现有启发式算法的基础上,本文构造了车辆路径问题的染色体表达,并
对染色体进了可行化影射,建立了此问题的遗传算法.实验结果表明,此算法可以有效求得车辆路径问题的优化解或近似优化解,是求解车辆路径问题的一个较好的方案.关键词 车辆路径问题 遗传算法 启发式算法 优化
AStudyontheGeneticAlgorithmforVehicleRoutingProblem
JIANGDali1 YANGXilong1 DUWen2 ZHOUXianwei2(1.LogisticEngineeringUniversity,Chongqing400041)(2.SouthwestJiaotongUniversity,Chengdu610031)
Abstract Ontheanalysisoftheexistingheuristicmethodsofthevehicleroutingprob-lem,thispaperproposesageneticalgorithmforthevehicleroutingprobem.Withthenovelchromosomepresentationforthevehicleroutingproblem,thecorrespondingfeasi-bilityprocessandotherimprovedGAoperators,thisalgorithmcanfindtheoptimalornearlyoptimalsolutiontothevehicleroutingproblemeffectively,whichisprovedbythenumberexperimentprovidedbythispaper.Keywords vehicleroutingproblem;geneticalgorithm;heuristicalgorithm;optimiza-tion
1 引言在许多配送系统中,管理者们需要采取有效的配送策略以提高服务水平、降低货运费用.其中车辆路线安排问题(车辆路径问题vehicleroutingproblem)是亟待解决的一个重要问题,此问题可描述如下:有1个货物需求点(或称顾客),已知每个需求点的需量及位置,至多用K辆汽车从中心仓库(或配送中心)到达这批需求点,每辆汽车载重量一定,安排汽车路线使运距最短且满足每条路线不超过汽车载重量和每个需点的需求必须且只能由一辆汽车来满足的约束条件.车辆路线安排问题是一个NP完全问题,只有在需点数和路段数较少时才有可能寻求其精确解.因此,车辆路径的启发式算法成为人们研究的一个重要方向,先后涌现出一大批启发式算法,如最早由Clarke和Wright提出的节约法[1],Gillett和Miller提出的扫描法[2],Bramel和Simchi-Levi的提出的基于选址问题转化的LBH法[3],Fisher和Jaikumar建立的一般分配算法[4],Christofides和Minggozzi等建立的不完全树搜索算法[5],Pureza和Franca研究的Tabu搜索算法[6]等等.这些算法为求解车辆路径问题提供了有效的方法,但也存在一系列问题,如节约法虽然通过列出各点对间的节约量,按节约量从大到小构造路径,具有运算速度快的优点,但存在未组合点零乱、边缘点
⒇收稿日期:1997-11-03难于组合的问题;扫描法为非渐进优化[7];LBH法则存在问题转化麻烦且选址问题本身难解等等.如何针对车辆路径问题的特点,构造运算简单、寻优性能优异的启发式算法,这不仅对于配送系统而且对于许多可转化为车辆路径问题求解的优化组合问题具有十分重要的意义.遗传算法(GeneticAlgorithm,GA)是由J.H.Holland等于70年代发展起来的[8].它是一种以自然选择和遗传理论为基础,将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法.其通过给解向量编码、形成初始种群,然后用变异、交叉重组、自然选择等算子,进行并行迭代,求得优化解.由于它采用随机运算,对搜索空间无特殊要求,无需求导,具有运算简单、收敛速度快等优点,因此近年来有很快的发展,并在组合优化、自适应控制、机器学习等许多领域获得应用[9,10],有着广泛的应用前景.为此,本文研究运用GA编码构造求解车辆路径问题的算法,并对其运算过程和结果进行分析.实验数据表明本算法行之有效,不失为一种求解车辆路径问题的性能优越的启发式算法.
1 车辆路径问题的数学模型假定中心仓库最多可用K辆车对1个分仓库进行运输配送,每个车辆载重为bk(k=1,2,…,K),每个分仓库的需求为di(i=1,2,…l),分仓库i到分仓库j的运距为cij.设nk为第k辆车所包含的分仓库数(若nk=0表示未启用第k辆车),用集合Rk表示第k条路径,其中的元素rki表示分仓库rki在路径k中的顺序为i(不包含中心仓库).令rk0=rk(nk+1)=0表示中心仓库,则有如下表示的车辆路径问题的数学模型:
minimize∑Kk=1(∑nki=1crk(i-1)rki+crknkrk(nk+1) sign(nk-1))
s.t.∑nki=1drki≤bkk=1,2,…,K(1)0≤nk≤l, k=1,2,…,K(2)
∑K
k=1nk=l(3)
Rk={rki|rki∈{1,2,…,l},i=1,2,…,nk}(4)Rk1∩Rk2= k1≠k2(5)
其中, sign(nk-1)=1 nk≥1
0 其他
上式中不等式(1)保证每条路径上的各分仓库的总需求量不超过此条路径的配送车容量,不等式(2)表明每条路径服务的分仓库数不超过总分仓库数,等式(3)要求每个分仓库都得到车辆的配送服务,等式(4)表示每条路径的分仓库组成,等式(5)则限制每个分仓库的需求仅能由一个车辆来完成.
2 车辆路径问题的遗传算法从上述模型可知,求解车辆路径问题的关键是合理确定车辆与各分仓库的关系,在满足车辆载重量和分仓库需求约束条件的情况下使得总费用最小,因此可以构造遗传算法如下:2.1 构造染色体,产生初始种群用矢量(s1,s2,…,sl)表示染色体G,其中元素(基因)sj为[1,k×l]之间的一个互不重复的自然数,它表
示了第j个确定第m=(sj-sj-ll l)个分库与路径k=(sj-sj-ll+1的关系([]表示取整数,下同.),即确定分库m是否由车辆k配送及确定分库m在路径k中的顺序的次序为j.随机产生一组染色体Gh(h=1,2,…,n)(其中n为一代种群中的个体数),Gh各不相同,此为第一代种群.2.2 可行化过程将染色体的编码向量映射为满足全部约束条件的可行解称为可行化,其过程如下:
41第6期车辆路径问题的遗传算法研究1)令分库需求条件满足的标志变量dzm=0(m=1,2,…,l).2)令路径k中的分库数目nk=0(k=1,2,….K),令b′k=bk,Rk= (k=1,2,…,K),路径k中除去中心仓库后第i个位置的分库号为rki=0(i=1,2,…,l),即此时所有路径皆未形成.3)j=1.
4)第j次确定分库m与路径k间的关系,其中,m=(sj-sj-ll×l),k=(sj-sj-ll+1.5)判断dzm是否等于0,若等于0,表明分库m的需求尚未满足,转5)继续判断路径m的情况;否则转7).6)判断dzm是否为0?①若为0:判断dm≤b′k成立否?若成立,令dzm=1,b′k=b′k-dm,nk=nk+1,rknk=m,Rk=Rk∪{m};若不成立,转7).②若不为0:转7).7)j=j+1,转4)重复上述过程,直到j=K×l+1.此时检查是否所有dzm=1,(m=1,2,…,l)成立,若成立,说明在满足各约束条件的情况下,所有的分库均分配了一个路径,构成路径集合RT={R1,R2,,…Rk
},即为染色体所对应的原车辆路径问题的一个可行解;若不成立,说明此染色体表示的路径分配方案不
满足约束,为原VRP问题的一个不可行解.以第三章中的数据为例说明上述过程,假设一染色体编码为:1 2 4 7 8 16 15 9 10 13 12 5 6 14 3 11
s1=1,首先确定路径k=s1-ll+1=1-18+1=1与分库m=s1-s1-1l×l=1-0=1关系,此
时dz1=0,d1=1确定路径k=s2-ll+1=1与分库m=s2-s2-1l×l=2的关系,此时dz2=0,d2=1库2加入到路径1中,将b′1变为b′1=7-1=6,dz2变为dz2=1,如此第i次根据基因si的值确定某一分库与路径的关系,最后即第16次确定路径k=11-18+1=2与分库m=11-11-18×8=3的关系,此时由于
dz3
=1说明分库3已安排至其他路径,无须再安排至路径2.其可行化过程可表示为表1:
表1 可行化表分库12345678路径
1r11r12r15r13××r14×
2××××r22r23×r21
需求量12121422
表中×格表示对应的路径无需安排分库,染色体所代表的路径安排为:0→1→2→4→7→3→0与0→8→5→6→02.3 性能估计对一代种群中的每一个染色体Gh(h=1,2,…,l)应用2.2,求得对应可行解RTh(h=1,2,…,n),代入
目标函数Zh=∑Kk=1∑nki=1(crk(i-1)rki+crknkrk(nk+1) sign(nk-1);若染色体对应的为非可行解,则赋予其目标函数一个很大的整数zh=M.令Gh的适应性函数fh=1/zh,fh是个体Gh在生存竞争中生存能力的表现,越大表明其性能越好,即其对应的解越接近最优解.2.4 判断停止进化条件判断迭代的代数是否为要求代数N,若是,停止进化,选性能最好的染色体G*h所对应的路径集合RT*h作为原VRP问题的优化解输出.反之,继续执行2.5.
42系统工程理论与实践1999年6月
