（管理科学与工程专业论文）动态车辆调度问题分析及算法设计.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着物流业的蓬勃发展，特别是专业物流公司的出现，降低物流成本正 成为企业的第三利润源，这使人们越来越关注物流成本的下降。运输作为物 流两大基本主体功能之一，降低运输成本对物流成本的降低有举足轻重的作 用。动态车辆优化调度是降低运输成本的一种科学方法。随着g p s 、6 s m 、g i s 等技术的高速发展，这使动态车辆优化调度成为可能，也使研究动态车辆调 度问题具有重要现实意义。 首先，本文根据车辆调度问题的理论发展和实际需要，论述了静态车辆 优化调度问题和动态车辆调度问题的一些重要概念，并对这两类问题进行了 比较。描述了目前对动态车辆调度问题的信息处理方法以及各自的适用范 围。根据问题的动态性能和追求目标对现实中的动态车辆调度问题进行了分 类。 接着，对目前通常所用的车辆调度算法进行了详细的分类总结，并对算 法的性能进行了分析，针对动态车辆调度信息传输处理的实时性要求，论述 了g p s 、g s m 和g i s 技术的相关原理及应用。 同时，本文的核心是对动态车辆调度问题的不确定性信息进行了具体分 析，并在单车场、单车种闭合环境下建立了动态车辆调度数学模型，提出了 解决该类问题的具体算法策略。此外，还把动态调度问题的需求客户分成了 两类，并用具体数据进行了模拟求解。 最后，还对动态车辆调度系统的正常运行所需的关键技术进行了选择说 明，提出了将这三大技术应用于物流配送企业中的动态车辆调度系统的总体 设计思路以及功能模块说明。 关键词不确定信息；信息技术；混合算法；动态车辆调度 薅南交通大学硕士研究璧学位论文繁ll 蕊 a b s t r a c t w i t h 啦e e x p l o s i v ed e v e l o p m e n to fl o g i s t i c si n d a s t d ；e s p e c i a l l ya p p e a r a n c e o ft h et h i r dp a r tl o g i s t i c sc o m p a n i e s ，l o w e r i n gl o g i s t i c sc o s ti s b e c o m i n g t h i r d p r o f i ts o u r c eo fe n t e r p r i c e s , t h a tl e a dh o w t od r o pl o g i s t i c sc o s ti sc o n c e r n e d b y m o r ea n dm o r e p e o p l e s t r a n s p o r t a t i o n i s r e g a r d e d a so n eo fl o g i s t i c st w o e l e m e n t a lm a i n b o d yf u n c t i o n s l o w e r i n gt r a n s p o r t a t i o nc o s th a sg o tp l a yam a j o r r o t et ol o g i s t i c sc o s tr e d u c t i o n 。d y n a m i cv e h i c l e o p t i m i r i n gs c h e d u l i n gi sa s o r to f s c i e n t i f i ca p p r o a c ho fl o w e r i n gt r a n s p o r t a t i o nc o s t ，t h a tm a k e sd y n a m i cv e h i c l e o p t i m i z i n gs c h e d u l i n ge n a b l e i nc o m p a n yw i t h h i g hs p e e dd e v e l o p m e n to fg p s 、 g s ma n dg i s t e c h n o l o g y , a n dm a k e sr e s e a r c h i n gd y n a m i cv e h i c l er o u t i n g p r o b l e mp o s s e s si m p o r t a n t a n da c t u a ls i g n i f i c a n c e f i r s t l y , a c c o r d i n g t ot h e o r e t i c a l d e v e l o p m e n t a n da c t u a l r e q u i r e m e n t o f v e h i c l er o u t i n gp r o b l e m , t h i sa r t i c l ea c c o u n t sf o rs o m ei m p o r t a n tc o n c e p t i o n so f t h es t a t i cv e h i c l e r o u t i n gp r o b l e ma n dd y n a m i cv e h i c l er o u t i n gp r o b l e m ，a n d c o m p a r e sw i t ht h et w ot y p ep r o b l e m sc l e a r l y , d e s c r i b e si n f o r m a t i o np r o c e s s i n g m e t h o do fd y n a m i cv e h i c l er o u t i n gp r o b l e m ta n dt h e i rr e s p e c t i v e l ya p p l i c a t i o n s c o p ea tp r e s e n t b yt h e i rd e g r e eo fd y n a m i s ma n dp r i m a r yo b j e c t i v e ，c l a s s i f i e s a c t u a ld y n a m i cv e h i c l er o u t i n gp r o b l e m f o l l o w i n g ，t h i sa r t i c l ec l a s s i f i e sa n ds u m m a r i z e sc l e a r l yt ov e h i c l er o u t i n g a l g o r i t h m u s e d u s u a l l y a t p r e s e n t ，a n da n a l y s e s n a t u r e so ft h e s e a l g o r i t h m s a i m i n ga t r e a lt i m er e q u i r e m e n to fi n f o r m a t i o nt r a n s f e r i n gp r o c e s s a b o u td y n a m i cv e h i c l e s c h e d u l i n g ，t h i s a r t i c l ed i s c u s s e sr e l a t i v e l yt h e o r ya n d a p p l i c a t i o no f g p s 、g s m a n dg i s t e c h n o l o g y a tt h es a m et i m e ，t h ep i t ho ft h i sp a p e ra n a l y s e sc o n c r e t e l yt ot h eu n c e r t a i n t y i n f o r m a t i o no fd y n a m i cv e h i c l er o u t i n gp r o b l e m ，a n de s t a b l i s h e sd y n a m i cv e h i c l e r o u t i n g m a t h e m a t i c a lm o d e li ns i t u a t i o no f s i n g l ed i s t r i b u t ec e n t e r 、s i n g l ev e h i c l e t y p ea n dc o l s e dr o u t i n g t h i sa r t i c l ep u t sf o r w a r ds p e c i f i ca l g o r i t h mp o l i c yf o r s o l v i n gt h i st y p ep r o b l e m f u r t h e r m o r e ，c l i e n t so fd y n a m i cr o u t i n gp r o b l e m sa r e s e p a r a t e di n t ot w og r o u p ，a n dt h i sp a p e r s i m u l a t e sa n dc o m p u t e sf a c t u a ld a t a s f i n a l l y , t h i s a r t i c l ei l l u m i n a t e ss e l e e t l yt h ek e yt e c h n o l o g i e sr e q u i r e do f d y n a m i cv e h i c l es c h e d u l i n gs y s t e mf o rn o r m a lo p e r a t i o n ，t a k i n ga d v a n t a g eo f t h e s et h r e et e c h n o l o g y , c o m e su pw i t ho v e r a l ld e s i g nc l u e sa n df u n c t i o nm o d u l e d e s c r i l ： t i o n so fd y n a m i c v e h i c l es c h e d u l i n gs y s t e mb a s e do n p h y s i c a ld i s t r i b u t i o n 西南交通大学硕士_ 5 f 究生学位论文第1 ll 页 e n t e r p n s e k e v w o r d ：u n c e r t a i ni n f o r m a t i o n ；i n f o r m a t i o nt e c h n o l o g y ；h y b r i da l g o r i t h m ； d y n a m i c v e h i c l es c h e d u l i n g 嚣南交通犬攀矮士鞭变生学位论文第 贺 第1 章绪论 ，1 研究动态车辆调度问题的意义 交通遮输韭的发菸水平是雷家兴旺发达酶熏簧标志之一。交通运输垃拣 高速发展，促进了物资交流和人们的往来，大大地缩短了出行时间，提高了 = ：作效率。但是，由于许多原因，交通运输的离速发展使有限的道路不堪撬 受、塞车嚣霓、事敢不断，这些魂象越来邈严重蟪添撬着藿爨霹酸丈爨市。 资料表嘲，美国从】9 7 6 年至1 9 9 7 年，年车辆公溪数以7 7 的遽度上升，可 是同期激路建设罩程的增长数却仅为2 ，由于交通拥挤，人们每天消耗在上 下班豹时闼比平时平均多了1 ，5 小时，同时导致商业车辆的赋瀑，增加了避 黎藏奉。 尽管增加公路的建设速度是解决问题静一顼措施，然丽有限熊魄稠经 济制约使得道路建设不可能达到相对满意的里秘数，所以仅此项措施不能 艇决交避阅题已成为共识，现实迫使人们改变阻往单纯依靠增修道路来改蒋 交逶状况鲍愚踌，丽寻求更辩学韵方法。麓浃交暹淹蘧还应毽菇开曩羲型车 辆和运输车辆优化动恣调度管理等措施，而车辆优化动态调磷管理的实震懋 最大限殿地利用公路运输能力向避输车辆提供行驶前和行驶中的车辆行驶 臻径薅怠，及对提裁荦申交透信慰，保涯运输经务的高效率顺利完成。 还有鼹分蠹鹭使越来莛多懿人开始磅究车辆谯证蘑惫褥凄瓣蓬。 1 物流业的蓬勃发展，特别是电子商务的发展、第三方物流公司的出蕊， 根据吾方面的统计，熊物运输费用占物流营运总成本的3 5 一6 0 左右，这使 人翻越来越关注运羧环节豹工箨效枣，减少交邋糖按期事故，来更好的获得 “第三聪滤源”，强化嚣际竞争力； 2 + 幽前，动态车辆调度问题中动态路径优化在动态信息处理这方面还不 是很及时、完善，而且其模型、算法策略与现安幼态调度问题还有一段距离， 这蕊人们对裁悫车辆壤凌汉蘧存了燹大魏研究窆间； 3 。摩予建强潦帮资金有隈，革靠遒藤建设缮谈交遂闽题有袋度，必簇 考虑现有设施的最有效利用，这使人们不得不研究动态车辆调度问题； 4 车辆优化动态调度作为智能交通系统的个重要组成部分，其研究的 孬嚣蠹接影臻了系统黠蓉囊歪有效熬簿决交逶黼题。 隧辫计算辊攘术、信怠技术、g 菸、g s m 鹣g i s 菝术等鹃离速囊震，这些 技术成为目前实现动态车辆优化调度的关键技术，通过这些技术，能实时获 取车辆位置信息、道路状况、客户信息，实时的进行车辆行驶路径优化，这 嚣囊交透文攀臻赣鸯璧攀菠沦交羹2 鼹 对琵舔率辆运输效率，缓解交通帮挤育重要意义。通过车辆橇傀谎度，可戳 方便交濑瞥理人员获黻各种交通俯息，提高工作效率；可以犬大提高城市交 通罄理决案秘奏效拣黎 菱确娃，撼黼交遂营理决簸效率，进步提翥交邋管 理嚣蕊最纯末孚；可辍捺爨一黪赫燮突逶藩蕊管遥毒囊饕爨菠瓣蒺莲；罱戳 解决城市变通拥挤、能源短缺、太气污染等问鼹，保证交通涤源台理配裁与 利用。 巍予动悫车辆端嶷麓蘧麴舔巍穗实嚣夔生产生溪毒塞切联暴，妻麸事墩 囊囊勰罐在1 9 5 9 苹蕊d a n t z i g 亵r a r a s e r 蓥浚爨窭，p s a r a f t i s 连l 孽8 器军蔻 先提出了动态车辆调艘的概念之前+ 经过几十举的发展研褒，车辆调度潞躐 的应用领域越来越广，它已从交瀚逸输领域拓腿到工业管理、电力工程、遒 綦王露簿方垂。交予舀潞、s s 耩秘g i s 接零强愁骥熟，动态警辆调受系统熟 磷突在缀多藩霉受瓣豢稷。餐蕊灏蒋在蓉嚣怒褥舞臻悫蒋惑，懿蠢嚣羚番 样的渤淹信息进行舱穗，如何根掭避些信息快谴淀出最佳率辆路径，其瑗论、 模型和簿法的优劣随按影响车辆谶行的效果，礅无疑问，垂缝步的研究动搭 辜羲凌澄逮蘧奏垂燮麓蠢曼。 2 礤究现状 囱从车辆调度脚趟牲四十多举黼提出后，它弓l 起了人们檄大的兴趣，邋 筹孥、癍露鼗学、缀会鼗擎、嚣终分辑、嚣渣、诗篓爨蠹粼等掌蛰蕊专浆冬 运输专 辩键是耆帮旃理者遂孬了太蘩蘸瑾论臻炎疑实验套缀，蒎得了瀑太避 展，避粥这些研究成果，车辆调殿问题已被成功运用到邮件速递、出租率服 务、奶龋配送、生产计划、紧急服务等之中。率辆调度问题煨种具有栩当 产夔安怒稔蓬麓攀零辏蹇漂錾；褒淫途主震予篾亲羹霪台裁德簿鞑。霰瓣掌 耆稻鹣讲究，车辆谯瘦弱蘧熬滚避可劳兔聂令瓣麓，藤衰 一l 疆示。 从嶷质上说，率辆调度问藤的求解方法，撼本上可分为精确算法和翮靛 式算法掰大类。精确黧法指可以辩i 菇最优解的簿法，计算嫩般随问题擞棋 夔瀵夹紧舞鼗露长，邃甓葵赛繇窳耀蓬霪富鞭，藤器专家_ 饕j 囊鬟雯藜力筢塞 碗究激矮量盼雇装式箨法主。 囱从1 9 8 0 年p s a r a f t i s 在燃输科学杂惑上提出了动磷车辆调度问粼的 撅念乏恁，入 f 才歼贻把动态攀辆调度词题从举辆调度问燧中剥离出来燃杼 专门憩磷凳，餮i - i 嫠窭了美予麓悫蠢蘧魏霉囊溪麦舞蹙蘩予霉磊戆侉茨 一骛融溪要酶瞬袋溅果。 渤恣车辆调庶问题的求解方法不仅追求腻髓和计算时间- 而且要求储息 楚理越蕊、县真弹性，在文献【3 翱中，b e r t s i m a s 总结提出了解挟动悉苹辅 西南交通大学硕士研究生学位论文第3 页 调度问题的几种策略，如f c f s 、分割策略、t s p 算法策略、最邻近插入策略 等等，在文献 3 3 中，提出了一种单车辆的动态车辆调度问题算法，在文献 7 中，作者在他的博士论文中详细阐述了动态车辆调度问题的各种特征、 算法策略。 表卜1 车辆调度问题的演进 年代事件 d a n t z i g 和r a m s e r ( 1 9 5 9 ) 利用整数规划模式来处理包含大约1 0 1 9 5 0 到2 0 个顾客点的小规模问题 c l a r k e 和w r i g h t ( 1 9 6 4 ) 提出了一种启发式节约法来建立车队配送 1 9 6 0 路线；c h r i s t o f i d e s 和e i l o n ( 1 9 6 9 ) 应用2 - o p t 及3 - o p t 方法来处理 包含大约3 0 到1 0 0 个顾客点的问题 提出了两阶段启发式算法来求解车辆调度问题，g i 1e t t 和 m i l l e r ( 1 9 7 4 ) 提出的扫描法( s w e e pa l g o r i t h m ) 即属于先路径再分 1 9 7 0组的方法、c h r i s t o f i d e s 等人( 1 9 7 8 ) 则提出先分组再路径的方法。 此时学者g o l d e n ，m a g n a n t i 和n g u y e n ( 1 9 7 7 ) 指出虽然两阶段启发式 方法可处理较大型问题，但其涉及运算效率是相当重要的问题 f i s h e r 和j a i k u m a r ( 1 9 8 1 ) 提出以数学规划为主的最优化方法来处 理包含大约5 0 个顾客点的问题，同样其运算效率是一个亟待解决的 1 9 8 0 问题。另外，c u l l e n ，j a r v i s 和r a t l i f f ( 1 9 8 1 ) 建立种人机互动的 启发式方法 f i s h e r ( 1 9 9 5 ) 对最优化方法加以改善，已经可以解决5 0 到1 0 0 个 顾客点的车辆调度问题，同一时期，有不少学者利用启发式算法来解 决车辆调度问题，包括模拟退火法、确定性退火法、遗传算法、神经 网络算法和禁忌搜索算法。如r o b u s t e ，d a g a n z o 和s o u l e y r t t e ( 1 9 9 0 ) 1 9 9 0 以及a l f a 、h e r a g u ( 1 9 9 1 ) 都利用模拟退火算法求解车辆调度问题； s e m e n t 和t a i l l a r d ( 1 9 9 3 ) 、g e n d r e a u 、h e r t z 和l a p o r t e ( 1 9 9 4 ) 、 r o c h a t 和t a i l l a r d ( 1 9 9 5 ) 以及x u 和k e l l y ( 1 9 9 6 ) 都利用禁忌搜索算 法求解车辆调度问题 麟南交遴犬攀磺士骚究生攀位论淀繁4 炎 蘑1 - 1 关予动悫辜骥清廑嗣越磷究熬成巢 隧藩定位导航技术、数据通讯技术、自动控制技术、图浆分析技术眺及 计算钒嘲络和信惑楚瑷技术稳诀逮笈隧，动态车辆调度系统彳乍为智能交遴系 圜 哪 嘲 l 羹 | 耋 鳓 徽 溅 眦 | 萋 | 萋 愀鳓 _ 鐾 三一 ；。i；。，一 | | 丽磊 ；上fi下淤一繁 褥毫交通夫攀矮圭臻窕燮警佼论文繁5 瑟 统酶一个遂要组成豁分，在很多圜黎受封关注。8 0 年代以来，随着i t s 研究 领域和内容的不断深入发展，逐渐澎成了美国、敞洲和日本三兰大智能交通体 系，这三大体系褒究方蕊各毒铡蘩。铡麴美强的磷究集孛在7 个领域共2 9 矮臻变内容，箕孛臻缝雩；导系凌恣磷挺鬟蒜蘩逡毽稳楚懿暴蕊纾驶踌凌，警 期的路缡芍f 导是一个静止的信息系统，当实现垒方位的调度时，这个系统就 可以为嗣机提供实时的信息，使司机遵循最佳婀行驶路线到达目的地，它可 婆嚣蠹个嫩较完善靛旗惑车辆调嶷系统。 霉蕊，菜些豢臻量鞍纛熬懿冀法露菠轰翳远瘸舞实舔懿勰悫车藜疆褒塞 统，美闲利用最短路径辫法、启发戒葬法开发计辨机配送调庹系统用来解决 货运汽车作业计划中路线优化选撵和车辆分配锵问题，使汽车慝程利用率摊 毫辩l 勰，运竣或率黎运辕对闽戳蠢了弱显下瓣，表j 一2 掰示豹是翼翦融 经器楚势窿菊予实跤游动态车穗溪浚系统。 袭1 2 动瓣牮辆调度系燧的应用 系统名称开发者核心算法 糕p xi 繇 焚屡 矮短路翼法、翡发式算法 锶s塞士邋( 透本)繁约法 t p c a d美翠( 葵国)扫描法 在溪蠹，对手动杰车鞭褒麦鞠越照罄究仍处予起步凝悫，邋过字霎期矧 鼗蠢瘁分掰蘑关键镶“车赣疆度”释“车辆鼹校”捡索，1 9 9 4 2 0 0 3 霉9 攀 时间，在中国中文核心期刊要斟惑览来源辎糊已经发表该领域的相蓑文 章仅2 7 篇，就收黛的资料来看，我国这方面的研究具有如下特点：所研 究翡鞠熬癸鳖赛爱穗定篷霆篷；躲定手段魄较攀一；对该镀域麴专裔越 谣竣蠢虢规范懿掇法；该领域勰磷究者群俸，l 、。 国内开发的车辆调度系统主黉有上海优能激码集团、深圳胜唐信息拽术 有限公铷、上海天字集团分别开拨的0 i ) i n 2 0 0 0 、恺飞e 6 8 、诺特车辆调腱臀 莲系筑。慧粪衷嚣，獒痤委主要霞绩惠黪警褒、导虢、鞭黥、饕态鉴接霹嫩 警处鬻等方西，萁串瓣算法连谴鹰g t s 叁繁靛凝短蘧算法，蕊装雳还在试狳 阶段。猩文献 1 0 c 1 5 中，对d 隼辆调度系统作了一定的研究，但是考虑的 情况不趄缀全面，使在实际操作过程中或多或少不符合实际情况，因此其动 鑫嚣嶷繁藐蕊秀发竣谤还寿覆支熬淡蕊窒窝。 1 3 本论文的盎要内容 零论文回顿了动态车辆调度瓣趱的研究成懿，较系统地分析了动态幕耥 透南交通太攀磙酝变生举继论文第6 炎 调度的应硝领域、相关算法，建立了动态车辆调壤的数学模受，提出了解块 动态车辆调度问题的髀法及策略，根据各种相关技术的发展概况，提出了动 态车辆调发系统豹初步设计方案，焚主要内容包含予以下各章中。 鼙l 章绪论：麓述了动态车辆调度薜疆炎意义、研究魏状及奉论文熬 主要研究内容。 第2 章动态车辆调度问题及撼信息处理：邋过动态车辆调度问题的樾 窭，对动态信息勰不鼹她理方法逊行了详缨论述，劳拭不同角度对动态车蝴 谣凄目鼷遂 亍了分类，最后凳辑了静态襄交态v r p 麓区囊。 第3 章车辆优化调度算法的几个理论问题：论述了评价麟法的复杂一隧 理论，对闰前解决车辆调度问题的蕊本算法进行了较系统的总结，并分析丁 墨妻熬优点和不是之懿。 蔡4 章动态车辆谖度系统静毂荚菝寒：滔述t 鑫p s 、g i s 裁0 s m 技术瀚 原理，并澍其在车辆调度系统中的应用做了相关描述。 第5 章动态车辆调度数学模激及算法：建立了不确定倍息条件下单线 爨魏巷态攀辆调凌懿数学模型，在髓基磁主毖较深入兹分撰了解决该翔题静 动态德诧褫度算法，并辩算法& 裁行过程述孬了数据攘叛分辑。 第6 章动态车辆调度系统设计：对车辆调皮系统设计的必要性、总体 原则、业务流程分析进行了陈述，最后对系统的组成、运行结构、功能模块 进行了篱革静装诗。 结论；对本谵文鹃主要工襻遴褥总结，提臻了不足，对下步工撵滋李亍 展望。 黎壤交邋必攀冁圭鞲鸯氅攀篷适囊繁7 麓 。一 一w * f _ m _ _ p _ - _ _ _ h _ _ _ 十一 辩2 毫锄态车辆调度问题疑莫信息处理 登。 避爨睾辆溪瀵瓣蘧 簸 。 率藉诱懑瓣麓 浆鞭调度问鼹 v e h i c l er o u t i n gp r o b l e n l * 简称v 嬲魁妇d a r l t z i g 豢嚣氇i i i s 瑶嚣子i 警瓣警鎏魄羹窭黪* 爨爨，覆浚攀 邈运嚣攀、褒溪鼗攀、媳 台爨誉、簿签势瓣、寨谂、谤黎麓藤蓬蒜攀褥熟专家蓦露麓诗辩饕寒帮拣 瓣毽淫麓缀大耋蠛，穗霸进雹了炎爨豹溪谂鞲变菠实骏势掇，敬餐了懑必 避晟。龙矮是几十秘年辩，计瓣机技术的快漶鬣展为各种姆法的实验研蹴 灏霎蕊爨髅了萋鼷。 豢灏褥囊 簿麓毒藤嚣蠢霹n ( t r a v e ? l 姆淑l 荤黼鞋赣酶l 薅鲰篱黎鹊p 奄饕锹切联系。t s p 措的是：被行髑从超点蝴敞经过殿娶国的城市愉婶 次爱拣溺霖遗，瘦獭祷蜜蒜英簇持耱线，方簸糙憨韵旅行鞴离矮短。熊簸 瓣，鼷淡篱羹鹫爨多躐慧鬻爨鏊镣簿，爨暴撼蒸袁暴蕊爆黪委蟊嫩簿 芋鼹辩鬻痰奁藤撩鬻孛鼗囊惑鬻鼹溪多瓣嘧寮拳蓑嚣黪，蕊嚣鼹嚣戆戆孛 止于粼点。 攀翡溺凄越怼燧黪楚：霹燃涮羧攫蹙黪( 或) 收撩燃，缀缀逢濑髓 露李姆媳，蓑搴瓣簿黪镳；藿建毫懿，誊瀑蕊一慰瑟霎搴焱蕊羚爨塞魏黥簿 爨、狳港鏊、赛聚餐漪黼、攀槲窬簦袋瓣、豁骚要翟辫濮t 瓣麓蘸粼游 下，逡潮一定瀚鞠貅( 鞠路程瀚淹、费翔撩小、时阊尽鬃务、经灞絮辆散 器量少撼) 。 露蓑攀攀谈藤瓣楚翁雾蠢黎落；惑蠢鏊寒攀溪囊滚搂鬻；誉蘩黧爨潦 鼯辜瓣灞度瓣麓、疼举释车辆灞凄薅鼷与藤黼髓车辆淤麟辩嚣薅。蔌舔黪 姆程努，窍装爨阉怒、卸货闻熊及装鄂渥合翘题；接任鼹憷竣分，寅对滥 瓣务麓瓣( 嚣孛瓣豁鼗润霆) 麟霹感爨务褥越 如藏行辩陶题) 驭及溅裔 爨舅瓣蘧蘩黧懑摹蔑薅麦黎辫蘸是疆零凝髓羹鼗黧努，警壤蓑黧瓣黎 簿滚瓣黼蘧；撩攀灏鼗器势；谢肇车璐瓣疆黪多事蓊瓣藤；按车囊慕爨辩 分，谢单车型闯飚带n 多苹型问燃；按车辆琳举煽的所属燕黼分，有率删辨 熬翼瓣车囊剪苏零嚣嚣享臻辩冬臻嚣粼瓣器 车辆当时位置 。动态需求点( 立即请求服务顾客) 一计划调度路径 新的路径调整段 幽2 一l动态车辆调度问题路径顺序示例 时i h j 尽可能的短。 般晚束，调度问题越严格复杂，新的动；仑顾客插入将越复杂，例如有 h , j 间窗约束调度问题比无时间商约束调度问题的新顾客插入更网难，而且如 果找不到可行的地方插入新顾客，在线渊度系统iu 能拒绝对顾客的服务。 传统意义l 的静念车辆调度问题是n p 难题，用适当训算时间为现实某 种规模问题找到一个满意解不总是可行的，显然动态车辆调度问题更属于n p 难题，它相当于每接收个服务请求时去觯决个静态车辆调度问题。，此时 动态午辆调度问题还必须考虑立即服务淆求顾客的到达日寸间、顾客需求和服 务时i h j 以及调度系统的反应时间，因此这类问题的求解对时间的要求很高。 2122 动态车辆调度问题信息处理方法 当处理动态调度问题刚，由丁存在不确定因素，如伺考虑这些，1 i 确定因 素来安排路径，可采用两种方法。 1 基于模型的预先优化法：调度者根据未来服务请求、顾客需求、旅行 时m 等预先制定出基于模糊信息的一种或多种路径，当出现新信息时局部简 单调整路径。如果完全更新所有路径，这样即使可以得到i f 确的计算资料， 但每次接收新信，r 鲁, n l 都伞部重新计算优化路径，方面太耗费b , j 问；另一力 而，全部重新计算会造成车辆刮机混淆服务指令，而且i 刊司机月务某一顾 客的策略可能在重新计算路径时遭到损蛳；。基于模型的预先优化法就不会出 现这些情况，下面的3 种问题是用这种方法来处理的。 ( 1 ) 模糊旅行商问题( p t s p ) ：对图g = ( n ，a ) ，n 个点，a 段弧，每 个j j 、i 以概率p i 表示服务的几率，概率为l 的点表示该顾客点一定服务，用 实心点表示，其它用空心点表示，距离( 或成本) c - ，是与所有弧相关的值， 瓣薅交逯大学鞭士磅究釜学馕毒仑文第 o 爽 问题的解怒找到与所有点相连的长度最小的回路，碲i 考虑空心点是否定服 务，当旅行开始时，不用服务的点煎按跳过到下一个需要服务的点，最后返 回愿点形成个新的嬲路。1 2 个点麴铡子如图2 - 2 所示。其中分图a ) 表示 校据模凝黉求颈先安搀的旅行线路；分蕊b ) 表示翔遂点l 、6 、7 不需要囊 达时实际行驶的旅行线路。 5 3 a )b j 图2 2 关于模糊旅行商问题的预先优化法示例 ( 2 ) 模糊车辆调度问题( p v r p ) ：有人把模糊v r p 定义为标准v r p ，圆 为真实的v r p 的需求往往是模糊的蕊非确定性的。这种调度润越很难找到满 意释。b e r t s i m a s 为戴糖窭了诱静薰辩霞伲繁臻努翔为策略a 鞠策略瑟。 在策略a 下，车辆按同样固定的顺序作为一个预先安排的车辆优化顺序 经过所谢顾客点。然而，车辆仅服务有需求的顾客，但要经过无需求的顾容 点，总豹翅望距离等予颧先制定路线的固定长度与由于车辆容嫠约束面使车 辆返回仓霹中心造成辩髓离迂圈长发之稻。在策礴b 下，无需浓的顾客可以 不经过，图2 - 3 显示了两种策略的区别( 假如姆辆车的容量限制是2 ，有6 个潜在顾客需要服务，需求量为0 躐1 个单位，且顾客l 、3 没有需求) 。策 臻b 鼷避7 这些颁客，嚣策珞a 经过了蘑有颥骞点，这强静繁旗可如下艇器： 策略a 可蠲于顾客需求鼙知道时车辆已经到达了顾客点的蒋淡；策略b 可用 于当车辆到达顾客点之前顾客的实际需求量已缀知道的情况。 ( 3 ) 随机车辆调度问题( s v r p ) ：如果v r p 的某些因素熙随机的，s v r p 藏出瑷了。镄热旋彳亍瓣翘豹不臻定、蔫求量素熟、颞客是否嚣在遣未知，这 些都属于随机因素。戳梵随枫v r p 被人们看成模糊v r p 的扩矮，通常，随辘 v r p 属于二阶段式求解的问题，在第一阶段设计个预先安排的线路，第= 阶段用求助方式来调节像超过容量限制这类的阀题。通常说来，在设计第一 鞭爨交逶夫攀矮奎骚窕鬟攀犍泛文筻 樊 2 巷 鸯鞭囊蜜舞舞壤黪 s 策蜷瘫e 策略耩 幽2 - 3p v r p 谢种优化僦嘴比较示例 銎蓑缝黪瓣，逮静黎稔骞霆产堡熬褥莲零囊苓终褒渡凳予考憋。赞热，测麟 酴袋方法寒考悫穗祗禳求戆辩辩，雾一餐鼗淤诗窿簿辩蕊窜藕蘸蓬爨涎鬻 个顾销点恰好一次，然阶段蝻聚池来之后，顾客实际需撒被确定。蹶群晌 总嚣蕊w 能超过车捌容量约束隰制，这时第一阶段的设计然路可能变得不可 孬；嚣：狳霪羹一争簿攀蓑臻蔼器瀣嚣襄嚣羧漆器驻，妻裂攀蕊窖量黪滚辫 蘸；鼹鬻褥返器奁簿中心鼙惑袋祷宠需求舔惑，然矗运嚣戮瓣较失蘩黎拣骞 重新歼贻顾客服务。猩这个例予燃，求助行为产生的相关溅率等于往返食麟 巾心黝逡输成本。燃神更好的蹬鼬方式为；幽车辆较靠避仓库中心，涮鼠 囊囊煞攀囊褰曩羹绞车囊装豢鬟 爨予墓一囊惫爨曝，享絮遨濯惫霉事心，搭 攘上一一方式进蠢爨搭。g e n d r e e t u 瓣挺随撬v r p 努藤6 娄：髓瓿藤霉蕊l 辨 随机臌杼时间的t 8 p j 随机旅行时间的最少车辆数的t s p ：随枇需求量的v 舭； 薅飙黻露麴y r p ；髓枫嫒馨和嚣裴爨的v r p 。 2 。餐露羲黎鬏嘉涟：薹子搂爨麓蓑蹇蠢纯法跫豢纛毒寒攀搏嚣毳霪魏辫蠖 颧藩蕊寐椅造线狳，猕置线路蕊帛辆离开套窿中心之懿爵添灏定好戆，瓣舞 时优化方法是在调媵执行过程中制定线路，即率辆运行过獭中实时在线制魁 舞线。下囊绘墨豫方法释凌翔慰髓3 静翔题t 蕊鬻交蓬麦喾矮童骚窕敷攀犍沦交葵 童鼹 动态旅符薅阏怒( d t s p ) , 缀典簿藤脊髓海瑟是遮簿擎磺蠢囊r 泛 的问飚也，这类研僦的大多数徽中在确定性裥静态t s p 方御。在1 9 8 8 举 p s m - a f i s 套塑了磁漆菠嚣黉翔然蜓蕊态形式，该弱题定义鳓eg 是一个n 争熹淤爽爨霪，臻瓣豢令袁鼗囊产篷蓬否藜骜爨慕；蓑嚣瓷蕊粪慕爨蚤蕊惑 必须黼不变的速度瓢蕊i 旅孬弼惠j ，每令瑟漆濂务点的舔潞辩瓣为南，漆 行商的悯题是遵 餍个最合适的蹄校策略来旅行糍成服务。潮然，g 也刚以 虽蚕竞垒戆、嚣嚣鹣鼹，瑟盈蚕辅蕊鞠霸象蟪撼霹烈是变化骢，当一个黢谶 嚣蘩舔壤籁嚣努黪蕊赛霉鬟瀵惫瓣，奁鹜遮芋令焘嚣雨誉惫羲霆臻爨紧 对所霄滞求点有意义m ( 2 ) 动态旅行修煺员问题( d t r p ) ：动态旅行修理员间删被认为是军c j 菱黎躲漆率囊毳藏瓣繇，霆凄豢率瓣凌麦彝粼熬避多扩艇黎数学土黝撼 蒙。褒蕊蜜爨琵蘧蕊拣枣，嚣攀，瀑蕊霆筵黎瓣寒蒸，辜瓣鬣蚕莲一卞莰蕊 订单黼求、形成旅行线路、分粼攀辆的连潦蛾糨。在动蕊蕊件下，趣予渗 及到调皮问题是嚣目顺利执行，越使等待时间邋常比旅行成本熙重要。铷绺 羹器麟壤爨羹垂螽露谶下嫠錾= 瓠蓥褒员蠛露鬻纂彰黎蚤天蕊攀一惠瓣逮整奁螽鬻溪壤囊薰嚣 b 所有的需求怒潮态的，衙辩彼置在区城确独立均匀分诮； 懿璁该阀题的渊魔壤略有；沌到先服务；中心随机排队 最小邻避法； 龛裁鏊嚓簿； 姆) 麓蠢醚袅l 幢曛 盘黍蕊；麓盎 一蠡- 瓢蕊瓣蘧( 露蠡龄) 遴零豢蕊爨凳 许多腻辫找到成本：融少的线路，瓣个顾客都育个起点( 蠹甜辩便车前能粼) 鄞一个终点( 递邀饿凝) 。为顾瓣提供一段的精驶距离和髓的服务桥凇一 曩黎惑稳簿交蠢寨禳寨，囊枣豫黪瑟瑟霪雾爨攀矮鼗；一靛戆嚣器努蕊兰 夫獒 a + 多对一( m t o ) ：这种撒黜魑该问题中潦简单盼，桐对而言容瓣榆邋 亵臧缴的线路。如激毖菜一区域 2 l 訇许多颞客粼嫩当地某一个购物商场，+ e 蒋兰 蔻燕霹麓季一器，慧蓬在嚣一熬蠹下辜，鏊黪粳凄霉瑟襄麟子多霪一。 舔。多瓣多e 斟擎) ：运母蔑熬姆辩要菱黎，艇莛与錾罴霄今冬熹下攀湾 情况棚比会更接 i 聩燃实，该问蹦构造线路质墩糊成本相对墩商些。例如。虹饼 串蓟黎煦甥巍场黝勰嫫报大，璃兰个不嗣的搭i 棼点，顾客粼在三个不踟的地 蠢下攀，运嚣蘧鼹鬻予多霪多。 铂雾j c 雩多辩蒲：该滔题懿：溪簧象黥，溢楚鬻藤螽藤舔霉霉不嚣懿稳豢 也有幂同的终点，忸是可能坐闻辆车，出枫$ 服务就燕卟很好的例子， 这耪瓣题也霹璐瘸子喾每又翻黢艨丸豹运输， 谶囊交嚣夫攀赣臻囊生鬻谨沦文冀 3 鬟 2 2 动态车辆调度问题的液用分类 2 。2 1 濑态车辆调艘问题豹威粥实捌 i 。藩嚣惨莲蚕瓣越 器；姿锻舒魏衮蓑爨繇了，叠羲遴澄跫蘩鐾蓉技 术员来修理，技术员制定的线路可姒根据目标的躐离来决定，也可以根据褥 到维修谶知的紧急穰媵来决定，邈种问题通常 艘称为“动悉旅行修理员阃 霆气它爨瓣窕最广泛熟漤枣辜秘谗嶷霹瑟之。鼹撵，建力公鸯骖理员羧 家挨产去修理突然繇褒戆戆蘧遣蕊溅嚣营莲瑟瓣麓。 2 邮件速递( e m 8 ) ：全球性的自b 件速递公诩擒供分拣邮件、包裹，并撼 物品在是时间内安全送达目的地的服务。通常，送的邮件溅包裹不是本地 葵委蕊寒囊爨嚣骧露袋辫塞，强热，这些饕瑟被送囊蒹令邃避中，孰葬鼓这 孛惑努溅爨受责送舞枣辍土，辜骥程舞孬速逢审心之蕊，霭椒寨道嚣畜攘浆 者的位黼，这个过稳形成的是一个静态车辆调廉问题。然而。由于车辆出凇 爱，司机和速递中心举知道在行驶i 藏程中，行驶车辆会在什么时候、什么地 煮茇垒嚣么事薮，搿熬获菜饕塞殳土浚，这篓器驶辜囊交或麓惑了。 3 、供燕琵送( 蚤猕) ；绘蘑民灏摸煞嚣遴楚掇掇产秀遴赛窝姥寒蕊攀黎潦 的，供热公司以天为鹅位来追踪磁释已经用了灞少暖油加热他们的房子。冤 论什么时捩，数据撵撩缆会告诉调艘系统哪个顾辫的暖油正溉少到一个设懋 ，蜜，逮个藤雾蓑会羧麓霜等爨爨势磐产器孛。鬣然强天嚣谤爨攀篷冒器臻羚 态顾寮瀚求寒考惠媛瓣题，翟潺液藜统会零黉怂蕊谚态颞蜜。潮为蕊煮一夺 部分麟裙可能在数搦麾系统把他4 i 1 漆加到等待腿貉客户群之黼用完暖油，例 如天气绽变可裁提黼骥油豹翔量，丽数据库群绕来不及记融顾客的这眷中行 舅；纛卷籁客耄藜怒熟爨骞夫囊豢谯，导蘩一蹙缀喾石囊黎煞蕊赛鬻黧熬声 生了蘸涵酶高灞量。艇验表龌，一个供燕公蔼大褥2 0 酶蹶嚣需要髅热公遴 立即供热，这称为动恣需求。 4 溺怒d a h l i a 杖i 缱e 系统( d n a 孵) ：d a i l - a - r i d e 运输聚统是普通分橼 递蘧张p 戆一争塞瑟蜜壤；在凌暴凌孛一餮蘩爹转襄箍茎 霰焱墓争蘧嘉努拣， 然后遂潮另一个逸方。其动态实诵肖著名酶蠢年入帮残疾入瓣铲送，灏辩拣 旅行需嫩发生前需辩印请服务，公间可制定政徽使调度系统魁静态的，但魁 弱土在线黢务是一个旗态嗣子。 5 感黎辜蘩蚤( 弱s ) ；薯囊爨餐攀邃暴爨癸垒潘孛群黔篷争瘦露癸 例。谯太多数出稚攀瀑统中动态灏留的磁铡是濑商靛，趣就髓说在出秘牵辫 开出租中心之前，出3 粗中心仅仅知道很少几个顺客的需求。嫩租车调度分醚 蕊一个姆隳嚣毪是爨樾擎霹孰被缀定，逛霹以犒黠租弱。当堪秘车没避谳嶷 鼹塞交逶丈搿矮士臻蠢生攀链谂文纂 霹焚 蔼显是警潮时，司桃常常重新逡簿率辆弼尺稍拽密程车魏燕黉闲置选点， 因为这样比出租车呆猩墩后一个顾裙的下车地点撇租用的概举龋商得多。删 耀置地点瓣确定往建怒攫撂班往懿经验数据或弼枫熬壹觉翻缀验。出租率调 度势熬暴竣露蒺曩藤坶蕊蓑睡寨努鬣簇褰，毽蕊憩要爨囊鼙努黪囊羹。 6 紧急事件服务( 霹s ) ：对警察髑、失炙、怒救服务等黎髁服务莳诱黼 类似于d v i t p ，服务请嫩要实时到遮。且系统类似于地理排队粼统，在大多数 象转下，耩爨羧务率诲爨爨之藏，臻寒翁请求鼠疑服务了，瓣然没商影残擗 菝线鼹。凝砉繁基聚努戆分嚣零覆瀑霞鲎舅藜寒决定辜耩窝王露天曩，娶麟 决的问劂是给新出聪的请求分配潦好的车辆，。 2 。2 2 幼惑车辆调蹴闻题的燃燃分类 囊蘩令凄悫攀凝潺菠系凌黎谯霞季霆一个溱攀嚣蘩务，笃穗定蕊棼蠢 车辆调艘黼题相眈，潮恣车辆调磨舔统的性能不暾依赖于总黼求数量和需求 的空间分晰，而且依赖于动态信息的数量和动态信息实际产生的时间，因此， 努暴戆梭羧变建条 譬下熬落算法辨蜓懿，蓑述黎髓媳动态链熊怒个麓单蜀 霞戆蕊_ 爨方洼。 在讲多在线动惑黼度系统中，倍息不总是拣谲度执行前垒部接收瓢，靛 们定义下髓的比率( d o 酌来反映隳统的动态恺黼： d o d ；鬻 理刊 崧跚2 一l 中，j 0 个总需求中黼2 个动态需泳* d o d 值蕊2 0 ，然而这个 值没有涔虑动态需求的接收时间，如图2 4 ( 设总需求是2 4 ，其中有6 个动 鑫雾袋，溪串嚣夸捷予藜壶疗黎蟋坶2 5 ，稳蒸凌态嚣裳接漆黠鞠畜缀穴 差裁，京蘑孛，彝令耱态羲泰黪搂鼓薅霹舔簿晕蕉，娃爨逡会客瑟一登， 而在b ) 中，动态需臻的接收时间嘏分散，显然粥成任务会瓣磐，明显其蛐 态性委臌些，为了农示这种差别。我们把动态黼求的接收时间纳入d o d 公 式串，掺袋一彝更饔羧戆羹量囊番涟鹱獒砉法，滚潼定爻势# 南蘸 edod=!=!一(2-2) 芝( 弘“ 蓑孛 琏。：慧羚凌惑 薹裘数； ：辩i 令动态需臻鹃援妖靖黎； 正调膦执行的时间牿束时刻； - _ w “* _ _ _ m m _ _ _ 一m h _ _ _ - - ”# m 。_ ”“_ _ 9 _ 西南嶷通大学硕士研究生学憾论文第15 页 一1 一r 一 辩总豹需求数。 o 吉托言f i i 璜e 0 t ，岛如f如d， b ) 强0 一：苓蠢援救时闾黪动态舞求承翻 露照，棂瓣系统孵动态憔憩，哥怒动悉黉度系统努为嚣汝、适审豁、臻 的动态调度系统，根据此分类和追求强标可把一些典型实际的动悉l 捌度实倒 滋行分类，如图2 - 5 所示。 囊毒魏渭庭黠霹 臻 蕊 餐 霹 最小佬调漤成本 弱的动 态系缝 通t p 的动 态系统 动态键鼹 的动 客系统 燃2 5 动态车辆澜度问趱瓣若l ：实例的分类 2 ，3 静态与豢态辜辆调度翔题耱 妻较分婿 在本节我们将讨论静态车辆调腋问题弓动态车辆调度问题的区别， p s a r a f t i s 列出了它们的1 2 个区别，f 嘲给出个简单的介绍。 l 。辩嚣霪溪犍：在羚态溪凄溺嚣巾，可孩考惑对翔篷可张不考虑黠翔， 时闯在静态闯题中不是穰嚣要；在动态灞度同题中，考虑时闯是必须鹩，谣 鼹囊交透交擎醺圭骚窕垒攀健沦文募 s 凝 度中心程任何时候豁灏在最短眩阕两辩遭所膏率辆耱位置，特嬲是有裁恋潲 求和信息收到时，因为在现实生潲的动态调度问髓中，如果渊躞中心不能及 辩童g 遴攀髓鹣袋曼，将罨致瑗蠢攀辅靛在线交流掰费麴或本将建巨大的。 2 。潺鏖霆嚣瑟癸羧瞧；在蘩态潺囊簿瑟孛，镳菠遥程透露蕊羧鋈蹇努煞， 郎调瀛、歼始和结束位乎褥一点，鼹闭合舔；然两程动态调寝阔怒中，调赓过 程没有淼n 此约束，常涔虑车辆实断的行驶线路，可能是开放的而不需闭合。 3 ，浓寒落惠熬确嫩姓：在静态瓣越串，掰裔缕患被缀设鼹b 翘豹甄且撼 骞禧弱蕊凄燕；吝穗惑簿逶孛，寒寒蒋会窭凌爨。么蕊塞霆零稳定戆，螽多霸 道未米w 能发生的模糊信息。 4 ，嶷b 瑷最新信息的蘑要性：赧静态调度问劂中，信息质擞煺样的，耐 基覆多瓣浚入骜鼗攒避嚣曼巍，嚣熬对瑟骞发生游誊 孛赋予糕添黪毅重；农 蘩鑫渣熬下，壹揍鬻率蘩赍濠囊愚长麓簧交霪琴鞠骜蘸，在簸疆瑟态适凄瓣 题时，调度中心应该先把车辆资源分配给最近靛生的新需求。 5 储息更新机制的必要性：对幼态调度问躐简言，几乎所肖的输入在调 麦藜谣熬甏装豪生馥嶷，透夔毽穗凝方蹇嚣穰怒瑟瑟撬裁一体纯是必要懿。 获本溪。莨诞，蕾惑熏辩藏蘸与蒸惫壤度薅瑟蕊秃芙戆， 6 徽新制定调麟拽路、重新舒黼车辆是许w 的：在动潜调度问题中，渐 豹输入w 能导致调度中心先前的渊艘方案变成次优，为了避成新的情形，媳 逵蓑溪凌卷去耋錾裁戆遵麦凌蘸，蕤至重囊势粼苇囊。 ? 。浚逶箍瑶霹鬻憋瑟要整：在静态舔壤蒸鼗秘子孛，谣震誊鸯了祷懿藤 质量的调度方案甚黧鼹优方案，辩拖一点处理时间是可行的 然而在动拣环 境中，避是不可能的，因为调度谢希望尽快知邋目前问题的涧度结果( 嫩姘 曩嚣磐辩蠛蔻爹餮。逶嚣藏舞鹭窳逮莲轰羹豢遮鼹蒙疆天法鞣廷交巍拣襻 静罨黼澈薄扁发式荐法，来重耩粼寇线路秘蠢精分甏车耩。 8 脊确定