车辆路径问题的启发式算法研究报告

1、- 目录 摘 要4第一章 绪论71.1研究背景71.2研究意义7第二章 车辆路径问题的研究综述92.1车辆路径问题描述92.2车辆路径问题分类92.3 国外对车辆路径问题的研究动态和水平10第三章 组合优化及现代启发式算法133.1 组合优化问题133.2 NP完全问题133.3启发式算法143.3.1传统启发式算法143.3.2 现代启发式算法14第四章 开放式车辆路径问题模型以及算法194.1 问题的提出194.2 OVRP数学模型的构建204.3 OVRP中应用的蚁群优化算法204.3.1算法的信息初始化234.3.2 问题的构造234.3.3 局部搜索244.3.4 信息素更新254.

2、3.5 算法的后优化过程264.4 实验和结果264.4.1 算法的测试问题264.4.2 算法中各类参数的设置274.4.3算法的实验结果284.5 小结30第五章 有时间窗的车辆路径问题的模型及算法315.1 问题的提出315.2 问题的描述及数学模型315.3遗传算法求解VRPTW335.3.1 自然编码遗传算法理论研究335.3.2 染色体构造365.3.4 遗传操作375.4 遗传算法的计算结果415.4.1遗传算法与其他启发式算法的比较415.4.2 遗传算法的计算时间的比较435.5 本章小结43第六章 带时间窗和随机旅行时间车辆路径问题模型及算法446.1问题的提出446.2

3、VRPSTW数学模型构建446.2.1VRPSTW时机约束规划模型456.2.2 VRPSTW带修正随机规划模型486.3 VRPSTW的禁忌搜索算法506.3.1 期望值求解和概率检查506.3.2解的评价526.3.4 邻域构造526.3.5 禁忌对象和禁忌表536.3.6 禁忌搜索算法的特赦标准536.3.7 禁忌搜索算法的流程536.4 实验结果556.4.1测试问题556.4.2参数的设置566.4.3 实验结果566.5 小结58第七章 结 论597.1 研究结论597.2 进一步研究方向59参考文献：60致63. z-. z-摘 要 在有关于物流配送的各种研究中，车辆路径问题是其

4、中的运筹学和组合优化领域的研究前沿和热点问题。车辆路径问题主要是针对一系列需求量的客户，而后对行车的路线进展适当的组织以使得车辆在不违反任何约束条件的根底上提供效劳，通过研究使得优化后的路线实现总本钱最小的目的。通过对这一类问题进展有效的解决可以在很大程度上使得车辆的利用率得以提高，配送本钱得以降低，同时还能有效提高配送时间的准确率，最终实现对物流效劳水平进展提升的目的。实践证明车辆路径问题是一个典型的NP难题，如果只是采用传统的方法，要想得到问题的最优解或者是满意解就显得比较的困难，因此采用现代启发式算法来对这些问题进展求解是现代专家学者想要解决这类问题的关键。本文也就是以车辆路径问题作为主

5、要的研究对象，综合利用了各种组合优化和现代启发式算法等工具，对三类比较常见而又重要的车辆路径问题模型极其优化算法进展了系统的研究。 1.针对开放式车辆路径问题 对于这一类问题的解决笔者主要采用的是通过假设将标准车辆路径问题的路线进展松弛成为哈密尔顿巡回，而后通过对哈密尔顿巡回式的车辆路径问题进展求解。文章首先给出了这类问题的数学模型，而后在这个数学模型的根底上，提出了求解开放式车辆路径问题的蚁群优化算法,通过进一步分析该蚂蚁算法的主体是一个在超立方框架下执行的MA*-MIN蚂蚁系统，该算法还在局部优化方面采用的是禁忌搜索算法，同时该算法还集成了一个后优化过程来进一步优化最优解。最后的时候，在标

6、准测试问题的根底之上，系统的对算法的性能和求解质量进展了研究。2.针对研究了带时间窗的车辆路径问题 对于这类问题笔者首先进展了数学建模，而后在此根底之上提出了解决该问题的遗传算法。因为基于自然数解码的遗传算法具有一定的全局搜索能力，可以极大的跳出局部最优解，从而对有时间窗的车辆路径问题进展很好的解决。3.针对带时间窗和随机旅行时间车辆路径问题进展了研究，笔者首先就通过对标准车辆路径问题的拓展，引入新的边约束条件：时间窗、随机旅行时间和效劳时间。而后根据优化标准的差异性，确定了该类问题的时机约束规划模型以及带修正随机规划模型。本文解决该类问题采用的就是建立在随机模拟的根底之上的禁忌搜索算法。而后

7、通过基于随机产生的测试问题通过实验检验算法的有效性。关键字：车辆路径 遗传算法 禁忌搜索算法 随机规划模型 研究意义AbstractOn the logistics and distribution of the various research, vehicle routing problem is one of the operational research and binatorial optimization of research in the field of frontier and hot issue. The vehicle routing problem is mainl

8、y aimed at a series of customer demand, and then known on the traffic of the route of the proper organization to make vehicles in not breach any constraint conditions provide services on the basis of research, through after the optimization of the route of the realization of the minimum total cost o

9、f purpose. Through this kind of problem to solve effectively can greatly improve the utilization rate of vehicles that can be reduced, and distribution costs, but also can improve the distribution of time, and finally achieve the accuracy of logistics service level for the purpose of ascension. Prac

10、tice proves the vehicle routing problem is a typical NP problem, if just the use of the traditional method, and to get the optimum solution of the or is satisfied solution is more difficult, therefore the heuristic algorithm to these modern solution is the modern e*perts want to solve the problem of

11、 the key. This paper also is to vehicle routing problem as the main research object, the prehensive utilization of all sorts of binatorial optimization and modem heuristic algorithm of three kinds of tools such as more mon and important vehicle routing problem model optimization algorithm is carried

12、 on the system research.1. According to open vehicle routing problem for this kind of solution of the problems the author mainly adopts the standard by assuming the vehicle routing problem on the route of the flabby, and then through the Hamilton bee tour of the Hamilton of the vehicle routing probl

13、em of tour solution. This paper first presents the mathematical model of the problem, and then in the mathematical model was put forward on the basis of solving open vehicle routing problem of ant colony optimization algorithm, through the further analysis the ant algorithm are the subject of a in t

14、he cubic framework of e*ecution MA*-MIN ant system, this algorithm is still in local optimization on the tabu search algorithm is, and the algorithm has integrated the optimization process to further optimize after the optimal solution. Finally, in the standard test problems on the basis of the syst

15、em of the performance of the algorithm and the solving quality was studied.2. According to the vehicle routing problem with time Windows to this kind of problem, first of all, the author the mathematical modeling, and then based on a solution to the problem of the genetic algorithm. Because the gene

16、tic algorithm based on natural number decoding has some of the global search ability, can greatly jump out of local optimal solution, thus to have time window of the vehicle routing problems in very good solve.3. According to take time window and random travel time vehicle routing problem is studied

17、, the paper first through to the standard vehicle routing problem development, introduction of new boundary constraint conditions: time window, random travel time and service time. Then according to the differences of optimization standard, and the problems of this kind of chance constrained program

18、ming model and with fi*ed stochastic programming model. This paper solve this kind problem is the establishment in the random simulation on the basis of the tabu search algorithm. And then based on random test problems through the e*periments verify the efficiency of the algorithm.Key words: genetic

19、 algorithm for the vehicle routing tabu search algorithm stochastic programming model research significance. z-第一章 绪论1.1研究背景 通过对物流这个行业历史的追溯，第一次提出对物品的配送本钱进展研究的学者是美国的J.F.Growell，他在1901年的美国政府报告“关于农产品的配送中，提到了对影响农产品配送本钱各项因素的研究。直到1927年R.Borsodi在其文章“流通时代中首次使用Logistic来称呼物流。对于物流这个概念日本还是上世纪五十年代中期才从美国引进的，在他们对其

20、国的物流进展调研的根底之上，将物流称之为“物的流通。一直到上世纪六十年代中期，理论界和实业界才开场全面承受物流这个词语。 随着全球经济的飞速开展，物流业在兴旺国家的国民经济中所扮演的角色也越来越重要，各大企业也对物流的重视度进一步提升，在这样的一种大背景下，第三方物流业取得了长足开展。根据权威机构的统计，我们可以发现有百分之七十多的德国企业和百分之五十多的美国企业都将物流放在了企业经营的第一或者是第二的位置。这也就说明了第三方物流在欧洲比在美国具有更高的成熟度。与此同时，也有越来越多的企业越来越多的美国和欧洲企业正在积极考虑使用第三方物流效劳。 我国是上世纪八十年代才开场引入“物流的概念和理论

21、的，但是一直以来国家和社会也没有对其引起足够的重视。随着我国改革开放的进一步深入，市场经济制度的进一步完善，各类企业所面对的竞争也越来越剧烈，物流作为一个可以从很大程度上提高禁忌竞争力的关键因素和影响众多领域开展的、巨大的潜在市场，开场被各界广泛的关注。特别是在1999年11月，世界银行和国家经贸委在召开了现代物流国际研讨会之后，我国的现代物流得到了高速的开展。 现代物流业是提升企业竞争的一种非常有效的方式，也可以让国民经济在高起点上持续快速的开展，并且提供比较根底的动力。在经济全球化和信息化的推动下，现代物流业已从为社会提供传统运输效劳，扩展到以现代科技、管理和信息技术为支柱的综合物流系统。

22、就目前而言，许多兴旺国家和地区已经形成了比较成熟的物理管理理念、先进的物流技术和高效的物流运营系统。进入到二十一世纪以后的中国，必定要对现代物流的开展方面加快步伐，通过这样的方法来增强企业竞争能力。对资源配置进展优化，进一步提高我国经济的运行质量，实现中国经济体制与经济增长方式的两个根本性转变，进而推动中国经济的持续安康的开展。1.2 研究意义 物流配送是物流中一个重要的直接与消费者相连的环节，是货物从物流结点送达收货人的过程。配送指的是建立在集货、配货根底上，按照货物种类、品种搭配、数量、时间等要求所进展的运送，是一种“配和“送的有机结合。整个的物流配送过程主要包括：从生产工厂进货并集结的集

23、货作业；根据各个用户的不同需求，在配送中心将所需要的货物挑选出来的配货作业；对所配送货物的质量和体积进展充分的考虑，同时利用好车辆的载重和容积对货物进展配装以及确定需要配送的路线。在物流系统的集约化以及一体化开展的大趋势下，通常的做法就是将配送的各个环节综合起来，这样的核心问题就是配送车辆的集货、货物配装以及送货过程。要想实现对货物配送系统的优化，主要需要考虑的就是关于车辆调度的优化，这种优化主要包括集货线路的优化、货物配装和送货线路的优化，以及集货、货物配装和送货一体化优化。在物流系统优化中对物流配送车辆的优化调度是其中非常重要的一个环节，同时这也是电子商务活动不可缺少的容。通过对配送车辆进

24、展优化调度，可以在很大程度上使得物流经济效益得到提升，并使得物流科学化得以实现。可以说对物流配送车辆优化调度理论与方法进展系统研究是物流集约化开展、构建综合物流系统、建立现代调度指挥系统、开展智能交通运输系统和开展电子商务的根底。 在中国参加到世界贸易组织之后，物流市场开放程度进一步加大，涌入了大量的外国物流企业，这样的情形对中国的物流企业来讲既是机遇又意味着挑战。在机遇方面表现为我国的大局部企业可以对国外的物流企业先进的管理经历和技术进展学习，而所要面临的挑战就是我国的物流企业将和国外的物流企业在同一块市场上竞争。各大物流企业要想在竞争中争取更好的位置，则实现准时、平安、低本钱的物流配送效劳

25、是极其重要的。而要想真正的实现这一点，对车辆采用人工调度的方式将很难满足这种要求，必须要对车辆运营调度问题进展系统的研究。 通过对人工调度的分析，我们发现人工调度由于存在着以下的一些缺乏使得其不能很好的满足现代物流企业的需求。这些缺乏主要表达在：第一个方面就是对于调度人员来讲人工调度的工作强度比较大，而且随着物流公司规模的不断扩大，客户的各类需求也越来越多，随之而来的就是配送车辆数的增加，直到增加到了一定的规模之后人工就比较难完成整个公司车辆的调度；表现在在另一个方面就是，调度人员在把握所有车辆的状态以及整个城市的交通状况这两个方面存在一定的偏差，这也就使得其很难对所有资源进展全局优化，难以提

26、高车辆的时空利用率；最后，使用人工调度还会受到人员的限制，一旦出现调度人员不能工作的情形，将直接对整个公司的运营产生影响。 在物流企业的整个运作中车辆的优化调度在其中起到一个非常重要的核心作用，同时也直接影响着公司的运营效率。通过对车辆调度系统深入而又细致的研究，既可以很好的使得车辆的利用率得到提升，而且也能够在一定程度上使得调度人员的工作强度得到降低，使得车辆的调度不会受到人员的限制影响。车辆的优化调度一个更为重要的作用就是可以极大的减少配送的车辆数，使得车辆的行驶距离和时间得以极大的减少，降低配送的本钱，提高配送时间的准确率，进而更好的使得物流效劳水平得以提升。. z-第二章 车辆路径问题

27、的研究综述2.1车辆路径问题描述 车辆路径问题是1959年由著名的学者Dantzig等1首先提出来的，他们对将汽油送往各个加油站的实际问题进展描述，在这个根底之上提出了相应的数学规划模型以及求解算法。在1964年的时候Clarke等2学者对Dantzig所提出来的算法进展了充分的改进，在这个改进的根底之上提出了一个更加有效的启发式算法Clark-Wright节约算法。自从这两篇具有开创意义的论文发表之后，有鉴于这类问题在应用和理论上的极大代表性，很多的各类相关学科的专家学者都对这类问题进展了研究，这些领域包括运筹学、组合数学以及图论与网络分析等。对于经典的VRP可以做出以下描述：给定一个完全图

28、其中可以作为图的顶点集，为弧集，顶点表示的就是库房，而顶点表示的就是用户。一个定义在A上的矩阵，它的元素表示的就是点到点的距离。有辆载重量为的车这个通常表示的就是决策变量。每一个顶点都只能够效劳一次，每一辆车都是从库房出发，在其完成效劳任务之后又回到。在对*些约束条件进展满足的情形下，如何更好的安排车辆行程，使得效劳所有用户的车辆行驶距离最小或者是所需要的车辆数是最少的。在一般的情形下通常会有以下几种约束：第一个方面就是关于容量的约束：也就是说每一条路径总的需求量或者说是供应量不可以超过车辆的容量。第二个方面就是关于行程距离方面的约束：每一辆车的最大行驶距离不能超过*一个预先就指定的数。第三个

29、方面就是关于时间窗方面的约束：这个时间窗也就包括硬时间窗和软时间窗。而这个所对应的分别是：带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows，VRPTW),这一约束主要表达在指定的效劳车辆必须要在用户所规定的时间提供理想的效劳；另外一种就是带软时间窗的车辆路径问题(Vehicle Routing Problems with Sof Time Windows，VRPSTW)，这个也就是规定车辆沿路径可以不在用户规定的时间提供效劳，但这样却会在一定程度上引起惩罚费用。2.2车辆路径问题分类自从VRP被提出来以后Bodin3,Desroche

30、rs,Linstra和Savelsbergh等众多专家学者都从不同的角度，按照不同的标准对VRP进展了分类。比方按照任务的特征来区分：可以分为纯装问题或者是纯卸问题pure pick up or pure delivery,车辆在所有顾客任务点只是进展装货或者是卸货，也就是集货或者是送货问题以及装卸混合问题bined pick up and delivery，这个说明的就是每一个任务都有不同的装货点和卸货点，也就是那种集货、送货的一体化问题。根据车辆的任务性质来分：可以分为弧效劳问题比方中国邮递员问题和对点效劳问题比方旅行商问题以及混合效劳问题比方交通车路线安排问题。按照车辆载货状况来区分：有

31、满载问题表示的就是货物量必须要大于车辆的容量，这就要求对一项任务的完成需要的不止一辆车和非满载问题这个一般就是确保货物量一定要小于车辆容量，用同一辆车完成多项任务。按照车场的数目来进展区分：可分为单车场问题和多车场问题。根据车辆的类型数来分，可以有单车型问题说明的就是所有的车辆容量一样和多车型问题这个说明的就是在执行任务的车辆其容量并不完全一样。通过对车辆与车场的所属关系来进展区分：分为车辆的开放问题这个指的就是车辆在执行完任务之后不需要再返回其原出发的车场和车辆封闭问题这个指的就是车辆在执行完任务之后必须返回其出发的车场。 还有就是根据优化的目标数来进展区分：可以分为单目标问题和多目标问题。

32、 由于有各种不同的情况，也就使得车辆路径问题的模型构造以及算法就会产生许多的极大的差异。2.3 国外对车辆路径问题的研究动态和水平通过对车辆路径问题的进一步分析我们可以发现这类问题的求解方法比较的丰富，从实质上来对这类求解方法进展划分，根本上可以分为准确算法和启发式算法两大类。准确算法指的就是可以将最优解求出来的算法。在准确算法的研究方面，Desrochers4, Kohl和Madesen5等专家学者都做过相关的研究，其中这种准确算法还可以分为分支界定法、割平面法、网络流算法以及动态规划法等。总的来说，这种准确性的算法是建立在比较严格的数学手段之上的，当这类算法处于可以求解的情况之下，所求出来

33、的解在通常情况之下要比人工智能算法要更加的优化。但是也正是要引入比较严格的数学方法，所以也就不得不面对其指数爆炸问题，这样一来也就使得这种准确算法只能应用于对小规模确实定性的VRP进展求解。通过分析，专家学者们普遍认为VRP是一个NP-hard问题，想要用准确算法来进展求解几乎不太可能，因此，就目前的情形来讲求解车辆路径问题的主要方法就是启发式算法，这么多年以来有大量的专家学者对车辆路径问题进展了充分的研究，并提出了比较多的启发式算法，Van Breedam6将启发式算法分成了三类：第一类就是路线构造法Route-construction algorithm,第二类就是两阶段法Two-phas

34、ed algorithm，而第三类就是建立在准确方法根底之上的启发式算法Heuristics based on e*act algorithm。本文将主要介绍建立在准确方法根底之上的启发式算法。1路线构造法 这一类方法的根本思想主要是：依据一些准则，每一次都将一个不在路线上的点增加进线路，这种过程一直持续到当所有的点都被安排进路线为止。这类算法的运行规则就是在每一步的时候都将当前的线路构形与另外的构形进展比较并加以改进，后者或是根据*个判别函数(例如总费用)会产生最大限度的节约的构形，或是以最小代价把一个不在当前构形上的需求对象插入进来的构形，最后得到一个较好的可行构形。关于这类算法中比较知名

35、的就是Clarke和Wright7在1964年提出来的。这种路线的构造算法最早是用来解决旅行商问题Traveling Salesman Problem,TSP以及VRP的，这类方法的一个比较突出的优点就是速度快，同时也比较的灵活，但是存在的缺乏之处就在于有时候这类方法所找到的解离最优解还有比较大的距离。2两阶段法 专家学者们都过对构造算法的进一步分析研究后认为，由构造算法所求得的解可以被进一步的改进，并在此发现的根底上提出了两阶段法。这就是将求解过程分成两个阶段，第一个阶段就是求得一可行解，第二个阶段就是通过对点的调整，在始终保持解的可行的情况之下，尽最大的可能向着最优化的目标靠近，通过这种算

36、法每一步都产生一个可行解来将原来的解进展代替，这样就可以使得目标函数值得到最大可能的改进，一直延续到不能再对目标函数值进展改进为止。Gillet和Miller的sweep算法，Christofides、Mingozzi和Toth的算法以及Fisher和Jaikumar的算法都是属于两阶段的算法。一般的两阶段算方法，在第一阶段时采用的就是构造的算法，而到了第二阶段就常常采用那些改进了的技术主要包括2-opt、3-opt和Or-opt变换法，这类方法主要是在解的邻域中进展搜索，以实现对初始解的一定程度的优化到达对算法进展改进的目的。3建立在准确方法根底之上的启发式算法 在这类算法中主要是以启发式准

37、则来代替准确算法中的决策准则，这样一来就可以从很大程度上缩小解搜索的空间。从总体的研究和实践经历来看，尽管启发式算法能够在比较有限的时间求出质量比较高的解，但由于其搜索解空间的能力的限制，因此很难得经常的到达预期的要求。而在二十世纪九十年代兴起的现代的亚启发式算法(Metaheuristics)则很好的解决了搜索空间比较有限的这个问题，这也在很大程度上吸引了很多专家学者对该类算法的关注。 就目前的研究状况而言，比较常见的亚启发式算法就包括模拟退火算法Simulated Annealing、禁忌搜索算法Tabu Search、遗传算法Genetic Algorithm、蚁群算法Ant Colon

38、y和神经网络Neutral Networks方法等。关于这些现代的亚启发式算法，将在下文中进展详细的表达。 2.4论文的主要章节安排 第一章主要是通过对物流这一概念的追溯，说明了物流对于现代企业以及国民经济的重要作用，而后论证了对车辆路径这一课题的研究背景和意义。第二章则主要详细介绍了经典VRP的数学模型，以及总结出了关于VRP的分类，同时也对国外对于VRP的研究和开展的动态进展了介绍。 第三章主要是详尽的介绍了求解组合优化问题的现代启发式算法。这一章的主要任务就是将研究中所要涉及到的根底知识进展介绍。第四章主要研究的就是开放式车辆路径问题，首先对开放式车辆路径问题进展建模，而后在此根底之上提

39、出解决该问题的蚁群优化算法，通过进一步分析该蚂蚁算法的主体是一个在超立方框架下执行的MA*-MIN蚂蚁系统，该算法还在局部优化方面采用的是禁忌搜索算法，同时该算法还集成了一个后优化过程来进一步优化最优解。最后的时候，在标准测试问题的根底之上，系统的对算法的性能和求解质量进展了研究。 第五章主要研究了带时间窗的车辆路径问题，首先对带有时间窗的车辆路径问题进展了数学建模，而后在此根底之上提出了解决该问题的遗传算法。因为基于自然数解码的遗传算法具有一定的全局搜索能力，可以极大的跳出局部最优解，从而对有时间窗的车辆路径问题进展很好的解决。 第六章主要研究的就是带时间窗和随机旅行时间车辆路径问题，首先就

40、通过对标准车辆路径问题的拓展，引入新的边约束条件：时间窗、随机旅行时间和效劳时间。而后根据优化标准的差异性，确定了该类问题的时机约束规划模型以及带修正随机规划模型。本文解决该类问题采用的就是建立在随机模拟的根底之上的禁忌搜索算法。而后通过基于随机产生的测试问题通过实验检验算法的有效性。 第七章主要是对全文的一个总结，给出论文研究的结果和成果。同时给出了进一步研究的容和方向。. z-第三章 组合优化及现代启发式算法3.1 组合优化问题组合优化问题binatorial Optimization,CO1011是指找到一组离散变量的值，使得给定的目标函数值最大或最小。在实际的生产生活中很多具有重要的实

41、际应用和理论研究的优化问题本身就具有一定的组合性质，比方最短路径问题、找出给顾客运送货物的最小本钱方案、互联网中对数据包传输的最理想路由策略等。组合优化在运筹学里是一个非常重要的分支，其主要的操作包括排序、分类、筛选等，在计算机科学、管理科学、生产调度、通信网络等领域有着非常广泛的应用。组合优化问题可定义为一个三元组。假设离散变量用表示，变量 的变量域为，则在三元组 中，表示“搜索空间search space 或者“解空间(solution space)；为搜索空间上的可行域，即表示目标函数。以最小化问题为例，组合优化问题的目标就是从可行域 中找到可行解，使得所有候选可行解 都满足 我们称为全

42、局最优解global optimum，集合 为全局最优解集合。 邻域构造Neighborhood Structure是组合优化问题中的一个重要概念，可定义为映射含义是对于每个解,一些“邻近的解构成的邻域，任意 都被称为 的领域解或邻居，通常约定 。假设,则称为 上的局部最优解。3.2 NP完全问题计算复杂性理论中对P问题是这样描述的即在确定型自动机上具有多项式时间算法的问题；如果一个问题困难到在确定型自动机上不可能用多项式算法求解，则就认为这个问题是难解的。5 同时，一般将在非确定型自动机上可用多项式时间算法求解的问题称作NP问题，而P是否等于NP仍然是数学界和计算机理论科学界尚未解决的问题。

43、如果NP类的任何一个问题都可以多项式时间规约到*一个问题，则该问题是NP难的；如果一个问题既是NP又是NP难的，则称该问题是NP完全的。在NP问题中NP完全问题是最难解的。事实上，求解大规模的NP完全问题已经成为当今计算机科学技术、人工智能等领域的瓶颈任务之一。自从上世纪60年代以来，已有许多组合优化问题被证明是NP完全的。除了本文重点讨论的车辆路径问题之外，比较有代表性的NP完全问题还包括旅行商问题、图着色问题、生产调度问题、装箱问题和覆盖问题。对于这类问题，由于其难解性和广阔的实际应用背景，人们通常更关心如何能够在可承受的时间找出问题的尽可能好的解，于是启发式算法成为求解这类问题的重要方法

44、。3.3启发式算法 启发式算法heuristic algorithm是相对于最优算法提出来的。启发式算法可以这样定义：一个基于直观或经历构造的算法，在承受的花费指计算时间、占用空间等下给出待解决组合最优化问题每一个实例的一个可行解，改可行解与最优解的偏离程度不一定事先可以预计。从20世纪70年代以来，对于组合优化问题尤其是NP完全问题的解决，大都采用了启发式算法来进展。随着各项研究的逐渐深入，启发式算法也经过了从简单到复杂，从单一到混合的开展阶段。3.3.1传统启发式算法 一般将构造性算法constructive algorithm和改进算法improvement algorithms称为传统

45、启发式算法。构造性算法是指从最初的空解开场，采用增量的方法迭代地添加解成分直到生产完整的解。这类算法通常是一些简单的启发式策略，在大多数情况下生成解的质量较差，因此目前常用于构造其它优化算法的初始解。改进算法是指通过从一个可行解到另一个可行解之间的变换，通过对两个解的比较而得到较优化地解。这类算法受初始解、邻域构造、搜索策略等各种因素的影响，往往容易陷入局部最优的情况。3.3.2 现代启发式算法现代启发式算法指的是在更高层次上组合根本启发式算法使得更加有效地探索问题的搜索空间。在国外对于现代启发式算法的研究也都比较的普遍，总结各学者对于启发式算法的研究可以发现，现代启发式算法是一组利用不同启发

46、式算法探索搜索空间的高级策略。这其中一个非常重要的思想就是多样化搜索和集中搜索之间的动态平衡机制。多样化搜索是指探索搜索空间，而集中搜索则是指利用搜索过程积累的经历知识在特定的区域进展深度开掘。这种搜索策略一方面快速地探索搜索空间包含高质量解的区域，另一方面又不浪费太多的时间在一些以前探索过的或者不能发现高质量解的区域探索。为了在集中搜索和多样化搜索的获得平衡，不同的现代启发式算法根据其构建所基于的哲学根底采用了不同的搜索策略。下面综述一些求解组合优化问题的有代表性的现代启发式算法，这些算法主要有模拟退火算法(Simulated Annealing，SA)，禁忌搜索算法(Tabu Search

47、，TS)、迭代局部搜索算法(Iterated Local Search，ILS)、遗传算法genetic algorithms蚁群优化算法(Ant Colony Optimization,ACO)等。1模拟退火算法模拟退火(Simulated Annealing，SA)18算法主要是研究者受到固体晶体的物理退火过程的启发而得到的。在这样的一个过程中固体首先是要先被融化掉，接着就是一步一步的缓慢的等却，在温度较低的条件下进展冷却过程，通过花费较长的时间从而获得一个处于最小能量状态的完美的晶格机构。通过对这样一个过程的模拟，模拟退火算法把问题的解集关联到物理系统的状态上，把目标函数对应固体的物理能

48、量，而最优解则是最小能量状态。模拟退火算法是局部搜索算法的扩展，它不同于局部搜索之处是以一定的概率选择邻域中费用最大的状态，从理论上来说，它是一个全局最优算法。简单的模拟退火算法如下： Step 1 任选一个初始解(初始温度).Step 2 假设在该温度到达循环停顿条件，则到Step 3；否则，从邻域 中随机选则一个 ，计算假设否则假设 重复Step 2.Step 3 假设满足停顿条件，终止计算；否则，回到Step 2. 在上述的模拟退火算法中，包含有一个循环和外循环，循环是Step 2，它表示在同一温度 时，在一些状态随机搜索。外循环主要包括Step 3的温度下降变化 迭代步数的增加和停顿条

49、件。 2禁忌搜索算法禁忌搜索tabu search算法是局部邻域搜索算法的推广，是人工智能在组合优化算法中的一个成功应用。Glover在1986年提出这个概念，进而形成一套完整算法。禁忌搜索算法得特点是采用了禁忌技术。所谓禁忌技术就是制止重复前面的工作。为了回避局部邻域搜索陷入局部最优的缺乏，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点或到达局部最优的一些过程，在下一次搜索中，利用禁忌表中的信息不再或有选择的搜索这些点或过程，以此来跳出局部最优点912。禁忌搜索算法中充分表达了集中和扩散两个策略。它的集中策略表达在局部搜索，即从一点出发，在这点的邻域寻求更好的解，以到达局部最优解而完毕

50、。为了跳出局部最优解，扩散策略通过禁忌表的功能来实现。禁忌表中记录下已经到达点的*些信息，算法通过对禁忌表中点的禁忌，而到达一些没有搜索的点，从而实现更大区域的搜索。禁忌搜索算法如下：Step 1 给以禁忌表tabu list并选定一个初始解；Step 2 满足停顿规则时，停顿计算，输出结果；否则，在的邻域中选出满足不受禁忌的候选集；在中选一个评价值最正确的解更新历史记录重复Step 2.禁忌搜索算法的Step 2中的邻域中不受禁忌的元素包含两类，一类是那些没有被禁忌的元素，另一类是可以被解除禁忌的元素。禁忌搜索算法是人工智能同局部搜索算法的结合，沿袭了局部搜索的邻域构造，增加了一个禁忌表。于

51、是，邻域连通条件为禁忌搜索可以到达全局最优解的一个必要条件。3遗传算法 遗传算法genetic algorithms这个概念是由Holland教授在20世纪70年代初期首先提出来的。遗传算法主要是借鉴了生物进化的一些特征，在自然选择的过程中适者生存也就是择优选择。遗传算法一般包括以下几个方面的步骤，第一是对优化问题的解编码，此处，我们称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和利于之后遗传算法中的计算。第二是适应函数的构造和应用。适应函数根本上是依据优化问题的目标函数而定。适应函数确定之后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪

52、些染色体适应生存，哪些被淘汰。生存下来的染色体组成种群，形成一个可以繁衍下一代的群体。第三是染色体得结合。双亲的遗传基因结合是通过编码之间的交配crossover到达下一代的产生。新一代的产生是一个生殖过程，它产生了一个新解。最后是变异，新解产生过程中可能发生基因变异，变异使*些解的编码发生变化，使解有更大的遍历性13。遗传算法简化的描述如下：Stpe 1 选择问题的一个编码；给出一个有N个染色体得初始群体POP(1),t:=1.Stpe 2 对群体POP(t)中的每一个染色体计算它的适应函数.Stpe 3 假设停顿规则满足，则算法停顿；否则，计算概率 并以概率分布从POP(t)中随机选一些染

53、色体构成一个种群 NewPOP(t+1)=. 注：NewPOP(t+1)集合中可能重复选POP(t)中的一个元素.Stpe 4 通过交配，得到一个有N个染色体的CrossPOP(t+1).Stpe 5 以一个较小的概率p，使得染色体的一个基因发生变异，形成MutPOP(t+1); t:=t+1,一个新的群体POP(t)=MutPOP(t);返回Stpe 2. 最优化问题的求解过程是从众多的解中选出最优的解。生物进化的适者生存规律使得最具有生存能力的染色体以最大的可能性生存。这样的共同点使得遗传算法能在优化问题中应用。(4)蚁群优化算法 蚁群优化算法Ant Colony Optimization

54、,ACO是一中分布式智能模拟算法，根本思想是模仿蚂蚁依赖信息素进展通信而显示出的社会行为。它是一种随机的通用试探法，可用于求解各种不同的组合优化问题，具有通用性和鲁棒性，是一个基于总体优化的方法。初始的蚁群优化算法是基于图的蚁群系统graph-based ant system ,GBAS可以简单地描述如下.Step 0 对n个城市的TSP问题，城市间的距离矩阵 ,为TSP图中的每一条弧赋信息素痕迹初值 ，假设有m只蚂蚁在工作，所有蚂蚁从同一城市 出发.k:=1.当前最好解.Step 1 (外循环)如果满足算法的停顿规则，停顿计算并输出计算得到的最好解。否则，让蚂蚁从起点出发，用表示蚂蚁行走的城

55、市集合，初始为空集，.Step 2 (循环)按蚂蚁的顺序分别计算.当蚂蚁在城市，假设或，完成第只蚂蚁的计算.否则，假设且，则以概率 到达 假设，则到达重复Step 2Step 3 对假设，按中城市的顺序计算路径长度；假设，路径长度是一个充分大的数.比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t，假设，用下面这个式子对W路径上的弧信息素痕迹加强，对其他弧的信息素痕迹挥发，得到新的重复Step 1.在这个简单的算法描述中，在其中的Step 3里，挥发因子 对于*固定的 满足并且 . 在上面描述的蚁群优化算法中，蚂蚁的搜寻过程是以信息素决定的概率分布选择下一个的城市。算法还包括两个其他的过程，由步

56、骤3的等式表达，称之为信息素痕迹的挥发evaporation过程和增强reinforcement过程.信息素痕迹的挥发过程就是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由.信息素痕迹的挥发过程主要用于防止算法太快地向局部最优区域集中。采用这种实用的遗忘方式有助于搜寻区域的扩展，增强过程是蚁群优化算法的一个可选局部，用于实现由单个蚂蚁无法事先的集中行动。. z-第四章 开放式车辆路径问题模型以及算法4.1 问题的提出 开放式车辆路径问题Open Vehicle Routing Problem，OVRP是经典的车辆路径问题VRP的拓展问题。经过分析可以知道OVRP和VRP的一个最明显的区别就在于：VRP中的车辆路线表现出的是一个汉密尔顿巡回Hamiltonian tour，而在OVRP中，车辆的路线就表现出的是一个汉密尔顿路径Hamiltonian path。出现这样区别的原因就在于因为在OVRP中，车辆在对最后一个顾客点的效劳完成之后，并没有提出其一定要回到车场的要求，如果需要返回车场，则必须按照原来的路线返回。在现代的配送管理中OVRP是一个存在面比较广泛的问题，该问题模型的建立可以通过许多的实际应用问题来进展。比方说一个配送公司没有其自身的配送车队，则该公司为了完成对顾客的