（计算机软件与理论专业论文）有车辆数限制的多起点开放式车辆路线问题.pdf

中山大学硕_ ：学位毕业论文有车辆数限制的多起点开放式车辆路线问题 有车辆数限制的多起点开放式车辆路线问题 专业：计算机软件与理论 硕士生：黄志钢 指导老师：郭嵩山教授 摘要 交通运输是国民经济的动脉，它对人民生活和社会经济发展起到了极大的作 用。各种运输方式都要遇到同一个问题：在有效地的服务客户前提下，怎样去减 少总的费用。 本文研究的问题是有车辆数限制的多起点开放式车辆路线问题 ( m o m d v r p ) ，浚问题是车辆路线问题( v r p ) 的一个较新的分支。在本文中，作 者提出了一种新的求解m o m d v r p 问题的思路，即把求解过程分成两个阶段。 第一个阶段对m o m d v r p 问题求解有车辆数限制多起点车辆路线问题 f m m d v r p ) ，得到按照车场中心分组的客户群；第二个阶段对分组后的客户群 分别求解有车辆数限制的开放式车辆路线问题( m o v r p ) ，求出每辆车的行驶路 线。作者采用禁忌搜索算法来求解r a o m d v r p 问题。在传统的禁忌搜索算法的 基础加入了多初始解、动态禁忌长度等改进方法，提高最终解的质量。实验结果 表明，本文提出的思想很好的解决了m o m d v r p 问题。 关键词：有车辆数限制的多起点开放式车辆路线问题禁忌搜索动态禁忌 长度多初始解 ! 坐查堂堡! ：堂竺望些堡塞 塑芏塑垫坚型竺兰整皇茎垫壅芏塑堕丝塑望 o p e nv e h i c l er o u t i n gp r o b l e mb ym u l t i p l ed e p o t s w i t hl i m i t e dn u m b e ro fv e h i c l e s m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：h u a n gz h i g a n g s u p e r v i s o r ：p r o f e s s o rg u os o n g s h a n a b s t r a c t p l a y i n ga ni m p o r t a n tr o l et ot h en a t i o n a le c o n o m y , t r a f f i co rt r a n s p o r t a t i o n p r o m o t e sd e m o t i cl i v i n gl e v e la n dt h ed e v e l o p m e n to fs o c i a le c o n o my v a r i e s t r a n s p o r tm a n n e r sf a c e st h es a m ep r o b l e m ：h o wt od e c r e a s et h et o t a lc o s ti nt h ec a s e o fs e r v i n gc u s t o m e re f f e c t i v e l y ? t h ep u r p o s eo ft h i sp a p e ri st or e s e a r c ho no p e n i n gv e h i c l er o u t i n gp r o b l e mb y m u l t i p l ed e p o t sw i t hl i m i t e dn u m b e ro fv e h i c l e 佃o m d v r p ) t h i si san e wb r a n c h o fv e h i c l er o u t i n gp r o b l e m s ( v r p ) i nt h i s p a p e r , t h ea u t h o rp u tf o r w a r dan e w m e t h o dt os o l v et h ep r o b l e mo fm - o m d v r p t h e p r o c e s sc a nb ed i v i d e di n t ot w o s t e p & i nt h ef i r s ts t e p ，c u s t o m e r sc a l lb ec a t e g o r i z e di n t og r o u p sa c c o r d i n gt ot h e v e h i c l ec e n t e rs t a t i o nb ys o l v i n gm m d v r ei nt h es e c o n d ，e v e r yc a r sd r i v i n gr o u t e i sg e ta f t e rs o l v i n gm o m d v r po ne a c hg r o u p s e p a r a t e l y h e r e ，t a b us e a r c h a r i t h m e t i cw a sa d o p t e dt os o l v em - o m d v r eo nt h eb a s i so ft r a d i t i o n a lt a b us e a r c h ， w ea d dm u l t i p l ei n i t i a ls o l u t i o n ，d y n a m i ct a b ul e n g t ha n de t cw h i c hi m p r o v et h e q u a l i t yo fl a s ts o l u t i o n t h ee x p e r i m e n tr e s u l ts h o w st h a tt h en e wm e t h o ds o l v e s m 一0 m d v r p c o m m e n d a b l y k e yw o r d s ：m - o m d v r p ( o p e nv e h i c l er o u t i n gp r o b l e mb ym u l t i p l ed e p o t s w i t hl i m i t e dn u m b e ro fv e h i c l e s ) t a b us e a r c h d y n a m i ct a b ul e n g t h ( d t l ) m u l t i p l ei n i t i a ls o l u t i o n ( m i s ) ， i i 中山大学硕= l 学位毕业论文 第1 章绪论 第1 章绪论 1 1 选题背景和研究意义 交通运输是国民经济的动脉，它对人民生活和社会的经济发展起到了极其重 要的作用。伴随着全球经济一体化的进程，作为“第三利润源泉”的物流，其作 用和地位，就显得比任何时候更为重要和突出，对经济活动的影响也同益明显。 根据美国物流研究委员会统计峨美国、开本等经济发达国家的物流成本占国民 经济成本的比重在1 0 左右。调查显示国内目前与物流相关的总支出有1 9 0 0 0 亿元 人民币，物流成本占g d p 的比重为2 0 左右，有的商品甚至高达6 0 一7 0 ，如 果利用第三方物流的方式，企业的成本可以降低1 0 。中国仓储协会对1 4 0 多个 企业的调查i ”，运输的费用占整个物流费用的比例如下：在生产企业成品物流中 占7 3 ，在商品企业物流中占5 2 ，在生产企业原料物流中占5 8 。由于运输在 社会经济活动中的如此重要，研究于运输相关的车辆路线问题就是一件很有意义 的事情。 当前的物流业虽然运输方式多种多样( 铁路、公路、水运、和航空等) 。但它 们都要面对一个共同的问题：如何更有效的使用运送工具来传送各站点间的货物 和旅客，如何更准确的做至l j 7 r ( r i g h t p r o d u c t ，r i g h t q u a l i t y ，r i g h t t i m e ，r i g h t p l a c e ， r i g h tc o n d i t i o n ，r i g h tc u s t o m e r ，r i g h t c o s t ) 【3 j 。因此设计合理、有效的车辆路线方案， 尽量减少车辆数量和配送路程就成为非常实际的问题。 车辆路线问题( v e h i c l er o u t i n g p r o b l e m v r p ) 在二十世纪的五十年代末期， 由d a n t z i g 和r a m s e r 提出以来，就成为了网络优化问题中最基本的问题之一， 此后，关于v r p 类问题的研究就一直非常系统地进行着。以下三个方面的原因 促成了许多人对v r p 类问题的研究：第一是问题本身来源于实际，由于其应用 的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注；第二是问题的 学术研究非常有意义，v r p 类问题大多数都是n p h a r d 类问题，该类问题不存 中山大学硕士学位毕业论文第1 章绪论 在一个多项式时间的算法，因此解决该类问题要做的是在合理的时间内得到一个 尽可能优的解，这样要充分利用问题本身的限制来改进算法，有时候，在一个问 题提出的算法改进思想可以扩展到其他的n p h a r d 问题中，这样对其他的问题的 研究可以产生帮助：第三v r p 的分支非常多，因为实际问题本身存在不同的限 制条件，源于实际问题的v r p 自然也就有了各种各样有意义的分支，而各分支 之间的解决方案有时候可以互相借鉴，从而促进各个分支的共同发展。 1 2 本文研究的主要内容 本文要研究的问题是车辆路线问题的一个分支一有车辆数量限制的开放式 多起点车辆路线问题m o m d v r p ( o p e nv e h i c l er o u t i n gp r o b l e mb ym u l t i p l e d e p o t sw i t hl i m i t e dn u m b e ro fv e h i c l e s ) 。该问题是开放式车辆路线问题( 0 v r p ) 和多起点车辆路线问题( m d v r p ) 的一个混合问题。在o v r p 中，所有的车辆必 须从车场中心( d e p o t ) 出发，行进在给定的路线上，以某种形式服务一组客户。 o v r p 类问题中，出发的车辆最后不用回到车场中心。客户和客户之间、中心和 客户之间既有一定的距离，也赋予一定的费用。每一个客户都只能被访问一次， 也就是只能是其中的一辆车为其提供服务。每辆车的运送能力都有一个上限，我 们称为最大承载量或容量( c a p a c i t y ) 。在现实生活中，我们可以把容量看成是重 量或体积上的要求。另外，每个客户的需求也是可以被量化的，我们称这个需求 为客户需求( c u s t o m e rd e m a n d ) 。中心点只有一个。如果中心点的数量不止一个， 我们就称该类问题为多起点的v r p 问题。本文研究的m o m d v r p 问题既具有 0 v r p 中出发的车辆最后不用回到车场中心这个特点，又具有m d v r p 中车辆中心 不唯一这个特点，因此浚问题有一定挑战性。 文章的组织结构如下： 第1 章是绪论； 第2 章叙述本文的研究背景及其意义，并对本文研究的对象作了简单介绍； 第3 章介绍了禁忌搜索算法的思想； 第4 章给出了求解m o m d v r p 的算法和实验结果。 第5 章对本文的总结。 中山大学硕：l 学位毕业论文 第2 章车辆路径问题概述 第2 章车辆路径问题概述 2 1 车辆路径问题的描述 车辆路径问题在现实生活中是十分普遍的一种调配问题，特别是对于有大量 服务对象的实体，例如一个拥有成百上千客户( 顾客) 的公司。对于此类问题的解 决，关键在于如何对车辆进行调度，如何安排每辆车的行进路线，才能使总费用 最小。在配送业务中，配送车辆调度问题涉及很多方面，需要考虑的因素也比较 多，例如车辆的承载能力、客户对送货时间的要求、客户之问的距离等等。车辆 路线问题自上世纪五十年代提出来后，很快引起了应用数学、图论与网络分析、 运筹学、计算机应用、物流科学等学科的专家与运输计划制订者和管理者的极大 重视，成为了组合优化领域和运筹学的前沿与研究热点问题。在实际的生活和生 产中，车船调度问题、邮政投递问题、管道铺设问题、计算机网络拓扑设计问题、 电力调度问题、公路铁路网铺设问题等都可以抽象为车辆路线问题。可见，研究 车辆路线问题具有重要的理论和现实意义。 v r p 的一般描述是：对一系列给定的客户( 送货点或取货点) ，设计适当的配 送车辆行驶的路线，使其从配送中心出发，有序的经过他们，最后回到配送中心， 并满足一定的约束条件( 如货物需求量、发送量、车辆载重量、交发货时间、行 驶里程限制、时间限制等等) 下，使总运输成本达到最小( 如费用最少、车队规模 尽量小、车辆利用率尽量高、车辆行驶时间最短或车辆行驶里程最短等) 。其中， 通常把最小的车辆数作为第一目标，而最低的行驶成本作为第二目标。它的特点 在于：顾客群体通常比较大，一条路径往往满足不了顾客的需求，也就是说，它 涉及了多辆配送车辆的服务对象选择和路径( 服务顺序) 确定两个方面问题。参见 图2 1 。 中山大学硕十学位毕业论文第2 章车辆路径问题概述 图2 - 1车辆路径问题不意图 下面从几个方面来大概描述车辆路径问题的特点【。 ( 1 ) 道路网 用来运送货物的道路网通常用个图来表示，其中，图中的弧线表示路段， 而点表示道路的交叉点、客户和车场( 配送中心) 。根据道路是单线还是双线， 对应的弧线可以分为无向弧和有向弧。每条弧线对应着一个量化了的费用f 通 常表示其距离、或运行时间1 。 ( 2 ) 车场 车场是用道路图中的点表示。用来服务客户的车辆的行驶路线都开始并终 止于一个车场。每个车场的特征通常是由所配备的车辆的种类和数量、所能处 理的货物总量表示。 ( 3 ) 客户 客户也是用道路图中的表示；客户需要发送或收取货物，并且每个客户的 要求发送或收取的货物的品种不同；在某类问题中，客户对提供的服务有时问 要求( 时间窗，例如有些客户只在9 ：0 0 1 1 ：3 0 这个时间段内营业等) ；通常情 况在对客户提供服务时( 例如卸货或装货) 所花费的时间是不在考虑之列；有 时，每个客户的需求不可能全部得到满足。在这种情况下，有两种处理方式， 一种是每个客户运送或收取的货物量可以减少，或者是一部分客户得不到服 务。为了处理这类情形，可以引入相应的优先权或惩罚。 ( 4 ) 车辆 中山大学硕：e 学位毕业论文第2 章车辆路径问题概述 车辆有如下特征：车辆配属车场，完成任务后车辆是否要求返回配属车场； 车辆通常有最大容量限制( 如最大的载载重量、或容积等) ；每辆车都有使用费 ( 单位距离、单位时问等) 。 ( 5 ) 车辆运行路径编排中的限制条件 在安排车辆行驶的路线时，应满足货物性质、客户要求和车辆的特点等限 制条件。例如，在每条线路上，相应的车辆的当前装载量不能超过车辆的最大 载重量：客户对服务的要求可能也有所不同，如客户只要求送货，或只要求取 货、或两者兼有，或者客户对提供的服务有时间窗的要求，只能在客户工作的 时间段内给客户提供服务。访问客户的顺序要求可以作为先后次序限制，有一 种类型的次序限制是要求同一线路上的某一给定的客户要先服务于另一组其 他给定的客户，因此该客户必须在该组客户之前被访问。例如在一个车队即要 给用户发送货物，又要从工厂运输产品到车场中心，这样在给车辆安排运行路 线时就要把用户的访问安排在工厂的访问之前，如果两者的访问次序颠倒了， 车队就不能完成预期的目的。 ( 6 ) 行驶费用和行驶时间 为了评价一组配送线路的总费用和检查其相应的运营限制，必须知道客户 与客户之问，车场与客户之间的行驶时间和行驶费用。在道路图中，对于图中 的每一点对i 和j ，定义一条弧线( j ，j ) ，其费用c 。等于图中从点i 到点j 的最 短路径的费用，行驶时间t i 则为图中从点i 到点j 的最短路径上各条弧线的行 驶时间之和。 ( 7 ) 目标 车辆路径问题需要考虑几个目标： 最小化总的运输成本。总运输成本取决于所使用的车辆有关的固定费 用、服务所有客户所需要的车辆数和总的行驶距离( 或总的行驶时间) ； 最小化与客户不完全服务等有关的惩罚值： 合理安排各线路上的车辆总的载重量和行驶时间，使的各条路线上的车 辆总的载重量和行驶时间趋于一致。 中山大学硕士学位毕业论文 第2 章车辆路径问题概述 2 2 车辆路径问题的研究现状 上个世纪五十年代末期由d a n t z i g 和r a m s e r n 通过描述把汽油送到不同加 油站的实际问题，第一次提出了v r p 问题，并给出了相应的数学模型以及求解 算法。当时，车辆调度问题主要是集中在静态的车辆调度问题上，描述的是一个 运筹学中的优化问题。到1 9 6 4 年c l a l k e 和w t i 叠h t 【6 j 提出了一种对 d a n t z i g - r a m s e r 方法进行有效改进的启发式算- - c l a r k e w r i g h t 节约算法。随着 数学规划和网络分析的发展，上个世纪的七八十年代人们提出了基于数学规划解 决这一问题的精确算法。到了上个世纪九十年代，人工智能的发展进一步促使了 车辆路线问题算法的研究，如模拟退火算法、遗传算法、禁忌搜索等智能算法。 f i s h e r 7 j 将车辆调度问题研究分成三个阶段。第一个阶段是从v r p 问题首次提出 年到1 9 7 0 年，在这个阶段算法多数注重针对具体问题的车辆安排方案，没有或 者是不太注意路径长度或者费用的最小化，而且处理的客户规模通常比较小，可 移植性较差。这个阶段通常称为古典的运输调度问题研究阶段。第二个阶段是从 1 9 7 0 年到1 9 9 0 年，为基于数学规划或网络分析的运输调度问题的研究阶段。在 这一个阶段中因为数学规划和网络分析有了一定的发展，人们丌始用数学规划和 网络的最大流和最小流来研究运输调度问题。这个阶段的算法是精确的，属于以 数学规划为主的启发式解法。第三个阶段从1 9 9 0 开始到现在，为基于智能算法 的运输调度问题的研究阶段。智能算法可移植性强，能在合理的时间内给出问题 的较好解，并且智能算法能处理规模比较大的运输调度问题。在第三个阶段，产 生了许多智能算法。 国外对v r p 类问题有长达半个世纪的研究，涌现出了很多很有价值的相关 文献。早在1 9 8 3 年，b o d i n 等在t s l 对v r p 的研究进行了综述，列举了6 9 9 篇 相关的参考文献。2 0 0 2 年，p a o l ot o t h 和d a n i e l e v i g o 9 q hv r p 的最新研究进 展和发展趋势进行了全面的分析。相比较，国内对v r p 的研究就较少，但最近 几年涌现出一批质量较高的研究成果，如李志业在第1 7 届i e a a i e 2 0 0 4 提出 的用改进的g r a s p 算法和禁忌搜索解决v r f r w 问题。通过世界各个国家的众 中山大学硕士学位毕业论文第2 章车辆路径问题概述 多研究人员的共同努力，经过几十年的研究发展，车辆路线问题研究已经取得了 大量成果，提出了许多不同类型的v r p 的分支以及相应的模型和各种有效的算 法。下面从车辆路线问题的现有研究型态( 车辆路线问题的分支) 和求解方法两个 方面介绍车辆路线问题的研究现状。 2 3 车辆路线问题型态 由目标或约束的不同，车辆路线问题主要有以下几个分支：经典旅行商问 题( 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 ) 、最短路径问题( s h o r t e s tp a t hp r o b l e m ，s p p ) 、 车辆路线问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 、带容量约束的车辆路线问题 ( c a p a c i t a t e dv e h i c l er o u t i n gp r o b l e m ，c v r p ) 、带时间窗的车辆路线问题( v e h i c l e r o u t i n gp r o b l e mw i t h t i m ew i n d o w s ，v r p t w ) 、配送问题( p i c k u pa n dd e l i v e r y p r o b l e m ，p d p ) 、多中心点车辆路线问题( m u l t i p l ed e p o tv e h i c l er o u t i n gp r o b l e m ， m d v r p ) 、优化约束车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t hp r e c e d e n c e c o n s t r a i n t s ，v r p p c ) 、相容性约束车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t h c o m p a t i b i l i t yc o n s t r a i n t s ，v r p c c ) 、随机需求车辆路线问题( v e h i c l er o u t i n gp r o b l e m w i t hs t o c h a s t i cd e m a n d ，v r p s d ) 、中途可以装载货物的车辆调度问题( v e h i c l e r o u t i n gp r o b l e mw i t hp i c k - u pa n dd e l i v e r i n g ，v r p p d ) 、开放式的车辆路线问题 ( o p e nv e h i c l er o u t i n gp r o b l e m ，o v r p ) 、有时问窗和车辆数限制的车辆路线问题 ( v e h i c l er o u t i n gp r o b l e mw i t hb o t h t i m ew i n d o wa n dl i m i t e dn u m b e ro fv e h i c l e s ， m v r p t w ) 等等。 本文要研究m o m d v r p 问题是m d v r p 问题和o v r p 问题的混合问题，在 下面章节中，将简略对这两类问题进行介绍。 2 3 1m d v r p 问题的介绍 随着经济的迅速发展，运输问题的重要性日益显著，研究与运输相关的车辆 路线i b i s ( v e h i c l er o u t i n gp r o b l e m ，v r p ) 的文献也越来越多。一般意义上的v r p 问题只考虑了只有唯一车场中心的情况，而实际运用中，通常要考虑车场不唯一 的情形。例一某种原料有m 个产地，现在需要将原材料从产地运往n 个使用这 7 中山大学硕二l 学位毕业论文 第2 章车辆路径问题概述 些原材料的工厂。假定m 个产地的产量和n 家工厂的需要量已知，单位产品从 任一产地到任一工厂的费用已知，那么如何安排运输方案可以使总运输成本最 低? 例二随着现代商业的发展，许多大型商业企业均建立了多配送中心，那么如 何安排配送车辆的行进路线使得运输费用最低? 多车场的车辆路线问题 ( m u l t i p l e d e p o tv e h i c l er o u t i n gp r o b l e m ，m d v r p ) 就是基于这样的实际背景提出 的优化问题。自问题被提出以来，相关的文献就不断涌现，其研究结果以广泛的 应用于物资调配系统，运输系统等。 2 3 1 1m d v r p 问题的描述及特点 多车场车辆路径问题描述具体如下 1 l 】：有m 个车场中心，各自扪j 有容量为 q 的车辆k 。( i n = 1 ，m ) 辆，负责对n 个用户进行货物分送工作，用户i 的货物 需求为g 。( i - 1 ，n ) ，且g 。 经典启发式算法 中山大学硕士学位毕业论文 第2 章车辆路径问题概述 1 9 6 0 年到1 9 9 0 年，提出的启发式算法都是基于经典启发式算法的思想之 上。经典启发式算法主要有以下几类：先聚集后路线f c l u s t e rf i r s t r o u t i n g s e c o n d ) 、先路线后聚集伽 ( r o u t i n gf i r s t c u s t e rs e c o n d ， 如最短路径法、 集划算法、集覆盖算法、匹配算法等) 、拉格朗日松弛法 2 1 1 ( l a g r a n g e r e l a x a t i o n a p p r o a c h ) 、改进与交抉法k 2 】( i m p r o v e m e n ta n de x c h a n g e ) 等。 智能算法 1 9 9 0 年后，智能算法在解决组合优化问题上显示了强大的功能，很多研究 人员把智能算法引入到车辆调度问题的求解中，如遗传算法( g e n e t i c a l g o r i t h m ，g a ) 【2 3 】f 2 4 】 、模拟退火算法( s i m u l a t e da n n e a l i n 曲【”l 矧、 禁忌搜索算法( t a b us e a r c h ) 2 8 2 9 】【3 0 、蚁群算法( a n tc o l o n ya l g o r i t h m ) 3 1 3 2 】【3 3 等和它们的各种变异形式的算法。 并行算法 现在国内外所提出的并行算法都是基于一种启发式算法，如插入算法、节 约算法等。很多的研究人员都运用并行算法求解车辆调度问题d s 】 3 6 】 3 7 】 3 ”。因为并行算法所具有的独特优越性，它将成为未来研究车辆调 度问题的一个重要的研究方向。 启发式算法得到的解虽然不是最优的，但启发式算法能在较短的时间内对一 个规模比较大的实际问题给出一个满意解，来满足实际的应用需要。启发式算法 的这一特性使得它的研究比优化算法更加活跃。本文中是利用禁忌搜索这一启发 式算法来研究车辆线路问题，在后续章节将对禁忌搜索进行简单介绍。 中山大学硕士学位毕业论文第3 章禁忌搜索算法概述 第3 章禁忌搜索算法概述 本文是利用禁忌搜索算法( t a b us e a r c h ，t s ) 研究m o m d v r p 问题。下面对 禁忌搜索进行一些简单的介绍。 3 1 禁忌搜索的概述 禁忌搜索算法是局部领域搜索算法的推广，是一种全局性领域搜索算法，模 拟人类具有记忆功能的寻优特点，是人工智能在组合优化算法的一个成功应用。 t s 是由g i o v e r b ，】在1 9 8 6 年首次提出，进而形成一套完整算法，见文献【4 1 1 。 禁忌搜索算法通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索，并通过 破禁忌水平来释放一些被禁忌的优良状态，进而保证多样化的有效搜索，来实现 全局优化的结果。禁忌搜索算法的特点是采用了禁忌技术，所谓禁忌就是禁止重 复前面的工作。为了回避局部邻域搜索陷入局部最优点，在下一次搜索中，利用 禁忌表记录下已经到达过的局部最优点不再或有选择的搜索这些点，以此来跳出 局部最优点【4 2 j 。 迄今为止，t s 算法在组合优化、生产调度、电路设计、机器学习、神经网 络等领域广泛应用并取得很大成功，近年来又在应用于函数全局优化方面得到较 多的研究，并体现它强劲的功能 4 2 1 。下面将介绍禁忌搜索的原理、算法细节与 禁忌搜索算法的收敛性等内容。 3 2 禁忌搜索的基本思想 禁忌搜索是人工智能的一种体现，禁忌搜索算法最重要的思想是记住以往已 经搜索过的局部最优解的一些对象，并在以后的迭代搜索中尽量避开这些对象 ( 也不是绝对禁止) ，从而避免了陷入局部最优解，能把搜索的空间拓展到全局， 进而使得搜索途径多样化。 中山大学硕二i ：学位毕业论文第3 章禁忌搜索算法概述 禁忌搜索的基本思想如下：确定一个初始可行解，初始可行解可以是从启发 式算法中获得或者是在所有可行解中随机挑选的。然后确定该初始解的一个邻 域，从当前邻域中确定若干候选解，若最佳候选解对应的目标值优于当前的最优 解，则用其代替当前解，并将相应得对象加入禁忌表，同时修改禁忌表中各对象 的存在时间。然后重新搜索其邻域。如果邻域不存在上述的候选解，则选择候选 解中非禁忌的最优状态替代当前解，同样把它加入到禁忌表中，并修改禁忌表中 各对象的存在时间。重复上述搜索过程，直到满足停止准则。图3 - 1 为禁忌搜索 算法的基本流程图。 叫掉法姑柬，亭l _ 输m 优化结米 耕用当前邻域产生邻域解井从， j 确定若。f 候进解 中粼篱渊揪黼 判断候选解中对应各埘霉的属性 选择候圭解鳃中非繁忌埘霉对应的最佳状态为新的当前解 同时与之对应的蔡总对象替代皿早进八禁忌表1 i 勺对象元素 图3 - 1 禁忌搜索算法流程图 3 3 禁忌搜索算法细节 禁忌搜索算法涉及到邻域( n e i g h o r h o o d ) 、适配值函数、禁忌表f t a b ul i s t ) 、 禁忌长度( t a b ul e n g t h ) 、禁忌对象f r a b uo b j e c t s ) 、候选解- ( c a n d i d a t e ) 、藐视准则 中山大学顶：i ：学位毕业论文第3 章禁忌搜索算法概述 ( a s p i r a t i o nc r i t e r i o n ) 、终止准贝1 ( t e r m i n a t ec r i t e r i o n ) 等概念。 禁忌搜索是在邻域搜索的基础上，通过设置禁忌表来禁忌一些已经有过的操 作，并利用藐视准则来奖励一些优秀状态。对禁忌搜索算法性能影响比较大的关 键因素主要有邻域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等。 需要强调的是；1 4 2 j 由于t s 是局部邻域搜索的一种扩充，因此邻域结构的设计很关键，它决 定了当前解的邻域解得产生形式和数目，以及各个解之间的关系。 为了改善算法的优化时间性能的考虑，若邻域结构决定了大量的领域解， 特别是对于大规模问题，则可以尝试部分互换的结果，而候选解也只取 其中的少量较佳状态。 邻域移动是从当前解产生另一个解( 新解) 的途径，它是保证产生好的解和 算法搜索速度的最重要的因素之一。邻域移动定义的方法有很多，对于 不同的问题应采用不同的定义方法。 禁忌表是禁忌搜索算法的核心，禁忌表的大小在很大程度上影响着搜索 速度和解的质量。如果选择的好，可有助于识别出曾搜索过的区域。如 果禁忌表规模过小，那么搜索过程就可能进入死循环，整个搜索将围绕 着相同的几个解徘徊。相反，如果禁忌表规模过大，那么它将在相当大 程度上限制搜索区域，好的解就有可能被跳过去，而且，不会改进解的 效果反而增加算法运行时间。因此一个好的禁忌表规模应该是尽可能小 却又能避免算法进入循环。禁忌表还有一个重要的作用就是通过调整其 大小使搜索发散或收敛。初始搜索时，为了提高解的分散性，扩大搜索 区域，使搜索路径多样化，经常希望禁忌表规模小；相反，当搜索过程 接近最优解时，为提高解的集中性，减少分散，缩小搜索区域，这时通 常希望禁忌表规模大。 禁忌长度是禁忌搜索算法的一个很重要的参数，对应不同的禁忌长度， 同一个算法会得到明显不同的结果。禁忌长度直接影响整个算法的搜索 进程与行为。 禁忌对象就是置入禁忌表中的那些元素，而禁忌的目的就是为了尽量避 免迂回搜索，陷入局部最优解的陷阱，从而能探索到新的领域，从而达 中山大学硕：卜学位毕业论文笫3 章禁忌搜索算法概述 到全局最优。 选择策略既择优规则，是对当前的邻域移动选择一个移动而采用的准则。 一个好的选择策略因该是既保证解的质量又保证计算速度。当前采用最 广泛的两类策略是最好解优先策略( b e s ti m p r o v e ds t r a t e g y ) 和第一个改进 解优先策略( f i r s ti m p r o v e ds t r a t e g y ) 。 藐视准则是为了避免优秀状态的遗失，激励对优良状态的局部搜索，进 而实现全局优化的关键步骤。在禁忌搜索算法中，可能会出现候选解全 部被禁忌，或者存在一个优于当前最优状态的禁忌候选解，此时藐视准 则将使得某些状态解禁。衡量藐视准则标准就是定义一个破禁水平函数。 破禁水平函数选取通常基于以下两个准则：基于适值的准则( 若某个禁忌 候选解的适值优于以往搜索最优解，则解禁此候选解为当前解) ，基于搜 索方向的准则( 正按有效的搜索途径进行) 。 对于非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅 考虑其中最佳状态为下步决策，如此可实现对局部极小的突跳。 为了使算法在一个合理的时问内能给出可满足解，必须设置一个合理的 终止准则来结束整个搜索过程。终止准则的设计通常采用如下准则 ( 1 ) 给定最大迭代步数； ( 2 ) 设定某个对象的最大禁忌频率； ( 3 ) 设定适值的偏离幅度。 3 4 禁忌搜索算法的收敛性 迄今为止，禁忌搜索算法在许多领域得到了成功应用。尽管许多文献通过仿 真研究来探讨参数和操作对算法性能的影响，但其理论研究还远不完善。文献【4 2 j 针对一类在有限状态集下求极小值问题给出了收敛定理以及证明：若有限状态空 问由当前的邻域解集中的非禁忌或满足破禁忌策略的候选解集是连通的f 即任意 两个状态可通过有限步邻域搜索互达) ，且禁忌表的大小充分大，则禁忌搜索一 定能够到达全局最优解。然而，要使得禁忌表的大小充分大，即遍历所有状态， 显然在时间上是不能够接受的。同时，上述定理的证明是在禁忌准则和破禁忌策 中山火学硕：i ：学位毕业论文第3 章禁忌搜索算法概述 略的抽象意义上进行的，并没有指出算法操作对性能的具体作用，尤其没有涉及 到算法效率。因此在理论上操作和参数对算法性能的影响以及算法搜索效率有 待进一步研究，这也有助于丌发高效的禁忌搜索算法。 1 7 中山人学硕士学位毕业论文第4 章m o m d v r p 求解及其结果分析 第4 章m _ 0 m d v r p 求解及其结果分析 4 1m - o m d v r p 问题的描述及数学模型的建立 有车辆数限制的多车场车辆开放式路径问题的形式化定义如下：给定一个无 向图c ( v ，爿l y = 似，k ，k + 1 ，k + ，) ，其中k ( o c fs n ) 是客户，每个客 户有需求容量d 。和服务时 h i s 。：k 0c is n + m ) 是车场，每个车场拥有容量为q 的车辆k 。m = n + l ，n + m ) 辆；所有车场所拥有车辆的总数是k 。，；每辆车 的最长工作时间为w ；求这k 。，辆车最多能服务多少个客户。每辆车都从各自 所在的车场出发，并且车在服务完相应的客户后不需要返回所出发的车场，每辆 车服务的客户k 的需求总和罗d ，要小于等于车的最大载货量q 。每个客户k 最 多只能被一辆车服务( 有些客户不能被任何车辆服务) ，车辆的工作时间不能超过 其最长工作时间。图4 一l 是m - o m d v r p 的一个示例： 图4 - i 有车辆数限制的多车场开放式车辆路线问题 问题的目标是在使用墨。，( 有限的) 辆车的情况下，服务尽可能多的客户。作者针 中山大学硕： ：学位毕业论文 第4 章m o m d v r p 求解及其结果分析 对m o m d v r p 问题提出了如下的数学模型： x = 。1 勒椭车黑胤微到前 脚善n 再。n 善，丢k m 工 + 村 童篁z 尹 k m f ：m + 1 ，+ 2 ，j v + m 善荟z 尹 b m “，+ 2 ，一，+ m 篙羹弦s - 雄，- ) 篙薹妻班腓z ， 静知q m 篙：i 甜 黔- 鬻争。一m e 配 n ：? ，圳 薹弦) 岷s k 茹黔型肘) 0 表示从u 到”的距离。 其中式( 2 ) 代表目标函数，式( 3 ) 表示各车场派出车辆的数目不能超过该车场 拥有的车辆数；式( 4 ) ( 5 ) 保证每个用户最多被一辆车服务一次( 也可能不会被服 务) ；式( 6 ) 定义了车辆容量约束；式( 7 ) 表示车辆不能从车场到车场；式( 8 ) 确保 了每条路的行驶时间( 包括服务时间) 不会超出车辆的最大的工作时间w 上述m - o m d v r p 问题的数学模型是合理的。证明如下：用一个( + 1 ) x n 矩 阵记录一辆车的行驶路线，其中1 到n 表示客户，0 表示车场中心。如果从点i 到 点j 有行驶路线，则在矩阵坐标为( f ，j ) 标记为1 ，否则标记为0 。如果一个车场 中心有k 辆车，则可以用k 个( + 1 ) 矩阵记录每辆车的行驶路线。可以给这 k 个( + 1 ) x n 矩阵从1 到k 编号，表示该车场中心编号从1 到k 的车辆各自的 行驶路线。我们可以把这k 个矩阵按照编号从大到小依次叠放在一起，组成一个 中山大学硕= i ：学位毕业论文 第4 章m o m d v r p 求解及其结果分析 ( + 1 ) x n k 的立方体。该立方体就记录一个车场中心所有车辆的行驶路线。 如果有m 个车场中心，可以利用上述方法构造m 个立方体，分别记录每个车场 中心拥有的车辆的行驶路线。同样，可以给这m 个立方体从1 到m 编号，组成 一个m kx n ( n + 1 ) 立方体群。现在可以把数学模型和该立方体群做一个如 下的映射关系：如果车场m 。中编号为k ，的车从用户i 到用户，有行驶路径，则把 m x k x n x ( + 1 ) 立方体群中编号为m 。x k 。x i x ，的立方块涂黑：否则，不涂任 何颜色。现在问题转化成只要证明在对肘k nx ( n + 1 ) 超立方体涂黑的过程 中，不会出现涂黑立方块的再被涂黑的情况，则数学模型正确。涂黑的过程其实 就记录车辆行驶路线的过程。从m k nx ( n + 1 ) 超立方体建立的过程中，不难 发现，对任意一个车场中心所对应的( + 1 ) x n k 的立方体进行涂黑时，不会 影响到其他( j v + 1 ) n x k 的立方体；同样，同一车场中心的不同车辆对应的 ( + 1 ) 矩阵进行涂黑时，不会影响到其他( + 1 ) n 矩阵。这样可以得到这 样一个结论：任意一个单位立方块最多被涂黑一次。故可以说m o m d v r p 问题 的数学模型是正确的。 4 2 求解m - 0 m d v r p 算法思想 考虑到m o m d v r p 问题存在多个车场中心，作者在这里把m o m d v r p 问 题分成两个阶段来求解。第一个阶段把m o m d v r p 问题简化成每个车场中心只 有辆车的m m d v r p 问题，把客户按车场中心进行分组；第二个阶段对每个 分组后的客户群求解一次m o v r p 问题。作者在这里要指出的是：在第一个阶 段求解m m d v r p 问题时，每个车场中心只有一辆“车”，该“车”的最大行驶 时间比该车场中心所有车辆最大行驶时间总和稍大，最大承载容量比该车场中心 所有车辆最大承载容量的总和稍大( 作者在这里乘上一个1 1 的系数) ，因为该 “车”在服务结束后，要返回同一个车场中心，形成一个闭合的行驶环路；第一 个阶段的结果可以用来求第二个阶段求解m o v r p 问题的初始解。后面章节作 者将详细介绍这两部分的求解过程。 2 0 中山大学硕士学位毕业论文第4 章m - o m d v r p 求解及其结果分析 4 3 第一个阶段：求解m - - m d v r p 问题 在第一阶段求解0 1 m d v r p 问题的算法中，作者用来生成初始解的算法不 是用通常用的随机算法而是利用贪心算法，用客户的交换、插入和删除来确定解 的邻域，禁忌表中的对象是客户，禁忌长度的确定上，作者比较了固定长度和动 态长度方法，发现动态长度优于固定长度，算法的终止条件是迭代次数达到了给 定的范围，每次找到一个更优的解时，迭代计算器就清零。 4 3 1m - m d v r p 问题禁忌搜索流程 解决m m d v r p 问题的禁忌搜索算法流程如下： 夺利用贪心算法得到初始解i n i t i a ls o l u t i o n 夺把初始解设置为当前最优解b e s t _ s o l u t i o n = i n i t i a l _ s o l u t i o n 夺设置禁忌表的规模t a b u l i s t l e n g t h 夺设置最大迭代次数m a xc o u n t 夺初始化迭代次数 c o u n t = 0 夺设置候选解集和c a n d i d a t es o ls e t = n u l l ，并将i n i t i a ls o l u t i o n 添加到 c a n d i d a t e s o l s e t 中 夺当c o u n t m a x _ c o u n t b e s l s o l u t i o n 中还有客户未被服务 c o u n t = c o u n t + 1 通过邻域搜索生成新的c a n d i d a t es o ls e t 如果找到比b e s t _ s o l u t i o n 更优的解则更新b e s ts o l u t i o n ，同时令 c o u n t = 0 根据c a n d i d a t es o ls e t 中的解更新禁忌表t a b ul i s t 4 3 2 构造初始解 传统的禁忌搜索算法采用随机的方法来构造初始解。这显然是不够