（控制理论与控制工程专业论文）车辆路径问题的启发式算法研究.pdf

摘要 摘要 物流配送中的车辆路径问题是运筹学和组合优化领域的研究前沿与热点问 题。车辆路径问题是对一系列已知需求量的客户，组织适当的行车线路进行服务， 在不违反任何约束条件下，优化路线使得总成本达到最小。有效地解决该问题可 以提高车辆的利用率，降低配送成本，提高配送时间的准确率，从而提高物流服 务水平。由于车辆路径问题是典型的n p 难题，使用传统的优化方法很难得到问 题的最优解或满意解，因此构造高质量的启发式算法成为研究该问题的主要发展 方向。 本文针对有时间窗的车辆路径问题提出了两种求解算法基于【交换的 局部下降搜索算法和基于自然数编码的遗传算法。前者是一个两阶段启发式算 法，可以有效地获得该问题的可行解。然而局部搜索算法易于陷入局部极小，因 此具有一定的全局搜索能力的遗传算法在求解组合优化问题时显示出了优越性。 遗传算法是基于“适者生存”的一种高度并行、随机和自适应的优化算法。虽然 遗传算法没有传统的优化算法复杂的运行机制，但是遗传算法具有很强的搜索能 力，能以很大概率找到问题的全局最优解，并且由于它固有的并行性，能有效地 处理大规模的优化问题。因此，与基于 交换的局部下降搜索算法相比，基于 自然数编码的遗传算法可以更好的解决有时间窗的车辆路径问题。 本文研究内容的一个重点和难点是集货和送货一体化的车辆路径问题。本文 采用了新颖的自然数编码方法，设计了遗传算法对该问题进行求解。在求解过程 中，对集送一体化、多种配送车辆类型的问题进行了有效处理，同时考虑了车辆 载重量和时间窗等约束。 通过求解s o l o m o n 提出的标准化有时间窗的车辆路径问题的5 6 个实例，将 本文提出的两种启发式算法的求解结果与笔者已知的最优解进行了比较。比较说 明本文提出的两种算法可以较好的解决s o l o m o n 标准化问题中的部分实例并且 具有较好的平均性能。本文还通过实际的北京市劲松地区路网，验证了求解集送 一体化的车辆路径问题的遗传算法，实验证明该算法是可行和实用的。 关键词车辆路径问题；启发式算法；遗传算法；编码 北京工业大学工学硕士学位论文 a b s t r a c t t h ev e h i c l er o u t i n gp r o b l e m ( v r p ) i nl o g i s t i c si sar e s e a r c h 矗o n f i e ra n dh o t s p o t p r o b l e mo fo p e r a t i o n a lr e s e a r c ha n dc o m b i n a t o r i a lo p t i m i z a t i o nf i e l d i nt h ev e h i c l e r o u t i n gp r o b l e m as e to fg e o g r a p h i c a l l yd i s p e r s e dc u s t o m e r sw i t l lk n o w nd e m a n d s a r et ob es e r v e db yaf l e e to fv e h i c l e s t h eo p t i m i z e dr o u t i n e sf o re a c hv e h i c l ea r e s c h e d u l e da st oa c h i e v et h em i n i m a lt o t a lc o s tw i t h o u tv i o l a t i n ga n yc o n s t r a i n t s s o l v i n gv r ps u c c e s s f u l l yc a ni n c r e a s et h eu t i l i z a t i o nr a t i oo fv e h i c l e ，r e d u c et h e w o r k i n gc o s t sa n di m p r o v ea c c u r a c yr a t eo fs e r v i c et i m e s oi tw i l le n h a n c el o g i s t i c s l e v e l b e c a u s ev r pi sat y p i c a ln p h a r dp r o b l e m t r a d i t i o n a la l g o r i t h m sa r eh a r dt o o b t a i nt h eo p t i m a lo rs a t i s f a c t o r ys o l u t i o n i nv i e wo fi t ，e x p l o i t i n gt h eh e u r i s t i c so f h i g hq u a l i t yh a sb e c o m et h em a i nr e s e a r c h i n gt r e n d t h j sp a p e rd e s c r i b e st w oa l g o r i t h m st os o l v ev e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w s ( v r p t w ) o n ei sl o c a ls e a r c hd e s c e n tm e t h o db a s e do n ，l - i n t e r c h a n g e ，t h e o t h e ri sg e n e t i ca l g o r i t h mb a s e do nn a t u r en u m b e rc o d i n g 1 l l ef o r m e ri sat w o p h a s e d h e u r i s t i c a n di tc a no b t a i nt h ef e a s i b l es o l u t i o no fv r p t we f f e c t i v e l y h o w e v e rt h e l o c a ls e a r c hm e t h o di ss u b j e c tt oc o n v e r g et ol o c a lm i n i m u m ，t h eg e n e t i ca l g o r i t h m t h a th a s s p e c i f i cg l o b a ls e a r c ha b i l i t yh a ss h o w ns o m ea d v a n t a g e si ns o l v i n g c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m g e n e t i ca l g o r i t h mi sap a r a l l e l ，r a n d o ma n d a d a p t i v eo p t i m a lm e t h o dt h a t i sb a s e do ns u r v i v a lo ft h ef i t t e s t a l t h o u g hg e n e t i c a l g o r i t h m i sn o ta s g o o d a st r a d i t i o n a l a l g o r i t h m s o n c o m p l i c a t e do p e r a t i o n m e c h a n i s m ，i th a sg o o ds e a r c ha b i l i t ys ot h a ti tc a no b t a i ng l o b a lo p t i m a ls o l u t i o n w i t hh i g hp r o b a b i l i t y f u r t h e r m o r e ，t h ei n h e r e n tp a r a l l e l i s mm a k e si te f f e c t i v et o t a c k l et h em a s so p t i m i z a t i o np r o b l e m s oc o m p a r e dw i t ht h el o c a ls e a r c hd e s c e n t m e t h o db a s e do n a i n t e r c h a n g e ，t h eg e n e t i ca l g o r i t h mb a s e do nn a t u r en u m b e r c o d i n gc a ns o l v et h ev r p t w m u c hb e t t e r v e h i c l er o u t i n gp r o b l e mw 池p i c k u pa n dd e l i v e r y ( v r p p d ) i sak e y s t o n ea n d n o d u so ft h i s p a p e r i n t h i s p a p e r , w h i l ec o n s t r a i n so fp i c k u pa n dd e l i v e r y ， h e t 9 r o g e n e o u sf l e e ta r ed e a l tw i t l le f f e c t i v e l y , a l li m p r o v e dg e n e t i ca l g o r i t h mo nn o v e l n a t u r en u m b e rc o d i n gi sd e s i g n e d a tt h es a m et i m e ，v e h i c l e c a p a c i t ya n dt i m e w i n d o w sr e s t r a i n t sa r ec o n s i d e r e d t h ef i r s tt w oh e u r i s t i c sa r ea p p l i e dt os o l v eas e to fb e n c h m a r kp r o b l e m sb a s e d o nt h es o l o m o n s5 6v r p t wi n s t a n c e s a 1 1t h er e s u l t so b t a i n e df r o mo u rh e u r i s t i c s h a v eb e e nc o m p a r e dw i t ht h eb e s t - k n o w nr e s u l t si nl i t e r a t u r ea c c o r d i n gt om yb e s t a b 5 l ( a 0 l k n o w l e d g e i th a sb e e ns h o w nt h a tt h et w oh e u r i s t i c sp r o d u c ec o m p e t i t i v es o l u t i o n si n s o m ei n s t a n c e sa sw e l la sa c h i e v eg o o da v e r a g e dr e s u l t s a n dt h eg af o rv r p p di s a p p l i e dt os o l v et h ei n s t a n c eb a s e do nt r a f f i cn e t w o r ko f j i n s o n ga r e ai nb e i j i n gc i t y t h ee x p e r i m e n td e m o n s t r a t e st h a tt h i sa l g o r i t h mi sa p p l i c a b l ea n df e a s i b l e k e yw o r d sv e h i c l er o u t i n gp r o b l e m ；h e u r i s t i c ；g e n e t i ca l g o r i t h m ；c o d i n g 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：趔日期：塑丛杰丛 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：邀 导师签名：垄垒妻 日期 2 0 。s z 6 第1 章绪论 第1 章绪论 1 1 课题背景及研究意义 1 1 1 研究背景 1 9 0 1 年j eg 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 9 年1 1 月，国家经 贸委同世界银行在北京召开了现代物流国际研讨会后，我国的现代物流有了迅速 发展。但是由于我国物流刚刚摆脱计划经济体制的束缚，目前还没有形成一个比 较完整的体系。 现代物流业是把握竞争优势的有效方式，将为国民经济在高起点上持续发 展，提供基础动力。在经济全球化和信息化的推动下，现代物流业已从为社会提 供传统运输服务，扩宽到以现代科技、管理和信息技术为支柱的综合物流系统。 目前，许多发达国家和地区已形成了比较成熟的物流管理理念、先进的物流技术 和高效的物流运营系统。进入2 1 世纪的中国，必将加快现代物流的发展，以此 增强企业竞争能力。优化资源配置，提高经济运行质量，实现中国经济体制与经 济增长方式的两个根本性转变，从而推动中国经济的持续健康的发展。 北京工业大学工学硕士学位论文 1 1 2 研究意义 物流配送是物流中一个重要的直接与消费者相连的环节，是货物从物流结点 送达收货人的过程。配送是在集货、配货基础上，按货物种类、品种搭配、数量、 时间等要求所进行的运送，是“配”和“送”的有机结合。物流配送过程主要包 括：从生产工厂进货并集结的集货作业；根据各个用户的不同需求，在配送中心 将所需要的货物挑选出来的配货作业：考虑配送货物的质量和体积，充分利用车 辆的载重和容积的车载货物的配装及配送路线的确定。 随着物流系统的集约化、一体化的发展，常将配送的各环节综合起来，核心 部分为配送车辆的集货、货物配装及送货过程。进行配送系统优化，主要就是配 送车辆优化调度，包括集货线路优化、货物配装及送货线路优化，以及集货、货 物配装和送货一体化优化。 物流配送车辆优化调度，是物流系统优化中关键的一环，也是电子商务活动 不可缺少的内容。对配送车辆进行优化调度，可以提高物流经济效益、实现物流 科学化。可以说对物流配送车辆优化调度理论与方法进行系统研究是物流集约化 发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开 展电子商务的基础。 中国加入w t o 后，物流市场的开放，大量国外物流企业的进入，对于中国 的物流企业来说既是机遇，又是挑战。一方面我们可以学习他们先进的管理经验 和技术：另一方面我国物流企业必须与他们相互竞争，争夺同一块市场。要想在 竞争中立于不败之地，准时、安全、低成本的物流配送服务是很重要的。要想做 到这一点，人工调度是远远不够的，必须对车辆运营调度问题进行系统研究。 人工调度不能满足现代物流企业的需求是因为人工调度具有以下不足：首 先，人工调度对于调度人员来说，工作强度很大，同时随着物流公司规模的不断 壮大，客户的需求越来越多，配送车辆数也在不断增多，到一定规模人工就难以 完成整个公司的车辆调度；其次，调度人员对所有车辆的状态，以及整个城市的 交通状况把握不是很准，难以对所有的资源进行全局优化，车辆的时空利用率不 高；另外，人工调度还受人员的限制，一旦调度人员不能工作，将会影响整个公 司的运营。 车辆优化调度作为物流企业运作中的核心，对于整个公司的运营效率有着至 关重要的作用。通过对车辆调度系统研究，不但可以更好的提高车辆的利用率， 而且可以减轻调度人员的工作强度，并且不会受人员的限制影响。更重要的是通 过车辆优化调度可以减少配送的车辆数，减少车辆的行驶距离和时间，降低配送 成本，提高配送时间的准确率，从而提高物流服务水平。 一2 一 第1 章绪论 1 2 车辆路径问题的研究概述 1 2 1 问题的提出 国外将物流配送车辆优化调度问题归结为或称之为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 ，即车辆路径问题或车辆调度问题。 物流配送中的车辆路径问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出 的。自此，该问题很快引起运筹学、应用数学、组合数学、图论与网络分析、物 流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为 运筹学与组合优化领域的研究前沿与热点问题。各学科专家对该问题进行了大量 的理论研究及实验分析，取得了很大进展。 该问题一般定义为：对一系列装货点和( 或) 卸货点，组织适当的行车线路， 使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、发送量、交发 货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目标( 如 路程最短、费用最少、时间尽量少、使用车辆数尽量少等) 。 国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1 9 8 3 年b o d i n 、g o l d e n 1 1 等人在他们的综述文章中就列举了7 0 0 余篇文献。在t o t h 和 v i g o l 2 1 编辑的论文集，以及a l t i n k e m e r 和g a v i s h 3 1 ，l a p o r t e 4 1 ，s a h l i t 5 】等人的综 述文章中都进行了详尽的阐述。该领域的代表人物有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 ，l a p o r t e ，d e s r o s i e r s 等人。 目前，问题的形式已有很大发展，该问题已不仅仅局限于汽车运输领域，在 水运、航空、通讯、电力、工业管理、计算机应用等领域也有定的应用，其算 法已用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设 计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。 对物流配送车辆优化调度问题，有的学者是根据问题的空间特性和时间特性 的相对重要性来划分的。一般认为，当不考虑时间要求，仅根据空间位置安排线 路时称为车辆线路安排问题( 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 gp r o b l e m ，简记v s p ) ；同时 考虑空间位置和时间要求时称为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 g a 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 ew i n d o w s 。 本论文将车辆优化调度问题统称为v e h i c l er o u t i n gp r o b l e m 车辆路径问 题。 北京工业大学工学硕士学位论文 1 2 2 分类 自v r p 被提出后b o d i n u j ，d e s r o c h e r s ，l i n s t r a 和s a v e l s b e r g h t 6 j 等许多学者 对v r p 从不同角度，按不同的标准进行了多种分类。 如按任务特征分，有纯装问题或纯卸问题( p u r e p i c ku p o r p u r ed e l i v e r y ，车 辆在所有任务点装货或卸货，即集货或送货问题) 及装卸混合问题( c o m b i n e dp i c k u pa n dd d i v e r y ，每项任务有不同的装货点和卸货点，即集货、送货一体化问题) 。 按任务性质分，有对弧服务问题( 如中国邮递员问题) 和对点服务问题( 如 旅行商问题) 以及混合服务问题( 如交通车线路安排问题) 。 按车辆载货状况分，有满载问题( 货运量不小于车辆容量，完成一项任务需 要不只一辆车) 和非满载问题( 货运量小于车辆容量，多项任务使用一辆车) 。 按车场( 或货场、配送中心等) 数目分，有单车场问题和多车场问题。 按车辆类型数分，有单车型问题( 所有车辆容量相同) 和多车型问题( 执行任 务的车辆的容量不全相同) 。 按车辆对车场的所属关系分，有车辆开放问题( 车辆可以不返回其发出车场) 和车辆封闭问题( 车辆必须返回其发出车场) 。 按优化目标数来分，有单目标问题和多目标问题。 由于情况的不同，车辆路径问题的模型构造及算法有很太差别。 1 2 3 计算复杂性 计算复杂性的研究是离散优化的重要内容之一，通过对复杂性的研究，可以 确定求解算法的研究方向。 v r p 被提出后，有不少专家和学者对它的计算复杂性进行了研究。l e n s t r a 和r i n n o o yk a n ”在1 9 8 1 年的文章中，对v r p 的计算复杂性进行了综述和分析； k a r p ( 1 9 7 2 ) 证明了旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，简称t s p ) 和有 向旅行商问题( d i r e c t e dt r a v e l i n gs a l e s m a np r o b l e m ，简称d t s p ) 为n p 难题， p a p a d i m i t r i o u ( 1 9 7 6 ) 证明了多重旅行商问题( m u l t i p l et r a v e l i n g s a l e s m a n p r o b l e m ，简称m t s p ) 为n p 难题，e d m o n d s 和j o h n s o n ( 1 9 7 3 ) 证明了中国邮 递员问题( c h i n e s ep o s t m a np r o b l e m ，简称c p p ) 的复杂性为o ( v 3 ) ，e d m o n d s 和k a r p ( 1 9 7 2 ) 证明了有向中国邮递员问题( d i r e c t e d c h i n e s ep o s t m a n p r o b l e m ， 简称d c p p ) 的复杂性为o ( v 3 l o g a ) ，d a n t z i g 和f u i k e r s o n ( 1 9 5 4 ) 证明了有确 定开始时问的v r p 的复杂性为o ( ) 。s a v e l s b e r g h s l 提出有时间窗约束的v r p 比一般的v r p 更复杂，并提出有时间窗约束的v r p 不仅问题本身是n p 难题， 甚至在车队大小固定时，找一个可行解也是n p 难题。l e n s t r a 和r i n n o o yk a n 还 d 第1 章绪论 证明了几乎所有类型的v r p 均为n p 难题。 1 3 车辆路径问题的研究动态和水平 车辆路径问题的求解方法非常丰富，究其实质，基本上可以分为精确算法和 启发式算法两大类。 精确算法指可求出其最优解的算法。对于精确算法，d e s r o c h e r s 【9 】，k o h l 和 m a d s e n 1 0 l 等人做过有关的研究，其中又可以分为分支界定法、割平面法、网络 流算法、动态规划法等。 总的来说，精确性算法是基于严格的数学手段，在可以求解的情况下，其解 通常要优于人工智能算法。但由于引入严格的数学方法，因而无法避开指数爆炸 问题，从而使该类算法只能有效求解中小规模的确定性v r p 。 由于v r p 是n p h a r d 问题，难以用精确算法求解，因此，目前启发式算法 是求解车辆路径问题的主要方法，多年来许多学者对车辆路径问题进行了研究， 提出了各种各样的启发式方法，v a nb r e e d a m j 将启发式算法分为三类：路线构 造法( r o w e c o n s t r u c t i o na l g o r i t h m ) ，两阶段法( t w o p h a s e da l g o r i t h m ) 和基于精 确方法的启发式算法( h e u r i s t i c sb a s e do ne x a c ta l g o r i t h m ) 。其中前两类较为常 见。 ( 1 ) 路线构造法这类方法的基本思想是：根据一些准则，每一次将一个不 在线路上的点增加迸线路，直到所有的点都被安排迸线路为止。该类算法的每一 步把当前的线路构形( 很可能是不可行的) 跟另外的构形( 也可能是不可行的) 进行比较并加以改进，后者或是根据某个判别函数( 例如总费用) 会产生最大限 度的节约的构形，或是以最小代价把一个不在当前构形上的需求对象插入进来的 构形，最后得到一个较好的可行构形。这类算法中最著名的是c l a r k e 和w r i g h t l l 2 1 在1 9 6 4 年提出的算法。 构造算法是最早提出用来解决旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简 称t s p ) 及v r p 的，这类方法一般速度快，也很灵活，但这类方法有时找到的 解离最优解差的很远。 ( 2 ) 两阶段法学者们通过对构造算法的研究，认为由构造算法求得的解可 以被进一步改进，为此提出了两阶段法。第一阶段得到一可行解，第二阶段通过 对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生 另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进 目标函数值为止。g i l l e t 和m i l l e r 的s w e e p 算法，c h r i s t o f i d e s 、m i n g o z z i 和t o t h 的算法以及f i s h e r 和j a i k u m a r 的算法都属于两阶段法。一般第一阶段常用构造 算法，在第二阶段常用的改进技术有2 - o p t 、3 - o p t 和o r - o p t 交换法，这是一种在 气一 北京工业大学工学硕士学位论文 m- -_ _ 解的邻域中搜索，对初始解进行某种程度优化以改进初始解的算法。 一些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学规划 问题，根据其模型的特殊构形，应用一定的技术( 如分解) 进行分划，进而求解 已被广泛研究过的予问题。 在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结 合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某 种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常 会增加模型最终实现并被采用的可能性。 两阶段法是目前成果最丰富、应用最多的一类方法。每一种方法讨论的情况 不尽一致，适用范围也不完全相同。 ( 3 ) 基于精确方法的启发式算法这类算法以启发式准则来代替精确算法中 的决策准则，以缩小解搜索的空间。 总体来看，尽管启发式算法能够在有限的时间内求出质量较高的解，但由于 其搜索解空间的能力的限制，因此经常无法达到预期的要求。而在2 0 世纪9 0 年 代兴起的亚启发式算法( m e t a h e u r i s t i c s ) 则较好的解决了搜索空间有限的问题， 从而引起了诸多学者的关注。 亚启发式算法从本质上讲仍然属于启发式算法，其基本思想是是从一初始解 开始，通过对当前的解进行反复地局部扰乱( p e r t u r b a t i o n s ) 以达到较好的解。 目前常见的亚启发式算法包括模拟退火算法( s i m u l a t e da n n e a l i n g ) 、禁忌 搜索算法( t a b us e a r c h ) 、遗传算法( g e n e t i ca l g o r i t h m ) 、蚁群算法( a n tc o l o n y ) 和神经网络( n e u t r a ln e t w o r k s ) 方法等。 模拟退火( s a ) 算法的思想最早由m e t r o p o l i s 在1 9 5 3 年提出，o s m a n 1 3 1 用 之解决v r p 。该算法通过模拟冶金作业的退火过程来搜索解空间。在某一初温 下，伴随着温度参数的不断下降，结合概率突跳特性在解空间中寻找目标函数的 全局最优解，即能概率性地跳出局部最优解并最终趋于全局最优。但是为了寻找 最优解，算法通常需要较高的初温，较慢的降温速度，较低的终止温度以及各温 度下的多次搜索新状态，因而s a 的运行时间较长，这是s a 的最大缺点。 禁忌搜索( t s ) 是基于存储结构的搜索策略，最早由g l o v e r 于1 9 8 6 年提出， 用来引导局部搜索跳出局部最优。它通过引入一个灵活的存储结构( 禁忌表) 和 相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状 态，进而保证多样化的有效探索以最终实现全局优化。g e n d r e a u 等人最先将该 方法应用于v r p ，其后e t a i l l a r d 等人通过按角度和路径重心对原问题的空间进 行分割，再用禁忌搜索结合模拟退火对子问题求解，实现了对问题求解的并行化。 c h i a n g 和r u s s e l 在提出了反应禁忌搜索算法( r e a c t i v et a b us e a r c h ) ，该算法使 6 ， 第1 章绪论 用了长度动态变化的禁忌表，在生成部分路线后就开始进行禁忌搜索。实践证明， t s 是一种局部搜索能力很强的全局迭代寻优算法。但是t s 也有明显的不足。最 显著的一点就是t s 对初始解有较强的依赖性，初始解的好坏极大地影响着算法 的收敛速度。 遗传算法( g a ) 最早由h o l l a n d 提出。g a 是基于“适者生存”的一种高度 并行、随机自适应搜索算法，它将问题的求解表示成“染色体”的适者生存过程， 通过“染色体”群的一代代不断进化，包括复制、交叉和变异操作，最终收敛到 “最适应环境”的个体，从而求得问题的最优解或满意解。m a l m b e o r g i 】”、o c l f i 和l u i z 15 1 ，l o u i s 16 1 ，b a k e r 1 7 1 等人利用遗传算法对v r p 进行求解。国内的姜大 立【1 8 】、李军1 1 9 1 等人也研究了使用遗传算法求解v r p t w 。通过大量的研究，显示 了g a 在求解v r p t w 时具有突出的优越性。这主要体现在：算法进行全局并行 搜索，并将搜索重点集中于性能高的部分，从而能够提高效率且不易陷入局部极 小。当然，g a 在求解v r p t w 上的应用尚处于起步阶段，还存着很多不足，尤 其是早熟现象，这就需要对g a 进行进一步的研究改进。 2 0 世纪9 0 年代，意大利学者m d 嘶g o ，v m a n i e z z a o ，a c o l o m i 等人从生物 进化的机理中受到启发，通过模拟自然界蚂蚁寻食的行为，提出了一种全新的模 拟进化算法：蚁群算法。b e l l 和l m c m u l l e n e 2 0 】将蚁群算法应用于求解v i 冲。总的来 说，目前蚁群算法在t s p 上的应用日趋成熟，但在v r p 上的应用还比较少见。 神经网络的发展，也促进了v r p 的较好解决，但在v r p 中的应用还刚刚开 始，主要从事该算法研究的有t o r k i 和a b d o l h a m i d l 2n j 等人。 上面这几类启发式算法其划分常不是绝对的，有的方法同属于好几类。由 于v r p 问题的复杂性，使各种算法的比较很困难。 1 4 课题来源及主要内容 本课题来源于北京市科学技术委员会的项目“北京市商用车辆运营管理关键 技术及示范工程”( h 0 2 0 6 2 0 3 4 0 2 9 0 ) 和北京工业大学交通工程重点实验室开放 课题( k p 0 2 叭2 0 0 3 8 0 ) 。 本论文主要对有时间窗的车辆路径问题( v r p t w ) 和集送一体化的车辆路 径问题( v r p p d ) 进行了研究。论文的组织结构如下： 第2 章介绍车辆路径问题的基本理论及求解算法理论，包括启发式算法与遗 传算法。第3 章分别介绍基于启发式算法和遗传算法求解有时间窗的车辆路径问 题的实现，并对两种算法的求解结果进行分析。在第4 章，着重介绍了基于遗传 算法求解集货和送货一体化的车辆路径问题的实现。最后给出论文的结论和展 望。 7 北京工业大学工学硕士学位论文 第2 章车辆路径问题的基本理论 车辆路径问题( v r p ) 是一个典型的组合优化问题，也是一个典型的n p 难 题。对于这类问题，使用启发式算法进行求解是一个合理的选择。本章简要介绍 了组合优化问题理论和算法复杂性概念，并阐述了启发式算法和遗传算法的基本 理论。 2 1 组合优化问题 由参考文献【2 2 】可知，组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过对数学 方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学 ( o p e r a t i o n sr e s e a r c h ) 中的一个经典且重要的分支，所研究的问题涉及信息技术、 经济管理、交通运输、通信网络等诸多领域。 个组合优化问题仃由三部分组成： ( 1 ) 实例集d ； ( 2 ) 对于一个实例d ，有一个有限的非空集合s ( ) ，s ( ，) 的元素称 为j 的可行解； ( 3 ) 对于每个可行解盯邵( ，) ，有个正整数c ( 盯) ，称为盯的值。 当口是最小化问题( 最大化问题) 时，如果口s ( ，) 使得对于所有的盯e s ( ，) ，有 c ( 盯) c ( 盯)( 或c ( 盯+ ) c ( 盯) ) 则称盯+ 是，的最优解。c ( 盯+ ) 称作，的最优解，记为o p t ( ，) 。 不失一般性，只要改变目标函数的符号，就可实现最小化问题和最大化问题 的相互转换。 2 2 算法及算法分析 2 2 1 算法 算法是能被机械地执行的动作( 或称规则、指令) 的有穷集合，一个动作的 一次执行称为一步。能够用算法来解的函数或问题称为可计算函数或可计算问 题。算法有五大特征。 ( 1 ) 输入。一个算法有零个或多个输入量，这些输入量是算法所要求的初 8 第2 章车辆路径问题的基本理论 始信息，它们取自某一特定的集合。 ( 2 ) 确定性。算法的每一步骤都必须有确定的含义，动作不能有二义性。 ( 3 ) 有限性。一个算法对任一合法输入都必须在执行有限步后终止。 ( 4 ) 输出。一个算法有一个或多个输出信息，它们常是同输入信息有特定 联系的量。 ( 5 ) 可执行性。指算法中的所有动作必须是相当基本的，也就是说，每一 步至少在原理上能由人在有限的时间内用笔和纸来完成。 计算机技术的发展，促进了问题的数值解法、模拟技术和信息处理技术的发 展。人们普遍认为，今日的科学技术的需要已超出了现有计算机的能力。计算机 只能执行算法，也就是说，它能准确和全面地识别和执行一系列的指令，而这些 指令是用于求解严格确定的可计算问题的。 2 2 2 算法分析 算法分析是对算法性能的讨论，它的目的是对同一问题的各种可实现的算法 进行比较，对它们的性能作出定量的判断。同时，可确定算法是否存在什么性能 上的限制，如难易程度、最好的下界、最坏情况下和平均意义下的性态等等，给 算法设计提供理论上的指导。 对算法的评价有许多标准，如清晰性、可读性、易修改、易排错等，它们属 于结构化程序设计的讨论范畴。在算法分析中，主要是研究完成算法所需要的运 行时间和占用的空间。 由于有些优化算法所需的计算时间和存储空间难以承受，因此算法可解的问 题在实践中并不一定可解。如对称t s p 问题，可能路径为( n 1 ) ! 2 ，若以路径 比较为基本操作，则需( n 1 ) ! 2 1 次基本操作。对于每秒执行一百万次操作的 计算机，当n = 2 0 时就需1 9 2 9 年才能找到最优解。所以，我们必须对计算复杂 性理论有所了解，这也是最优化的理论基础。只有了解所研究问题的复杂性，才 能有针对性地设计算法，进而提高优化效率。 算法的时间和空间复杂性对计算机的求解能力有重大影响。算法对时间和空 间的需要量称为算法的时间复杂性和空间复杂性。问题的时间复杂性是指求解该 问题的所有算法中时间复杂性最小的算法的时间复杂性，问题的空间复杂性也可 类似定义。按照计算复杂性理论研究问题求解的难易程度，可把问题分为p 类、 n p 类和n p 完全类。 算法或问题的复杂性一般表示为问题规模 ( 如t s p 问题中的城市数) 的函 数，时间复杂性记为t ( h ) ，空间复杂性记为s ( ”) 。在算法分析和设计中沿 用实用性的复杂性概念，即把求解问题的关键操作，如加、减、乘、比较等运算 ，9 北京工业大学工学硕士学位论文 指定为基本操作，算法执行基本操作的次数则定义为算法的时间复杂性，算法执 行期间占用的存储单元则定义为算法的空间复杂性。在分析复杂性时，可以求出 算法的复杂性函数p ( n ) ，也可用复杂性函数主要项的阶p ( p ( ，? ) ) 来表示。 若算法爿的时间复杂性为乃( h ) = o ( p ( 撵) ) ，且p ( 行) 为”的多项式函数， 则称算法a 为多项式算法。时间复杂性不属于多项式时间的算法统称为指数时间 算法。 当输入规模不断增大时，任意一个多项式算法终将变得比任一指数算法更有 效。多项式算法的另一个特色是：在某种意义上它很好地利用了技术发展的优点。 另外，多项式算法有较好的“闭”性：即几个多项式算法可以结合起来解同卜 问题的某些特殊情形：一个多项式算法也可以利用另一个多项式算法作为其“子 程序”，并且最后的结果仍是多项式算法。 有少数最坏情况下复杂度为指数函数的算法，在实践中证明是有效的算法， 如线性规划中的单纯形算法就是一个突出的例子，它有指数时间复杂度，可是实 践表明其运行时间相当快，其奥秘在于这些算法的平均性态良好。因此，在具体 选择算法时，应根据算法的时间和空间复杂度，结合具体因素( 如问题大小、机 器容量、平均性态等) ，选择使用好的算法。 2 2 3n p 难题 n p 是n o n d e t e r m i n i s t i cp o l y n o m i a l 的缩写，即非确定型的多项式算法的意思。 2 2 3 1p 类问题与n p 类问题一个问题的判定过程可形式地描述如下：己知 l o ，1 ) ，对于x o ，1 ) ，若x l ，则给出答案“是”：若x 茌l ，则给出答案 “非”。 o ，1 指的是由有限个0 和l 组成的符号串集合。 按照判定问题的复杂性对最优化问题进行分类。问题复杂性的形式定义可用 图灵机( t u r i n g m a c h i n e ) 计算模型给出。如果一个问题有解它的多项式时间d i m