（交通运输规划与管理专业论文）基于模糊行程时间的车辆配送问题研究.pdf

摘要 摘要 现代物流是企业的第三利润源泉，发展现代物流是我国转变经济增长方式 的重要举措。社会物流的发展、城市交通拥挤的加剧，迫切要求合理组织物流 配送活动。同时，交通状况的差异性和时变性，也要求配送计划制定时要予以 响应。九部委在关于促进我国物流业发展的意见中明确指出：“优化城市配 送车辆交通管理。要加强对道路交通流的科学组织，根据当地的交通状况 和物流业务发展情况，研究制定配送车辆在市区通行和停靠的具体措施”。 交通流的时变性与差异性是客观存在的，因此在制定车辆配送计划时假定 车辆在配送路径中的行程时间是固定值的作法不仅与事实相悖，而且常使货物 在实际运送中欲速不达。如果将交通流状态和运输资源结合起来考虑物流配送 问题，则可以减轻交通拥挤并提高配送的时效性，从而提高物流服务质量，增 加企业经济效益，同时对提高居民生活质量也具有重要意义。 本文将研究对象限定在城市复杂的道路交通条件限制下的物流车辆配送问 题领域，以构建基于交通流状态的车辆配送问题理论框架和分析求解方法为目 标展开研究。研究的主要内容及形成的结论或成果主要由以下五部分构成： ( 1 ) 交通流状态的分类与预测 从交通状态的差异性及人类对交通状况主观认知的模糊性角度出发，借助 模糊数学等理论工具，研究基于路段的交通状态的分类和预测。 静态预测：通过将各时段的历史交通流数据输入聚类模型实现对不同时段 不同路段上的交通流状态进行分类与标定，借以初步预测次日路段上不同时段 的交通流状态。 动态预测：建立了满足车辆配送问题需要的交通流状态动态预测的智能预 测系统，设计开发了相应程序并进行了实例研究。 ( 2 ) 车辆模糊行程时间分析与建模 研究不同交通流状态下的车辆行程时间。针对不同时段不同路段的不同交 通状态建立相应的速度隶属函数( 尤其是速度隶属函数) 。基于单一交通状态及 多模式交通状态分别建立相应的路段模糊行程时间及路径模糊行程时间模型。 提出了路网模糊行程时间矩阵的路网权重标定方法。 ( 3 ) 基于交通状态和模糊行程时间车辆配送问题( f v r r ) 建模和求解方法 摘要 建立了基于模糊行程时间的车辆配送问题( f v r p l h - j 题) 的系统模型。采用 了模糊数排序的方法解决模糊最短路问题，提出了基于距离测度的修正c w 法及 基于模糊行程时间可靠度的混合遗传算法进行求解。 ( 4 ) 基于交通流状态变化的动态车辆配送问题 建立了交通流状态的a n f i s 智能预测系统，针对动态车辆配送问题进行了研 究和探索。 ( 5 ) 理论分析与实证分析相结合 实例研究和算例分析贯穿于全文的始终，确保了理论研究与实践的紧密结 合，同时也保证了模型与算法的可行性。 关键词：车辆配送模糊行程时间交通流状态模糊聚类模糊最短路路 网模糊行程时间矩阵模糊行程时间可靠度动态车辆路径 2 摘要 a b s t r a c t m o d e m l o g i s t i c si st h e3 r dp r o f i ts o u r c eo fe n t e r p r i s e s d e v e l o p i n gm o d e r nl o g i s t i c si st h e i m p o r t a n tm o v et oc h a n g ee c o n o m i cg r o w t hp a t t e r n t h ea g g r a v a t i o no ft r a f f i cc r o w d sa n dt h e d e v e l o p m e n to fe x t e r n a ll o g i s t i c sa s ku r g e n t l yt oo r g a n i z el o g i s t i c sd e l i v e r yr e a s o n a b l y a tt h e s a m et i m e ，i ti sn e c e s s a r yt om a t c ht h ed i s c r e p a n c ya n dt i m ev a r i a n c eo ft r a f f i cc o n d i t i o nw h e n p l a n n i n gl o g i s t i c sd e l i v e r y “s o m es u g g e s t i o n s f o r d e v e l o p m e n to fc h i n a sl o g i s t i c s p r o m u l g a t e db y9d e p a r t m e n t sp o i n t so u td e f i n i t e l y ：“t oo p t i m i z et r a f f i cm a n a g e m e n to f l o g i s t i c sd e l i v e r yv e h i c l e si nc i t y t or e i n f o r c et h es c i e n t i f i co r g a n i z a t i o no fr o a dt r a f f i cf l o w ， a n dt oa r r a n g et h es c h e m e sf o rd e l i v e r yv e h i c l e st ot r a n s i to rb e r t ha c c o r d i n gt ot h ec o n d i t i o no f l o c a lt r a f f i ca n dl o g i s t i c si n d u s t r yd e v e l o p m e n t t h ed e n a t u r a t i o na n dd i s c r e p a n c yo ft r a f f i cf l o wi so b j e c t i v ee x i s t e n c e s oi ti sn o to n l y i m p r o p e rt oa s s u m et r a v e lt i m ea saf i x e dv a l u eb u ta l s oo r e nl a t e rt h a ns c h e d u l e dt i m ef o r v e h i c l e st od e l i v e rg o o d si nac e r t a i nr o u t e i ft r a f f i cf l o ws t a t e sa n dv e h i c l e sr e s o u r c ec a nb e c o n s i d e r e dt o g e t h e rw h e ns c h e d u l i n gv e h i c l er o u t i n gp r o b l e m s ( v r p ) s y n c h r o n o u s l y ，t h e nt h e t r a f f i cc r o w d s 锄b el e s s e n e da n dt h eg o o d se a rb ed e l i v e r e di nt i m ew i t ht h ei n c r e a s i n go f r e s i d e n t i a le n v i r o n m e n ta n dq u a l i t yo fl i v i n g t h u s ，t h el o g i s t i c ss e r v i c 宅q u a l i t ya n de c o n o m i c b e n e f i t so fe n t e r p r i s e ss h o u l db ei m p r o v e dl a r g e l y t h i sp a p e rw i l ls t u d ya tv r pu n d e rc o m p l e xr o a dt r a f f i cc o n d i t i o ni nc i t ya n da i ma t c o n s t r u c t i n gt h e o r e t i c a lf r a m ea n da n a l y s i sm e t h o d sf o rv r pb a s e do nt r a f f i cf l o ws m t e s t h e m a j o rc o n t e n t so fr e s e a r c ha n dt h ec o n c l u s i o n st h a tf o r mo ra c c o m p l i s h m e n ta r ef o r m e dm a i n l y b yt h e5f o l l o w i n gp a r t s ： ( 1 ) c l a s s i f i c a t i o na n dp r e d i c t i o no f w a f f i cf l o ws t a t e t h i sp a p e rs t u d i e sa tt h ec l a s s i f i c a t i o na n dp r e d i c t i o no fr o a dt r a f f i cs t a t e sw i t ht h ea i do f t h e o r e t i c a lt o o l ss u c ha sf u z z ym a t h e m a t i c sf r o mt h ec o m p r e h e n s i v ea n g l eo fd i s c r e p a n c yo f t r a f f i cs t a t ea n dt h ev a g u e n e s so f m a n k i n d sl o o k i n ga tt r a f f i cc o n d i t i o ns u b j e c t i v e l y s t a t i cp r e d i c t i o n ：t h i sp a p e rc l a s s i f i e dt h er o a dt r a f f i ci n t od i f f e r e n ts t a t e sb yp u t t i n g h i s t o r i c a lt r a f f i cd a t ai n t oc l a s s i f i c a t i o nm o d e la n dt h e np r e d i c t e dt h es t a t eo fr o a dt r a f f i ca tt h e s a m et i m ep e r i o do fn e x td a y 3 摘要 d y n a m i cp r e d i c t i o n ：t h i sp a p e re s t a b l i s h e da l li n t e l l i g e n tf o r e c a s ts y s t e mf o r t r a f f i c d y n a m i cp r e d i c t i o nw h i c hc a ns a t i s f yt h en e e do fv e h i c l er o u t i n gp r o b l e m t h i sp a p e ra l s o d e s i g n e dr e l e v a n tp r o g r a m sa n dc a r r i e do u te x a m p l e sr e s e a r c h ( 2 ) a n a l y z i n ga n dm o d e l i n go fv e h i c l ef u z z yt r a v e lt i m e ( m a tf i r s t ，t h i sp a p e rs t u d i e dv e h i c l ef u z z yt r a v e lt i m ea c c o r d i n gt od i f f e r e n tr o a d s ( 1 i n k s ) a n d r e l e v a n tt i m ep e r i o d s f o re a c hr o a d ( 1 i n k ) a n dr e l e v a n tt i m ep e r i o d , t h ep a p e rf o u n dm o d e lo f f u z z ym e m b e r s h i pf u n c t i o n , a n dt h e ng e tr e l e v a n tf 1 v rf o rv e h i c l e st ot r a v e lo ni t o nt h es e c o n d , f o rs i n g l ea n da l s of o rm u l t i p l et r a f f i cs t a t ep a a e r n , t h ep a p e re s t a b l i s h e dm o d eo fl i n k ( r o a d ) f u z z y t r a v e lt i m e ( l f t t ) a n dt h e ne s t a b l i s h e dm o d eo fp a t hf u z z yt r a v e lt i m e ( p m o nt h et h i r d , t h e p a p e rp u tf o r w a r dan e wm e t h o do ff u z z yt r a v e lt i m em e t r i xt om a r kt h ew e i g h to f r o a dn e t w o r k ( 3 ) m o d e l i n ga n ds o l v i n gm e t h o df o rv e h i c l er o u t i n gp r o b l e mb a s e do nt r a f f i cs t a t ea n d f u z z yt r a v e lt i m e ( f v r p ) t h i sp a p e rp u tf o r w a r dt h es y s t e m a t i cm o d e lt os o v e lf 冲t h em e t h o do ff u z z yn u m b e r s o r to r d e rh a sb e e na d o p t e dt os o v e lf u z z ym i n i m u mr o a d sp r o b l e m t h em e t h o do fc o r r e c t e d c wl a wb a s e do nf u z z yn u m b e rs o r to r d e ra n dt h em e t h o do fm i xg e n e t i ca l g o r i t h mb a s e do n r e l i a b i l i t yo ff u z z yt r a v e lt i m eh a v eb e e np u tf o r w a r d t os o v e lt h em o d e lo f f v r p ( 4 ) d y n a m i cv e h i c l er o u t i n gp r o b l e m sb a s e do nt h em o m e n t a r i l ya l t e r e dt r a f f i cf l o w s t a t e ( d r v r p ) a ni n t e l l i g e n ts y s t e mo fa n f i sw a sa d o p t e dt of o r e c a s tt h ew a f f f i cs t a t e t h e n , t h i sp a p e r r e s e a r c h e dt h ed f v r pw i t he x p l o r e ( 5 ) a p p r o a c ho fs t a n d a r dr e s e a r c ha n df a c tr e s e a r c ha r ec o m b i n e & f a c tr e s e a r c ha n dm a t h e m a t i c a le x a m p l ea r et a k e ni nt h i sp a p e rp e r f o l i a t e t h i sc o m b i n e s t h es t a n d a r dr e s e a r c ha n df a c tr e s e a r c hc o r r e c t l y o nt h eo r t h e rh a n d ，t h i si n s u r e st h ef e a s i b i l i t yo f s t a n d a r dr e s e a r c ha n da r i t h m a t i cs o l u t i o n k e y w o r d ：v e h i c l er o u t i n gp r o b l e m ；f u z z yt r a v e lt i m e ；t r a f f i cs t a t e ；f u z z yc l a s s t e r i n g ；f u z z y m i n i m u mp a t h ；f u z z yt r a v e lt i m em e t r i xo f r o a d n e t w o r k ；r e l i a b i l i t yd e g r e eo ff u z z yt r a v e lt i m e ； d y n a m i cv e h i c l er o u t i n g 4 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下 各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学 位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存 论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务； 学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在 不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术 活动。 文作者签名： 一要犯e t 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名： 年月日 学位 律日 j 十一略 r 9、 名 e 戥 年 静s 作 饥 文乙蝣勘 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名： 年 月日 第一章绪论 第1 章绪论 通过对选题背景、国内外研究现状的分析，明确论文的理论和现实意义。 在界定研究问题的前提下，提出研究的主要内容，最后给出研究的思路和章节 安排。 1 1 选题背景与研究意义 1 1 1 实践背景与研究必要性 1 1 1 1 人类对交通状态及行程时间模糊性的主观认知 日常生活中，人们常用畅通、拥挤、堵塞等描述交通状态。这些语义本身 是模糊的，它们之间没有分明的界限。同时，从认知角度来看，行程时间的估 计多数情况下是具有模糊性的主观词汇。例如，某人开车上班，他( 或她) 每 次所用的时间是个确定的值。但是在到达之前，他( 或她) 对所用行程时间的 感知却总是根据对交通状态的某种经验判断而预估为“t 分钟左右”、“大约t 分 钟 。这表明在特定路径上某种出行方式的行程时间，在大量的重复性试验( 如每 天上班) 中，表现出一定的与时段相关的稳定性及类区间性。而这种类区间性正 是由于行动计划中行程时间本身排中律的或缺所引起的模糊性。 1 1 1 2 社会物流的发展要求合理组织物流运输 国民经济的持续健康发展，工业化和城市化步伐的加快，居民消费结构的 升级，有力地推动了现代物流业的发展。同时，电子商务衍生的频繁货物交付 活动及基于低库存与及时交付的生产与配送活动，引起货物运输不断增多，带 来更严重的交通阻塞、尾气排放和噪声污染，不仅严重影响生活质量，还使货 物运输在实际运送中欲速不达，不能很好地实现城市货物快速运输【17 】【l8 1 19 】。 因此，从城市道路资源和运输资源综合的角度考虑物流配送问题，不但可以提 高企业的服务质量，增加经济效益，而且对提高生活质量具有重要意义。 第一章绪论 1 1 1 3 九部委 关于促进我国物流业发展的意见要求根据交通状态制定配送 措施 2 0 0 4 年8 月5 日，国家九部委( ，黝发屠祀改事委另会、蔚务积么嶝瓤 铁道部、交通部、海关总署、国家税务总弱、中国民甬航空总碣、国家i 商行 硬朗：盛局) 关于促进我国物流业发展的意见【l 】中指出：“优化城市配送车辆 交通管理。公安交通管理部门要加强对道路交通流的科学组织，根据当地的交 通状况和物流业务发展情况，研究制定配送车辆在市区通行和停靠的具体措施， 提供在市区通行、停靠的便利。一 1 1 2 理论背景与研究意义 1 1 2 1 在降低货运成本和缓解交通拥挤间权衡是社会物流的目标 考虑交通、环境和能源消耗等社会经济问题的物流问题研究，目前在国内 大多体现在“社会物流”相关概念和方法研究等方面【4 】。国外上世纪9 0 年代末开 始的“c i t yl o g i s t i c s ( “城市物流”) 问题的研究类似我国“社会物流”的概念。 r u s k e ( 1 9 9 4 ) ，k o h l e r ( 1 9 9 7 ) ，t a n i g u c h i ( 1 9 9 9 ) 和v a n d e rh e o d e n ( 1 9 9 9 ) 分 别在相关的论文中提及该概念，t a n i g u c h i ( 1 9 9 9 ) 将c i t yl o g i a i c s 定义为：在自 由市场经济的框架下，在考虑交通环境、交通拥挤和能源消耗等因素条件下， 在城市地区优化私有部门的物流和运输活动的过程。城市物流的目标是：在考 虑成本效益的情况下，不仅对于私有部门，同时也对于社会公众，系统优化城 市地区范围内的物流系统。其实质问题是在私有部门降低货运成本和公共部门 缓解交通拥挤和环境污染两者之间权衡；其研究的对象主要局限于城市范围内 的物流活动【5 】。主要的研究成果分别发表于i n s t r u t ef o rc i t ) rl o g i s t i c s 在1 9 9 9 - 2 0 0 1 年间组织的城市物流国际会议上【6 】【7 】 8 1 【9 】【10 1 。 1 1 2 2 交通流状态的差异性与时变性要求物流配送计划予以响应 交通系统的开放性、随机性和复杂性，使车辆在道路上的行程时间难以事 先准确预估。图1 1 为某路段2 0 0 6 年5 月3 1 日( 虚线) 和6 月4 日( 实线) 两天2 8 8 个时段 ( 每5 分钟一个时段) 的交通变化情况，红色代表流量，绿色代表速度，蓝色代表 占有率。该路段一天的交通状态不断变化，而另一天的变化又与该天不同。这 种情况在城市道路中非常普遍。在制定配送计划时假定车辆在某路段的行程时 2 第一章绪论 间是固定值的作法显然与事实相悖。由于交通状态的变化严重影响车辆行程时 间，所以非常有必要将交通状态的影响纳入制定物流配送计划的重点考虑因素。 v o l u m e - s p i e d - o c c u p a n c yc o r m l m s tf i g u r e 图1 1 某路段2 天的交通流变化 注：虚线反映2 0 0 6 年5 月3 1 日交通流参数，实线反映2 0 0 6 年6 月4 日交通流参数。 1 1 2 3 缺乏不同交通状态对v r p 问题影响的系统研究 在基本车辆路线问题( ) 研究的基础上，车辆路线问题在学术研究上产生 了许多不同的延伸和变化型态 1 5 , 1 6 】，包括时间窗限制车辆路线问题( v e h i c l e r 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 r p d t ) 、多车种车辆路线问题( f l e e ts i z ea n d m i xv e h i c l er o u t i n gp r o b l e m s ， f s 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 hm u l t i p l e u s eo f v e h i c l e ，v r p m ) 、考虑回程的车辆路线问题( v e h i c l er o u t i n gp r o b l e m sw i t h b a c k h a u l s 。v r p b ) 、随机需求车辆路线问题( v 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 c d e m a n d 。v r p s d ) 等。杨锦冬【1 1 】研究了有交通约束的车辆配送问题，但只是考虑 货车通行路段限制、单行线限制及道路交通饱和度的限制，并未对交通流的状 态进行系统分析与分类，更没有考虑不同交通状态下车辆行程时间的问题。 实际上，车辆在道路上的行程时间不是仅与路径长度成正比的固定值，而 是随着该道路上交通状态的变化而变化的量。在同一路段上，车辆在不同交通 流状态下的行程时问是不同的。同时，某一路段在某种交通流状态下的预测行 程时间也不会是定值，这是由不同状态下行程车速的波动造成的。某种交通状 态下车速的波动导致在该种交通状态下的行程时间在某一范同内波动，即表现 出行程时问预测的区间性。 1 1 2 4 现有v r p 的研究很少考虑行程时间的类区间性( 模糊性) 就笔者所查阅文献而言，国内外对v r p 问题行程时间的区问性问题研究较 第章绪论 少。多数研究者考虑的是车辆到达顾客点的可容忍时间的区问性，从顾客满意 度的角度研究车辆到达时间的影响，而不是车辆在路径上行程时间的区间性。 b a n ，x g 等【2 】研究了车辆行程时间的模糊性，将车辆的模糊行程时间确定为 由固定部分和可变的误差区间两项组成，但并未解决误差区间项的具体计算问 题，另外，他们也没能把这种模糊行程时间引入物流配送问题的研究。张建勇【1 4 】 在研究中考虑了行程时问的模糊性，将模糊性的行程时间作为成本约束项建立 了v r p 的模型，但他未对模糊行程时间的确定进行研究，同时也没有考虑交通流 状态对模糊行程时间的影响。 鉴于以上理论和实践的需要，有必要研究道路交通状态的归类属性，并在 此基础上对各种交通流状态下的行程时间的模糊性进行分析。 1 2 研究问题界定 本文对车辆配送问题的研究是基于交通流状态分析和预测的。受各种因素 的影响和制约，交通流状态是时变的、不确定的，导致车辆在某路段上的行程 时问具有不确定性，因而配送车辆在配送路径上的行程时间是难以事先准确预 知的。然而，笔者在长期的观测分析中发现，在某固定路段上的交通流特征( 如 流量、占有率与行程时间) 在一天中的固定时段往往表现出在一定范围内的相 对稳定性( 在这个范用内的波动较小) 。本文根据路段交通流在不同时段所表现 出来的不同波动范闱定义交通流的不同状态，进而研究在不同状态的交通流情 况下静态及动态的车辆配送路径问题。 交通流状态的分析、描述和预测是本文研究的重要内容之一。交通流各种 状态的出现本身具有不确定性，而即使在同一状态下的交通流特征参数也是在 某一范围内波动的。交通流状态的这种不确定性和波动的类区间性，采用模糊 数学工具进行研究是比较适宜的。鉴于此，本文在对交通流状态划分、描述和 预测时利用了模糊数学理论和分析工具。本文研究的另一重点内容是分析不同 交通状态下车辆的配送问题。由于交通流状态的预测在本文中分为静态和动态 两种，因而车辆配送问题的研究相应分为静态和动态两种情况。 4 第一章绪论 1 2 1 原始v r p 问题 车辆配送问题，一直是运筹学与组合优化领域的前沿与热点问题。在现实 生产和生活中，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度 问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象 为物流配送车辆调度问题。该问题的一般描述是【2 6 】：有一个配送中心，对，个客 户进行服务，假定每个客户的重量g 均小于额定载重q ，求满足一定的约束条件 ( 包括车辆费用与时间费用) 总运输成本最小的车辆数k 和车辆行驶路线。数学 模型如下： r ai nz = c 盯x 驰 yg ：y vki q k 艺j v y 。= 1 i = l ，2 ， 工啦= y 酊= o ，1 ，；v k i = yf = ，1 x i j y k i01 ，；vk 艺 t= j = ，；v z 渺，一1 i ，j es j 毗= 0 或1 i ，= 0 ，1 ，；vk y 。，= o 或1i ，= 0 ，1 ，；vk 在上述模型中，f 代表配送中心与客户的编号，其中配送中心的编号为0 ，客 户的编号为从1 到，；当客户f 的任务由车辆k 完成时，y 。；= l ，否则为o ；当车辆k 从f 行驶到，时，x , k = 1 ，否则为0 。式( 1 1 ) 为目标函数，式( 1 2 ) 表示每辆车所装的 货物总重量不能超过车辆的载重，式( 1 3 ) 限制每客户只能由一辆车服务，式( 1 4 ) 与式( 1 5 ) 限定了只能有一辆车从每个客户节点进来与出去一次，式( 1 6 ) 约束配送 车辆在任何一个客户本身中不形成回路。 q 表示从i 至：u j 的运输成本，可以是距离、费用、时间等评价指标。目前的研 究对的标定以确定性的实值为多。 d 动 q $ 回 乃 d -_1_1，_l 1 l ，i、，、，l，ji、，i、 第章绪论 12 2 本文对、1 r p 问题的分类 国内外对v r p u j 题进行研究的资料很多，就所搜集的资料及本文的研究需要 而占，本文将v r p i n 题的分类归纳 2e 牌艄1 如f 表11v r p 分类 序号 说明 # 一值耻 确定犁 辅机刑l 懒客薯求指_ 争鼯棚 ， - 单目标 问题目标 多i ；i 标 配送中心数e l 单中心 多中心 扦放耻心屈性 封闭型 确定性、随机性、纯挂( 卸) 、装卸混台等 单车喇 乍辆属性 多车刊 路网属性 静态 动态 无时间宙 时间窗属性 硬时间窗或软时间宙( v r p t w ) 路径费用对称或不对称等 第一章绪论 法详见第四、五章。 就v r p 问题的路径费用而言，主要指路径的距离或者时间。本文从时间角度 考察路径的费用。从时间角度分析，v r p 问题主要涉及路径行程时间费用、顾客 预约服务时间或时间窗等。本文研究路径行程时间费用。从路径费用的确定性 而言，有单一值型和区间型两种。由于模糊行程时间本身具有区间属性，是可 变的区间型路径费用。由于本文考虑了不同交通状态对行程时间的影响，因此 所研究的各路径的行程时间应是多种交通状态模式下的不同区间。 从v p p i h j 题的确定性角度，主要有确定性( 如确定的路径时间费用等) 和不确 定性( 如不确定性的路径时间费用等) 两种。不确定性问题又可分为随机性问题 和模糊性问题。随机性是对事件的某种结果而言的，是因果律的破缺造成的不 确定性。模糊性指存在于现实中的不分明现象，差异双方经历从量变到质变的 连续过渡过程。模糊性是排中律的破缺造成的不确定性。交通状态的划分，是 状态之间本身排中率的或缺造成的不确定性，因此是模糊性问题而不是随机性 问题。针对不同交通状态下的行程时间的预计，由于状态本身是模糊性问题， 因此各状态所对应的行程时间也必定具有类区间性( 即同样缺少排中率而具备模 糊性) 。 1 2 3 交通流状态分类和预测 交通系统的开放性和随机性使交通流状态随时间变化呈现较强的差异性和 时变性。本文研究的重点之一就是对道路交通状态进行分类，进而研究不同状 态下车辆的行程时间特性。各种交通流状态( 畅通、拥挤、堵塞等) 语义本身 的模糊性客观上要求对状态的划分是一种基于模糊理论的划分。在对道路交通 状况较长时间段的历史数据分析基础上，应用模糊集理论，分析道路交通状况 影响因素类，对各类状态进行数学描述。模糊数本身是区间数，从而各类交通 流状态的类区间性可以用模糊数来表示。用历史数据对隶属度函数进行建模和 标定。 首先研究在较长时期历史数据积累的情况下，对固定路段不同时段上的交 通流状态进行划分和描述，并以此做为第二天( 工作日与非工作日有所区别) 该路段上不同时段的交通状态所属类别和行程时间的初始预测信息( 静态预 测) 。 7 第一章绪论 其次，针对实时的交通流变化，研究交通流状态的动态预测。这种动态预 测不是微观的实时预测，而是针对配送计划制定和改变的需要所进行的一种中 观层面的预测。 1 2 4 基于模糊行程时间的车辆路径问题( 心f t t ) 车辆在道路上的行程时间不是仅与路径长度成正比的固定值，而是随着该 道路上交通流状态的变化而变化的量。在同一路段上，车辆在不同的交通流状 态下通过所需要的行程时间是不同的。同时，某一路段在某种交通流状态下的 行程时间预测值也不会是定值，而是一个区间量，这是由不同状态下行程时间 的波动性所决定的。 本文首先对交通流状态划分进行研究，并在此基础上研究基于模糊行程时 间的车辆路径问题( v e h i c l er o u t i n gp r o b l e m sw i t hf u z z yt r a v e lt i m e ，冲f t t ) 。 在道路交通状况历史数据积累的基础上，对次日各路段交通状态进行非精确的 判断，判断路段上相应于该种交通状态的模糊行程时间范围，根据这种区间性 的( 模糊) 行程时间制定物流配送方案( 静态车辆路径) 。在配送方案的执行中， 随着道路交通流的实时变化，交通状态可能与预测的状态不一致，需要研究与 交通状态变化相适应的车辆路径变更问题( 动态车辆路径) 。 1 3 国内外研究现状 配送车辆路径问题的研究最早可以追溯到1 9 5 9 年，i 主t d a n t z i g 和r a m s e r 首次 提出车辆调度优化问题。最初的研究局限于如旅行商问题和0 1 背包问题等基本 模型问题上，进一步的研究侧重在分析简单的车辆路径问题( v l 冲) 与一个配送 中心多个配送点的配送策略问题上，也有一些研究致力于较复杂的实际配送问 题、随机库存问题或对这些相关问题的整合。 交通研究分为微观和宏观两个角度，交通流状态本身的特征参数是集合的 概念，是通过大量的个体行为表现出来的。本文对交通流状态进行研究时，注 重于整体特征。通过采集足够的数据，从宏观的角度探讨路段及路径上的交通 流特征。在交通流研究领域，有学者专门研究交通流状态的分类，也有学者研 究行程时间的模糊性，但将二者结合起来研究不同交通状态的模糊行程时间的 8 第一章绪论 论著很少。桂小玲【2 7 】、罗丽君【2 引、李研【2 9 】等将聚类分析引入交通规划领域，对 站点规划、交通分配等问题进行了研究。陈德望【3 0 】基于回归分析的方法对快速 路的交通流状态进行了分类探索。b a n ，x 。g 2 】等研究了具有模糊行程时间的交通 流分配，并给出了模糊行程时间的一种概念模型。但这种模糊行程时间并没有考 虑交通状况的影响，同时由于这种模型的模糊行程时间是由固定部分和可变误 差项组成，而其误差项在现有手段下无法具体确定，因此只能束之高阁。另外， 他们也没能把这种模糊行程时间引入物流配送问题的研究。马国旗f 3 4 】对城市干 道的行程时间进行了分析。张建勇【1 4 】在研究中考虑了行程时间的模糊性，将模 糊性的行程时间作为成本约束项建立了冲的模型，但未对模糊行程时间的确定 进行研究，目标函数也只考虑了运行时间最短为优化目标，未考虑固定成本及 车辆运行的费用的影响，当然也没有考虑交通流状态对行程时间的影响。 国内外对v p j ) 问题行程时间的区间性问题研究很少。多数研究者考虑的是车 辆到达顾客点的可容忍时间的区间性，从顾客满意度的角度研究车辆到达时间 的影响，而不是车辆在路上的行程时间。 确定型v r p 与非确定型姆。文献【1 4 】认为，“如果一个公式的结果( 输出) 是一系列由确切己知的、且不随时间变化而变化的输入计算而得，并且不能重 新优化的规划好的路径，则该问题为确定型静态车辆路径问题。如果输出结果 由一系列非确定性输入计算而得的规划好的路径，则该问题为非确定型静态车 辆路径问题。而如果输出的不是一组路径，则是随输入的实时变化而规划路径 变化的策略，则该问题为动态车辆路径问题( 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 ) ”。因此，本文所研究的是非确定型静态v r p 和非确定型动态v r p 。 非确定v r p 分类。在现实中常碰到的两类不确定现象是随机现象和模糊现 象。相应地，非确定v r p 问题也可分为随机车辆路径问题( s t o c h a s t i cv e h i c l e r o u t i n gp r o b l e m ，s v r p ) 和模糊车辆路径问题( f u z z yv e h i c l er o u t i n gp r o b l e m ， f v r p ) 两类。 f v r p 问题研究综述。在v r p 问题研究中，很多因素具有一定的模糊性。例 如，估计两个节点间的大约费时3 0 分钟等问题，在主观估计时，没有人会估计 成费时2 8 分钟，而一般描述成3 0 分钟左右，或半小时左右。这种行程时间的估 计不是客观测量的结果，而是随不同决策者主观判断的不同而变化，并且这些 判断的行程时间都是“t 分钟左右，即都是缺少排中率的。在研究领域，行程 时间通常也被看作随机变量，但在这种情况下要对旅行时间进行测度并建立特 9 第一章绪论 定的概率密度函数。但在很多情况下，决策者需要根据其对绝对行程时间的经 验进行主观估计，将行程时间表述成诸如“短”、“长”、“t s ? 钟左右刀等模糊语 句。到目前为此，研究f v r p 的论著还很少，而研究模糊行程时间的廿问题 ( v r p f t t ) 的论著就更难遇了。下面将研究f v r p 相关问题的一些文献做一简单介 绍。 p e r i n c h e r r y 和k i c u c h i t 3 5 】研究了模糊环境下的转载转乘问题，引入了模糊线 性规划原则处理模糊输入信息( 需求、供给、转运点储存成本等) 条件下的转运问 题。但他们研究的行程时间以及相关费用是精确信息，而不是模糊行程时间费 用。t e o d o r o v i c 和p a v k o v i c t 3 6 1 研究了单车场具有模糊顾客需求的车辆路径问题。 在文中，他们假设只是大概知道各节点的需求，并用三角模糊数来表示需求， 而其它条件都是确切己知的，目的是设计最小化总费用的车辆路径。t e o d o r o v i c 和r a d i v o f e v i c l ，7 】对模糊动态d i a l - a r i d e i h 题进行了研究。他们假设每一顾客都有 一个偏好或者期望的开始服务时间，每一顾客都有其特定的起点和终点。作者 假设顾客、驾驶员和调试员对行程时间的认识都是模糊的，并且顾客的期望开 始服务时间也是模糊的。但他们并没有系统研究模糊行程时间的确定方法。c h e n 和g e n 从模糊预约时间的概念角度描述了模糊车辆路径问题，并提出了一种解决 模糊车辆路径问题的遗传算法。他们提出的目标是最小化车队大小，最大化顾 客满意度，最小化总行驶距离和总等待时间。 1 4 研究目的、内容和思路 1 4 1 研究目的和内容 1 4 1 1 研究目的 通过研究交通流状态的分类，理清各路段上不同时段的交通流状态的分类 特性，从而在制定配送计划时能够对路段上的交通状态进行较准确的判断，对 车辆在道路上执行计划所需时间做出更加科学的预测。 研究基于交通流状态的路径模糊行程时间，建立基于模糊行程时间的车辆 配送问题理论框架及实用算法，为制定基于交通流状态的车辆配送方案提供一 套切实可行的方法，为物流配送提供决策支撑。 1 0 第一章绪论 1 4 1 2 研究的主要内容 ( 1 ) 交通流状态分类 在对道路交通状况较长时间历史数据分析的基础上，应用模糊数学理论工 具，建立道路交通状况影响因素类，对各类交通流状况进行分类和数学描述。 在历史数据积累基础上，并对第二天的各路段的交通状况进行初步的预测，判 断各路段的交通状况所属类别。 ( 2 ) 路段交通流状态隶属函数的建模和求解 单个交通主体模糊行程时间是有主观测度范围的模糊数，关