《应急物流路径优化问题研究9800字（论文）》

\o"79296:基于遗传算法的震后军事应急物流路径优化的研究"\t"3:81/Crm/Task/_blank"基于遗传算法的应急物流路径优化的研究目录TOC\o"1-3"\h\u301541.绪论 .绪论1.1研究背景面对频繁的自然灾害，不断完善防灾体系，必须继续改善自然灾害发生后的应急管理。在发生自然灾害时，救灾工作的有效性在很大程度上取决于应急后勤系统的有效运作。目前，应急物流领域的研究已引起社会各界的关注。中国目前在应急物流领域的研究可以分为：应急资源的分配与规划，应急物流网络，应急物流计划，评估应急物流的有效性，应急物流系统和应急物流决策支持。作为自然灾害后紧急救援行动的重要组成部分，对应急资源的分配和调度的研究主要包括为武警部队在应急后勤运送车辆和物资分配的问题。其中，紧急情况下车辆路径任务的有效优化实施，是提高应急救援水平，提高应急能力的重要保证[1]。尽管近年来，中国各级政府在应对自然灾害时的紧急情况管理方面做得非常出色而富有成果，但应对重大灾害的被动形势却揭示了应急机制，物资储备和优化的决策过程。缺乏尊重。同时，中国的公共卫生基础设施发展欠佳，在紧急情况下缺乏经验。为了最大程度地减少自然灾害造成的损失并确保受影响人员的生命和财产安全，不仅需要对实施紧急物流的内涵、法律机制和方法进行系统的研究，而且还需要在销售渠道中紧急运输物料的车辆。进一步研究了优化决策理论和任务路由方法，以提高应急物流的效率。1.2研究意义基于应急物流的特点和车辆路径问题的模型，建立了应急车辆路径优化的优化系统。根据该优化系统，建立了适当的数学模型，并在车辆路径问题的优化过程中添加了建模解决方案的几个参数，例如：各种运输材料的重要权重，时间限制，交通拥堵条件和惩罚函数参数，对各种影响的定量评估关于运输计划有效性的可变决策。本文将目标距离最小的传统运输车辆问题转化为运输规划效率最高的应急物流车辆的多用途任务，为进一步研究武警部队在应急物流运输车辆的多用途问题提供了理论依据。本文具有重要的实践意义。1.3国内外研究现状1.3.1国外研究现状Fiedrich(2000)[2]探讨了在有限的时间，资源的数量和质量的情况下，讨论了资源的有效利用以提高救援质量并最大程度地减少死亡人数，并开发了一种优化的计划模型，以将资源分配和运输到地震后受灾的多个地方。JaeYoungChoi(2003)[3]介绍了在未定义道路网络的情况下如何分配有限的资源（例如救护车和其他应急设备）以将受害者运送到医院，目标是最大程度地增加受救者人数。Linet(2004)[4]讨论了紧急运输计划，该研究假设当前和将来的物料供应有限，当前所需的物料数量已知，并且可以预测未来所需的物料数量。假定不应将车辆返回到库存点，并且车辆的分配过程由一系列“断点”路线组成。目标是在请求的时间内使救援中心的需求最大化。该模型从几个要素分为两个网络流量问题。P1是线性的，以使需求点处的项目满意度最大化，P2是一个整数，以使车辆达到最大化认识P1。这两个模型通过拉格朗日松弛的迭代同时求解。Jiuh-BingSheu(2010)如果大规模自然灾害发生后没有足够的信息，本文提出了一种用于应急物流运作的动态紧急需求管理模型，包括以下步骤：①数据集中以预测受灾地区的物质需求；②使用模糊聚类将所有灾难分为几组：③使用几组标准来确定这些组的优先级。他还通过实例验证了信息不完全的模型的动态预测和需求分配效果，实验结果表明模型总误差小于10％。1.3.2国内研究现状缪成、许维胜、吴启迪(2006)[5]结合救援物资的运输和商业运输的各种特点，表明了救援物资的运输问题将几个货运网络中的流动问题与多个起止点和几种运输方式结合起来，并规划了车辆的满载问题，并以此为基础描述这个问题。通过递延计算成本和时间的方法，由分层网络构建多功能数学编程模型。本文提出了一种基于拉格朗日松弛法的解决方案，将原始问题分解为两个子任务：货物流和交通流，分别使用混合货物流和低成本流算法来解决。计算示例证实了该解决方案具有良好的收敛性和计算效率。卢茜(2009)[6]采用最短路径理论选择地震发生时应急车辆的路径，以最短时间和最大数量为主要思想。该模型考虑了时间、交通量、交通强度和其他因素之间的内部关系，以及交通流和影响安全性的因素的理论，定量确定了实际任务中时间和交通量的数学表达式，并建立了地震紧急情况的物流系统。用于选择平均道路上的运输路线的模型。邓敏皓、文振华(2011)[7]由于对企业和个人的紧急物流有严格的时间要求，因此提出了一种改进的层次分析法来解决此类问题。为了减少判断矩阵的一致性检查的计算，对可以获取精确值的因子进行加权平均计算。通过测试，改进的AHP建模的结果变得更加合理。2.相关概念2.1应急物流概述2.1.1应急物流的定义应急物流是一项特殊的物流活动，可根据紧急情况为材料，人员和设施的需求提供紧急支持。紧急情况包括严重的自然灾害，应急公共卫生事件，公共安全事件和军事冲突的建设。与常规物流不同，紧急物流包括液体、载体、流向、过程、流量和其他因素以及时空的利用。在大多数情况下，应急物流通过物流效率实现其物流优势，而常规物流则强调效率和有效性。2.1.2应急物流的性质与特点(1)应急物流的性质应急物流系统受社会利益驱动，为受灾地区的人们提供服务。当前，中国应急物流的特点如下：政府高度重视企业的积极参与，军民相互配合，军方拥有强大的登陆部队，通常需要提前进行准备工作并进行前期准备。(2)应急物流的特点①突发性和不可预测性。这是应急物流区别于一般物流的最明显特征。②时间约束紧迫性。应急物流的服务对象,即受灾群众对物资的需求非常紧迫,关系到生命安全。③弱经济性。应急后勤的原则是通过科学合理地分配劳动力、物资、设施和其他资源，在自然灾害影响的地方尽可能地挽救人们，并执行后勤任务。物流速度的重要性高于物流成本，这与一般物流不同。④政府与市场共同参与。2.1.3应急物流的主要缺陷 面对突发的自然灾害,应急物流过程当中最主要的问题是出现“救援真空”。“救援真空”表示灾害发生后到灾民得到救援的这段时间。导致“救援真空”出现的原因主要有以下几点:(1)信息不畅通。重大灾害发生后通信设备一般会再短时间处于瘫痪状态,使得灾区与外界信息的交流中段。(2)物流路段不畅通。灾害发生后,尤其是大地震往往会伴随山体崩塌,造成道路中段,导致部分物流路段通行受阻,影响了物资运输进度。(3)灾区物资需求点的需求时间限制。灾害发生后,各受灾区需求点对物资的需求具有时间限制,而由于总体运输任务重、人员及车辆不充等原因,难以将物资及时送往各个受灾点。此外,在制定货运代理工作计划的过程中，考虑到灾区人们对各种材料的紧迫性也很重要。例如，地震后的早期阶段的应急后勤应集中于运输医疗材料，随后集中于食品，帐篷，毯子和其他生活材料。在一定时间段内，如果在此时间间隔内无法满足需求，则将影响灾区人民的生命和安全以及紧急安全隐患的相关费用。各种材料需求的紧迫性应与紧急安全隐患的成本线性相关。在宏观层面上存在的不足主要在于:(1)应急平台系统不完善,影响应急物流效率。(2)应急预案不完善。(3)国家应急救援物资储备不足。(4)缺少第三方物流企业的参与。(5)缺少应急救援专业队伍。2.2车辆路径优化理论概述2.2.1车辆路径问题的定义车辆路径问题(VehicleRoutingProblem,简称VRP)是指在一定的约束下,根据已知的待服务客户的网点布局、物流配送中心的位置、车辆的最大负荷等信息,为车队组织出适当的行车路线分送货物。在满足客户的需求的同时,实现诸如路程最短、成本最小、耗费时间最少等目标。车辆路径问题是现代物流系统研究中的一项重要内容。通过规划合理的运输路线,优化配置各类资源,可以提升对客户的响应速度,降低运输成本并提高服务质量。2.2.2车辆路径问题需满足的前提条件车辆路径问题存在不同的优化模型,但一般而言车辆路径问题的研究需满足一下条件假设:(1)客户即需求点的位置可知;(2)配送中心与各个客户即需求点的距离矩阵可知;(3)所有参与配送任务的车辆都以配送中心为起点,并在完成运输任务后返回配送中心;(4)每一条配送路径上各个客户即需求点的总需求量不超过车辆负载;(5)每个客户即需求点的需求由且仅由一辆车来满足。2.2.3车辆路径问题的模型分类按照车辆路径问题所涉及的各类因素,可以对车辆路径问题的模型进行划分:(1)按照供应点与需求点数量划分:包括单供应点多需求点的简单车辆路径问题与多供应点多需求点的复杂车辆路径问题;(2)按有无时间限制划分:包括有时间窗限制的车辆路径问题(VehicleRoutingProblemwithTimeWindow,VRPTW)与无时间窗限制的车辆路径问题。其中时间窗限制有分为硬时间窗限制与软时间窗限制,硬时间窗车辆路径问题要求每项运输任务必须在指定的时间内完成;软时间窗车辆路径问题指对于未在指定时间内完成运输任务给以一定的惩罚。如果将对单个点的运输任务效率与到达时间的线性关系作比较,能够更加直观地分析硬时间窗与软时间窗的区别,如下图2.1与图2.2:图中,p表示对于单个需求点运输任务完成的效率,t表示货物到达的时间,et表示时间窗的最早到达时间,lt表示时间窗的最晚到达时间,M表示运输任务的效率值。其中硬时间窗VRP问题中,如果货物在时间窗外到达,则此需求点任务完成的效率为0。而软时间窗VRP问题中,如果货物在时间窗外到达,任务完成的效率呈线性关系递减。图2.1硬时间窗中效率与时间的关系图2.2软时间窗中效率与时间的关系(3)按客户需求量与车辆负载大小划分:包括满载车辆路径问题和非满载车辆路径问题。当单个客户需求量大于单车的载重负荷时,这个需求点的运输任务要由一辆以上的车来完成,此类车辆路径问题称为满载车辆路径问题。当单个客户需求量小于单车的载重负荷时,这个需求点的运输任务只需要由一辆车来完成,而一辆车可以完成一个以上的需求点的运输任务,此类车辆路径问题称为非满载车辆路径问题。按客户需求类型划分:包括确定型需求车辆路径问题、模糊需求车辆路径问题(FuzzyVehicleRoutingProblem,FVRP)以及随机需求车辆路径问题(VehicleRoutingProblemwithStochasticDemand,VRPSD)。随机需求车辆路径问题是指虽然明白客户即需求点的位置,但无法准确地指定客户的需求量。模糊需求车辆路径问题是指在车辆调度的过程当中,面对某些客户无法给出准确需求信息的情况,将模糊概念引入模型来解决此类问题。确定性需求车辆路径问题则指对客户即需求点的位置、需求量等信息都明确的车辆路径问题。2.3遗传算法的概念遗传算法(GeneticAlgorithm,GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,它最初由美国Michigan大学约翰·霍兰德(J.Holland)教授于1975年首先提出来的,并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》,来的,并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》,GA这个名称才逐渐为人所知,J.Holland教授所提出的GA通常为简单遗传算法(SimpleGeneticAlgorithm,SGA)。1975年,J.Holland的学生DeJong在其博士论文“Ananalysisofthebehaviorofaclassofgeneticadaptivesystems”一文中结合Holland的模式定理进行了大量的函数优化试验,将遗传算法的思想运用于最优化问题当中。20世纪80年代是遗传算法的发展阶段,Holland实现了第一个基于遗传算法的及其学习系统——分类系统,提出了遗传算法的机器学习的新概念,为分类器在构造上提出了一个完整的框架。1989年,美国伊利诺大学的古尔德伯格(Goldberg)所著的“GeneticAlgorithminSearch,OptimizationandMachineLearning”对于遗传算法的理论及其多领域的应用展开了较为全面的分析和例证,奠定了现代遗传算法的科学基础[42]。此后,许多专家与学者对简单遗传算法提出了改进措施,建立了许多遗传算法的模型,从而使遗传算法更加完善,被广泛的应用与各个领域。3.应急物流车辆路径问题的优化系统及模型构建3.1应急物流车辆路径问题的优化系统构建3.1.1系统的输入(1)车辆信息:包括车辆行驶的平均速度、车辆的最大载重量、单位车辆行驶的固定成本与可变成本。对于所有成本最小化的车辆路径问题,车辆速度和载重负荷都是必须考虑的变量。另外在本系统的车辆单位成本中,划分了固定成本与可变成本。固定成本即启动一辆车所需的必要成本,如驾驶车辆产生的人力成本;可变成本即为单位油耗、车辆磨损等,与车辆行驶路程呈线性关系的成本。(2)道路网络信息:包括网络中各配送点与灾区需求点的运输距离矩阵与道路阻塞情况。在车辆路径问题的一般模型中,道路网络信息主要是指供应点与需求点之间的距离,车辆行驶距离是成本最小化与最短时间优化目标需考虑的一般因素。(3)受灾区需求点信息:包括各需求点对各种物资需求量、物资需求的时间窗限制以及各物资的需求紧急程度。对于应急类的车辆路径问题,需要明确各灾区的需求量与各灾区的需求时间窗。作为考虑运输不同类物资的车辆路径问题,需要引入需求紧急程度,以此量化不同物资的需求对于时间的敏感度。3.1.2系统的优化过程(1)优化目标:使总体应急物流调度计划的运输效率最高。在应急物流车辆路径问题所需实现的多目标优化问题当中,既要考虑车辆行驶产生的成本,又要考虑时间的紧迫性。因为车辆行驶成本最小化与时间窗限制不能同时得到满足。运输计划往往因为达不到时间窗的要求,所以在系统的优化过程中加入超过时间窗的安全违背成本,将车辆的行驶成本与安全违背成本之和作为系统优化的总体目标。车辆的行驶成本与安全违背成本之和越小,则总体的运输效率越高。图3.1应急物流车辆路径问题的优化系统(2)量化指标:对未满足需求点时间窗要求的运输线路乘以相应的惩罚因子,从而使得该运输路线产生相应的应急安全违背成本。对于不同物资的需求紧急程度赋于权重值,度量运输不同物资的车辆路线出现未满足时间窗情况下的应急安全违背成本。3.2应急物流车辆路径问题的模型构建3.2.1问题描述本文所构建的模型属于多供应点多需求点的带软时间窗非满载类车辆路径优化问题。非满载车辆路径问题指各个需求点的需求量都小于运输车辆的载重负荷,每辆车可以完成一个以上需求点的运输任务。应急物流车辆路径问题模型可以描述为m个供应点,n个需求点。供应点与需求点依次从1至m+n排序。运输计划的车辆行驶成本为车辆的固定成本(与使用车辆的数量呈正比)以及车辆行驶的可变成本(与总行驶距离呈正比)之和。运输计划的安全违背成本为各需求点的安全违背成本之和(考虑到达需求点的时间是否在时间窗内)。运输计划的总成本即为车辆行驶成本与安全违背成本之和。总成本越小、总效率越大。求:总体效率最大化的应急物流车辆路径问题的调度计划。3.2.2问题假设(1)要求每辆车的子路径上送往各需求点的货物重量总和Gk<q;k表示第k辆车,Gk表示车辆k运输线路上经过的所有需求点的需求总量;(2)每辆车同时运输两种物资,每个需求点的物资运输任务只能由一辆车来完成,非满载类VRP问题需求点的需求量小于车辆载重负荷;(3)每辆车可从任一供应点出发,并返回任一供应点;(4)每辆车不重复经过任何一点。完成运输任务的车辆返回到距离最后一运输任务所到达需求点最近的供应点。(5)未考虑运输任务过程当中装货与卸货的时间损耗;(6)所使用的车辆类型一致,即载重负荷相等;(7)运输过程当中,所有车辆只单向运输,即只送货而不在需求点装货。3.2.3应急安全违背成本的量化应急安全违背成本就是因运输过程当中,需求点对不同物资的需求的时间窗限制未得到满足而产生的影响到相应灾区群众生命安全的成本。在本文的模型当中,结合各灾区需求点的时间窗限制、不同物资的需求紧急程度,通过惩罚函数的形式将应急安全违背成本量化,以完善目标模型。(1)时间窗限制的惩罚函数对于未满足时间窗限制的运输路线调度方案,所产生的应急安全违背成本将通过惩罚函数表达出来,到达某一指定需求点的时间距时间窗越久,那么这一点的应急安全违背成本就越高,而在时间窗内到达某一指定需求点,则这一点不产生应急安全违背成本,所有需求点的应急安全违背成本之和即为运输线路调度计划的应急安全违背成本。对于某一指定的需求点其应急安全违背成本的惩罚函数可以按如下方式表示:本文所采用的时间窗限制为软时间窗限制(第二章中已做介绍),即未满足时间窗限制所产生的惩罚随到达时间距时间窗的间隔改变。从上述公式可以看出单个需求点的应急安全违背成本与惩罚参数、到达时间与时间窗的两端临界值的差成正比例关系。不同物资的应急安全违背成本量化。对于不同物资的应急安全违背成本的度量，对物资需求紧急度高的物资,如果运输计划的到达时间未满足其时间窗要求,则应急安全违背成本的增加相对弹性更大,需求紧急度低的物资,应急安全违背成本的增加相对弹性较小。对于任何一个需求点来说,都同时存在对物资A与物资B的需求。因此,对于任何一个运输调度计划,每个灾区需求点上的应急安全违背成本都同时包括物资A与物资B各自引起的应急安全违背成本,具体表述如下:3.2.4车辆载重负荷与道路阻塞(1)车辆载重负荷对于3.1节问题描述中的车辆载重负荷限制,如果车辆出现超重行驶,则相应引发安全违背成本的增加。这对此问题的量化,在本模型中同样采取惩罚函数的形式表述:当车辆实际载重小于车辆载重负荷时,安全违背成本为0。当车辆实际载重大于车辆载重负荷时,安全违背成本产生,并且本文模型假设中硬性规定车辆不得超负荷行驶,故M*的取值是一个足够大的正整数,以保证一旦发生超载行驶,运输调度计划的效率将降到足够低,从而在优化过程中杜绝车辆超载行驶的出现。(2)道路阻塞道路阻塞情况的出现,必然导致应急物流车辆路径在优化过程当中的路径选择上存在限制。本模型中将道路阻塞情况考虑为阻塞路段不可行驶,具体表述如下:3.2.5模型的建立分别介绍了应急安全违背成本、车辆行驶总成本、车辆超载行驶以及道路阻塞的量化过程。模型的总目标函数可以通过上述的几部分综合而得出:运输调度计划的总成本=车辆行驶成本+应急安全违背成本单个灾区需求点的应急安全违背成本包括物资A与物资B两种物资所引起的违背成本之和,总体运输调度计划的应急安全违背成本为各个灾区需求点的应急安全违背成本之和。可以推出运输调度计划的应急安全违背成本:可得到应急物流车辆路径问题的优化模型的目标函数:4.求解应急物流车辆路径问题的自适应遗传算法设计4.1染色体构造对于应急物流车辆路径问题中的多供应点多需求点运输模型,算法在染色体的构造上采取自然数的序号编码形式,在遗传空间内的染色体结构为长度为需求点数量的随机自然数编码,而遗传空间的染色体经过一定的规则可言转换为实际问题的运输计划,具体如下:(1)根据运输网络的路段长度,判断g中第一点距离供应点“1”近还是距供应点“2”近,将较近的供应点加入到第一个序号之间,如果点“19”距供应点“1”较近,则:根据车辆负载的限制,计算从第一个供应点开始运输线路上的需求点的累积需求量是否超过车辆负载。假设需求点“19”、“11”、“14”、“9”的需求总和重超过了车辆负载,则在需求点“9”之间插入距上一个需求点“14”较近的供应点,假设为“3”,则 4.2种群初始化对于本文中应急物流车辆路径问题的遗传算法求解过程的种群初始化,需结合上一小节中染色体的构造、种群规模的设定来完成。在Matlab7.1软件中,单个染色体的生产采用randperm函数随机生成代表需求点的序号排列。初始种群可以表示为：4.3适应度函数由于本文中应急物流车辆路径问题的目标函数为最小化的优化目标,所以其遗传算法的适应度函数可以取目标函数的倒数,即目标函数的值越小,适应度越大,个体越优秀。为了简化算法流程,在遗传算法的操作过程中,直接将适应值,即目标函数的值作为评价指标;目标函数越小,个体性能越优秀。染色体的适应值的计算流程如下:(1)划分子路径。根据每段子路径上各需求点需求的重量之和不能超过车辆载重的原则,将染色体划分为若干个子基因段,每条基因段代表一条子路径。得到的子路径数量即为所需的车辆数量。(2)子路径连接供应点。将每条子路径的首尾两端的需求点连接上距离最近的供应点。(3)计算各子路径运输成本。各条子路径的运输距离乘以单位运输成本(4)计算运输计划的总车辆运输成本。包括单位运输成本与车辆启动成本。对于种群规模为popsize的群体,其适应度的评价流程如图4.1所示。图4.1适应度评价函数流程图4.4选择算子本文采取轮盘赌法与最佳个体保存法相结合的选择算子。它能够使适应度高的个体以较大的概率进入下一代,能提高种群的平均适应度。但是轮盘赌法采取概率的随机选择方式,这样就不能保证在每一代的选择过程中,优秀的个体都能被复制进入下一代,从而不能够保证每一代种群的最优个体的适应值逐步减小,收敛性得不到保证。为此,本文将最佳个体保存法进入选择算子中,将每一代种群中排名在前两位的个体直接进入到下一代中,不进行交叉、变异操作。这样就能够使最优个体不被破坏,使进化过程最优解逐步收敛。选择算子的操作步骤如下:(1)将种群按个体适应值由小到大进行排序。适应值低,适应度高。(2)保证排名前2位的最佳个体,直接进入下一代。(3)从排名第三的个体开始运用轮盘赌法进行选择复制,产生中间群体。4.5交叉算子1.适应交叉算子本文采用自适应的交叉算子,其交叉概率不是固定的0到1的某一值,而是由每一代种群中最优个体的适应值与其它个体的差额关系所决定的。交叉概率的计算步骤如下:(1)搜索种群中个体的最小适应值,记为min;(2)搜索种群中适应值小于平均适应值的所有个体;(3)计算适应值小于平均适应值的所有个体的平均值,记为f;(4)交叉概率表示如下:2.两点、顺序交叉法本文采取两点、顺序交叉法,对于任意的两条染色体,具体的交叉过程如下:(1)根据随机生成的两点交叉点讲两条染色体分别划分为三段;(2)分别将两染色体的中间基因段复制到另一染色体的首端;(3)将复制前的两染色体中的与所复制的基因段中有重复的序号逐步删除。例如以下两条染色体的交叉过程,假设交叉点未5和15:5.结论 本文对于应急物流车辆路径问题的研究是以探索的目的进行的,由于理论与水平、时间与硬件水平的限制,本文的研究还有一些不足与有待完善之处。以下几点可作为未来的研究方向:(1)