免费下载
网站简介

找论文变得更简单!

帮找论文

当前位置:

重点论文网    管理论文    物流管理论文    基于遗传算法的物流配送路径选择
创建时间:07-10

基于遗传算法的物流配送路径选择


Based on genetic algorithm to choose the path of logistics and distribution

内 容 摘  要

如何解决物流成本过高的问题是摆在政府和企业面前的一个亟待解决的难题。而对于一些处在城市配送业前线的物流企业来说,如何选择一条合理的配送路线成为了阻碍他们发展壮大的一个紧瓶。而本文则通过用最小包络法确定潜在设施的位置以及它所服务者的客户和用遗传算法下选择最优路径,从而确定最优路径,以此来提高物流配送系统的效率,降低物流配送的运输成本。

关键词:遗传算法、LRP、优化选择

 
ABSTRACT

It is a real problem that logistic cost is too high and it is also a difficulty facing the government and companies。 For those logistics companies on the front line of distribution industry, how to chose a proper distribution line seems to be even more important  Based on the genetic algorithm, my thesis tries to make research on the arrangement of distribution line by applying two-stage heuristic algorithms as well as the machine language emulation technique。 There are two main tasks in the two stages of heuristic algorithms: How to know the position of the facility and the customer; and how to use the genetic algorithm to choose the best distribution line。
My thesis is aimed to discuss how to program these tow tasks in two-stage heuristic algorithms and at the same time input all kinds of data。 By doing this ,we are able to find the best distribution line and improve the efficiency of distribution allocation system  and reduce  logistic cost 。

Key Words: the genetic algorithm,LRP,optimization
 
  
目 录
第一章 引言    1
第一节 选题的背景及意义    1
第二节 研究的主要内容    4
第二章 定位—运输路线安排问题的描述    5
第一节 定位—路线安排问题的综述    5
一、LRP的含义    5
二、LRP的发展历程    6
三、LRP与LA和VRP的比较    6
四、LRP的分类    7
五、未来LRP问题的研究方向    8
六、LRP问题的求解方法    9
第二节 遗传算法    10
一、遗传算法(GA)的基本原理    10
二、遗传算法(GA)的特点及应用    11
三、遗传算法(GA)的要素及其实现步骤    11
四、遗传算法的缺陷    14
第三章 单目标LRP问题模型的建立及分析    15
第一节 单目标LRP问题的描述    15
第二节 单目标定位—运输路线安排问题(LRP)的数学问题    15
一、模型中的决策变量    15
二、模型中的参数含义    15
三、模型的建立    16
四、两阶段启发式算法求解单目标LRP问题    17
第三节 实例分析    21
第四章 结束语    26
【参考文献】    27
致  谢    28
 

第一章 引言
2019年3月10日,国务院转发《物流业调整和振兴规划》,正式通知各省、自治区、直辖市人民政府、国务院各部委、各直属机构,振兴物流业以应对金融危机对实体经济造成的冲击。其规划目标大致如下:力争在2019年改善物流企业经营困难的状况,保持产业的稳定发展。到2011年,培育一批具有国际竞争力的大型综合物流企业集团,初步建立起布局合理、技术先进、节能环保、便捷高效、安全有序并具有一定国际竞争力的现代物流服务体系,物流服务能力进一步增强;物流的社会化、专业化水平明显提高,第三方物流的比重有所增加,物流业规模进一步扩大,物流业增加值年均递增10%以上;物流整体运行效率显著提高,全社会物流总费用与GDP的比率比目前的水平有所下降。
然而就中国目前的物流业来说,特别是在作为民营经济比较发达的浙江地区,多而小,密而杂,杂而乱,很多物流线路被重复,造成资源很大浪费,所以对于物流路径的优化选择是一个亟待解决的问题,它直接关系着振兴物流业这宏伟大计的成败。


第一节 选题的背景及意义

当今物流环境已经解决了区域限制。由于缺乏管制和全球化的限制,许多物流管理者面临位置—分配运输上的困难。许多管理学家开始用集成化物流系统技术区解决相关的问题。这些技术的核心是综合定位—运输模型。通常条件下,综合定位——运输模型能够解决关联的优化数目、容量、设施位置等优化问题。其主要目标是实现协调的、有效的配送,并且实现货物的完整移动。
近年来,国外许多学者对物流系统优化问题进行了一定的研究,构建了解决实际问题的优化模型,并找到了一些求解方法。比如定位—运输路线安排问题(LRP)、运输—车辆安排问题(VRP)、定位—配给问题(LA)并取得一定的进展。随着集成化物流管理的概念被越来越多的企业所接受和全球贸易的快速增长,提高分销效率成为了企业生存和发展的必由之路。LRP更贴近目前物流系统的实际特征,所以对其研究有十分现实的意义。
电子商务不但作为一套全新的技术,而且作为一种全新的管理理念,在我国发展势头强劲。但是在其发展过程中,必然存在一些具体的问题亟待解决。因此,针对基于电子商务的城市物流配送路径优化LRP问题进行研究具有重要的现实意义。
然而,就目前的城市物流配送,还存在着如下这些问题:
1.    服务水平、质量较低。信息流和物流的矛盾会导致整个电子商务客户服务水平的低效。电子商务的特征要求有与其相应快速、高效响应的物流配送关系。
2.    控制物流成本困难。人工调度的传统的物流配送只适合在交易量较小的系统操作,面对巨大交易量的电子商务环境,需要建立合理的、自动的物流配送调度系统。
3.    影响城市交通状况。物流配送调度的不合理,会增加物流配送的运行车次、路程,从而加重城市交通运输负担。因此建立合理的物流配送调度系统,有利于缓解拥挤的城市交通。
为解决上述三个问题,合理的城市物流配送调度应满足如下三个目标:
1.    准时运输。即货物按客户要求的指定时间段被运输到客户手中。
2.    总成本(包括运输路线成本,建立和运营仓库的固定成本,获得运输工具成本等)最小。
3.    车辆运输总路径最短。
综上所述,物流配送路径优化选择的研究对于企业可以降低成本,提高顾客满意度,实现利润最大化;而对于国家,可以实现其振兴物流的规划目标,降低整个社会的物流成本以及缓解金融危机对我国的冲击,为我国经济健康、稳定的可持续发展做出贡献。因此,企业物流配送的路径优化是一个非常值得研究的问题。
而对于研究物流配送的路径选择的方法,近年来也有了特别的发展。进入90年代,遗传算法迎来了兴盛发展时期,无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃,不但它的应用领域扩大,而且利用遗传算法进行优化和规则学习的能力也显著提高,同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展,这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。
随着应用领域的扩展,遗传算法的研究出现了几个引人注目的新动向:一是基于遗传算法的机器学习,这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合,这对开拓21 世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展,而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象,其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象,而遗传算法在这方面将会发挥一定的作用,五是遗传算法和进化规划(Evolution Programming,EP)以及进化策略(Evolution Strategy,ES)等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的,同遗传算法一样,它们也是模拟自然界生物进化机制的只能计算方法,即同遗传算法具有相同之处,也有各自的特点。目前,这三者之间的比较研究和彼此结合的探讨正形成热点。
1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子(Adjacency based crossover),这个算子是特别针对用序号表示基因的个体的交叉,并将其应用到了TSP问题中,通过实验对其进行了验证。
D.H.Ackley等提出了随即迭代遗传爬山法(Stochastic Iterated Genetic Hill-climbing,SIGH)采用了一种复杂的概率选举机制,此机制中由m个“投票者”来共同决定新个体的值(m表示群体的大小)。实验结果表明,SIGH与单点交叉、均匀交叉的神经遗传算法相比,所测试的六个函数中有四个表现出更好的性能,而且总体来讲,SIGH比现存的许多算法在求解速度方面更有竞争力。
H.Bersini和G.Seront将遗传算法与单一方法(simplex method)结合起来,形成了一种叫单一操作的多亲交叉算子(simplex crossover),该算子在根据两个母体以及一个额外的个体产生新个体,事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时,文献还将三者交叉算子与点交叉、均匀交叉做了比较,结果表明,三者交叉算子比其余两个有更好的性能。
国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2012年,戴晓明等应用多种群遗传并行进化的思想,对不同种群基于不同的遗传策略,如变异概率,不同的变异算子等来搜索变量空间,并利用种群间迁移算子来进行遗传信息交流,以解决经典遗传算法的收敛到局部最优值问题
2014年,赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象,提出了一种用基因块编码的并行遗传算法(Building-block Coded Parallel GA,BCPGA)。该方法以粗粒度并行遗传算法为基本框架,在染色体群体中识别出可能的基因块,然后用基因块作为新的基因单位对染色体重新编码,产生长度较短的染色体,在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。
2015年,江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。
第二节 研究的主要内容
第1章介绍了在当前金融危机下我国对于物流业发展的目标、政策,并对此重点详细介绍了目前在城市物流配送中存在的问题以及解决这一问题时应满足的目标,进而分析出进行集成化LRP选题的重要性,引出该选题的意义。
第2章综述了LRP问题及其优化算法,对定位-运输路径安排问题的起源,发展以及分类作了简单的介绍。同时也对遗传算法的步骤做了详细的描述。
第3章简单概述了单目标LRP模型的表示方法和求解方法;详细介绍了单目标LRP问题的数学模型以及要对此求解的遗传算法,并对此做了一些简单的概述,通过对遗传算法的各个步骤行分析,进行优化。
第4章作为结束语,对全文进行了总结。介绍了一些未来需要进一步研

最新论文

网站导航

热门论文