（系统工程专业论文）车辆路径问题的建模及优化算法研究.pdf

西北工业大学博上学位论文车辆路径问题矬摸0 优化算法研究 摘要 智能交通系统作为基于现代科学技术建立起来的，一种在大范围内全方位 发挥作用的，准时、准确、高效的交通运输管理体系，受到各国的普遍重视。 全球经济的一体化。也正推动着被称为是企业“第三利润源”一现代物流业 的快速发展。车辆路径问题作为智能交通系统中的重要内容，在现代物流中占 据着很重要位置。虽然经过几十年研究，取得了不少的成果，但由于该问题的 复杂性，目前还存在许多需要进一步加强研究的问题。随着计算技术和优化方 法以及信息和通信技术的发展，过去解决不够完善的或没能解决的问题，可以 借助现代科技的力量，将其进一步完善或解决。本文针对目前车辆路径问题的 现状，利用系统工程理论和最新的优化方法，对存在的问题进行建模和优化算 法研究，具有重要的理论意义和实用价值。论文主要做了以下几方面工作： 1 、针对带时间窗有限车辆路径问题，设计了一种混合遗传禁忌算法。在描 述问题和建立模型的基础上，首先，因染色体中仅有部分基因起作用，为充分 利用染色体包含的信息，提出采用b e l l m a l l f o r d 最短路算法，找到它最佳的分 割方法。其次，利用禁忌搜索法改善因遗传算法变异概率小，带来局部搜索能 力低的问题。另外，对禁忌搜索法又进行设计，通过在目标函数中添加惩罚项， 使搜索在可行和不可行交界区域自j 动态调整，既使搜索不偏离最优解太远，又 丰富了搜索区域，提高获得更优解的概率。最后，将解与已知的最优解进行对 比，并分析参数对解的影响。 2 、针对大规模单车型带软时间窗车辆路径问题，设计了一种基于大系统分 解协调技术新的解决方法。在对问题进行了描述并给出它的模型后，首先，运 用动态聚类法，基于每辆车的位置坐标对车辆聚类，得到分类车辆的中心坐标； 再根据每个任务到分类车辆中心的距离，对任务进行分类。其次，针对采用传 统分解协调法解决该问题，收敛性能比较差的问题，设计了有效的协调参数， 并在主子系统中，分别设计了不同的自适应遗传算法。通过仿真试验，证实了 该算法的有效性。 针对大规模多车型带软时间窗车辆路径问题，设计了一个有效的禁忌搜索 算法。在给出了问题描述并建立了它的模型后，首先，提出采用候选表策略， 通过它舍弃大部分没有希望的移动，且随着搜索过程的进展，动态地调整与搜 索邻域有关候选表的大小，提供了一个简单的实施集中性援索和分散住搜索的 摘耍 方法。其次，采用动态摆动策略，控制它集中在可行和不可行空问交界区域搜 索。仿真试验结果证实了所设计禁忌搜索算法的有效性。 3 、对多库房带时日j 窗车辆路径问题，在分析几个经典的多库房位置模型后， 对该问题进行了描述并构建了它的模型。针对目前解决多库房车辆路径问题， 效率低且易陷于局部最优解的问题，提出一种采用分解协调技术解决该问题的 新方法。首先，根据启发式方法，将用户分解为耦合和非耦合用户。其次，利 用遗传算法设计了协调参数，并设计了禁忌搜索算法，有效地解决各库房的车 辆路径问题。最后，通过仿真试验，对它的有效性进行了验证。 对多库房随机需求车辆路径问题，在描述该问题以及分析了有关模型的基础 上，建立了它的数学模型。基于分解协调技术，在协调层，利用自适应遗传算 法确定耦合用户的最佳分解方式；在执行层，对解决子系统的随机需求车辆路 径问题，基于预防性补救措旃，设计了自适应交叉熵法。最后，通过对不同算 法仿真结果比较，验证了所设计方法的有效性。 4 、在分析了几种解决随机需求车辆路径问题典型方法后，提出了一种基于 交义熵，结合重要抽样、m o n t c c a r l o 及m a r k o v 状态转移技术，解决更复杂的 随机_ f | j 户艰i 需求车辆路径闯题新方法。在对该问题进行了描述，并建立模型后， 旨先，针对路径期望费用函数的复杂性，设计了基于m o n t e c a r i o 抽样求解的有 效方法。其次，为提高标准交叉熵法性能，根据迭代过程中分位值改变大小， 对用于更新转移矩阵关键的路径，设计了自适应调整方法。最后，利用仿真试 验，验证了所设计交叉熵法的鲁棒性和有效性。 5 、在分析了随机最短路问题的基础上，对动态随机需求车辆路径问题进行 了掐述，并建立它的最优策略模型。针对状态空问“维数灾”问题，基于增强 学习函数近似原理，利用径向基函数网络逼近最优c o s t t o g o 函数。首先，对径 向基函数进行分析和设计，其次，在一给定的控制策略下，将最小平方瞬时差 分法确定近似函数权系数与交叉熵法确定隐层节点基函数参数相结合，透过在 线调整。使b e l l m a n 残差平方和性能指标达到最小，以实现对最优c o s t - t o 9 0 函 数的逼近。通过仿真试验，证实了此算法的有效性。 关键词：车辆路径b e 【i m a n f o r d 最短路动态聚类分勰协调法 遗传算法禁忌搜索交叉熵m a r k o v 决策径向基函数 i i 西北1 = 业人学博l 学位论文 车辆路杼问题的建模与优化尊法研究 a b s t r a c t i n t e l l i g e n tt r a n s p o f t a t i o ns y s t e ma c t s a sat i m e l y ，a c c u r a t ea n dh i g he f f i c i e n t t 瑚s p o r t a t i o nm a n a g e m e n ts y s t e mw h i c hi sb a s e do nm o d e ms c i e n c ea 1 1 dt e c l l i l o l o g y 趴dh a sg r e a ti n n u e n c eo nal a r g es c a l ei nm a n yf i e l d s t h eg l o b a le c o n o m i c i n t e g m t i o ni sp r o m o t i n gt h ed e v e l o p m e n to fm o d e ml o g i s t i cw h i c h i sc a l l e dt h et h i r d p r o f i ts o u f c eo fe n t e r p “s e s v 曲i c l er o u t i n gp r o b l e m sa st h ei m p o r t a j l tc o n t e n to f i n t c l l i g e n tt r a n s p o n a t i o ns y s t e mp l a ya ni m p o n a i l tm l ei nm o d e ml o g i s t i c 1 1 l o u g hi t h a sa c q u i r e da1 0 to fr e s e a r c ha c h i e v e m e n t sf o rd e c a d e s ，d u et oi t sc o m p l e x i 吼t h e r c a r en o wm a n yp r o b i e m sn e e d e dt ob ei n v e s t i g a t e d w i t ht h ed e v e l o p m e n to fc o m p u t e t e c h n o i o g ya 1 1 do p t i m i z a t i o na l g o r i t h m ，酗w e l la si 1 1 f o 姗a t i o na n dc o m m u n i c a t i o n t e c h n o l o g y t h ep r o b l e m st h a t 、犏r ei m p e r f c c to ru n s o l v e di nt h ep a s tc a n b ei m p m v e d o r b es o l v e db ym e a n so ft h ep o w e ro fm o d e ms c i e n c ea n dt e c h n o l o g y c o n s i d e r i n g t h es t a t u so fv e h i c l er o u t i n gp r o b l e m sn o wa n du s i n gt h es y s t e m se n g i n e e r i n gt h e o r y a n dn e w l yo p t i m i z a t i o n a 1 9 0 r i t h m ， t h i sd i s s e r t a t i o nb u i l d e st h em o d e l sa n d i n v c s t i g a t e st h eo p “m i z i n gm e t h o d sf o rt h ci m p e r f e c t0 ru r i s o l v e dp m b l c m s ，肌dh a s t h e o r c t i c a ls i g n m c a i l c ea n dp 糟c t i c a iv a l u e t h em o s td i s t i n c t i v ep a r t so ft h i s d i s s e r t a t i o nc a nb el i s t e di nt h ef o i l o w i n ga s p e c t s ： l 、f o rt h ev e h i c l er o u t i n gp r o b l e m s 谢t h 、i n d o w sa j l da1 i m i t e dn u m b e ro f v e h i c l e s ，a h y b r dg e n e t i ca n dt a b us e a r c ha l g o r i t h mi sp r o p o s e d o nt h eb a s i so ft h ep r o b l e m d e s c “p t i o na n dm o d e le s t a b l i s h m e n t ，f i r s t l y ，鹪o n l yp a n so fg e n e si nac 1 1 r o m o s o m e a r eu s e d ，i no r d e rt 0m a k ef u l ll l s eo f t h ec h r o m o s o m e ，t h eb e l l m a n _ f o r ds h o r t e s tp a t h a l g o r i t h mi sa d o p t e dt o f i n dt h eb e s ts o l u t i o nt h a tt h ec h r o m o s o m es t “n gc a n r c p r e s e n f s e c o n d ly ，l a b us e a r c hi su t j 】i z e dt oi m p r o v et h ec a p a b i j j i yo fl o c a ls e a r c ho f g e n e t i ca l g o r i t h m ，、v ! h i c hi sc a u s e dd u et os m a l l e rm u t a t i o np r o b a b i l i t i e s m o r c o v e r t a b us e a r c hi sd e s i g n e db ya d d i n gp u n i s h i n gi t e m si nt h eo b j e c t i v ef u n c t i o n ，a n d s e a r c h e sd y n a m i c a l l yb e t w c e nf 毫a s i b i ea n di n f e a s i b l er e g i o n ，t h u sn o to n l ym a k e st h e s e a r c hf l o t 蠡rf o mt h eo p t i m a ls o l u t i o nb u te 埘c h e st h es e a r c ha 1 e a ，s dt h a tl h e p r o b a b i i i t i e so f o b t a i n i n gm u c hb c 仕e rs o l u t i o na r ei m p r o v e d ，f i n a l l y ，t h es o l u t i o i l sa r e c o m p a r e dw i t hl h eb e s tk n o w ns o l u t i o na n dt h ei m p a c t sa f ca n a l y z e dw i t hd i 氐r c n t p a m m e t e r s 1 a h 5 i k 0 i 2 、f o rt h el a r g es c a l ca n dh o m o g e r l c o u sf l e e tv e h i c l er o u t i n gp r o b l e mw i t hs o rt i m e w i n d o w s ，an e wm e t h o df o rs o l v i n gi ti sp r o p o s e db a s e do nd e c o m p o s i t i o n 钮d c o o r d i n a t i o nt e c h n o l o g y a r e rt h ep r o b l e mi sd e s c r m e d 锄d t sm o d e li se s t a b l i s h e d ， f i r s t l y ，b yu s i n gf 屺z yk m e a n sc l u s t e r ，t h ev e h i c l e sa r ec l a s s i f i e da n dm ec e n t e r c o o r d i n a t e so ft h cc i a s s i f i e dv e h k l e sa r eo b t a i n e db 髂e do nt 虻p o s i t i o no fe a c h v e h i c l e ：t h e nt h et a s k sa r ec l a s s i f i e db a s e do nl h ed i s t a n c e sb e t w e e nt h et a s k sa n dt h e c e n t e rc o o r d i n a t e so ft h ec l a s s i f i e dv e h i c l e s s e c o n d l y ，r e g a r d i n gt h eb a dc o n v e i g e n c e w h i l eu s i n gt r a d “i o n a ld e c o m p o s i t i o na n dc o o r d i n a t i o nt e c h n o l o g ) ，t os o l v et h c p r o b l c m ，t h ec o o r d i n a t i o nv a l u e sa r cd e s i g n e de l a b o m t e l ya n dd i f 如r e n ta d a p t i v e g e n e l i ca 培o r j l h m sa r ep r o p o s e df o r t h em a i ns y s l e 】a 1 1 ds u b s y s t e m s t h es i m u l a t i o n r e s u l t ss h o wt h cc m c i e n c yo f t h ep r o p o s e da l g o r i t l l i l l f o r t h cl a r g es c a l ea n dh e t e r o g e n e o u sn e e tv e h i c l er o u t i n gp r o b l e mw i t hs o at i m e w i n d o w s ，a 1 1c f c t j v et a b us e a r c hf o ra p p 】j c a t i o nt 0t h ep r o b l e mi sp r 印o s 。d a f t e r t h ed e s c r i p t i o no f t h ep r o b l e mi sg i v e na n di t sm a t h c m a t i cm o d e l i sp r e s e n t e d ，f i r s t l y ， t h cc a r i d i d a t el i s ts t r a t e 醪i sp r o p o s e d ，w h i c hi su s e dt oa b a n d o nal a r g en u m b e ro f h o p e l e s sm o v c m e n 括，8 n dt h cs i z eo f c a n d i d a t ei i s tf e b t e dt o 啦es e a r c hn e i g h b o f h d o d i sa d j u s t e dd y m m i c a l l yw i t ht h ep r o 伊e s so fs e a r c h ，w h i c hp r o v i d e sas i m p l em e t h o d f o ri m p l c m e m i n gi n t e n s i f i c a t i o na n dd i v e r s m c a t i o ns e a r c h s e c o n d l y ，t h ed y n a m i c o s c i l i a t i o ns t r a c e g yi sd e v e l o p e dt oc o n t f o ic h cs e a f c hi nc h eb o u n d a f ya r c ab e t w c e n f b a s i b l ca n di n f c a s i b l es p a c e t h ev a l i d i t yo ft h ep r o p o s e dm e t h o di sp r o v e db yt h e s i m u l a t i o nr e s u h s 3 、f o rt h em u “i d e p o tv e h i c l er o u t i n gp r o b i e m 硒mt i m ew i n d o w s ，a 氏rs e v e m l c l 嬲s i cm u l t i d e p o tl o c a t i o nm o d c l sa r ea n a l y z e d ，t h ep r o b l e mi sd e s c r i b e da n di t s m a t h e m a t i c a lm o d e li sb u i l t c o m i d e r i n gt h ep r o b l e m so fl o w e re f f i c i e n c y 锄do f e a s i i yf a l i i n gi n t oi o c a io p t i m a ls o i u t i o n s f o rs o i v i n gm u l t i d e p o tv e h i c i er o u t i n g p r o b l e mp r c s c n t l y ， ai l c wm e t h o db a s e do nd e c o m p o s i t i o n锄dc o o r d i n a t i o n t e c h n o l o g yi sp r o p o s e d f i r s t l y ，t h ec i l s t o m c r sa r ed e c o m p o s e di n t oc o u p l i n ga n d n o n c o u p l i n gc u s t o m e r sb yah e u r i s t i cm e t h o d s e c o n d l y ，t h ec o o r d i n a t i o nv a l u e sa r e d c s i g r i e de l a b o r a t e l yb ym e a i l so fa l la d a p t i v eg e n e t i ca l g o r t h r na n dat a b us e a r c h m c t h o di sd e v e l o p e dt os o l v et h ev e h i c l er o u t i n gp r o b l e mf o re a c hd e p o t f i n a l i y ，t h e s i m u l a t i o nr e s u l t sa r eg i v e n f o rm u l t i d c p o tv e h i c l er o u t i n gp r o b l e mw i t hs t o c h a s t i cd e m a n d s ( v r p s d ) ，o nt h e b a s i so ft h ed e s c r i p t i o no fl h cp r o b l e ma n d 也ea n a l y s i so fm o d e l sr e l a t e dt ot h e 西北工业大学博士学位论文车辆路径问题的矬模与优化曰法研究 p m b l e m ， i t sm a t h e m a t i c a lm o d e li s d e v e l o p e d b a s c do nd e c o m p o s i t i o na n d c o o r d i n a t ；o nt c c h n o i o g y ，i nt h ec o o r d i n a t i o ni a y e rt h ec o u p l i n gc u s t o m e r sa f e d e c o m p o s e di nt h eo p t i m a lw a yb y 璐i n ga na d a p t i v eg e n e t i ca l g o r i t h m ，i nt h e e x e c u t i v el a y e r a na d a p t i v ec r o s s e m r o p ym e t h o di sd e s i g n e df o rs o l v i n gv r p s d w i t ht h ep r e v e n t i v er e c o u r s ea c t i o nf o re a c hs u b s y s t e m f i n a l l y ，t h ec o m p a r i s o no f r c s u l t so b t a i n e db yl l s i n gd i 矗c r e n tm e t h o dp r o v e st h ev a l i d i t yo ft h ep r o p o s e d m e t h o d 4 、a r e rs e v e r a lt y p i c a l a l g o r i t t i i i i sa r ea n a l y z e df o rs o l v i n gt h ev e h i c l er o u t i n g p r o b l e m sw i r hs t o c h a s c i c 出m a n d s ，b a s e do nc f o s s e n t r o p ya sw c l la si n c e g r a “n g i m p o n a n ts a m p l e ，m o n t e c a r l oa n dm a r k o vc h a i n ，an e wm e t h o di sp r o p o s e df o f s o m n gt h ev e h i c l er o u t i n gp r o b l e m 嘶t hs t o c h a s t i cc u s t o m e r sa n dd e m a j l d s o nt h e b a s i so ft h ed e s c r i p t i o no fp r o b l e ma n dt h ee s t a b l i s t m i e n to fi t sm a t l l e m a t i c a lm o d e l ， f i r s t i y ，d u et ot h ec o m p l e x i t yo fi t so b j e c t i v ef u n c t i o n ，a ne 行爸c t i v ea l g o r j t h mi s d e s i g n e dt oo b t a i l lt t l ee x p e c t e dc o s to fr o u t e sb yu s i n gm o m e c a r l os a m p l i n g s e c o n d l y i no r d c rt 0i m p r o v et h cp e 雨肌a n c eo fb a s i cc r o s s - e n t r o p ym e t h o d ，龃 a d a p t i v ea d j u s t m e n ts c h e m ei sd e v c l o p e df o r t h cc n l c i a lf o u t e su s e dt ou p d a t c m a r k o vt r a n s i t i o nm a t r i xi l lt e 咖so ft h ei m p m v e m e n tl c v e lo fq u i m i l e s f i n a l l y ， s i m u l a t i o nr e s u i t ss h o wb o t ht h er o b u s t n e s sa n dt h ee 能c t i v e n e s so ft h ep r o p o s e d a p p r o a c hf o rs o l v i n gt h ep r o b l e m s 5 、0 nt h eb a s i so fh l ca n a 】y s i so ft h es t o c h a s t i cs h o r t e s tp a t hp f o b l e m ，亡h ed ”a m i c v e h i c l er o u t i n gp m b l e mw i t hs t o c h a s t i cd e m a n d si sd e s c r i b e da n di t so p t i m a ip o i i c y m o d e li se s t a b i i s h e d ，f o rt h e “d i m e n s i o nd i s a s t e r ”p r o b l e mo fi t ss t a t es p a c e ，ar a d i c a l b a s i sf u n c t i o ni su t i l i z c dt oa p p r o x i m a t et h eo p t i m a ic o s t - t o g of u n c t i o nb a s e do nt h e p r i n c i p l eo fr e i n f o r c e m e n tl e a m i n g f i r s t l y ，ab a s i sf l m c t i o ni sa n a l y z e da n dd e s i g l l c d s e c o n d l y ，f o raf i x c dp o l i c y ，t h eb e l l m a ne r r o r 硒a no p t i m i z a t i o nc r i t e r i o ni s m i n i m i z c db yo n i i n et u n i n gb o t hi e a s ts q u a r c st e m p o 阻ld i f r e n c ea i g o r i i h mf o r d e t e r i l l i n i n ga p p r o x i m a t i o nf u n c t i o nw e i g h tc o e m c i e m sa n dc r o s se n t r o p ym e i h o df o r s o l v i n gb 酗i sf h n c t i o np a m m e t e r s ，s oa s t o a p p r o x i m a t e t h eo p t i m a lc o s t t o g o 凡n c t i o n f i m l ly ，s i m u i a t i o nr c s u 王t ss h o wt h ee 旋c i i v e n e s so f t h ep r o p o s e dm e t h o d k e y w o r d s ：v e h i c i er o u t i n g ； b e l l m a n - f o r ds h o r t e s tp a t h ； f u z z yk m e a n sc l u s t e r ； d e c o m p o s i t i o na 1 1 dc o o r d i n a 6 0 nt e c h n o j o g y ；g e n e t i ca l g o r i t l l f l l ； 诅b u s e a r c h ；c f o s s - e n t r o p y ；m a r k o vd e c i s i o n ； r a d i c a lb a s i sf u n c t i o n v 西北工业大学业 学位论文知识产权声明书 本人完全了艉学校有关保护知识产权规定，即：研究生在校攻读学能! j | 词论文1 ：作 的知识产权单位属于撕北工业火学。学校有权保留并向国家有关部门战机构送交论文的复 印件和l 电子版。本人允许论文被查阅和借阅。学校可以将本学位沦文的全部或部分内容编 入有关数据庠进行检索，可以采川影印、缩印或扫捕笛复制手段保存年汇编本学位沦文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北【：业 人学。 保密论文待解密后适用本声明。 学位论文作者签名挝 指导教师签 西北工业大学 学位论文原创性声明 秉承学校严谨的学风平| 1 优良的科学道德，本人郧暖卢1 1 j ：所交的q 何论文是 本人在导师的指导f 进行研究工作所取得的成果。尽我所知，除文r | | 已经注明引川j 的 内容和l 致谢的地方外，本论文不包禽任何其他个人或集体已经公开发表或撰写过的研 究成果，不包含本人或其他已 扣请学位或其他川途使川过的成果。对本文的研究做 重要贡献的个人平集体均已在文中以明确方式袭叫。 本人学位论文与资利若有0 i 实，愿意承担一切相关的法律责任。 学位论文作者签名挝 彬年灿狐 西北工业大学乜耳士学位论文卞辆路径问题的建模与优化算法研究 第一章绪论 1 1 选题背景及意义 交通运输是国民经济的命脉，是社会经济活动中人流、物流、资金流和信 息流的主要载体。在现代社会中，没有高效运转的交通运输体系，就不可能有 经济的持续发展。因此，自2 0 世纪7 0 年代，国外就研究将先进的计算机技术， 信息技术，数掘通信传输技术，自动控制技术，人工智能及电子技术等，有效 地综合运用于交通运输管理体系中，建立一种在大范围内，全方位发挥作用的 准时，准确，高效的交通运输管理体系，也就是智能交通系统( i n t c l l i g e n l 1 r a i l s p o n a t i o ns y s t e m s ，简称i t s ) ，尽管当时由于信息处理技术的不成熟曾一度 陷入低谷，但随着信息处理技术的发展，对i t s 的研究热情又重新高涨起来， 特别是进入9 0 年代后，各发达国家在i t s 研究方面投入巨大的人力、物力和财 力，使得i t s 成为继航空航天、军事领域之后，高新技术应用最为集中的领域， 并逐步形成了以美国、同本和欧盟为代表的三大i t s 研究中心。为推动i t s 的 发展，1 9 9 5 年3 月美国交通部首次正式颁布了国家智能交通系统项目规划， 明确规定了智能交通系统的7 大领域和2 9 个用户服务功能，并确定了到2 0 0 5 年的年度，于发计划。其中7 大领域包括：出行和交通管理系统、出行需求管理 系统、公共交通运营系统、商用车辆运营系统、电子收费系统、应急管理系统、 先进的车辆控制和安全系统。我国对i t s 的研究还处于起步阶段，但它的重要 性已得到国家相关部门的高度重视。1 9 9 5 年正式成立i s o 厂r c 2 0 4 中国委员会， 该委员会以推进中国i t s 标准化为主要任务。在全面研究国外i t s 发展的基础 上，结合我国的国情和具体实际情况，提出了适合我国交通发展全新的i t s 。 主要包括：先进的交通管理系统、先进的公共交通系统、交通信息服务系统、 电视监控系统、车辆安全系统、物流管理系统等。1 9 9 8 年1 月交通部又正式批 准成立交通智能运输系统工程研究中心( i t s c ) ，为加强该中心智能交通系统的 开发及实验能力，投资1 4 0 0 万元建设交通智能运输系统中心试验室，为今后国 家制定道路交通运输的发展和政策提供科学依掘。 随着经济全球化和信息技术的飞速发展，被普遍认为是企业减少物质消耗、 提高劳动生产率、降低成本的“第三利润源”现代物流业正在世界范围内 兴起。目前，美、同、欧等发达国家和地区已经形成了比较完善的物流基础设 第一荦绪_ 施和高效的物流信息平台，现代物流产业对社会、经济发展的贡献越来越大。 美国2 0 0 0 年物流支出占g d p 的比重为1 0 1 ，物流产业的规模已达到l 万亿 美元。e | 本在近2 0 年内，物流产业每增长2 6 个百分点，经济总量就增加1 。 在全球经济的带动下，我国物流业的发展速度和规模都是惊人的。据一些国际 组织统计，我国物流费用占g d p 总量大约在2 0 一3 0 。现代物流业已成为衡 量一个国家现代化程度和综合国力的重要指标，也是现代社会、企业经济持续 增长的“动力”和“加速器”。 车辆路径问题( v c h i c l e r o u t i n g p r o b l e m s ，简称v r p ) 作为i t s 中的重要内容， 在现代物流中占有很重要的位最。据不完全统计，运输费用在物流费用中占的 比例最大，达4 4 【“。因而，针对当前我国物流业科技水平比较落后，物流效 率不商、物流从业人员专业化程度低等问题，充分利用电子技术和信息技术( 譬 如，数据通讯传输技术、电子传感技术、电子控制技术及信息处理技术) 等，开 发能快速处理多种信息的车辆路径系统，以便适应现代物流业高速发展提出的 新要求，是非常必要的。这不仅有助于改变我国物流管理落后的现状，也有助 于解决城市交通靠h 挤、能源短缺、大气污染等困扰人们的社会问题，实现效率、 资源和环境各方面的内在统一，促进物流业的进步和社会经济的可持续发展。 另外。随着电子商务的蓬勃发展与全球经济的一体化，市场竞争进一步加剧， 企业要在竞争中取胜，不仅要保证产品的质量，而且还要提供优质的服务。研 究丌发先进的车辆路径系统，不仅有助于企业节约运输成本，提高车辆的利用 效率，缩短生产周期，加速资金周转，实现资源的合理配置，而且，还可以使 企业实现安全、快速、高效的运输，满足消费者对物流要求适时变化的需要， 为物流实现快速化、信息化、柔性化、准时化及“零库存”的管理模式提供了 条件。 1 2 车辆路径问题描述及分类 1 2 1 车辆路径问题描述 车辆路径问题是由著名学者d a n t z i g 等1 3 l 于1 9 5 9 年首先提出来的，他们描述 了一个将汽油送往各加油站的实际问题，并提出了相应的数学规划模型及求解 算法。1 9 6 4 年c l a r k e 等p l 对d a n t z i g 的算法进行了改进，提出更为有效的启发式算 法c l a r k e w r i g h t 节约法。自这两篇开创性的论文发表后，由于该问题在理论上和 应用上非常具有代表性，因而很快引起运筹学、组合数学、图论与网络分析、 两北工业大学博七学位论文车辆路径问题的建模与优化算法研究 物流科学、计算机应用等学科的专家，以及运输计划制定者和管理者的极大重 视，成为“最近十年运筹学领域最成功的研究之一”i ”。 经典v r p 描述如下：给定一个完全图g = ( 圯彳) ，其中矿= 札，h ，v 。) 为 图的顶点集，爿= 【v ，v ，) f ，v j ，v ，e 矿j 为弧集。顶点”o 表示库房，顶点 v ，( f = l ，2 ，胛) 表示用户( 或城市) 。已知一个定义在彳上的矩阵c = ) ，它的 元素o i i 表示点”f 到点”，的距离( 费用或行程时白j ) 。有肌辆载重量为q 的车( m 为常数或决策变量) 。每个顶点仅被服务一次，每辆车都从库房”o 出发，服务完 后又回到”o 。在满足某些约束条件下，如何安排车辆行程，使服务所有用户的 车辆行驶距离最小或所需车辆数最少。 下面给出几种常用的约束： 1 ) 容量约束：每条路径总的需求量( 或供应量) 不超过车辆的容量q 。 2 ) 行程距离约束：每辆车的最大行程距离不超过某一预先指定的数。 3 ) 时间窗约束：包括硬时问窗和软时间窗。对应的v r p 分别为：带时间窗的车 辆路径问题( v e h i c l er o u t i n gp r o b l e m sw i t ht i m ew i n d o w s ，v r p t w ) ，指车辆 沿路径必须在用户规定的时间内提供服务；带软时问窗的车辆路径问题 ( v e h i c l er o u t i n gp r o b l e m sw i t hs o f 【t i m ew i n d o w s ，v r p s t w ) ，指车辆沿路径 可以不在用户规定的时间内提供服务，但会引起惩罚费用。 1 2 2 车辆路径问题分类 根据已有的研究成果，可以将v r p 按下列方式分类： 按数据特征分类：根据输入数掘是否与时间有关，可分为静态的平l i 动态的v i 冲； 根据调度时所有的数据是否已知，可分为确定性的和不确定 性v r p ，其中，不确定性v r p 又可分为随机的和模糊的v r p 。 按任务特征分类：有送货的、拉货的和送拉货混合的v r p 。 按任务性质分类：有弧需求的、点需求的和点弧混合需求的v r p 。 按载货状况分类：有满载的和非满载v r p 。 按库房数目分类：有单库房的和多库房v r p 。 按车辆类型分类：有单车型的和多车型v r p 。 按服务方式分类：车辆一次服务单个用户的和车辆次服务多个用户的v r p 。 按约束条件分类：有带能力约束的、带距离约束的和带时i 日j 窗约束的v r p 。 按库房封闭性分类：有丌放型的( 车辆完成服务不返回库房) 和封闭型的v r p ( 服务完后，车辆返回库房) 。 第一章绪论 按计划期长短分类：单计划期的、滚动计划期的和无穷计划期的v r p 。 按目标数多少分类：有单目标的和多目标的v i 冲。 按需求是否分割分类：有可分割的和不可分割的v r p 。 1 3 车辆路径问题研究概况 1 3 1 国内车辆路径问题研究概况 2 0 世纪9 0 年代以来，对v r p 的研究在国内逐渐兴起。十几年的研究，取得 了一些成果，但与国外相比，目前仍处于起步状态。对此问题进行深入系统性 的研究有：1 9 9 4 年郭耀煌教授等1 6 j 出版的国内该领域第一部专著车辆优化调 度，随后在2 0 0 1 年李军教授等1 7j 在车辆优化调度的基础上。出版了物 流配送车辆优化调度理论与方法一书。2 0 0 3 年刘宝碇教授等pj 对随机和模糊车 辆调度问题进行了系统研究，在他的不确定规划及应用一书中给予了专题 论述。通过中国期刊网数据库检索，到2 0 0 5 年为止，与