（管理科学与工程专业论文）基于遗传算法的车辆调度问题解决方案.pdf

中文摘要 车辆优化调度是物流配送优化中关键的一环。对车辆优化调度理论与方法进 行系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统 和开展电子商务的基础。可见，研究配送车辆调度问题具有重要的理论和现实意 义。 本文一共分为六章。其主要内容如下： 一、对物流配送车辆优化调度问题进行详细介绍，包括国内外研究现状与存 在问题等，并进行分类；最后，提出本文要研究解决的问题。 二、介绍目前用于解决车辆调度问题的相关理论与方法。本章详细介绍了启 发式算法的原理与遗传算法，并阐述了选择遗传算法解决车辆调度问题的原因。 三、集货送货一体化的满载v s p 行车路线规划方法。本章分为两节，分别解 决运输任务己确定和运输任务未确定的情况。在每一节中，首先，对问题进行定 义，并进行分析，建立数学模型，设计遗传算法解决方案，主要包括：设计染色 体结构和适应度函数，选择遗传算子和参数调整策略，设计算法终止条件等；然 后分析了该编码方案的合理性和有效性，并针对不合理的情况设计了调整方案； 最后使用v i s u a lb a s i c6 0 开发了实验测试平台，验证了算法的有效性。 四、本章主要针对非满载的情况，同样分为两节，分别解决运输任务已确定 和运输任务未确定的情况。解决思路同上一章。 五、将前两章的解决方法结合起来，提出集货送货一体化的满载非满载综合 v s p 行车路线规划方法。 六、对所得出的结论进行总结与评价，并提出展望。 关键词：车辆调度问题、启发式算法、遗传算法、染色体 a b s t r a c t v e h i c l eo p t i m i z e ds c h e d u l i n gi st h ec o r el i n ki nl o g i s t i cd e l i v e r y s y s t e m a t i c r e s e a r c ho nt h et h e o r i e so fv s pi st h eb a s eo fd e v e l o p i n gi n t e n s i v el o g i s t i c ，b u i l d i n g m o d e r n s c h e d u l i n gs y s t e m , d e v e l o p i n gi n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m a n d e x p a n d i n ge l e c t r o n i cc o m l n e r c e s o r e s e a r c h i n go nv s ph a sg r e a tm e a n i n gb o t l l t h e o r e t i c a l l ya n dp r a c t i c a l l y t h e r ea l es i xc h a p t e r si nm y p a p e r t h em a i nc o n t e n ti sa sf o l l o w s ： 1 i n t r o d u c et h ev e h i c l es c h e d u l i n gp r o b l e mi nl o g i s t i cd e l i v e r y , i n c l u d i n g ：t h e r e s e a r c hs i t u a t i o na th o m ea n da b r o a d ，e x i s t i n gp r o b l e ma n dc l a s s i f i c a t i o n a tl a s t , i p r o p o s et h ep r o b l e mw en e e dt os o l v e 2 i n t r o d u c et h er e l e v a n tt h e o r i e sa n dm e t h o d st h a tu s et os o l v ev e h i c l e s c h e d u l i n gp r o b l e m 孤sc h a p t e ri n t r o d u c e st h ep r i n c i p i u mo fh e u r i s t i ca l g o r i t h m a n dg e n e t i ca l g o r i t h mp a r t i c u l a r l y , a n de x p l a i n st h er e a s o nw h yic h o o s eg at os o l v e t h ep r o b l e m 3 s o l u t i o nt ot h el o a d i n g & u n l o a d i n gi n t e g r 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 w i t hf u l ll o a d t h e r ea r et w os e c t i o n si nt h i sc h a p t e r o n es o l v e st h ep r o b l e mt h a tt h e t r a n s p o r t a t i o nt a s ki sc o n f i r m e d ；t h eo t h e rs o l v e st h eu n c o n f n r n e dt a s ks i t u a t i o n i n e a c hs e c t i o n , ia n a l y z et h ep r o b l e m ，b u i l dam a t h e m a t i c a lm o d e la n dd e s i g ng a s o l u t i o n , i n c l u d i n g ：d e s i g n i n gt h es t r u c t u r eo fc h r o m o s o m e s a n dt h ef i t n e s se v a l u a t i o n f u n c t i o n , s e l e c t i n gg e n e t i ca l g o r i t h mo p e r a t e r s ，a n dd e s i g n i n gt h e t e r m i n a t i o n c o n d i t i o n s a f t e rt h a tw ea n a l y z et h er e a s o n a b l e n e s sa n dt h ev a l i d i t yo ft h ec o d i n g s o l u t i o n , a n dp u tf o r w a r dt h ea d j u s t m e n ts o l u t i o nf o rt h eu n r e a s o n a b l es i t u a t i o n a t l a s tw ed e v e l o pat e s t i n ge x p e r i m e n tp l a t f o r mw i t hv i s u a lb a s i c6 0 ，a n dv e r i f yt h e v a l i d i t yo f t h ea l g o r i t h mt h r o u g he x p e r i m e n t s 4 t h i s c h a p t e rs o l v e st h en o n - f u l ll o a dp r o b l e m t h e r ea r ea l s ot w os e c t i o n s o n es o l v e st h ep r o b l e mt h a tt h et r a n s p o r t a t i o nt a s ki sc o n f i r m e d ；t h eo t h e rs o l v e st h e u n c o n f i r m e dt a s ks i t u a t i o n 1 1 1 es t e p so f t h es o l u t i o na r et h es a m ea st h el a s tc h a p t e r 5 c o m b i n i n gt h es o l u t i o i l so ft h el a s tt w oc h a p t e r s ，t h i sc h a p t e rp r o p o s e st h e s o l u t i o nt ot h el o a d i n g & u n l o a d i n gi n t e g r 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 l lf u l l l o a d & n o n - f u l ll o a di n t e g r a t i o n 6 s u m m a r i z ea n de v a l u a t et h ec o n c l u s i o n s ，a n dp r o p o s et h ep r o s p e c t k e y w o r d s ：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 ) ；h e u r i s t i ca l g o r i t h m ；g e n e t i c a i g o r i t h m ；c h r o m o s o m e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名： 杰签字日期，磊谢夕日 学位论文版权使用授权书 本学位论文作者完全了解羞鲞本堂有关保留、使用学位论文的规定。 特授权盘生盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：刁夕髫，年z 月 毒眺轹圜 v ；= 审? i 曩 7 日签字日期：矛7 2 月7 日 第一章绪论 第一章绪论 1 1 物流配送车辆优化调度问题概述 随着市场经济的发展，作为“第三利润源泉”的物流对经济活动的影响日益 明显，越来越引起了人们的重视，成为当前最重要的竞争领域之一。在未来的市 场竞争中，物流将起着举足轻重的作用【l 】。 最初的物流概念( p h y s i c a ld i s t r i b u t i o n ) 是美国学者克拉克在2 0 世纪2 0 年代提出的。随着社会经济的发展，物流已从传统的运输服务发展成为以信息技 术和管理为核心的综合物流系统。因此，美国物流管理协会于1 9 8 4 年正式将物 流概念改为了l o g i s t i c s 渊。 现代物流配送流程包括集货、存储、配货、车辆运输等环节，其中存储环节 的要求日益趋向弱化，配送成为最重要的环节，直接为用户服务。配送一般定义 为：将货物从物流结点送达收货人的过程。配送是在集货、配货的基础上，完全 按用户的要求，包括种类、品种搭配i 数量、时间等方面的要求所进行的运送， 是“配”和“送”的有机绪合形式【4 j 。 随着物流配送集约化、一体化的发展，常将配送的各环节综合起来。配送的 核心部分是配送车辆的集货、货物、配装及送货过程；而车辆配送路线的合理优 化，对于整个物流运输速度、成本、效益影响至关重要。根据中国仓储协会对 1 4 6 个企业的调查显示，用于运输的费用占整个物流费用的比例分别为：在生产 企业原料物流中占5 8 ，在生产企业成品物流中占7 3 ，在商业物流中占5 2 【5 1 。 所以进行配送系统优化，最主要是对配送车辆的优化调度，包括集货线路优化、 货物配装及送货线路优化，以及集货、货物配装和送货一体化的优化【3 】。在国外， 类似的工作已广泛地运用于生产、生活的各个方面，如保质投递及线路的优化、 牛奶配送及送达线路的优化、电话预订货物的车辆载货和线路设计、垃圾车的线 路优化及垃圾站选址优化、连锁商店的送货及线路优化等。 物流配送车辆优化调度，是物流配送优化中关键的一环，也是电子商务活动 不可缺少的内容。对货运车辆进行优化调度，可以提高物流经济效益、实现物流 科学化。对货运车辆优化调度理论与方法进行系统研究是物流集约化发展、建立 现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础i ”。 1 2 车辆调度问题分类 车辆调度问题( v i s u a l s c h e d u l ep r o b l e m ，v s p ) 被提出后，国内外各学科 第一章绪论 的学者从不同角度对它进行了各种研究，并各自按不同的标准对其进行了分类 6 , 7 1 。综合起来可分为以下几种： 按任务性质分，有对弧服务问题( 如中国邮递员问题) 和对点服务问题( 如 旅行商伺题) 以及混合服务问题( 如交通车线路安排问题) 。 按车辆载货状况区分，有满载问题( 货运量是车辆容量的整数倍) 和非满载 问题( 货运量小于车辆容量，一辆车可一次完成多项任务) 。 按车场( 或货场，配送中心等) 数目区分，有单车场问题和多车场问题。 按车辆类型区分，有单车型问题( 所有车辆类型和容量相同) 和多车型问题 ( 执行任务的各车辆的类型和容量不完全相同) 。 按车辆对车场的所属关系区分，有车辆开放问题( 车辆可以不返回其发车场) 和车辆封闭问题( 车辆必须返回其发车场) 。 另外，根据v s p 中各项任务是否有时间限制来区分，有一般车辆优化调度问 题和带时间窗的车辆优化调度问题。其中时间窗又可分为硬时间窗和软时间窗， 硬时间窗( h t w ) 是指任务必须在给定的时间范围内完成，否则得到的解视为不 可行解；软时间窗( s t w ) 指如果任务不能在给定的时间范围内完成，则同时给 予一定的惩罚。 按照分类方式的不同，车辆优化调度问题的模型构造和算法也有很大差别 【3 】。 1 3 物流配送车辆优化调度问题研究现状 物流配送车辆优化调度问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出 的【i ，”，之后很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科 学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学 与组合优化领域的前沿与热点问题。在现实生产和生活中，邮政投递问题、车船 调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽 象为配送车辆调度问题。可见，研究配送车辆调度问题具有重要的理论和现实意 义嘲。 物流配送车辆优化调度问题一般可定义为：对于一系列装货点和( 或) 卸货 点，组织合适的行车线路，使载货车辆有序地通过它们，在满足一定的约束条件 ( 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限 制等) 下，达到一定的目标( 如路程最短，费用最少，时间尽量少，使用车辆数 量尽量少等) 1 3 l 。 国外对物流配送车辆优化调度问题作了大量而深入的研究，早在1 9 8 3 年 b o d i n 、g o l d e n 等人在他们的综述文章中就列举了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 ) 编辑的论文集，以及h l t i n k e m e r 和g a v i s h ( 1 9 9 1 ) ，l a p o r t e ( 1 9 9 2 ) ，s a l h i ( 1 9 9 3 ) 等的综述文章中都进行了详尽 的阐述。该领域的代表人物有b o d i n ，c h r i s t o f i d e s ，g o l d e n ，a s s a d ，b a l l ， l a p o r t s ，r i n n o o yk a n ，l e n s t r a ，d e s r o s i e r s 和d e s r o c h e r s 等人”j 。 目前，该问题己不仅仅局限于汽车运输领域，在水运、航空、通讯、电力、 工业管理、计算机应用等领域也有一定的应用，其算法已用于航空乘务员轮班安 排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产 系统中的计划与控制等多种组合优化问题【l 】。 对物流配送车辆优化调度问题，国外一般称之为v e h i c l er o u t i n gp r o b l e m 或v e h i c l es c h e d u l i n gp r o b l e m ，有的学者是根据问题的空间特性和时间特性 的相对重要性来划分的( b o d i n1 9 8 3 ) 。一般以为，不考虑时间要求，仅根据空 间位置安排线路时，称为车辆线路安排问题( v e h i c l er o u t i n gp r o b l e m ，简记 v r p ) ：考虑时间要求安排线路时，称为车辆调度问题( v e h i c l es c h e d u l i n g p r o b l e m ，简记v s p ) 1 9 ；同时考虑空间位置和时间要求时，称为r o u t i n g 和 s c h e d u l i n g 混合问题( v e h i c l er o u t i n ga n ds c h e d u l i n gp r o b l e m ，简记 v r p & v s p ) 。对v r p 与v s p ，也有学者不区分两者，只是加上具体约束定语，例如， 将有时间要求的车辆调度问题称为v e h i c l er o u t i n g p r o b l e mw i t ht i m e w i n d o w s 。由予大多数国外文献习惯采用v s p 表述车辆调度问题，本文循例称之 为v s p 【3 。 1 4 车辆调度问题研究中存在的问题 目前，国内对v s p 研究的比较少，代表著作有郭耀煌、李军编著的车辆 优化调度等；国外对v s p 的研究比较深入，应用也比较广泛，但也存在不足， 主要表现在： 1 、研究非满载问题主要集中在研究集货或送货问题，而对集货和送货一体 化问题研究较少；对有时间窗问题的研究仅限于单车场问题，且因条件限制应用 有限；对单目标研究较多，对多目标情况研究较少；对随机不确定性需求问题的 研究较少，且限于单车场无容量约束的情形( 3 】。 2 、对满载问题的研究较少，仅限于把满载问题转化为非满载问题来处理， 这样不但扩大了变量的维数，而且只有在非满载问题得到很好解决的情况下才有 意义，缺乏实用性【j 】。 3 、研究的车辆调度问题多是运输任务已经确定的情况下的车辆调度，而在 实际中，我们常常只是接收到订单，而要根据订单的情况来安排运输，这里就需 要对运输任务来进行分配和安排，目前这方面的研究还很少。 第一章绪论 4 、算法的适应性差。对于各种各样的v s p ，还没有一种通用算法。即使对 于形式十分相近的问题，通常也不能用同一种算法来求解，给问题的研究者和应 用者带来很大的不便。并且从v s p 提出至今，一直沿用传统的求解方法，没有 太大的突破，对大规模的组合优化问题，传统方法一般很难求得全局最优解，即 使取得全局最优解也要依靠选取优良的初始搜索尉砌。 1 5 本文所要研究车辆调度问题及其意义 在现实生活中，我们经常遇到的问题是： 从车场发出的车辆要先到供应点上货之后运输到相应的需求点，即集货 和送货一体化问题。如果解决了集货和送货一体化问题，将车场与供应 点或需求点的位置设为相同，问题就转化为集货或送货问题； 我们只是收到了订单，需要自己确定要从哪个供应点中供货，即运输任 务未确定问题； 所要执行的运输任务既需要满载运输又需要非满载运输，因为运输任务 量可大可小，即满载和非满载综合问题。 在本文以下章节中，将分别解决以上问题。 首先，本文针对集货与送货一体化的满载问题进行论述，并按运输任务已确 定和运输任务未确定两种情况下进行讨论，设计了比较有效的解决方案； 之后，针对集货与送货一体化的非满载问题进行论述，也是按运输任务己确 定和运输任务未确定两种情况进行讨论，同样也给出了行之有效的解决方案； 最后，本文分析了集货与送货一体化的满载& 非满载综合问题的特点，并将 之前得出的结论加以分析和综合，提出了运输任务已确定和运输任务未确定两种 情况下的解决方案。 本文所研究的问题是从现实中的实际情况出发，抽象出理论模型，再从理论 上提出解决方案，并通过实验平台进行验证，具有很强的实用性和极大的现实意 义。 1 6 本文的体系 4 第一章绪论 一：! i ! ! ! i ；i i ；i i 芝， ，j ，? 1 | ，j ，一：。，二。；车辆优化调度问题解决方法相关理论：，7 7 ：j 7 夕j7 ：l 困；，；匾：匿7 i ，- ，j7 ：，。：，z ? ，。，。车辆调度问题行车路线规划方法：7 ，孑j7 ，7 ，= _ ，7 i 。? j ? ? 一7 ， ，? ，。 j ，j ，j 琴暮贷写送货二体化满载i器襄货写送货二律花非满月 + 1 ：。j ：， ，7 ，。，7 一i ， ， ：，7。， ，一? ，o ，：，黧：车辆调度问题 秀爹，载车辆调度问题鋈 ? 一7 ，i ， 黔；张；一一一。；。 虢女* 。z * 。一一”一”糍? ， ? ? 溺嘲 ? 爨运输任务已确定。舞 雾运输任务已确定l 1_?， 一 ，? ，。| + 琏黪鑫g 黪魏i 融赫赫赣赫籀蕊l 翊| 薹l 藏，骥鑫# 蕊，蕊忿簸；菇藏测! ， ， lj ，i - 畦。廷输任务泰确定；j 睦运输任务未确定j 7 j i ，+ 磷鏊敞戳黼端豁落越甾舞蕊躐蠡 i ，。，? 。i j?，? ， m ，? 一 。?。?7，i i 。7 7i。j7 7 j 谶鬣。豢茹繁落_ 。j 蠢i ；。赫e 撩绺oj j ，。一| j 一? ，7 1 1 | i 篾 集赁与送赁一体化满载非满载综合辆 7 ，“，：77 调度问题 1 0 27 。 爹l 运输任务已确定一 一臻鼍 t0 0 ，j 。j j o j。撬镒邈誊l l 溢滋鑫蕊篮盎鑫麓滚潦凌鍪鍪瀛瓣测 孽 j j ? 0 0 j j j ” li ” 蕊蠡瓣熬涵搿澎麓溢盏盏篮滋澎滋溢澎蕴浏 彬_ ， 图l - l 本文的体系 第二章车辆调度问题解决方法相关理论研究 第二章车辆调度问题解决方法相关理论研究 2 1 车辆调度问题的解决算法分类 车辆优化调度问题的求解方法非常丰富，许多学者对v s p 求解方法的分类 进行了研究，认为究其实质，基本上可以分为精确算法和启发式算法两大类。 2 1 1 车辆优化调度问题的精确算法 精确算法指可求出其最优解的算法，精确算法主要有： l 、分支定界法( b r a n c ha n db o u n d a p p r o a c h ) 混合整数规划问题一般有无限多个可行解。即使是纯整数规划问题，随着问 题规模的扩大，其可行解的数目也将急剧增加。因此通过枚举全部可行解，并从 中筛选出最优解的算法无实际应用价值。分支定界法是一种隐枚举法，或部分枚 举法，它不是一种有效算法，是枚举法基础上的改进。分支定界法的关键是分支 和定界。 若整数规划的松弛问题的最优解不符合整数要求，假设x i = b i 不符合整数要 求，【b i 】是不超过b i 的最大整数，则构造两个约束条件：x i 【b i 】和) 【i b i 】+ l 。 分别将其并入上述松弛问题中，从而形成两个分支，即两个后继问题。两个后继 问题的可行域中包含原整数规划问题的所以可行解。根据需要，各后继问题可以 类似地产生自己的分支，即自己的后继问题。如此不断继续，直到获得整数规划 的最优解。这就是所谓的“分支”。 所谓“定界”，是在分支过程中，若某个后继问题恰巧获得整数规划问题的 一个可行解，那么它的目标函数值就是一个“界限”，可作为衡量处理其它分支 的一个依据。因为整数规划问题的可行解集是它的松弛问题可行解集的一个子 集，前者最优解的目标函数值不会优于后者最优解的目标函数值。所以对于那些 相应松弛问题最优解的目标函数值比上述“界限”值差的后继问题，就可以删除 而不再考虑了。当然如果在以后的分支过程中出现了更好的“界限”，则以它来 取代原来的界限，这样可以提高定界的效果。 “分支”为整数规划最优解的出现创造了条件，而“定界”则可以提高搜索 的效率。经验表明，在可能的情况下，根据对实际问题的了解，事先选择一个合 理的“界限”，可以提高分支定界法的搜索效率【l l 】。 2 、割平面法( c u t t i n gp l a n e sa p p r o a c h ) 用割平面法解整数规划时，若其松弛问题的最优解x 整数约束，则从x 的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中， 6 第二章车辆调度问题解决方法相关理论研究 形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整 数规划的最优解；否则，重复上述步骤，直到获得整数最优解为止。 为最终获得整数最优解，每次增加的线性约束条件应当具备两个基本性质， 其一是已获得的不符合整数要求的线性规划最优解不满足该线性约束条件，从而 不可能在以后的解中再出现；其二是凡整数可行解均满足该线性约束条件，因而 整数最优解始终被保留在每次形成的线性规划可行域中。 从几何意义上课，约束条件实际上对r 做了一次“切割”，在留下的r 中， 保留了整数规划的所以整数可行解，但不符合整数要求的x ，被“切割”掉了。 随着“切割”过程的不断继续，整数规划最优解最终有机会成为某个线性规划可 行域的顶点，作为该线性规划的最优解而被得到【l ”。 3 、网络流算法( n e t w o r kf l o wa p p r o a c h ) 网络流算法是一种高效实用的算法，相对于其它图论算法来说，它的模型更 加复杂，编程复杂度也更高。但是它综合了图论中的其它一些算法( 如最短路径、 宽度搜索算法) ，因而适用范围也更广，经常能够很好地解决一些搜索与动态规 划无法解决的非n p 问题。 网络流在具体问题中的应用，最具挑战性的部分是模型的构造，它没用现成 的模式可以套用，需要我们对各种网络流的性质了如指掌( 比如点有容量、容量 有上下限、多重边等等) ，根据具体的问题发挥我们的创造性。一道问题经常可 以建立多种模型，不同的模型对问题的解决效率的影响也是不同的。 4 、动态规划方法( 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 ) 阶段；( 2 ) 状态；( 3 ) 决策和策略；( 4 ) 状态转移；( 5 ) 指标函数。 第二章车辆调度问题解决方法相关理论研究 建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程。其关键在 于识别问题的多阶段特性，将问题分解成为可用递推关系式联系起来的若干子问 题，而正确地建立递推关系方程的关键又在于正确选择状态变量，保证各阶段的 状态变量具有递推的状态转移关系【1 1 】。 精确算法的计算量一般随问题规模的增大呈指数增长，因此在实际中其应用 范围很有限。 2 1 2 车辆优化调度问题的启发式算法 由于v s p 是强n p 难题，高效的精确算法存在的可能性不大，所以寻找近似 算法是必要和现实的，为此专家们主要把精力花在构造高质量的启发式算法上 1 2 - 2 。启发式算法是指一种基于直观或经验构造的算法，目标是在可接受的花费 ( 计算时间、占用空间等) 下得出待解决问题的满意解，而不是最优解。考虑到 v s p 是强n p 难题，而启发式方法能够比较快地得到满意解，这对解决n p 难题来 说有着不可估量的作用，因此大部分文献中，专家们主要是在构造各种高质量的 启发式算法。目前已提出的启发式算法很多，分类也相当多，按c e s a rr e g o 的 分类法有以下分类f 3 ，2 2 】。 1 、构造算法( c o n s t r u c t i v ea l g o r i t h m ) 根据一些标准，每一次将一个不在线路上的点增加进线路，直到所有的点都 被安排进线路为止。该类算法的每一步，把当前的线路构形( 很可能是不可行的) 跟另外的构形( 也可能是不可行的) 进行比较并加以改进，最后得到一个较好的 可行构形。另外的构形指，根据某个判别函数( 例如总费用) 可产出最大限度 节约的构形，或是能以最小代价把一个不在当前构形上的需求对象插入进来的构 形。 构造算法是最早提出用来解决旅行商问题( 简称t s p ) 及v s p 的，这些方法 一般速度快，也很灵活，但这类方法有时找到的解和最优解相差很远【3 】。 2 、两阶段法( t w o - p h a s ea l g o r i t h m ) 学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改 进，为此提出了两阶段法。第一阶段得到一个可行解，第二阶段通过对点的调整， 在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解 来代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为 止。一般第一阶段常用构造算法，在第二阶段常用的改进技术有2 一o p t 】，3 一o p t 凹】 和o r o p t 【2 习，这是一种在解的领域中搜索，对初始解进行某种程度优化的算法， 以改进初始解。 一些基于数学规划的算法也属于两阶段法，可以把问题直接描述成一个数学 8 第二章车辆调度问题解决方法相关理论研究 规划问题，根据其模型的特殊构形，应用一定的技术( 如分解) 进行分划，进而 求解已被广泛研究过的子问题。 在两阶段求解过程中，常常采用交互式优化技术，把人的主观能动作用结合 到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种 判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会 增加模型最终实现并被采用的可能性。 两阶段法是目前成果最丰富，应用最多的一类方法。每一种方法讨论的情况 不尽一致，适用范围也不完全相同【3 】。 3 、不完全优化算法( i n c o m p l e t eo p t i m i z a t i o n a l g o r i t h m ) 以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空n t 3 3 。 4 、改进算法( i m p r o v e m e n tm e t h o d s ) 从一初始解开始，通过对当前的解进行反复地局部扰乱以达到较好的解。基 于启发式的并行算法和一些称为亚启发式算法的方法都属于此类。 用并行算法求解v s p 还处于起步阶段，并且都是基于一种启发式规则如节 约算法、插入算法等等。由于并行算法要求条件较高，一般需要并行计算机效果 才好，这在现实应用中很受限制【2 6 i 。 亚启发式算法包括表搜索法( t a b us e a r c h ) 、模拟退火算法( 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 ) 和神经网络( n e u r a ln e t w o r k s ) 方法 2 7 , 2 8 。 表搜索算法和模拟退火算法在求解v s p 中已取得了较好的效果。但是这些 方法过于复杂，运算量大，涉及复杂的邻域转换和求解策略，在实际中不容易实 现【2 9 】。 遗传算法在旅行商问题中的应用已有一定成果，已有文献利用遗传算法对 v s p 进行求解，但仅仅是开始尝试阶段，还有待于进一步的研究d o l 。 神经网络的发展，也促进了t s p 的较好解决，但在v s p 中的应用还剐刚开 始【”1 。 上面这几类启发式算法，其划分常不是绝对的，有的方法同属于好几类。由 于v s p 问题的复杂性，使各种算法的比较很困划“。 2 2 启发式算法理论 启发式源自英文单词h e u r i s t i c s ，启发式方法意为通过对过去经验的归纳推 理以及实验分析来解决问题的方法，即借助于某种直观推断或试探性的方法。启 发式方法要求分析人员必须运用自己的感知和洞察力，从与研究问题有关而较基 本的模型及算法中寻求其间的联系，从中得到启发，去发现适于解决问题的思路 9 第二章车辆调度问题解决方法相关理论研究 和途径。 用启发式算法解决问题时强调“满意”，常常是得到满意解，决策者就认为 可以了，而不去追求最优解和探求最优解。之所以这样，原因是： 1 、很多问题不存在严格最优解，这时，对目标的满意性常比最优性更能准 确地描述人们的选择行为。 2 、对有些问题，得到它的最优解所花的代价太大。 3 、从实际决策的需要出发，有时要求结果有过高的精度没有意义。 启发式算法能够比较快地得到满意解，这对解决n p 难题来说，有着不可估 量的作用。 2 2 1 启发式算法的求解过程 用启发式算法求解问题是通过迭代过程实现的，因而需拟订出一套解的搜索 规则，为能得到满意解，在整个迭代过程中要不断吸取新的信息，必要时改变原 来拟定的不合适的策略，建立新的搜索规则，注意从失败中吸取教训，并逐步缩 小搜索范围。 2 2 2 启发式策略 用启发式算法求解问题时，需要采用一定的策略。下面列举几个常用的策略， 可根据问题的性质和要求选用。 1 、逐步构造解策略 逐步构造解策略是指每次增加解的一个元素( 如结点、弧) ，直至得到一个 完整的可接受解。 2 、改进解策略 这种方法从一个初始解( 初始解不一定可行) 开始，通过一系列替换、分解 和合并过程来逐步修正解，以提高解的可接受性。 3 、数学规划策略 数学规划策略运用数学模型和优化算法，并通过对解的判别和修正以提高对 问题的实用性，常会得出高效的启发式算法。 4 、分解策略 把一个复杂的问题分解成一系列易于处理的子问题来求解，一个问题的输出 常是下一个子问题的输入。 5 、分割策略 这种策略把一个复杂的问题分割成一些平行的小的子问题，然后求解每一个 子问题，最后在相容原则下进行综合，把子问题的解合并成原问题的一个解。 第二章车辆调度问题解决方法相关理论研究 6 、可行解空间的限制策略 在某些情况下，把可行解集限制到一个可应用己存在高效算法的解集上，然 后再求解问题。 7 、松弛策略 有时扩展问题的可行域( 即放松约束) 以得到一个易于处理的松弛问题，然 后求解松弛问题，就能直接得到或者很容易得到原问题的一个可行解，然后再对 得到的解进行修正。 8 、搜索学习策略 此策略包括在解空间的定向搜索以及在搜索过程中发现和收集新的信息，并 根据对新信息的分析，重新确认或改变搜索方向，修正搜索参数，消去不必要的 搜索范围，以有效提高搜索效率，尽快获得问题的解。 在构造启发式算法时，一般都采用上述的某一种策略，或者是几种策略的组 合形式。有时在启发式算法的某一步也可采用优化算法来提高算法的精度。 2 2 3 启发式算法的评价标准 对构造的启发式算法，衡量它是优还是劣主要有以下几个评价标准。 1 、解的质量 对启发式算法产生的解的质量进行测度，包括下面两个方面：目标函数值与 最优值的近似值；算法产生可行解的能力。 测度启发式算法得到的解与最优化方法所得解的接近程度有许多方法，如实 例分析、统计分析等。测度时还应明确解的质量对问题特征的依赖关系。 2 、运行时间和所需存储量 启发式算法的好坏与算法所需的存储量大小及求解问题的运行时间长短密 切相关。在测度时可应用概率分析、经验分析和对最坏情形下的分析等方法。 3 、实现的难度 启发式算法实现的难度大小主要指编码的复杂程度如何及对数据的需求情 况。 4 、灵活性 指启发式算法能否容易地处理模型、约束和目标函数的变化。一个好的启发 式算法，一般来说应具有适应性广和比较灵活的特点。 5 、可靠性 启发式算法应具有进行灵敏度分析和产生解的界值的能力。一个好的启发式 算法可以使用户能利用得到的信息确定所得的解与最优解的接近程度，避免得出 错误的结果。 第二章车辆调度问题解决方法相关理论研究 6 、简洁性和可分析性 算法应该能够用简洁明了的语言陈述出来，而且易于分析。 7 、交叉式特性 在大多数情况下，算法都应便于人一机交互式处理，以更好地反映决策者的 愿望。 2 2 4 车辆优化调度问题的启发式算法 目前用于求解v s p 的启发式算法相当多，从实质上讲大体可分为以下几大 类： 1 、先分组后安排线路的方法 这种方法是先把结点或弧的需求进行分组或划群，然后对每一组设计一条经 济的线路。如g i l l e t t 和m i l l e r 的s w e e p 算法，其目的在于形成需求点的径向区 域，从车场发出的射线“扫过”这个区域，使不超过车辆容量的需求点组成一个 区域，一个区域就是一组，当形成一系列这样的组合，再对组中的各点安排线路， 这种算法一般仅适应于装货或卸货问题，且车辆是封闭的。 2 、先安排线路后分组的方法 这种方法首先构造一条或几条通常不可行的长线路，它包含了所有需求对 象，然后再把这些长线路分成一些短而可行的线路。具体进行时，一般是先解一 个经过所有点的旅行商问题，形成一条线路，然后根据约束对其进行划分。 3 、节约一插入法 该算法的每一步都把当前的线路跟另外的线路进行比较后加以改进。后者或 是根据某个目标函数产生最大限度的节约的线路，或是以最小代价插入一个不在 当前线路上的需求对象的线路，最后得到一个较好的可行线路。如c l a r k e w r i g h t 的“节约”算法。 4 、改进一交换法 在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可 行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数 为止。如c h r i s t o f i d e s 和e i l o w 算法，把问题先转化成一个旅行商问题得到初始 解，然后应用交换法2 o p t 或3 - o p t 来改进初始解。 5 、基于数学规划的方法 把问题直接描述成一个数学规划问题，根据其模型的特殊构形，利用一定的 技巧进行划分，进而求解已被广泛研究过的子问题。如f i s h e r 和j a i k u m a r 把车 辆线路安排问题构造为一个广义分派问题，提出下述启发式算法：首先把问题描 述为一个数学规划问题，再将其分解为一个旅行商问题和一个分派问题。把每一 第二章车辆调度问题解决方法相关理论研究 辆车分派给某些顾客可通过解一般分派问题来得到。每辆车为它的顾客服务，以 一个近似等于旅行商线路的费用为目标，分派一旦做出，通过应用解决旅行商问 题的启发式算法或优化算法来得到每辆车的行车路线。 6 、交互式优化法 交互式方法把人的主观能动作用结合到问题的求解过程中，其主要思想是： 有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观 的估计加到优化模型中去，这样通常会增加模型最终解决实际问题的能力。 以上启发式算法的分类并不是绝对的，某一中算法可能属于以上几大类。因 此我们应该具体问题具体对待，从多方面考虑问题，尽可能地构造出高效省时且 行之有效的算法。 由于v s p 是n p 难题，因此，要想在v s p 上有更大的突破，必须引入新思 想、新方法，而遗传算法的引入正是适应了这种需要。 2 3 遗传算法理论介绍 2 3 1 生物进化与遗传算法的产生 生命自从在地球上诞生以来，就开始了漫长的生物进化历程。关于生物进化 的原因有多种解释，其中被人们广泛接受的是达尔文的自然选择学说。自然选择 学说认为，生物要生存下去，就必须进行生存斗争。生物斗争包括种内斗争、种 间斗争以及跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个 体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体 就容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体 都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰 的过程叫做自然选择。自然选择学说表明，遗传和变异是决定生物进化的内在因 素【3 2 1 。 。 生命科学与工程科学的相互交叉、相互渗透和相互促进是近代科学技术发展 的一个显著特点，而遗传算法的( g e n e t i ca l g o r i