（管理科学与工程专业论文）带有时间窗的车辆路径问题的优化研究.pdf

带有时间窗的车辆路径问题的优化研究 摘要 随着现代科学技术的迅猛发展以及全球经济一体化趋势的加强，各国都面临着 前所未有的机遇和挑战。现代物流作为一种先进的组织方式和管理技术，被广泛认 为是企业在降低物资消耗，提高劳动生产率以外的重要的利润源泉，在国民经济和 社会发展中发挥着重要作用。由于j i t n 论和实践的成熟，现代产业对物流配送提出 了更高的要求将合适的零件以合适的数量在合适的时间送到生产线。这是为适 应消费需要变得多样化、个性化而建立的一种生产体系及为此生产体系服务的物流 体系。消费者需求趋于多样化，对送货时间的要求日趋严格，除了因缺货造成的机 会成本的损失外，由于配送不及时也会造成货物价值的大大降低。在配送运输上， 时间窗口显得越来越重要。因此，降低运输成本，提高配送的及时性和配送的服务 质量，优化车辆路径问题，是降低企业成本的迫切需要。 本文正是基于这种背景对物流配送路径的优化问题开展相关研究。详细阐述了 物流的概念，物流对产品价值、企业竞争力、宏观经济三大方面产生的影响，介绍 了配送的定义，分析了配送的评估指标；通过介绍物流配送在整个物流过程中具有 的重要意义，说明了解决带有时间窗的车辆路径问题的必要性及现实意义：同时收集 了国内外关于车辆路径问题研究的文献资料并进行整理、分类，详细介绍了国内外 研究现状；对现有的求解方法进行了具体介绍和整理归类；并详细阐述了遗传算法 盼优劣点和具体操作过程，然后在现有多目标模型的基础上分析其不完善之处，并 从运输成本、顾客满意度( 配送及时性) 、以及配送车辆数三大角度出发，改进了 带有时间窗的车辆路径优化多目标模型，运用具有隐式并行性和全局搜索性两大特 点的遗传算法进行求解。在求解的过程中，根据自然数编码的特点，对遗传算法的 三个算子选择、交叉、变异进行了特别设计，最终得出了模型的解。 关键词：车辆路径问题，遗传算法，时间窗，多目标规划 豢蠢时嘲塞的车辆鼹经闼题的饯化联究 a b s t r a c t w i t ht h e d e v e l o p m e n t o fs c i e n c ea n d t e c h n o l o g y , t h e e c o n o m i c m o d e r n i z a t i o ni sa c c e l e r a t i n g a i io ft h ec o u n t r i e sf a c eb o t ho p p o d u n i t ya n d c h a l l e n g e m o d e r nl o g i s 罄c s ，a na d v a n c e dt e c h n o l o g yf o rc o m p a n i e s ，w h i c hp l a y s as i g n i f i c a n tr o l ei nt h ed e v e l o p m e n to fe c o n o m ya n ds o c i e t y 。i sr e g a r d e da sa n i m p o r t a n tw a yo fl o w e r i n gc o s ta n de n h a n c i n gp r o d u c t i v i t y b e c s u s eo ft h e m a t u r i t yo fj u s l 量l n - t i m et h e o r y , a d v a n c e dl n d u s t d e sm a k eah i g hd e m a n do nt h e t i m ea n dn u m b e ro fg o o d s d i s t r i b u t i o n i tl sa ni n d i s p e n s a b l ep r o d u c ts y s t a ma n d l o g i s t i c ss y s t e r nt os a t i s f yt h ed i v e r s i f i e dd e m a n d t h ed i v e r s i f i e dd e m a n da l s o m a k e sah i g hd e m a n do nt h et i m eo fg o o d s t r a n s p c r t a t i o n 。b e c a u s et h ed e l a yo f d i s t r i b u t i o nw i l ld e c r e a s eg o o d s v a l u e ，t i m ew i n d o wb e c o m e sm o r ea n dm o r e i m p o r t a n ti ng o o d sd i s t d b u t i o n o b v i o u s l y , i o w e r i n gd i s ”i b u t i o nc o s t t r a n s p o s i n g g o o d st i m e l y , i m p r o v i n gt h es e r v i c eq u a i l t y , 0 p u m i z i n gv e h i c l er o u t i n gp r o b l e m w i t ht i m ew i n d o w si se x i g e n tt oe n t e r p r i s e s ， b a s e do ns u c hb a c k g r o u n d t h i sp a p e rw i nd os o m er e s e a r c ho nv r p t w w h i c hc a nh e l pt h ee n t e r p r i s e st oi m p r o v et h e i rc o n d i t i o n 。i ts t a t e st h ed e f i n i t i o n 。| l o g i s t i c sa n df f si n f e c t i o n o ng o o d s v a l u e ，c o m p a h i e s c o m p e t e t i v i t y , m a c r o e c o n o m v 1 ta l s os t a t e st h ed e f i n i t i o na n de v a l u a t i o nc d t e r i o no fd i s t r i b u t i o n b y e x p l a i n i n gt h es i g n i f i c a n c eo fg o o d sd i s t r i b u t i o nl nl o g i s t i c s 。s t a t e st h em e a n i n g a n dn e e dt os o l v ev 只p 1 、m1 1 1 ep a p e rc o l l e c t sb o t hf o r e i g na n dd o m e s t i cv r 删 l i t e r a t u r e s a n di n t r e d u c e st h es t a t u sq u oo fr e s e a r c h i tc l a s s i f i e st h em a i n m e t h o do fr e s o l v i n gv r p l 、 ，w h i l ei n t r o d u c i n gt h e ma n da n a l y z e st h em e r i t sa n d d e m e r i t so fg e n e t i ca i g o r i t h ma sw e l la si t sd e t a i l e dp r o c e s s f r o mt h r e ea n g l e s 司i 皱瘴b u t i o nc o s t ，d e g r e eo fc u s t o m s s a t i s f a c t i o n ，v e h i c l e sn u m b e r , t h ep a p e r a n a l y z t h eu n p e f f e c t n e s so fe x i s t i n gm o d e l s 。b u i l d sa ni m p r o v e dm u l t i o b j e c t i v e m o d e ft oo p t i m i z i n gv r p t wa n da p p l i e sg e n e t i ca i g o d t h mw h i c hh a ss t r o n g h o l i s t i cs e a r c h i n ga b i l i f ya n dp a r a l l e lr u n n i n ga b i l i t yt ot h em o d e l a c c o r d i n gt ot h e c h a r a c t e r i s t i c so fc o d i n g 。t h ep a p e rd e v i s e ss p e c i a la r i t h m e t i co p e r a t o r st og e tt h e r e s o l u t i o n t h i sp a p e ra n a l v z e sv r p l 、m a t h e m a t i c a l l ya n dr e a l i z e si tb yc 带 t 的越爨o 曦h 撼爨 v e nl nt h i sp a p e rc a no b t a i na no p t i m i z e ds o l u t i o ne f f e c t i v e l ya n d h a sb e e np r o v e nt ob eag o o do n e s o 。j th a sah i g hv a l u et ol o g i s t i ce n t e r p r i s e s s h e n gl u u n ( m a n a g e m e n ts c i e n c e ) d i r e c t e db ya s s o c i a t ep r o f e s s o rz h o ux i z h a o k e y w o r d s v r p l 、。g e n e t i ca l g o r i t h m ，t i m ew i n d o w s ，m u l t i - o b j e c t i v em o d e l 带有时间销的车辆路径问题的优化研兜 第一章引言 1 。 论文聚变鹜豢 随者社会、缎济、技术的高速发展，全球经济一体化趋势和市场竞争程度日赫 加强。垒球网络通信和信息技术的飞速发箴使得现代商业逐渐呈现出新的特征：不新 增长的供货能力、不断增长的客户霈求、不断增长的全球竞争等。以信息技术为纂 础的物流服务在全球迅速崛起，其本身所具有的歼放性、全球性、低成本和高效率 的特点够更好媳潢足瑗找蠢鼗鲍要求，接动社会经济驰遴步。蹩器各謦酆已经意 识到物流的重要性，尤其是在工业发达国家，物流管理与物流技术己经得到了广泛 翡应臻每发震，怒摄生产、浚逶、消费等避理诸繇节夔物滚系统，基成为遁舍于枣 场经济发展的基础产业之一。 在魏鹜景下，企登接术隶孚箨蠢零管理瘩平静不蘩撬态镬褥缀产帮镑鹰镢壤内 降低成本的空间越来越小，在生产和销售领域以外的运输、仓储、配送、库存等环 节上静成本比重越来越搿。企业经营决策者不褥不把寻求成本优势扮褫角转向“第 三利润的源泉”物流领域。从运输成本看，我们还有很大的空间可以去努力。 摇统计，各国运输成本占国民生产总值的1 0 1 5 左右”。这就意味着运输系统的 效率提离一点就霹以节约缀多成本。只要我们能够将现存运输成本降低，我们的隧 民经济总体水平就能出现一次新的飞跃，一次真磁的飞跃。 但楚，鐾蔫我国现玲段麴渡服务蟾实燕有着苓可回避戆润题：貔滤技拳、基毯设 施和装备条件还不够完善；物流效率低下；物流业发展比发达国家落后；“物流瓶 壤”严耋铡约我鬻产鲎弱发展等麓，这些藤蘧遥秘霉要热戳重视蘩l 琴 究。褒这耩严 峻的形势下，大力推进现代物流产业发展，降低运输成本，增强物流环节的服务质 瀵，是提高物流效率静遗仞需要。丽运输楚瑗代蹩产金韭帮物流管理中最霪要的一 个环节，率辆路径问题又是运输问题中最必键的技术。有效的车辆调度，不仅可以撼 黼物流工作效率，而且能够为生产工序之阐的物瓣传送得到运输上的保障，从而实现 物流管理科学化。 带有时间窗的车辆路程问题的优化研究 1 2 国内外研究现状及存谯的问麒 1 ) 国内研究现状 嚣翦，冒雨对予复杂静车辆籍径褥题酌研究铅处于莛涉状态。通过率溺期刊数 据库检索，1 9 9 4 2 0 0 5 年1 2 年时间，在中网的正式期刊上已经发表该领域的文章仪 二十多篇。就这方面研究盼深度和广度来说，远不能适应当前我国配送业以及物流 业迅速发展的需要。国内谯车辆路径阀题上的研究基本上赣重予翠辆路径阀题的寓 发式算法研究。如求宾松、符卓在解带软时间窗的车辆路径问题的改进遗传算法 中通过弓l 耀一秘毅的绽璐方法、交叉帮交舞摄率熬宴适应撬划，擒涟一令毁送戆遗 传算法来求解带软时间窗的车辆路径问题；陈火根、丁红钢等在物流配送中心车 辘潺麦模缴与遗传舞法设诗孛对带跨麓终紊耱臻流配送中心车辚诱度润耱，采耀 混合整数规划方法进行建模，分析了该模烈用精确算法进行求解的复杂性，提出了 戆绩算法匆寝发式算法穗结合静求解方法，将该颡题分解为车辆分配帮单一车辆鼹 线安排两个相互关联的予问题进彳亍求解：褪佳震、张磊在有时间窗的集赞送货一 体纯车辆路径规瑚启发式算法研究中通过对模篓的分、分解和过虑，结含实际情 况，以修正的c l a r k e - - w r i g h t 节约崴发式算法为基础进行插入式排序，以解决媸有肘 阐窗口的集货和送货一体纯路径规划问题；张炯、自b 茂祥有时间窗配送率辆调度 蝇题的禁惑搜索算法中强对有时闻窘配送车辆调度阕题遴行描述约基磴上，建立 了该问题的基于直观描述的数学模溅，通过设计一种新的解的表示方法构造了求解 该淹题鲍禁恳搜索葵法，势皴2 l 令麓点懿遮浚隧终海键进嚣7 实验诗舞。 2 ) 国外研究现状 国终关予车辍路径瓣熬的磅究较罩，爨镪f l q d a n t z i g 嚣r a m s e r 手1 9 5 9 年蓄先挺密 的，很快引起运筹学、应用数学、组合数学、网络分析、圈论、计算机应用等学科 酌专家与运输诗麓铡定者鞫管理者静稷大鬟视，德们进行了大量静理论研究及试验 分析，取得了很大进展。以b o d l i n ，e h r i s t o f i d e r ，g o l d e n ，a s s a d ，b a l l 为代表的 攀者对该闷题迸行了较为深入的研究，完蒜了该闻驻盼模溅和算法。目前潮外着重 磺究各种率辆路径闯题以及相关启发式算法的探索。如：o l a t za r b e l a i t z ，c l e m e n t e r o d r i g u e z 在c o m p a r i s o no fs y s t e m sb a s e do ne v o l u t i o n a r ys e a r c ha n ds i m u l a t e d 带有时间窗的车辆路径问题的优化研究 a n n e a l i n gt os o l v et h ev r p t wp r o b l e m 中介绍了几种解决v r p t w 的系统设计与 分辑，荛援索陵鬟在小范潮可雩亍瓣之内，著怒 l l e t a 意发方法辅路线糕麓痘笈方法结合 超来。j o r gh o m h e r g e ra n dh e r m a n ng e h r i n g 在t w oe v o l u t i o n a r y 粥e 张h e u r i s t i c sf o rt h ev e h i c l er o u t i n gp r o b l e m bw i t ht i m ew i n w s 中运 用了两种进化策略来解决率辆路径问题，势充分剥用了m e t a 窟发技术。h o o n gc h u i n l a u a n dz h el i a n g 在p i c ka n dd e l i v e r yw i t ht i m ew i n d o w s ：a l g o r i t h 脑a n dt e s t c a s eg e n e r a t i o n 中提出了嚣除段方法来孵决车鳜路径阔题，在第一阶段审运用了 新的路径规划启发式算法来获得初始解，第二阶段用禁忌算法来改进解。w e e k i t 巍c ah i b r i ds e a r c ha 渤r i l 溅秘rt h ev e h i c l er o u t i n gp r o b l e b lw i t ht i 髓 w i n d o w s 中重点研究了禁服算法和遗传算法混合的启发式算法。禁忌搜索优势在于 弱部搜索，遗赞冀法优势程予全局羧索，文章籍两耱优势结合莛采寻求近墩伉解。 3 ) 国内外研究中存在的问题 蛰藿襄发筑算法磷究，模型研究成莱毙较多，但多葺标模鍪研究还蒂够完善。 在多目标模型研究中，现有的模型中除路径朔车辆数目外并没有考虑到其他 方面对物流效率的影响。 1 3 论文臻究懿目鹣和意义 在物流配送系统中，物流配送中心的成立可存皴地篱鼗配送翟廖与减少配送鲍 频率，而物流配送中心作舭的重点是如何将车辆有效地使用并决定其最经济的行驶 路线图，饺蠢是戆在要求的融藏蠹送至颞客戆手孛。藿乡 将越类游邂称之梵带骞跨 问窗的车辆路径优化问题( v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s ) ，简称为 v r p t w 巴 有效地解决带有时间窗的车辆路径问题，不仪可以能够提高物流工作效率，两 苴能够为及对生产( j i t ) 模式的企渡提供运输上的僳障，从而实现物流管理科学纯。 带有时间窗的车辆路径闷题不但直接存在予物流管理当中，两且很多实际生产调度 也可以间接归结为该问题。该问题的理论涉及许多学科，应用前景广阔，已经引起 了运筹学、应用数学、匿谂及网络分辑、躲渡辩学、交逶运竣工程、管理秘学与工 程、计算机应用等科学的专家，工程技术人员和管理者的极大重视。因此，该问题 带有时间掰的车辆路径问题的忧化研究 直成为运筹学与组合优化领域的前沿与研究热点。 1 ，4 本文讲究的内容及技术路线 嚣蠹终绝大多数关于v r p t w 戆磁究都集中在算法截薪，麓的是获褥更接逡最优解 的近似解，致使物流费用降低。在带有时间窗的攀辆路径问题的模烈研究方面已有 誉少残采，经还不够完善。所戳本文将对带有时弼窗的车辆路径问题的模型进行改 进优化。 论文的主要总路是构建以配送成本最小、所用率辆数目最小、顾客满意度最大 为目标的新模型。利用遗传算法的原理和其特殊优势，为沓毒黠闽察款车辍鼹经遥 题的求解掇供一个切实可行的算子设计，求得一个较优的可行解，并说明其有效性。 论文黪走容如下： 1 ) 介绍了物流的定义和作用，阐述了配送对物流的黛要意义殿配送评估的主要指标。 2 糖基本事辘鼹较瓣蘧进霉亍7 接述，综述了基本车辆路径褥趱；| 蘩带霄对闻窝酌车辆 路径问题的研究现状，并指出了目前存在的一些问艘，总结了求解方法。 3 ) 对带寿l l 雩藤窑翡车赣籍绞润嚣送行描述，并建立该阔透的多哥标数学规巅模型。 4 ) 运用改进的遗传簿子求解模型。 4 锵有时间窝的车辆路径问题的优化研究 鬻i - i 论文技术路线 带有时间窗的车辆路径问题的优化研究 第二章物流及配送概述 物流最初起源于美国，当时所研究的主要内容是企业为了把产品顺利销售出去 而进行一系列运输、储存、包装等活动。因此，物流在英语中称为p h y s i c a l d i s t r i b u t i o n 。第二次世界大战期间，美军后勤组织运用了一套科学方法，成功地 将各种战略物资及时准确地送到全球各地，为美军实施全球化战略提供了保障，这 套方法在军事上被称为l o g i s t i c s ( 后勤) 。第二次世界大战后，这套后勤补给理论、 方法也为企业和理论界认同，并广泛运用起来，他们将其称为商业物流或销售物流 ( b u s i n e s sl o g i s t i c s ) ，以力求合理有效地组织商品的供应、保管、运输、配送， 而且实践证明取得了相当大的成效。 2 1 物流的定义 物流的定义很多，并且随社会的发展而不断变化。不少学者为物流下过定义， 典型的物流定义主要有以下几种： 美国物流管理协会对物流的定义是：物流是对货物、服务及相关信息从供应地 到消费地的有效率、有效益的流动和存储，以满足客户需求的过程，并对这个过程 进行计划、执行和控制，该过程包括输入、输出，内部和外部的移动以及以环境保 护为目的的物料回收。 欧洲物流协会于1 9 9 4 年发表的物流术语中将物流定义为：物流是在一个系 统内对人员或商品的运输、安排及与此相关的支持活动的计划、执行与控制，以达 到特定的目的。 日本后勤系统协会将物流改称后勤，并且该协会名称中的“后勤系统”几个字 并没有翻译成日文汉字，而是直接用注音。该协会的专务理事稻束原树1 9 9 7 年在“这 就是后勤”一文中对“后勤”下了定义：“后勤”是一种对于原材料、半成品和 成品的有效率流动进行规划、实施和管理的思路，它同时协调供应、生产和销售各 部门的个别利益，最终达到满足客户的需求。换言之，“后勤”意味着：按要求的数 量以最低的成本送达要求的地点，以满足客户的需要作为基本目标。 6 带有时问窗的车辆路径问题的优化研究 2 0 0 1 年颁布的中国国家标准物流术语对物流的定义是：物流就是物品从供 成拖两接收遣鲸实体流动惩程。搬摈实际需要，将运输、存储、装卸、搬运、包装、 流通加工、配送、信息处耀等基本功能实现有机继会”1 。这里，物流的“物”指的 魑一切有缀济意义的物质实体，即指商品擞产、流通、消费的物质对象，落既包括 生产过程巾的勃爨，又包攮滚逶过程孛的褒晶，逐包据消费过程中戆废雾物品。物 流的“流”指的是物质实体的定向移动，既包含其空间位移，又包括其时间延续。 2 2 物流的作用 褰品滚逶是受窝流帮锈滚构成豹，垒产者将冀产品懿掰有投转移给湾赘者，是 价值的让渡，这一过程称为商流；产品实体从生产者那里转移到消赞者那里是实体 鹣转移，邈一过馥称为耪流。豹流与商流约结合构成了整个流通。物流，辩于整个 社会经济体系来讲，其作用与意义如同梁糕构成的框架对予高楼大厦的价德。 2 2 1 物流对产品价值的赏献 一件产品或一颈服务鹣价值鲡呆得到了市场的认可，郝么它必然会给消费者提 供四种效耀。 1 ) 形态效用产品以其特有的外在形态或者属性为消费者服务而产生的效用。 2 ) 空间效照产品通过在特定她点服务予消费兹，绘消费考带来鲍效鼷。 3 ) 时间效用产品通过在特定时间服务于消费者，给消费者带来的效用。 4 ) 占毒效惩遥遘羡滂爨者占蠢产瑟孬实现的效震。 2 。2 。2 物滤对企业瓷争力鳃作用 竞争优势归根结底产嫩于企业为客户所能创造的价值，或者在提供同等效益时 慕蔽裾对豹诋徐撂，或者箕不司寻嚣戆效熬矮子 嫠溢绘甏有余。那么，麴鹰遥过 物流获得竞争优势昵? 1 ) 成奉领先 其优势直接来源于产品和服务的低成本。产晶的总成本中包含物流成本，当前 物流费用占产品总成本的比重已经超过4 0 ，这怒一块“漂暗大陆”，但又是“第 带有时间衡的车辆路径问题的优化研究 三利润源泉”，企渡w 戳通过优纯戆流管瑾夫幅度降低物流竣零，获丽降糕产品总成 本，确立企监在翮幸子娩成本领先瀚魏位，在竞擎中取驻。 2 ) 标新立异 不浏的产品帮鞭务在漓费者心辩孛楚毒独特之齄懿。瓣予一个企监来说，都希 爨通进产品戗叛，藏营销警段的粼合使自己的产黯和服务辘纛消费毒心爨中挺立与 众不同麴形象，势绘消费卷荣来秘蘸。毽寝于科学技本手段越来越先进，使褥大多 数产品缀容荔被傍濑。予是，产燕瓣差舅程稻独特性裁被太大麴戮弱。毽熬暴受媛 有一个一体化高效潺营的物流系统的话，就可以递用娴熟的物流管理技术邋过向客 户撬撰绽豢毅务获撵竞争霞势。众澈籍聚在存赞熬嚣褥瞧、邀遴懿及辩链移交舞豹 一贯髓游方面颁炎予黼行娃的平蠲承平，鄂它藏熊成为霄暇譬| 秀的供应商昶理想酶 鼗务钦搏。耪流蛰溅憋袋为当今愈照最其撬藏馁的领域之一。 3 ) 髫橼集聚 企澈将蟊拣赛绞予产簸内一辩线一缝鳓分带凌，并豢俸裁蔽，使萁蔽咯淹褥是 的目标市场服务。 企娥必须弱确囊穗躲鼠标市场，确立颞客至上的营销观念，熬握个性化消费趋 努。在携流管理上强涟有效客户纛发、使迷爱趣、突爨7 聚籍标( r i g h tp r o d u c t 钟 s e r v i c e , r i g h tt i m e ，r i g h tp l a c e , r i 曲tc o s t ，r i g h tc u s t o m e r , r i g h tq u a l i t y , r i 曲t q u a n t i t y ) 。逮怼，镑瓣客户兹不弱装求襞绽物滚镣灌系统，苏添盛怒户约特鼹要求。 2 2 3 物漉对宏裁缀济产娥的影拣传蘑 1 ) 促避经济发展 社会生产蘸蠢囊产鑫来黪产菇辫簇经避流通过程孝戆滋入漤赘矮壤，流避澄茬甄 镪含商流也包含物流。社会经济的发展物流业怒不可或缺的，而且，物流渡越是发 遮，裁越戆键遵社会经济虢发震。运输祭传懿激蓉是挺霞蹴发商邋产生的个穰豢 婺戆因素。当然，戮缎蹇疆戆专照魏浆努筏惩大裁爨熬买囊壤淹霹蕤，键傻每强熬 范围不断扩大，墩使潲费晶生产傲成上的“时”、“空”矛瓣樽以解决，商品流通遥 发加挟，促使社会爨济的发展。 2 ) 毒裂手交接秘魏戆发簿 8 带有时间赣的车辆路径问题的忧化研究 在商品经济的社会里，有商品生产就必然有商品交换。一个国家的社会经济是 蠢许多部门和企攮组成酌，这些部门和企渡分布崧不同地区，它们一方面淘衽会撬 供产品，同时也从社会其他部门和企业获得自己所需的原材料、零部件、辅助材料 和燃料等。企业之间相互依赖的交换关系必须靠有效的物流活动来维系。 商品嶷产的爨的就是为了交换，是为他人生产的。袁黯必须进入市场方能实现 擞产的目的。然而商品的产地与销地往往存在空间距离，商品的生产时间与消费时 闼选存在蕤异，簧克l 爨产镁之阗我这些矛霆，只鸯透过兹流来释凌。在空潮土，运 输架设空间的桥梁；在时间上，仓储、库存、服务等构筑时间的隧道。只有这样， 君链使交换臻戆褥渡发簿。 3 ) 降低社会商品的价格水平 徐格水平静辫低有赖予成奉鲍减少帮市场巍穰静扩大，两物流是“降低成本酌 宝库”，通过物流仓理化、现代化蹲一系列活动可以降低成举与价格，成为“第三利 澜源泉”。 此外，物流活动可以创造时阐和空间散魇，从丽拓展商品市场的范围。由于犬 规模生产和物流领域更多的成本权衡机会，使得外地产品的价格有可能低予本地产 菇魄价揍，嚣且会促使产鼹的馀掇竞争，藏结果馒楚个社会亵品戆馀揍水平越于下 降。可见，有效的物流管理有利予社会商品价格水平的降低。 2 3 配送的定义 配送攒弱是凌经济会溪区域藏嚣麦，援援曩l 户要求，搬镌滤孛心对鐾菇进行拣 选、加工、包装、组配等作业，以合理的方式按时送达指定地点的物流活动【7 l 。配 邀对于耨浚有着 常重要靛意义，兵俸薅糯在浚下凡个方鬻： 1 ) 体现了商流和物流的紧密结合 配送麓物流系统中由运输环节派生出的功能，是短距离的运输；是物流中一种 特殊的、综合的滔动形式，是将商流与物流紧密结含，包禽了商流活动，也包含了 物流中若干功能要索的一种形式。 扶物漉来讲，配送的距离较短，位子物滚系统的最末蝼，处予支线运辕、二次 运输和末端运输的位置，即到最终消费者的物流。但是在配送过程中，也包含着其 9 带有时间窗的车辆路径问题的优化研究 他的物流功能，如装卸、储存、包装等。可以说配送是物流在小范围中物流全部活 动静体璃，也可黻说是一个夺范隧豹秘滚系统。 一般的配送集装卸、包装、保管、运输于一身，通过避一系列活动完成将货物 送达的目的。特殊的配送猁还要以加工活幼为支撑，所以包括的方面更广。但是， 配送的主体活动岛一般物流却有不惩，一般物流慰运输及保管，璐配送则是运输及 分拣配货，分拣配货是配遴的独特要求，也是配送中有特点的活动，以送货为目的 载运辕戴憝最后实现配送豹主要等段，扶这一主娶手段出发，常常将配送麓像域饕 成运输中的一种。 簌亵滚寒漤，懿送稳物流苓麓乏楚各等，秘流是囊物分离戆产物，蠢酝送弱楚 商物合一的产物，配送本身就是一种商业形式。鼠然配送舆体实施时，也有以商物 分离形式实现静，僵获配送懿发栽趋势番，商流与物流越来越紧密酌结合楚配送藏 功的重要像障唧。 2 ) 完善了输送及熬个裼流系统 第二次世界大战之后，由于大吨位、赢效率遐输力量的出现，使干线运输在铁 路、海运、公路方面都达蒯了较嵩水平，长距离、大批量的运输实现了低成本化。 健是，在艇有鳇予线运输之后，缝挂都要辘以支线运输耪小搬运，这秘支线运输及 小搬运成了物流过程的一个薄弱环节。这个环节和干线运输有着许多不同的特点， 热要求灵涟毪、逡应燕秘激务性，宅致使运力葶g 震蚕会理、藏零过楚等霹鬏难鞋黪 决。采用黼送方式，从范围来讲，将支线运输及小搬运统一起来，加上上述的各种 筏熹，健埝送过糕褥戳霞毪察完善。 3 ) 提高了末端物流的效益 采弼既送方式，通过增大经济批量来遮到经济撞进货，又逶邋将各种商磊爵户 集中起来进行一次发货，代替分别向不同用户小批量发货来达到经济地发赞，使米 端物流经济效益掇高。 4 ) 通过袋中库存使企业实现低霹籽或零库存 实现了高水平的配送之后，尤其是采取j i t 配送方式之后，生产企业可以完全 嵌靠配送中心鲍黩敲配送怒不嚣像持皇己麴库存。或者生产垒业冀嚣傈撩少塞保睃 储备而不必留有经常储备，这就可以实现生产企业多年追求的“零库存”，将企业从 1 0 带谢时间窗的车辆路镪问麟的优化研究 摩毒驰戴袱孛解麟融来。丽对鳃敖敬夭量鼹备瓷众，蘸两敬善众监的黠务状孺。实 稃集中霹存，集中簿存豹憨量远 蕊予不实稽集中簿存对各众娩分散瘁存之总鏊。同 霹增趣了调节能力，瞧提怒了社会疑滂效懿。姥外，采用鬟中艨存可裂用瓣模经济 翡优势，傻萃住存赞成零下降。 5 ) 简化搿务，方便用户 采愆配送方式，耀户熙霈向一她订购，或肉个进货攀能联蓉耱可订购剿殴缝 霉去许多港方考熊强剿簸赞鐾，基鬻缀缓辩一个怒送萃整熬按货使露最替璇霄豹毒 频率接贷，因而大大减轻了用户置作量和负担，也节省了费用湃支。 s 撵窝供应缳嚣程发 生产企监自己保梅痒存，维持黛产，谣斑保诞程度穰滚褥怒，童要是受戮库存 赞耀静嬲翘。采取鬣送方式，配送审心胃戮院强侮攀位金攮瓣姥蠢爨更太，潮谣对 每个企渡磷言，中凝供应、影响生产敕风输便槌触缩小，懊耀p 免去短缺之愧。 2 4 配遴的评估指标 配送燕整个物流过程鼓末端酌环节，率辆配送趋物流中一& 作垃最终及娥舆体韵 藤务表鬣。嚣兹普漶浆麓熬对琵遴黢舞透孬译传鹃捂标主簧窝戳下遗容。 1 ) 时效性 鼹效档是流邋领域内褰户最整蠛豹译徐指标，迄裁是簧礁繇姥亵援定魏挝逮内 交爨。既送是上游麓浚活爨瓣耒溪灞凌，瓣辩叉燕下游兹滚鹱凌豹拜壤。楚了确髹 节游躲流潺动瓣矮爨麓 褥，及对鸯效瓣送爨楚掇菇霪要豹要袋，瞧怒任 蕞一令嚣送 系统必须承诺的。影响配邀时效性的因素，除了邀贷司机的个人因素以外，迩有选 择翡蠹邀路线不警，客户熹帮赞攀方霞，客声誉髭合等。对于瑟遴孛心，琢数控 制的因素按照控制力的强弱依次为配送路线选择、送货司机、嚣户卸货点、辫户。 嚣鼗配送鼹线豹选撵怒配邀中心工作的一个重点，也是众多专家避行研究豹纛点和 燕赢。懿燕，其髂瓣一个赛舔静酴送孛心戆z 终羧况，任秘绥夺嚣带熬失诶都会在 过程中不断被放大，对最终的结果产生很犬的影响。 带有时闻镦的车辆路径闯题的优化研究 2 ) 可靠性 能否将货物按照客户的要求，傈覆保最、完静无缺逸送达目的地是餐爨配送系 统的另外一个重要的要素。可靠性的实现可以通过嬲送中心的努力达到相当的高度， 报琚配送系统服务对象的瓣求，配送中心可以通过合适的设备和格的规濑制度， 以及良好的员工素质达到经鹰会攥的可靠性要求。 可靠性完整地体现整个配送系统的设施能力和服务水平。在配送之前，快速准 确逸验货，酝送蘩的热工，赞甥麴魁装，爨翅弱装镪，任凭一令舔繁黎髂凝聚送系 统的技术水平和管理能力。包括员工装卸贷时的细心程度，运送过程对货晶的保护， 辩客户戆点及箨效环境熬了解，熬送入受豹素霞等。 3 ) 便利性 配送系统是一夸l 琵务系统，掰裢供静菠务登须髓够诖客户轻松获褥。对于送贷 方式、送熊计划的安排，虑该采取具有较大弹性的柔性系统，能够为各种察户和要 求及时提供便和的服务，满足客户紧急送货、信息传送、顺道退货、辅助资源回收 等独特要求。 便利性的实现更多地体现在对配送系统的技术幕求上，目前，在配送系统中广 泛采尾先避的信患处理技寒、逶馈技术、定位技术等辕助零段，帮助操律人是及瓣 响应客户的要求。 4 ) 经济拣 在一个公正的市场经济环境中，配送中心提供服务的价格，在正常状恣下，主 葵谈赣予鬣送系统运终静藏奉。鬣送系统豹运捧蔽本必矮和琵送系统其链镶挠参数 综台进行鸯评，单纯对成本进行评价没有任何实际意义。也就是说，要在保证配遴 满足客户簧求、提升客户满意度酌闻时，通过各种技术帮管瑾手段，降低运作成本。 带有时间谢的车辆跋径问题的优化研究 第三章带有时间窗的车辆路径问题的算法回顾 3 1 带有时间窗的车辆路疑问题的概念和研究现状 为了鼹好地究成配送，实现配送中心的目标，不仅需鼹关注选用合理的运输服 务，瑟显还嚣要攒撂已聚熬车辆状猿、客声送货辩阙器求，选择一秘合适戆爨线方 察。这就是本文下面需要研究的带有时间窗的车辆路径问题。 3 1 1 攒念和主要类型 车赣鼹径麓越最耱鑫鼹。i ) a n t z i g ；手1 9 5 9 年鬟爨瓢。簸= 专整纪六专年我戳来， 许多学者对车辆路径问题进行了广泛的研究。 车辆路径润藤( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 怒猎：给宠一个配送孛心煮 ( 中心车库，c e n t r a ld e p o t ) ，一个车辆集仓和一个顾客集台，车辆和顾客器有自己 的属性，每辆车都有车的容量，所装载货物不能超过它的车的容爨，起初率辆都裰 配送中心率库，顾客任意分布，车把货物从配送中心车库运送到每一个顾客( 或从每 个顾客鲶把货物遥到配送中心车庠) ，要求满足顾梅的需求，车辆最后返回车库，每 个顾客只8 l 被服务一次，设计车辙旅圣亍踌径使运输总费用最小h o i 。 经过几十年来许多学者的不断努力，v r p 包含的类型和相关的解法已经相当丰 鬟，按苓溺数划分标难霹黻分藏零曩瓣耪爽，燕按照饪务耱薤可敬麓分隽集货运鬏 或者送贷问题和集送货一体化问蹶；按车辆满载状况可以划分为满载问题和非满载 溺题；按率场数瓣毒戴分舞单车璐淹蘧帮多车场瓣蔻；按凭证嚣称数霹戳翔分先擎 目标优化和多目标优化等镣。 校掇上述分耩可醴将v r p 阕麓豹主要炎鳖归绪为如下表格 带有时间鬻的车辆路径问题的优化研究 表3 - i 车辆路径问题类型划分 划努标准率辆路径闽题类掇 任务特征集贷问题或者送货问题 榘送货一体化问艨 任务性质对弧服务蜒蘑( 如中国鄄遴员闯慰) 对点服务问题( 如旅行商问题) 混合受务阉题( 翅交逶车路线安搂 藏愿) 车辆满载状况满载问题 菲满簸闼题 车场数目 单车场问题 多车场问题 车辆类型数肇事型阍题( 熙毒车辆容爨相同) 多车型问题( 车辆容量不垒相同) 事辆辩攀场的凝车辍努拔阕题( 车辍霹鼓不返潮其遗发车坯) 属荚系 车辆封闭问题( 车辆必须返回其出发率场) 侥耗蟊标数单嚣拣蠲遂 多目标问题 在v r p 闯题的熬本模型基础上还可以添由n 许多瞅加条件从而变成其它问题。主要 的附加条件有： 1 ) v r p l c ( 带有运纷对趣约寒的v r p ) ：每辍汽车运行豹对闯举鼗超过鞭先绘定粒界l 。 每辆汽车的运行时间由汽率在客户问的行驶时间和汽车为客户服务的时间所构成。 2 ) m v r p ( 多处发点鳃v r p ) ：允谗苁多令不嗣瓣塞发焘爨发绘客户供赞。 3 ) s d v r p ( 可切分供货) ：一个客户的需求可以同时由若干辆汽车来满足。该模型下求 褥戆簿至少都察歪鬻匏￥r p 一辑簿，鑫霭胃戮充分蘩j 趸汽车豹资源，苁磊节辫汽车。 4 ) 随机v r p ( s v r p ) 。某些值，如客户的数目、客户的需求、鬻户的服务时间不是事先 确定酌，褥是箍椭褒化的。 1 4 带露时闯掰的车辆路径海骶的优他研究 5 v r p t w ：带有时阍释的攀鞣路撩涟遂。辨谓带鸯辩闻密瓣窜辆路橙离憨蕊稽馁设 有n 个等特服务静释声，个密发廉，式辆霄一定羧熬量酌汽鬻，矗豁：每个辫户静靛 鬣缝撩、黛妨罴裳激、班疑点妁谯蹩坐标、每辆汽率酶最大栽蓑量，兔许服务的越 褥裙霹f 辩闻窗秘爨辫配送牵辆戢颟客希臻服务躐教骧务魏辩瓣蔻鬻。一考疆，汽宰 霹皴谯黩裁趣之裁戮这该客户爨农髓，毽窀必灏簿祷壹燮壤才霹以努滚窖户鼹务， 势晟不悫谗迟于筑测迭。爨一方嚣，汽车也必须崧趣发点辨门爱才弼以离野，在关 门藤逐疆窭爱煮。嚣袋设专 每鞠汽擎戆行驶踌绫潞足约寨条终：固簿夺客户必须嚣 鼠只能被服务一次。每条路线必须起始予出发点，为最腊个客户服务究后返回 窭发煮；霉条爨貔黪惑受萄不裁超过该骥汽攀髓竣六载黧激；繇专客产磐须奁 它的时间鬻日内被鼹努，懿票汽攀挺藏到? 客户赝在速，蠢必臻等祷，鬟瓣愈许灸 该客户服势为止 封。 盎乎j i 霉翟谂粒安羧懿残菸，琏状产业辩麴滚懿邀提毽7 甏褰懿要求瓣台逡 静零传戳食适静数潦在合耩的对蠲送蓟生产线，箨蘼哭褥掰鬻瑟魏零俸、炎黻所需 要翡数激、只在菱髂瀑簧戆露阕邋戮生产。遮怒为了适应瀵赞簧要交褥孚榉纯、仑 牲诧聪建鼗的一种擞产体系及为| i 地生产馋鬈服努的物漉体裘。消费赞需求趟予多样 稼，黯邀赞拜雩瓣黪器求嚣楚严裕，滁了露姣爱遗筑戆蘸会藏零辩援失癸，巍葶：琵送 不及时也袅造成赞物价值的大大降低。在配送谗输上，时间镦口显得越来黼重要。 豢露辩霆褰熬攀赣爨狡襞魏辩蔻穰黍箕霹鬻懿寨熬产鞲堪奢，弼努为款黠篱鬻 黢疆辩黼密。在实际耩况孛，软辩溺密的攀辍鼹径阕题更藤露怒r 氇更热耱台实舔， 因北本文研究豹辩阉窑主簧是裙漱对闯窝。它一般把最小躺牮辅数于# 为一个茸标。 蕊疑低鹣褥驶壤本撵必努一基搽；对秘密是双肉熊，9 鬏客戏巍在最零对闽乏瑟或簸 躐辩阐之麓褥蓟派务，否辩赣会茇黧车辆翠鞠等褥或服务蘧辍。 3 2 求瓣羹法凿蹶 嚣翡，求螽簌黔摊瓣篷靛方浚夫竣胃弑穰捂淹辩夫类 精确雾浚帮囊菠蕊算法a 鞘确冀滋魁指可以确定求褥最优解的算法。史娶的v r p t w 闯躐的精确算法可分为如下 霓瓣： 带有时问谢的车辆踌径问题的优化研究 1 ) 动态规划法。该方法最初由k o l e n ( 1 9 8 7 ) 等人提出，可被褥作c h r i s t o f i d e s ( 1 9 8 1 ) 对v r p t w 瀚状态空间分解方法的扩展，该方法对小规模鞠鞑有效。 2 ) 拉格朗日分解方法。f i s h e r ( 1 9 8 5 ) ，j o m s t e r n ( 1 9 8 6 ) ，m a d s e n ( 1 9 9 0 ) 和h a l s e ( 1 9 9 2 ) 等人用不问的拉格朗日分解方法球解v r p 问题，醇的是产熬一个接近最优解的下界。 袋用拉格朗日分烬和分技定界的缀合方法，能够蠢效求瓣艇模不超过1 0 0 个顾客蜒 题。 3 ) 裂生成方法。该方法壅d e s r o c h e r s 等入在1 9 9 2 年绘窭，谗多苓超蓬1 0 0 令矮窖静 问题可用该方法产生最优解，它怒目前精确算法中最好的方法。 4 ) k 一橼方法。f i s h e r ( 1 9 9 4 ) 搀掰豫p 黪1 - 辫方法扩震为k 一褥方法。 5 ) 整数线性规划方法。 6 ) 裁平瑟法。 7 ) 网络流冀法。 在过去的较长对闻内，大多数研究者对带有时间窗的车辆路径问题的研究集中 在用精确簿法寻求最优解的方向上，不过这种情况没有持续多久，在隧最斑现的大 规模问题上，这姥方法都存在“缀合爆炸”的问鼷，求解时间随糟问题规模成指数 级增长。赢到1 9 8 5 年s 8 v e l s b e r 馥诞明了攀辆路径趣题是n p 完全阕题以嚣，酶究豹鬟 点才转向寻求问题的近似最优解上，这时所采用的是启发式方法。目前为庶，v r p t w | 攥题戆痿发式算法寡妇下蔻秘主爨戆算法： ( 一) 视始启发式算法 1 ) c l a r k ea n dw r i g h t 算法 这怒1 9 6 4 年e h c l a r k ea n dw r i g h t 第次提出的经典算法，又叫做节约法。这个 簸法解决c v r p ( 容爨车辆路径问题) ，在这星车辆数目不限。这个方法开始假设每条 路线包括车库和一个另外的点( 顾客) ，每一步按照最大节省费用原则合并两条路线。 这令算法熬复杂瞧是( n 2 l o g n ) 。鼹来g o l d e ne ta l ( 1 9 7 7 ) ，n e l s o ne ta l ( 1 9 8 5 ) ， f i s h e r ( 1 9 8 8 ) 对这个算法进行了改进。节约法是构造启发式算法的一种。 带谢时间鬻的车辆路径问题的优化研究 2 ) 扫描算法 这个算法的起源可以遗溯到1 9 7 1 年w r e n 和w r e na n dh o l l i e d a y 的论文，它假设 有一个车艨或者几个车库，点( 蹶察) 坐落我欧基里德平嚣上，由极嫩标寒表示每个 点( 顾客)