（车辆工程专业论文）基于网络的邮政运输车辆调度问题研究.pdf

西华大学硕士学位论文 基于网络的邮政运输车辆调度问题研究 车辆工程专业 。摘要 邮政运输是国家邮政事业的中心环节，关系到国民经济的发展及人民生活 的便利程度，它不仅是邮政企业赖以传递邮件实现实物空间转移的物质基础， 还是决定邮政企业竞争能力和服务质量的主要因素。然而，邮政运输是否得以 顺利快速实现这就要取决车辆调度的合理化程度。因此优化车辆调度成为邮政 企业提高运行效益、保持竞争实力的有效途径。 本文以省一级邮政汽车运输企业为背景，从邮政运输系统的约束条件、优 化目标、车辆、时限、运输成本等因素出发，对邮政运输问题进行了系统分析， 提出了解决该问题车辆调度数学模型。由于模拟退火算法局部寻优的能力以及 遗传算法固有的缺陷，二者的结合正好实现了优势互补，从而设计了模拟退火 混合遗传算法对该问题进行求解。为了评估算法性能，我们在v i s u a lc + + 6 0 环境下进行编程实验，试验结果表明，利用模拟退火混合遗传算法进行车辆优 化调度问题求解，能够方便有效的求得近似最优解，此算法可以应用于邮政车 辆调度问题的研究。 最后，针对邮政汽车运输企业面临的市场竞争和发展前景以及计算机实现 车辆自动调度的趋势，本文提出开发邮政运输车辆调度管理系统的设想，进行 系统的可行性分析和对数据的完整性分析，为开发此系统提供了理论依据。该 系统的完成将大大提高邮政企业的服务水平，降低运营成本，提高邮政企业的 客户满意度。 关键词：邮政运输，车辆调度问题，模拟退火算法，遗传算法，邮运车辆调度系统 西华大学硕士学位论文 s t u d y o np o s t a lt 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 p r o b l e mb a s eo nt h en e t w o r k v e h i c l ee n g i n e e r i n g g r a d u a t es t u d e n t l ij i e a b s t r a e t p o s t a lt r a n s p o r t a t i o n , t h ec e n t r eo ft h en a t i o np o s t a le n t e r p r i s e ，r e l a t et h e d e v e l o p m e n to fc o u n t r ye c o n o m i c a la n dt h ec o n v e n i e n to fp e o p l e sl i f e w h i c hi s n o to n l yas u b s t a n c eb a s ei nt h ew h o l ep r o c e s so f p o s t a lo p e r a t i o n ，b u ta l s ot h em a i l f a c t o ri nm e a s u r i n gt h ec o m p e t i t i o na b i l i t ya n ds e r v i c eq u a l i t yo fap o s t a le n t e r p r i s e h o w e v e r , t h er a t i o n a l i z a t i o no fv e h i c l e ss c h e d u l i n gd e c i d e dt h ep o s t a ls e r v i c e t r a n s p o r t sb e t t e r t h u st h eo p t i m i z a t i o no fc u r r e n tv e h i c l es c h e d u l i n gi sa ne f f e c t i v e w a yf o rt h ee n t e r p r i s et oe n h a n c et h eo p e r a t i o n a le f f e c t i v e n e s sa n dt or e i n f o r c et h e c o m p e t i t i o na b i l i t y t h i sp a p e rt a k et h ep r o v i n c ef i r s t - l e v e lp o s t a lv e h i c l et r a n s p o r te n t e r p r i s ea sa b a c k g r o u n d ，w em a k eas y s t e ma n a l y s i sf o rt h ep o s t a lt r a n s p o r t a t i o np r o b l e mf r o m t h ep o s t a lt r a n s p o r t a t i o ns y s t e m sc o n s t r a i n t s ，o p t i m i z e dg o a l ，v e h i c l e s ，t i m el i m i t , t r a n s p o r t a t i o nc o s ta n ds oo n a c c o r d i n gt os a h a v et h el o c a ls e a r c h i n go p t i m i z a t i o n a b i l i t ya n dt h ed i s f i g u r e m e n to fg a , t h eu n i o no ft h et w oa l g o r i t h m sc o u l dr e a l i z et h e p r e d o m i n a n c e s ow ed e s i g na na r i t h m e t i cn a m e ds i m u l a t ea n n e a l i n gh y b r i d g e n e t i ca l g o r i t h m st os o l v et h i s p r o b l e m f o re v a l u a t et h ep e r f o r m a n c eo ft h i s a r i t h m e t i c ，w eh a v eap r o g r a me x p e r i m e n ti nv i s u a lc + + 6 0 t h er e s u l ti n d i c a t e d t h i sa r i t h m e t i cc o u l ds o l v et h ev e h i c l es c h e d u l i n gp r o b l e me f f e c t i v e l ya n dg e tt h e a p p r o x i m a t eo p t i m a ls o l u t i o n s ot h i sh y b r i da l g o r i t h mc o u l db ea p p l i e di nt h ep o s t a l v s p 西华大学硕士学位论文 a tl a s t , r i ma tt h ec o m p e t i t i o na n dd e v e l o p m e n ti nt h ep o s t a lt r a n s p o r t a t i o n e n t e r p r i s e ，a n dt h et r e n do ft h ea u t o m a t i cv e h i c l es c h e d u l i n gw i t hc o m p u t e r w e m a k eap l a nt o e x p l o r eap o s t a lt 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 gm a n a g e m e n t s y s t e m ，a n a l y z i n gt h ed a t a si n t e g r a l i t ya n dr e a l i z e dt h es y s t e ms i m p l y p e r f e c tt h i s s y s t e m ，i tc o u l db ei m p r o v et h es e r v i c el e v e lo ft h ep o s t a le n t e r p r i s e ，r e d u c et h e o p c r a t ec o s ta n di n c r e a s et h ec l i e n ts a t i s f a c t i o n k e y w o r d s ：p o s t a l t 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 ，s i m u l a t e d a n n e a l i n g ，g e n e t i ca l g o r i t h m s ，p o s t a lt r a n s p o r tv e h i c l es c h e d u l i n g s y s t e m i i i 西华大学硕士学位论文 学位论文原创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成果归 西华大学所有，特此声明。 学位论文作者签名： 导师签名： 杏 泐矿 月2 7 re t r 月2 ，孑日 ， 西华大学硕士学位论文 西华大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅，西华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书： 2 、不保密适用本授权书。 ( 请在以上口内划) 学位论文作者签名：专走 日期：口9 j 2 7 指导教师签名：砌 日期： 6 售5 鼍 西华大学硕士学位论文 1 绪论 随着中国改革进程的不断深入，经济建设的不断发展，各种形式的快递和 物流企业的相继出现，邮政在实物传递领域的垄断地位已经被打破。邮政想要 在众多物流行业中立于不败之地必须在各方面进行优化，在邮政运输中存在着 许多优化决策问题，车辆调度问题( v e h i c l es c h e d u l i n gp r o b l e m ，v s p ) 是其中 的一个核心问题和关键问题【1 1 。本文研究的就是关于邮政运输的车辆调度问题。 1 1 本文研究的背景 中国邮政是目前全国最大的实物传递网之一，它涵盖了物品的收取、包装、 分拣、运输、直至送到最终用户的手里的全过程，从邮政的组织过程来看，一 般分为收揽、分拣、运输、投递四大环节。每年运输的邮件量数以亿计，运输 网络遍布全国城乡各地。由于中国邮政是个百年老企业，点多面广、摊子大、 人员多，客观地说，存在着效率不高、反应较慢、成本较高等缺点。当前随着 邮政体制改革的深化，整个运输网络也在不断的优化和调整。 邮政运输网络是邮政企业运营的重要保障，是决定邮政企业竞争能力的主 要因素。随着中国改革进程的不断深入，经济建设的不断发展，社会经济的竞 争性越来越强。特别是中国经济的对外开放程度的加强，原来邮政在实物传递 领域的垄断地位已经打破，各种形式的快递和物流企业、尤其是近年来进入中 国的t n t 、u p s 、联邦快递以及国内的中铁快运等企业对邮政企业造成巨大的 竞争压力。由于集成化物流的理念的进一步的推广，物流系统比以往任何时候 都要复杂，技术的应用和管理具有很强的系统性，在缩短邮件运输时限和降低 成本的同时，如何降低各个环节企业的物流成本，提高邮政行业服务质量和信 誉，最大限度地满足客户需求，保持邮政行业的竞争能力和取得良好的社会效 益，具有积极而现实的意义。邮政通信生产的运输环节是实现邮政通信生产整 体效能最关键的一环，而车辆调度问题是邮政运输的一个最核心问题。因此， 解决运输成本的合理化，集中体现在运输过程的合理组织与安排上，通过路径 的优化来体现这种对降低运输成本具有重要作用的管理工作与具体物流活动的 西华大学硕士学位论文 运作，是安排合理运输、解决运输与配送问题的重要手段，也是实现物流管理 科学化和合理化的重要途径【2 】。 关于智能调度的一系列研究我国起步较晚。车辆调度状况一般是由有经验 的调度人员编制计划，按照预定计划执行调度，对临时事故或高峰期邮件则根 据经验拟定方案，通过电话交流，联系有关调度环节，确定车辆调度方案。这 种现状存在以下问题： 1 、服务水平，质量较低。信息流与物流的矛盾会导致整个邮政系统客户服 务水平低效； 2 、计划编制劳动强度太大，且难以保证方案较优，控制物流成本困难； 3 、影响道路交通状况； 4 、不利于邮政运输部门提高效益，不适应邮政行业未来经营的需要。 车辆调度问题是整个邮政运输过程中涉及资源调配、费用节约的重要步骤， 在整个邮政运输过程中占有重要的地位。因此，邮政运输车辆调度问题的研究 与应用，能有效的减少车辆的空驶率，实现合理路径运输，从而有效的减少运 输总成本，节约运输时间，提高运输经济效益，进而达到提高邮政运输部门的 整体效益、增强邮政企业在市场上的竞争力的目的。 本文研究内容是本人参加导师主持的以下科研的总结： 1 、r 0 7 2 0 3 0 5 ，汽车运输组织优化与信息支持系统 2 、2 7 2 0 31 6 3 ，邮政汽车运输信息管理系统( p t m i s ) 升级 1 2 国内外研究现状 1 2 1 国外研究现状 车辆调度( v e h i c l es c h e d u l i n gp r o b l e m ，v s p ) 问题最早是由d a n t z i g 和 r a l t i s e r 于1 9 5 9 年首次提出的【3 】，很快引起运筹学、应用数学、组合数学、图 论与网络分析、物流科学、计算机应用等学科专家与运输计划制定者和管理者 的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科的专 家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。其求解方 法大体上归结为优化算法和启发式算法，其中由于优化算法对于解决v s p 问题 的局限性，实际中一般采用启发式算法，如g i l l e t t 和m i l l e r 提出的扫描法和 2 西华大学硕士学位论文 c l a r k - w r i g h t 的“节约 算法【4 】，己经在邮件运输中得到广泛的应用。 国外对v s p 问题作了大量而深入的研究。早在1 9 6 2 年，b a l i n s l 【i 【5 j 等人首 先提出了v s p 的集分割，直接考虑可行解集合，在此基础上进行优化，建立了 最简单的v s p 模型。1 9 8 3 年，b o d i n 、g o l d e r 【6 l 等人针对一般的车辆调度问题 做了较为详细的论述，在他们的综述文章中就列举了7 0 0 余篇文献。在 c h r i s t o f i d e s ( 1 9 8 5 ) 【”，g o l d e n 和a s s a d ( 1 9 8 8 ) 【4 】编辑的论文集中，以及a l t i n k e m e r 和g a v i s h ( 1 9 9 1 ) 【8 】，l a p o r t e ( 1 9 9 2 ) 1 9 ，s a l h i ( 1 9 9 3 ) 【l o 】等发表的综述文章 中都对这一问题做了详尽的阐述。 半个世纪以来，科学家们对车辆调度模型的算法研究一直很重视。总的来 讲，求解车辆调度问题的算法主要分为精确算法和启发式算法【1 1 1 。对于精确算 法，d e s r o e h e r s t l 2 1 ，k o h la n dm a d s e n 1 3 1 ，f i s h e r t l 4 】等人做过有关的研究，其中 又可以分为分支界定法、割平面法、网络流算法、动态规划法等。精确算法可 以求得模型的精确解，但是，它只能解决规模比较小的问题，即配送车辆数和 客户数都比较少的问题。并且，在求解的过程中所需要较长的运行时间。由于 这两方面的限制，精确算法难以真正应用，对此的研究也越来越少。车辆调度 的启发式算法最早是由c l a r k e 和w r i g h t 提出的节约法【1 5 1 ，g i l l e t t 和m i l l e r 提 出的扫描法【1 6 1 ，b r a m e l 和s i m c l l i n 、，i 的提出的基于选址问题转化的l b h t l 7 j 法【1 7 1 ，f i s h e r 和j a i k u m a r 建立的一般分配算法 1 8 】，c h r i s t o f i d e s 和m i n g g o z z i 等 建立的不完全树搜索算法【1 9 1 ，p u r e z a 和f r a n e a 研究的t a b u 搜索算法【2 0 】等等。 另外，p o t v i na n dr o u s s e a u 2 1 1 ，r u s s e l l 2 2 等人提出了启发式算法有构造启发式 算法，p o t v i na n dr o u s s e a u 2 3 1 ，s o l o m o n l 2 4 1 等得出了改进启发式算法，以及后 来又出现了把两者结合起来的综合启发式算法。构造算法又分为节约算法( c w 算法) 、最邻近法、几何启发式算法、最小生成树算法、最近插入算法、最节 约插入算法、凸集插入算法和非对称距离的t s p 构造法。这些算法为求解车辆 调度问题提供了有效的方法，但也存在一系列问题，如节约法虽然通过列出各 点对间的节约量，按节约量从大至t j d , 构造路径，具有运算速度快的优点，但 存在未组合点零乱、边缘点难于组合的问题：扫描法为非渐进优化1 2 5 1 ；l b h 法 则存在问题转化麻烦且选址问题本身难解等等。 现在，车辆调度问题的形式已有很大发展，该问题己不仅仅局限于公路交 3 西华大学硕士学位论文 通运输领域，在水运、航空、通讯、电力、工业管理、计算机应用等领域也有 一定的应用，其算法己用于航空乘务员轮班安排、轮船公司运送货物经过港口 与货物安排的优化设计、连锁商店的配送、生产系统中的计划与控制等多种组 合优化问题，并且取得了很大的经济效益。 1 2 2 国内研究现状 与国际上相比，国内对v s p 的研究相对较少，最近几年才陆续有一些相关 的研究成果发表。我国对车辆路径问题的研究是在2 0 世纪9 0 年代以后才逐渐 兴起，比国外滞后3 0 余年，处于起步阶段，无论是从深度还是广度来说，远远 不能满足我国社会主义市场经济迅速发展的需要，也不能满足我国物流业迅速 发展的需要。总的来说，对通用性强、精度高、速度快的调度指挥算法还有待 进一步研究发展。 目前，国内对于复杂的车辆调度问题的研究已有了一定的进步。郭耀煌、 李军等用传统启发式算法解决了一些相对简单的v s p 问题，如送货点比较少的 容量约束、时间窗约束v s p ；马卫民【2 6 】在其博士论文中用在线和竞争策略研究 了带时间窗的、开放式v r p t w 。冯萍叨在其硕士论文中用插入法、遗传算法、 模拟退火算法研究了带软时间窗的车辆路径问题( v i 冲s 刑) 。蔡延光用遗传 算法、模拟退火算法等【2 8 - 3 0 】研究重载v s p ，取得了一定的成绩。张涛等通过遗 传算法来保证搜索的全局性，用3 - o p t 算法来加强局部搜索能力，得到针对 v s p 的混合算法1 3 u ；文献 3 2 1 就普遍意义上的车辆优化调度i 口- j 题的研究现状进 行了评述，文献 3 3 1 和 3 4 1 分别就多车型货运车辆优化调度和满载问题的车辆路 线安排进行了深入的研究，特别是后者对满载运输的问题解的特征进行了分析， 在此基础上提出了一个根据运输问题最优解或满足解安排行车路线的方法，该 方法是一种实用性很强的交互式优化方法，把复杂的调度问题的多个目标置于 求解的不同过程，通过交互式方法得以实现并进行了验证。有时间窗的车辆调 度问题是一个典型的n p 难题，传统求解方法往往不能令人满意，对于这个问 题，文献 3 5 提出了以分派为基础的启发式算法，并且讨论了如何完成任务所 需要的车辆数，定义了两种分派费用，设计了在分派过程中安排线路的方法。 文献【3 6 】进一步提出了以网络优化为基础的启发式算法，算法中引入重载点， 4 西华大学硕士学位论文 把求解有时间窗的调度问题转化为求解多个有确定开始时间的车辆调度问题， 利用最小费用最大流算法求解有确定开始时间的车辆调度问题，再根据检验数 来调整开始时间值。文献 3 7 】将货运量约束和时间窗约束转化为目标约束，设 计了基于自然数编码的可同时处理软、硬时间窗约束的遗传算法，实验分析获 得了较好的结果。文献【3 8 】在分析车辆调度问题特征的基础上，应用运输问题 伏格尔法的思想，设计了求车辆初始分派的表上作业法，在分派过程中处理车 辆容量约束，并应用闭回路法或位势法对分派进行优化，算法中车辆数目可动 态调整【3 9 】。 尽管国内学者在v s p 的研究方面已经有了一定的成果，但总体来说还是处 在起步阶段。就收集到的资料来看，主要表现在以下几个方面：( 1 ) 所研究的 问题类型都是确定性问题；( 2 ) 研究问题的手段比较单一，特别是智能算法， 很少人对各种算法应用于v s p 的性能进行综合研究。( 3 ) 对该领域的专有名 词没有统一规范的提法( 如对v s p 的提法，有车辆路径问题、车辆路线问题、 车辆路线安排问题、路由问题、车辆调度问题、多重运输调度问题) ；( 4 ) 该 领域的研究者群体小，仅有西南交通大学、清华大学、浙江大学、西安交通大 学、北京交通大学、，东北大学、南京航空航天大学等少数高校的科研工作者在 从事这方面的研究工作。因此，就这方面研究的深度和广度来说，远远不能适 应我国配送业以及物流业迅速发展的需要。 1 3 本文主要研究内容和意义 本论文主要以成都邮区中心局为背景，在借鉴国内外己有的研究成果的基 础上，主要的研究工作是通过与生产实际相结合、从邮政物流企业提供智能化 决策支持的目标出发，专门针对邮政运输系统的车辆调度问题，建立数学模型。 同时，利用遗传算法，用自然序列编码方式以及交叉算子，构建一个车辆调度 问题的遗传算法解决方案，并且在确保运输时限的前提下，以最少的运输费用 支出和最快的传递时限，准确、安全地处理和运输货物，实现时限与成本的最 优化匹配，真正实现汽车运输信息化、智能化。 本文的结构安排如下： 第一章主要提出课题的来源，介绍了课题的背景及其意义，并分析了该问 5 西华大学硕士学位论文 题的研究现状。 第二章邮政车辆调度问题基本描述。简要介绍了邮政车辆调度问题的定义、 分类、目标、特征以及邮政运输企业评价指标。 第三章详细介绍了遗传算法。论述了遗传算法的基本思想、算法模型、算 法特点，以及算法的应用领域，最后对算法的原理进行了详细的分析。 第四章介绍了经典v s p 问题的定义及其数学模型，运用基本遗传算法对该 问题进行求解。 第五章邮政车辆调度模型及模拟退火混合遗传算法研究。首先提出车辆调 度问题，然后根据约束条件和目标，建立邮政v s p 调度数学模型，根据所研究 问题的特点，应用模拟退火混合遗传算法进行求解。 第六章邮政车辆调度系统设计与分析。本论文根据前面几章的理论研究提 出了邮政车辆调度系统规划与设计的构想，这里对这一系统进行简单的介绍。 第七章对本文进行了小结，总结了论文的主要工作以及有待改进之处，并 对进一步的研究工作进行了展望。 邮政运输车辆调度问题的研究与应用，将使管理人员从繁忙的手工操作中 解脱出来，并迅速地从本系统中获得预知的邮运生产信息，以利于及时地正确 地做出决策，保证邮政车辆调度的优良运行。 6 西华大学硕士学位论文 2 邮运车辆调度问题基本描述 邮政企业是兼有国家公益性质的特殊企业，邮政运输部门的主要任务是协 同其它部f - j ( 如分拣封发、营业窗口和其它各地运输部门) 及时准确地将邮件 运送到指定的地点，在此前提下尽量考虑降低生产成本。因而，经济性不是邮 运企业的唯一目的，对邮政车辆调度问题的研究的最终目的是保证车辆、设备 始终处于最佳状态、人员处于最优配置，做到有车可用、成本最低，使邮运生 产的时限、运量、可靠性达到要求。 2 1 车辆调度问题的提出及分类 车辆优化调度问题是一类重要的组合优化问题。一般可定义为：对于一系 列装货点和( 或) 卸货点，组织合适的行车线路，使载货车辆有序地通过它们， 在满足一定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、 行驶里程限制、时间限制等) 下，达到一定的目标( 如路程最短，费用最少、时 间尽量少、使用车辆数量尽量少等) 【加】。 由于运输任务的性质和特点不同，道路条件及车辆类型不同，即使在相同 收发货点间完成同样任务时，采用的行驶路线方案也可能不同。而车辆按不同 运行线路完成同样的运输工作时，其利用效果是不一样的，有时甚至会有很大 的差别。因此，在满足货运任务要求的前提下，如何选择最经济的运行路线， 是一项重要的工作。所谓最经济的运行路线，就是在保证货物需求的前提下， 运输时间或运输费用最省的路线。如何按时按量、经济高效地配送商品，在很 大程度上取决于有效的车辆调度安排，调度方案的优化与否，对提高配送效率、 减少物流费用和提高服务水平具有重要的意义。 车辆优化调度问题提出后，l i n u s ( 1 9 8 1 ) 【4 1 1 ，b o d i n 和g o l d e n ( 1 9 8 1 ) 【4 2 】 b o d i n ( 1 9 8 3 ) ，a s s a d ( 1 9 8 8 ) ，d e s r o e h e r s 、l e n s r t a 和s a v e l s b e r g h ( 1 9 9 0 ) 者从不同角度，按不同的标准分为以下五种类型【4 0 】： ( 1 ) 单车型和多车型 按车辆类型数分，有单车型和多车型。单车型问题即所有配送车辆的容量 7 西华大学硕士学位论文 相同，多车型问题即配送车辆的容量不完全相同。 ( 2 ) 单车场和多车场 按照车场( 或货场、配送中心等) 的数目可以分为单车场和多车场的配送 车辆路线优化问题。单车场问题即只存在一个车场，所有的车辆都从一个车场 发出，按照路线巡回所有需求点后，返回同一车场。 多车场问题是相对单车场问题提出的。即有多个车场，并且在每个车场都 拥有一定数目的车辆，允许车辆从任何其中的一个车场出发，完成任务后，返 回所属车场。 ( 3 ) 满载型问题和非满载型 按车辆载货状况分：有满载问题( 货运量多于一辆车的容量，完成所有任 务需要多辆运输车辆) 和非满载问题( 货运量小于车辆容量，一辆车即可满足 货运要求) 。 当每个客户需求货物量小于车辆容量时，用一辆车执行一项任务就存在不 满载运行情况，调度时可安排一辆车执行多项任务，即在一辆车上装载不同货 主的货物。这类问题称为非满载v s p ，当然，这类问题有一个前提条件，即不 同货的货物允许混装。当每个客户需求货物量大于车辆容量时，用一辆车执行 一项任务就不能满足客户的需求，此时需要一辆以上的车对其进行送货，车辆 能够满载该问题称为满载v s p 。 ( 4 ) 有时间窗约束和无时间窗约束 按照到达需求点的时间有无时效约束可分为有时间窗约束和无时间窗约束 的配送车辆路线优化问题。 若到达和离开时间没有规定，即无时间窗约束情况下，配送车辆路线问题 就是一个直接的车辆路线安排问题。有时间窗约束的车辆调度问题又可分为硬 时间窗v s p 和软时间窗v s p 。硬时间窗( h a r dt i m ew i n d o w s ) 指配送车辆必 须在特定时间区段将货物送达需求点手中，无论是迟到和早到都完全不能接， 其惩罚值等于一个非常大的正值表示硬时间窗的限制。软时间窗( s o f tt i m e w i n d o w s ) 指配送车辆如果无法将货物在特定的时间段送到需求点手中，将按 照违反时间的长短进行惩罚。 ( 5 ) 纯装或纯卸和装卸混合问题 8 西华大学硕士学位论文 按任务特征分，可分为纯装问题或纯卸问题( p u r ep i c ku p0 1 p u r ed e l i v e r y ) 和装卸混合问题( c o m b i n e dp i c ku pa n dd e l i v e r y ) 。 若所有任务全是装货点或全是送货点，车辆空车( 或满车) 从配送中心出 发，去各需求点装满( 或卸载) 货品后返回配送中心，这种情况为纯装或纯卸 问题。 若每一项配送任务都有自己的装货点和卸货点，车辆从配送中心出发，去 某一项任务的集货地点装货后运至送货地点卸货( 即集货、送货一体化问题) ， 完成任务后返回配送中心，这种情况下为装卸混合问题。 2 2 车辆调度问题的优化目标 车辆调度是否合理对配送速度、成本、企业效益的影响很大，如何有效、 合理的对车辆调度问题进行优化，就成为了非常现实的问题。在进行车辆调度 优化时，必须遵循基本原则，有明确的目标。可以只选用一个目标，也可以选 用多个目标。经常选用的目标函数主要有： ( 1 ) 总里程最短。配送里程与配送车辆的耗油量、磨损程度以及司机疲劳 程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响。 由于配送里程计算简便，它是确定配送路线时用得最多的指标。但运输成本不 能通过里程来反映时，如道路收费、道路运行条件严重的影响成本，就不能单 以最短路程作为目标。 ( 2 ) 总成本最低。物流企业要达到盈利的目的，必须优化配送方案，合理安 排物流配送使得总成本最低，包括固定成本和变动成本、减少固定成本主要是使 车辆指派数目最小，减少变动成本主要是使油费、路程中的机会成本最小。 ( 3 ) 准点率最高。由于客户对交货时间有较严格的要求，为提高配送服务 质量，有时需要将准时性最高作为确定配送路线的目标。 ( 4 ) 运力利用最合理。在运力非常紧张、运力与成本或效益有一定相关的 情况下，要求使用的较少的车辆完成配送任务，并使车辆的满载率最高，以充 分利用车辆的装载能力。 以上四个目标既具有独立性，又具有复杂的内部关系。因此，本文在建立 v s p 模型时，以总成本最低为目标，运力利用最合理，考虑客户间配送的网络 9 西华大学硕士学位论文 化，来确定车辆的数目和车辆配送路径。 2 3 车辆调度算法理论 车辆优化调度问题是组合优化领域中的典型的n p 难问题其求解方法非常 复杂，目前应用于车辆调度优化的算法主要有以下几种： 1 、人机互动法 此方法结合人类决策与计算机能力，在求解的过程中，通过高度的人机交 互模式，结合专家的决策信息，并据以计算出结果。优点是寻优的过程中，决 策者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致的 成本变化。 2 、系统仿真法 此方法是由g o l d e n 和s l 【i s c i m 【4 3 】在19 8 6 年提出的，主要应用于行车路线 与配送中心区位的选择，优点在于可直接观察系统安排的效率和效果，但由于 问题的实际情况多变且具有不确定性，很难将要实现的配送情形系统逻辑化为 仿真程序。 3 、精确解法 精确式算法一般应用于线性规划( 包括经过了专门处理的分枝定界法、割 平面法和标号法) 和非线性规划等数学规划技术，以便求得问题的最优解。在 v s p 问题研究的早期，主要是单源点( o n e p o i n t ) ( 即配送中心、车场等) 派 车，研究如何用最短路线( 或最短时间内) 对一定数量的需求点( 即用户) 进 行车辆调度，因此主要运用精确算法，求出问题的最优解。精确式算法一般有 以下几种方法：分枝定界法( b r a n c ha n db o u n da p p r o a c h ) 、割平面法( c u t t i n g p l a n e sa p p r o a c h ) 、网络流算法( n e t w o r kf l o wa p p r o a c h ) 和动态规划方法 ( d y n a m i cp r o g r a m m i n ga p p r o a c h ) 等。精确算法随着运输系统的复杂和调度 目标的增加，其计算量呈指数递增，使得获取整个系统的精确最优解越来越困 难，而用计算机求解大型优化问题的时间和费用又太大，因此，此类优化方法 和算法现在一般仅用于求解运输调度的局部优化问题。 。 精确解法将车辆配送问题，通过严谨的数学模型或计算机数据结构规划， 利用数学法则或数据结构搜寻方式，求得问题的解。由于两种方法都在所有可 1 0 西华大学硕士学位论文 行解集合( f e a s i b l es o l u t i o ns e t ) 寻找最优解，所以所求的解均为最优解。但是 随着变量的增加，车辆配送问题的解集合会有组合爆炸( c o m b i n a t o r i a l e x p l o s i o n ) 现象，求解时间也呈指数函数的趋势增长，不能在有限的时间 ( p o l y n o m i a lt i m e ) 给予决策者一个可行解，是这种方法最大的缺点。常见的 精确解法有动态规划法( d y n a m i cp r o g r a m m i n g ) 、分枝定界法( b r a n c ha n d b o u n d ) 与切平面法( c u t t i n gp l a n e s ) 。 4 、传统启发式算法 由于v p s 是强n p 难题，高效的精确算法存在的可能性不大，所以寻找近 似算法是必要的和现实的，为此专家们主要把精力花在构造高质量的启发式算 法上。该方法在解题是可减少搜寻的次数，所以是一种容易且快速求解困难问 题的算法。s o l o m o n 曾提出数个时间窗约束车辆巡回问题的启发式算法，包括 节约法( s a v i n gm e t h o d ) 、最邻近法( n e a r e s tn e i g h b o r ) 、插入法( i n s e r t i o n ) 及扫描法( s w e e p i n g ) 。由于上述各解法起初都用于求解v r p 问题，如果应用 于求解v i 心t w 问题时，则在求解过程中必须增加时间可行性检验，此检验的 目的在于确保配送行程能满足顾客的时间窗的要求，所以当顾客被排入路径时， 需检验该排入点是否违反该顾客的时间窗限制。 ( 1 ) 节约法：c l a r k e w r i g h t 节约算法( c l a r k ea n dw r i g h ts a v i n g s a l g o r i t h m ) 1 4 4 1 是于1 9 6 4 年由c l a r k e 提出的，其思想是将每条路线只含一个配 送点的n 条路线作为初始解，其中，每条路线中第一个和最后一个配送点分别 称为路线的起点和终点。考察一条路线的起点与另一条路线的终点相连合并成 新的一条路线。如果合并后的路线满足约束条件( 车辆容量、车辆运输距离等) ， 则说明这样的合并是可行的，并将合并的节约值定义为连接这两条路线的边的 节约值。选择节约值最大的可行合并进行一次路线的合并。当不存在可行合并 时算法结束。此方法的优点是可提高车辆的利用率，解决车辆调度的规模比精 确算法大，缺点是解是较优的可行解，不一定是最优解。 s o l o m o n 于1 9 8 3 年将此法应用于求解时间窗约束的车辆巡回问题，此方法 的关键在于当节省值较大的两顾客点被排入路径时，除需要考虑车辆容量限制 外，更需要考虑到时间窗的限制，也就是时间窗上界较早者，应优先被配送， 并检验其时间可行性。此方法的优点是可提高车辆的利用率。两节点间的距离 西华大学硕士学位论文 和费用节省值计算公式如下： s ( f ，歹) = d ( i ，o ) + d ( o ，j ) - d ( i ，) ( 2 - 1 ) s ( f ，歹) = c ( i ，0 ) + c ( o ，j ) - c ( i ，j ) ( 2 2 ) 其中s ( f ，j ) 代表两节点i 与j 之间的距离或费用节省值，d ( i ，0 ) 、c ( i ，0 ) 分别 代表顾客i 至配送中心的距离和费用，d ( i ，j ) 和c ( f ，j f ) 分别代表顾客i 至顾客j 的距离和费用。在计算两节点间的节省值时，应先计算原路径中各往返路径的 总距离或总费用，然后与较短路径的总距离或总费用相比较。对往复配送线路 的整合如图2 1 所示。 f i g u r e2 - 1t o - a n d - f r od e l i v e r yw a y sc o n f o r m i t y 图2 - 1 往复配送路线的整合 具体的计算步骤如下： 步骤1 ：计算节约值。将起点分别与各客户点连接，形成n 条初始线路 ( o ，f ，o ) ，f = 1 , 2 ，刀；对f ，j = 1 , 2 ，力且f ，计算节约值s ( f ，) ；将所有的 j ( f ，) 按从大到小的顺序排列。 步骤2 ：可行的最好合并。按照s ( “) 的上述顺序，逐个进行检查，若存在 两条这样的线路，一条包含弧或边( f ，0 ) 另一条包含弧或边( o ，歹) ，且合并后能保 持解可行，则引入弧或边( f ，歹) ，将两条线路合并，并删去( f ，o ) 和( o ，) 。重复该 步骤，直到没有可合并的线路为止。 另外，d e s r o c h e r s 和v e r h o 0 9 1 4 5 1 ，以及a l t i n k e m e r 和g a v i s h l 4 6 1 分别提出了 非常相似的标准节约算法的变形一基于匹配的节约算法( m a t c h i n g b a s e d 1 2 西华大学硕士学位论文 s a v i n g sa l g o r i t h m ) 。其算法思想是：在算法的每次迭代中，合并线路p 和g 所 获得的节约值s 。为 s p q = f ( s p ) + f ( s g ) 一t ( s pu s 口) ( 2 - 3 ) 其中墨是线路k 的点集，r ( 最) 是关于& 的t s p 的一个最优解中的线路长 度。以s 阳的值作为匹配的权，求关于各集合瓯的一个最大权匹配问题。如果 满足可行性的话，则将对应于最优匹配的线路进行合并。这种基本算法可以有 几种变形，其中之一是在运算过程中只取t ( s k ) 的近似值，而不是其精确解。 ( 2 ) 邻接算法：s o l o m o n 【4 7 1 于1 9 8 3 年所提出的求解v r p t w 的方法，它 是一种序列构造路线法。该方法的思想如下所述：由配送中心开始搜寻，若i 为离配送中心最邻近的节点( c 打最小) ，则其优先排入路径中，接着搜寻另一 节点j 以排入路径的下一位，且该节点加入后必须满足以下条件，满足者称为 可排入点： 之前尚未被排入路径的节点； c ；，最小者； 车辆载量限制与时间窗限制的时间可行性。 若其它尚未排入路径的节点中皆无法找到可排入点，则构造另一新路径， 直到所有顾客点都被排入所有路径为止。而决定节点是否为最邻近点的要素有 以下三点： 两顾客节点间的距离d i ； 两顾客节点间的运输时间f 配送下一顾客时所需等待服务的时间材，。 在确定两节点间的最邻近法总成本时，配送中心应先评估对此三要素的权 重组合，且总和应为l ，所以最邻近法总成本的计算公式如下： 白= 6 1 吒+ 6 2 t 玎+ 6 3 ，( 2 - 4 ) 其中 6 l + 6 2 + 6 3 = 1 且6 l ，8 2 ，6 3 为场站对该三要素的权重组合。 ( 3 ) 插入法：序列插入法( s e q u e n t i a li n s e r t i o nh e u r i s t i c s ) 是由m o l e 和 j a m e s o n 4 8 1 于1 9 7 6 年所提出，用于求解v s p 问题的方法，其结合邻接算法与 节约法的观念，依序将顾客点插入路径中以构建配送路线。s o l o m o n 于1 9 8 3 年 1 3 西华大学硕士学位论文 将此方法应用于求解v s p t w 问题，因为时间因素加入，而使原问题的顾客的 等待时间缩短。它的流程与邻接算法相似，也是从初始路线出发，序列构造路 线。并在不存在可行插入时新增一条初始路线。插入算法的关键是选择最合适 的未分配点在路线中进行最佳位置的插入。该算法寻优化速度慢、解非最优， 只适用规模小的车辆调度问题。 此方法的步骤： 选取距离配送中心最远的顾客点为起点，从其它剩余的顾客点中，根据 最邻近法决定下一个被插入的顾客点； 以节约法决定该顾客应被插入的位置，在车辆容量限制下，重复进行选 取与插入的步骤，当无法再扩充路径时，则再建立另一条路线，直至所有顾客 都被排入路径中。 ( 4 ) 扫描法：扫描算法( s w e e pa l g o r i t h m ) 是g i l l e t t 和m i l l e r 【4 9 】于1 9 7 4 年所提出的求解v r p 问题的方法，此方法属于先分群再排路线的方式，此方法 分为两阶段，第一阶段：利用极坐标来表示各需求点的区位，然后任取一需求 点为起点，以车辆容量为分群