（管理科学与工程专业论文）干线运输车辆调度问题研究.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：! 金：! ：笙日期：丝! z ! ：! 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子版， 允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和 汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：筮：! ：生导师签名：弛日 期：兰! 塑丝2 摘要 随着物流业的蓬勃发展，特别是专业物流公司的出现，降低物流成本成为企 业的第三利润源泉。运输作为物流主要基本功能之一，其成本的控制对物流成本 的降低有着举足轻重的作用。干线运输成本占运输总成本的绝大部分，而车辆调 度是运输合理化的关键，因此，对干线运输车辆进行优化调度是降低运输成本的 一种科学方法。随着国道主干线系统的不断完善和g p s 、g s m 、g i s 等技术的高速 发展，对干线运输车辆进行统一调度成为可能，也使研究干线运输车辆调度问题 具有重要的现实意义。 本文首先根据国内外运输行业发展的现状和趋势，详细论述了干线运输车辆 调度问题的基本情况，包括干线运输车辆调度的构成要素、分类、调度方式及问 题研究的难点。其次，对目前解决车辆调度问题的各种算法进行了系统的分类、 比较和总结。针对干线运输车辆调度的特点，本文提出了用遗传算法来求解干线 运输车辆调度问题，并对遗传算法的特点和实现方法作了重点论述。 在对干线运输实际背景作合理假设的基础上，建立了较完整的干线运输车辆 调度问题的数学模型。将基本遗传算法在交叉、变异等操作方面进行了一系列改 进，使之适用于干线运输车辆调度问题的求解。同时，对改进的遗传算法进行计 算机数值仿真实验，并对实验结果进行分析和评价。结果证明：本文采用的方法 比传统的调度方法有很大改进，它在整个服务周期内大大节约了运输里程，降低 了运输成本。 最后，本文应用d e l p h i7 0 开发了企业实际需要的干线运输车辆调度信息系 统。按照信息系统分析与设计的总体原则，对车辆调度系统的运行环境、功能模 块进行了详细的设计，并用计算机程序进行实现。该系统具有较好的实用性和可 扩展性，能提供科学合理的调度计划。通过该信息系统进行车辆调度，可以提高 车辆的利用效率，提高企业的运营效率，为企业创造更大收益。 关键词：干线运输；车辆调度；遗传算法；系统设计 7 w i t ht h e v i g o r o u sd e v e l o p m e n to fl o g i s t i c s , e s p e c i a l l yt h ea p p e a r a n c e o f p r o f e s s i o n a ll o g i s t i c sc o m p a n i e s ，l e s s e n i n gl o g i s t i c sc o s ti sb e c o m i n gt h et h i r ds o u r c e o fp r o f i t ，a n dt h i sm a k e sp e o p l ep a ym o r ea n dm o r ea t t e n t i o nt o l o g i s t i c sc o s t s r e d u c t i o n a so n eo ff u n d a m e n t a lm a i nb o d yo f1 0 9 i s t i e sf u n c t i o n , t r a n s p o r t a t i o n s c o s t - r e d u c t i o np l a y sam a j o rr o l ei nl o g i s t i c s sc o s t - r e d u c t i o n t r u c k - r o a dt r a n s p o r t a t i o n c o s ta c c o u n t sf o rt h em o s tt r a n s p o r t a t i o nc o s t , a n dv e h i c l es c h e d u l i n gi st h ek e yt o t r a n s p o r t a t i o nl o g i s t i c s s oo p t i m i z i n gt h ec o n t r o l l e ro nt r u c k - r o a dt r a n s p o r tv e h i c l ei sa s e i e n t i s mm e t h o dt or e d u c et r a n s p o r t a t i o nc o s t a l o n gw i t ht h ep e r f e c t i o no fm a j o r n a t i o n a l1 1 i g h w a ys y s t e ma n dt h es p e e d i n gd e v e l o p m e n to ft e c h n o l o g i e sl i k eg p s g s m ，g i se t c ，i tb e c o m e sp o s s i b l et os c h e d u lt r a c k - r o a dt r a n s p o r t a t i o nv e h i c l e s g e n e r a l l y , a n dt h i sa l s om a k e st h es t u d ya b o u tt r u c k - r o a dt r a n s p o r t a t i o nv e h i c l e s c h e d u l i n gh a si m p o r t a n tp r a c t i c a ls i g n i f i c a n c e t h i sp a p e rr e v i e w st h er e s e a r c hr e s u l t sa b o u tv e h i c l es c h e d u l i n gp r o b l e m , c o m b i n e sw i t l lt r u c k r o a dt r a n s p o r t a t i o n si n d u s t r ys t a t u sa n dd e v e l o p m e n tt r e n d sa n d a n a l y z e ss y s t e m i c a l l yt h eb a s i cq u e s t i o n sa b o u tt r u c k r o a dt r a n s p o r t a t i o nv e h i c l e s c h e d u l i n g ，i n c l u d i n gt h ec o n s t i t u e n te l e m e n t s ，c l a s s i f i c a t i o n , r e s e a r c hm e t h o d sa n d d i f f i c u l t i e so ft h et r a n s p o r t a t i o nv e h i c l es c h e d u l i n g t h i sp a p e rm a k e ss y s t e m i c c l a s s i f i c a t i o n , c o m p a r i s o na n ds u m m a r ya b o u tt h ep r e s e n ts o l u t i o n st o v e h i c l e s c h e d u l i n g a c c o r d i n gt ot h ef e a t u r e so f t r u c k r o a dt r a n s p o r t a t i o nv e h i c l es c h e d u l i n g ， t h i sp a p e rp u t sf o r w a r du s i n gg e n e t i ca l g o r i t h mt os o l v et h et r a n s p o r t a t i o nv e h i c l e s c h e d u l i n gp r o b l e ma n dm a k e sf o c u sd i s c u s so nt h ec h a r a c t e r i s t i c sa n di m p l e m e n t a t i o n m e t h o do f g e n e t i ca l g o r i t h m b a s e do nt h er e a s o n a b l eh y p o t h e s i sa b o u tt h ep r a c t i c a lb a c k g r o u n do ft r u c k - r o a d t r a n s p o r t a t i o n , t h i sp a p e rs e t su pr a t h e ri n t e g r a t e dm a t hm o d e l sa b o u tt r u c k - r o a d t r a n s p o r t a t i o nv e h i c l es c h e d u l i n gp r o b l e m t h i sp a p e rp u t su pas e r i e so f i m p r o v e m e n t s o nb a s i cg e n e t i ca l g o r i t h m si n t e r s e c ta n dv a r i a t i o nt om a k ei ts u i t a b l ef o rt h es o l u t i o n o ft r u c k - r o a dt r a n s p o r t a t i o nv e h i c l es c h e d u l i n gp r o b l e m t h ep a p e ra l s om a k e s c o m p u t e rn u m e r a ls i m u l a t i o ne x p e r i m e n to ni m p r o v e dg e n e t i ca l g o r i t h m t h er e s u l t p r o v e st h a tt h em e t h o du s e di nt h i sp a p e rh a sg r e a ti m p r o v e m e n tt h a nt r a d i t i o n a l 8 m e t h o d s ，i ts a v e st h et r a n s p o r t a t i o nm i l e a g ea n dr e d u c e st h ec o s ti nt h ew h o l es e r v i c e p e r i o d f i n a l l y , a i m i n ga ts p e e d i n gd e v e l o p m e n to f t r u c k - r o a dt r a n s p o r t a t i o na n d t h eh u g e a p p l i c a t i o nf o r e g r o u n d ，u s i n gd e l p h i7d e v e l o p st h et r u c k - r e n dt r a n s p o r t a t i o nv e h i c l e s c h e d u l c h i n gi n f o r m a t i o ns y s t e mt h a te n t e r p r i s e sr e a l l yn e e d a c c o r d i n gt og e n e r a l p r i n c i p l eo fd e s i g na b o u tv e h i c l es c h e d u l i n gi n f o r m a t i o ns y s t e m ，t h i sp a p e rm a k e s g e n e r a ld e s i g na n dc o m p u t e rp r o g r a ma b o u ts y s t e mr u n n i n ge n v i r o n m e n t a n d f u n c t i o n a lm o d u l e s t h es y s t e mh a sp r e f e r a b l ep r a c t i c a b i l i t ) ra n de x p a n s i b i l i t y , i tc a n p r o v i d er a t i o n a ls c h e d u l i n gp l a n s c h e d u l i n gv e h i c l e st h r o u g ht h i ss y s t e mc a ni n c r e a s e t h ev e h i c l e s u t i l i z a t i o ne f f i c i e n c y ，i m p r o v ee n t e r p r i s e s o p e r a t i o ne f f i c i e n c y , a n d c r e a t em o r ep r o f i tf o re n t e r p r i s e s k e y w o r d s ：t r u c k - r o a dt r a n s p o r t a t i o n ；v e h i c l es c h e d u l i n gp r o b l e m ； g e n e t i ca l g o r i t h r n ；s y s t e md e s i g n 9 第一章绪论 1 1 课题的研究背景 近年来，我国的高等级公路发展迅速，通车里程不断增加，并逐步趋于网络 化。特别是高速公路，路面质量好，通行能力大，且具有全封闭全立交的特点， 大大提高了车辆的行驶速度，使货物运输的及时性得到了可靠的保证。 根据交通部总体规划，到2 0 2 0 年，将建成总长度为3 5 万公里的“五纵七横” 国道主干线系统，形成贯通首都、直辖市、各省省会，连接全国主要城市的运输 大通道。届时，高速公路将达到7 5 0 0 0 公里，一、二级汽车专用公路5 5 0 0 0 公里， 纵横交错的高等级公路网，将为快速运输提供可靠的保障。 在高等级公路迅速发展的同时，运输业也取得了长足发展，但也存在着许多 问题需要解决。 从总体上来看，我国公路运输的发展，基本上是靠运输企业和车辆数量的规 模增长来实现的，是一种粗放式的低层次的发展。主要表现在当前公路货运市场 经营主体数量过多、规模较小。同国外运输业的高度组织化相比，我国道路运输 业几乎形不成规模，像中外运、中远物流等几家全国性的大企业，其市场份额也 只在1 3 n1 8 之间，缺乏全国性的物流中心和网络，而且经营主体高度分散，规 模经营严重不足。这就意味着经营主体之间缺少合作与交流，悖离了集约化发展 的方向，货物运输还基本处于单车单干的原始状态，未能形成整体优势。这使得 运输信息不畅，导致车辆单程载货，或者不能很好地衔接各项运输任务，从而导 致车辆空驶现象存在且相当严重，运输效率低下。据甘肃、河南、江苏、广东、 河北等地测算，货运汽车平均实载率只有5 2 。 目前，许多物流企业都意识到了这一问题，并采取了一些措施来加强货运组 织和运力调配，提高货运车辆实载率，降低空驶率。采取的措施主要有：扩大企 业规模，加强企业与企业之间的合作关系，如建立企业间的虚拟组织、建立企业 闻战略联盟、建立企业协同组织以及发展企业集团等。这样，运输网络覆盖范围 增大，运输任务增多，可调度的车辆循环使用、分布复杂，从而增加了调度的难 度。如何对干线运输车辆进行合理调度，提高车辆利用率，是我们必须面对且亟 l o 待解决的问题。 1 2 课题的研究意义 运输分为干线运输和支线运输。干线运输是以高等级公路为基础，以货物运 输市场为条件，充分发挥汽车运输灵活、机动、门到门的优势，使有形的运输对 象一一货物得到高效、快捷的位移。 在干线运输中，对车辆优化调度，其实质是合理安排运输车辆，最大限度地 满足不同时段、不同地域上产生的运输任务需求，并达到以最少的资源投入获得 最优经济效益的目的。 随着我国物流业的快速发展，省际型、区域型货运企业迅速发展起来，逐渐 从粗放型转向集约型，公司规模不断扩大运输网络不断完善。通过对干线运输 车辆的优化调度，可以提高车辆利用率，减少车辆空驶现象发生，优化货物运输 组织，从而降低运营成本，提高货物运输的经济效益，实现货物运输科学化，提 高企业的竞争力。 干线运输车辆调度的发展研究对我国运输业具有重要意义，特别是在物流迅 速发展的今天，对一些专业物流企业而言，合理实现车辆调度成为他们获得利润 的重要途径，也是企业竞争力提升和企业现代化的重要标志之一。同时，车辆优 化调度是物流实现集约化发展，构建综合物流系统，建立现代调度指挥系统，发 展智能交通运输系统和丌展电子商务的基础。 干线运输车辆优化调度除在汽车运输领域外，在水运、航空、通讯、电力、 工业管理等领域也具有一定的借鉴意义。 1 3 课题的研究现状 1 3 1 国内外运输行业发展现状 l 、国外运输行业发展现状 从7 0 年代以来，在一些经济发达国家，比如美国、日本和澳大利亚等，由于 社会经济和科学技术的发展与进步，社会工商业的运行趋于高效率和快节奏，对 货物运输的服务质量和时间要求也越来越高。国外大型运输公司发展较早、经验 丰富、规模强大，大多数拥有一套比较完整、先进的管理办法，在本国的运输市 场中处于垄断地位。一些著名的企业，如美国的联邦快运( u p s ) 、澳大利亚的t n t 、 瑞士的a s g 等，无一不具备先进的设备、发达的技术，倡导运输的快捷性、安全 性i ”。 目前，美国较大的从事运输的汽车运输企业，均在全国大部分城市布设站点， 建立自己的业务网络和通信系统，以便对货物运输的情况进行随时跟踪查询。有 关数据表明，在美国排名前1 0 0 位的公路货运企业全部是一级运输企业( 年营运 收入在5 0 0 万美元以上的企业) ，其中，年营运收入超过一亿美元的有8 2 个，这 足以说明美国货物运输企业的发展规模。美国的货物运输主要是以快速和优质的 服务吸引顾客，特别强调在时间上取胜：运距8 0 0 公里以内，当天到达；运距 8 0 0 - 2 4 0 0 公里，两天到达；运距2 4 0 0 - 4 8 0 0 公里，三天到达；运距4 8 0 0 公里以 上，基本4 天到达。除了集装箱运输外，厢式半挂车承担了主要部分。美国在过 去3 0 年罩投放在市场的厢式半挂车总量占半挂车总量的7 0 多。 澳大利亚公路快速货运是由取送运输和城间( 或城镇间) 运输两部分组成。 取送车辆一般采用载重量为1 4 吨的小型短途运输车辆，每天以城市货运站为中 心，在一定的区域范围内取送货物。城间运输车辆通常是载重量为8 吨以上的大 型货车，或由牵引车与挂车组合而成的汽车列车，其载重量可达3 0 吨，主要承担 城市问、城市和乡镇问的中长途运输。这种运输车辆一般在夜间行驶，夜间行程 可达1 0 0 0 公里。当运距超过1 0 0 0 公罩时，则采取轮换司机或牵引车的组织方法， 使载货汽车列车昼夜不停地行驶至目的地。一般而言，1 0 0 0 公里以内只需2 4 小 时即可运达，当运距长达数千公里时，可以在4 天之内从发货人送到收货人手中。 总体来看，国外公路货物运输具有以下主要特点： ( 1 ) 覆盖面广，服务范围广。由于公路网的密度远高于其它各种运输方式， 汽车运输具有机动、灵活、“门到门”的优势。 ( 2 ) 形成以现代化货运站为节点的运输服务体系。通过完备的货运站服务系 统集散货源，利用站内高效的分拣、装卸、仓储等设施中转货物，保障了干线运 输的通畅进行。 ( 3 ) 优质、高效的运输形式。站与站之间的干线运输通常利用高等级公路， 由大型货车或汽车列车来完成，运输作业一般在夜间进行；载货车专用化的发展 趋势非常明显，在主要发达国家专用车保有量已经占到重型车保有量的8 0 左右。 ( 4 ) 采用了先进的通信信息系统，实现站与站以及站与运输车辆之间的通信， 以满足现代化运输的信息管理。 ( 5 ) 规模化的经营主体。只有营运区域达到一定范围，具备了以站场为节点 的运输网络和服务体系，才能实现运输的全过程并取得良好的运营效果。 2 、国内运输行业发展现状 近2 0 年来，我园公路货物运输业有了巨大的发展，国民经济对公路运输的需 求不断增长，车辆保有量、公路里程迅速增加。我国在道路基础建设方面成绩显 著，由于国家对高等级公路建设的大量投入，以高等级公路为主体的国道主干线 系统建设速度很快，十几年自j ，我国的高速公路从1 9 9 2 年的6 5 2 公里增加到2 0 0 6 年的4 5 万公里，高速公路总里程仅次于美国，名列世界第二。服务范围和整体 技术水平大幅度提高，尤其是东部地区高速公路网已开始形成并发挥规模效益， 同时又以滚动式、递进式的扇面辐射，带动中部和西部地区的发展，在全国范围 内形成了以基本交通运输干线为基础的若干运输网络体系。 近几年来国内涌现出许多比较知名的货运企业，如山东佳怡、山东快直送、 河南长通、宁波中通、远征、华宇、佳吉等。但是我国本土企业在企业规模、服 务网络、信息化程度、财力及客户服务水平等方面同国外还有很大差距。 具体来看，当前我国公路运输业面临的主要问题有i ”】： ( 1 ) 社会物流信息系统不健全 目前由部分企业建立的物流信息系统规模小、信息量少、服务范围窄，因而 货源信息和车辆信息不能及时沟通，车和货不能很好的匹配。 ( 2 ) 生产企业的自货自运比重过大，对于专业化物流服务的需求少 据统计，目前全国自货自运车辆占全国运输车辆总数的7 0 以上。据中国仓 储协会组织的全国物流状况调查显示，工业企业汽车空驶率高达3 4 7 ，企业自 备汽车资源当中有6 0 0 5 的车辆处于严重闲置状态，导致企业生产成本增加，运输 效益低，运输浪费大。这是受以前计划经济体制形成的“大而全，小而全”的生 产模式所影响，这种自货自运的方式使得公路货运市场呈现货源封闭、市场需求 不足的状况，造成相当一部分生产企业不了解现代物流，仍然实行产、供、销 体化的经营模式，排斥专业化的物流服务，导致企业难以形成现代物流观念。 ( 3 ) 专业物流企业规模小，缺少主导型的大型运输企业 生产企业的自货自运比例过高，与此相对应，提供专业运输服务的企业比例 过小。目前，我国专业公路货运部门的车辆只占相应社会车辆总数的5 左右，规 模较大的国有大中型公路运输企业的发展步伐缓慢，规模经济的优势没有得到充 分发挥。联户、个体专业运输户拥有车辆占到专业公路货运车辆的2 5 左右，但 一般只拥有一、二辆车，规模太小。总体而言，我国目前大部分物流企业经营规模 较小，发展极不平衡，缺乏完整、合理的运力管理办法，物流服务专业化程度低。 ( 4 ) 货物运输方式滞后 公路运输企业的小规模、分散化的经营方式，造成货物运输方式严重滞后。 例如，依靠规模经济效益和整体实力运作的长距离、定点、定线、长短线相结合 的货物集散运输、大吨位拖挂运输等在发达国家较常见的运输形式在我国没有得 到有效的应用。我国公路、铁路多式联运等高级运输方式更是处于初级阶段，远 没有形成规模。 ( 5 ) 货运成本居高不下，制约行业发展 我国货物运输车辆的空驶率达3 7 ，某些专门运送特种货物的专用车辆，如 专门运送商品汽车的运输车辆，其空驶率高达3 9 ，每年损失高达1 0 0 亿元人民 币。据不完全统计，2 0 0 2 年我国运输成本约占国民经济总成本的3 0 。而此项成 本在发达国家仅占1 0 左右，也就是说仅从运输成本一项来看，我们还有约2 0 的空间可以去努力压缩。 ( 6 ) 运输市场缺乏统一管理，不能按照科学、合理的运输线路规划方法安排 车辆运行和配载，运输市场基本处于自由运行状态。 ( 7 ) 运输企业面临激烈的外来竞争 国外一些公司，瞄准我国运输市场建立货运合资公司，如t n t 在上海，u p s 在北京设立公司，美国d h l 与国内外运集团成立敦豪国际航空快件公司，他们的 运营必将对国内的物流行业形成冲击。面对严峻的竞争形势，我国传统的公路货运 企业需要转变经营策略，既要引进国外的资金、技术和设备等硬件，也要引进国外 先进的管理经验和经营思想等软件，以促进我国公路运输业向现代物流业转变。 1 3 2 国内外调度算法研究现状 车辆调度问题在d a n t z i g 和r a i n f 把r 于1 9 5 9 年提出后，它引起了人们极大的 兴趣，运筹学、应用数学、组合数学、网络分析、图论、计算机应用等学科的专 家与运输计划制定者和管理者进行了大量的理论研究及实验分析，取得了很大进 展。目前对调度问题的研究主要集中在配送车辆路线安捧上，而对干线运输的调 1 4 度研究较少，但算法是相通的，因此，对干线运输及配送的调度算法的研究现状 作一概述。 l 、国外研究现状 国外对运输及配送车辆调度问题作了大量而深入的研究，并取得了不少成果 6 1 ， 见表1 - 1 。 表1 - 1 国外研究成果 年代研究成果 d a n t z i g 和r a m s e r ( 1 9 5 9 ) 币1 j 用整数规划模式来处理包含大约1 0 到2 0 个顾 1 9 5 0 客点的小规模问题 早在1 9 6 2 年，b a l i n s k i 等人首先提出v r p 的集分割，直接考虑可行解集 合，在此基础上进行优化，建立了最简单的v r p 模型；c l a r k e 和 w r i g h t ( 1 9 6 4 ) 提出了一种启发式节约法来建立车队配送路线；g o l d e n ， n e l s o n ，p a e s s e n s 等人通过使用适当的数据结构，降低了它的复杂度； 1 9 6 0 1 9 6 8 年，r a o 等人在v r p 集分割的基础上引入了列生成方法进行求解， 这种算法本质上是最短路径算法，同时结合了分枝定界算法；d e s r o c h e 求解了有1 0 0 个客户的v r p ，c h r i g 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 个顾客点的问题 1 9 7 1 年，e i l o n 等人提出将动态规划法用于固定车辆数的v r p ，通过递 归方法求解； g i l l e t t 和m i l l e r ( 1 9 7 4 ) 提出先路径再分组的扫描法( s w e e p 1 9 7 0 a l g o r i t h m ) ；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 ) 指出虽然两阶段启发式方法可处理较 大型问题，但其涉及的运算效率是相当重要的问题 1 9 8 1 年，针对带能力约束、时问窗以及无停留时间的v r p ，f i s h e r 提出 了三下标车辆流方程。基于b e n d e r s 的分解方法，他们提出了一种启发 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 ) 建立一种人机互动 的启发式方法 t h a n g i a h ( 1 9 9 1 ) 和j o e ( 1 9 9 3 ) 分别用遗传算法求解v r p ，但是都存在“早 熟收敛”的问题；1 9 9 4 年，p w a r k 等人提出了重复匹配的方法，该算法 在其模型里同时考虑了时间约束和能力约束，因此适用于这类具有强约 束的v r p ，重复匹配算法也可求解较大规模的问题( 1 9 9 个客户) ； f i s h e r ( 1 9 9 5 ) 对最优化方法加以改善，已经可以解决5 0 到1 9 9 个顾客点 的车辆调度问题，同一时期，有不少学者利用启发式算法来解决车辆调 度问题，包括模拟退火法、确定性退火法、神经网络算法和禁忌搜索算 1 9 9 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 ) 以及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 ) 都利用禁忌搜索算法求解车辆调度问题；p a r e z a ，f r a n c a 研究 了禁忌搜索( t a b us e a r c h ) 算法；a b d o l h a m i d ，s a m e r k a e ，t a k a o e n k a w a ( 1 9 9 7 ) 提出用自组织的神经网络算法来求解车辆线路优化问题； l u i z ，d a l e s s a n d r o ( 1 9 9 8 ) 建立平行遗传算法；t a n ，l e e ，d u ( 2 0 0 0 结合遗 传算法、t a b u 树搜索算法的优点，形成知识库，用人工智能的方法来求 解；d e s a n ，g o r a r ( 1 9 9 6 ) 提出用模糊集理论来求解需点数不确定的车辆路 径问题；t a r a n r i l i s ，k i r a n o n d i s ( 2 0 0 2 ) 使用空间决策支持系统来解决车辆 路径问题：s h a w ( 1 9 9 8 ) 用大邻域搜索法对v r p 问题进行了求解；b b u l l n h e i m e r ，r eh a r d ，a n dc s t r a u s s ( 1 9 9 8 ) 对用蚂蚁算法来求解v r p 问题进行了研究 2 、国内研究现状 国内对车辆调度问题的研究较少，在2 0 世纪9 0 年代以后才逐渐兴起。近年 来，随着电子商务在我国的兴起和物流业务在我国展开并越来越得到重视，对车 辆调度问题的研究也同益受到学者们的关注，近年来取得的成果见表卜2 。 表i - 2 国内研究成果 作者 研究成果 以t s p 的最近距离启发式算法为基础，通过设置评价函数来处 李大卫 理时自j 窗约束，求解了简单的v r p 张震针对单车场满载问题，提出考虑运输行程约束的优化方法 利用遗传算法来求解物流配送路径优化问题。在建立物流配送 郎茂祥路径优化问题数学模型的基础上，构造了求解物流配送路径优 化问题的遗传算法 郎茂祥提出用混合遗传算法求解v r p 问题 胡思继 李军对车辆路径问题进行了比较系统的研究，从车型、车场、载重 郭耀煌情况的不同组合出发，提出了多种求解算法 将t a b us e a r c h 搜索算法应用到物流系统的配送路线优化( v r p ) 问题中。详细介绍了算法的设计过程：先用g e n i u s 算法构造 袁庆达 v r p 问题初始解，之后用t s 算法优化初始解。通过数值模拟， 验证了算法的可行性 提出了在考虑时间窗情况下用c - - w 节约法来解决非满载运输 李金苹 问题的算法，并用某超市8 项送货任务对算法进行了验证说明 罗上远根据零售业的实际情况，提出一个配送中心多个零售点的库存 徐天亮分布模型，并提出了一种改进分区配送算法 通过引入新颖交叉算子，构造了一种改进遗传算法。该算法摆 张丽萍脱了对群体多样性的要求，不存在传统遗传算法常见的“早熟 收敛”问题，可用于解决v r p 问题 周贤伟根据车辆装载g p s 设备的特性，建立了货物运输的数学模型， 李光远并设计了求解的遗传算法 将货运量约束和时间窗约束转化为目标约束，设计了基于自然 谢秉磊数编码的可同时处理软、硬时间窗约束的遗传算法，实验分析 获得了较好的结果 通过将地理信息系统与基于遗传算法的优化决策相结合，建立 陈艳艳 了一个综合优化决策模型，利用地理信息系统计算与位置相关 的成本，并实现数据的连续传递，将结果输出到外部程序，进 宋健民 而利用遗传算法进行优化决策，使总成本最小。实例表明该方 法可以大大减轻劳动强度，是实现决策自动化的有力工具 姜大立分别用遗传算法求解了无时限和有时限的物流配送车辆调度问 李大卫题 蔡延光应用并行禁忌搜索算法和模拟退火算法对满载问题进行了求解 刘浩 用模拟退火算法求解了两车型随机需求的v r p 马良 介绍了蚂蚁算法与遗传算法相结合来求解t s p 问题 袁健 用神经网络法求解了v r p 国内的一些研究者也从实用开发角度出发对v r p 进行了研究，其中李军、张 红历提出了以g i s 为平台通过集成v r p 算法开发车辆路径系统的设计思想。目前 1 7 已经投放市场的路径软件有：武汉测绘科技大学奥发公司的“商业送配货地理信 息系统”和北大方正的“路径规划系统”。而对于能大大提高车辆利用率的干线运 输调度问题，针对性的研究较少，因此，从我国干线运输的真实环境和现状出发， 探索和开发适合我国干线运输的车辆调度软件，具有明显的现实意义。 1 4 课题研究的主要内容 论文首先回顾了车辆调度问题的研究成果，系统地分析了干线运输车辆调度 问题；其次建立了一套较完整的数学模型，设计了一种改进的遗传算法，并对该 算法进行计算机数值仿真实验，对实验结果进行分析和评价；最后提出了动态车 辆调度信息系统的整体设计方案。 主要研究内容： 第一章：阐述了干线运输车辆调度的研究背景、研究意义、研究现状及本论 文的主要研究内容。 第二章：系统分析干线运输车辆调度问题的基本情况，包括干线运输车辆调 度的构成要素、分类、调度方式及问题研究的难点。 第三章：对目前解决车辆调度问题的算法进行了系统的总结，重点论述了遗 传算法的特点及实现方法。 第四章：提出了干线运输车辆调度问题的数学模型，并应用遗传算法对其进 行求解，通过实例对求解过程和结果进行分析和评价。 第五章：设计了一套车辆调度信息系统，按照车辆调度系统设计的总体原则， 对系统运行环境、功能模块进行了总体设计和计算机实现。 第六章：对论文的主要工作进行总结，指出论文的不足之处，对下一步工作 进行展望。 1 8 第二章干线运输车辆调度问题基本情况概述 2 1 干线运输基本情况 2 1 i 干线运输 1 9 9 3 年，我国在国道网基础上，提出了国道主干线系统。其技术标准是以汽 车专用公路为主的高等级公路，是指按照国家规定的二级以上公路修建标准建设， 设有分隔双向行驶车道、防护隔栏和道路诱导标志、全立交，专供汽车高速行驶 的公路。它包括高速公路、一级公路和二级汽车专用公路。这个主干线系统是全 国综合运输大通道的组成部分，拥有比较完善的安全保障、通信和综合管理服务 体系。国道主干线连接了首都北京与各省会和所有1 0 0 万以上人口的特大城市及 5 0 万以上人口的绝大部分城市。根据交通部总体规划，到2 0 2 0 年，将建成总长 度为3 5 万公里的“五纵七横”国道主干线系统，形成贯通首都、直辖市、各省 省会，连接全国主要城市的运输大通道。届时，高速公路将达到7 5 0 0 0 公里，一， 二级汽车专用公路5 5 0 0 0 公里，纵横交错的高等级公路网，将为快速运输提供可 靠的保障【刀。 干线运输以高等级公路为基础，以货物运输市场为条件，充分发挥汽车运输 灵活、机动、门到门的优势，使有形的运输对象一一货物得到高效、快捷的位移。 高等级公路是构筑干线运输市场的必要前提，高等级公路的使用价值在运输生产 过程中得到体现嘲。 2 1 2 干线运输运营模式 干线运输的运营模式可以用图2 一l 来表示： 图2 - i 干线运输运营模式 从图2 1 中可以看出，其运营模式是可逆的。 2 1 3 干线运输的发展趋势 发展干线运输，一是要保持运量与运力的平衡关系，二是要提高运输市场的 组织与管理水平。因此，必须从这两个方面采取对策【3 只埘。 1 、促进干线运输业规模化发展，提高运输市场集中度 交通运输行业管理部门和地方政府，要加强对运输业的宏观调控，完善运输 市场准入制度，强化货运企业资质管理；要适度限制个体运输车辆的发展，对现 有个体运输车辆要强化集约化管理；扶持和促进国有大型运输企业通过合作、协 同、重组、兼并、入股等方式整合社会运力资源，扩大企业规模，提高运输市场 集中度，形成规模化经营管理和指挥能力。企业规模扩大后才能形成市场控制能 力，遏制市场无序竞争，建立货源与运力资源共享的物流体系，合理统筹发展和 配置运力资源，科学规划运输线路，实现合理配载，最大限度的提高车辆利用效 率。 2 、采用现代化信息技术，建立现代化物流运输信息系统 全面推广现代化信息技术，是现代物流运输的主要特征和发展方向，也是科 学组织和管理物流运输市场、提高运输车辆利用效率的重要技术手段。各地方政 府、各地物流管理部门，应以物流基础设施建设为基础，积极建立社会物流信息 平台，物流企业、配载中心、汽车运输企业等都应积极参与构建和使用物流信息 系统，实现信息共享、数据交换，实现货物预约和车辆配载，提高车辆的送达速 度和运输效率。 3 、大力发展大吨位、专用化车辆 由于干线运输要求的运行条件高，必须依托高等级公路，以大型车辆进行长 远距离运输、以专用车辆进行特殊货物的运输。未来我国运输车辆将围绕提高运 输效率、降低能耗、确保运输安全三大目标发展，普通敞棚货车将逐渐淘汰，“裸 露”运输将成为历史，散挂汽车列车运输技术和集装箱拖挂等集装单元在货物运 输领域的运用将得到大力推广，形成专业化运输，扩大服务范围，从而提高汽车 的利用效率。 4 、整合运输资源，统一调度专用车辆 对于一些特种商品的运输，因其运输车辆结构的特殊性、货源市场的集中性 和单一性，使其运输回程配载困难。应该发挥行业主管部门或行业协会的作用， 2 0 整合运输资源，建立货源与运力资源共享的物流体系，合理统筹发展和配置运力 资源，科学规划运输线路，在全行业内实现合理配载。最大限度的提高车辆利用 效率。 2 2 干线运输车辆调度问题 2 2 1 干线运输车辆调度问题的描述 干线运输车辆调度问题可以描述为：在庞大的存在供求关系的运输网络中， 有若干台已知分布状况的车辆，要求合理安排车辆的行车路线和出行时间，从而 在给定的约束条件下，最大限度地满足在不同时段不同地域上所产生的运输任务 要求，以达到以最少的资源投入获得最优经济效益的目的。 2 2 2 干线运输车辆调度问题的构成要素 干线运输车辆调度问题主要包括货物、车辆、运输网络、约束条件和目标函 数等要素 1 i j 2 j 。 l 、货物 货物是运输的对象。可将每次要运输的货物看成一批货物，每批货物都包括 品名、包装、重量、体积、要求送达的时间和地点等属性。 货物的品名和包装，是选用运输车辆的类型以及决定该批货物能否与其它货 物装在同一车辆内的依据。例如：一些货物因性质特殊需要使用专用车辆装运， 一些货物因性质特殊不能与其它货物装在同一车辆内，一些货物虽然性质特殊， 但由于包装条件很好，故也能与其它货物装在同一车辆内。 货物的重量和体积是进行车辆装载决策的依据。当货物的重量或体积超过运 输车辆的最大装载重量或容积时，则该任务将需要多台车辆进行运输。 货物的送达时间和地点是制定车辆的出行时间和路线的依据。 2 、车辆 车辆是货物的运载工具。其主要属性包括：车辆的类型、装载量、一次运输 的最大行驶距离、执行任务前的停放位置及完成任务后的停放位置等。 车辆的类型有通用车辆和专用车辆之分，通用车辆适于装运大多数普通货物， 专用车辆适于装运一些性质特殊的货物。 车辆的装载量是指车辆的最大装载重量和最大装载容积，是进行车辆装载决 策的依据。在干线运输系统中，车辆的装载量可以相同，也可以不同。 2 l 车辆在执行任务前的停放位置是运输网络中的某个节点。车辆完成运输任务 后，或者在该网络节点等待调度，或者有目的的行驶到另一网络节点处。 3 、运输网络 运输网络是由运输网络节点、有向运输路径组成。运输网络节点也称为物流 基地、物流据点，是指进行集货、分货、配货、配装、送货作业的物流中心、仓 库、车站等。其主要功能是承揽当地货源，负责业务受理、货物集散、分拣、装 卸等作业，进行本辖区内的短途取送货服务，并负责对发货人的运费结算。因此， 根据业务量的需要，拥有不同规模的、网络化的物流基地是干线运输成功运营的 必要条件。 4 、约束条件 干线运输车辆调度问题应满足的约束条件主要包括： ( 1 ) 满足货物送达时间范围的要求。 ( 2 ) 在允许运输的时间进行运输。 ( 3 ) 车辆在运输过程中的实际载货量不得超过车辆的最大允许装载量。 ( 4 ) 车辆每天的行驶距离不能超过最大行驶距离。 5 、目标函数 对干线运输车