基于遗传算法解决CVRP的研究

。公路物流运价指数是反应一定时期我国的运价变动，目前采集的信息涵盖9大物流区域、38个重点城市、1406条公路运输线、200万运输车辆[6]。这个统计并不是普查数据。但是还是不难看出目前物流行业如日中天，而物流涵盖点极广，运输线路较多，运价也在呈现上升趋势。具有时间调度的物流物品会选择其他交通工具（如SF）应对特殊物品时选择了空运，成本价格也在由一部分消费者承担。其他大部分都是选择公路运输，京东为了加快物流运输直接选择建立本地仓库（只有京东自营）。但目前为止大部分物品都是选择公路运输。在路线还有物品选择时我们一辆车节约1元将会节约200万一次。而公路运输中，根据网络数据一辆车一个月会平均进行10次物流交易，一个月将会是20000万一年节约2.4亿元。而利用数学建模帮助决策，在进行决策时节约的成本又何止是1元。建立数学模型分析车辆路径及物流交换将带带巨大的财富。帮助物流运输中以最经济最节约的方案进行配送，不单单满足了物流企业节约了大量的成本同时也为消费者建立了更加完美的物流体检。下图1-2表示在社会物流中各种费用所占的比例。图1-2（物流费用所占比例）运输费用在社会物流中占据着大半江山，研究如何通过科学的物流管理，降低运输成本，提到服务质量。物流运输当中利用好科学决策对于降低运输成本，提高配送效率。为企业给顾客带来舒适，快乐，快捷的服务而且还能提高车辆利用率，道路的规避率，缩短配送周期，加快资金流动，实现经济可持续发展，节约资源保护环境都有重大的现实意义和深远的历史意义。综上所述本课题物流配送中车辆路径问题研究既能增加国民收入，加快跻身发达国家，发展节约性社会都有重大的意义。1.2国内外研究现状国外车辆路径（VehicleRoutingProblem，VRP）在提出已经有60多年的历史而且针对车辆路径问题也提出过专门的算法（如节约算法）。在国内吴斌教授于2013年专门针对目前市场上流行的各大算法及改进方法已专门成书。京东每年都会花费大量的资金进行各种研究旨在解决物流问题，在全国数学建模大赛中也是会涉及到物流分配优化课题。为什么这么过年过去了，还是没有具体的方法解决这一问题？因为这个是一个与时俱进的问题，随着生活水平的提交物流已经从国家层次走进了群众生活，以前只会涉及到进出口为题物流，近几年来淘宝、京东、拼多多的崛起，在2019年淘宝双十一活动成交额2135亿元[7]，之后就要解决物流问题。故此物流问题就是是一个与时俱进的问题，国外也没有彻底的能解决，只是在不断的完善。目前有的关于综合车辆路径问题的算法分启发算法，精确算法，智能优化算法，拉格朗日松弛算法等。本课题主要就针对车辆载重还有路径中的安排和分配，利用算法的优势互补最终达到我们想要的目的。1.3本文的内容及组织结构(1)本文主要内容本论文主要研究的是无时间窗口的车辆运输问题。主要是在固定的坐标点上寻找车辆的最佳的派送路径。主要从车辆运输物品最大化，在车辆道路情况相同下寻找出最优化的路径从而节省时间、耗油量从而给收货人最优的购物体验，给物流公司最省钱的方案。(2)本文的组织结构第一章、主要介绍出目前对于VRP的国内外现状和研究这个问题的意义。第二章、介绍了VPR中的各种情况，进行了相应的分类。第三章、对实际生活中的车辆路径问题进行了解答，以及针对相应的算法存在的缺点进行了改进。第四章、重点利用遗传算法对CVRP问题进行了相应的解答，带入实际生活中的物流规划，建立数学模型进行解答实际问题。第五章对本文的总结与展望。第二章车辆问题（VRP）的基本理论2.1VRP问题概念车辆路径问题（VRP）最早是由乔治·伯纳德·丹齐格（GeorgeBernardDantzig）和Ramser在1995年首次指出[8]，是指一定数量的用户，有着不同的需求，需要从货场进行各自的请求，货场配送中心向顾客提供配送，由车队负责分配货物，组织适当的装货任务，规划出合理的路线，最终使得客户需求求得到满足，在一定约束条件下可以达到（如：路程最短、成本最低、效率最高、费时最小等）要求。VRP问题是从旅行商问题，即TSP问题（TraverlingSalesmanProblem）和多个旅行商问题演变而来的商问。旅行问题是指：一个人从一个点出发拜访不重复的拜访所有不同地点求出出发点到目标地点的最优路径。VRP问题不同与TSP问题的最大之处是旅行商出发以后不出现重复，而VRP是需要返回货场提取货物为供货商提供货物。在多个旅行商问题中我们就可以把他看作是一个车队，车队的载货量利用贪心算法为旅行商设定好最大的旅行地点数目，把最优的路径安排出来也就成为了车辆路径问题。再加入其他约束条件就成为了车辆路径分配模型。2.2车辆路径的分类车辆路径的研究近70年的发展。衍生出重多模型，求解模型更是层出不穷。早在1983年，JeanBodin等在长达140多页的VRP研究中就，就罗列出699篇参考文献。1995年出版《运筹学与管理科学手册》[9]。2013年《物流配送车辆路径问题及其智能优化算法》都是特别针对车辆路径规划安排而成书。目前已经归类的车辆路径问题模型有：1、有能力约束车辆路径问题[10]。简称车辆路径问题。车辆路径问题约束条件较少，一般只对车辆载重还有行驶的时间进行约束。此模型研究的时间是相对于最长的而解决的实际问题也是最多的，下文中提到的大部分模型都是在此基础上的改进及完善。2、有时间窗约束的车辆路径问题[11]。该模型就是在车辆路径问题中加入了时间窗口。在实际生活中时间是最能体现一种算法的实用性，目前带时间窗口的模型研究最为广泛，大量的算法及智能模型都是由他引出的，时间窗口主要研究两个极端，最早时间窗口和最迟时间窗口的服务作文条件进行分析。3、带软时间窗和同时取送货的车辆路径问题(VRPSPDSTW)[12]。此模型提出的主要原因是根据目前的市场行业和企业。快递在生活中有着重大作用。这个问题又可以细分为：一种客户不单单需要取回货物，还需要返还的货物，即用完即还。为了使问题更加简单一般来说返还的货物直接回到货场。还有一种是从一个客户提交到另外一个客户搜集，客户之间具有时间顺序。4、周期性的车辆路径问题[13]。该模型之间就是在VPR上的一个扩展。即在一个时间周期上车辆服务用户的最多次。这个模型主要是针对食品为主。5、带有容积的车辆路径问题[14]（CVRP）。该模型是指顾客不单单是被访问，而是带有一定容积和质量的物品的装卸物品。涉及到不同类型及种类的车辆和型号的车辆安排策略。对于含有容量约束的CVRP问题。因学历和时间问题。我主要利用遗传算法及禁忌搜索进行分析，同时本论文主要研究的也是CVRP问题。2.3CVPR问题描述1、关于车辆构成问题的描述：在单一货场、送货点带有时间窗口、车辆载重、网络道路、服务是否单一、优化目标等问题。具体如下表2-3-1所示：表2-3-1（CVRP问题描述）车辆构成要素属性库场单一库场送货点有时间窗口/无时间窗口，送货/收货，静态/动态需求，客户优先顺序等。车辆车辆载货容量、载重、耗油，有/无行驶里程的限制等。道路网有线/无线网络，动态/静态/不确定网络，行驶费用，过路费等。运输要求客户由多个车辆服务/单个车辆服务，运输车需要/不需要返回货场等。优化目标最小化运输成本（车辆数、行驶路程等），用户最小等待时间，最大满意程度等。2、关于CRVP的描述：从一个配送中心出发。每个配送中心都有着G种不同类型的车辆，对一定区域的G的用户C进行物流分派服务，已知客户需求为都为相对小并且（k=1,2，…,m）。知道配送中心到客户的成本为。在不超重的情况下优化安排路线，使目标最优，配送综合费用优化。第三章基CVRP问题的描述及模型定义3.1CVRP问题描述及定义前提假设对于CVRP要在以下前提条件执行：假设所选车辆为同一类型车辆且每辆车的载重量为Q；货物可以混合装载；每个用户地点及需求为已知条件；配送中心到用户的距离为已知条件；油量或电力充足；车辆在运输过程中匀速运动；模型参数说明及数学建模输入变量用户参数：客户需求qi、数学定义：c:用户集合。i,j∈C=(0,1,2,3,…,n)。0表示配送中心，要求所有车辆都从配送中心出去返回配送中心。Cij：从用户i到用户j的配送成本。Cqi:用户i的需求量为qb、车辆参数：车辆总载重k=1mQ数学定义解释如下：Qk：车辆K的载重量是Qk，假设为同一种类型的车辆，则CCk：车辆k启用的固定成本Ck，若为同一类车辆则数据变量：Xijk:即客户i和客户j都是由车辆k来访问服务，则Xijk=1i≠j∈C,k=1,2,3,….m。在未定义好的Xijk的值为0约束条件为：车辆开始和结束都需要返回配送中心；所有的用户只被服务一次，任一配送用户数量之和不得超过车辆的负载能力。优化目标：考虑车辆启用需要固定成本和运输成本，使用的总费用最少。建立数学模型约束条件①②③④⑤⑥⑦⑧目标函数主要考虑的是固定成本和运输成本的最优化策略。约束条件（1-3）保证每次访问的唯一性约束，每个用户有且只有一辆运输服务。条件（4）保证所有车辆都从配送中心出来。条件（5）保证每条配送路径上用户的物品总质量不大于车辆的最大载重量。条件（6）保证车辆访问用户之后都回到配送中心。条件（7）和条件（8）是保证为整数。最终整理的车辆数第四章基于遗传算法解决CVRP的研究4.1算法举例遗传算法（GeneticAlgorithms,GA）该算法是一种基于生物界的自然选择和基因的遗传学原理产生的算法。它是由美国密歇根大学的JohnHolland教授和同事及学生在20世纪60年代末初步研究形成的一部较为完整的理论和算法[15]。Blanton和Wainwright[16]将该算法用于车辆路径规划问题中，算法创建主要有两个研究目的：①抽象的解释自然界演化的过程；②是为了自然界生存应用到工程系统、计算机系统和运筹学系统等设计中。遗传算法在计算机上，模拟生物的进化和基因选择，而且不需要特定的知识系统，也不需要对象搜索的连续性，遗传算法具有全局寻找最优解的能力。他和基因一样具有遗传特点，把自然界的机制融汇到现代多门科学设计的应用中，例如某些工程以及计算机系统等。在此我们列举在计算机中的运行机制，它的运行不需要某些指定的体系，它可以自动的在有限我们所规定的范围内寻找最优的答案，与遗传基因相差无几。能不断的推算最优，高度并行性。目前遗传算法在组合优化，机器学习，动态识别，图像动作处理等多个人工智能领域都有涉及，而且遗传算法开启了人工智能领域的先河，涉及到计算机方面的改进都会优先考虑遗传算法。4.2遗传算法的原理自然界的每一种生物都是由长期自然的选择而活下来的。根据达尔文的自然选择学说理论，每一种生物都具有强大的繁殖能力。在繁殖的过程中，大部分生物都是由遗传来保持物种的优秀，自然界通过自然选择，诞生适应社会的生物。我们从小便得知自然界中总是弱肉强食，既然能存在，那么每种生物便具有存在的意义，达尔文的相关论点有所提到，任何一种自然界的物种都有繁殖，不断衍生下一代的本领，而在繁殖的过程中也存在选择，那么遗传基因的优异性就不容小视。自然界中永远是适者生存，优胜劣汰，把遗传算法如图4-2所示：图4-2（遗传算法）根据生物进化原则，生物的发展和进化主要是三个条件：遗传、变异自然选择。遗传是指从父代继承的。遗传性是一切生物所共用的特别，不管是植物动物还是微生物都是具有的，遗传能够把本身具有的特征、性状等都遗传给后代。众所周知，DANA是遗传物质保持亲带相似的遗传因子。变异是指任何两个物体都会存在差异，正如达尔文说过世界上没有两片相同的叶子这就是存在一定的变异。引起变异的因素很多，比如：核辐射直接可以影响遗传因子，还有杂交（著名的杂交水稻）。生物的变异为生物的进化提供了选择，而决定进化的方向则是由自然环境选择。自然选择是指在生物圈中适者生存，优胜劣汰的一个残酷的过程（恐龙的消失）。因为有遗传的存在保持物种特性，变异又可以提供进化的基础，自然选择使得优秀的特性不断的完善从而达到一个和谐美好的生物圈。遗传算法就是基于“适者生存、优胜劣汰”的进化原则，可以使得该算法能够在一次又一次的选择中做出正确的抉择达到一个最优的结果。如表4-3所示表4-3生物遗传概念与遗传算法对应表生物概念遗传算法个体解DNA解的编码基因解的特性环境合适的数学模型群落选择好的一组最优解嫁娶不断的演化找出新的解变异实际环境中的约束条件4.3遗传算法解答过程遗传算法的解答过程：采用编码方式将解空间映射到编码空间（用数组）每个编码对应一个解，通过随机方式产生一个群落，利用约束函数对数组进行优化排序，当适应函数确定以后，自然选择出符合的最优解。最后得到满足终止条件推出算法。遗传算法流程示意如图4-4图4-4（遗传算法流程）4.4CVRP遗传算法设计针对CVRP问题路径的表示：0表示配送中心，1,2,…,n表示用户。每一条路径必须开始于配送中心结束于配送中心。这样规定好以后，1,2,…,n就不会出现重复现象而且构成随机整齐的配送路径方案。例如：0-2-3-7-0。根据问题利用遗传算法进行求解。对每一个候选解进行不断的叠加最后形成相对最优的路径。以配送中心为坐标原点不断的迭代形成可行的方案，在所有的候选方案中进行不断进行遗传、变异、选择最后形成最优解。4.5算法实例分析案例以京东物流公司分析，现在有12个用户分布于不同城市。每个用户的需求量为（单位：吨）。这些配送任务都从配送中心出发，车辆能运输的最大载货量为8吨。配送中心到用户的距离（单位：吨）。用户分布图4-5、需求量表4-6、用户分布表4-7所示图4-5（用户分布图）把地图上的用户坐标规划到平面上如图4-5图4-5（用户坐标点简化图）表4-6（用户需求表）用户点距离（公里）需求量（吨）昆明（配送中心）00曲靖252玉溪201.5昭通601.5大理1151丽江851.5临沧1561.5普洱1650.5保山1440.7迪庆1401.2红河1881.5文山901西双版纳1500.8表4-7（用户分布表）配送中心配送中心02520601107015616514414018890145200408090601251351201302001101301640050957017018016512016075706080500120751309070707030301109095120035353545901601351007060707535060605080120956015612517013035600203565909060165135180903560200306516013050144120165704550353006010011040140130120709080656560045604018820016070160120901601004505595901107530135959013011060550651501307030100606050404095650为了简化计算，假设每公里耗油成本及其他费用总和为1，所以。用同一辆车运输完成。车辆的启用成本为100元。安排合理的车辆运输路径，使运输费用最少。利用上一章模型进行求解，结果为。结果表如4-7所示表4-7（运输路线及容积变化）路线1昆明-曲靖-大理-临沧-普洱-保山-丽江-昆明容积变化7.2-5.2-4.2-2.7-2.2-1.5-0路线变化0-25-115-150-170-200-250-320路线2昆明-玉溪-西双版纳-红河-迪庆-玉溪-昭通-昆明容积变化7.5-6-5-3.5-2.3-1.5-0路程变化0-20-95-150-195-235-265-325最终根据表4-7整理得运输路线图如图4-8所示图4-8（运输路线图）4.6算法应用上面实例证明该算法的确可以节约运输成本，我们把上面的算法用C#编程把算法实现。主要代码如图4-9图4-9（该模型中主要代码）4.7模型求解我们输入50个送货点的坐标利用进行分析，利用算法可以直接把CVRP问题中的路径规划出来，结果如图4-10所示。图4-10（CVRP规划结果图）第五章本课题的总结及未来展望5.1课题总结伴随着互联网时代的到来，物流行业的兴起面向全球化、信息化、科技化一体发展，物流配送过程在物流系统中越来越重要。用户对物流的服务质量越来越高，要求时间较短、送货上门等一系列要求。物流运输的安排对于时间要求有着决定性作用，在物流分配作业中应用了运筹学，管理学等多门科学一起进行管控与调节。配送中心对于优化车辆路径、车辆配送、线路选择、车辆油耗、车辆师傅工资、货物管理等众多问题越来越关注。而且目前对于车辆管理的学术论文更加多，多种算法都在与车辆优化路径靠拢，国内京东公司针对车辆路径问题已经设立大赛，众多大学也已经开车车辆路径管理课程。企业应用学者的研究已经落到实处，不单单在车辆路径规划还在供应需求、通信线路设计、城市路径规划等多个领域都已经广泛应用，对于改善供应需求、节约通信设备及线路、优化城市交通网都取到了决定性因素。本论文针对改善车辆路径安排，从车车辆的载货量，及车辆的路径行驶进行一系列的论述及改进，还包括问题提出、研究背景、目前物流国内外现状。同时针对多辆车无时间窗口问题利用贪心算法、节约算法、遗传算法进行了实验。并分析了优缺点，针对缺点进行改进。并利用代码对有效性进行了验证。本论文研究的主要成果：1、在针对较小货场的运输车辆先利用贪心算法对其进行了路径的规划。对于该模型较小的货场具有极强的借见作用。2、针对规模较大的货场利用遗传算法找出静态规划中最短的路径。5.2未来展望本篇论文对于VRP问题都是在理论基础上进行一定的规划与安排，能适应大量静态数据中找到最优化的路线。但是实际过程中在路径最短的基础上并不一定是最优的解答会出现其他成本的损失最后将不一定是最优方案。我希望自己能过学的更加深层次的知识来补充对于在运输车行驶过程中如车辆油耗高低、车辆磨损严重与否、带时间窗口的VRP、天气问题、道路质量、变速行驶等问题进行分析及建立模型。针对在VRP中出现的一系列算法中本文只是提出了其中的集中，对于蚁群算法、粒子群优化算法、拉格朗日松弛算法等多种算法没有提出没有对各种算法的优缺点进行分析同时在缺点的基础上进行改进这些都是因为知识的缺陷，以后能对这些算法进行系统的分析及改进是我目前最大的展望。第六章致谢在论文完成之际，向导师李杰教授致以由衷的感谢和崇高的敬意!感谢李老师在我的学习中给我热情的关心和论文中的巨大帮助。在写本篇论文之处想过写一个项目当作自己的毕业论文，李杰老师说：“我们是本科生，我们的毕业论文最好是拥有算法，把我们的计算机编程能力应用到实际问题中”。讲了好几个论文题目，而且每个论文题目李杰老师都能说出一方自己的见解，可谓是博学多姿。在后来的计划中老师总是在百忙之中来帮助我们，有问题在QQ中也是会及时回复。最让我佩服的是李杰老师的知识水平，在老师面前所有的计算机编程软件可以说是无所不通。老师一丝不苟的工作态度、严谨的学习态度、深厚的学术造诣、敏捷的思想。在我写初稿及以后的修改中都有着巨大的帮助。再次向李杰老师表示衷心的感谢和深深的谢意。论文导师选择的时候我曾经犹豫了好长一段时间，一直仰慕李杰老师但是害怕自己的算法太差了，跟不上李杰老师的脚步。但是在之前的教学中我能感受老师是一位能把学生当作自己孩子的老师，课上看到学生玩手机他会苦口婆心的劝说，而且他还是我们计算机科学与技术班授课教师中为数不多的一名博士生。仰慕者学历，得知老师会指导我们的论文很紧张，害怕选择不到一位良师，最终我很开心毕业论文是他带我。事实证明我的选择没有错，老师带我们大纲、初稿、修改初稿、模拟论文答辩、及其修改。老师说过：“既然跟着我就要好好写，给其他人看到论文就知道这个学生是经过论文的培训及修改的”。再次送上我最真诚的感谢，同时愿老师身体健康，学术无限成就。感谢我的班主任邵晶晶老师，在大学期间有无私的关心及帮助在此送上最真诚的谢意。感谢辅导员教师，段君荣老师、王文佳老师，他们两位老师可以说是人生的伯乐，人生因为有了您们两位从而变得明亮。感谢教过我的朴丽莎老师、杨博宁老师、王衫老师、侯俊松老师、孙文静老师、刘玉娥老师、张云飞老师、丁艳波老师、谭清明老师、吴东恒老师感谢您们教会我不同的学科知识。送上我最衷心的感谢。感谢自己的父母及家人这么多年对我学业的支持并同我一起承担的压力。谢谢您在我漫长的求学道路上默默的支持，您们是我的精神支柱。在论文完成时也就意味着我的大学生涯结束啦。感谢您们对我殷勤的关心和默默无私的奉献与支持。第七章参考文献[1]LaporteG.Thevehicleroutingproblem:Anoverviewofexactandapproximatealgorithms[J].EuropeanJournalofOperationalResearch,1992,59(2):231-247.[2]2019年中国第三方物流行业分析及投资咨询报/[3]2019年中国物流信息中心物流交易报告./中国物流信息中心.2018年全国物流运行情况通报[EB/OL]./wltjwlyx/300920.jhtml,2019-03-2309:00:18.中国物流信息中心.公路运价指数[EB/OL]./,2020年第7周.DantzigGB,RamserJH.Thetruckdispatchingproblem[J].Man