（管理科学与工程专业论文）时变网络环境下车辆调度问题研究.pdf

西南交通大学博士研究生学位论文第1 页 摘要 我国十一五规划中将现代物流业作为今后重点发展领域，提出到2 0 1 0 年全 社会物流成本下降2 3 个百分点。运输配送是影响物流总成本的重要因素，大 约占物流成本的6 0 。作为物流系统优化中关键的一环，物流配送车辆的优化 调度问题成为研究的热点。在以往的静态车辆调度问题( v e h i c l er o u t i n g p r o b l e m ， 简写v r p ) 研究中，车辆路径安排大部分都是基于确定性的信息，其中包括需求 确定、车辆位置确定和车辆在路途的行驶时间确定，尤其考虑车辆在任意两节 点( 顾客或车场) 间的运行成本( 时间) 只取决于节点间的距离，通常被认为是已知 且静态的常量。但在实际的车辆行驶过程中，由于交通管理、交通流量、交通 事故、天气变化、上下班高峰期等因素的影响，车辆的行驶速度总是处在不断 变化之中，从而导致了路网中各个路段上的运行成本( 时间) 也相应地发生变化。 这种动态变化的情况，静态v r p 问题的理论和方法已无法适用，这就使得对时 变网络v r p 问题的研究成为迫切需要。本论文主要以时变网络v r p 的三类子 问题作为研究对象，分别是基于时段的时间依赖型旅行商问题( t i m ed e p e n d e n t t r a v e l i n gs a l e s m a np r o b l e m ，简写t d t s p ) 、基于具体位置的t d t s p 问题和时间 依赖型车辆调度问题( t i m ed e p e n d e n tv e h i c l er o u t i n gp r o b l e m ，简写t d v r p ) 。主 要研究内容如下： 第l 章首先介绍了论文所要研究问题的来源及研究目的，进而分析了时变 网络v r p 问题的背景和研究意义，并描述了本文即将讨论的三类子问题的研究 特点，最后指出了本文的技术路线和主要研究工作。 第2 章在对大量相关文献进行总结提炼的基础上，综述时变网络v r p 问题 的研究现状。描述了目前对时变网络问题的研究情况，并对已研究的时变网络 v r p 问题进行分类，总结了时变网络特性处理方法的研究现状。在求解算法方 面，对静态v r p 问题和时变网络v r p 问题的求解算法进行综述，并引入本文 将用于求解时变网络v r p 问题的大规模邻域( v e r yl a r g es c a l en e i g h b o r h o o d ，简 写v l s n ) 搜索技术，最后指出现有文献中存在的问题及进一步需要研究的方向。 第3 章以基于时段的t d t s p 问题作为研究对象，描述该问题的特征与性质， 提出一种满足先入先出( f i r s ti nf i r s to u t ，简写f i f o ) 准则的时变网络特征处理方 法，建立问题的数学模型，并给出传统的动态规划启发式算法求解策略。在求 第1 i 页西南交通大学博士研究生学位论文 解算法上，采用一种基于v l s n 搜索技术的动态搜索算法求解该问题。通过实 验比较不同算法的性能，并对算法性能进行分析。 第4 章以基于位置的t d t s p 问题作为研究对象，描述该问题的特征与性质， 建立问题的数学模型。在求解算法上，同样采用一种基于v l s n 搜索技术的动 态搜索算法求解该问题。通过实验比较不同算法的性能，并对算法性能进行分 析。 第5 章以t d v r p 问题作为研究对象，描述该问题的特征与性质，提出一 种满足f i f o 准则的时变网络特性处理方法，建立问题的数学模型，并给出传统 的最近邻算法求解策略。在求解算法上，采用一种基于v l s n 搜索技术的动态 规划启发式算法和环状交换算法分别求解该问题，共有五类策略。通过实验比 较不同算法的性能，并对算法性能进行分析。 第6 章以成都某物流企业的配送作为背景，收集实际数据，建立该企业配 送的数学模型。通过实际数据分析，对配送环境进行合理假设，得出不同情形 下的最优配送路线，该路线同样也是本论文中所提算法的计算结果。该实际案 例为本文所提算法的有效性提供了一个很好的实际验证背景，为企业配送作出 满意决策。 结论部分对论文内容进行了全面的总结，指出了进一步研究的方向。 关键词：车辆调度问题；时变网络；时间依赖；大规模邻域 西南交通大学博士研究生学位论文第1 i i 页 a b s t r a c t i nc h i n a sllt hf i v e y e a rp l a n w et a k em o d e ml o g i s t i c si n d u s t r ya sa k e y d e v e l o p m e n ta r e ai nf u t u r e ，a n dp u tf o r w a r dt h a tb y2 0 10t h ew h o l es o c i e t a l l o g i s t i c s c o s tw o u l db er e d u c e d2 - 3 p e r c e n t a g ep o i n t s t r a n s p o r t a t i o na n dl o g i s t i c s d i s t r i b u t i o na r et h em a i nf a c t o r st h a ta f f e c tt h et o t a l l o g i s t i c sc o s t w h i c ha c c o u n tf o r t h el o g i s t i c sc o s to fa r o u n d6 0 a sak e yr o l eo fl o g i s t i c so p t i m i z a t i o n t h e v e h i c l e so p t i m a ls c h e d u l i n gp r o b l e mh a sb e c o m et h eh o tr e s e a r c ht o p i c s i nt h e p a s ts t a t i cv e h i c l er o u t i n gp r o b l e m ( v r p ) s t u d y , v e h i c l em u t i n ga r r a n g e m e n t sa r e m o s t l yb a s e do nc e r t a i ni n f o r m a t i o n ，i n c l u d i n gt h ec e r t a i nd e m a n d t h ec e r t a i n v e h i c l el o c a t i o na n dt h ec e r t a i nd r i v i n gt i m eo fv e h i c l e s e s p e c i a l l yt h eo p e r a t i n g c o s t ( t i m e ) b e t w e e na n yt w op o i n t s ( c u s t o m e r so rd e p o t ) o fv e h i c l e si sc o n s i d e r e d d e p e n d i n go nt h ed i s t a n c eb e t w e e np o i n t s ，w h i c hi su s u a l l yr e g a r d e da sk n o w na n d c o n s t a n t w h i l ei nt h ea c t u a lt r a f f i cp r o c e s s ，t r a f ! f i cm a n a g e m e n t t r a f f i cf l o w , t r a f f i c a c c i d e n t s ，w e a t h e rc h a n g e s ，a n dt h er u s h i n gh o u r sw i l lc h a n g et h ed r i v i n gs p e e d c o n t i n u a l l y , i tl e a d st h eo p e r a t i n gc o s t ( t i m e ) i nt h er o a dn e t w o r kc o r r e s p o n d i n g l y v a r y s ot h et h e o r ya n dm e t h o d sf o rs t a t i cv i 冲a r eu n a b l et oa p p l yt ot h ed y n a m i c e n v i r o n m e n t t h i sm a k e st h es t u d yo fv l 冲i nt i m e v a r y i n gn e t w o r ku r g e n ta n d n e c e s s a r y i nt h ed i s s e r t a t i o n ，w et a k et h et h r e es u b p r o b l e m so ft i m e v a r y i n g v r p sa ss t u d yo b j e c t s t h e ya r et i m ed e p e n d e n tt r a v e l i n gs a l e s m a np r o b l e m ( t d t s p ) b a s e do nt i m ep e r i o d ，t d t s pb a s e do np o i n tp o s i t i o na n dt i m ed e p e n d e n tv e h i c l e r o u t i n gp r o b l e m ( t d v r p ) t h em a i nc o n t e n t so ft h i sd i s s e r t a t i o na r el i s t e da s f o l l o w s ： i nc h a p t e rl ，w ef i r s ti n t r o d u c et h es o u r c ea n dp u r p o s eo ft h es t u d y i n gp r o b l e m ， t h e na n a l y z et h eb a c k g r o u n da n ds i g n i f i c a n c eo fv i 心i nt i m e - v a r y i n gn e t w o r k a n d d e s c r i b et h ec h a r a c t e r i s t i c so ft h et h r e es u b p r o b l e m st ob ed i s c u s s e d f i n a l l yw e c o n c l u d et h et e c h n i c a l l i n ea n dt h em a i nr e s e a r c hw o r k i nc h a p t e r2 ，w es u m m a r i z et h es t u d ys t a t u sq u oo ft i m e - v a r y i n g 馄只b a s e do n t h el a r g en u m b e ro fr e l e v a n tl i t e r a t u r e ，b yc l a s s i f y i n gt h es t u d i e dt i m e - v a r y i n gv i 冲s ， a n ds u m m i n g u pt h em e t h o d sf o rd e a l i n gw i t ht i m e v a r y i n gc h a r a c t e r i s t i c s 。 腑a l s o r e v i e wt h ea l g o r i t h mf o rs o l v i n gt h es t a t i cv r pa n dt i m e - v a r y i n gv r p , a n di n t r o d u c e t h ev e r yl a r g es c a l en e i g h b o r h o o d ( v l s n ) s e a r c ht e c h n o l o g yi s s u e st ob eu s e df o r t i m e - v a r y i n gv r p si nt h i sd i s s e r t a t i o n f i n a l l yw ec o n c l u d et h ed e f i c i e n c yo ft h e e x i s t i n gl i t e r a t u r e sa n dt h ef u r t h e rn e c e s s a r yr e s e a r c hd i r e c t i o n 第页西南交通大学博士研究生学位论文 i nc h a p t e r3 w et a k et d t s pb a s e do nt i m ep e r i o da sar e s e a r c ho b j e c t ， d e s c r i b i n gt h ec h a r a c t e r i s t i c sa n dt h en a t u r eo ft h ep r o b l e m ，a n dd e v e l o p i n ga l l a p p r o a c ht od e a lw i t ht i m e v a r y i n gc h a r a c t e r i s t i c sw h i c hs a t i s f i e sf i r s ti nf i r s to u t ( f i f o ) p r o p e r t y b a s e do ni t ，w ee s t a b l i s ht h em a t h e m a t i c a lm o d e l ，a n dg i v et h e t r a d i t i o n a ld y n a m i cp r o g r a m m i n gh e u r i s t i cs t r a t e g y , a n dt h e nw ea d o p tt h e d y n a s e a r c ha l g o r i t h mb a s e do nv l s ns e a r c ht e c h n o l o g yf o rs o l v i n gt h ep r o b l e m t h r o u g he x p e r i m e n t sw ec o m p a r et h ep e r f o r m a n c eo fd i f f e r e n ta l g o r i t h m s ，a n d a n a l y z et h ea l g o r i t h mp e r f o r m a n c e i nc h a p t e r4 ，w et a k et d t s pb a s e do nt h ep o i n tp o s i t i o na sar e s e a r c ho b je c t ， d e s c r i b i n gt h ec h a r a c t e r i s t i c sa n dt h en a t u r eo ft h ep r o b l e m ，a n de s t a b l i s h i n gt h e m a t h e m a t i c a lm o d e l b a s e do ni t ，w ea l s oa d o p tt h ed y n a s e a r c ha l g o r i t h mb a s e do n v l s ns e a r c ht e c h n o l o g yt os o l v et h ep r o b l e m t h r o u g he x p e r i m e n t sw ec o m p a r et h e p e r f o r m a n c eo f d i f f e r e n ta l g o r i t h m s ，a n da n a l y z et h ea l g o r i t h mp e r f o r m a n c e i nc h a p t e r5 ，w et a k et d v 即a sar e s e a r c ho b j e c t ，d e s c r i b i n gt h ec h a r a c t e r i s t i c s a n dt h en a t u r eo ft h ep r o b l e m ，a n dd e v e l o p i n ga na p p r o a c hf o rd e a l i n gw i t h t i m e v a r y i n g c h a r a c t e r i s t i c sw h i c hs a t i s f i e sf i f op r o p e r t y b a s e do ni t ，w e e s t a b l i s ht h em a t h e m a t i c a lm o d e l ，a n dg i v et h et r a d i t i o n a ln e a r e s tn e i g h b o r h o o d h e u r i s t i c f o rt h ea l g o r i t h m ，w ea d o p tt h ed y n a m i cp r o g r a m m i n gh e u r i s t i c sa n d c y c l i ct r a n s f e ra l g o r i t h mb a s e do nv l s ns e a r c ht e c h n o l o g yt os o l v et h ep r o b l e m t h e r ea r ea l lf i v e s o l v i n gs t r a t e g i e s t h r o u g he x p e r i m e n t s w ec o m p a r et h e p e r f o r m a n c eo fd i f f e r e n ta l g o r i t h m s ，a n da n a l y z et h ea l g o r i t h mp e r f o r m a n c e i nc h a p t e r6 ，w et a k et h ed i s t r i b u t i o no p e r a t i o no fo n el o g i s t i c se n t e r p r i s ei n c h e n g d ua s a b a c k g r p u n d ，b yc o l l e c t i n g t h ea c t u a ld a t aa n de s t a b l i s h i n gt h e e n t e r p r i s ed i s t r i b u t i o nm o d e l t h r o u g ht h ea c t u a lc o l l e c t i o nd a t aa n da n a l y s i s ，w e g i v es o m er e a s o n a b l ea s s u m p t i o n sf o rd i s t r i b u t i o n b a s e do ni t ，w eg e tt h eo p t i m a l d i s t r i b u t i o nr o u t e si nv a r i o u ss i t u a t i o n s ，w h i c hi sa l s ot h er e s u l to fa l g o r i t h m s m e n t i o n e di n t h i sd i s s e r t a t i o n t h ec a s ep r o v i d e sag o o da c t u a lb a c k g r o u n df o r v e r i f y i n gt h ea l g o r i t h m s e f f i c i e n c y f r o mi t ，w ec a nm a k et h es a t i s f a c t o r yd e c i s i o n f o rt h ee n t e r p r i s e i nc o n c l u s i o n ，w es u m m a r i z et h ed i s s e r t a t i o nc o n t e n ta n dp r o s p e c tt h ef u t u r e o r i e n t a t i o no ft h ep r o b l e m k e y w o r d s ：v e h i c l er o u t i n gp r o b l e m ；t i m e - v a r y i n gn e t w o r k ；t i m ed e p e n d e n t ；v e r y l a r g es c a l en e i g h b o r h o o d 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权西南交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩微或扫描等复制手段保存和汇编本学位论文。 本学位论文属于： 1 保密口，在年解密后使用本授权书； 2 不保密影使用本授权书。 学位论文作者虢籼哼 日期：c ) 0 0 3 年f 土月f 6 日 指导教师签名： 卜 多多 日期：c ；k 矿年f 胡以1 1 3 西南交通大学 学位论文创新性声明 本人郑重申明：所呈交的学位论文，是本人在导师指导下独立进行研究所 得的成果。除文中已经注明引用的内容外，本论文不包括任何其他个人或集体 已经发表或撰写过的研究成果。对本论文的研究做出贡献的个人和集体，均已 在文中作了明确的说明。本人完全意识到本申明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 对基于时段的时间依赖型旅行商问题( t i m ed e p e n d e n tt r a v e l i n gs a l e s m a n p r o b l e m ，简写t d t s p ) 币i 时间依赖型车辆调度问题( t i m ed e p e n d e n tv e h i c l er o u t i n g p r o b l e m ，简写t d v r p ) 提出一种满足先入先出( f i r s ti nf i r s to u t ，简写f i f o ) 准则 的时变网络特性处理方法计算车辆在任意跨时段( 单时段、多时段) 所对应路段的 行驶时间，推导出的公式中不含路段距离和车辆的行驶速度，操行性强。( 对应 论文第3 章第2 节和第5 章第2 节) 2 针对基于时段的t d t s p 问题和基于位置的t d t s p 问题，构造了基于大 规模邻域( v e r yl a r g es c a l en e i g h b o r h o o d ，简写v l s n ) 搜索技术的动态搜索算法 d s k - o p t ( k = - 2 ，2 5 ，3 ) 。该算法采用动态规划搜索多个独立的k - o p t 移动，能在多 项式时间内搜索到指数大小的邻域。算法性能优于目前在邻域搜索领域求解此 类问题最有效的动态规划启发式算法。( 对应论文第3 章第4 节和第4 章第3 节) 3 针对t d v r p 问题，构造了基于v l s n 搜索技术的动态规划启发式算法 和环状交换动态规划算法。动态规划启发式算法通过设置参数平衡解质量和算 法运行时间，扩大了最近邻算法的邻域空间，且缩短了动态规划精确算法的运 行时间。环状交换动态规划算法采用一种顾客能在多辆车之间进行交换的策略， 打破传统只能对某辆车路线进行优化的思想，将搜索空间进一步扩大。为了保 证原有路线的最佳性和环状交换的可行性，构造了两类改进策略：带有虚拟顾 客的改进环状交换策略能使交换过程更加柔性化；底层嵌入i n s e r t 的改进策略能 在保证解质量的前提下缩短算法运行时间。( 对应论文第5 章第4 - 一6 节) 名 及 学位论文作者签名：才婀嵫 日期：如p kk 西南交通大学博士研究生学位论文第1 页 第1 章绪论 随着世界经济的快速发展和现代科学技术的进步，物流产业作为国民经济 中一个新兴的服务业，正在全球范围内迅速发展。在国际上，物流产业被认为 是国民经济发展的动脉和基础产业，其发展程度成为衡量一个国家现代化程度 和综合国力的重要标志之一，被喻为促进经济发展的“加速器 、产业结构演 变的“润滑剂和现代企业的“第三利润源泉”。目前我国的物流业尚处于起 步阶段，与发达国家存在很大差距，物流运作成本较高。2 0 0 5 年中国物流总费 用高达3 3 8 6 0 亿元，占g d p 的1 8 6 ，而美国等发达国家物流成本约占g d p 的1 0 ，这表明中国物流业整体水平严重落后，过高的物流成本消耗严重削弱 了企业的市场竞争能力j 。对于我国，降低1 的物流成本相当于多出2 0 0 0 亿 的经济效益。因此，通过提高物流管理水平，降低物流成本，可为企业及社会 带来可观的经济效益，提高国际竞争力。近年来国家和各地政府纷纷制定了各 种有利于物流发展的政策和计划，在国家的“十一五规划”中将“大力发展现 代物流业作为今后重点发展的领域，明确提出到2 0 1 0 年，全社会物流成本要 在2 0 0 4 年的基础上下降2 3 个百分点【lj 。 现代物流不仅在国民经济的合理布局、社会资源的优化配置、减少流通环 节、加速资金周转、促进社会分工以及加速生产的集中化、规模化等方面起着 积极的作用，而且还贯穿于企业生产和经营的全过程，企业物流合理化作为“企 业脚下的金矿 、“企业的第三利润源泉”，已成为当前企业最重要的竞争领 域。甚至有人认为，在2 1 世纪，谁掌握了物流，谁就掌握了市场。目前，许多 发达国家和地区已形成了比较成熟的物流管理概念，先进的物流技术和高效的 物流运营系统。进入2 l 世纪的中国，必将加快现代物流的发展，以此增强企业 竞争力，优化资源配置，提高经济运行质量，实现中国经济体制与经济增长方 式的两个根本性转变，从而推动中国经济的持续健康发展。 当前自然科学与社会科学飞速发展，边缘科学不断出现，学科之间的相互 交叉、相互融合越来越显著。物流作为一门综合学科，正是借鉴运用了运筹学、 技术工程学、系统工程、计算机和网络等学科的方法和技术成就，获得了蓬勃 的生命力，取得了长远的发展。所蕴含的巨大潜力已经越来越引起人们的注意， 挖掘物流潜力，已成为代表社会总体效益、现代化程度的重要指标之一。 第2 页西南交通大学博士研究生学位论文 作为物流系统优化中关键的一环，物流配送车辆的优化调度问题( v e h i c l e r o u t i n gp r o b l e m ，简写v r p ) 研究受到了人们的广泛关注，各国学者对其理论和 应用进行了大量的研究工作，取得了数以千计的研究成果。c a n e n 和s c o t t 将 肿问题称为“最近十年运筹学领域最成功的研究之一”【2 1 。许多学者认为v r p 问题的成功归因于理论和实践的紧密联系，具有学术背景的运筹学学者不仅设 计和改进了形式多样的模型和算法，而且对推动路径系统在实际中的应用也起 到重要作用；另一方面，由于符合生产需要的计算机软件的成功研制，工商业 者对v r p 问题的重视也日益加强。 本章中首先介绍了论文所要研究问题的来源及研究目的，进而分析了时变 网络v r p 问题的背景和研究意义，并描述了本文即将讨论的三类子问题的研究 特点，最后指出本文的技术路线和主要研究工作。 1 1 问题的研究目的及意义 1 1 1 问题的来源及研究目的 本论文的研究课题来源于国家自然科学基金项目具有时变特性的有害物 品运输的路径问题研究( 7 0 4 7 1 0 3 9 ) 、国家社科基金基于e p r 的循环经济决 策问题研究( 0 7 b j y 0 3 8 ) 、教育部新世纪优秀人才支持计划项目( n c e t 一0 4 0 8 8 6 ) 和四川省教育厅自然科学基金项目基于i l s 智能优化方法求解动态v r p 问题 研究( 2 0 0 5 8 0 2 5 ) 。 时变网络v r p 问题是广泛存在于物流配送、交通运输管理工作中的一类问 题。本论文在查阅现有文献，并对实际物流企业进行调研的基础上，对时变网 络v r p 问题的时变网络特性进行详细分析，并根据该特性重点研究三类典型时 变网络冲问题( 依赖于时段的时间依赖型旅行商问题( t i m e d e p e n d e n tt r a v e l i n g s a l e s m a np r o b l e m ，简写t d t s p ) 、依赖于具体位置的t d t s p 问题和时间依赖型 车辆调度问题( t i m e d e p e n d e n tv e h i c l er o u t i n gp r o b l e m ，简写t d v r p ) ) ，分别对以 上三类问题的研究现状进行综述，描述各自的特征与性质，提出满足先入先出 ( f i r s ti nf i r s to u t ，简写f i f o ) 准则的时变网络特性处理方法，并进行理论推导证 明。该方法能够解决跨多时段问题，其应用范围更加广泛。在对以上三类问题 时变特性、约束条件和目标函数进行分析和数学描述的基础上，分别建立对应 的数学模型，从而为构造其求解策略和算法奠定基础。 西南交通大学博士研究生学位论文第3 页 在求解算法上，本论文采用基于大规模邻域( v e r yl a r g es c a l en e i g h b o r h o o d ， 简写v l s n ) 搜索技术的智能优化算法的通用框架为基础，结合以上三类问题的 特点引入一些新的技术设计求解算法，进而通过数值试验对算法性能进行分析。 论文最后以成都某物流企业的配送作为背景，收集实际数据，并建立该企 业配送的数学模型。通过对实际配送环境进行合理假设，得出在不同情形下的 最优配送路线，该路线同样也是本论文中所提算法的计算结果。该实际案例为 本文所提算法的有效性提供了一个很好的实际验证背景，为企业配送作出满意 决策。 1 1 2 问题研究意义及问题描述 1 1 2 1 时变网络v r p 问题研究意义 运输是现代生产企业和物流管理中最重要的一个环节。而车辆调度是运输 问题中最关键的技术。有效地调度车辆i 不仅可以提高物流工作效率，而且能 够为生产工序之间的物料传送得到运输上的保障，从而实现物流管理科学化。 v r p 问题不但直接存在于物流管理当中，而且很多实际生产调度也可以间接归 结为该问题，一直是运筹学与组合优化领域的热点研究课题。该问题可描述为： 对一系列装货点或卸货点，组织适当的行车路线，使车辆有序地通过它们，在 满足一定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行 驶里程限制、时间限制等) 下，达到一定的目标( 如路程最短、费用最少、时间最 少、使用车辆数最少等) 【3 】。 自1 9 5 9 年著名学者d a n t z i g 和r a m s e r l 4 】首次提出v r p 问题后，国内外的众 多学者从不同角度对该问题进行了大量的研究，相关的文献资料非常多。为了 能够全面系统地了解v r p 问题的结构，以下从不同的角度对该问题进行分类。 1 优化目标 最常见的v r p 问题目标有以下几类： 最小化运输成本最小化行驶距离最小化行驶时间最小化使用的车辆数最 小化顾客的等待时间最大化利润 目标函数可以是以上的单个目标，也可以是由两个或两个以上组合形成的 多目标函数，如带有车队的v r p 问题目标函数是最小化行驶距离与最小化使用 的车辆数的组合；带有利润的v r p 目标函数是最小化行驶距离与最大化利润的 组合等。 2 车场 第4 页西南交通大学博士研究生学位论文 车场的数量：单车场多车场 车场的封闭性：封闭( 车辆必须返回其出发车场) 开放( 车辆可以不返回其出 发车场) 3 车辆 车辆数：单车多车 容量：容量不限容量相同容量不同 车型：单车型问题多车型问题 载货状况：满载问题( 货运量不小于车辆容量，完成一项任务需要多辆车) 非满载问题( 货运量小于车辆容量，多项任务由一辆车完成) 行驶里程：无行驶里程约束多车具有相同行驶里程约束不同车具有不同行 驶里程约束 4 需求 需求对象：弧需求( 如中国邮递员问题) 点需求( 如旅行商问题) 混合需求( 如 交通车路线安排问题) 需求行为：配送需求收集需求配送和收集混合需求 需求确定性程度：确定性需求随机需求其它不确定性需求( 如模糊需求) 需求稳定性：静态需求动态需求 时间需求：无时间窗软时间窗硬时间窗 需求计划性：单计划期多计划期无穷计划期 5 网络特征 网络方向性：无向网络有向网络混合网络 网络稳定性：静态动态 以上是对v r p 问题中各要素划分的一个归纳和总结。实际中的v r p 问题 很可能是以上要素的不同组合。而对实际v r p 问题的研究大多是经过抓住其主 要特征，忽略其次要特征简化处理的。 在第5 种分类中，根据网络稳定性可将v r p 问题分为静态v r p 问题( s t a t i c v e h i c l er o u t i n gp r o b l e m ，简写s v r p ) 和动态v r p 问题( d y n a m i cv e h i c l er o u t i n g p r o b l e m ，简写d v r p ) 。d v r p 研究范围较广，需求不确定、网络性能不确定、 服务车辆不确定、提供数据有偏差引起的问题都属于d v r p 问题的研究范畴【5 】。 由于v r p 问题为n p 难题，目前大部分的学者对v r p 的研究仅限于s v r p ，在 d v r p 领域的研究非常少，文献【6 】、 7 对动态v r p 问题进行了综述。在该领域 中目前研究较多的是由需求不确定引起的问题，而由网络性能不确定引起的问 题研究还比较少。时变网络v r p 问题实质正是由网络性能不确定引起的d v r p 西南交通大学博士研究生学位论文第5 页 问题，它属于d v r p 的研究范畴。 在以往的v r p 问题研究中，车辆路径安排大部分都是基于确定性的信息， 其中包括需求确定、车辆位置确定和车辆在路途的行驶时间确定，尤其考虑车 辆在任意两节点( 顾客或车场) 间的运行成本( 时间) 只取决于节点间的距离，通常 被认为是已知且静态的常量，在路径安排和实施过程中不会发生变化。但在实 际的车辆行驶过程中，由于交通管理、交通流量、交通事故、天气变化、上下 班高峰期等因素的影响，行驶的速度总处在不断变化之中，从而导致了路网中 各个路段上的运行成本( 时间) 也相应地发生变化。这种动态变化的情况，若采用 传统静态网络下的冲理论和方法安排车辆路线，则将导致车辆陷入城市拥挤 的交通环境中。例如，顾客要求车辆在指定时间送货或取货，若物流公司没有 考虑交通环境随时间的变化，则车辆会在行驶过程中花去大量的时间等待，而 顾客也会在无任何车辆准确到达时间的情况下等待。显然传统静态网络下的 冲问题理论和方法已无法解决，这就使得对时变网络v 】婢问题的研究成为迫 切需要。同时，随着计算机通信以及信息处理技术的不断进步和智能交通系统 的日益完善，实时获取和处理交通信息已成为可能，石建军等【8 】应用基于地理 信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，简写g i s ) 技术的节点弧段拓扑数 据模型对具有交通管制信息及实时、动态交通流信息的城市路网进行描述。宋 延掣9 j 利用智能交通系统( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ，简写i t s ) 技术建立现 代物流车辆调度信息平台。这些技术为时变网络v r p 问题研究提供了有利的条 件。 引用文献 1 0 】中的例子，图l 一1 给出了时变网络( 图a ) 和静态网络( 图b ) 之间 的差异。在该网络中，节点l 代表车场，节点2 、3 、4 代表三个客户，整个配 送过程由1 辆车完成。图( a ) 表示简单的两时段网络配送问题( 如分成0 ：0 0 - - - 1 2 ：0 0 和1 2 ：0 0 - - 2 4 ：0 0 两个时段) ，实线代表车辆在第l 时段的路段行驶时间，虚线代 表车辆在第2 时段的行驶时间，车辆在两时段的行驶时间见表1 1 。图( b ) 表示静 态网络的状况，即使是在不同时段，车辆在同一路段上行驶时间完全相同。 假设车辆在凌晨6 ：0 0 从车场( 节点1 ) 出发，则有6 条路径可以选择( 见表1 2 ) 。 在静态网络v r p 中，网络路段的运行时间是固定不变的，例中分别以 0 ：0 0 - - - - 1 2 ：0 0 ( 情形1 ) 和1 2 ：0 0 - - 2 4 ：0 0 ( 情形2 ) 两个时段的运行时间以及平均行驶 时间( 情形3 ) 作为网络的静态运行时间作比较，再将两时段相结合考虑路径运行 时间( 情形4 ) ，得到结果见表1 2 。 第6 页西南交通大学博士研究生学位论文 ( a ) 图1 1 时变网络和静态网络 表1 1 两时段路网的行驶时间 ( b ) 行驶时间( 小时) 1234 1 0 o o3 0 0 7 5 9 5 0 0 2 3 0 0 o 0 0 5 0 1 4 0 0 0 0 ：0 0 1 2 ：0 0 37 5 95 0 l0 0 04 0 1 45 0 04 0 04 0 1 0 0 0 l0 0 03 9 86 0 86 7 8 2 3 9 8 o o o7 o l 9 8 3 1 2 ：0 0 - - 2 4 ：0 0 36 0 87 0 1o 0 04 9 0 4 6 7 89 8 34 9 00 0 0 表1 2 不同情形下网络的路径运行时间 路径安排情形1情形2情形3情形4 1 2 3 4 11 7 0 22 2 6 71 9 8 51 9 6 9 1 2 _ 4 3 11 8 62 4 7 92 1 7 l1 7 9 8 1 4 2 3 12 1 62 9 72 5 6 62 2 0 9 1 4 3 2 11 7 0 22 2 6 71 9 8 51 9 9 9 1 3 4 2 11 8 62 4 7 92 1 7 l2 6 3 1 3 2 4 1 2 1 62 9 72 5 6 63 1 2 1 西南交通大学博士研究生学位论文第7 页 从表中数据可以看出，若将该网络作为静态网络考虑，不论是以某个时段 的旅行时间作为静态行驶时间，还是以平均行驶时间作为静态旅行时间，得到 的最优路径都不是作为时变网络计算得到的最优路径。时变网络下与静态网络 下的最优路径如图1 2 所示，动态网络下( 情形4 ) 的最优路径为1 2 4 3 1 ，如图 1 - 2 ( a ) 中粗线所示；静态网络下( 情形1 ) 的最优路径为1 2 3 4 1 或1 4 3 2 1 ，该 路径为对称路径，如图1 - 2 ( b ) 中粗线所示。 ( a ) ( b ) 图1 2 动态网络与静态网络的最优路径 就静态网络三种情形而言，得到的两条最优路径都是对称的，而且不存在 路段交叉的现象，这与静态网络v r p 问题的特征是完全一致的。相反地，在时 变网络中得到的最优路径不仅产生交叉现象，而且也不具有对称性，路径具有 确定的方向( 只能沿着箭头所示方向) 。这里只计算了从凌晨6 ：0 0 出发的情况， 如果在不同的时刻出发，得到的最优路径运行时间或成本又会发生变化。实际 配送网络一般都是动态变化的，若单纯简化为静态网络往往得到的不是最优路 径，使得计算成本与实际运行成本严重不符，导致资源的严重浪费。这样，在 解决时变网络v r p 问题时，既要考虑不同路线间成本的不同，也要考虑相同路 线在不同出发时间点的差异。 时变网络v r p 问题在实际许多场合中都有其原形。以下列举了几种不同情 形下的实际问题。 1 城市交通问题 城市交通问题是最典型的一类时变网络v i 冲问题。在城市交通网络中，车 辆的行驶时间会受到交通管理、交通流量、交通事故、上下班高峰期等因素的 影响而变化。行驶时间取决于一天中的具体时