毕业设计（论文）针对突发事件的水利防汛车辆动态调度

1、针对突发事件的水利防汛车辆动态调度 摘要摘要：车辆调度问题是一个有约束的组合优化问题，属于 np 难题，突发事件可以被理 解成突然发生的事情 。在以突发事件为背景的情况下，动态调度的目的是在最短的时间 内将救援物资送到事发现场，以将损失降到最低。遗传算法是一类借鉴生物界的进化规 律演化而来的随机化搜索方法。 本文首先介绍了选题的目的、意义以及背景，然后对 突发事件、车辆的动态调度、遗传算法的相关知识进行了简单的介绍，最后以已经 发生过的水灾为背景，选取河南省辉县市西南部地区极易发生水灾或易受到水灾影响的 31 个地区，针对救援物资的二次分配，以路径选择为研究对象，将其看成是简单的 tsp 问题

2、。根据遗传算法基本原理，应用 matlab 软件，对算法进行了较为详细的设计，通过 对实际问题进行的分析，最终找到一条耗时最短的路线，并对算法进行了分析与优化。 关键词关键词：突发事件，水利防汛，动态调度，遗传算法 the vehicle scheduling of water conservancy control aiming at the emergencies abstract: vehicle scheduling problem is a constrained optimization problem. it is belongs to the nonderministic po

3、lynomial problem. the emergency can be known as one thing which happened suddenly. based on the emergencies, the intention of the vehicle scheduling problem is to make sure that the goods and materials which are used to the emergency relief can be sent to the destination as soon as possible, in orde

4、r to cut down the damages to the least. the genetic algorithm is a random-search method imitating the rules of the organic world. firstly, the intention, meaning and the background of the vehicle scheduling are introduced; secondly, there was a simple introduction of the emergencies, vehicle schedul

5、ing and the genetic algorithm; thirdly, based on the flood which have happened, choosing 31 countries and all of these countries suffer the flood easily, aiming at the secondary distribution of the goods and materials, this problem was regarded as a simple chinese salesman problem and the choice of

6、the way was treated as the object of our study. according to the principle of the genetic algorithm, a more particular means was made combined with the matlab. finally, a best answer was found through the analysis of the actual problem. at the same time, some analysis and optimization that about the

7、 means were made. key words: emergency, water conservancy control, vehicle scheduling, genetic algorithm 目 录 摘要 .i abstract .ii 1 绪论 .1 1.1 选题背景.1 1.2 选题目的及意义.2 1.3 研究方法.2 2 突发事件、救援物资的定义与分类 .3 2.1 突发事件及其分类.3 2.2 救援物资的分类及其调度特点.3 2.2.1 救援物资的分类 .3 2.2.2 救援物资调度的特点 .4 3 车辆动态调度的现状 .5 3.1 运输车辆调度分类.5 3.2 国内

8、外对于车辆调度问题的研究现状.6 3.2.1 国外研究现状 .6 3.2.2 国内研究现状 .6 4 遗传算法的研究动态 .8 4.1 遗传算法的特点.8 4.2 遗传算法得有关术语及控制参数.9 4.2.1 遗传算法的有关术语 .9 4.2.2 控制参数 .9 4.3 基本遗传算法的步骤.10 5 用遗传算法解决实际问题 .12 5.1 遗传算法的设计.13 5.1.1 给所有地区编码 .14 5.1.2 编码和初始群体生成 .14 5.1.3 城市位置及距离矩阵和适应度函数 .15 5.1.4 选择复制 .15 5.1.5 交叉 .15 5.1.6 变异 .16 5.1.7 群体的更新和终

9、止条件 .16 5.2 有关 matlab 的计算如下.16 5.3 算法分析与优化.22 6 结语 .24 致 谢 .25 参考文献 .26 附 录 .28 附 录 1：英文原文.28 附 录 2：中文翻译.34 1 绪论 1.1 选题背景 伴随着越来越多突发事件的发生，进一步要求相关部门做好应急救援工作。从远古 时期开始，就采用各种方法来预防和解决由于夏季的大降雨量所带来的各种水利突发事 件，从历史数据可以看出，每年多次的暴雨造成七大江河水势不稳，从而容易引发部分 地方山洪、滑坡、泥石流和城乡滞涝，因此每年中国都会有或大或小的水灾。 河南省辉县市地处太行山脉，属于多山区，辉县市的西南地区地

10、处丘陵地区，且有 宝泉水库、三郊口水库、要街水库，到每年雨季，三大水库必须做好防汛工作，及时的 放水，稍有不慎，将造成较大的损失。且经过多年的开发，已造成山体不稳，在夏季， 暴雨之后，极易造成山体滑坡现象。 无论是事业单位还是私营企业，都希望在一定的约束条件下将成本降到最低，合理 的车辆动态调度是降低生产成本、提高经济效益的有效手段。车辆调度问题自 1959 年 g.b.dantzig 等开始进行了初步研究后，由于其应用的广泛性和经济上的重大价值，很快 成为国内外学者研究的热点问题。车辆调度问题是指在车辆数量信息已经确定的情况下， 怎样根据用户的需求（静态的或者动态的）合理地安排车辆的调度方案

11、，从而在最大满 足用户需求的前提下（约束条件）使得运输成本降到最低（即使目标函数值达到最优） 。 车辆调度问题可以看成一个特殊的运输问题，运输的对象是物，而车辆调度的对象 是一般的人，货物可以根据载量分批运输而人是必须一次性调度，所以调度问题的条件 要比运输问题的条件要求严格，条件约束性更强。 动态规划调度，就是利用动态规划的思想，把调度问题根据需要划分为若干阶段， 在每一个阶段中根据目前掌握的可利用的车辆情况和需要进行调度的需求情况，做出调 度的最优决策。由于突发事件是一个整体活动，需要多方面的协作和共同努力，因此引 起更多重视的是最早完成任务所需的时间。进行车辆调度的方案有很多种，可以满足

12、不 同的需要。应急环境下的车辆调度就是在众多的调运方案中，选择使得调度任务完成时 间最早且运输成本最少的方案。在本文中只要求任务完成的总时间最短。 1.2 选题目的及意义 从 98 年的洪灾到 10 年的舟曲泥石流，每一次的洪灾都将危害群众 的生命财产安全， 而每一次的洪灾都将对洪灾发生地的全年农业、工业、交通、电力、通信、民生等造成 重大经济损失，虽然相关部门每一年都积极的做好水利防汛工作，但是很多情况下，对 天灾并不能很好的预测，为此在水利防汛方面，存在着严重的问题，面临着巨大的挑战， 针对一些无法准确预测的水利事件，相关部门应尽可能的将事后的损失降到最低，为此 就要求在一定范围内，做好调

13、度工作，确保救援物资在第一时间内安全、快速的送到受 灾地。 1.3 研究方法 在本文中，以河南省辉县市易发生水灾的八里沟所在地及其周围的 31 个地方为研究 对象，以 2010 年及以往发生的水灾为参考，研究的是对救援物资的二次分配问题。将这 个简单的二次分配问题看成是简单的 tsp 问题，从而找出最优路径，对车辆进行动态调 度。在研究问题时，假设只有时间最短这一个目标函数，除了每个事发地都必须到达外， 并没有其他的约束条件。 目前，针对 tsp 问题，相对比较成熟的算法有遗传算法和蚁群算法，这两种算法都 是根据生物现象演变发展而来的，针对蚁群算法搜索时间长，容易出现停滞现象等缺点， 本文选择

14、遗传算法，应用 matlab 软件对实际问题进行分析。 2 突发事件、救援物资的定义与分类 2.1 突发事件及其分类 突发事件可被广义地理解为突然发生的事情：第一层的含义是事件发生、发展的 速度很快，出乎意料；第二层的含义是事件难以应对，必须采取非常规方法来处理。 在中国把突发事件分为四类：第一类是自然灾害，类似地震、海啸、洪水等等；第二类 一般是重大的生产事故，像“京广路塌陷” ，就属于重大的交通事故，还有工厂的生产安 全事故、煤矿的坍塌、爆炸等等；第三类也就是常讲的公共卫生突发事件，像非典、 “禽 流感”等，都属于公共卫生领域的突发公共事件；第四类是涉及重大社会安全的事件， 比如恐怖袭击等

15、。 一般依据突发事件可能造成的危害程度、波及范围、影响力大小、人员及财产损 失等情况，突发事件预警 级别可以由高到低划分为特别重大 (级)、重大(级)、 较大(级)、一般(级)四个级别，并依次采用红色、橙色、黄色、蓝色来加以表示。 2.2 救援物资的分类及其调度特点 2.2.1 救援物资的分类 （1）防护用品 防护服(衣、帽、鞋、手套、眼镜)，防毒面具，防火服，头盔，手 套，面具，消防靴，潜水服(衣)，水下呼吸器，防爆服，安全帽(头盔)，安全鞋，水靴， 呼吸面具。 （2）生命救助 止血绷带，骨折固定托架(板)，救生圈，救生衣，救生缆索，减压 舱，保护气垫，防护网，充气滑梯，云梯。 （3）生命支

16、持 便携呼吸机，急救药品，防疫药品。 （4）临时食宿 炊具，过滤净化机(器)，压缩食品，罐头，真空包装食品，帐篷(普 通、保温)，棉衣，棉被，简易厕所(移动、固定)，简易淋浴设备(车)。 （5）通讯广播 移动电话，对讲机，有线广播器材，扩音器(喇叭)。 （6）污染清理 喷雾器，垃圾焚烧炉，杀菌灯，消毒杀菌药品，凝油剂，吸油毡， 隔油浮漂。 （7）动力燃料 防爆防水电缆，配电箱(开关)，电线杆，工业氧气瓶，煤油，柴油， 汽油，液化气，干电池、蓄电池(配充电设备)。 （8）器材工具 葫芦，绞盘，滚杠，千斤顶，手锤，钢钎，电钻，电锯，油锯，张 紧器，液压剪，灭火器，灭火弹，风力灭火机，防水望远镜，工

17、业内窥镜，潜水镜。 2.2.2 救援物资调度的特点 （1）救援过程中时间的紧迫性决定了物资调度以时间快速为首要目标。 （2）涉及范围广、需求点多、物资种类繁多、物资需求量大。 （3）由于信息的不确定性，物资调度具有动态性。 （4）救援物资来源范围广，物资的到达具有滞后性，剩余物质需要妥善回收处理。 3 车辆动态调度的现状 车辆调度问题属于 np 难题，车辆调度是各专业运输公司和大型企业部门的一项日常 性工作。其目的是在一系列已知的装货点和卸货点组成的运输网络中，选择适当的行车 路线，将运输任务合理分配，在满足一定的约束条件(如车辆容量、容积限制、行驶里程 限制等)下，达到一定的目标(如总路程最

18、短、费用最少、使用车辆最少等)。 3.1 运输车辆调度分类 货运车辆优化调度问题可根据不同的性质具体分为以下几类： 按照运输任务分为纯装问题、纯卸问题以及装卸混合问题。按照车辆载货状况分为 满载问题和非满载问题，满载问题是指货运量多于一辆车的容量，完成所有任务需要多 辆运输车辆；非满载问题是指车的容量大于货运量，一辆车即可满足货运要求1。 按照类型分为单车型和多车型问题；按照车辆是否返回车场划分为车辆开放问题和 车辆封闭问题，车辆开放问题是指车辆不返回其出发地；车辆封闭问题是指车辆必须返 回其出发车场。 按照优化的目标可分为单目标优化问题和多目标优化问题；按照有无休息时间要求 可以划分为有休息

19、时间的调度和无休息时间的调度。 实际中的车辆优化调度问题可能是以上分类中的一种或几种的综合。 车辆优化调度问题是一个有约束的组合优化问题，属于 np 难题（nondeterministic polynomial problem） 。随着问题输入规模的扩大，求解时间呈几何级数上升。 目前车辆优化调度的方法通常可以分为精确算法、启发算法和智能算法。精确算法 主要有分支定界法等；启发算法主要有构造函数法、两阶段法等；智能算法分为神经网 络法、遗传算法和模拟退火算法等1。其中精确算法的计算量随着车辆优化问题规模的增 大呈指数增长，当卸货点的数目超过 20 个时，采用精确算法求解最短路径的时间在几个 小

20、时以上，为此精确算法不适合于求解大规模的车辆优化调度问题。基于智能计算的搜 索算法求解 sp 问题近年来发展迅速。遗传算法、蚁群算法、人工神经网络、粒子群算法 等在克服 sp 问题上述困难方面具有独特优势，并且能克服传统方法在处理多目标或有约 束的 sp 问题时灵活性差和无法适应动态网络等缺点，且能够给出 pareto 解集，具有实 用性。在本文中，选择遗传算法。 3.2 国内外对于车辆调度问题的研究现状 3.2.1 国外研究现状 国外对动态问题的研究开始于 1954 年，文献17研究了利用动态网络来解决如何安 排油轮的调配才能使得所使用的油轮数最少的问题。文献1820主要对确定性的车队 动态

21、调度问题进行了研究。文献18研究确定性的有时间窗限制的多车型车辆动态调度 问题，并利用一系列线性规划模型对原有的动态网络模型进行改进从而能够用于处理多 车型和有时间窗的车队管理问题。文献1920都是利用物流排队网络解决确定性的车 队动态管理问题，但是这种方法运算速度有时较慢而且难以实现。 文献21研究了铁路运输中空车调配问题，用一种时空图表来表示车辆实际运动过 程，并设计了相应的网络流算法，在时空图表上求解了空车分配方案，但是由于本质还 是图表作业，对一定规模的车队，有一定的局限性。文献22针对在运输网络中的空车 规模和分配问题设计了一个优化模型，同时优化车队的大小和车辆分配，利用一种网络 近

22、似计算的方法来解模型，并证明算法收敛4。其中文献23主要通过假设未来的任务需 求和空车分布情况已知去制定调度计划，对模型本身进行深入的分析。但是文献2223均 忽略了载货车辆的重要性。文献29研究了一种铁路调度系统中的空车调配问题，计算 空车调配的费用，并且证明这种费用体现了规模效益。 3.2.2 国内研究现状 在静态 vrp 问题上，国内有关文献对静态 vrp 作了广泛而深入的研究，主要是在满 载与非满载、带有时间窗限制、是否带有回程取货等方面作了研究。在动态 vrp 问题上， 文献11主要研究了不确定信息造成的随机性事件的解决策略，并给出了单车场、单车 型闭合环境动态车辆调度的数学模型和算

23、法。文献12将复杂交通网络下的车辆路径问 题分为确定需求和动态需求两部分。并分别建立了不同需求下的调度模型和动态调整策 略。文献16采用系统科学的观点和方法、类比法及数理模型的研究方法，同时结合离 散数学、最优化理论、计算机数学等相关学科的理论知识，以提供一种新的建模思路和 求解算法为目的，但是并没有考虑到对空车进行动态调整，以及与重车流的协调优化， 欠缺一定的系统性4。文献14深入剖析了存在于已有研究工作中的不足，并从车辆调配 影响因素、车辆调配形式、车辆调配方案制定和问题的动态特性四个方面对车队动态管 理问题的基本情况进行详细论述，将车队动态管理问题分为单车型确定性问题、多车型 确定性问题

24、和随机问题三大类，并从其模型建立与算法构造的角度出发开展了系统化的 研究工作，分别针对单车型确定性车队和多车型确定性车队的动态管理问题，进行了分 析，同时对于随机车队动态管理问题，分析了问题的随机特性，并根据未来需求的概率 分布函数，设计期望车辆数的估计方法、车辆选择概率的确定方法和车辆期望收益值的 确定方法，从而确定线性替代函数斜率，构造线性替代函数来逼近目标函数中的期望函 数部分，使问题分解为多个单时段单节点问题6。但此文献为了降低分析问题的复杂度， 对实际的情况进行了很多简化。根据以上文献综述分析，国内外学者大多利用函数逼近 技术从时间上和空间上把问题分解为多个单时段单节点的车辆调度问题

25、进行求解，或者 利用仿真技术来模拟调度情况，从而获得可行的调度方案。但是均对实际问题进行了较 大程度的简化，也没有实现整个运输网络所有车辆的统筹调度，并且主要思路是将未知 需求转化为确定概率分布，因此所做出的调度方案无法保证存在确定的货源，在实际应 用中具有一定的限制性。并且目前国内外有关水利方面的车辆的动态调度研究较少。 4 遗传算法的研究动态 遗传算法（genetic algorithm）是一类借鉴生物界的进化规律（适者生存，优胜 劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的 j.holland 教授于 1975 年首先提出，遗传算法是从代表问题可能潜在的解集的一个种群（popul

26、ation）开始 的，而一个种群则由经过基因 （gene）编码的一定数目的个体 (individual)组成。每 个个体实际上是染色体 (chromosome)带有特征的实体。染色体作为遗传物质的主要载 体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的 形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。 因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的 工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存 和优胜劣汰的原理，逐代 （generation）演化产生出越来越好的近似解，在每一代， 根

27、据问题域中个体的适应度 （fitness）大小选择（selection）个体，并借助于自然遗 传学的遗传算子 （genetic operators）进行组合交叉 （crossover）和变异（mutation） ， 产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前 代更加适应于环境，末代种群中的最优个体经过解码（decoding） ，可以作为问题近 似最优解。在本文中选择的是简单遗传算法 （sga） 。 4.1 遗传算法的特点 遗传算法的主要特点如下： （1）遗传算法一般是直接在解空间搜索,而不像图搜索那样一般是在问题空间搜索, 最后才找到解。 （2）遗传算法的搜索随

28、机地始于搜索空间的一个点集,而不像图搜索那样固定地始 于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。 （3）遗传算法总是在寻找优解,而不像图搜索那样并非总是要求优解,而一般是设法 尽快找到解,所以遗传算法又是一种优化搜索算法。 （4）遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索, 而不像图搜索那样一般是从空间的一个点到另一个点的搜索。因而它实际是一种并行搜 索, 适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。 （5）遗传算法的适应性强, 除需知适应度函数外,几乎不需要其他的先验知识。 （6）遗传算法长于全局搜索,它不受搜索空间的

29、限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。 4.2 遗传算法得有关术语及控制参数 4.2.1 遗传算法的有关术语 （1）个体 就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼， 一个个体也就是搜索空间中的一个点。 （2）种群(population) 就是模拟生物种群而由若干个体组成的群体,它一般是整个搜 索空间的一个很小的子集。 （3）适应度(fitness) 适应度就是借鉴生物个体对环境的适应程度,而对问题中的个体 对象所设计的表征其优劣的一种测度。 （4）适应度函数(fitness function) 就是问题中的

30、全体个体与其适应度之间的一个对应 关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。 （5）染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编 码表示；字符串中的字符也就称为基因（gene） 。 （6）遗传操作(genetic operator) 亦称遗传算子，就是关于染色体的运算。遗传算法 中有以下三种遗传操作: 选择-复制(selection-reproduction) 通常做法是：对于一个规模为n的种群s,按每 个染色体xis的选择概率p(xi)所决定的选中机会, 分n次从s中随机选定n个染色体, 并进行复制。这里的选择概率p(xi)的计算公式

31、为 （4.1） 1 i in j j fx p x fx 交叉(crossover，亦称交换、交配或杂交) 就是互换两个染色体某些位上的基因。 变异(mutation)，亦称突变，就是改变染色体某个(些)位上的基因。 4.2.2 控制参数 （1）最大换代数 预设的代数一般为 100500 代。 （2）交叉率(crossover rate) 就是参加交叉运算的染色体个数占全体染色体总数的比 例，记为,取值范围一般为 0.40.99。 c p （3）变异率(mutation rate) 指发生变异的基因位数占全体染色体的基因总位数的比 例，记为，取值范围一般为 0.00010.1。 m p 4.3

32、 基本遗传算法的步骤 第一步 在搜索空间上定义一个适应度函数f(x)，给定种群规模，交叉率和un c p 变异率，代数； m pu 第二步 随机产生u中的n个个体，组成初始种群， 123 ,., n s sss 123 ,., n ss sss 置代数计数器t=1； 第三步 计算s中每个个体的适应度 f() ； 第四步 若终止条件满足，则取s中适应度最大的个体作为所求结果，算法结束； 第五步 按选择概率所决定的选中机会，每次从s中随机选定 1 个个体并将其 i p x 染色体复制，共做n次，然后将复制所得的n个染色体组成群体； 1 s 第六步 按交叉率所决定的参加交叉的染色体数c，从中随机确定

33、c个染色体， c p 1 s 配对进行交叉操作，并用产生的新染色体代替原染色体，得群体； 2 s 第七步 按变异率所决定的变异次数m，从中随机确定m个染色体，分别进行变 m p 2 s 异操作，并用产生的新染色体代替原染色体，得群体； 3 s 第八步 将群体作为新一代种群，即用代替，转第三步。 3 s 3 s 2 s1tt 生成初始种群 计算适应度 选择-复制 交叉 变异 生成新一代种群 终止结束 图 4.1 遗传算法基本流程 注意：在遗传算法中还应注意编码问题，对个体进行编码，但对 121 ,., nn sc cc c 于这样的个体如何编码却不是一件直截了当的事情，因为如果编码不当，就会在实

34、施交 叉或变异操作时出现非法城市序列即无效解。 例如，对于 5 个城市的 tsp，用符号 a、b、c、d、e 代表相应的城市，用这 5 个符 号的序列表示可能解即染色体然后进行遗传操作。设 =（a, c, b, e, d, a） ，=（a, 1 s 2 s e, d, c, b, a） 实施常规的交叉或变异操作，如交换后三位，得 =（a,c,b,c,b,a） ， =（a,e,d,e,d,a） 1 1 s 1 2 s 或者将染色体第三位的b变为d，得 1 s =（a, e, d, e, d, a） 11 1 s 可以看出，上面得到的，和都是非法的城市序列。 1 1 s 1 2 s 11 1 s

35、针对此类编码问题，人们已经提出许多编码方案：顺序编码或整数编码、随机键编 码、部分映射交叉、循环交叉、反转变异、移位变异等，只需在运用时进行选择即可10。 5 用遗传算法解决实际问题 2010 年辉县市八里沟所发生的水灾，造成上盘必经之路愚公洞坍塌，数百亩田地被 淹，大水淘空路基，多条道路成为危路，多条上山道路的路边护坡滑了下来，大水冲进 村庄和农户家里，造成严重的损失。河南省辉县市地处太行山区，到每年的多雨时节， 极易发生水灾，本文以河南省辉县市西南部地区为研究对象，选择易发生水灾的三个地 方黄水、洪州、上八里，以及其最容易波及到得地区，共计 31 个地方，分布图见图 5.1： 上八 里 中

36、八 里 下八 里 下白 古潭 五里 河村 大史 村 梅溪 村 前小 庄 前郭 雷 南关 村 西坪 回龙 村 大方 山 康庄 龙门 村 圪针 林 黄水 新小 庄 西池 头 岳村 高庄 乡 张货 郎乡 赵雷 西孟 庄 和寺 庵村 洪州 乡 新郭 村 宋庄 新乡 庄 王庄 北冀 庄 图 5.1 31 个地方分布图 本文中讨论的是对物资的二次分配问题，31 个地方均需要救灾物资，那么就要求所 用车辆将 31 个受灾地均走一遍，所以该问题可以看作为简单的 tsp 问题，对于一条路径 为,其中，一般数学模型如下： 121 ,., nn lt tt t 11n tt ,1 1 min in i i i d

37、（5.1） 代表第 i 地和第 i+1 地之间的距离。 ,1i i d 5.1 遗传算法的设计 如上文所述，本文中采用简单遗传算法来进行求解，遗传算法总体设计如图 5.2 选择交叉变异 随机路径 n2n2 产生初始群体n 产生随机路径使 群体数目不变n- n2-1 最优解下次迭代1 跟新群体n 图 5.2 遗传算法总体设计 说明：（1）本算法的判断结束准则是固定最大迭代的次数，当算法达到迭代次数时，算 法结束，输出当前的最优解。 （2）在根据适配值计算并选择的时候，记录下来当前最优值，在变异后加入跟新的 群体，保证新的迭代循环中 tsp 解越来越好（不会变差） 。 （3）选择的一种操作是拿最优

38、的 k 个替换最差的 k 个个体，本例是按适配值选择， 并使群体数目变少，当每次变异操作后，产生随机路径补充群体是使群体数目不变，再 次循环，一定程度上防止因初始群体的选择问题而陷入局部最优10。 （4）在本文选择复制概率确定方法为赌轮选择法，赌轮选择法可用下面的子过程 来模拟: 在0, 1区间内产生一个均匀分布的随机数r； 若,则染色体被选中； 1 rq 1 x 若, 则染色体被选中。其中的 qi称为染色体 1 2 kk qrqkn k x 的积累概率, 其计算公式为 1,2,3,., i x i n （5.2） 1 i ij j qp x 详细设计如下： 5.1.1 给所有地区编码 编码情

39、况如表 5.1 表 5.1 31 个地方编码情况 梅溪村1洪州乡17 前郭雷2西池头18 岳 村3北冀庄19 和寺庵村4前小庄20 新乡庄5南关村21 新小庄6赵 雷22 黄 水7西孟庄23 宋 庄8张货郎乡24 龙门村9康 庄25 下白古潭10下八里村26 大方山11中八里村27 回龙村12上八里镇28 西 坪13王 庄29 高庄乡14大史村30 圪针林15五里河村31 新郭村16 5.1.2 编码和初始群体生成 在 matlab 中使用 randperm(n)产生一个 1n 的矩阵（n 为所有城市的个数，本例 中为 31）为一个随机路径，利用 nn 矩阵存储 n 个随机群体产生初始群体。

40、5.1.3 城市位置及距离矩阵和适应度函数 城市的位置为编译前指定，也可以使用随机生成的坐标参数。距离矩阵使用一个 nn 矩阵 d 存储，d（i，j）代表城市 i 和城市 j 之间的距离。 （5.3） 22 , ijij d i jxxyy 在该问题的求解中，用距离的总和来衡量适应度，距离的总和越大，适应度越小， 进而探讨求解结果是否最优11。 每个个体（每条路径距离）总和计算公式为： len=d(1,n); for i=1:(n-1) len=len+d(i,i+); end len 纪录总路径格式 n1，len(i)代表第 i 个个体（路径）距离总和。 5.1.4 选择复制 选择操作是为了

41、避免有效基因的损失，使高性能的个体得以以更大的几率生存，从 而得到全局收敛性和计算效率。本问中所用的适配值函数为： 1,1min ,1 maxmin0.0001 len ilen fitness i lenlen （5.4） maxlen,minlen 为最大和最短路径 利用 fitnessrand 选择个体，将个体，将较小路径(适应度较大)个体选择下来。 但这种算法的群体的个体数目变小并且较优的个体个数较少，可能收敛的数目变慢，在 算法调试的过程中证明了这一点。 5.1.5 交叉 本文中交叉采用部分匹配交叉策略,其基本实现的步骤是： 第一步，随机选取两个交叉点； 第二步，将两交叉点中间的基因

42、段互换； 第三步，将互换的基因段以外的部分中与互换后基因段中元素冲突的用另一父代的 相应位置代替，直到没有冲突。 5.1.6 变异 变异操作通过随机改变个体中某些个体的某些基因而产生新个体，有助于增加种群 的多样性，避免早熟收敛（非全局最优） 。 本文中变异操作使用互换操作算子（swap） ，即随机交换染色体中两个不同基因编码 的位置，swap 相对于 inv（逆序操作）和 ins（插入操作）更有利于算法的大范围搜索。 对于一个 31 路径的染色体的变异操作，依变异概率确定是否变异，随机选择路径 上的两个城市进行交换。例如：变异交换位置为 2 和 8 83456719028945671302

43、5.1.7 群体的更新和终止条件 为保证计算随迭代次数的增加，最优解越来越好，本例中每次变异后将每次的上次 迭代最优解加入群体，防止因交叉或变异而使最优解失去，出现退化现象。 为保持群体数目不变，将变异后产生的随机解加入群体（本算法群体数目在选择中 可能发生减少） 。 终止条件最常用的有事先给定一个最大进化步数，或者是判断最优化值是否连续若 干步没有明显变化两种。 在本文中，由于地方跟地方间距离较近，选用的距离单位为米（m） 。 5.2 有关 matlab 的计算如下 （1）初始值（图 5.3） 种群个数 n=100;迭代次数 c=1000；交叉概率 pc=0.9；变异概率 pm=0.2；初始

44、种群 中的一个随机值: r = 30 13 15 16 23 17 22 12 2 18 31 5 25 28 11 6 26 3 14 29 24 1 9 21 10 20 8 7 4 19 27 rlength=4.4308e+005 ；迭代 1000 次后路径如图 5.3，rlength=3.0903e+006；发 现算法收敛很慢。 图 5.3 （2）初始值（图 5.4） 种群个数 n=100；迭代次数 c=2000；交叉概率 pc=0.9；变异概率 pm=0.2；初始种群 中的一个随机值:r=22 31 21 18 3 15 11 5 1 6 7 8 10 19 20 24 25 27

45、 29 2 4 9 12 13 16 14 17 23 26 28 30；迭代 2000 次后路径如图 5.4，rlength=1.9496e+003 趋向于 收敛。 图 5.4 （3）初始值（图 5.5） 种群个数 n=100；迭代次数 c=2500；交叉概率 pc=0.9;变异概率 pm=0.2；初始种群 中的一个随机值: rlength=4.3507e+006；迭代 2500 次后路径如图 5.5，rlength =1.8755e+005，趋向于收敛。 图 5.5 （4）初始值：（图 5.6） 种群个数 n=100；迭代次数 c=3000；交叉概率 pc=0.9；变异概率 pm=0.2；

46、rlength = 4.4721e+005；迭代 3000 次路径如图 5.6，rlength=1.6957e+004。 次序为 r= 29 13 7 10 24 8 3 18 30 21 26 28 27 31 1 15 14 12 11 23 6 5 2 4 16 17 19 9 20 25 22 路径较小可能已经为最优解。 图 5.6 （5） 初始值：（图 5.7） 种群个数 n=100；迭代次数 c=3500；交叉概率 pc=0.9；变异概率 pm=0.2；rlength = 4.4723e+004；迭代 3500 次路径如图 5.7，rlength = 1.7094e+004。 次序

47、为 r= 25 20 27 22 18 3 17 16 5 6 7 2 4 8 9 10 13 12 11 23 19 24 29 14 15 1 31 30 21 28 26 路径较小可能已经为最优解。 图 5.7 城市 坐标矩阵为 a=1303 2322；3539 1415；4277 2144；3613 1398；3487 1534；3325 1565；3240 1229；4189 1055；4322 791；4385 571；3017 975；2560 1755；2787 1490；2380 1675；1334 696；3716 16798；3917 2178；4068 2375；378

48、4 2213；3674 2575；4023 2836；4265 2934；3427 1909；3500 2377；3395 2644；3438 3200；2936 3241；3139 3549；2544 2356；2777 2825；2371 2976 可以认为该算法在迭代 3000 左右时，已经发生了收敛，对于本例给出一个解为 r =30 31 24 10 26 16 8 27 28 13 14 12 11 25 9 15 7 6 18 29 5 17 23 22 19 14 3 21 1 20 2 具体情况如图 5.8： 上八 里 中八 里 下八 里 下白 古潭 五里 河村 大史 村 梅溪

49、 村 前小 庄 前郭 雷 南关 村 西坪 回龙 村 大方 山 康转 龙门 村 圪针 林 黄水 新小 庄 西池 头 岳村 高庄 乡 张货 郎乡 赵雷 西孟 庄 和寺 庵村 洪州 乡 新郭 村 宋庄 新乡 庄 王庄 北冀 庄 图 5.8 具体行车路线 5.3 算法分析与优化 （1）选择操作 在本文中算法收敛较慢，改进选择操作如下，选择 n 个最大适应度 的个体，用来代替适应度最小的 n 个个体，保持群体的整体数目不变，此方法可以使群 体的平均适应度大幅度提高，可以使其收敛速度加快。 （2）每次交叉或变异后操作以后，检验子代的适应度，如果子代发生退化，取消操 作，用父代代替子代，这种方法可能带来的问

50、题有：不利于种群的多样化，可能收敛 解非最优解；虽然收敛迭代次数可能较少，但是每次运算的计算量增加，增加了运算 的时间。解决方法是根据某一较小概率 0.1-0.2 有选择的进行检验和替换16。 （3）免疫遗传算法 免疫遗传算法是在变异后加入免疫算子，可以大幅减少迭代次 数。针对 tsp 问题，免疫算子设计为先用一个的矩阵存储每一个定点（城市或者区2n 域）与其相应的最近城市（或区域）的编号。如和 aj,2最近的城市（或区域）aj,1。 对于 tsp 问题而言，在最终的解决方案中，即在最佳路径中必然包括（活在很大程度上 包括）了相邻城市（或区域）间距离的最短路径。将城市（或区域）aj,1移到 a

51、j,2 之后，进行免疫检测，如果个体发生退化，取消免疫。免疫遗传算法可以在很大程度上 加快收敛速度，减少迭代的次数。 （4）终止条件 终止条件最常用的有以下两种：事先预定一个最大的迭代次数； 判断最优化值是否连续若干步没有明显的变化。在本文中选用的是第一种方法，此外 还可以根据第二种方法，设定每隔 100 次记录一次最优解，当连续四次输出的解不变或 者结果相差不大，则终止计算16。 6 结语 在不考虑具体路况的情况下，本文中求得的解为满意解，即按照求得的路线行驶， 可以使救援物资的二次分配在最短的时间内完成，但是如若考虑到具体情况，那么在路 况改变的情况下，应该及时通过一定的通讯手段将信息传递

52、给指挥部，以便对路线进行 及时的调整，并且本文中所涉及到的易发生水灾以及易受水灾影响的地方，交通并不是 十分的便利，并且在这 31 个地方当中，有大部分的地方是处在辉县市多山区，此类地方 若发生水灾，救援物资想送到水灾发生地，则必须经过愚公洞，相对来说此段在发生水 灾的时候是关键点，如若此段坍塌救援物资则不能顺利的运送到山里，并且辉县市相对 来说比较重要的旅游景点：八里沟、回龙、南坪、郭亮、关山、万仙山都在此周围，如 若救援不及时进行，那么将造成较为严重的经济损失。对于这一类的应急情况，本文不 作进一步的分析。 致 谢 四年的读书生涯在这个季节即将划上一个句号，而于我的人生却只是一个逗号，我

53、将面对又一次征程的开始。四年的求学生涯在师长、亲友的大力支持下，走得辛苦却也 收获满囊，在论文即将付梓之际，思绪万千，心情久久不能平静。 本学位论文是在我的指导老师马歆老师的细心指导下完成的，从课题的选择到论文 的最终完成，马歆老师始终都给予了细心的指导和不懈的支持，我不是您最好的学生， 但是却是最尊敬您的学生，在马歆老师的细心指导下，明白了授人以鱼不如授人以渔的 道理，每一次与您谈话结束，总会学到很多东西，有一种豁然开朗的感觉，在此，表示 深深的感谢，同时也感谢四年来帮助我、教育我的每一位老师，从你们身上，学到的不 仅仅是书本上的知识，还有很多书本以外的，但是是使我们受益终身的知识。 本文最

54、终得以顺利完成，也是与我的同班同学、朋友以及施浩然学长分不开的，虽 然他们有的没有直接参与我的论文指导，但也给我提供了不少的意见，提出了很多可行 性的建议，在此向他们表示真挚的感谢。 感谢我的父母，养育之恩，无以回报，谢谢你们对我的支持与帮助，你们永远健康 快乐是我最大的心愿。 最后再一次感谢所有在毕业论文的写作中曾经帮助过我的良师益友和同学，以及在 论文中被我引用或参考的论著的作者。 参考文献 1李军,郭耀煌.物流配送车辆优化调度理论与方法研究m.中国物资出版社.2001 2李臻,雷定猷.多车场车辆优化调度模型及算法j.交通运输工程学报.v0l.4 no.1 mar2004 3李菁,王宗军,

55、蒋元涛,邹彤. 免疫算法在车辆调度问题中的应用j.运筹与管理 vol.12 no.6 dec2003 4张武梅.车队动态调度优化模型与算法研究d.山东大学硕士学位论文.2007.04.08 5张志涌等.matlab 教程基于 6.x 版本m.北京航空航天出版社 6孙红,谭笑. 遗传算法在车辆调度优化问题中的研究j.计算机工程与应用. 2010,46（24）:246-270 7谢秉磊,李军,郭耀煌. 遗传算法在非满载车辆线路安排问题中的应用j.系统工程学 报.1999，5(8)：10681069 8邓薇.带时间窗的车辆路线问题及算法研究d.武汉大学硕士学位论文.2005.04.20 9王新华.带

56、时间窗的车辆路线问题研究d.同济大学硕士学位论文.2005.12.0l 10宗满意.遗传算法的 tsp 的求解.智能优化计算及应用课考核论文 11刘云霞.动态车辆调度问题分析及算法设计d.西南交通大学硕士论文. 20040201 12肖增敏.动态网络车辆路径问题研究d.西南交通大学硕士论文. 20050301 13李引珍,郭耀煌.运输网络最短路径关键点问题研究j.铁道学报.vol.26 no.6 december 2004 14李冰.动态车队管理问题的模型及算法研究d.西南交通大学博士论文. 20031101 15纪寿文等.货运车辆优化调度方法j.公路交通科技.vo.20 no.6 16周荣敏

57、等.管网最优化理论与技术遗传算法与神经网络m.黄河水利出版社 17 dantzigg, fulkerson d minimizing the number of tankers to meet a fixed schedule j, naval research logistics, 1954, 1:272-222 18 warren b.powell, tassio a. carvalho. dynamic control of multicommodity fleet management problems j. department of civil engineering and op

58、eration research princeton university princeton september 25, 1996 19 tassio a. carvalho, warren b.powell.a multiplier adjustment method for dynamic resource allocation problemsd.department of civil engineering and operation research princeton university princeton,may 2000 20 warren b.powell, tassio

59、 a. carvalho. dynamic control of logistics queuing networks for large-scale fleet management d. department of civil engineering and operation research princeton university princeton, february, 1998 21 w.w.white and a.m.bomberault a network algorithm for empty freight car allocation j.freight car all

60、ocation, 1969 no 2: 147-168 22 beaujon george j, turnquist mark a model for fleet sizing and vehicle allocation j.transportation science, 1991 1(25):19-24 23 joborn m.empty freight car distribution at swedish railways-analysis and optimization modelingd.ph.d.thesis,department of mathematics,linkopin