1999年6月系统工程理论与实践第6期
车辆路径问题的遗传算法研究a
姜大立1 杨西龙1 杜 文2 周贤伟2
(1.后勤工程学院自动化系,重庆400041)
(2.西南交通大学运输系,四川成都610031)
摘要 在分析车辆路径问题的现有启发式算法的基础上,本文构造了车辆路径问题的染色体表达,并
对染色体进了可行化影射,建立了此问题的遗传算法.实验结果表明,此算法可以有效求得车辆路径
问题的优化解或近似优化解,是求解车辆路径问题的一个较好的方案.
关键词 车辆路径问题 遗传算法 启发式算法 优化
A Study on the Genetic Algorithm for
V ehicle Routing Problem
JIANG Dali1 YANG Xilo ng1 DU Wen2 ZHOU Xianw ei2
(1.L o gistic Eng ineering U niv ersity,Cho ngqing400041)
(2.Southw est Jiaoto ng U niv ersity,Cheng du610031)
Abstract O n the analy sis of the existing heurist ic methods o f the v ehicle r outing pr ob-
lem,this paper pro poses a g enetic algo r ithm for t he v ehicle ro uting pro bem.With t he
nov el chro moso me pr esentation for t he vehicle ro ut ing pro blem,the cor r esponding feasi-
bility pr o cess and ot her impr ov ed GA o per ato rs,this alg or ithm can find the optimal o r
nearly optimal so lution t o the v ehicle ro uting pro blem effect ively,w hich is pr ov ed by t he
number ex per iment pro vided by this paper.
Keywords vehicle r outing pro blem;g enet ic algo rithm;heur istic alg or it hm;o ptimiza-
tio n
1 引言
在许多配送系统中,管理者们需要采取有效的配送策略以提高服务水平、降低货运费用.其中车辆路线安排问题(车辆路径问题vehicle ro uting pr oblem)是亟待解决的一个重要问题,此问题可描述如下:有1个货物需求点(或称顾客),已知每个需求点的需量及位置,至多用K辆汽车从中心仓库(或配送中心)到达这批需求点,每辆汽车载重量一定,安排汽车路线使运距最短且满足每条路线不超过汽车载重量和每个需点的需求必须且只能由一辆汽车来满足的约束条件.车辆路线安排问题是一个NP完全问题,只有在需点数和路段数较少时才有可能寻求其精确解.因此,车辆路径的启发式算法成为人们研究的一个重要方向,先后涌现出一大批启发式算法,如最早由Clarke和W right提出的节约法[1],Gillett和M iller提出的扫描法[2],Br amel和Simchi-Lev i的提出的基于选址问题转化的L BH法[3],Fisher和Ja ikum ar建立的一般分配算法[4],Chr istofides和M ing go zzi等建立的不完全树搜索算法[5],Pur eza和F r anca研究的T abu搜索算法[6]等等.这些算法为求解车辆路径问题提供了有效的方法,但也存在一系列问题,如节约法虽然通过列出各点对间的节约量,按节约量从大到小构造路径,具有运算速度快的优点,但存在未组合点零乱、边缘点
a收稿日期:1997-11-03
难于组合的问题;扫描法为非渐进优化[7];L BH 法则存在问题转化麻烦且选址问题本身难解等等.如何针对车辆路径问题的特点,构造运算简单、寻优性能优异的启发式算法,这不仅对于配送系统而且对于许多可转化为车辆路径问题求解的优化组合问题具有十分重要的意义.
遗传算法(Genetic A lgo rithm,G A )是由J.H.Holland 等于70年代发展起来的[8].它是一种以自然选择和遗传理论为基础,将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法.其通过给解向量编码、形成初始种群,然后用变异、交叉重组、自然选择等算子,进行并行迭代,求得优化解.由于它采用随机运算,对搜索空间无特殊要求,无需求导,具有运算简单、收敛速度快等优点,因此近年来有很快的发展,并在组合优化、自适应控制、机器学习等许多领域获得应用[9,10],有着广泛的应用前景.为此,本文研究运用G A 编码构造求解车辆路径问题的算法,并对其运算过程和结果进行分析.实验数据表明本算法行之有效,不失为一种求解车辆路径问题的性能优越的启发式算法.
1 车辆路径问题的数学模型
假定中心仓库最多可用K 辆车对1个分仓库进行运输配送,每个车辆载重为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 表示分仓库r ki 在路径k 中的顺序为i (不包含中心仓库).令r k 0=r k (n k +1)=0表示中心仓库,则有如下表示的车辆路径问题的数学模型:
minimize
6K
k =1
(6
n k
i =1
c r k (i -1)r ki +c r kn
k
r k (n k
+1)
?sig n(n k -1))
s.t.
6n k
i =1
d r k i F b k
k =1,2,…,K
(1)0F n k F l , k =1,2,…,K
(2)6
K
k =1
n k =l
(3)R k ={r ki ?r k i ∈{1,2,…,l },i =1,2,…,n k }(4)R k 1∩R k 2=á P k 1≠k 2
(5)
其中,
sig n(n k -1)=
1 n k E 10 其他
上式中不等式(1)保证每条路径上的各分仓库的总需求量不超过此条路径的配送车容量,不等式(2)表明每条路径服务的分仓库数不超过总分仓库数,等式(3)要求每个分仓库都得到车辆的配送服务,等式(4)表示每条路径的分仓库组成,等式(5)则限制每个分仓库的需求仅能由一个车辆来完成.
2 车辆路径问题的遗传算法
从上述模型可知,求解车辆路径问题的关键是合理确定车辆与各分仓库的关系,在满足车辆载重量和分仓库需求约束条件的情况下使得总费用最小,因此可以构造遗传算法如下:2.1 构造染色体,产生初始种群
用矢量(s 1,s 2,…,s l )表示染色体G ,其中元素(基因)s j 为[1,k ×l ]之间的一个互不重复的自然数,它表
示了第j 个确定第m =(s j -s j -l l ?l )个分库与路径k =(s j -s j -l
l
+1的关系([]表示取整数,下同.),
即确定分库m 是否由车辆k 配送及确定分库m 在路径k 中的顺序的次序为j .随机产生一组染色体G h (h =1,2,…,n )(其中n 为一代种群中的个体数),G h 各不相同,此为第一代种群.2.2 可行化过程
将染色体的编码向量映射为满足全部约束条件的可行解称为可行化,其过程如下:
41
第6期车辆路径问题的遗传算法研究
1)令分库需求条件满足的标志变量d z m =0(m =1,2,…,l ).
2)令路径k 中的分库数目n k =0(k =1,2,….K ),令b ′k =b k ,R k =á(k =1,2,…,K ),路径k 中除去中心仓库后第i 个位置的分库号为r ki =0(i =1,2,…,l ),即此时所有路径皆未形成.3)j =1.
4)第j 次确定分库m 与路径k 间的关系,其中,m =(s j -s j -l l ×l ),k =(s j -s j -l
l
+1.
5)判断dz m 是否等于0,若等于0,表明分库m 的需求尚未满足,转5)继续判断路径m 的情况;否则转7).
6)判断dz m 是否为0?
1若为0:判断d m F b ′k 成立否?若成立,令dz m =1,b ′k =b ′
k -d m ,n k =n k +1,r kn k =m ,R k =R k ∪{m };若不
成立,转7).
o若不为0:转7).
7)j =j +1,转4)重复上述过程,直到j =K ×l +1.此时检查是否所有dz m =1,(m =1,2,…,l )成立,若成立,说明在满足各约束条件的情况下,所有的分库均分配了一个路径,构成路径集合RT ={R 1,R 2,,…R k },即为染色体所对应的原车辆路径问题的一个可行解;若不成立,说明此染色体表示的路径分配方案不满足约束,为原V RP 问题的一个不可行解.
以第三章中的数据为例说明上述过程,假设一染色体编码为:1 2 4 7 8 16 15 9 10 13 12 5 6 14 3 11
s 1=1,首先确定路径
k =
s 1-l
l
+1=1-18+1=1与分库m =s 1-s 1-1l ×l =1-0=1关系,此时dz 1=0,d 1=1
1=8-1=7,dz 1变为d z 1=1;s 2=2,第2次确定路径k =
s 2-l l +1=1与分库m =s 2-s 2-1
l
×l =2的关系,此时dz 2=0,d 2=1
1=7-1=6,d z 2变为dz 2=1,如此第i 次根据基因s i 的值确定某一分库与路径的关系,最后即第16次确定路径k =
11-18+1=2与分库
m =11-11-1
8
×8=3的关系,此时由于
dz 3=1说明分库3已安排至其他路径,无须再安排至路径2.其可行化过程可表示为表1:表1 可行化表
分库12345678路径
1r 11r 12r 15r 13××r 14×2
××××r 22r 23×r 21需求量
1
2
1
2
1
4
2
2
表中×格表示对应的路径无需安排分库,染色体所代表的路径安排为:0→1→2→4→7→3→0与0→8→5→6→02.3 性能估计
对一代种群中的每一个染色体G h (h =1,2,…,l )应用2.2,求得对应可行解RT h (h =1,2,…,n ),代入目标函数Z h =
6K
k =1
6
n k
i =1
(c r k (i -1)r ki +c r kn
k
r k (n k
+1)
?sig n(n k -1)
;若染色体对应的为非可行解,则赋予其
目标函数一个很大的整数z h =M .令G h 的适应性函数f h =1/z h ,f h 是个体G h 在生存竞争中生存能力的表现,越大表明其性能越好,即其对应的解越接近最优解.2.4 判断停止进化条件
判断迭代的代数是否为要求代数N ,若是,停止进化,选性能最好的染色体G *h 所对应的路径集合RT *h 作为原V RP 问题的优化解输出.反之,继续执行2.5.
42
系统工程理论与实践1999年6月
2.5 自然选择
将每代种群共L 个染色体按适应值f h 由大到小排列(h =1,2,…,n ),排在最前一位的个体性能最优,将它复制一个,直接进入下一代种群.下一代种群的另L -1个染色体则从前代种群的n 个染色体中按概率p h =q ′(1-q )h -1(h =1,2,…,n ),用轮转法选择个体G h ,产生后代形成.这样既可保证最优者生存至下一代,又可避免个体间因适应值大小不同而使被选择进入下一代的机会相差悬殊,保持了下代种群个体的多样性,从而可有效提高整个算法的收敛速度.其中q ′=q /(1-(1-q )n ),q =0.08.种群代数增1.2.6 染色体交叉重组
对2.5所产生的新种群,按选择概率p c 选择个体对进行交叉重组,共进行n /2次.文献[11]表明交换率p c =0.6～0.8之间时,进化性能较好,本文取p c =0.7,交叉规则采用P M X 法[12],下面举例说明.设父代的两个染色体为A =9 8 4 5 6 7 1 3 2 10,B =8 7 1 2 3 10 9 5 4 6,按照PM X 法,交叉重组过程如下:
k 1
k 2
k 1
k 2
A =9 8 4
B =8 7 15 6 72 3 101 3 2 109 5 4 6^
A ’=9 8 4
B ’
=8 10 12 3 105 6 71 6 5 79 2 4 3 其中交叉交换点1≤k 1 在每代种群中,以变异率p m =0.02对染色体进行变异,变异策略是随机交换选中染色体内两个基因的值.对变异成功所获染色体应用2.2,2.3求得其适应值,并与其父染色体比较,择性能优者进入种群.2.8 返回2.4,循环. 3 实验及分析 有八个分仓库和一个中心仓库的配送系统,各分仓库对中心仓库的需求为d i (i =1,2,…,8)(单位为吨),中心仓库只有两辆车用于配送,每辆车的容量皆为8吨,已知中心仓库与各分仓库间的距离如表2(其 中0表示中心仓库),要求合理安排车辆的行驶路线,使总运行费用最少,即总运输里程最小. 表2 分库间距离及各分库需求量表 c ij 01234567800467.592010168140 6.541057.5111026 6.507.510107.57.57.537.547.501059915491010100107.57.5105205105100797.56107.57.597.570710716117.597.59701088 107.515107.510100需求量 1 2 1 2 1 4 2 2 运用本文提供的遗传算法对上述问题进行求解,用2×8个互不重复的1到16的自然数构成一个染色体码链,表示一种车辆路径安排方案,随机产生10个这样的染色体构成初始种群,预定进化代数为50,以0.7和0.02分别作为染色体的交叉率和变异率对染色体进行交叉和变异操作,经过上机运算,得最终的线路 43 第6期车辆路径问题的遗传算法研究 为: 0→4→7→6→00→1→3→5→8→2→0运输总距离为:67.5 显然,此方案既满足车辆容量约束又满足了各分仓库的需求,是上述车辆路径问题的一个可行解.而用节约法对同一问题进行求解,得线路安排为: 0→6→5→7→3→00→4→8→2→1→0相应的运输距离为:79.5 从上可见,本文的遗传算法解的结果明显优于节约法,不失为车辆路径问题一个较优的满意解.而对上述算例的遗传算法过程进行跟踪,发现每代最优个体的适应度变化如图1所示,说明本文所构造的车辆路径遗传算法在较小的种群规模下可以较快的速度进化,向最优解逼近.进一步以文献[5]中所提供的几种规模的车辆路径问题进行试算,得本文的GA 算法的结果与其他启发式算法的结果比较如表3,从中不难看到G A 算法在大多数情况下比其他算法具有较好的寻优结果. 表3 V R P 的启发式算法寻优结果对比表 问题 序号规模节约法 扫描法 选址法 分配法 树搜索法 GA 法 150585532524.9524534521.82100886851832.9833832.9840.53150120410791088.610141088.61060.94 199 1540 1389 1461.2 1386 1461.2 1461.2 图1 GA 寻优过程图 4 结论 在物流配送系统中,合理安排车辆路线是减少浪费、提高经济效益的重要手段,然而由于问题本身的N P 完全性质,精确求解非常困难,研究启发式算法不失为一种可行的方向.通过对车辆路径问题的分析,本文提出了巧妙的染然体编码和可行化过程,建立了基于GA 的车辆路径的启发式算法,实验证明本算法性能较好,可以较快地找到问题的优化解或近似优化解,是求解车辆路径问题的一个较好的方案.运用本算法同样可以有效求解带时间窗的V RP 问题,作者将另撰文予以探讨. 参考文献 1 Clar ke G and W right J .Scheduling o f v ehicles fr om a centr al depo t to number o f deliver y po ints .O pns . Res ,1964,12(4):12～182 Gillit t B E and M iller L R .A Heur istic A lg or it hm fo r the V ehicle Dispatch Pr oblem .O pns .Res , 1974,22:340～3493 Bra mel J and Simchi -L evi D .A Lo catio n Based Heur istic for G eneral Routing P r oblems .O pns .Res , 1995,43:649～6604 F isher M L and Jaikumar R.A G eneralized Assig nment Heur istic fo r V ehicle Ro ut ing.N etwo r ks, 44 系统工程理论与实践1999年6月 1981,11:109～124 5 Chr isto fides N ,M ing ozzi A and T oth P .T he V ehicle Routing P ro blem .Co mbinato rial O ptimizat ion . Jo hnly Wiley ,N ew Y o rk ,19796 Pur eza V M a nd F ranca P M.V ehicle Routing P ro blems v ia T abu Search M etaheur istics.P ublicatio n CRT -747,Centr e de R echer che sur les T r anspo rt s,M o nt real,1991 7 D imit ris ,Ber tsimas J and Sim chi -L evi D .A N ew G enerat ion of V ehicle Routing Resear ch :Robust A l-go rithms ,A ddressing U ncer tainty .O pns .Res ,1996,44(2):286～3048 Ho lland J H.A dapt atio n in N at ur al and A rt ificial System.M it Pr ess,Cambridg e,M ass,1975.9 Go ldberg D E.Genetic A lg or ithm in Sear ch.O ptimizat ion and M achine L earning ,A ddiso n-Wesleg.Reading.M ass,1989 10 Andro ulakis I P and V enkata subra manian V .A Genetic A lg or ithm Fr ame W or k fo r Pr ocess Desig n and O ptimization .Com puter s Cher m .Eng ang ,1991,15:217～22811 Dejo ng K A.Analysis of the behavior o f a class of genetic adaptive sy stems.Ph.D.t hesis.U niv.o f M ichig an.A nn A r bir ,M ich .1975 12 Go ldberg D E and L ing le Jr R .Alleles ,lo ci ,and the tr aveling salesman pr oblem .Seco nd Int .Conf .o n Genetic A lgo rithms a nd their A pplicatio ns ,1985,154～159 (上接第39页) 6 K now lton B J et a l .A N eo st riatal Habit L earning System in Humans .Science ,1996,273:1399～14027 F ust er J M.M emor y in Cer ebral Cor tex.M IT P ress,1995 8 Zipser D et al.A spiking netwo r k model of sho rt -ter m activ e memo ry.J.N eur osci,1993,13:3406～ 34209 A ndr easen N C .L inking M ind and Br ain in the Study of M ental Illnesses :A Pr oject fo r a Scientif ic P sycho-Patho lo gy.Science,1997,275:1586～159310 黄秉宪.海马记忆功能的神经网络模型.生物物理学报,1993,9:599～603 11 Huang Bingx ian.M emo ry Co nso lidat ion and N eur al N etw or k o f t he Hipocampus.Pr oc.I nt Conf N eu-r al N etw o rks and Signal Pr ocessing .G uangzhou ,1993:114～11912 Pav ildes C and Winso n J .Reactiv atio n o f Hippocampal Ensemble M emor ies D ur ing Sleep .,J N eu-r osci,1989,9:2907～2918;W ilso n M -A ,a nd M c N aughto n B.L ,Science,1994,265:676～67913 Alv arez P and Squire L R.M emo r y Co nso lidat ion and M edial T empor al L obe :A Simple N etw or k M odel .Pr oc N atl A cad Sci U SA ,1994,91:7041～704514 M cClelland J L et al .Why T her e ar e Complementar y L earning Sy st em in t he Hippo campus and N ecor tex.P sycholog ical Review ,1995,102:419～45715 黄秉宪.短时记忆的神经网络模型.生物物理学报,1995,11:411～415 16 黄秉宪,李忠.具有竞争指针的短时记忆神经网络模型.生物物理学报,1996,12:603～608 17 周鹏翔,黄秉宪.海马齿状回信息加工模型.1996生物医学中的信息与控制学术讨论会,黄山,199618 Bunsey M and Eichenbaum H .Co nser vation of Hippocampal M emor y Funct ion in R ats and Humans .N atur e,1996,379:255～25719 T r aub R D,et al.A M echanism for G ener ation o f L o ng -r ange Synchro no us Fast O scillatio n in the Co rtex.Na ture,1996,383:621～624 45 第6期车辆路径问题的遗传算法研究 捕食搜索算法 动物学家在研究动物的捕食行为时发现，尽管由于动物物种的不同而造成 的身体结构的千差万别，但它们的捕食行为却惊人地相似.动物捕食时，在没有 发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物.一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有 猎物迹象的附近区域进行集中的区域搜索，以找到史多的猎物.在搜寻一段时间 没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻 找猎物。 模拟动物的这种捕食策略，Alexandre于1998提出了一种新的仿生计算方法，即捕食搜索算法(predatory search algorithm, PSA)。基本思想如下：捕食 搜索寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解;然后在较 优解附近的区域(邻域)进行集中搜索，直到搜索很多次也没有找到史优解，从 而放弃局域搜索;然后再在整个搜索空间进行全局搜索.如此循环，直到找到最优解(或近似最优解)为止，捕食搜索这种策略很好地协调了局部搜索和全局搜索 之间的转换.目前该算法己成功应用于组合优化领域的旅行商问题(traveling salesm an problem )和超大规模集成电路设计问题(very large scale integrated layout)。 捕食搜索算法设计 (1)解的表达 采用顺序编码，将无向图中的，n一1个配送中心和n个顾客一起进行编码.例如，3个配送中心，10个顾客，则编码可为:1一2一3一4一0一5一 6一7一0一8一9一10其中0表示配送中心，上述编码表示配送中心1负 贡顾客1,2,3,4的配送，配送中心2负贡顾客5,6,7的配送，配送中心3负贡顾 客8,9,10的配送.然后对于每个配送中心根据顾客编码中的顺序进行车辆的分配，这里主要考虑车辆的容量约束。依此编码方案，随机产生初始解。 (2)邻域定义 4 仿真结果与比较分析(Simulation results and comparison analysis) 设某B2C电子商务企业在某时段由3个配送中心为17个顾客配送3类商品，配送网络如图2所示。 摘要：经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去其最优性。本文提出的局内最短路问题，就是在已知条件不断变化的条件下，如何来快速的计算出此时的最优路径，文章设计了解决该问题的一个逆向标号算法，将它与传统算法进行了比较和分析，并针对实际中的物流配送管理中路径优化问题，按照不同的算法分别进行了详细的阐述与分析。 一、引言 现实生活中的许多论文发表经济现象通常都具有非常强的动态特征，人们对于这些现象一般是先进行数学上的抽象，然后用静态或统计的方法来加以研究和处理。从优化的理论和方法上看，经典的优化理论大多是站在旁观者的立场上看问题，即首先确定已知条件，然后在假设这些已知条件不变的基础上给出最优方案（即最优解）。条件一旦发生变化，这种方法所给出的最优方案就会失去其最优性。在变化的不确定因素对所考虑的问题影响很大的时候，经典的优化方法有：一是将可变化的因素随机化，寻求平均意义上的最优方案，二是考虑可变化因素的最坏情形，寻求最坏情形达到最优的方案。这两种处理方法对变化因素的一个特例都可能给出离实际最优解相距甚远的解，这显然是难以满足实际的要求的。那么是否存在一种方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内呢？ 近年来兴起的局内问题与竞争算法的研究结果在一定意义上给如上问题一个肯定的答案。其实本文所提出的逆向标号算法就是对应局内最短路问题的一个竞争算法，从本质上来说它是一种贪婪算法，在不知将来情况的条件下，求出当前状态下的最优解。[1]本文所考虑问题的实际背景是一个物流配送公司对其运输车辆的调度。假设物流公司需要用货车把货物从初始点O(Origin)运送到目的点D(Destination)。从日常来看，物流公司完全可以通过将整个城市交通网络看成一个平面图来进行运算，找到一条从O到D的最短路径以减少运输费用和节省运输时间。现考虑如下一个问题：如果当运输车辆沿着最短路径行驶到最短路径上的一点A，发现前方路径上的B点由于车辆拥塞而不能通过，车辆必须改道行驶，而此时物流配送公司应如何应对来保证其花费最低。问题推展开去，如果不是单个堵塞点，而是一个堵塞点序列，那物流配送公司又将如何来设计其最短路算法来在最短的时间内求出已知条件发生变化后的最优路径，从而有效的调度其运输车。本文首先建立了物流配送公司动态最短路的数学模型，相比较给出了求本文所提出的动态最短路问题的传统算法和作者提出的逆向标号算法，并分析了各自的算法复杂度。 二、数学模型假设城市交通网络是一个平面图，记为G，各个交通路口对应于图G上的各个顶点，令G=(G，V)为一边加权无向图，其中V为顶点的集合，E为边的集合，|G|=n，对于一般平面图上的三点之间，一定满足三角不等式，即任意三角形的两边之和一定不小于另外一边。对于本文要讨论的城市交通网络来说，即，任意三个结点之间的距离一定满足三角不等式。我们用O来表示运输的起始点，D表示运输的目的点。SP表示在没有路口堵塞情况下的最短路径，W(SP)表示沿着最短路径所要花费的运输费用。以下的讨论都是基于如下的基本假设：第一，去掉堵塞点后图G仍是连通的。第二，只有当运输车走到前一点后，才能发现后面的一点发生堵塞而不能通过。 三、算法分析 对于本文的上述问题，有两种算法一(传统算法)和二(逆向标号算法)可以满足要求，但两种算法在求动态最短路的过程中都将会用到Dijkstra算法[2]，通过对Dijkstra算法的分析我们知道，Dijkstra算法采用了两个集合这样的数据结构来安排图的顶点，集合S表示已 !""#$%%%&%%’( )#$$&***+,#清华大学学报-自然科学版. /012345678329-":2;0<:5.= *%%>年第(>卷第$$期 *%%>=?@A B(>=#@B$$ +C,+C $C(’&$C(D 车辆路径优化问题的均衡性 但正刚=蔡临宁=杜丽丽=郑力 -清华大学工业工程系=北京$%%%D(. 收稿日期E*%%’&%>&%F 基金项目E国家自然科学基金资助项目-F%*%$%%D. 作者简介E但正刚-$C F D&.=男-汉.=重庆=博士研究生G 通讯联系人E蔡临宁=副教授=H&I72A E:72A3J K1234567B 车辆路径问题(vehideRoutingProblem，vRP)是组合优化和运筹学领域研究 的热点问题之一，其主要研究满足约束条件的最优车辆使用方案以及最优的车辆路径方案。基于基本车辆路径问题的框架，研究满足生产经营和运作需要的各种车辆路径问题，并构建具有高质量和高鲁棒性(roubustuess)的问题求解算法对于提高生产经营管理水平和降低运作成木具有重要的理论意义和现实价值。 本文以车辆路径问题为研究对象，综合运用组合优化和现代启发式算法等工 具，对几类重要的车辆路径问题模型及其优化算法进行了系统的研究，主要研究工作及成果总结如下: 1.综述了车辆路径问题在定义车辆路径问题分类和扩展标准的基础上，给出了 车辆路径问题的研究综述。基于不同的分类标准，首先讨论了主要的标准车辆 路径问题扩展问题。在此基础上详细地综述了求解标准车辆路径问题的现代启 发式算法，系统地描述了各种算法的实现机理以及各种算法的性能比较结果。 2.综述了求解组合优化问题的现代启发式算法在给出组合优化问题和计算复杂 性定义的基础上，综述了求解复杂组合优化问题的各种现代启发式算法。 3.研究了开放式车辆路径问题通过松弛标准车辆路径问题中车辆路线为哈 密尔顿巡回(Hamiltoniantour)的假设，研究了车辆路线为哈密尔顿路径(Hamiltonianpath)的开放式车辆路径问题。该问题中车辆在服务完最后一个 顾客点后不需要回到车场，若要求回到车场，则必须沿原路返回。在首先给出 问题数学模型的基础上，提出了求解开放式车辆路径问题的蚁群优化算法。该 算法主体是一个在超立方框架下执行的侧只刃一侧工加尸蚂蚁系统，算法混合了禁忌搜索算法作为局部优化算法，同时集成了一个后优化过程来进一步优化最优解。基于基准测试问题，系统地研究了算法性能。同其它算法的性能比较结果 表明本文提出的蚁群优化算法是有效的求解开放式车辆路径问题的方法。 4.研究了带时间窗和带时间期限开放式车辆路径问题通过引入时间约束，研究 了两类新的满足时效性要求的开放式车辆路径问题—带时间窗和带时间期 限开放式车辆路径问题。首先构建了两类问题的数学模型，同时提出了求解两 上海交通大学博十学位论文 类问题的基于禁忌搜索的迭代局部搜索算法，该算法集成了不同的解接受标准 以及一个基于阂值接受的后优化过程。基于随机产生的测试问题的实验结果表明:基于禁忌搜索的迭代局部搜索算法可以有效地求解带时间窗和带时间期限 开放式车辆路径问题。 5.研究了带时间窗和随机旅行时间车辆路径问题通过对标准车辆路径问题的拓 展，引入新的边约束条件:时间窗、随机旅行时间和服务时间，研究了一类新 的随机车辆路径问题—带时IbJ窗和随机旅行时间车辆路径问题。根据不同 的优化标准，分别构建了问题的机会约束规划模型以及带修正随机规划模型。 机会约束规划模型是在随机约束以一定的置信水平成立的条件下最小化运输费用。带修正的随机规划模型是一个两阶段优化问题，其确定第一阶段的路线集 以最小化第二阶段(随机变量实现后)的期望运输费用。鉴于问题的随机特 性，为了有效求解该问题提出了基于随机模拟的禁忌搜索算法。同时基于随机 产生的测试问题通过实验检验了算法有效性。 6.研究了固定车辆数异型车辆路径问题在车辆路径问题经典文献中，一般均假 设车辆同质目‘车辆数无限。然而在实际运作中，车辆集一般是由具有不同属性(装载能力、固定成本以及单位公里可变费用)的车辆组成，且受运作成本的 》本文对在GIS（地理信息系统）环境下求解动态路径优化算法及相关技术 进行了研究。最短路径问题是网络分析中的基本的问题，它作为许多领域中选择 最优值的一个基本却又是一个十分重要的问题。特别是在交通诱导系统中占有重 要地位。本文分析了GIS环境下动态路径优化算法的特点，对GIS环境下城市 路网的最优路径选择问题的关键技术进行了研究和验证。 》考虑现实世界中随着城市路网规模的日益增大和复杂程度不断增加的情况，充分利用GIS 的特点，探讨了通过限制搜索区域求解最短路径的策略，大大减少了搜索的时间。 》另一方面，计算机技术的进步，地理信息系统(GIS)得到了飞速的发展。地理信息系统是采集、存储、管理、检索、分析和描述整个或部分地球表面与空间地理分布数据的空间信息系统。它是一种能把图形管理系统和数据管理系统有机地结合起来的信息技术，既管理对象的位置又管理对象的其它属性，而且位置和其它属性是自动关联的。它最基本的功能是将分散收集到的各种空间、非空间信息输入到计算机中，建立起有相互联系的数据库。当外界情况发生变化时，只要更改局部的数据，就可维持数据库的有效性和现实性[3][4]，GIS为动态路径优化问题的研究提供了良好的环境。目前GIS带动的产业急剧膨胀，已经应用到各个方面。网络分析作为地理信息系统最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用[5]。文献[6][7]说明了GIS 在城市道路网中的应用情况。而路网分析中基本问题之一是动态路径优化问题。所谓动态路径，不仅仅指一般地理意义上的距离最短，还可以应用到其他的参数，如时间、费用、流量等。相应的，动态路径问题就成为最快路径问题、最低费用问题等。 》GIS因为其强大的数据分析功能、空间分析功能,已被广泛应用于各种系统中与空间信息有密切关系的各个方面.各种在实际中的系统如电力系统，光缆系统涉及到最佳、最短抢修等问题都可以折合到交通网络中来进行分析，故而交通网络中最短路径算法就可以广泛的应用于其它很多的最佳、最短抢修或者报警系统中去[5]。最短路径问题是GIS网络分析功能的应用。最短路径问题可分为单源最短路径问题及所有节点间最短路径问题，其中单源最短路径更具有普遍意义[9]。 》2.1地理信息系统的概念 地理信息系统（Geographical Information System,简称GIS）是一种将空间位置信息和属性数据结合在一起的系统，是一种为了获取、存储、检索、分析和显示空间定位数据而建立的计算机化的数据库管理系统（1998年，美国国家地理信息与分析中心定义）[4]。这里的空间定位数据是指采用不同方式的遥感和非遥感手段所获得的数据，它有多种数据类型，包括地图、遥感、统计数据等，它们的共同特点都有确定的空间位置。地理信息系统的处理对象是空间实体，其处理过程正是依据空间实体的空间位置和空间关系进行的[25]。地理信息系统的外在表现为计算机软硬件系统，其内涵却是由计算机程序和地理数据组织而成的地理空间信息模型。当具有一定地理学知识的用户使用地理空间分析非空间分析等处理工具输入输出GIS数据库信息系统时，他所面对的数据不再是毫无意义的，而是把客观世界抽象为模型化的空间数据。用户可以按照应用的目的观测这个现实世界模型的各个方面的内容，取得自然过程的分析和预测的信息，用于管理和决策，这就是地理信息系统的意义。一个逻辑缩小的、高度信息化的地理系统，从视觉、计量和逻辑上对地理系统在功能上进行模拟，信息流动以及信息流动的结果，完全由计算机程序的运行和数据的变换来仿真。地理学家可以在地理信息系统支持下提取地理系统各个不同侧面、不同层次的空间和时间特征，也可以快速地模拟自然过程演变成思维过程的结果，取得地理预测或“实验”的结果，选择优化方案，用于管理与决策[26]。 一个完整的GIS主要有四个部分构成，即计算机硬件系统、计算机软件系统、地理数据（或空间数据）和系统管理操作人员。其核心部分是计算机系统（硬件和软件），地理数据反映 一、车辆路径问题描述和建模 1. 车辆路径问题 车辆路径问题（Vehicle Routing Problem, VRP ）,主要研究满足约束条件的最优车辆使用方案以及最优化车辆路径方案。 定义：设G={V,E}是一个完备的无向图，其中V={0,1,2…n}为节点集，其中0表示车场。V ,={1,2,…n}表示顾客点集。A={(i,j),I,j ∈V,i ≠j}为边集。一对具有相同装载能力Q 的车辆从车场点对顾客点进行配送服务。每个顾客点有一个固定的需求q i 和固定的服务时间δi 。每条边（i,j ）赋有一个权重，表示旅行距离或者旅行费用c ij 。 标准车辆路径问题的优化目标为：确定一个具有最小车辆数和对应的最小旅行距离或者费用的路线集，其满足下列约束条件： ⑴每一条车辆路线开始于车场点，并且于车场点约束； ⑵每个顾客点仅能被一辆车服务一次 ⑶每一条车辆路线总的顾客点的需求不超过车辆的装载能力Q ⑷每一条车辆路线满足一定的边约束，比如持续时间约束和时间窗约束等。 2.标准车辆路径的数学模型: 对于车辆路径问题定义如下的符号： c ij ：表示顾客点或者顾客点和车场之间的旅行费用等 d ij ：车辆路径问题中，两个节点间的空间距离。 Q ：车辆的最大装载能力 d i ：顾客点i 的需求。 δi ：顾客点i 的车辆服务时间 m:服务车辆数，标准车辆路径问题中假设所有的车辆都是同型的。 R ：车辆集，R={1,2….，m} R i :车辆路线，R i ={0，i 1,…i m ,0},i 1,…i m ?V ,,i ?R 。 一般车辆路径问题具有层次目标函数，最小化车辆数和最小化车辆旅行费用，在文献中一般以车辆数作为首要优化目标函数，在此基础上使得对应的车辆旅行费用最小，下面给出标准车辆路径问题的数学模型。 下面给出标准车辆路径问题的数学模型。 对于每一条弧（I,j ）,定义如下变量: x ijv = 1 若车辆v 从顾客i 行驶到顾客点j 0 否则 y iv = 1 顾客点i 的需求由车辆v 来完成0 否则 车辆路径问题的数学模型可以表述为： minF x =M x 0iv m i=1n i=1+ x ijv m v=1n j=0n i=0.c ij (2.1) x ijv n i=0m v=1≥1 ?j ∈V , (2.2) 系 统 管理学报 第１９卷 不同，文献［６］中１００，本文３０；③文献［６］中没有给出２０次求解中有多少次求得最优解，本文算法在软硬２种时间窗下，求得最优解的概率分别为９０％和７５％。由此可以看出本文算法具有较快的收敛速度和较高的稳定性。 表２实例ｌ。软时间窗下算法运行结果 第２个实例［６］，该问题有８个客户，顾客的装货或卸货的时间为Ｔｉ，一般将ｔ作为车辆的行驶时间的一部分计算费用，ｇｆ和［ｎ，，６ｉ］的含义同前，具体数据见表４。这些任务由仓库发出的容量为８ｔ的车辆来完成，车辆行驶速度为５０，仓库以及各个顾客之间的距离见表５。 ６），达到最优解的概率为８０％，其最终结果与文献［６］中相同最优解其费用值为９１０，对应的子路径 为（Ｏ一３一ｌ一２—０）、（Ｏ一６—４一Ｏ）、（Ｏ一８—５—７一Ｏ）。然而，文献 ［６］是在ｍａｘｇｅｎ＝５０、ｐｏｐｓｉｚｅ一２０的情况下，达到最优解的概率为６７％。这又说明了本文算法的有 效性。 表６实例２的算法运行结果 ４ 结语 尽管用带有子路径分隔符的自然数编码作为遗传算法解决ＶＲＰＴＷ问题的编码方式有其优点，但缺陷也是显而易见的，为了弥补该缺陷，本文去掉了 子路径中的分隔符，并采用Ｓｐｌｉｔ作为解码方式，就此设计了求解ＶＲＰＴＷ的遗传算法，并进行了数值试验的对比分析，试验结果表明，该算法是十分有 效的。参考文献 ＤａｎｔｚｉｑＧ，Ｒａｍｓｅｒ Ｊ．Ｔｈｅｔｒｕｃｋｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍ ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ ｓｃｉｅｎｃｅ，１９５９，１３（６）８０一９１． 谢秉磊，李军，郭耀煌．有时间窗的非满载车辆调 度问题的遗传算法［Ｊ］．系统工程学报，２０００，１５ （３）２９０一２９４． 宋伟刚，张宏霞，佟玲．有时间窗约束非满载车辆调度问题的遗传算法［Ｊ］．系统仿真学报，２００５，１７ （１１）２５９３—２５９７． 刘诚，陈治亚，封全喜．带软时间窗物流配送车辆路径问题的并行遗传算法 ????????? ?仈?ウ?? ??????????? ?仈а? ?? 亶 ??ウ???а? ???? ?仈? ?? ? ? ?? 学?仈 ??????ウ? ? ? ??? ?? ??????????? ?仈??? ?????? The Current Situation and Development Trends on Vehicle Routing Problems of distribution management Abstract: Vehicle routing problem is one of the attractive research area in the circles of operations research. In this paper, on the basis of introducing briefly the application background, the research classified the vehicle routing problem, analyzed and summarized the progress of different type of problems and solution algorithms. Furthermore, the research progress of the problems is also discussed. It is expected to provide inference for relevant research work. Key words: distribution management; vehicle routing problem; heuristics; overview. 摘要 供货小车的路径优化是企业降低成本,提高经济效益的有效手段,供货小车路径优化问题可以看成是一类车辆路径优化问题。 本文对供货小车路径优化问题进行研究，提出了一种解决带单行道约束的车辆路径优化问题的方法。首先，建立了供货小车路径优化问题的数学模型，介绍了图论中最短路径的算法—Floyd算法，并考虑单行道的约束，利用该算法求得任意两点间最短距离以及到达路径，从而将问题转化为TSP问题，利用遗传算法得到带单行道约束下的优化送货路线，并且以柳州市某区域道路为实验，然后仿真，结果表明该方法能得到较好的优化效果。最后对基本遗传算法采用优先策略进行改进，再对同一个供货小车路径网进行实验仿真，分析仿真结果，表明改进遗传算法比基本遗传算法能比较快地得到令人满意的优化效果。 关键字:路径优化遗传算法 Floyd算法 Abstract The Path Optimization of Goods Supply Car is the effective way to reduce business costs and enhance economic efficiency.The problem of the Path Optimization of Goods Supply Car can be seen as Vehicle routing proble. This paper presents a solution to Vehicle routing proble with Single direction road by Researching the Way of Path Optimization of Goods Supply Car. First, This paper Establish the mathematics model of Vehicle routing proble and introduced the shortest path algorithm-Floyd algorithm, then taking the Single direction road into account at the same time. Seeking the shortest distance between any two points and landing path by this algorithm,then turn this problem in to TSP. Solving this problem can get the Optimize delivery routes which with Single direction road by GA,then take some district in the state City of LiuZhou road as an example start experiment.The Imitate the true result showed that this method can be better optimize results. Finally improving the basic GA with a priority strategy,then proceed to imitate the true experiment to the same Path diagram. The result expresses the improvement the heredity calculate way ratio the basic heredity calculate way can get quickly give satisfaction of excellent turn the result. Keyword: Path Optimization genetic algorithm Floyd algorithm 粒子群优化算法 计算车辆路径问题 摘要 粒子群优化算法中,粒子群由多个粒子组成,每个粒子的位置代表优化问题在D 维搜索空间中潜在的解。根据各自的位置,每个粒子用一个速度来决定其飞行的方向和距离,然后通过优化函数计算出一个适应度函数值(fitness)。粒子是根据如下三条原则来更新自身的状态:(1)在飞行过程中始终保持自身的惯性;(2)按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题 由Dan tzig 和Ram ser 于1959年首次提出的, 它是指对一系列发货点(或收货点) , 组成适当的行车路径, 使车辆有序地通过它们, 在满足一定约束条件的情况下, 达到一定的目标(诸如路程最短、费用最小, 耗费时间尽量少等) , 属于完全N P 问题, 在运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法, 有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO 应用于车辆路径问题求解中, 取得了很好的效果。 针对本题，一个中心仓库、7个需求点、中心有3辆车，容量均为1，由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。 1233,1,7. k q q q l =====货物需求 量12345670.89,0.14,0.28,0.33,0.21,0.41,0.57g g g g g g g =======， 且 m a x i k g q ≤。利用matlab 编程，求出需求点和中心仓库、需求点之间的各 个距离，用ij c 表示。求满足需求的最小的车辆行驶路径，就是求 m i n i j i j k i j k Z c x = ∑∑∑ 。经过初始化粒子群，将初始的适应值作为每个粒子的个 ——第6届全国青年管理科学与系统科学学术会议论文集 2001年·大连 437 物流系统优化中的定位—运输路线安排问题 （ＬＲＰ）研究评述* 林岩 胡祥培** （大连理工大学系统工程研究所, 116023） 摘要 本文概述了物流优化问题中的定位—运输路线安排问题 （Location-Routing Problems, LRP ）的发展历程，并对LRP 的分类和解决方 法加以评述，最后就这一问题的发展方向进行简单地探讨。 关键词 LRP 物流 系统优化 运筹学 1 引言 新技术的迅速发展，特别是电子商务的风起云涌，为我国经济的快速发展提供了契机。目前我国电子商务得到政府和民众的支持，发展势头强劲，但是，由于它是一套全新的技术，同时还是一种全新的管理理念，所以其发展过程中必然存在一些难题。在电子商务“三流”（信息流、物流、资金流）中，随着网络基础设施建设的成熟、电子商务网站的蓬勃发展以及有效利用网络资源观念的普及，信息流的发展已经比较成熟了；而随着各大银行纷纷开展网上业务，以及支付网关的建立和加密技术的成熟，网上支付已经在许多网站上成为现实；然而，我国传统的物流体系是在计划经济环境下建立、发展起来的，与目前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社会经济快速发展的重要制约因素之 一。所以对物流系统优化的研究将会具有很大的现实意义。 国外许多学者在电子商务出现之前就已经研究物流系统优化的问题了，为各类实际问题构建了优化模型，并形成了许多解决问题的算法。依据实际问题的不同，可以对物流系统优化问题进行分类，比如，运输车辆路线安排问题（VRP ）、定位—配给问题（LA ）、定位—运输路线安排问题（LRP ）等等，其中LRP 更贴近目前的物流系统复杂的实际特征，所以对它的研究是十分有意义的。 本文先从VRP 和LA 的集成来探讨LRP 的由来，然后讨论LRP 的分类，同时探讨LRP 的研究现状，并对LRP 的解决方法进行概述，最后就LRP 的未来发展方向作简要的讨论。 2 从VRP 、LA 到LRP ——物流系统的集成 依据实际问题的不同，可以对物流系统优化问题进行分类，比如确定设施（指的是物品流动的出发点和终到点，如配送中心、仓库、生产工厂、垃圾回收中心等）位置、运输路线 * 国家自然科学基金重点项目(70031020) ** 林岩, 硕士研究生, 1972年出生, 主要研究方向: 电子商务, 信息系统工程。 胡祥培, 1962年出生, 教授,博导, 主要研究方向: 电子商务, 智能运筹学, 信息系统集成。 物流配送的车辆路径优化 专业：[物流管理] 班级：[物流管理2班] 学生姓名：[江东杰] 指导教师：[黄颖] 完成时间：2016年6月30日 背景描述 物流作为“第三利润源泉”对经济活动的影响日益明显，越累越受到人们的重视，成为当前最重要的竞争领域。近年来，现代物流业呈稳步增长态势，欧洲、美国、日本成为当前全球范围内的重要物流基地。中国物流行业起步较晚，随着国民经济的飞速发展，物流业的市场需求持续扩大。特别是进入21世纪以来，在国家宏观调控政策的影响下，中国物流行业保持较快的增长速度，物流体系不断完善，正在实现传统物流业向现代物流业的转变。现代物流业的发展对促进产业结构调整、转变经济增长方式和增强国民经济竞争力等方面都具有重要意义。 配送作为物流系统的核心功能，直接与消费这相关联，配送功能完成质量的好坏及其达到的服务水平直接影响企业物流成本及客户对整个物流服务的满意程度。配送的核心部分是配送车辆的集货、货物分拣及送货过程，其中，车辆配送线路的合理优化对整个物流运输速度、成本、效益影响至关重要。 物流配送的车辆调度发展现状 VRP（车辆调度问题）是指对一系列装货点和卸货点，组织适当的行车线路，使车辆有序的通过，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量等限制）下，达到一定的目标（如路程最短、费用最少、时间最少、使用车辆数最少等）。一般认为，不涉及时间的是路径问题，涉及时间的是调度问题。VRP示意图如下 当然，VRP并不止是这样的一个小范围，而是又更多的客户点与一个仓库链接，从而达 到一整个物流集群。 根据路径规划前调度员对相关信息是否已知，VRP可分为静态VRP和动态VRP，动态VRP 是相对于静态VRP而言的。静态VRP指的是：假设在优化调度指令执行之前，调度中心已经知道所有与优化调度相关的信息，这些信息与时间变化无关。一旦调度开始，便认为这些信息不再改变。 而VRP发展到现在的问题也是非常突出的，例如，只有一单货物，配送成本远高于一单的客户所给的运费，在这种情况下，该如何调度车辆？甚至还有回程运输的空载问题，在这些问题之中，或多或少都涉及到了VRP的身影，那么在这样的配送中怎么有效的解决车辆的路径优化问题就是降低运输和物流成本的关键所在。 解决怎么样的问题？ 现如今对于VRP研究现状主要有三种静态VRP的研究、动态VRP的研究以及随机VRP的研究。 而我对于VRP的看法主要有以下几点。 有效解决VRP或者优化车辆调度路径优化问题，那么将非常有效的降低物流环节对于成本的比重，有效的增大利润。 而我想到的方法，就是归类总结法。 建立完善的信息系统机制，将订单归类总结出来，可以按地区划分出来，一个地区一个地方的进行统一配送，这样也有效的降低了物流配送的车辆再使用问题，降低了成本。如下图所示。 仓库 客户 变换前 由上图可以看出来这样的路径，车辆需要来回两次，严重增加了配送成本，也增加了运输成本，使得利润并不能最大化。 摘要：作为现代物流领域的研究前沿，车辆路径问题的求解算法及应用领域一直是学者研究的重点。本文在研读大量文献的基础上介绍了遗传算法的研究现状及其应用情况，并对车辆路径优化在生鲜农产品配送上的应用进行了简单的综述。 关键词：车辆路径问题；遗传算法；生鲜农场品；研究综述 一、引言 车辆路径问题最早在60年代被提出，dantzig和ramser首次在交通领域提出该问题就立即引起了社会的广泛关注。发展到现如今，车辆路径问题的应用已经跳出了交通领域，在别的很多领域被使用，如：通讯、工业管理、航空等。 二、遗传算法 1.遗传算法简介 达尔文的生物进化论自被提出以来就一直被科学家们广泛应用到各个领域。60年代时美国科学家结合进化论，提出了遗传算法。跟大自然中生物优胜劣汰的进化过程类似，遗传算法在计算过程中模拟了自然界各种群由简单到复杂，由低级到高级的进化过程，不断进化种群，直至使种群达到包含最优解或接近最优解的状态。 2.遗传算法研究现状 遗传算法作为一种群体随机搜索方法，在车辆路径问题研究中运用很多。很多国内外的研究学者对基础的遗传算法进行了改良，以期达到求解不同约束条件下车辆路径优化问题的目的。通过研究撰写遗传算法的文献发现，研究学者们分别用各种改进遗传算法对车辆路径问题进行了求解，如：免疫遗传算法、小生境遗传算法，以及遗传算法与爬山算法、禁忌搜索算法、蚁群算法相结合的混合算法。 将基础的遗传算法与改进的遗传算法进行对比仿真实验，可以发现经过改良的遗传算法，其各方面能力都更优。罗勇等为了求解更优的物流配送路线，就采用了针对性改进的遗传算法。通过研究发现，改良后的算法不仅收敛速度变快，而且全方位寻优的能力也有很大提高。由此可见改进的遗传算法是能更好的处理物流配送路径问题。基础的遗传算法有容易陷入局部最优和早熟的缺点，为了解决这个问题，周艳聪等设计了基于小生境技术的改进遗传算法，还在改进的遗传算法的基础上求解了物流配送路径的优化问题。不仅如此，还通过对物流配送过程的研究，建立了不带时间窗约束的物流配送优化模型。大规模车场的车辆路径问题是车辆路径优化问题中的一个难点，一直是学者们研究的重点。李波等引入了双层模糊聚类方法，针对基础的遗传算法进行了改进，得到了求解该问题的基本框架。通过随机的实验算例证明，所提出的方法是有效可行的。 三、车辆路径问题在生鲜农产品配送中的应用 对近年来，针对生鲜农产品配送路径问题的研究已经越来越多，人们对绿色食品的质量要求不断提高，是导致该问题备受关注的根本原因。容易腐烂变质，存放不易是大多数生鲜农产品的特点。而在整个销售过程中，生鲜农产品需要经历从农户手中到经销商手中这样一个配送过程，尽可能在配送过程中选择合适的路径，节约时间，保证生鲜农产品的质量，从而保证农户、经销商、消费者的利益就变得越来越重要。 为了保证生鲜农产品的质量、安全，生鲜农产品配送过程中的时效性一直是各个学者研究的关注点，大多数相关文献的模型建立都是以配送时间最短和配送成本最低为目标。王红玲等学者的研究考虑了生鲜农产品的特点构建了以生鲜农产品在途时间最短、配送成本最低为优化目标的农产品配送模型，并采用经过改进后的粒子群算法进行求解。由于生鲜农产品的时效性强的特点，对带时间窗的车辆路径问题的研究也相当多。邱荣祖等在分析了农产品的物流配送模式的基础上，建立了有时限的物流配送路径优化模型，并应用gis于禁忌搜索算法集成技术进行求解。文献中还选用了具体的数据进行了实验的验证，进行了初步的应用 用ACO 算法求解机器人路径优化问题 4.1 问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 4.2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士在文献[30]中给出改进模型（ACS），文中 改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。 蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图 2-1 所示，AE 之间有 物流车辆路径算法的优化与设计 【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50％左右，所以降低物流成本首先要从降低物流配送的运输成本开始。 一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化，这正是本文要研究的课题。 【关键词】：物流配送；路径；车辆路径问题(VRP)；MATLAB 1 前言 1.1 课题研究背景 运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从1959年Danting和Rams er提出车辆路径问题(Vehicle Routing Problem，VRP)以来，VRP便成为近年来物流领域中的研究热点。 VRP一般定义为：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。本文围绕VRP展开了研究，共包括五章内容。首先，本文收集国内外关于物流配送中几种路径优化算法
物流配送管理中路径优化问题分析
车辆路径优化问题的均衡性
车辆路径问题
动态路径优化算法及相关技术
车辆路径问题
时间窗车辆路径问题【带有时间窗约束的车辆路径问题的一种改进遗传算法】
配送运输中车辆路径问题研究综述
路径优化的算法
粒子群优化算法车辆路径问题
物流系统优化——定位——运输路线安排问题LRP研究评述
物流配送的车辆路径优化
车辆路径问题研究综述
matlab_蚁群算法_机器人路径优化问题
《物流车辆路径算法的优化与设计》
相关主题
文本预览