基于遗传算法的配送路线优化研究.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：2.46M 资料格式：pdf 举报版权申诉

garycool-3299689-4744302542989142345.pdf-第1页.png

第1页 / 共52页

garycool-3299689-4744302542989142345.pdf-第2页.png

第2页 / 共52页

garycool-3299689-4744302542989142345.pdf-第3页.png

第3页 / 共52页

garycool-3299689-4744302542989142345.pdf-第4页.png

第4页 / 共52页

garycool-3299689-4744302542989142345.pdf-第5页.png

第5页 / 共52页

garycool-3299689-4744302542989142345.pdf-第6页.png

第6页 / 共52页

garycool-3299689-4744302542989142345.pdf-第7页.png

第7页 / 共52页

garycool-3299689-4744302542989142345.pdf-第8页.png

第8页 / 共52页

封面

文摘

英文文摘

声明

第一章绪论

1.1引言

1.2课题的提出及研究意义

1.3 VRPTW国内外研究现状分析及待解决的问题

1.3.1国外关于VRPTW问题的发展及研究现状

1.3.2国内关于VRPTW问题的发展及研究现状

1.3.3国内外研究中待解决的问题

1.4本课题的研究内容和研究方法

第二章城市物流配送中带时间窗的车辆路径问题研究

2.1城市物流特征及发展城市物流意义

2.1.1城市物流

2.1.2城市物流特征

2.1.3发展城市物流的意义

2.2车辆路线问题

2.2.1车辆路线问题简介

2.2.2车辆路线问题分类

2.3一般车辆路线问题模型

2.4车辆路线问题的求解算法

2.4.1组合优化问题

2.4.2计算复杂性

2.4.3精确优化方法

2.4.4启发式方法(Heuristics)

2.5车辆路径问题及带时间窗的车辆路径问题的应用

2.6小结

第三章遗传算法的理论基础及应用

3.1遗传算法的产生及思想

3.2遗传算法的数学基础

3.2.1模式定理

3.2.2 Walsh模式变换及欺骗问题

3.2.3隐含并行性

3.2.4算法的收敛性

3.3遗传算法的特点及其应用

3.3.1遗传算法的特点

3.3.2遗传算法的应用

3.4遗传算法的研究现状

3.5遗传算法的基本步骤

3.6小结

第四章遗传算法在带时间窗的车辆路径问题中的运用

4.1带时间窗的车辆路径问题模型

4.2遗传算法求解带时间窗的车辆路径问题

4.2.1染色体的编码与解码

4.2.2初始群体的生成

4.2.3适应度函数

4.2.4选择策略

4.2.5交叉概率、变异概率

4.2.6交叉算子

4.2.7变异算子

4.2.8算法终止规则

4.3算法试验分析

4.4小结

结论与展望

1.论文结论

2.论文展望

参考文献

攻读硕士研究生期间发表的论文

致谢

Y洲1㈣527㈣3Ⅲ4Ⅻ7分类昏“el盔舅10710—200512087，蟛，壤孝太海硕士学位论文基于遗传算法的配送路线优化研究导师姓名职称申请学位级别论文提交日划学位授予单位顾Jj学科夸业名称载运T具运Ⅲ工程2000年5月20El论文菩辩目期2000年5月27R咎辩委员会主席学位论立抨阅^

摘要随着物流业在我国的不断发展以及物流专业化水平的不断提高，我国物流配送业近年来也得到了迅速的发展。在物流配送活动中，配送车辆路线优化问题是配送合理化的核心问题，时间窗约束在配送路线优化过程中具有举足轻重的作用。因此对带时间窗的车辆路线问题进行研究具有一定的理论价值和现实意义。本文对单站点、非满载带时间窗城市物流配送的车辆路线问题进行了研究。首先从城市物流入手，分析了城市物流的特点和分类属性及车辆路线问题的主要应用领域。在基本车辆路线问题模型的基础上建立了带时间窗车辆路线问题的数学模型。对带时间窗的车辆路线问题设计了改进的遗传算法。论文采用自然数编码的方法，初始群体的生成采用混合方式，即部分随机生成、部分根据初始解生成，选择策略采用轮盘赌选择法和截断选择法相结合的方法，用改进的边重组法代替常用的PMX、OX、CX交叉法。根据设定的终止条件，最终取得满意解。最后，通过C++实现了算法，用Solomon测试数据里C101中25个客户集的数据进行验证，并与不同算法所得解进行对比，其求解结果和计算时间都有明显改进。本文所得结果，在基于遗传算法求解城市物流配送车辆路径问题领域和物流系统的开发中具有一定的参考价值。关键词：遗传算法车辆路线问题时间窗城市物流

AbstractWiththecontinuousdevelopmentoflogisticsindustryandtheconstantlyimprovementofthespecializationleveloflogisticsinourcountry,logisticsdistributionindustryhasalsobeendevelopedquickly．Ofalltheactivitiesindistribution，thevehicleroutingproblemisthekeyproblem．Thewindowsisimportantintheoptimizationaboutthevehicleroutingproblem．Theobjectofthispaperistoresearchthesingle—depotvehicleroutingproblemwithnotfullloaded．Firstlyitintroducescitylogistics，thenanalysesthecharacteristicsandtheattributesofitandthemajorusedareasofthevehicleroutingproblem．Abovethebasicvehicleroutingproblem，thispaperfoundsthemathmodelofthevehicleroutingproblemwithtime．windows．Thispaperadoptsimprovedgeneticalgorithmtosolvethevehicleroutingproblemwithtime-windows．Thegeneticalgorithmchoosesthenaturedatacodingmethod，theinitialgroupadoptedmixedmethodwhichgeneratedpartlybyrandomlyandpartlybygeneration,selectionstrategyadoptedthemethodofcombiningroulettewheelselectionandtnmcationselection，andtheimprovededgerecombinationcrossoverinsteadthecommonlyusedPMX，OXandCX．Itgotasatisfactorysolutionaccordingtotheterminationoftheconditions．Finally,thealgorithmrealizaedbyC++，verifiedwiththetestdataintheSolomonC101customersin25setsofdata，andcomparedwithdifferentalgorithm，fondthatthecomputertimecostandresultshavemakedimprovementobviously．Theresultsinthispaperwhichbasedongeneticalgorithminthecitylogisticsanddistributionvehicleroutingproblemareasandthedevelopmentofthelogisticssysternhassomereferencevalue．Keywords：geneticalgorithmvehicleroutingproblemtime-windowscitylogistics

论文独创性声明本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表的成果。本声明的法律责任由本人承担。论文作者签名：支球川年r月矽El论文知识产权权属声明本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为长安大学。(保密的论文在解密后应遵守此规定)论文作者签名：良披导师签名：2佳易俐年．I-月矽El础对罗日

长安大学硕士学位论文1．1引言第一章绪论在全球经济一体化的进程中，物流作为“第三个利润源泉"，以其先进的组织方式和管理技术，出现在一系列与高科技相结合和实行现代管理的新兴产业中。物流产业自诞生以来就不断蓬勃发展，至上世纪90年代，物流产业已经在发达国家和地区的国民经济领域占据了十分重要的地位，譬如1996年英国的物流产值占GDP的比重已经达到lO．63％，而欧洲工业化国家的社会物流总成本一般相当于国内生产总值的12％左右。物流成为现代经济的重要组成部分，在国民经济和社会发展中发挥着重要作用。可以说，发展现代物流对于提高国民经济运行的质量和效益，优化资源配置，改善投资环境，促进企业结构调整，提高国家经济实力，具有十分重要的意义【H】。物流是指原材料、产成品从起点至终点及相关信息有效流动的过程。运输、储存、包装、装卸搬运、流通加工、配送和信息是物流的基本功能，其中运输和配送是物流系统最主要的功能，对整个物流系统的效率起着关键作用。黄晓英和张剑芳【5】发表的文章指出，根据一般综合分析计算社会物流费用，运输费占60％的比例，有些产品运输费用甚至高于产品的生产费用。可见，运输成本是影响物流成本的重要因素，运输成本的大小直接影响到物流总成本的大小。据一份来自世界银行的报告称：如果中国物流成本占国内生产总值的比例，由目前的16．7％降低到15％，每年将为全社会直接节省约2400亿元的物流成本。因此，控制物流总成本的根本是降低运输成本，这对我国经济建设有着十分重要的意义。物流已经发展成为我国经济发展中的热点之一，特别是由于城市经济快速发展和城市化进程的不断加快，导致了以城市为依托的物流服务需求不断增长，城市物流发展成为热点中的热点。由于在我国城市经济发展和城市化进程不断加快的过程中，产生了愈来愈严重城市交通拥挤问题，特别是经济中心城市，交通效率问题比一般城市更为突出。为提高城市交通的效率，几乎所有经济中心城市均出台了限制程度不同的禁止货运车辆在交通流量较大城区通行的交通管制政策。虽然这种政策对部分解决城市的交通问题具有一定作用，但是，随着城市在工业加工、商贸流通等产业发展集约化、规模化程度的提升，以及城市居民生活水平的提高，城市生产、生活对优质、高效物流配送服务的需求也越来越强烈，城市交通管制及管制范围的不断扩大，无疑对城市物流效率和满足城

第一章绪论市的物流配送提出了更高的要求[6-71。1．2课题的提出及研究意义当前，物流的现代化水平不仅成为反映一个国家现代化程度和综合国力的重要标志，也成为城市经济发展水平的体现。城市物流配送，它不但给供应者和需求者带来降低物流成本、享受优质服务的直接效益，而且还能为社会节省运输车次、缓解交通压力、减少运输污染、保护生态环境等作出贡献。而今，由于小批量、多批次等及时配送方式的发展，运输费用正在逐年提升，许多企业的运费已经超越了库存费用，城市交通与改善物流的矛盾也愈演愈烈，城市交通混杂、阻塞、车辆噪音、尾气污染、车祸事故和能源浪费等现象更加严重，若物流路线选择的不合理，还会使物流配送的行车路程变长，导致载运车辆增加，从而使本已拥挤的城市交通加重负担。以上问题均需要选择合理有效的运输路线来减少重复运输、倒流运输、迂回运输、单程运输和空驶等，这样不仅提高配送效率，控制了物流成本，而且还可限制车辆在城市中的运行时间，有效缓解城市交通负担。针对以上情况，本研究课题拟采用经典的车辆路线问题模型，结合配送时间窗要求来优化配送线路，即运用VRPTW使得配送体系合理化。1．3VRPTW国内外研究现状分析及待解决的问题1．3．1国外关于VRPTW问题的发展及研究现状自从1959年跳ig和Rams一8】首次提出车辆路径问题以来，车辆问题(VRP)一直为众多的研究者所关注。有时间窗车辆路径问题(Ⅵ强TW)是基本VRP的一个特殊类，按照集合论的观点，VRPTW是VRP的一个真子集。1985年，Savelsberght9】证明了VRPTW是一个NP(Non--linearProblem，非线性规划)问题，很难求得问题的最优解。目前，国内外专家和学者对其求解主要集中在启发式算法，用以求得问题的近似最优解(可行解)。1964Clarke矛1]Wright[101提出一种较有效的启发式算法叫larke．WrightS"乡4J算法。PaessensI¨1等人通过使用适当的数据结构，降低了它的复杂度，Clarke—Wright法随后成为许多专家和学者研究V】RJPTw的基础。1968年，Rao[12】等人在Balinski的VRP集分割【13】的基础上引入了列生成法进行求解，这种算法本质上是最短路径算法，同时结合了分枝定界算法，Desroche曾用它求解了有100个客户的VRPTW。1981年Fishedl4】等人针对带2

长安大学硕士学位论文能力约束、时间窗口以及无停留时间的VRP，提出了三下标车辆流方方程。Thangiahtl5l(1991年)和Joe[16】(1993)，分别用遗传算法求解了VRPTW，但是都存在“早熟收敛"的问题。1994年，RWark[17】等人提出了重复匹配的方法，该算法在其模型里同时考虑了时间约束和能力约束，因此适用于这类具有强约束的VRP，另外，重复匹配算法也可求解较大规模的VRP。1999年，Gambardella[18】等提出一种MACS(MultipleAntColonySystem)系统用来解决VRPTW，是以蚁群算法为基础，主要设计用来解决2个目标函数的VRPTW，一个是使车辆数最小，另一个是使时间最短，而最主要的目标是使时间最短，该算法只在总体上优于其他算法，求解具体问题时优势不是很明显。2003年，Baker[19】等对不确定车辆数的VRPTW进行了改进的遗传算法优化，取得了较为理想的效果。1．3．2国内关于VRPTW问题的发展及研究现状在国内，一些专家和学者也在尝试研究VRPTW。1998年，李大卫【20】等对适用于旅行商问题的最近距离搜索启发式算法进行修正，构造出评价函数，并据此提出一个求解VRPTW的启发式算法。2000年，谢秉磊【21】等将货运量约束和时间窗约束转化为目标约束，设计了基于自然数编码的可同时处理有软、硬时间窗VRP的遗传算法(GA)，得到了较好的结果。2001年，周贤伟f221等根据车辆装载GPS设备的特性，建立了VRPTW的数学模型，设计了相应的GA。2002年，张丽萍【23】等通过引入新颖交叉算子，构造了一种改进的GA，该算法摆脱了对群体多样性的要求，不存在标准GA常见的“早熟收敛"问题，可用于解决VRPTW。2003年，宋厚冰【24】等针对VRPTW，在标准GA的基础上，将分组信息与每一个染色体结合，并辅以交换局部搜索技术，构造了一种GA，使得求解结果更接近最优解。同年，宾松【25】等用一种新的编码方法及交叉和变异概率的自适应机制，构造了改进的GA求解VRPTW。2004年，刘小兰【26】等为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽VRP的缺陷，介绍了VRPTW的通用数学模型，并通过分析各主要变量之间的关系，设计了一种简单、快速的确定性初始算法，同时引入“短路径优先策略"构造了改进的大规模邻域搜索算法，该策略也可嵌入到求解时间窗比较窄的VRP中，达到加速搜索的目的。2005年，刘诚【27】等针对GA在求解VRPTW时初始种群的单一性，提出一种并行遗传算法，该算法对不同的种群用不同的初始化方法一随机初始化法和构造初始化法，效果比较理想。2006年，杨宇栋【28】等引入客户直接排列的解的表示方法，改进了模拟退火算法，提高了求解VRPTW的效率。3

第一章绪论1．3．3国内外研究中待解决的问题从车辆路线问题提出，直到研究的重点已放在精确优化算法和新兴人工智能算法的今天，国内外对于VRPTW问题的研究都取得了很大的进步，广大学者对此也有了越来越多的关注，但是从国内外的文献中都可以看出，在求解VRPTW问题上还存在着许多的缺陷：1)配送不但要满足客户的实物需求还要满足客户的时间需求，特别是在客户要求尽量减少库存的前提下，及时配送变得越来越重要，所以满足客户的时间窗口是制定车辆路线优先考虑的重点，但是目前的研究对于这一点还没有足够的重视和考虑。2)目前多数配送路线问题的研究都局限于具有确定性参数的模型，也就是固定路线问题的研究。实际上，每一次配送客户的数量、需求、位置以及车辆的运输时间、道路信息等事先并不一定知道，应把它们当作随机变量来看待，这一点还有待于进一步的研究。3)现有的配送路线的研究多为开发静态的模型，很少分析参数随时间变化的特性。例如，仓库位置的成本将随时间变化；在一定的时间范围内，公司需要根据情况的变化来重新决策配送中心及销售网点的分布。因此，在配送路线模型中加入动态特性，实现实时或在线物流管理，会极大地提高与现实接近的程度。4)车辆路线问题的求解方法现阶段以启发式为主，而人工智能这种未来发展方向的方法却没有被很多的研究和采用。5)现有启发式解法多是针对某一类型问题求解，本质上不具有通用性，因此，今后应设计高效的通用性启发式算法。1．4本课题的研究内容和研究方法本研究课题重点研究大规模VRPTW模型的智能方法。针对我国城市物流配送特点，建立满足城市物流配送的VRPTW模型并找出有效智能算法。由于VRPTW问题属于NP．hard问题，运用常规优化方法难以进行求解，故拟采用遗传算法对理论模型进行算法设计，如对遗传算法中的参数进行数值模拟计算，找出较好的参数搭配，分析算法对解的质量影响，并运用Solomon标准测试数据进行计算结果测试。通过计算机编程，在可接受的计算时间内得到满足一定精度的相对最优化解，最终找出解该类问题有效的遗传算法，为解决城市物流大规模配送问题奠定理论基础。本项目研究的技术路线如图1．1所示：4

分享到：

赞收藏

资料库

基于遗传算法的配送路线优化研究.pdf

相关推荐

课程资源

热门标签

最新资料