当前位置:文档之家 > 求解车辆路径问题的混合遗传算法

求解车辆路径问题的混合遗传算法

第13卷第10期计算机集成制造系统v01.13No.102007年10月computerIntegratedManufacturi“gSystemsOct.2O07

文章编号:1006—5911(2007)10一2047一06

求解车辆路径问题的混合遗传算法

姜昌华1,戴树贵“2,胡幼华1

【1.华东师范大学信息科学技术学院.上海200062;2.滁州学院数学系,安徽滁州239000)

摘要:针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2一OPT子路径优化的混合造传算法。在该算法中,提出了一种新的双层染色体编码方案。该染色体编码方案能确保子路径为满足车辆容量约束的可行路径,并且该编码方案只需根据客户编号生成染色体.无需预先知道有容量限制的车辆路径问题所需的最小车辆数,更适于求解实际中的车辆路径优化问题。采用2一oPT算法作为遗传算法的变异算子以优化子路径,从而提高算法的收敛速度。基于典型基准测试实例的计算结果表明,该算i击是求解有容量限制的车辆路径问题的有效方法。

关键词:物流配进}车辆路径问题f混合遗传算法,双层染色体,2一OPT子路径优化

中图分类号:TP391文献标识码:A

Hybr树霉姐eHcalgnrithmfor曲p越itatedvehiclemutingpmblem

,mⅣGC^口n一埘1,DAf鼬俨g“1”.HU‰卉啪3

(1.schoolofInfornmtion

Science&khnoIogy?EastC11i眦No咖丑lUni卵硌ity'Shllghai200062?Chi眦}

2.Deparnnentof

Mathematlcs,Ch眦houUIIiver甜ty.Ch皿hou239000,C11i眦)A崦tract:Ahybridgeneticalgorithmwith2一oPTsub-rout幅optimi豫tionwaspresentedforCapacitatedVehicleRDu石ngProblem(CVRP).mthelogisncsdistributionoptim妇tionar髓.Inthismethod,aDoubleLa”rsChrorno—som£(DLC)codlngscheme宵a8pr。posedwhichcouldassure吼ch5ub-rou健wa5feasIbleandgenerate

ch咖osomeaccordingtocustome如numbefinDLCwitllouthlowingtheoptiT舶lvehiclenumberoftheCVRPinadvallce.Profitfromabove-metltionedfeatu仲s,thehybridgeneticalgodthmwasmoresuitableto∞lvethepracticalVI廿’whoseminimalvehicle岫ber宵asunknowninadvance.2—0PTaIgorithmwasusedtoopdmi钟s出route8to8ccelefateconve。gencesp牲d.Simulations

hsedontypicalbenchmBrkproble士nssIlowedthatthealgorithm啪sfeasibleandef-fectiv屯

Kqwofdsl109i3ti娼di3tTibu曲舢v≤陆ckroutmgpfoblcm}h如r讯genebc“g。Tithm;doublelaye玛chr。mosorne}2一OPT5ub_route5o口timigation

O引言

物流被称为企业的“第三利润源泉”,而物流配送是物流活动中的重要环节。因此,在进行物流配送时优化车辆调度能有效降低物流成本,提高企业的经济效益。在此领域最有名的优化问题为车辆路径问题(VehicleRoutingProblem,VRP)。VRP最早由Dantzig和Ramser于1959提出[”。VRP有多种形式,如具有容量限制的车辆路径问题(capac_itatedvehicleRoutingProblem,cVRP)、带有时同窗的车辆路径问题(vehicleRoutingProblemwithTimewindow,VRPTw)等。该类问题已被证明

收藕日期:2006-09_18,謦订日期:2007。04。12?Re亡eiVedl8Scp.z006}aco印tedl2Apr.2007.

基叠项目:安徽高校自然科学研究基金资助项目(2006KJ253B).h仰d_“岫l‘哪tProje吐5uPponedhytheAnh山collegesanduniv材5iti髓N8turalSc岫ceF。undBd呻,Chim(N“2006脚253B).

作者简介:萤昌华(1973一),男.江西南昌人,华东师范大学信息科学技术学院助理研究员t博士研究生,主要从事智能优化算法’暂漉仿真优化等的研究。E_miIlcMiang@cc.神n也ed虬曲.

计算机集成翩造系统第13卷

是一个NP—Hard问题,只有当问题规模较小时,才

能求其精确解。因此,应用智能算法求解vRP成

为人们研究的一个重要方向,如遗传算法[“]、微粒

群算法[“等。本文设计了一种结合2一OPT子路径

优化的混合遗传算法,在该算法中提出了一种新的

双层染色体编码方案,仿真计算表明,本文算法能有

效地求解CVRP。

l有容量限制的车辆路径问题的数学模型

CVRP可描述如下:配送中心有m辆货车,每

辆车的容量为g;配送中心需为n个客户提供货物

配送任务,每个客户的需求量为毋({一1,2,…,n),

&<q,每个客户由一辆车服务;目标是优化车辆调

度,使得在满足货运要求的前提下。最小化车辆的使

用及车辆行驶路径,从而节约运输成本。

将车辆路径问题抽象成图的最短路问题。令配

送中心的编号为。号节点,各客户节点的编号为£(f

一1,2,…,n),配送中心车辆的编号为t(^=1,2,

…。m);夸G表示各节点之间的距离,并定义如下

变量:

fl车辆々经客户i驶向客户J

”‘

1o否则’

f1客户l的需求由车辆^满足

10否则。

则车辆路径问题的数学模型如下“];

minz=∑∑∑qz¨。(1)

{一O’一O^一1

∑g;y*≤q,^一1,2,…,m}耋y*一∽三。...。;

∑z#一,p}

∑蛳=y^;

zil一0或1,

蛳=o或1;(2)(3)(4)(5)

(6)(7)

J一1-2,…,n;女=l?2,…'m。

上述数学模型中,式(2)表示每条配送路线上的总客户需求量不大于车辆的容量;式(3)表示配进任务由m辆车完成,并且每个客户的配送任务仅由一辆车完成;式(4)和式(5)则确保到达客户的车必须离开该客户;式(6)和式(7)表示变量的取值满足定义要求。

2混合遗传算法

应用遗传算法的一般步骤‘7],①针对待优化问题设计染色体编码方案;②根据染色体编码方案生成初始群体,并在一定条件下(如在规定的进化代数之内)用遗传算子对群体进行进化操作。遗传算子主要包括选择(select)、交叉(crossover)、变异(mu—tation)三种。其中,选择算子的主要作用是根据个体的适应度选择种群中的优良个体进入下一代种群,交叉算子的主要作用是产生比双亲更好的个体,而变异算子的主要作用是防止遗传算法过早收敛于局部优化解。

2.1有容量限制的车辆路径问题的求解思路实际上,在vRP中包含两个著名的组合优化问题”],即装箱问题(BinPackingProblem,BPP)和旅行商问题(TravellingsalesmanProblem,TsP)。将客户分配到不同的子路径相当于BPP,子路径的最优化则相当于TSP。不论TSP还是BPP,本身就是NP_Hard问题,在求解CVRP时还必须考虑车辆的容量约束,因此求解cVRP非常困难。本文的求解思路是用遗传算法来解决BPP,用2一oPT算法来优化TsP。虽然2一oPT算法不是求解TsP最有效的方法,但是2一oPT算法简单、计算复杂度低而且易于实现,是求解小规模TsP的有效方法。由于在很多实际的物流配送系统中,每条子路径上的客户数不会很多,因此2~oPT算法能满足很多物流配送优化问题的实际需要。

2.2双层染色体编码方案

在现有遗传算法中,个体的染色体编码需要用到最优车辆数。例如,在文献[2]和文献[3]中,将染色体编码成m×n维的向量;虽然文献[4]和文献[5]采用的是微粒群算法,但是粒子也是由染色体构成的,它们将染色体编码成m+n一1维的向量(上述m代表最优解所需车辆数)。这两种编码方案有三个缺点:①由于染色体维数变长,使组合空间变大,降低了搜索到最优解的几率;②由染色体解码后获得的子路径有可能不满足车辆的容量约束;③需要预先知道最优解所需车辆数。为了避免上述缺点,本文提出一种新的双层染色体编码方案:第一层是n维向量L1,代表n个客户的一种排列;第二层是一个维数可变的向量L2,在L2中存放的元素代表每辆车所服务的第一个客户在L1中的顺序号,

第10期姜昌华等:求解车辆路径问题的混合遗传算法

需根据车辆的容量限制计算得出。以下文的仿真实验1为例,用自然数1~8代表八个客户,其需求量分别为(1,2,1,2,1,4,2,2),车辆的容量约束为八个单位。假定某个体的第一层染色体为Ll(4,l,3,7,2,6,5,8),第二层染色体的计算过程如下:

(1)第一辆车编为o,其第一个客户为客户4,在L1中的顺序号为o,因此第二层染色体暂时为L2(o)。编号顺序都从O开始,便于编程实现,因为在很多编程语言中,都将数组的起始编号设为O。

(2)继续让O号车服务后面的客户,直到超出车辆的容量约束。在本例中,o号车可以服务前五个客户,到第六个客户,由于违反车辆的容量约束,需派出1号车(第二辆车)。1号车所服务的第一个客户为客户6,其在L1中的顺序号为5,将其加入L2,第二层染色体变成L2(o,5)。

(3)继续应用步骤(2),直到所有的客户都得到服务为止。在本倒中,1号车可以为剩下的三个客户服务。为以后计算方便,将客户数添加到Lz的最后,最终第二层染色体变为L2(O,5,8)。

根据上述编码方案,可以方便地计算出所需车辆数t及每辆车所服务的客户。所需车辆数一L2的维数一l,上例中,所需车辆数=3—1,即需要两辆车,^号车所服务的客户为L1中从编号L2[^]开始的连续(L2卟+1]一L2n])个客户,上例中,o号车所服务的客户为L1中从编号。开始的连续五个客户,即(4,1,3,7,2)。每辆车所服务的客户与配送中心一起构成一条闭合子路径。

值得指出的是:对于最优车辆数已知的VRP基准测试实例,应用上述编码方案后,可能使一些个体的所需车辆数超过已知的最小车辆数。但是,车辆数多即代表子路径数多,而一般来说,子路径数的增加将使目标函数的值增加,从而导致这些个体的适应度降低,在选择算子中易被淘汰。另外,本文在计算第二层染色体时,实际上运用了贪心算法来尽量减少所需车辆数。贪心算法及选择算子的联合使最优个体的所需车辆数接近,甚至等于已知的最小车辆数。在本文的几个仿真实例中,所求最优解的所需车辆数均等于已知的最小车辆数。

上述编码方案与以上所述参考文献的编码方案相比,具有如下优点:①染色体的维数最低,能有效地缩小问题的搜索空问,从而提高搜索效率}②能保证所生成的子路径都满足车辆的容量约束,无需象参考文献一样用罚函数处理容量约束,从而降低计算量;③仅根据客户的信息进行编码,无需预先知道最优解所需车辆数,这更适合物流配送优化问题中所需车辆数未知这一实际情况。由于车辆数不固定,在编程实现时可以采用动态数组或链表等动态数据结构来存储L2。

在文献[9]中,也介绍了一种双层染色体编码方案。与本文不同的是,该编码方案的第二层染色体直接对应子路径,其中存储的是子路径中客户的编号。2.3选择算子

以个体所对应的行驶距离的倒数作为个体的适应度,个体对应的行使距离越长,其适应度越低。选择算子采用最优选择算子,即按一定的比例选择适应度高的个体进入下一代种群。相对于文献[8]中介绍的选择算子,本文的选择算子计算简单,易于实现。2.4交叉算子

交叉算子采用顺序交叉(Ordercorssover,Ox)算子。下面以九个顶点的TsP为例说明Ox交叉算子的原理。对如下两个父个体随机选择两个交叉点“l”。

声1;(1234567I89),p2:(452187693)。

子个体cl按以下方式确定:取户1中两个交叉点之间的点放在Hamilton回路的开始处,其状态暂时为c1(4567xxxxx),对未确定的点z,从户2第二个交叉点开始依次向后进行如下判断:如果该点还没有出现在声1中,则把它放在c1中已确定点的后面,如果声2列达尾部,则跳至p2的头部继续向d中增加点直到c1形成一条合法回路。最终生成的子个体为cl(456793218)。虽然按上述步骤可以生成子个体为c2(187692345),但是,为了从更多的父个体产生子个体,以维持种群中个体的多样性,本算法让每对父个体只产生一个子个体。

2.52—oPT变异算子

2一opt算法o”是求解TsP常用的启发式算法,算法的示意图如图1所示,其中没有标号的顶点代表两个或两个以上顶点间一系列的边。如果曲+cd>nf+Ⅺ成立,则删除边曲和cd,同时增加边口c和6d,并把顶点6和f之间的边反向。通常的2一opt算法从某个起始点开始,依次对两条边进行上述判断和操作。

计算机集成制造系统第13卷

圈l2一日pt邻域搜索优化示意

2.6混合遗传算法计算步骤

步骤l生成初始种群:根据设定的种群规模M,随机生成M个个体的第一层染色体,并根据2.1节所述方法计算个体的第二层染色体。

步骤2循环处理(1)至(4),直到设定的最大进化迭代次数GEN。

(1)对种群中的个体,计算个体所对应的行驶距离,并对个体按行驶距离从小到大排序。

(2)选择算子。将当代种群中适应度最低的Mx(1一P。)个个体删除,(1一P。)是选择概率。

(3)交叉算子。从种群中未被删除的个体中,随机选取M×P。对个体进行交叉操作(只是交叉概率),产生M×P。个子个体,使种群的个体数恢复到M以形成下一代种群。由于交叉算子只对个体的第一层染色体进行操作。因此,对于每个新生成的个体都要计算其对应的第二层染色体。

(4)变异算子。选择种群中M×P,的个体(P。是变异概率),采用上文介绍的2一。pt变异算子对个体的每条子路径进行优化。发生变异的个体中必须包含当前代中的最优个体(精英个体),其余的个体则随机选择。在变异操作后,也要将所有子路径按顺序重新组合成第一层染色体,保持个体在两层染色体之间的同步。

本文的混合遗传算法与文献[9]的算法比较相似,都在遗传算法中结合了2一opt算法。两种算法的区别如下t文献[9]中的交叉、变异算子仅作用于第二层染色体。在交叉、变异等遗传操作之后也没有对第一层染色体和第二层染色体进行同步。因此,可能产生不满足车辆容量约束的新个体,该文将这些新个体舍弃。这有可能产生大量的无效个体。而本文的交叉算子作用于第一层染色体,变异算子作用于第二层染色体,并且在上述遗传操作之后对两层染色体进行了同步,因而能保证第二层染色体符合容量约束;文献[9]将2一opt算法作为精英个体的改进算法,而本文将2一opt算法作为变异算子及精英个体的改进算法。3仿真计算及分析

为验证所提出算法的有效性,运用JAVA语言编程实现了上述混合遗传算法。并对几个国内外的常用vRP基准测试实例进行了仿真计算。仿真计算时,设置算法的选择概率P。一30“,变异概率只一20%。

3.1仿真实例l

文献[2]~文献[6]都采用了该实例。描述为t有一个配送中心和八个商店,它们之间的相互距离及各商店的商品需求量如袁1所示”3(商店。表示配送中心),配送中心有两辆载重量为8T的货车,要求合理安排车辆行驶路径,使总运输距离最小。

为了和文献进行比较,设置M一60,GEN=50,与文献[3]和[4]相同(文献[3]和文献[4]的计算结果优于其它文献)。对仿真实例随机进行了20次计算,计算结果及来自文献的结果列于表2,对三种算法计算结果的统计列于表3。从表中可以看出,本文提出的混合遗传算法的计算结果明显优于所列参考文献的结果。计算所得最优调度为:车辆一:[o476o],车辆二:[o13582o],装载率均为100%。改变遗传算法的参数,设置M一100,GEN;100,随机运行本算法程序20次,则每次都获得了最优解。

囊2算法结幂比较表

双种群遣传算法‘”

微粒群算法∞

车文混合遗传算法

一。一。

协礼

一o

一,一m¨L

吼L

m色

一o

—o—m

L乱

■一

一o

求了蠹乳豇

L吼L

警i瓮羔篡鬣

兰㈡㈡㈦篡咒

。一。一吼机

立一¨㈨:¨钟¨Ⅲ…㈨

一。一。

一一。m。。。,。挺

;曲∞盯ln∞盯l曲曲盯i∞盯∞l加的盯l盯盼盯;仲卯∞i儿明盯i曲明钉l盯钾盯l∞卯盯i儿∞盯i盯盯艚OO0佗蚰曲i加鲫盯i明∞∞;n盯∞l盯盯卵i曲船盯!阳钾盯

第10期姜昌华等:隶解车辆路径问题的混台遗传算法2051

裹3算法结果统计裹

3.2仿真实例2

文后所列大多数文献只使用规模很小的仿真实例1来验证算法的有效性。虽然在文献[4]和文献[9]中提及了更大规模的cVRP,但是实验数据非常简单。为了验证算法对更大规模cVRP的适用性,本文对cVRP基准测试实例E—n22一k4和E—n33一k4进行了计算(基准测试实例的数据从网址http://branchandcut.org/VRP/data/下载得到),计算结果如表4所示。

襄4E一Ⅱ22一¨和E—n33一k4计算结果衰

实倒名(已知最优值)种群大小连代次数l2345678010

(1)对于21个客户的实例E—n22一k4。由表

4可见,如果和实例l一样设置遗传算法的运行参

数(M=60,GEN=50),解的质量较差,随着M和

GEN的增大,解的质量也随之提高。当M增大到

100,GEN增大到1Ooo时,虽然可以获得该实例的

最优解,但是获得最优解的几率较低且各次计算结

果之间存在较大的偏差。当M—loo,GEN=

10000时,在10次随机运行中有9次获得了最优解。

为了观察算法的优化过程,在程序运行时,每当出现更好的解时都作日志记录。选择一次获得最优饵的运行日志(M=100,GEN;10000),其优化过程曲线如图2所示.从图2可以清楚地看出遗传算法的优化过程。由于遗传算法存在随机性,虽然最大进化迭代次数为10000,该次运行在1031代就获得了最优解。

(2)对于32个客户的实例E—n33一k4。由表4可见,当M一200,GEN一10000时,可以获得满意解。在10次计算中所求得的最大行驶距离为879,与最优解的误差为5.27%}最小行驶距离为850,与最优解的误差为1.8%。行驶距离为850的车辆调度为:

车辆1:[o303114l131220],装载量为7300,装载率为91-25%}车辆2#[o26271628

400

350

巍;圭量量{薰量嚣}篓囊糍;点蠹嬲

?::’:。:’j?:+:’::’??::‘:‘:‘??:‘:‘

.一:二。:.:.:.:.:二i:.:.:.:二二:.:.:二二二:.:.:揣:-;.:二二;,:,:.:二二?-:

OZ004W6∞8‘loJuuu

进化迭代次数

图2算法优化过程示意圈

29o],装载量为6800,装载率为85.o%;车辆3;[o113210897653o],装载量为7370,装载率为92.12%;车辆4#[o418192122202324251715o],装载量为7900,装载率为98.75%。

如果继续增大种群规模M至500,解的质量还能提高。行驶距离为837的近似解非常接近巳知最优解,其详细调度为:车辆1:[o1317252423202221】9181065123O],装载量为7920.o,装载率为99.o%;车辆2l[o211328974o],装载量为7700.o,装载率为96.25%}车辆3;[o1152627281629o],装载量为7950.0,装载率为99.37跖;车辆4:[o30143lo],装载量为鼻}鲥掣妊薜廿

2052计算机集成制造系统第13卷

5800.O,装载率为72.5%。

进一步增大M和GEN,计算时间变长,但解的质量没有明显提高。可见,针对不同客户数,M和GEN这两个参数对遗传算法的运行结果有较大的影响。在M和GEN相同的情况下,随着问题规模的增大,搜索空间也增大,这将导致解的质量降低。因此,在实际应用时,应根据问题规模的不同适当调整M和GEN的取值。如果问题规模小,则M和GEN的值可以小一些;反之,则应大一些。

4结束语

本文针对物流配送优化中的VRP,设计了一种结合2一opt子路径优化的混合遗传算法,并提出了一种新的双层染色体编码方案。采用该染色体编码方案能保证子路径为可行路径,且不需要预先知道完成配送任务所需的最少车辆数,更适于求解实际的物流配送优化问题。典型基准测试实例的计算结果表明,该算法是求解cvRP的有效方法。

参考文献:

[1]DANTzIGGB,RAMsERJH.Thet珈ck出8pⅡtchingprob—l∞l[J].Mana肛m朋tScience,1959,4(6)l8∞91.

[2]zHANGLipmg,cHAIYuet。tlg.Im邮vedgeneticalgorithm—f。fveh置山㈨gprobIem[J].研轧啪sE吨i纰吖i叫一The铲

ry&Practic3,2002,22(8){79—84(incMnc5e).[张丽萍,集跃

廷.车辆路径问题的改进遗传算法口].系统工程理论与实践,

2002,22(8):79一B4.]

[3]zHAoYanwei,wuBin.JIANGLi,etal-Do“Iepopula-Ⅱonsgeneticalgo^thmfoⅢhkIeroutingprobl咖[J].com—puterIntegfated

M删±a吐udngSygtema,2004r10(3)1303—306(Inchinese).[赵燕伟,吴斌,蒋丽t等.车辆路径问题的

双种群遗传算法求解方法[J].计算机集成制造系坑,2004,10

(3)一303—306.]

[4]xIA0mnmd,uJu嘶uⅡ.wANGⅪhuaLMod讧iedpanide啪rm

optimi加tioⅡalgonthmforvehicleroutIngproblem[刀.computerInt昭mted

M删factu五ngS”tem5,2005,11(4)l5"一581(inch【n髓e).[肖健梅,李军军,王锡淮,求解车辆路径问题的改进微粒群优化算莹[J].计算机集成制造系统,

2肿5,11(4);s77—581.]

[5]Lu0xia“guo.sHlHongbo.IrnProvedpartide绷flIl0ptI嘶-zatioⅡforvehicl¨叫tingproblem州thno小fullload口].Jour—nalofEa8tChinaUn|vcrsityofSdenccandT托h∞Io窖y;Natu一阳lScienceEdition,2006,32<7);767—771(岫chine5e).[罗先

国,侍洪渡.非满载车辆路径同题的改进粒子群优化算法[刀.华东理工大学学报:白然科学版,2006.32(7),767—77l_][6]LIJun,GuoYaohuang.Th∞ryandmethodfor她hicle叱hedulingprobleminlogist”dd抽tributi∞[M].B刮ing:Na—t岫tlalMatefiaIP嘲s,200l(inchin船e).[李军,郭耀煌.物流配送车辆优化谰度理论与方法[M].北京,中国物资出版

社,2001.]

[7]zHouMi雌,suNshudon墨Ge耻t证algodthm5:th∞ryandapplj曲tioIls[M].BeIjingINat如nalDden∞IⅡduBtry

P删,2002(inchi㈣),[周明,孙树栋.遗传算法原理及应用

[M].北京;国防工业出版社.2002.]

[8]RAu?HsTK.KoPMANL,PuLLEYBLANKwR,eta1.()nthe∞p扯htedⅥllicleroutitlgp∞bkm[J].MathemticalProgrammlng,2003,94(2/3)1343—359.

[9]wANGzuzhu,cHENGJh置ing。FANGHongbing'eta1.Anh如甜opt【mi珊t|onnlgo血hmsol“T岖wh记k∞“ngptobk砒[J].opentio始ResearchandMan89c册tsd洲,2004,”

(6),48?52(inchine盹).[狂祖柱,程索辫,方宏兵,等.车辆路径问题的混合优化算挂[J].运筹与管理.2004,13(6):48-52.]

[10]uNs,KERNIGHAMBw.Anefk吐i代h“^sticaIgorIthmfortlletr盯elliIIg8山蹦nprobl咖口].OperatioIIsRe¥earch,

1973,21(2,。408—516.

qphp+q,、一pq■、妒q≯、口hopq,、日4’ph日_q■h_pⅥ,h日pqp~,hd’__~,h日’Ⅵ■、■h_pqpqd、_‘qp、■“0p~,‘_9Ⅵ√h-pⅥ■、99Ⅵ■、_+q,、F‘_’、,、d、¥p、,、。产(上接第2046页)

4结束语

本文提出并介绍了一种基于过程控制的IQs系统的体系结构及其应用实例。该系统具备集成质量系统的基本功能要求,具有过程控制、柔性结构、可集成等特点。就文中所述的不合格品管理实例而言,应用本系统后,一是有效地避免了不合格品管理的过程失控;二是可以轻松地将质量管理目标和责任,通过过程控制落实到各个具体环节、落实到人,大大提高了工作效率}三是能够根据企业的要求,对业务过程进行快速重构;四是可以进行过程分析、过程优化,实现持续改进,提高企业的质量管理水平,增强顾客满意度。参考文献:

[1]LARI九Anintegratedinformation9”temfofqu“tyman-agefn姐t[J].Bu5}Ⅱe5sProcc船Man且g㈣t

J㈣l,2002,8(2)t16*182.

[2]Intemat∞nalO嘻跖i强tionforstandardi;a廿omls09001Qual—itylIla聃geⅢent8”t锄P北quirem∞ts[s].Genc".晰t弛r-hnd:Intemat岫naIorgannat如nforStand8rdization,2000.[3]PANYⅡshun,wuchcllg.cumnt8tateanddevelopmenttrer山。£珊rkflowmBnag嘲entM坼a比h^ⅡdⅣoduct8[J].c。mputerIntegratedManufa吐udngSyst唧st2000,6(1)Il一8(inchi吐se).[范玉顺,吴澄.工作巍管理技术研究与产品现状五发展趋势口].计算机集成制造系统,2000,6(1);1-8.][4]HoLLINGswoRTHnTheworkn。霄re如rencelnodeI[R]Wlnch幅t盯,UK{WorknowManag㈣tCoa“on,1999.

求解车辆路径问题的混合遗传算法

求解车辆路径问题的混合遗传算法

作者:姜昌华, 戴树贵, 胡幼华, JIANG Chang-hua, DAI Shu-gui, HU You-hua

作者单位:姜昌华,胡幼华,JIANG Chang-hua,HU You-hua(华东师范大学,信息科学技术学院,上海

,200062), 戴树贵,DAI Shu-gui(华东师范大学,信息科学技术学院,上海,200062;滁州学院

,数学系,安徽,滁州,239000)

刊名:

求解车辆路径问题的混合遗传算法

求解车辆路径问题的混合遗传算法

计算机集成制造系统

英文刊名:COMPUTER INTEGRATED MANUFACTURING SYSTEMS

年,卷(期):2007,13(10)

被引用次数:1次

参考文献(10条)

1.DANTZIG G B.RAMSER J H The truck dispatching problem 1959(06)

2.张丽萍.柴跃廷车辆路径问题的改进遗传算法[期刊论文]-系统工程理论与实践 2002(08)

3.赵燕伟.吴斌.蒋丽车辆路径问题的双种群遗传算法求解方法[期刊论文]-计算机集成制造系统-CIMS 2004(03)

4.肖健梅.李军军.王锡淮求解车辆路径问题的改进微粒群优化算法[期刊论文]-计算机集成制造系统-CIMS

2005(04)

5.罗先国.侍洪波非满载车辆路径问题的改进粒子群优化算法[期刊论文]-华东理工大学学报(自然科学版)

2006(07)

6.李军.郭耀煌物流配送车辆优化调度理论与方法 2001

7.周明.孙树栋遗传算法原理及应用 2002

8.RALPHS T K.KOPMAN L.PULLEYBLANK W R On the capacitated vehicle routing problem 2003(2-3)

9.汪祖柱.程家兴.方宏兵车辆路径问题的混合优化算法[期刊论文]-运筹与管理 2004(06)

10.LIN S.KERNIGHAM B W An effective heuristic algorithm for the travelling salesman problem 1973(02)

相似文献(10条)

1.学位论文曹二保物流配送车辆路径问题模型及算法研究2008

物流企业为了节约成本和保护环境,必须将先进的物流理论和物流技术引入企业的生产和经营管理中,作为实现物流合理化的重要内容和手段,研究车辆路径问题有助于企业降低物流成本、提高运作效率、提高客户满意度。车辆路径问题将运筹学理论与管理实践紧密地结合在一起,是近半个世纪以来运筹学领域最成功的研究之一。以往对车辆路径问题的研究都是将前向物流和逆向物流中的车辆路径问题分开考虑,而实际中的企业或客户为了节约成本和保护环境需将两者结合起来运作。本文研究几类物流配送车辆路径问题的模型和算法,在分析其理论和实践背景的基础上,提出其数学模型

,并构造了几种有效的亚启发式算法求解相关问题。其中同时送货和取货车辆路径问题有效整合了前向物流和逆向物流的车辆路径问题,本文在不确定性信息条件下,研究了同时送货和取货车辆路径问题的三种特殊情形,建立了相关的不确定性模型,给出了求解算法,并用数值实验检验了模型和算法的有效性。本文的主要研究内容和创新成果如下:

(1)基于改进差分进化算法的同时送货和取货车辆路径问题研究现有的车辆路径问题的模型不能完全描述同时送货和取货车辆路径问题的特征,提出同时送货和取货车辆路径问题的整数规划数学模型;同时运用改进差分进化算法求解该问题;并用数值实验检验该算法的有效性。

(2)基于改进遗传算法的带时间窗的同时送货和取货问题研究首次提出并建立了带时间窗的同时送货和取货车辆路径问题(VRP-SDPTW)的混合整数规划数学模型,可以将其转换为其它经典的车辆路径问题,同时采用改进遗传算法(IGA)求解该问题,数值实验结果表明该算法可以有效地求解VRP-SDPTW。

(3)基于复合最优模型微粒群算法的车辆数目不确定的带时间窗的车辆路径问题研究车辆数目不确定的带时间窗的车辆路径问题是带时间窗的同时送货和取货车辆路径问题的一种特殊情形,运用复合最优模型的微粒群算法求解该问题,并用数值实验检验该算法的有效性,同时与遗传算法、分派算法等启发式算法进行比较。

(4)多车型随机需求车辆路径问题研究在客户需求为随机条件下,研究具有多种车型、每种车型有多辆车的车辆路径问题,提出该问题的随机规划数学模型,在客户服务不可分割的前提下,研究了区别于重新优化策略的预优化策略,并分析了预优化策略的渐近性,结果表明预优化策略可以在节约大量计算资源的前提下能获得该问题的高质量解,并以预回路的期望成本作为目标函数,分别设计了改进的遗传算法和差分进化算法求解该问题,通过大量数值实验验证了算法的有效性。

(5)模糊需求车辆路径问题研究模糊需求车辆路径问题是对传统的确定性车辆路径问题的拓展。在引入决策者主观偏好概念的基础上,对于基于模糊可能性的模糊机会约束规划模型,提出了一种基于随机模拟的混合遗传算法;对于基于模糊可信性的模糊机会约束规划模型,提出了一种基于随机模拟的混合差分进化算法。同时,分别在两种混合算法中,采用随机模拟的数值实验研究了决策者主观偏好值对最终决策目标的影响,在最小化总行驶距离的目标下,得出了运用上述两种混合算法时的决策者的主观偏好值的最佳取值范围。

2.期刊论文于姗姗浅谈物流配送中的车辆路径问题-商场现代化2009,""(2)

本文通过分析物流在国民经济的重要地位,进而得出优化物流的核心是配送中的车辆路径问题,并对车辆路径问题进行描述和分类,便于进一步对车辆路径问题进行研究,从而优化物流配送,提高国民经济水平.

3.学位论文陈利基于混合粒子群算法的物流配送车辆路径问题的研究2007

配送是物流系统中很重要的一个环节。在物流的各项成本中,配送成本占了相当高的比例。车辆路径问题是配送系统中的核心问题,也是研究热点之一。路径安排合理能有效提高运输效率、降低服务成本。本文以物流配送为背景,对物流配送车辆路径问题和带时间窗的车辆路径问题采用基于爬山

算法的混合粒子群算法进行了深入的研究。

粒子群算法是一种基于群智能方法的演化计算技术,具有深刻的智能背景,广泛应用于科学研究和工程问题。针对粒子群算法早熟收敛和局部搜索能力不足的缺陷,本文引入局部搜索能力强的爬山算法对其进行优化,提出了基于爬山算法的混合粒子群算法。设计了两种混合粒子群算法,对每代群体中的全局极值引入爬山操作构成混合PSO方案一,对每个粒子进行爬山操作构成混合:PSO方案二。混合粒子群算法在局部搜索能力和收敛速度上较标准PSO都有很大的改进。混合PSO方案一局部搜索能力大于标准PSO,混合PSO方案二局部搜索能力大于混合PSO方案一。混合PSO方案二的收敛速度最快

,混合PSO方案一次之,标准PSO的收敛速度最慢。

本文在查阅大量中外文献的基础上,结合物流配送的特点,建立了物流配送车辆路径问题的数学模型。采用标准PSO算法、混合PSO方案一和混合PSO方案二3种方法求解了物流配送车辆路径问题和带时间窗的车辆路径问题。仿真试验表明,本文提出的混合PSO方案一和混合PSO方案二性能均优于标准PSO。混合PSO方案二的性能最优,具有很强的收敛能力,能够有效地求解物流配送车辆路径问题。该方法对物流配送企业优化配送路径、降低配送成本和提高物流经营管理水平,最终增加企业的竞争能力具有重要的参考价值。

4.期刊论文方金城.张岐山.FANG Jin-cheng.ZHANG Qi-shan物流配送车辆路径问题(VRP)算法研究-徐州工程学

院学报2007,22(2)

物流配送车辆路径问题(VRP)属于NP-hard问题.文章介绍了当前最具有代表性的算法,分析并总结了各种算法的优缺点及目前的改进情况,指出目前启发式算法是求解车辆路径问题的主要方法,至于大规模客户集的配送路径优化问题或者是多约束的复杂VRP问题,可以考虑利用多种算法相结合的办法来解决.

5.学位论文李宏城市冷链物流配送车辆路径问题的研究2006

随着社会经济的发展和生活、工作节奏的加快,人们对生鲜冷冻食品的需求越来越大。零售商为了提高其销售水平,对城市冷链物流配送商的要求也愈来愈高,通常会对配送时间和配送质量提出限制性的要求;对配送商而言,在考虑时间窗限制的同时,还要考虑到城市道路交通的可能拥塞、配送商品的易腐特性等“随机”性因素对配送的影响,以最终达到配送成本最小化的目的。因此,在考虑时间窗约束和随机性因素影响的条件下,研究构建成本最小化的冷链物流配送车辆路径问题的数学模型具有重要的理论和实践意义。

本文以传统时窗限制下的车辆路径问题为基础,分析生鲜产品路线配送特性并构建相关成本函数,包括因产品腐坏所造成的货损成本、违反顾客需求时间窗所造成的惩罚成本、配送时冷冻设备消耗的能源成本,以及传统车辆路径问题中的车辆固定成本和随里程递增的运输成本等。从冷链物流配送商的角度使上述各项成本的总和最小为目标,构建冷链物流配送路径的基本模型。同时,研究城市冷链物流配送车辆运行时间和一天之中温度变化的依时特性,将基本配送路径模型进行改进,从而得出冷链物流配送车辆路径问题的数学规划模型。最后进行算例分析及主要参数的敏感度分析,以验证本文所构建的模型的合理性及可行性。本论文的研究结论可为冷链物流配送商在追求配送总成本最小化的前提下进行线路选择、车辆规模、配送时间的优化安排等的参考,具有良好的应用价值。

6.期刊论文方金城.张岐山.FANG Jin-cheng.ZHANG Qi-shan物流配送车辆路径问题(VRP)算法综述-沈阳工程学

院学报(自然科学版)2006,2(4)

物流配送车辆路径问题(VRP)属于NP-hard问题,时这类问题如何求解,学术界提出了多种算法,这些算法可归结为2大类:精确算法和启发式算法.通过对这2类算法中最具代表性的几种算法的分析、比较和总结,指出了各种算法的优缺点、适用范围和场合、存在的问题以及改进的方案,为物流配送车辆路径问题求解过程中算法的选择提供了依据和参考.

7.学位论文张丽萍物流配送中车辆路径优化系统的研究与实现2001

该文研究了两类车辆路径优化问题——有能力约束的车辆路径问题(Canac1tated Vehic1e Routing problem简称CVRP)和有时间窗约束的车辆路径问题(Vehid,Routing Problem With Time Window简称VRPTW),并就此开发了车辆路径优化的原型系统.首先,对有能力约束车辆路径问题的内在特征进行了研究,在此基础上建立了有能力约束车辆路径问题的数学模型,该模型集中了影响有能力约束车辆路径问题的定量和定性指标,这不仅能够满足大多数实际情况的需要,而且充分发挥了调度人员的主观能动性.提出了一种基于新颖交叉算子的改进遗传算法用于问题的求解,此算法不仅在收敛速度和解的性能上优于其它算法,而且能够有效地避免传统遗传算法的"早熟收敛"问题.其次,进一步描述了时间窗口对车辆路径优化问题的约束,构造了有时间窗车辆路径问题的通用数学模型,该数学模型不仅能够满足大多数实际问题的需要,而且通过对特定参数的设定还能够转换成其它几种典型的组合优化问题的数学模型.提出一种基于优先关系的遗传算法,将该算法用于有时间窗的车辆路径问题的解决中,实验结果表明,此算法可以有效求得有时间窗车辆路径问题的优化解,是求解该问题的一个较好方案;同时也为求解其它组合优化问题提供了新的途径.最后,实现了物流配送中车辆路径优化的原型系统,该系统想给调度者提供一个可行的.有效的辅助决策工具,以提高决策的质量和速度,从而提高企业的经济效益和对顾客的服务质量.

8.学位论文尹传忠铁路行包物流配送系统优化若干问题研究2006

结合国外包裹快递四大巨头(UPS、FedEx、DHL、TNT)的经营现状和在中国的发展状况以及国内包裹快递市场的现状,以铁路行包运输的改革及目前的经营方式为背景,分析了铁路行包运输所面临的形势,说明铁路行包运输发展现代物流的紧迫性及必要性。

本文应用现代物流中选址问题及配送车辆路径问题的理论,解决铁路行包物流配送问题。详细回顾了国内外物流节点选址的方法、数学模型、求解算法;将配送车辆路径问题分成一般的车辆路径问题、有时间窗的车辆路径问题、有回送任务的配送车辆路径问题、可分切配送的车辆路径问题进行分析,结合目前研究最多的有时间窗的车辆路径问题,综述了该类问题的数学模型和求解算法,重点分析了各种启发式算法的研究结果。

铁路行包基地及配送点选址规划问题是多层选址问题,文章给出了一般情况下铁路行包基地及配送点选址规划的数学模型,用基于扫描法、迭代法的局部搜索启发式算法求解,实例证明了模型及算法的有效性;考虑到铁路行包客户的不确定性,结合物流节点选址问题的动态模型和概率模型,给出了铁路行包基地及配送点选址规划的动态模型及概率模型,同时针对两种模型在表述不确定需求的铁路行包基地及配送点选址规划问题不足的情况,建立了不确定需求的铁路行包基地及配送点选址规划的数学模型。通过对客户需求的预测,求客户需求的分布函数,进行曲线拟合,对客户需求分布函数积分得出客户需求量的方法求解,该方法使求解得到简化,切合实际。

配送车辆路径问题是NP-hard问题,是目前物流学领域的热点。本文着重考虑铁路行包配送同时集货的实际,并以一般情况下铁路行包配送车辆路径问题为基础、研究有客户优先及考虑到大宗客户的铁路行包配送车辆路径问题。分别给出其配送车辆路径问题的数学模型,针对一般情况下铁路行包配送车辆路径问题的数学模型,采用基于最近邻域的禁忌搜索算法求解。在求解有客户优先的铁路行包配送车辆路径问题的遗传算法中,用时间窗表示行包客户的优先等级,同时考虑一个配送点配送和集货不同的时间窗;在编码时通过增加虚拟集货点,使问题得到简化,设计了确保个体编码有效性的OX交叉算子,保证在两个父代个体相同的情况下仍让能产生变异效果,设置适当的个体评价函数确保符合条件而较优的个体有较大的生存机会,用基于模拟退火技术的Metropolis判别准则的改进复制算子,确保个体的多样性,避免算法过早收敛。实例表明算法有效可行。

考虑大宗客户的铁路行包配送车辆路径问题属于可分切配送车辆路径问题,根据铁路行包物流配送的实际,将问题分为一般客户不分切和可分切两种情况,针对一般客户不分切的情况,采用将大宗客户按其剩余运量视为一般客户的方法求解;针对一般客户可分切的情况,参考求解VRPTWSD的方法,考虑同时具有送货和集货的约束进行求解。求解过程分为三个阶段:首先基于时间窗和配送同时集货构造基本可行解,用禁忌搜索优化初始解,最后采用快速优化手段对得到的解再优化,得到优化解。最后用实例证明算法有效可行。

论文紧密结合铁路行包运输的实际、采用物流节点选址问题和配送车辆路径问题的理论和方法,系统地研究了铁路行包基地及配送点选址规划和铁路行包配送车辆路径问题,为铁路行包企业发展现代物流提供一定理论支持与决策依据,同时,也为解决类似铁路行包物流配送的问题提供了的思路。

9.会议论文许鑫.范文慧.冯雅喆车辆路径问题的仿真建模分析2008

车辆路径问题是物流研究领域的热点问题,合理的车辆路径规划可以降低物流配送成本,提升客户服务质量.本文结合仿真的优势,建立了基于AnyLogic仿真软件平台的仿真模型.在所建立的仿真模型基础之上,通过似真运行参数的动态随机变化,对实际的配送过程进行模拟,通过仿真模型的反复运行对车辆路径问题的一些关键因素进行分析,考察交通拥挤状况、时间窗宽度等关键因素对车辆路径问题的影响,从实际应用的角度对车辆路径问题涉及到的各种关键因素进行分析,对实际的物流配送具有一定的参考价值。

随着人类社会的发展,对问题的求解要求已经不仅仅停留在可行性的角度上,而是朝着简洁、高效、快速的方向前进,不仅要求满足人们的生活学习的一般需求,而且在时间、空间等资源消耗上也要求达到最少,以最小的代价实现最好的结果.现代的物流管理学便是其中一个例子.

随着物流业向全球化、信息化及一体化发展,配送在整个物流系统中的作用变得越来越重要.运输系统是配送系统中最重要的一个子系统,运输费用占整体物流费用的5096左右,所以降低物流成本首先要从降低物流配送的运输成本开始.其中,运输线路是否合理直接影响到配送速度、成本和效益,特别是多用户配送线路的确定是一项复杂的系统工程.高节奏高效率的社会,人们对于物品的配送,不仅要满足正常的物品配送要求,而且还在物质资源、人力资源、时间资源等的消耗上也提出了要求.

在物流配送业务中,配送车辆调度问题的涉及面较广,需要考虑的因素较多,对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大

.而且,随着市场经济条件下对配送服务水平要求的提高,时间因素在配送过程中越发显得重要.鉴于此,本文将着重研究带时间窗约束的物流配送车辆路径问题.

运输问题是物流决策中的关键问题.一般来说,除去产品中的采购成本外,运输成本比任何其他物流活动的成本所占的比例都要高.尽管运输的形式有很多种,但其中最重要的不外乎运输方式的选择、车辆调度与规划等内容.

选取恰当的车辆路径,可以加快对客户需求的响应速度,提高服务质量,增强客户对物流环节的满意度,降低服务商运作成本.正是有这种迫切的需求

,所以在计算机高度发展的今天,如何让计算机模拟物流的配送过程,并最终给出最简洁最高效的配送方案,一直以来是众多计算机学者研究的焦点,并由此衍生出了一个新的研究课题--车辆路径问题(Vehicle Roting Problem,VRP).

通过世界各国广大研究人员的共同努力,现已提出了许多用于求解不同类型的VRP的最优解和近优解的模型及其精确和启发式算法,以及相应的软件包.与国际上相比,国内对VRP的研究相对较少,有关车辆路径问题的研究是在20世纪90年代以后才逐渐兴起的,比国外相对落后30余年.目前,国内对于复杂的车辆路径问题的研究尚处于起步状态.

基于对目前VRP研究中存在的问题进行详细的分析,本文首先将物流配送问题及物流配送环节中的VRP问题进行系统详细的阐述,包括对该问题提出的研究背景、国内外的研究现状,以及研究的理论依据及存在的问题均作出深刻剖析和总结,并将在VRP问题中需要考虑的目标及约束进行综合,列出一个统一的数学模型.这个模型可以根据不同单位对各目标的重视程度给每个目标辅以不同的权重值,或者可以将五个目标按优先权合理安排目标模型.本文还根据研究该问题的发展过程,把国内外出现的解决VRP问题的各种算法的原理及执行过程作了详细地说明,并分析各种算法的优缺点,说明其最适用于解决何种问题.然后根据建立的数学模型,找一个典型的物流配送案例,使用C-W方法解决该问题.最后,对该研究领域做出总结和展望.

引证文献(1条)

1.李净.袁小华.朱云飞物流配送系统中车辆路径问题的实现[期刊论文]-计算机工程与设计 2009(16)

本文链接:http://www.doczj.com/doc/f10e325177232f60ddcca16d.html/Periodical_jsjjczzxt200710027.aspx

授权使用:北京航空航天大学(bjhkht),授权号:f4f1e9c0-c41b-468d-9df4-9ddb00bb58b2

下载时间:2010年8月23日