（系统工程专业论文）基于VLSN的智能ILS优化方法求解VRP问题研究.pdf

东北大学硕上学位论文摘要 摘要 运输是现代生产企业和物流管理中最重要的一个环节。而车辆调度是运输问 题中最关键的技术。有效的调度车辆，不仅可以提高物流工作效率，而且能够为 生产工序之间的物料传送得到运输上的保障，从而实现物流管理科学化。车辆调 度问题不但直接存在于物流管理当中，而且很多实际生产调度也可以间接归结为 该问题，所以它一直是运筹学与组台优化领域的热点研究课题。 由于大多数车辆调度问题都已证明是n p 一难问题，研究问题的近似算法成为其 关键技术。本论文针对三类不同的车辆调度问题，分别建立了数学规划模型，探讨 了适合不同问题的新的基于大规模邻域搜索( v l s n ) 技术的迭代局域搜索( i l s ) 算 法。主要研究工作如下： 1 ) 对基本车辆调度问题( v r p ) ，提出了两类不同的算法：( 1 ) 两阶段算法。第一阶 段，采用传统启发式算法一节约法；第二阶段，采用基于v l s n 的d y n a s e a r c h 求解t s p 问题的算法，在该算法中，嵌入了随机k i c k 的i l s 算法：( 2 ) 两阶段算法。第一阶段， 提出基于v l s n 的环状交换动态规划算法；第二阶段同上。在该算法中嵌入了两层 随机k i c k 的i l s 算法。同时对环状交换动态规划算法提出底层采用i n s e r t 和加入虚 拟顾客两种改进策略。 2 ) 带有顾客选择的v r p 问题，由于顾客数目太多而需要从中挑选些具有较大 利润的顾客来服务，同时最小化运输费用。对这类问题，采用了传统与改进的节 约算法进行求解。基于v l s n 技术，提出一种带有虚拟车辆的改进环状交换动态 规划算法，并嵌入了随机k i c k 的i l s 算法。 3 ) 对带有车队大小的v r p 问题，车的型号不同导致能力和固定费用不同，因 此需要从中挑选出一些车辆组合使得总的费用最小。对这类问题，采用了传统的 节约算法进行求解，并在此基础上采用两阶段策略进行改进。提出了一种带有虚 拟顾客的改进环状交换动态规划算法，并结合了随机k i c k 的i l s 策略。 所有的实验程序都是用c h 编写，并在p e n t i u m l l i 主频9 9 8 m h z 和p e n t i u m 4 主频2 4 g h z 的计算机上进行实验仿真。实验结果表明：( 1 ) 对基本v r p 问题，就 解的质量而言改进节约法比传统节约法要好，计算时间相差不大。基于v l s n 的 环状交换动态规划算法明显改善了解的质量，由于算法结构不同，所以导致计算 一it 东北大学硕士学位论文 摘要 时间要比前两种算法长：( 2 ) 对带有顾客选择的v r p 问题，同样改进节约法比传 统节约法好，而改进环状交换动态规划算法明显优于前两种算法；( 3 ) 对带有车队 大小的v r p 问题，改进节约法也比传统的节约法好，改进环状交换动态规划算法 就解的质量而言优于前两种算法，同样计算时间也较长。 关键词：车辆调度问题，n p _ 难问题，大规模邻域搜索技术，环状交换，动态规划， 随机k i c k ，迭代局域搜索 东北大学硕士学位论文 a b s t r a c t a b s t r a c t t h e t r a n s p o r t a t i o np r o b l e mp l a y st h em o s ti m p o r t a n tr o l ei nm o d e mm a n u f a c t u r i n g e n t e r p r i s ea n dl o g i s t i c sm a n a g e m e n t v e h i c l er o u t i n g i st h e k e yt ot r a n s p o r t a t i o n p r o b l e m e f f e c t i v ev e h i c l er o u t i n gs c h e d u l i n gc a ni m p r o v e t h ee f f i c i e n c yo fl o g i s t i c s a n dc a np r o v i d eag u a r a n t e eo fm a t e r i a l st r a n s p o r t a t i o na m o n gp r o d u c t i o no p e r a t i o n s v e h i c l er o u t i n gp r o b l e m ( v r p ) c a nb ef o u n de i t h e rd i r e c t l yi nl o g i s t i c sm a n a g e m e n t ，o r i n d i r e c t l yi nm a n y a c t u a lp r o d u c t i o ns c h e d u l i n g sw h i c hc a nb er e d u c e dt ov r p f o ra l o n gt i m ei t h a sb e e nt h eh o tr e s e a r c ht o p i ci no p e r a t i o n sr e s e a r c ha n dc o m b i n a t o r i a l o p t i m i z a t i o na i r e a s d u et ot h er e a s o nt h a tm o s to fv r p sh a v eb e e np r o v e dt ob en p - h a r dp m b l e m s ，t h e i r a p p r o x i m a t i o n - a l g o r i t h mr e s e a r c hi st h ek e y t ot h ep r o b l e m s o l v i n g i n t h i sp a p e r , t h r e ek i n d s o fv r p sa r ei n v e s t i g a t e d w ed e v e l o pm a t h e m a t i cp r o g r a m m i n gm o d e l sa n dp r o p o s e c o r r e s p o n d i n g i t e r a t e dl o c a l s e a r c h ( i l s ) a l g o r i t h m s b a s e do n v e r yl a r g e s c a l e n e i g h b o r h o o ds e a r c h ( v l s n ) t e c h n o l o g yr e s p e c t i v e l y t h em a i nr e s e a r c hw o r ki s l i s t e da sf o l l o w s 1 ) f o rb a s i c 冲，t w ok i n d so fa l g o r i t h m sa l ed e v e l o p e d ( 1 ) t w o - p h a s ea l g o r i t h m i n t h ef i r s tp h a s e ，t h et r a d i t i o n a lh e u r i s t i ca l g o r i t h m - s a v i n gm e t h o di sa d o p t e d i nt h es e c o n d p h a s e ，w e u s et h ed y n a s e a r c ha l g o r i t h mb a s e do nv l s nf o rs o l v i n gt s p i nt h ea l g o r i t h m ， i l sa l g o r i t h mb a s e do nr a n d o mk i c ki se m b e d d e d ( 2 ) t w o - p h a s ea l g o r i t h m i nt h ef i r s t p h a s e w ed e v e l o pc y c l i ct r a n s f e rd y n a m i cp m g r a m m i n ga l g o r i t h mb a s e do nv l s n n l e s e c o n d p h a s e i st h es a m ea sa b o v e 5 a l g o r i t h m b a s e do nr a n d o mk i c ki sa l s oe m b e d d e di n t o t h ea l g o r i t h m w e i m p r o v e t h e a l g o r i t h mb ya d o p t i n g i n s e r ta n d d u m m y c u s t o m e r s s t r a t e g i e s 2 ) f o rv r p w i t hp r o f i t s ，w i t ht h ee x c e s s i v en u m b e ro fc u s t o m e r sw eh a v et os e l e c t s o m ec u s t o m e r sw i t hb i gp r o f i t sw h i l em i n i m i z i n gt r a n s p o r t a t i o nc o s t w ea d o p t t r a d i t i o n a la n di m p r o v e ds a v i n gm e t h o dt os o l v ei t ，a n dd e v e l o pa ni m p r o v e dc y c l i c t r a n s f e rd y n a m i cp r o g r a m m i n ga l g o r i t h mw i t hd u m m yv e h i c l e i l sa l g o r i t h mb a s e do n r a n d o m d c ki sa l s oe m b e d d e di n t ot h ea l g o r i t h m 3 ) f o rv r p w i t hf l e e ts i z e ，t h et y p eo f t h ev e h i c l e si sd i f f e r e n t ，w h i c hm a k e st h ec a p a c i t i e s 一1 v 一 东北大学硕士学位论义a b s t r a c t a n df l x e dc o s t sd i f f e r e m s ow en e e ds e k ts o m ev e h i t i e st om i n i m i z et h et o t a lc o s tw e a l s o a d o p t t r a d i t i o n a ls a v i n gm e t h o dt os o l v ei t ，a n di m p r o v ei tw i t h t w o - p h a s es t r a t e g y t h ec y c f i c t r a n s f e rd y n a m i c p r o g r a m m i n g m e t h o da n di l ss t r a t e g ya l ea l s ou s e d a l lt h e e x p e r i m e n t a lp r o g r a m s a l ec o d e dw i t hc * a n dv a no n c o m p u t e r s w i t h p e n t i u m l i i9 9 8 m h za n dp e n t i u m42 4 0 g h z r e s p e c t i v e l y c o m p u t a t i o n a lr e s u l t sa r e l i s t e da sf o l l o w s ( 1 ) f o rb a s i cv r p ，t h ei m p r o v e ds a v i n ga l g o r i t h mi sb e t t e rt h a nt h e t r a d i t i o n a lo n ef o rt h es o l u t i o nq u a l i t y ，w h i l et h e i rc o m p u t a t i o nt i m ei sa l m o s tt h es a m e t h en o v e lc y c l i ct r a n s f e rd y n a m i c p m g r a m m i n ga l g o r i t h m sb a s e do nv l s ns t r a t e g y c a ni m p r o v et h es o l u t i o nq u a l i t yg r e a t l ya sc o m p a r e dt ot h ef o r m e ra l g o r i t h m s ，b u tt h e c o m p u t a t i o nt i m e i sm u c hl o n g e rf o ri t s s p e c i a ld a t as t r u c t u r e ( 2 ) f o rv r p w i t h p r o f i t s ，t h ei m p r o v e ds a v i n ga l g o r i t h m i sa l s ob e t t e rt h a nt h et r a d i t i o n a lo n e t h e i m p r o v e dc y c l i ct r a n s f e rd y n a m i cp r o g r a m m i n ga l g o r i t h mi sm u c hs u p e r i o rt ot h et w o f o r m e ra l g o r i t h m s ( 3 ) f o rv r pw i t hf l e e ts i z e ，t h ei m p r o v e ds a v i n ga l g o r i t h mi sa l s o b e t t e rt h a nt h et r a d i t i o n a l s a v i n ga l g o r i t h m t h ei m p r o v e dc y c l i ct r a n s f e rd y n a m i c p r o g r a m m i n ga l g o r i t h mi sm u c hs u p e r i o rt ot h et w of o r m e ra l g o r i t h m si nt h es o l u t i o n q u a l i t ya tt h ec o s to f m o r e o p e r a t i o n t i m e k e y w o r d s ：v e h i c l ei o u t i i 培p r o b l e m ( v r p ) ，n p - h a r dp r o b l e m ，v e r yl a r g es c a l en e i g h b o r h o o d s e a r c h l s n ) ，c y c l i ct r a n s f e r ，d y n a m i cp r o g r a m m i n g ，r a n d o mk i c k ，i t e r a t e dl o c a l s e a r c hm j ) v 东北大学硕士学位论文声明 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示了谢意。 本人签名： 东r 事 日期：毋。4 d ，、7 ， 东北大学硕士学位论文 第一章绪论 第一章绪论 本章首先介绍了v r p 问题的来源、研究目的、背景和意义。对v r p 问题的分 类及研究现状进行了介绍，并指出了现有文献中存在的问题及迸步研究的方向。 最后总结了本文的工作。 1 1 问题的研究目的及意义 1 1 1 问题的来源及研究目的 本论文的研究课题来源于国家自然科学基金项目基于v l s n 的智能i l s 优 化方法及其在调度中的应用研究( 6 0 2 7 4 0 4 9 ) 。 本论文的目的是研究三类不同的v r p 问题。本文描述了这三类v r p 问题的特 征与性质综述了这些问题的研究现状，以总费用最小化为目标，给出了传统的 启发式算法，并在该算法的基础上分别进行改进。描述了v l s n 技术的产生与性 质，通过深入分析三类不同的v r p 问题，分别在i l s 算法的基础上。构造并改进 邻域及其搜索策略。最终数据实验结果比较了不同算法的性能，并对算法性能进 行了分析。 1 1 2 问题的背景、特点及意义 在现实生活中，运输问题与人们的日常生活和经济活动密切相关。而车辆最 优调度是运输问题中最关键的技术。有效的调度车辆，不仅可以能够提高物流工 作效率，而且能够为及时生产( j i t ) 模式的企业提供运输上的保障，从而实现物 流管理科学化；如果把有效的车辆调度算法应用于公交车调度中，将有助于改善 城市的交通状况，进而方便市民出行，提高其生活节奏。由于该问题的理论涉及 许多学科，很多实际问题的理论抽象都可归结为这一类问题，应用前景广阔，很 快引起运筹学、应用数学、图论及网络分析、物流科学、交通运输工程、管理科 学与工程、计算机应用等科学的专家，工程技术人员和管理者的极大重视，因此， 该问题一直成为运筹学与组合优化领域的前沿与研究热点。 v r p 问题可以描述如下：车辆从一个或者多个仓库出发，为了满足地理位置 一】一 查些查堂堡主堂垡丝苎墨二里堕丝 上处于分散的城市或者顾客的需求，而需要优化设计派送路线或者收集路线这样 的问题。v r p 问题在实物分销和物流系统中扮演了一个很重要的角色。在现实生 活中存在很多v r p 问题的变形，有很多文献都研究了这类问题。下面列举了一些 主要的v r p 问题延伸。 1 ) 每个顾客只能在给定的一段时间内被访问，即带有时间窗。 2 ) 车辆不仅给顾客派送实物，还需要从顾客那里收集实物。这类问题被称为 b a c k h a u l i n g 。 3 ) 每辆车在一个给定的时间t ，可服务多条路线。 4 ) 车队里具有不同能力，不同型号的车。 5 ) 包括了除去运输时间以外其它的一些消耗时间，比如卸货时间，装卸时间 等。 6 ) 顾客有优先权，即访问顾客时需要考虑哪些顾客是要先访问的，哪些顾客 是可以后访问的，哪些顾客是可以不必访问的。 7 ) 不同的目标函数，有的问题是追求车辆数目最小化，有的是追求总费用最 小，有的是追求总路径最短，或总时间最小化。 在本文中，研究了三类不同的v r p 问题，类是基本的v r p 问题，第二类是 带有顾客选择的v r p 问题，第三类是带有车队大小的v r p 问题，这三类问题具有 很重要的实际意义与理论意义。本文的工作就是在充分了解基本v r p 问题的基础 上，以最小化总费用为目标，采用v l s n 技术，展开对带有顾客选择和带有车队 大小这两类v r p 问题的研究。 1 2 本文问题研究特点 1 2 1 基本v r p 问题研究特点 在实际中存在很多不同情形的v r p 问题，在这里只研究一种能代表所有v r p 问题最核心的基本问题，c h r i s t o f i d e s i l 把该类基本问题称为基本v r p 。 基本v r p 问题就是给车辆安排路线( 一条路线一辆车，以车场为起点和终点) ， 使得能满足所有的顾客需求，目标为最小化整个运输费用。基本v r p 问题忽略了 实际中的许多附加约束和外延，比如，每辆车可以走多条路线、顾客带有时间窗、 送货与收集同时进行、多仓库、多目标等。尽管实际中存在许多诸如这样的附加 一2 一 查韭查兰堡圭堂焦丝兰 兰二童堕丝 约束和外延，但都不能脱离基本v r p 问题的本质特性，所以研究基本v r p 问题有 很重要的实际意义。 1 2 2 带有顾客选择的v r p 问题研究特点 带有顾客选择的v r p 问题是基本v r p 问题的延伸。研究这类问题具有很重要 的实际意义。在实际中，可能被服务的顾客有很多使得管理人员需要考虑哪些顾 客是需要去服务的，而哪些顾客是可以不需要去服务的，作为考虑的依据就是哪 些被服务的顾客将带来更多利润。一类典型的问题就是带有回收的v r p 问题，在 这里顾客的回收价值等于顾客利润。同时这类问题还是一个典型的多目标优化问 题，其中各目标之间的利益是冲突的，一个目标是要使收集的利润最大，另一个目 标是要使整个路径最短。从利润最大的角度来看，希望访问的顾客越多越好；从 路径的角度来看，希望访问的顾客越少越好。另外，这类问题不仅仅局限于车辆 调度中，在其它的调度领域也存在这类问题的模型，b a l a s 和m a r t i n 2 1 提出了带有 顾客选择的t s p 模型在轧钢厂日调度的应用，因此研究这类问题也具有很重要的 理论和实际意义。 1 2 3 带有车队大小的v r p 问题研究特点 带有车队大小的v r p 问题是一个很重要的费用投资问题，解决该问题实质就 是以最低的费用，在满足顾客定单的情况下，选择最佳的车队组合。该问题是一 种带有两个目标的优化问题，其中一个目标是最小化车的固定费用，另一个目标 是最小化运输费用。从费用的角度来看，应该最小化车辆数目，从而降低车辆的 固定成本；但从服务的角度来看。这样势必会增加车的行驶时间，在带有时间窗 1 2 1 的情况下会降低顾客的服务满意程度，当然也会增加车的行驶路程。在实际中， 一旦购买了车，车就需要一定的固定费用。真正合理的车队应该具有很多类型的 车辆，这样会使得整个运作效果更好，费用更省。有文献e i l o n t 3 表明，车的固定 成本大约占与车辆相关费用的8 0 ，车的固定成本成为决定车辆组合的一个主要 因素，因此研究这类问题具有很重要的实际意义。尽管很多研究者都接触过这类 问题，但与其它问题相比，还不够引起重视。 东北大学硕士学位论文第一章绪论 1 3v r p 问题的研究现状 由于v r p 问题具有很重要的理论意义和实际意义，因此在以前的文献中对冲 问题研究有很多。在运筹学( o r ) 、人工智能( a d 、决策支持系统( d s s ) 等著名杂志上都有 很多相关的研究。综合起来，求解v r p 问题的算法包括两大类：最优化算法和启发式 算法。下面就分别介绍在以前的文献中这两大类算法在v r p 问题领域的应用。 在最优化领域里，从l a p o r t e n 的综述中可以看到，l a p o r t ee t a l 嘲提出了一个指派下 界和与之相关的分支定界算法，利用了v r p 问题与它的松弛问题m - t s p 之间的关系。 c h r i s t o f i d e se t 以网也提出了个对称v r p s 的算法，该算法定义在图g = ，e ) 上，并 采用了求解m t s p 的k l e g r e e c e n t e r t r e er e l a x a t i o n 策略。另外e i l o n e t a l 7 1 首次提出动 态规划算法来求解v r p ，接着，c h r i s t o f i d e se ta 1 1 8 也提出了一个求解基本v r p 的 整形规划和动态规划公式，并提出了一个基于状态空间松弛的分支定界算法，该 算法能提供最优解价格的一个更长的界。b a l i n s k i 和q u a r d t 9 首次提出了求解v r p 的 集划分公式，该公式已被o r l o 弹1 们，a g a r w a l e ta 1 【l l l ，f o s t e r 和r y a n 1 习等人应用，并在 此基础上，引出了一个整数线性规划。除此以外，f i s h e r 和j a i k u m a d ”1 给出了一个基 于b e n d e r s 分解的算法。 就启发式算法而言，c l a r k e 和w r i g h t 1 4 1 首次提出了求解冲的经典算法一节约 法。该算法可以在o ( n 2 1 0 9 m 时间内执行，如采用正确的数据结构该复杂性还可以减少。 该方法通过变形还被应用在许多冲问题的变形中。w r e n 1 5 在1 9 7 1 年首次提出了求解 带有能力v r p 的扫描法原形，其中该v r p 问题包括个或者多个仓库。紧接着g i l l e t t 和m i n e d 删在1 9 7 4 年正式命名该原形为扫描法，同样，由于v r p 问题的不同，也存在 很多扫描法的变形。另外c h r i s t o f i d e se la 1 1 1 7 1 提出了一个两阶段策略：在第一阶段， 以串行方式构造路线；在第二阶段，以并行方式构造路线。g e n d r e a ue ta 1 【1 8 1 提出 了一个禁忌搜索算法，并已成功应用到许多经典的v r p 问题中。 1 4 本文的技术研究路线及主要工作 1 a 1 研究的技术路线 本文的研究技术路线见图1 1 。 11292苫8u日a矗ohgil量。昌_【蔷匠 繇龉*辎s状警【_i团 东北大学硕士学位论文 第一章绪论 1 4 2 本文的主要工作 本文主要研究了三类不同的v r p 问题，分别建立了数学模型并采用了传统的 启发式算法与基于v l s n 的智能i l s 优化方法。具体工作如下： 1 )对基本v r p 问题进行了描述，综述了基本v r p 问题的研究现状，并指出了存 在的问题。指明了本文中针对该问题的研究方向，并建立了该问题的数学规 划模型。 2 )对基本v r p 问题采用了传统的启发式算法节约法，在此基础上运用了基于 v l s n 的d 3 ，n a s e a r c h 求解t s p 的三种算法，并嵌入了随机k i c k 的i l s 算法。 3 )对v l s n 技术进行了描述，综述了v l s n 的研究现状，主要思想和方法。 4 )基于v l s n 技术，对基本v r p 问题提出了一种环状交换动态规划算法，结合 了随机l d c k 的i l s 策略，并在此基础上给出了两种改进方法。实验分析了算 法性能和影响算法性能的主要因素。 5 】对带有顾客选择的v r p 问题进行了描述，综述了该类问题的研究现状，指明 了本文中针对该问题的研究方向，并建立了该问题的数学规划模型。 6 )对带有顾客选择的v r p 问题采用了传统的启发式算法一节约法进行求解，并在 此基础上进行变形改进。 7 )基于v l s n 技术，对带有顾客选择的v r p 问题提出了一种改进环状交换动态 规划算法，并结合了随机k i c k 的i l s 策略。实验分析了算法性能和影响算法 性能的主要因素。 8 1对带有车队大小的v r p 问题进行了描述，综述了该类问题的研究现状，指明 了本文中针对该问题的研究方向，并建立了该问题的数学规划模型。 9 )对带有车队大小的v r p 问题采用了传统的启发式算法一节约法的变形进行求 解，并在此基础上采用了两阶段策略进行改进。 1 0 ) 基于v l s n 技术，对带有车队大小的v r p 问题提出了一种改进环状交换动态 规划算法，并结合了随机k i c k 的i l s 策略。实验分析了算法性能和影响算法 性能的主要因素。 东北大学硕士学位论文 第二章基本v r p 河题的传统求解策略 第二章基本v r p 问题的传统求解策略 本章分析了基本v r p 问题的研究特点，该类问题是组合优化领域中研究最广 泛的一类问题，给出了求解基本v r p 问题最经典的求解方法一节约法，并在该节 约法的基础之上给出了一个基于v l s n 技术的改进新策略，该策略利用了两阶段 的思想。随后在该改迸新策略的基础上将随机k i c k 的i l s 算法与之相结合进行了 研究，最后对各种算法进行了性能比较和分析。实验表明，嵌入i l s 的v l s n 算 法在很大程度上能改进问题的解。 一? 2 。l 引言 在现实生活中，存在这样的个分配问题：基于中心仓库( 车场) 的车辆在给 定的时间段内，为了满足顾客的需求需要去访问地理位置上分散的顾客。该问题 在商品派送中存在很多实际的情形，统称为v r p 问题( v e h i c l er o u t i n gp r o b l e m ，简 称v r p ) 。由于v r p 在制造业和服务业( 比如第三方物流) 中有着举足轻重的经济 重要性，同时在实际中，还存在许多这类问题的变形，“车辆”该词往往用的很抽象， 因此研究这类问题具有很重要的实际意义。在实际中存在很多不同情形的v r p 问 题，在这里只研究一种能代表所有v r p 问蹶最核心的基本问题，该类基本问题被 称为基本v 】冲( c h r i s t o f i d e s 【1 1 1 。 在以前的文献中对基本v r p 的算法研究有很多。总的来说，求解这类问题的算法 包括两大类：最优化算法和启发式算法。在最优化领域里，从l a p o n 羽的综述中可以看 到，l a p o r t ee ta 吲提出了一个指派下界和与之相关的分支定界算法，利用了v r p 与它 的松弛问题m - t s p 之间的关系。c h r i s t o f l d e se t a 6 1 也提出了一个对称v r p s 的算法，该 算法定义在图g = f v ，e ) 上，并采用了求解m - t s p 的k - d e g r e ec e n t e rt r e er e l a x a t i o n 策 略。另外e i l o ne ta l 7 】首次提出动态规划算法来求解v r p ，接着，c h r i s f o f i d e se ta l t 8 1 也提出了一个求解基本v r p 的整形规划和动态规划公式，并提出了一个基于状态 空间松弛的分支定界算法，该算法能提供最优解价格的一个更长的界。b a l i n s k i 和 q u a n d t 9 1 首次提出了求解冲的集划分公式，该公式已被o r l o m 1 ，a g a r w a l “以【l l 】， f o y e r 和r y a n t l 2 1 等人应用，并在此基础上，引出了一个整数线性规划。除此以外，f i s h e r 和j a i k u m a r 【l 到给出了一个基于b e n d e r s 分解的算法。 查! ! 查兰堡圭兰垡笙塞蔓三童苎查些囹墅些堡竺查鳖整堕 就启发式算法而言，c l a r k e 和w r i g h t 1 4 】首次提出了求解v r p 的经典算法一节约 法。w r e n 1 5 】在1 9 7 1 年首次提出了求解带有能力v r p 的扫描法原形，其中该冲问题 包括一个或者多个仓库。紧接着g i l l e t t 和m i l l e r t l 6 】在1 9 7 4 年正式命名该原形为扫描法。 另外c h f i s t o f i d e se td 【17 1 提出了一个两阶段策略：在第一阶段，以串行方式构造路 线；在第二阶段，以并行方式构造路线。g e n d r e a ue ta l l l 8 l 提出了一个禁忌搜索算 法，并已成功应用到许多经典的v r p 问题中。 由于v r p 问题是一个强n p 难问题，最优化算法存在很大的局限性，而且在实际 中没有必要追寻最优值，因此在这里研究的都是启发式算法。本章描述了求解v r p 问 题最经典的启发式算法一节约法，并在该节约法的基础上提出了一种基于v l s n 技术的 改进新策略，最后将基于k i c k 的1 l s 算法与该改进节约法相结合进行了研究。 2 2 基本v r p 问题描述 基本v r p 可以描述如下：顾客和车辆以一定的顺序编号，编号0 表示车场( 或仓库) 。 每个顾客有一需求量，任意两个顾客之间有一路途费用，每辆车都有一个最大能力，基 本v r p 就是给车辆安排路线( 一条路线一辆车，以车场为起点和终点) ，使得能满足所 有的顾客需求，同时最小化整个运输费用。 路线3 路线2 图2 1 基本v r p 形状示意图 f i g 2 1t h e i l l u s t r a t i o no f b a s i cv r p v r p 问题应该包含设计一系列最低费用的车辆路线。在设计过程中，应满足以下 条件： 1 ) 每个顾客只能被一辆车访问一次： 一r 一 奎j ! 查堂堡圭兰堡笙苎墨三兰董查坠塑里堕堡堕苎堑签堕 2 ) 所有的车辆从仓库出发，并最终回到仓库； 3 ) 所有的车辆必须满足能力约束。 基本v r p 忽略了实际中的许多附加约束和外延，比如，每辆车可以走多条路线、顾 客带有时间窗、送货与收集同时进行、多仓库、多目标等。尽管实际中存在许多诸如这 样的附加约束和外延，但都不能脱离基本v r p 的本质特性。其示意图如图2 1 所示。 整个问题可以描述如下： 决策变量： 如果车k 访问顾客i 之后，立即访问顾客_ ， 否则， 如果车k 访问顾客i ， 否则。 = 0 ，l ，2 ，3 ，n ) 表示一系列的顾客集合，其中0 表示仓库，i ( i = l ， 2 ，3 ，n ) 表示顾客的编号。 m = 1 ，m ) 表示车集合，一共有m 辆车。 o 表示顾客i 到顾客，之间的运输费用。 甄表示第k 辆车的能力，k = - 1 ，m ) 。 卯表示第i 个顾客的需求量，i = 1 ，甩) 。 基本v r p 的目标函数如下： m t l 肌l ：曾 s t c 。像 k e m f n ，n 、 i ) = 1 e ， l m f = 1 ，” f = 0 z q ，y * s 幺 | ：1 ，m “! n ( 2 1 ) ( 2 2 ) ( 2 3 ) = = 剧删 i = 0 ，n ，= 1 ，m ( 2 4 ) 一9 1 o 1 o ，l rj、l = | | 嘞 ；荨 东北大学硕士学位论文 第二章基本v r p 问题的传统求解策略 丢强蚓酬q 对所有的网”“州，h ，m y ( o ，1 )i = 0 ，n ，k = 1 ，m x 社 0 , 1 ji ，j = 0 ，t * o 7n ，尼= 1 ，m ( 2 5 ) ( 2 6 ) ( 2 7 ) 约束( 2 2 ) 保证每个顾客只能被某一辆车访问，而仓库则被所有的车访问。约 束( 2 3 ) 为车的能力约束。约束( 2 4 ) 保证访问了该顾客的车同时也离开该顾客。约束 ( 2 5 ) 为t s p 问题的避免予环约束。 2 3 求解基本冲问题的传统启发式算法描述 由于v r p 问题是强n p 难题，其最优化算法的计算量一般随问题规模的增大 呈指数形式增长，因此只能求解很小规模的v r p 问题，应用这些最优化算法所能 求解的最大规模v r p 问题包含8 辆车，5 3 个顾客( c h r i s t o f i d e s 1 1 ) ，在实际中其应 用范围很有限，而且最优解对实际决策也没有多大意义，因此本文所研究的都是 v r p 问题的启发式算法。由于对v r p 问题研究的启发式算法很多，包括节约法、 扫描法、分支定界算法等，在这里只描述求解v r p 问题中最经典的算法节约法。 节约法( s a v i n gm e t h o d ) 是v r p 算法中研究最早的算法之，同时也是目前 v r p 中摄经典的算法。早在1 9 6 4 年c l a r k e 和w r i g h t t 1 就研究了这种算法，提出 之后得到了普遍的认同，它简单，易于理解，灵活性好，可分析性及交互式特性 都较好，不少算法都局部或是全部应用了c w 算法。这种算法的思想是根据一些 准则，每一次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路 为止。这种算法一般计算速度快，也很灵活，但这类方法有时找到的解离最优解 相差很远。 整个算法可以描述如下： s t e p l ：计算节约值 对每一对顾客i 和，计算节约值5 0 = 岛r c o + c j o 。其中啊为将两条路线( 0 ，i ， 0 ) 和( 0 ，j ，0 ) 合并成条路线( o ，i ，j ，0 ) 后的节约值。 如图2 2 所示，当把两条线路0 _ i 一0 和o 一，_ 0 连成一条线路 一1 0 东北大学硕士学位论文第二章基本v r p 问题的传统求解策略 可得到的节约值 町= 2 x c l o + 2 x c j o 一( d o + c j o + c t j ) 图2 2 计算节约值示意图 f i g 2 ，2t h e i l l u s t r a t i o no f c a l c u l a t i n g s a v i n g v a l u e s t e p 2 ：将节约值以递减的顺序排序。 s t e p 3 ：从该排列的顶端开始，执行下面步骤。 并行式 s t e p 4 ：对一个节约值s 口，如果把将路线i 和路线- ，合并后，在满足v r p 问题的约 束条件下能够可行，则把该两条路线合并。 s t e p 5 ：在排列里找其他的路线连接，反复执行s t e p 4 ，直到没有可再选择的连接。 串行式 s t e p 4 ：在当前排列里找到第一个可行的连接，追加到当前已构造的路线里。 s t e p 5 ：如果该路线不能在扩展，终止该路线。在排列里另起一条新的路线。 s t e p 6 ：重复s t e p 4 和s t e p 5 ，直到没有可再选择的连接。 整个算法的流程图如图2 3 所示。 2 4 基于传统算法的改进策略 本节主要在节约法的基础上，对其进行改进。其基本思想为两阶段：在第一 阶段对顾客进行聚类，即把顾客分配给车辆，在这一阶段主要采用了上面节约法 所得到的结果；第二阶段安排这些车辆路线。在该阶段，利用了t s p 的思想，即 把每一条路线看成一个旅行商问题( t s p ) ，然后对该t s p 进行改进。在这里，采 用了求解t s p 的启发式算法，基于v l s n 技术的d y n a s e a r c h 算法来搜索近似解。 在接下来的几节中，将分别介绍求解t s p 问题的传统改进策略和基于v l s n 技术 的改进策略。在本文中，考虑车的总运输费用与总路径成正比关系，因此，在第二阶段 东北大学硕士学位论文第二章基本v r p 问题的传统求解策略 计算任意两顾客以及顾客 与车场之间的运输费用甜 t i 计算节约值s 。 i 一+ i 找出节约值列表中的最大值町l ； 滞 n 嘉襄 、o 芝：拳 千y 穗 曲 连接r ， 孙 s +嚣 更新节约值列表 一t o = = ：二 lv 计算所有车的运输费用i 图2 3 利用c w 节约算法求解基本v r p 的流程图 f i g 23t h e f l o wc h a r to f c ws a v i n ga l g o r i t h mf o rs o l v i n gb a s i cv r p 中，t s p 问题的最短路径也可以看作是t s p 问题的最小运输费用。 2 4 1 求解t s p 问题的传统改进策略 在传统改进策略中，通常采用的是一个简单的启发式算法来搜索当前解的 k - o p t ( k = 2 ，3 ，) 邻域，传统的改进算法为k - o p t ( k = 2 ，3 ，) 算法，这些算法 是以任意一条路径开始，然后通过交换初始路径的一部分边，产生新的路径。那 么搜索当前路径的k - o p t 邻域的目的是为了找到比以前更短的路径。如果找不到这 样的路径，当前的路径就为局部最优解，算法终止。如果新边的长度少于替换边 的总长度时，将新的路径替换为当前路径。以下分别介绍三种不同的改进邻域 一12 查韭奎堂婴主兰垡丝塞笙三兰茎查坠塑望盟堡堑垄塑整堕 2 - o p t ，3 - o p t 和o r - o p t 。 1 ) 2 - o p t 邻域 2 - o p t 算法以任意一条路径开始，断开该路径的任意两边，把整条路径分 成两部分，重新以另外一种方式连接这两部分，构成了一条新的路径。如果 该新路径比原路径短，就将原路径