摘 要

近年来，世界范围内自然灾害频发，威胁到了人类生命安全，同时侵犯了财产安全，减缓了人类社会进步的进程。中国灾害以种类的繁多，形式的多样化，分布范围的广泛性等特点而闻名，同时也是世界范围内遭受自然灾害破坏的较为严重的国家中的一员。虽然随着世界经济的发展，世界科技也发生着翻天覆地的变化，人们对于灾害的预测水平也在不断的提高，但是对于突发事件预测的精确度仍然存在着问题。如何减少灾害对人类带来的损害是我们目前迫在眉睫的任务之一。

本文从遗传算法的角度研究了灾后应急物资运输异构车辆路径优化问题，首先介绍国内外关于异构车辆路径问题的研究现状，提出研究内容，然后阐述了遗传算法的相关概念及运作流程，以及需要的具体的技术手段，接着构建异构车辆路径优化问题模型，并且采用遗传算法的思想和上文构建的模型来结合具体例子求解出异构车辆物资运输的最佳路径。文章的最后提出对灾后应急物资运输异构车辆路径问题未来的展望。

关键词：应急物资配送，遗传算法，异构车辆调度模型

Abstract

In recent years, the frequent occurrence of global natural disasters has caused great damage to the lives and property of human beings, and seriously hindered the progress of human society. China is one of the most affected countries in the world by natural disasters. The variety of disasters, the diversification of disaster forms and the wide distribution of the disasters have brought serious harm to people. Although with the development of world economy, science and technology in the world are undergoing changes which has taken placing around us, the level of disaster prediction has been improved, but the precision of prediction for emergencies is still a problem. How to reduce the damage caused by disasters is one of our urgent problems.

This paper studies the emergency materials transportation problem of heterogeneous vehicle routing optimization genetic algorithm after the disaster from the static angle, through the construction algorithm, and case analysis, put forward the prospects for the post disaster emergency materials transportation heterogeneous vehicle routing problem in the future.

Key Words：Emergency material distribution, genetic algorithm, Vehicle Scheduling Model

目录

摘要 I

Abstract II

1.绪论 1

1.1研究背景 1

1.2研究目的 1

2.研究现状 2

2.1引言 2

2.2国内灾后应急物资配送异构车辆路径优化研究现状 2

2.3国外灾后应急物资配送异构车辆路径优化研究现状 2

3.遗传算法 4

3.1遗传算法定义 4

3.2遗传算法的发展 5

3.3遗传算法相关概念 7

3.4遗传算法流程图 9

4.灾后应急物资配送异构车辆路径问题模型 10

4.1问题描述 10

4.2异构车辆路径问题模型构建 10

4.2.1物资配送异构车辆路径问题的构成要素 10

4.2.2物资配送异构车辆路径问题模型构建 11

5.应急物资配送异构车辆路径问题算法设计 14

6.案例分析 15

7.全文总结与展望 19

7.1全文总结 19

7.2展望 20

致谢 22

1.绪论

1.1研究背景

近年来全球自然灾害频发，根据统计数据，全球范围内发生的自然灾害高达400次以上。造成上万人死亡，上亿人受伤。如2004年底印度洋板块与亚欧板块之间的海啸、2008年四川汶川地震、2011年9.0级里氏地震等。虽然随着世界经济的发展，世界科技也发生着翻天覆地的变化，人们对于灾害的预测水平也在不断的提高，但是对于突发事件预测的精确度仍然存在着问题。自然灾害的频发，威胁到了人类生命安全，同时侵犯了财产安全，减缓了人类社会进步的进程。如何减少灾害对人类带来的损害是我们目前迫在眉睫的任务之一。

1.2研究目的

在世界范围来说，中国遭受的自然灾害十分频繁，由此所带来的损失也是十分惨重。2008年，四川地震，引起的直接经济损失高达8000多亿人民币。根据四川省卫生厅所接收到的捐赠物资的数据，灾后需求物资还是以生活用品、食物为主。这些捐赠物质种类繁杂，数量庞大，这就对灾害物资救助的体系提出了很高的要求。如何快速而有效的把救灾物质运送到灾区是我们当前面临的一项严峻的挑战。本文主要研究应急物资运输中异构车辆路径优化问题，通过了解路况，车辆容量等，对灾害应急物资配送进行规划，高效地完成灾后物质救助。

2.研究现状

2.1引言

灾后应急物资分配和运输是将各种灾后救援物资进行分配并通过最佳的路径输送到对应灾区。灾害发生以后，救灾中心会向灾区运送大量的救灾物质，由于灾害的影响，物资运输道路必然遭受到了不同程度的损害，一方面由于救灾物质数量十分庞大，种类也很繁杂，另一方面由于灾害影响具有严重的危害性，间发性，以及联系性，快速而有效的展开救援工作就显得极为重要了，否则将会对人类的财产和生命安全造成更为无法挽回的损失。

在此之前，在国际范围内就有许多研究人员从各种方面开展过应急物资分配运输方面的问题的研究。在所有的结果中，绝大部分的研究都专注于在单阶段应急物质的分配和运输，并且将应急车辆路径规划归为车辆路径问题，同时针对于多阶段问题的研究还是从静态物资的分配问题角度出发。虽然国内外在灾后物质运输车辆路径优化方面有了大量的研究，但是还并未真正处理好灾害救资物质运输时间过长，成本过大的困难。

2.2国内灾后应急物资配送异构车辆路径优化研究现状

国内在这方面的研究起步较晚。在2007年，朱建明建立了一个单周期，单出救点的应急车辆路径模型，这个模型主要是对准大规模突发事件应急医疗物资调度问题所提出的，它的主要目标是以满足的需求量何总的物资延误时间为最小，然后运用多项式事件算法求解。2008年唐连生以需求满足的概率最低化和车辆对于物资的运输时间最短提出了一个多目标车辆路径优化问题，并且通过对蚁群算法进行优化，得出车辆和人员的最优路径。此外，2010年，魏航通过构造时变随机网络下多目标应急车辆路径选择优化模型来设计一个求解应急路径选择的算法。

另外还有一些学者也对该问题提出了相应的研究，卢安文分别以时间为目标和以费用为目标建立了应急物资车辆调度优化模型，樊建华利用免疫遗传算法对车辆调度问题进行求解。

2.3国外灾后应急物资配送异构车辆路径优化研究现状

早在1987年Knott以最小化运输成本为目标，1988年基于食品运输问题为灾区运输大批食品的车辆调度提出了线性规划模型。1996年Haghani和Oh通过建立动态车辆路径问题模型，研究了多种运输模式下从多个供给中心将种类繁多的灾后救援物资进行分配运送到灾区的车辆路径问题。在这个模型中，车型，时间窗等随着时间变化而变化。2004年Ozdamar和Demir运用了CPLEX软件，通过使灾害点聚集分类，将构建车辆路径问题转化为带能力约束的网络流问题。该种方式主要是基于车队规模大小，时变，供应数量等不断更新数据。该方法将着重点放在解决车辆流和商品流两个方面然后运用了拉格朗日松弛算法来进行解决。2007年Araz通过使用不同方法，提出了一个基于覆盖多目标应急车辆定位模型，解出了该模型。2008年Burcu提出了一个研究问题，主要是针对灾后物资运输中最后一公里的救灾物品配送，换而言之就是在一定的期限内将救援物资从配送中心运输到灾区。坚持运输成本的最低，配送的公平性，建立相应模型，而且为了更新问题相关的信息，还运用了时间间隔滚动制。2009年Geroliminis基于空间排队论研究了城市应急物流网络车辆分配与定位问题。同年的Jotshi运用情景计划的方法，利用了伤亡、道路、条件来制定车辆路线。这个方法周顾了损坏和网络的可用性造成的的不确定性，深入探讨了灾后物资运输的路径规划方面。此外Matisziw通过与已有模型进行对照，构建了一个不需要全部列举最短路的s-t路径选择模型，评价分析了模型的网络空隙时间，总旅行距离和拥堵可能性。2011年Gu以灾害人员死亡数目最低作为目标，通过考虑运输耗时的不确定性来构建多种周期的灾后救援物资的配送模型。2012年Berkoune等提出了一个应急条件下的运输模型，使用遗传算法进行求解。另外Pisinger等还提出了统一通用的启发式算法，能够求出五种（时间窗，容量限制等）车辆路径问题的变形。

3.遗传算法

3.1遗传算法定义

遗传算法是一种搜索方法，它可以类比于生物体的进化过程，主要是基于生物进化论的自然选择和遗传机制而提出的一种模拟模型，它的主要技术方法是模拟自然进化过程，最终目的是搜索最佳解。

在使用遗传算法进行求解问题时候，问题的参数空间被编码空间所代替，在以编码群体为进化的基础下，充分运用适应度函数来进行评价。遗传算法的主要过程是一个迭代过程，主要的思想是通过个体位串的遗传操作实现选择和遗传。利用随机重组的思想，对编码位串中的重要基因进行改变，所得到的新的一代的位串基因总体要比老一代的位串基因要优良，这就像生物遗传上面个体的不断进化的思想，通过迭代计算，使得群体中的个体不断地进化发展，慢慢的向最优解靠拢，最后得到最接近最优解的结果，如此就十分有效的解决了问题。

据我们所知，达尔文的自然选择学说中有“适者生存”的观点，具体来说就是对环境相对而言适应性较好的生物就能够得以发展，哺育出更多的后代，而那些对环境适应性较差的生物就会经过自然界的竞争机制被淘汰。

遗传算法与生物的遗传概念有着千丝万缕的联系，遗传概念在遗传算法上得到了充分的运用，主要归纳为以下几点：

表3.1 遗传算法与生物遗传联系

3.2遗传算法的发展

遗传算法是一门从生物学和计算机科学中所衍生的交叉学科，最初是被科学家所提出为了解决现实世界复杂适应系统的一种计算机技术，科学家经过长期的研究和拓展，主要将这种计算机技术的研究发展为两个方向：自然进化系统的计算模型，模拟进化算法。