（道路与铁道工程专业论文）商用车辆应急调度研究.pdf

摘要 摘要 对于物流企业来讲，车辆调度是整个物流企业运作中的核心，对于提高整 个企业的服务水平和降低物流成本都有重要的作用。而现有的交通状况是道路 上的交通拥堵现象很严重，这样常常会导致配送车辆不能按时完成日常调度制 定的配送计划。当物流企业的车辆发生堵塞时，如何有效得制定应急调度计划， 对物流企业就显得尤为重要。因为从客户的角度来讲，客户评价物流公司的很 重要得指标之就是物流公司是否能够准时、安全的把货物送到客户指定的地 点；从物流企业的角度来讲，降低成本是企业赖以生存得条件，而车辆发生交 通堵塞就意味着物流成本得增加，这两点都需要物流公司在车辆发生交通堵塞 时迅速制定应急调度方案，实现物流企业的资源优化配置，最大限度的降低物 流企业的运营成本。同时，商用车队也是城市交通中的一个大的组成部分，如 果商用车队在发生交通堵塞时及时的制定应急调度方案，避开交通拥堵的路段， 这从客观上也有利于缓解道路上严重的交通拥挤问题。所以我们有必要针对应 急调度问题展开研究。 本论文针对由于道路交通堵塞引起的物流企业的车辆不能按时完成日常调 度制定的配送计划的问题进行了分析，在经过实地调研的基础上，分析了物流 公司的现有的业务模式，提出了应急调度模型。并以地理信息系统为平台构建 了商用车辆应急调度系统。具体的说本论文共由六部分构成。第一部分为绪论， 简要论述了论文的课题来源、研究背景、研究对象、研究的思路和方法以及本 论文研究的意义。第二部分则主要介绍了国内外相关研究的状况，分别从模型 和算法两个角度论述了国内外的学者在车辆调度方面所做的工作。第三部分笔 者通过对应急调度问题进行系统的分析，在此基础上提出了应急调度模型。第 四部分针对应急调度模型选取了相应切实可行的算法，并针对算法的流程进行 了详细的分析。论文的第五部分基于a r e g i s 8 3 ，a r c s d e 8 3f o ro r a c l e ，s q l s e v e r8 0 ，在整个北京市的电子地图上开发了物流配送车辆应急调度系统。在 论文的第六部分首先说明了模型采用启发式算法的合理与可行性，然后通过实 例解释了应急调度模型在实际中的应用情况。最后总结了论文的研究内容和研 北京工业大学工学硕士学位论文 究成果，并对未来的研究工作做了简要的前瞻。 关键词应急调度；启发式算法；局部搜索；九交换 a b s t r a c t f o rt h el o g i s t i c sc o m p a n y ，h o wt od i s p a t c ht h ev e h i c l et oa c c o m p l i s hi t s b u s i n e s si sk e yi nt h el o g i s t i c sc o m p a n yo p e r a t i o n ，a n di sv e r yi m p o r t a n tf o r i m p r o v i n gt h el o g i s t i c sc o m p a n y s e r v i c ea n d r e d u c i n gt h el o g i s t i c sc o m p a n y c o s t b u tt h ec o m m e r c i a lv e h i c l eo r e nc a n ta c c o m p l i s ht h ei o g i s t i c sc o m p a n yd a i l y d i s p a t c hb u s i n e s s e sb e c a u s eo f t h eb a d t r a f f i cc o n d i t i o nf o re x a m p l et h et r a f f i c j a m w h e nt h ec o m m e r c i a lv e h i c l ei si nt h er o a di nw h i c ht h et r a f f i c j a mo c c u r s ，h o wt o m a k et h ee f f e c t i v ee m e r g e n tv e h i c l es c h e d u l i n gp l a ni sv e r yi m p o r t a n tf o rt h e l o g i s t i c sc o m p a n y b e c a u s ef o rt h ec l i e n t ，t h eo n eo f t a r g e t so f e v a l u a t i n gt h e l o g i s t i c sc o m p a n yi sw h e t h e rt h el o g i s t i c sc o m p a n yc a nc a i yt h ec l i e n t sf r e i g h tt o a p p o i n t e dp l a c ei ns a f e t ya n do nt i m e f o rt h el o g i s t i c sc o m p a n y ，r e d u c i n g t h e l o g i s t i c sc o s ti sv e r yi m p o r t a n t ，b u tt h a tt h ec o m m e r c i a lv e h i c l e m e e tt r a f f i cj a m m e a n st h el o g i s t i c sc o s ti n c r e a s i n g s of o rt h ec l i e n ta n dt h el o g i s t i c sc o m p a n y ，t h e y b o t hh o p et h a tw h e nt h ec o m m e r c i a lv e h i c l em e e tt r a f f i c j a m ，t h el o g i s t i c sc o m p a n y c a ni nt i m em a k et h ee m e r g e n tv e h i c l es c h e d u l i n gp l a nt om a k et h eb e s tu s eo f l o g i s t i c sc o m p a n ys o u r c ea n dc a r da sm a n yb e n e f i t s 嬲p o s s i b l eu s i n gt h el e a s tc o s t i nt h es a m et i m e ，t h ec o m m e r c i a lv e h i c l ei st h ep a r to f c i t yt r a f f i c i f w ec a l li nt i m e m a k et h ee m e r g e n tv e h i c l es c h e d u l i n gp l a nw h e nt h ec o m m e r c i a lv e h i c l em e e tt h e t r a f f i cj a ma n dl e tt h ec o m m e r c i a lv e h i c l ea v o i dt h er o a di nw h i c ht h et r a f f i cj a m o c c u , i ti sa v a i lt or e d u c et h ep r e s s u r ec a u s e db yt h et r a f f i c j a mp r o b l e mi nt h er o a d i ti sn e c e s s a r yt os t u d yt h i sp r o b l e m t h i sp a p e ri sa i m sa ta n a l y s i st h ep r o b l e mt h a tl o g i s t i c sc o m p a n yv e h i c l ec a n t f i n i s hi t st a s ka c c o r d i n gt ot h ed a i l ys c h e d u l eo nt i m eb e c a u s eo f t h eh e a v yt r a f f i c j a m o nt h eb a s eo f t h es i t es u r v e y ，w ea n a l y s i sl o g i s t i c sc o m p a n y st h em o d e lo f b u s i n e s sa n ds u g g e s tt h ee m e r g e n tv e h i c l es c h e d u l i n gm o d e l b a s e do ng e o g r a p h i c i n f o r m a t i o ns y s t e m ，w eb u i l du pt h ee m e r g e n tv e h i c l es c h e d u l i n gs y s t e m c o n c r e t e l y ，t h i sp a p e rc o n s t i t u t e so f s i xp a r t s t h ef i r s tp a r ti st h ei n t r o d u c t i o n ， w h i c hs i m p l ys u g g e s t st h es o u r c eo f t h i sr c s e a r c h ，t h es t u d yb a c k g r o u n d ，t h es t u d y o b j e c t ，t h es t u d ym e t h o da n dt h em e a n i n g o f t h er e s e a r c h t h es e c o n dp a r tm a i n l y r e v i e w so v e l s e a sa n dd o m e s t i cp r e v i o u ss t u d i e s ，a n da n a l y z e st h e i rs t u d yf r o m m o d e la n da r i t h m e t i c i nt h et l l i r dp a r t , t h ea u t h o ra n a l y z e ss y s t e m i c a l l yt h e c n a e r g e n tv e h i c l es c h e d u l i n gp r o b l e m ，a n db a s e dw h i c ht h ee m e r g e n tv e h i c l e s c h e d u l i n gm o d e li sp u t t e df o r w a r d t h ef o u r t hp a r tw es e l e c tt h eu s e f u la r i t h m e t i c f o rt h ee m e r g e n tv e h i c l es c h e d u l i n gm o d e l ，a n dw ep a r t i c u l a r l ya n a l y s i st h ef l o wo f t h ea r i t h m e t i c t h ef i f t hp a r tb a s e do na r c g i s 8 3 ，a r c s d e 8 3f o ro r a c l e ，s q ls e v e r 8 0 ，w eb u i l du pt h ee m e r g e n tv e h i c l es c h e d u l i n gs y s t e mo nt h eb e i j i n gd i g i t a lm a p t h es i x t hp a r ta n a l y z e st h ef e a s i b i l i t ya n dt h er a t i o n a l i t yo f t h eh e u r i s t i ca r i t h m e t i c a d o p t e db yt h em o d e l ，a n dt h e nd e m o n s t r a t e st h ea p p l i c a t i o no f t h ee m e r g e n tv e h i c l e s c h e d u l i n gm o d e l a tl a s t ，t h ep a p e ra c h i e v e m e n ti ss u m m a r i z e da n dt h ef u t u r es t u d y i sa l s os u g g e s t e d k e y w o r d s e m e r g e n tv e h i c l es c h e d u l i n g ，h e u r i s t i ca r i t h m e t i c ，l o c a ls e a r c hd e s c e n t ， x - i n t e r c h a n g e i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 弦列，西 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：邀叠宏导师签名：兰土盏l 坠日期：型：梦 第1 章绪论 1 1 课题来源 第1 章绪论 本课题来自北京市科学技术委员会设立的“商用车辆运营关键技术及示范 工程”项目，它是“北京市智能交通系统规划与实施方案研究”大课题中的重 点科研项目。该项目主要是为北京市中小型物流企业提供一套切实可行的商用 车队调度的解决方案。本研究课题为该项目的子课题，“商用车辆的应急调度 系统”。 1 2 研究背景 1 9 0 1 年j f g r o w e l l 在美国政府报告“关于农产品的配送”中，第一次论述 了对农产品配送成本的各种因素，揭开了人们对物流认识的序幕。1 9 2 7 年 r b o r s o d i 在“流通时代”一文中首次用l o g i s t i c 来称呼物流。日本1 9 5 6 年从美 国引入物流概念，在对国内物流进行调研的基础上，将物流称之为“物的流通”。 至1 9 6 5 年，物流一词正式为理论界和实业界全面接受。 目前，发达国家的物流业在整个国民经济中已经占有重要的地位，企业对 物流越来越重视，第三方物流发展十分迅猛。据有关统计：欧洲物流营业额1 9 9 8 年和1 9 9 9 年分别为：1 4 6 0 亿美元、1 5 4 0 亿美元。7 1 的德国企业和5 3 的美 国企业把物流放在企业经营第一或第二的位置。在美国，第三方物流被认为尚 处于发展期，但在欧洲，普遍认为第三方物流市场已经具有了一定的成熟度。 目前欧洲使用第三方物流服务的比例约为7 6 ，美国约为5 8 ，同时，欧洲约 有2 4 ，美国约有3 3 的非第三方物流服务用户正在积极考虑使用第三方物流 服务。据统计，1 9 9 4 年美国第三方物流企业的收入为1 5 0 亿美元，1 9 9 6 年为 2 5 0 亿美元。在未来的3 5 年中，第三方物流业将以1 5 。2 0 的速度递增。1 9 9 7 年，在美国的主要市场( 汽车、化学、计算机、日用品、医药品和医疗器械) 第三方物流的利用率已达到7 3 。 我国自八十年代初引进“物流”概念和理论以来，在很长一段时间里没有 引起足够的重视。随着社会主义市场经济体系的逐步完善，市场一体化、竞争 北京工业大学工学硕士学位论文 国际化趋势的加强，物流作为一个提高经济竞争力的关键因素和影响众多领域 发展的、巨大的潜在市场，开始为各界广泛的关注，尤其是在1 9 9 9 年11 月， 国家经贸委会同世界银行在北京召开了现代物流国际研讨会后，我国的现代物 流有了迅速发展。 对于物流企业来讲，车辆调度是整个物流企业运作中的核心，对于提高整 个企业的服务水平和降低物流成本都有重要的作用。 对于客户来讲，希望物流公司能够准时、安全的把货物送到客户指定的地 点；同时，对于物流企业本身来讲，需要在满足客户的这一点需求的基础上， 尽可能的降低物流成本，这两点都需要有良好的车辆运营调度作保障。 干线运输和市内配送构成的运输费用在物流成本中占有较大比重。2 0 0 0 年 美国物流成本中，仓储和运输费用的总和占到整个物流成本比重的9 6 ，分别 为仓储费用3 7 7 0 亿美元，运输费用5 8 5 0 亿美元。 我国已经加入了w t o ，在这近几年中，我国将会成为全球真正的生产基地， 同时也是世界上最大的市场。在生产和销售过程中，物流就显得尤为重要，尤 其物流效率仍然有待提高。但是随着我国在机动化进程中车辆的增多，人们的 出行变得越来越困难，昔日条条大路通罗马，今日驶车不如步行快。无论是出 行在外，还是生活在某个城市当中，交通出行问题已经是最大的困惑了。这样 在物流公司执行配送的过程中，由于道路交通状况的影响，使得交通状况常常 使原来的安排的配送计划安排失效。 2 0 0 1 年在美国的加州所作的调查问卷表明：有3 0 的货运公司经理说交通 拥挤经常或者非常经常影响车辆任务的时间安排，大多数( 5 6 ) 的经理说有 时候交通拥堵会使时间安排失效，只有1 5 的说没有多大影响。参见图1 - 1 ： 第1 章绪论 1 5 1黧，圜赢凰 从不有时经常频繁 图卜1 经理对交通堵塞是否导致调度计划失效的反应 f i g u r e1 - 1m a n a g e r sr e s p o n s et ot h eq u e s t i o no f p l a nf a i l u r ef o rt r a f f i c j a m 对于交通拥堵是否需要改变交通路线的问题，8 0 的驾驶员说至少有时候 是需要改变配送路线的，只有2 0 的驾驶员说不受影响，具体参见图1 2 ： 而 。 2 0 霪 i羹圈。意。凰 从不有时经常频繁 图l - 2 司机对交通堵塞是否导致路线计划失效的反应 f i g u r ei - 2d r i v e r sr e s p o n s et ot h eq u e s t i o no f c h a n g i n gr o u t ef o rt r a f f i c j a m g o l o b 针对这种状况，在大量调查数据的基础上，利用构造性均衡模型 ( s t r u c t u r a le q u a t i o nm o d e l i n g ，s e m ) 对交通拥挤和应用车辆调度软件之间的 关系进行相关分析，分析结果表明：交通拥挤的不断加剧将会导致车辆运营调 姆 o 筛 吣 吨 洲 嘶 傩 o 6 5 4 3 2 1 北京i 业大学工学硕士学位论文 度软件需求的提高。同时也表明，智能交通信息系统中实时交通信息应用到车 辆调度软件中可以大大提高软件的实用性【l j 。 新加坡的南洋工业大学( n a n y a n gt e c h n o l o g yu n i v e r s i t y ) 在2 0 0 1 年2 0 0 2 年对新加坡的5 0 0 家物流企业进行调查。调查结果表明：大部分企业的车辆管 理系统不是很有效。对于车辆运输的影响因素方面，交通拥挤也是最重要的影 响因素 2 1 ，由此得到的一个很重要的结论就是要进行动态车辆调度管理研究和 软件开发。 1 3 商用车辆应急调度的概念 商用车辆应急调度是指当道路由于交通事故等原因发生交通拥堵或者客户 的需求突然发生变化等紧急事件导致原来的配送计划不能继续执行时，根据当 时的车辆、道路状况等实时采取相应的补救措施和方案，进行车辆调度安排， 以保障最新配送目标的准时完成。 根据紧急事件发生的原因，可以将应急调度的对象分为两类：一类是由于 客户的原因。包括客户临时提出新的任务请求或撤消某项业务请求；一类是由 于交通条件。如发生交通事故、交通拥堵等。这些突发事件往往会打乱正常的 调度计划，或者造成原来制定的配送计划不能按时完成。上述任何一类情况的 应对措旋可以有很多变化，由于篇幅的关系，本论文只针对后一种情况即由于 道路发生交通拥堵而导致日常调度计划不能按时完成的情况展开讨论。 本研究设想的条件如下( 参见图1 3 ) ：一配送车辆原计划由配送中心出发， 经节点完成配送任务。但现行驶到节点之间时，遇到严重交通拥堵。 为此，需要紧急启动应急调度系统。 第1 章绪论 图1 - 3 应急调度条件图 f i g u r e1 - 3t h ec o n d i t i o no f e m e r g e n tv e h i c l es c h e d u l i n g 1 4 课题研究对象的界定 5 当道路发生交通事故、交通拥堵等使得原有的配送车辆可能不能按原计划 完成配送任务。此时车辆的状态可能是有货和无货两种。有货的情况比较复杂， 因为无货只是相当于货物为零时的一种特殊情况；在车辆剩下还未完成的业务 中可能是集货、送货、集送一体化业务的组合。如果发生堵塞的车辆不能完成 剩下的业务，则可以调度附近的车辆进行协助完成或者从配送中心另外调配车 辆协助调度。 由上面可知，当应急调度发生的时候，面临的情况是以下三种元素各种状 态的组合。 j e 京工业大学工学硕士学位论文 图l - 4 应急调度分类图 f i g u r e1 - 4t h ec l a s s i f i c a t i o no f e m e r g e n tv e h i c l es c h o d u l i n g 考虑到解决问题的可能性和现实性，我们在建模时把应急调度产生时的状 况设定为发生堵塞时车辆的状态是车上有货，剩下朱完成的业务是集货、送货、 集送一体化三者的混合业务，协助配送的车辆要从配送中心重新进行调配。 当发生堵塞的车辆上存在货物的时候，则在该车辆剩余要配送的业务中， 必然有一些业务是该必须由该车辆进行配送的，例如送货业务，货物在原有配 送车辆车上并且配送中心没有该货物的情况；以及集送一体化业务，车辆已经 完成取货业务在送货的途中。这样在应急调度的业务类型中，除了集货、送货、 集送一体化业务，还存在一类业务类型就是发生堵塞车辆必须要进行配送的业 务。 第1 章绪论 1 5 研究的思路和方法 本课题的研究思路是首先回顾和总结国内外相关的研究，然后分析应急调 度产生的机理和影响应急调度的因素，在进行分析的基础之上对应急调度进行 建模，最后利用启发式算法对模型求解，并对算法的有效性进行评价。 1 6 课题的研究意义 城市道路作为城市的大动脉，承担着城市中的交通出行，道路的交通状况 在相当程度上影响着城市的出行质量。调查显示，目前，北京市道路交通拥堵 问题比较突出，1 2 2 在一周之内，平均每天接到的交通拥堵报警电话为四五百 起。早晚流量高峰期间，9 0 以上的道路交通处于饱和或超饱和状态，特别是 二、三、四环等几条环路和环路之间的联络线，交通拥堵尤为严重，给市民的 工作、生活带来了极大的不便。严重影响着人们的出行质量，也造成了社会资 源的极大浪费。 图1 - 5 北京市道路情况 f i g u r e1 - 5t h es t a t u so f t o a di nb e u h a g 当物流企业的车辆发生堵塞时，如何有效得制定应急调度计划，对物流企 业就显得尤为重要，因为物流作为一个服务性行业，客户对物流公司评价得很 重要得指标之一就是物流公司是否能够准时、安全的把货物送到客户指定的地 点；同时，对物流企业来讲，降低成本也是企业赖以生存得条件，而车辆发生 交通堵塞就意味着物流成本得增加，这两点都需要物流公司在车辆发生交通堵 塞时迅速制定应急调度方案，实现物流企业的资源优化配置，最大限度的降低 7 北京工业大学工学硕士学位论文 物流企业的运营成本。 同时，商用车队也是城市交通中的一个大的组成部分，如果商用车队在发 生交通堵塞时及时的制定应急调度方案，避开交通拥堵的路段，这从客观上也 有利于缓解道路上严重的交通拥挤问题。 第2 章国内外相关研究状况 第2 章国内外相关研究状况 2 1 国内外模型的相关研究 从应急调度的理论研究来看，国内的刘春林、戴更新、何建敏在这方面曾 做过一些研究，不过他们所做的研究大部分针对的是灾害发生时，紧急物资的 调度问题进行研究。它的一个最显著的特点表现在时间的紧迫性，决策者应以 较短的时间完成调度方案，应急活动旦开始，就有物资消耗，连续性条件就 是要保证在任何时刻己到达物资量满足物资持续消耗，即不能出现因物资供应 不足引起的应急活动的停止口j 。它描述的情境是有多个应急资源供应点，单个 的应急地点，多个应急资源供应点的资源总和大于应急地点的需求量，然后在 一定的约束条件下，求出参与应急的出救点和各个出救点的资源数量【4 】。这种 情况显然和我们所要表现的情况不一致。 从车辆调度的角度来看，王万平等系统介绍了智能物流配送服务系统的结 构模块f 5 】，包括货物自动信息识别系统、基于g s m g p s 技术的运载工具调度监 控系统、基于g i s 技术的物流网络和配送优化模型与系统、基于w e d g i s 的货 物实时信息查询与发布系统、现代物流实时跟踪系统平台设计的解决方案。整 个构架较为完整，并基于g i s ，并结合i t s 、e c ，但其核心模块物流网络配送 优化模型系统中并没有真正结合i t s ，尤其是动态路网交通信息，更加没有考 虑到当配送车辆发生交通堵塞时的应急处理状况。它的整个系统实际上不是真 正的物流配送调度优化，而是i t s 中的交通最优路线。 张开碧、胡向东在对智能化物流配送决策支持系统实现技术探讨中对物流 配送的主要因素进行了分析，提出影响因素包括道路网结构、运输工具、流量 流向、时限和成本，在建立模型的时候是建立的分层模型，包括路径优化、车 次优化、和发送计划生成三步，但也没有真正的考虑路网和道路状况。也不能 解决实际情况中当车辆发生交通堵塞时的应急调度问题【”。 姜丰伟研究了现代商业企业物流配送系统的建设与实施策略研究 7 1 。论文 主要分析了以电子商务为背景的现代商业企业建立物流配送系统的必要性和系 统的结构、功能。仅仅介绍了宏观的运输问题，对于具体的车辆安排以及应急 北京工业大学工学硕士学位论文 情况出现的处理方案并没有详细的阐述。 管仕平针对一个矿泉水配送企业的状况，设计了物流配送车辆调度实时优 化系统【8 。在研究的过程中，同时涉及到配送中心数量、位置的等问题。他所 谓的实时优化是针对客户的需求是实时变化的情况，实时做出相应的调度方案。 应该说这种情况属于应急调度问题，但是这不是我们本课题着重要研究的方面， 我们的着眼点在于车辆发生交通堵塞时的应急处理方案。 李军在对车辆调度问题的研究后，也在系统开发方面进行了简单的尝试。 其他的还有一些在设计物流企业信息系统的时候，涉及到一点运输配送模块， 但这些运输的配送模块中都没有涉及应急调度部分的，从理论和实际来讲都不 完善。如于瑞波f ”。朱向梅在设计第三方物流决策支持系统的时候也只涉及了 运输管理和配载问趔1 0 。 另外一种就是适应外界环境变化而进行的调度。对于动态车辆调度，钟小 鹏在他的硕士论文中有详细的论述【1 1 】，他的论文详细论述了日常调度，但是对 应急调度却没有做进一步的研究，这样就显得整个系统不完善。 从企业的应用角度来看，我国的物流企业起步较晚，大部分是从传统的运 输仓储企业转型过来的以及刚刚成立不久的第三方物流企业，在车辆调度方面 比较薄弱。这一方面是还没有引起足够的重视，另一方面是没有足够的科研力 量进行相应的研究开发。基本上还是处于人工作业阶段，凭个人的经验进行调 度，真正应用车辆运营调度系统的很少，相应的软件系统也很少。有的物流企 业在企业信息系统中建立了运输管理系统，包括承运人查询、运单生成、发货 通知、运输及时率、运输成本分析和报关记录等。运输管理系统能将整个物流 网络的运输活动联系在一起，为每一个配送中心提供运输解决方案。具体的说， 运输管理系统能基于已有的承运人指标和客户定义参数，自动对每天的进货和 发货订单制定运输计划。在制定计划时，运输管理系统优先考虑紧急订单，并 将订单组合为发货单，同时根据货物的供应情况和客户要求的交货组织发货。 此外，运输管理系统按计划执行订单任务，并随时根据实际情况变化作出确认， 通过订单号查询发货状况、货物丢失与损坏索赔等，并提供给客户和承运人 1 2 】。 从中可以看出，这种运输管理系统实际上是一种办公系统，并没有真正的调度 第2 苹国内外相关研冗状况 作用。更没有办法进行车辆的应急调度。随着信息技术和其他技术的发展，越 来越多的物流企业也建立了地理信息系统( g i s ) ，在配送车辆上安装了g p s 等定位技术。但是他们主要是用这些技术对配送车辆进行监控，调度也仅仅是 知道车辆所在的位置后，进行人工调度。 人工调度不能满足现代物流企业的需求，因为人工调度具有以下不足：首 先，人工调度对于来说，调度人员的工作强度大。随着物流公司规模的不断壮 大，客户的需求越来越多，配送车辆数也在不断增多，到一定规模人工就难以 完成整个公司的车辆调度；其次，调度人员难以对所有车辆的状态，以及整个 城市的交通状况把握不是很准，难以对所有的资源进行全局优化，车辆的时空 利用率不高；另外，人工调度还受人员的限制，一旦调度人员不能工作，将会 影响整个公司的运营。 车辆运营调度作为物流企业运作中的核心，对于整个公司的运营效率有着 至关重要的作用。车辆运营调度软件系统不但可以更好的提高车辆的利用率， 而且可以减轻调度人员的工作强度，并且不会受人员的限制影响。 车辆运营调度模型是整个调度软件系统的核心部分，也是整个软件成功与 否的关键。当前国内外研究中的热点几乎都停留在理论上，离实际的应用还有 很大的距离，这就需要不但在理论上进行进一步的研究，而且在此过程中要更 加注重与实际相结合。 2 2 国内外算法相关研究 对于车辆调度模型的算法研究半个世纪以来一直是研究的热点，下面就在 车辆调度模型中经常用到的算法做逐一介绍。 2 2 1 模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n ga l g o d t h r n ) 是1 9 8 3 年由k i r k p a t r i c ks e l3 1 等人首次提出的随机性搜索方法，因为该技术适宜与比较大型的组合优化问题， 所以近些年来引起广泛的注意和重视 1 4 】。 模拟退火算法的基本思想就是用物质系统的退火过程来模拟优化问题的寻 北京工业太学工学硕士学位论文 优过程，当物质系统达到最小能量状态时，优化问题的目标函数也相应地达到 全局最优值。设优化问题的一个解i 等价于固体的一个微观状态i ，其目标函数 贝i ) 等价于固体能量e i ，用随算法进程递减的控制参数t 担当固体退火过程中温 度t 的角色，则对于t 的每一取值，算法持续进行“产生新解一判断一接受舍 弃”的迭代过程就类似于固体在某一温度下趋于热平衡的过程，也就是执行了 一次m e t r o p o l i s 算法。模拟退火算法从某个初始解出发，经过大量解的变换后， 可以求得给定控制参数值时优化问题的相对最优解然后减小t 的值，重复执行 m e t r o p o l i s 算法，就可以在t 趋于0 时，得到优化问题最终的全局最优解。固体 必须徐徐降温，才能使其在每一温度下都达到热平衡，最终趋于能量最小的基 态；温度t 也必须缓慢递减，才能确保模拟退火算法最终趋于优化问题的全局 最优解。 m e t r o p o l i s 准则是1 9 5 3 年m e t r o p o l i sn 等人在研究二维相交时提出的1 5 】， 模拟退火算法用m e t r o p o l i s 算法产生优化问题解的序列，并由与m e t r o p o l i s 准 则相对应的转移概率。 i 1 ，( 0 厂( ，) 唰旧力2 1 唧p 掣卜m 但。1 ) 确定是否进行从当前解i 到新解j 的转移。由上式可知，系统温度t 决定着 随机移动的转移( 接受) 概率。温度越高，则算法接受使目标函数上升移动的能 力越强，具有较强的“爬山”能力，温度很低则使目标函数值上升移动的接受 概率很低。 模拟退火算法在搜索策略上与传统的随机搜索方法不同，它不仅引入了适 当的随机因素，而且还引入了物质系统退火过程的自然机理。模拟退火算法依 据m e t r o p o l i s 准则接受新解，因此除接受优化解外，还在一个限定范围内接受 恶化解，这正是模拟退火算法优于局部搜索算法的本质区别所在。开始时，t 的值较大，可能接受较差的恶化解，随着t 的减小，只能接受较好的恶化解， 最后在t 趋于零时，就不再接受任何恶化解了，这就使模拟退火算法可以从局 部最优的陷阱中跳出，最后求出近似整体最优解。它的算法步骤描述如下： 第2 覃国内外相关研究状况 ( 1 ) 任意给定一个初始解x 。t = t 。：其中，t 为模拟退火算法中的温度，t 。 是算法的初始温度； ( 2 ) 若在该温度下达到内循环停止条件，则转到步骤( 4 ) ，否则从邻域内产生 一个新解x ： 计算接受概率，并在 0 ，1 区间内生成一随机数，如接受概率 该随机数则 令x o = x ； ( 3 ) 如果满足搜索结束条件，则转至( 5 ) ，否则返回步骤( 2 ) ； ( 4 ) 降低温度t ，返回步骤( 2 ) 进行降温后的新一轮循环； ( 5 ) 结束。 需要说明的是，由于模拟退火是随机搜索算法，尽管理论上以概率1 收敛 于全局最优解，但实际应用中由于参数选取及时间条件的限制，一般只能得出 优化问题的某近似最优解。而且算法的随机性也会导致优化结果的不确定性， 即每次优化计算结果是不确定的，这是现代优化算法的共性。 2 2 2 神经元网络 人工神经元网络( a r t i f i c i a ln e u r a ln e t w o r k ，简称a n n ) 的研究始于19 4 3 年， 它是由心理学家w s m o c u l l o c h 和数学家w p i t t s 所提出的m p 模型”】。m p 模型的提出不仅具有开创意义，而且还为以后的研究工作提供了依据1 8 j 。 8 0 年代以来，人工神经网络受到各国高度重视并已得到迅速发展的一门新 型学科。人的思维主要概括为逻辑思维( 包括联想) 和形象思维两种。以规则为 基础的知识系统可以被认为是致力于模拟人的逻辑思维，而人工神经元网络则 可被认为是探索人的形象思维。人工神经元网络是生理学上的真实人脑神经网 络的结构和原理，以及若干基本特性的某种理论抽象、简化和模拟而构成的一 种信息处理系统。从系统的观点看，人工神经元网络是由大量神经元通过极其 丰富和完善的连接雨构成的自适应非线性动态系统。由于神经元之间有着不同 的连接方式，所以组成不同结构形态的神经网络系统是可能的。而神经网络优 化算法就是利用神经网络中神经元的协同并行计算能力来构造的优化算法，它 将实际问题的优化解与神经网络的稳定状态相对应，把对实际问题的优化过程 1 3 北京工业大学工学硕士学位论文 映射为神经网络系统的演化过程。b p 神经网络模型是目前应用最广泛的一种人 工神经元网络模型。它结构简单、理论完善、工作状态稳定、易于实现 1 9 】。 b p ( b a c kp r o p a g a t i o n 反向传播) 神经网络模型是一种用于前向多层神经网 络的反传学习算法，由美国加州大学的鲁梅尔哈特和麦克莱伦德在研究并行分 布式信息处理方法，探索人类认知微结构的过程中，于1 9 8 5 年提出2 0 1 。b p 网 络模型包括输入层、隐含层和输出层，同层单元之间不相连。如下图所示，b p 网络可以看成是一个从输入到输出的高度非线性映射函数。 b p 算法的学习过程由正向传播和反向传播两部分组成。正向传播过程中， 输入模式从输入曾经隐含层逐层处理，并传向输出层，每一层神经元的状态仅 影响下一层神经元的状态。如果在输出层不能得到期望的输出，则转入反向传 播过程，将误差信号沿原来的连接通路返回。其目的在于通过调整网络内部的 连接权及阙值使网络系统误差达到给定的精度2 “。 整个b p 神经网络完整的算法如下： 1 、初始化网络结构及学习参数，包括设置输入输出及隐含层单元数、隐含 层数、网络初始权矩阵、学习因子玎、动量参数口等； 2 、提供训练模式，开始训练网络； 3 、前向传播过程，输入给定训练模式，计算网络的输出模式，并与期望模 式比较，若满足误差要求，训练成功，退出程序。否则执行4 。 4 、反向传播过程： ( 1 ) 计算同一层单元的误差钟； ( 2 ) 修正权值和闽值： ( 3 ) 返回2 。 b p 网络存在以下问题1 2 2 z 3 】： l 、从数学角度b p 算法是一种提梯度最速下降法，算法性能依赖于初始条 件，学习过程容易陷入局部最小，而得不到整体最优。从表面上看，误差符合 要求，但这时所得到的解并不一定是问题的真正解； 第2 章国内外相关研究状况 2 、学习算法中的学习因子玎和动量参数口固定不变，训练容易陷入瘫痪， 收敛速度缓慢； 3 、网络中隐节点个数的选取尚无理论上的指导，仅凭经验而定； 4 、网络的泛化与推广能力较差，不能满足应用需要。在训练中学习样本有 以往旧样本的趋势。 2 2 3 禁忌搜索算法 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，简称t s ) 的思想最早由g l o v e r ( 1 9 8 6 ) 提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类 智力过程的一种模拟2 4 甾】。t s 算法通过引入一个灵活的存储结构和相应的禁忌 准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保 证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，t s 是 又一种搜索特点不同的算法。迄今为止，t s 算法在组合优化、生产调度、机器 学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优 化方面得到较多的研究，并大有发展的趋势【2 6 2 7 趣2 9 1 。 t s 算法的基本思想是：给定一个当前解( 初始解) 和一种邻域，然后在当前 解的邻域中确定若干候选解；若晟佳候选解对应的目标值优于“b e s ts of a r ”状 态，则忽视其禁忌特性，用其替代当前解和“b e s ts of a r ”状态，并将相应的对 象加入禁忌表，同时修改禁忌表中各对象的任期：若不存在上述候选解，则选 择在候选解中选择非禁忌的晟佳状态为新的当前解，而无视它与当前解的优劣， 同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述 迭代搜索过程，直至满足停止淮ne 3 0 1 。条理化些，则简单禁忌搜索的算法步骤 可描述如下： ( 1 ) 给定算法参数，随机产生初始解工，置禁忌表为空； ( 2 ) 判断算法终止条件是否满足? 若是，则结束算法并输出优化结果；否则， 继续以下步骤： ( 3 ) 平i j 用当前解工的邻域函数产生其所有( 或若干) 邻域解，并从中确定若干 候选解： 15 北京工业大学工学硬士学位论文 ( 4 ) 对候选解判断藐视准则是否满足? 若成立，则用满足藐视准则的最佳状态 y 替代z 成为新的当前解，即工= 弘并用与y 对应的禁忌对象替换最早进入禁 忌表的禁忌对象，同时用y 替换“b e s ts of o r ”状态，然后转步骤6 ；否则，继 续以下步骤； ( 5 ) 判断候选解对应的各对象的禁忌属性，选据候选解集中非禁忌对象对应 的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的 禁忌对象元素； ( 6 ) 转步骤( 2 ) 。 我们可以明显地看到，邻域函数、禁忌对象、禁忌表和藐视准则，构成了 禁忌搜索算法的关键。其中，邻域函数沿用局部邻域搜索的思想，用于实现邻 域搜索；禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；藐视准 则。则是对优良状态的奖励，它是对禁忌策略的种放松。 同时，与传统的优化算法相比，t s 算法的主要特点是： ( 1 ) 在搜索过程中可以接受劣解，因此具有较强的“爬山”能力； ( 2 ) 新解不是在当前解的邻域中随机产生，而或是优于“b e s ts of a r ”的解， 或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。 但是，t s 也有明显的不足，即：( 1 ) 对初始解有较强的依赖性，好的初始解 可使t s 在解空间中搜索到好的解，而较差的初始解则会降低t s 的收敛速度： ( 2 ) 迭代搜索过程是串行的，仅是单一状态的移动，而非并行搜索。 2 2 4遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ) 是模拟生物在自然环境中的进化过程而形 成的一种自适应、全局优化概率搜索方法。遗传算法的概念最早是由a a g l a y