车辆路径规划算法及其应用综述

第８期总第３０２期物流工程与管理

ＬＯＧＩＳＴＩＣＳＥＮＧＩＮＥＥＲＩＮＧＡＮＤＭＡＮＡＧＥＭＥＮＴ

物流技术

ｄｏｉ:１０.３９６９/ｊ.ｉｓｓｎ.１６７４－４９９３.２０１９.０８.０３５

车辆路径规划算法及其应用综述

(广东理工学院经济管理学院ꎬ广东　肇庆　５２６１００)

　　【摘　要】随着经济信息化的发展ꎬ车辆路径规划算法的发展变得越来越重要ꎮ对车辆路径规划算法进行综述ꎬ根据算法进行分类ꎬ列举了三种算法ꎬ分别是遗传算法、ＲＲＴ算法和Ａ~∗算法ꎮ这三种算法都存在有不同的缺陷ꎬ人们根据其求解的具体问题ꎬ对算法进行改进ꎬ并以仿真验证改进后的算法确实优于标准算法ꎮ在此基础上ꎬ对求解路径规划问题算法的研究上作了展望ꎮ

【关键词】车辆路径规划ꎻ算法ꎻ优化

【中图分类号】　Ｆ２５２.５　　　　【文献标识码】　Ｂ　　　　【文章编号】　１６７４－４９９３(２０１９)０８－０１００－０２

□顾　蕾

ＳｕｍｍａｒｙｏｆＶｅｈｉｃｌｅＰａｔｈＰｌａｎｎｉｎｇＡｌｇｏｒｉｔｈｍａｎｄｉｔｓＡｐｐｌｉｃａｔｉｏｎ

(ＧｕａｎｇｄｏｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙＳｃｈｏｏｌｏｆＥｃｏｎｏｍｉｃｓａｎｄＭａｎａｇｅｍｅｎｔꎬＺｈａｏｑｉｎｇ５２６１００ꎬＣｈｉｎａ)

□ＧＵＬｅｉ

ｍｏｒｅａｎｄｍｏｒｅｉｍｐｏｒｔａｎｔ.ＴｈｉｓｐａｐｅｒｓｕｍｍａｒｉｚｅｓｔｈｅｖｅｈｉｃｌｅｐａｔｈｐｌａｎｎｉｎｇａｌｇｏｒｉｔｈｍｓꎬｃｌａｓｓｉｆｉｅｓｔｈｅｍａｃｃｏｒｄｉｎｇｔｏｔｈｅａｌｇｏｒｉｔｈｍｓꎬａｎｄｅｎｕｍｅｒａｔｅｓｔｈｒｅｅａｌｇｏｒｉｔｈｍｓꎬｎａｍｅｌｙｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍꎬＲＲＴａｌｇｏｒｉｔｈｍａｎｄＡ≤∗ａｌｇｏｒｉｔｈｍ.Ａｌｌｔｈｒｅｅａｌｇｏｒｉｔｈｍｓｈａｖｅｄｉｆｆｅｒｅｎｔｄｅｆｅｃｔｓ.Ａｃｃｏｒｄｉｎｇｔｏｔｈｅｓｐｅｃｉｆｉｃｐｒｏｂｌｅｍｓｓｏｌｖｅｄｂｙｔｈｅｍꎬｔｈｅａｌｇｏｒｉｔｈｍｉｓｉｍｐｒｏｖｅｄꎬａｎｄｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓａｌｇｏｒｉｔｈｍｉｓｐｒｏｓｐｅｃｔｅｄ.

【Ｋｅｙｗｏｒｄｓ】ｖｅｈｉｃｌｅｐａｔｈｐｌａｎｎｉｎｇꎻａｌｇｏｒｉｔｈｍꎻｏｐｔｉｍｉｚａｔｉｏｎ

路径问题的求解ꎬ目的在于设计一条最合理的路径ꎬ使得配送代价最低ꎮ当约束条件不同时ꎬ纳闷选择求解的算法当然也不相同ꎮ

(ＣａｐａｃｉｔａｔｅｄＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍꎬＣＶＲＰ)ꎮ在此系统内ꎬ每只给出了一个约束条件ꎬ根据现实当中约束条件的不同ꎬ还有其他各种模型ꎮＣＶＲＰ只是其中最基本的模型[１]ꎮ

ＣＶＲＰ模型是有一个配送中心、若干个地理上随机分散的标准车辆路径问题就是有能力约束的车辆路径问题

ｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｉｓｉｎｄｅｅｄｓｕｐｅｒｉｏｒｔｏｔｈｅｓｔａｎｄａｒｄａｌｇｏｒｉｔｈｍ.Ｏｎｔｈｉｓｂａｓｉｓꎬｔｈｅｒｅｓｅａｒｃｈｏｆｐａｔｈｐｌａｎｎｉｎｇ

【Ａｂｓｔｒａｃｔ】Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｅｃｏｎｏｍｉｃｉｎｆｏｒｍａｔｉｚａｔｉｏｎꎬｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｖｅｈｉｃｌｅｐａｔｈｐｌａｎｎｉｎｇａｌｇｏｒｉｔｈｍｂｅｃｏｍｅｓ

　　伴随着贸易和经济全球化的发展ꎬ市场竞争愈演愈烈ꎬ人们对于效率的要求也越来越高ꎮ车辆路径规划问题逐渐引起人们的关注ꎬ并且成为人工智能和经济发展过程当中亟待要解决的问题ꎮ

截至北京时间２０１８年１０月９日ꎬ全球最权威的车辆路径规划(ＶＲＰ)问题评测系统中有二十六项世界记录是由菜鸟保持的ꎮ作为中国第一个问鼎该评测系统的研究机构ꎬ菜鸟将算法在配送中ꎬ大幅度减少车辆行驶的距离和车辆分配的数量ꎻ在仓库内部拣选作业中ꎬＶＲＰ算法大幅度减少仓库操作人员行走的距离ꎮ除此之外ꎬ菜鸟还将ＶＲＰ算法应用到外卖的配送路径规划当中ꎬ缩短外卖配送时间ꎬ增加有限时间内外卖的配送数量ꎬ极大地提高了外卖员的工作效率ꎬ提升了顾客满意度的同时又增加了外卖员的收入ꎮ１　车辆路径规划问题

ＶＲＰ可以概述为:从实际的角度出发ꎬ在各种限制条件ＶＲＰ算法优化应用到他们的各项实际操作的业务当中ꎮＶＲＰ

辆车都有限制最大载重量ꎮ这只是ＶＲＰ系统中的一种模型ꎬ

配送点ꎬ车辆从配送中心出发为这些配送点提供服务ꎬ要从众多配送方案中找出车辆行驶的最佳路线ꎬ使得整个系统配送时间最短ꎬ成本最低ꎬ同时需要满足三个条件:最大需求量ꎻ

①每辆车的最大载重量要大于或等于每条配送线路上的②每辆车的能够行驶的最大距离不小于每次交付路径所③配送中心只有一辆配送汽车[１]ꎮ

Ｄａｎｔｚｉｇ和Ｒａｍｓｅｒ[２]在１９５９年第一次提出车辆路径规划

需距离的最大值ꎻ

下ꎬ车辆从一个或者多个配送中心出发ꎬ按照一定的顺序注意经过随机分布的若干个配送点ꎬ且每一个配送点保证有且仅有一辆车经过提供服务ꎮ对于此类ＶＲＰ问题的设计就是要求规划出一条效率最高ꎬ配送所付出的代价最低的路径车辆

２　ＶＲＰ算法应用综述

的问题ꎮＶＲＰ属于ＮＰ难题ꎬ随着节点数目的越来越多ꎬ想要

【收稿日期】２０１９－０５－２６

【作者简介】顾　蕾(１９９０—)ꎬ女ꎬ河北邢台人ꎬ助教ꎬ硕士ꎬ研究方向:生产系统优化与调度ꎮ

第８期顾　蕾:车辆路径规划算法及其应用综述

１０１

求解此类问题的困难越来越大ꎬＶＲＰ对于运行时间和存储空间的要求非常高ꎬ它对于更方面知识的要求都也非常高ꎬ因此ＶＲＰ出现之后很快引起了各学科的专家、运输计划制订者和管理者的极大重视ꎮ随着电子商务的发展ꎬ带动了物流供应链系统的发展ꎬＶＲＰ也逐渐成为人们研究的热点ꎮ

模型的使用中ꎬ人们将ＶＲＰ分解成各种子问题可ꎮ根据不同的约束条件分解成各种不同类型的ＶＲＰꎮ例如:当车辆装载状况取值为:最大载重量ꎻ配送中心数目取值为:多配送中心ꎻ车型数目取值为:同车型ꎻ时间限制取值为:软时间窗ꎻ需求信息取值为:需求不确定ꎻ那么该问题就是一个载重量限性ꎬ对ＲＲＴ－Ｃｏｎｎｅｃｔ算法进行改进ꎬ并提出了改进后的算法ＤＲＲＴ－Ｃｏｎｎｅｃｔꎮ改进后的算法在起始点与目标点中间随机抽取一个节点ꎬ做为第三节点也就称之为扩展点ꎬ抽取新的节点后算法可以同时从起始点、第三节点、目标节点生成四棵随机树ꎻ同时在改进算法中引入自适应步长调节函数ꎬ当搜索不到障碍时ꎬ步长调节函数自动增大调节步长ꎬ提高四棵随机树的搜索效率ꎻ在标准ＲＲＴ－Ｃｏｎｎｅｃｔ算法的上引入目标偏置策略ꎬ当改进后算法在探索无障碍空间时可以通过调节步长朝目标点快速扩展ꎬ在探索障碍物空间时则调用随机采样函数ꎬ可以使算法效率提高ꎬ但又不会陷入局部最优ꎮ

制下的多配送中心、同车型、软时间窗的随机需求的ＶＲＰ问题ꎮ

在实际的求解过程中约束条件越多ꎬ那么求解的过程将越复杂ꎬ需要花费的时间越长ꎮ就目前求解的现实状况来看ꎬ一般人们研究的最复杂的ＶＲＰ问题也就是三到四个属性ꎮ为了简化模型ꎬ更多的研究小合着只选择一到两个属性来作为约束条件ꎬ这种情况下求解货稍微简单一些ꎬ模型也更加凸显某方面的问题ꎮ例:Ｄｒｏｒ等

[３]

主要研究的满载问题ꎻ李军

等[４]主要研究的非满载问题ꎻＣｏｒｄｅａｕ等[５]研究的带有时间窗的问题ꎻＧｅｎｄｒｅａｕ等[６]研究的多车型的问题等等ꎬ诸如此类都是的研究选取一到两个属性ꎮ

近年来ꎬ随着ＶＲＰ应用的越来越广ꎬ几种车辆路径规划的求解算法:

２.１　龚艺遗传算法[７]等采用改进遗传算法对外卖配送系统建立了路径

最短的带时间窗约束的模型ꎮ易欣[８]等针对机器人运动规划中可能出现的局部陷阱和过早收敛问题ꎬ提出了一种自适应遗传算法ꎬ用自适应算子代替常规选择算子ꎬ令自适应算子在整个算法运行中恰当的选择压力ꎮ梁凯[９]等主要针对配送中障碍物的位置与机器人行驶路径之间的关系ꎬ通过采用可视图法建立环境模型并进行全局路径规划ꎬ移除影响路径规划障碍ꎮ将粗糙集理论和遗传算法融合ꎬ在路径规划中减少可供选择项ꎬ从而提高机器人路径规划的效率ꎬ减少搜索时间ꎬ提升机器人路径规划的整体性能ꎮ余文曌[１０]等针对标准遗传算法进行路径规划时搜索空间大、出现过多搜索冗余和收敛效率低等问题ꎬ给出在网格的遗传算法上加入弹性网格概念ꎮ在低密度的网格地图下求解最优路径ꎬ增加转向点从而增加网格的密度ꎬ继续搜索ꎬ反复此步骤ꎬ以减小算法搜索空间ꎬ提高路径规划效率ꎻ给出自适应变异概率ꎬ使其根据各代２.路径离散程度自适应调整大小２　ＲＲＴ算法

ꎬ以提高各代路径多样化ꎮ

蔡文涛[１１]等针对快速探索随机树(ＲＲＴ)路径规划算法

缺乏导向性和规划空间增大时算法时间复杂度高的问题ꎬ提出一种目标概率偏置与步长控制的改进ＲＲＴ算法(Ｉ－ＲＲＴ)ꎮＩ点－ꎬＲＲＴ提高路径规划的导向性结合目标概率偏置ꎬꎬ以一定概率使采样点偏置为目标并引入步长控制优化算法ꎬ提高运算效率ꎬ优化路径ꎮ王坤[１２]等针对双向快速扩展随机树(ＲＲＴ－Ｃｏｎｎｅｃｔ)算法的路径规划效率较低且采样具有随机

２.３　王铭枫Ａ~∗[１３]算法

等提出一种基于转向约束和能耗最优的Ａ~∗

路径规划算法ꎮ在采用载波相位差分(ｒｅａｌ－ｔｉｍｅｋｉｎｅｍａｔｉｃꎬ简称ＲＴＫ)全球导航卫星系统(ｇｌｏｂａｌｎａｖｉｇａｔｉｏｎｓａｔｅｌｌｉｔｅｓｙｓｔｅｍꎬ上ꎬ针对道路坡度起伏大的问题简称ＧＮＳＳ)精确采集及存储田间道路路径信息的基础ꎬ建立起伏道路的能耗计算函数ꎬ对Ａ~∗算法估价函数进行重新设计ꎻ同时ꎬ针对部分路口转向困难的问题ꎬ引入路口转向曲率进行约束判断ꎮ陆皖麟[１４]等针对Ａ~∗算法的缺陷进行改进ꎬＡ~∗算法有搜索过程慢、路径不光滑、折点过多浪费时间等问题ꎮ通过ｏｐｅｎｌｉｓｔ添加阈值Ｎꎬ如果搜索次数大于Ｎ且最先插入的节点未扩展ꎬ就将该节点设为最高级优先扩展ꎬ减少了搜索时间ꎬ将Ｆｌｏｙｄ算法和Ａ~∗算法融合ꎬ两种算法优势互补ꎬ解决Ａ~∗算法的缺陷ꎬ解决路径不光滑等问题ꎮ３　总结

物流供应链系统不断的发展ꎬＶＲＰ作为物流系统中至关重要的环节ꎬ已经受到越来越多的重视ꎮ目前人们对于ＶＲＰ的研究主要集中在对于各种算法的优化与改进上ꎬ研究学者们致力于提出更优的算法ꎬ使得路径规划变得更快速更优ꎮ各种算法在单独使用时都会存在一些比较大的缺陷ꎬ而且随着社会的发展ꎬ人们所要解决的问题规模越来越大ꎬ结构越来越复杂ꎬ仅仅只依靠一种算法很难解决现实中复杂的问题ꎮ于是人们开始致力于算法融合和改进ꎬ各种算法互相弥补ꎬ克服了单一算法的很多缺点ꎬ构造出改进后更优的算法ꎮ近十几年ꎬ人们对于算法的研究更加侧重于多种算法的融合ꎬ不断构造新的混合算法ꎮ

[参考文献]

[１]岳苹.基于改进蚁群算法的车辆路径优化问题研究[Ｊ].

工业控制计算机２０１７ꎬ３０(０９)ꎬ５４－５５.

[２]ＭａｎａｇｅｍｅｎｔＤａｎｔａｉｇＧꎬＲａｍｓｅｒＪ.Ｔｈｗｔｒｕｃｋｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍ[Ｊ].[３]ＤｒｏｒＭꎬＬａｐｏｒｔｅｓｃｉｅｎｃｅＧꎬꎬ１９５９Ｔｒｕｄｅａｕ(６):Ｐ.８０Ｖｅｈｉｃｌｅ－９１.

ｄｅｌｉｖｅｒｉｅｓ[Ｊ].ＤｉｓｃｒｅｔｅＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓｒｏｕｔｉｎｇꎬ１９９４ｗｉｔｈꎬ５０(ｓｐｌｉｔ

２６９－２５４.

３):

[４]李军ꎬ谢炳磊ꎬ郭耀煌.非满载车辆调度问题的遗传算法

[Ｊ].系统工程理论方法应用ꎬ２０００ꎬ９(３):２３５－２３９.

(下转第３３页)

第８期张中强等:徐连地区物流一体化问题研究

３３

角区域大通关建设协作备忘录»ꎬ将这种通关协作模式运用到徐连两个市级单位中来ꎮ具体来说ꎬ徐连地区两地海关开通货物通关快速通道ꎬ徐州地区的货物可直接通过快速通道进行通关手续ꎮ在这个通关快速通道体系中ꎬ连云港海关将一部分权利授予给徐州海关ꎮ对于那些想在连云港出关的企业ꎬ徐州海关将拥有高度的控制权ꎮ企业需要在徐州海关处提供所有出入境手续证明和其他通关所需文件ꎬ由徐州海关对这些文件进行审核ꎮ当徐州海关进行相应调查检验后ꎬ如确认该企业当批货物具有出关资格ꎬ而且货物符合安全标准ꎬ即可开具出关通行证ꎮ当企业货物运达连云港海关时ꎬ连云港海关只需检查徐州海关提供的通关证明ꎬ并对当批货物安全性进行再次检查ꎮ如果企业提供的证明无误ꎬ货物安全性４.３　建立多式联运物流信息平台

又能够能达到要求ꎬ连云港海关即可放行出关ꎮ

平台ꎬ中心信息平台根据多式联运流程ꎬ将信息传达给与该流程有关的其他子系统ꎬ其他子系统收到信息ꎬ进行本系统业务操作ꎬ并将结果反馈给中心系统ꎬ这就是连云港港多式联运信息平台的工作流程ꎮ具体工作流程图见图１ꎬ图中实线代表物流ꎬ虚线代表信息流ꎮ

图１　连云港港多式联运信息平台中心工作流程图

[参考文献]

[１]ＢｅｒｎａｒｄＪＬａｌｏｎｄｅ.ＥｖｏｌｕｔｉｕｎｏｆｔｈｅＩｎｔｅｇｒａｔｅｄＬｏｇｉｓｔｉｃｓ[２]ＧｉａｎｎｏｃｃａｒｏＩꎬＰｏｎｔｒａｎｄｏｌｆｏＰ.Ｓｕｐｐｌｙｃｈａｉｎｃｏｏｒｄｉｎａｔｉｏｎｂｙ

ｒｅｖｅｎｕｅｓｈａｒｉｎｇｃｏｎｔｒａｃｔｓ[Ｊ].ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＰｒｏｄｕｃｔｉｏｎＥｃｏｎｏｍｉｃｓꎬ２００４ꎬ８９(２):１３１－１３９.[Ｊ].科技管理研究ꎬ２０１０(１９):５３－５６.

[４]卢美丽.城乡物流一体化体系的构建和评价[Ｊ].农业经

济问题ꎬ２０１２(４).

[５]刘新华ꎬ陈刚.城乡经济一体化下物流发展问题研究[Ｊ].

企业导报ꎬ２０１３(３)

[６]孙青华ꎬ张灿ꎬ杨斐.邮政电子商务物流模式研究[Ｊ].邮

政研究ꎬ２０１３(３).

Ｃｏｎｃｅｐｔ[Ｍ].ＮｅｗＹｏｕｋ:ＴｈｅＦｒｅｅＰｒｅｓｓ.ｌ９９４.

假如徐连地区一体化设想能够成为现实ꎬ届时出于时间

成本、财务成本、便利程度等多方面因素考虑ꎬ徐州大多数货物都将选择由连云港地区的港口出关ꎮ可以说徐连一体化的目标之中ꎬ最重要的一条就是将连云港港变为徐州的直通ꎮ

多式联运信息系统平台的作用是为了实现多式联运过程中高效的联合作业以及整个运输过程的优化ꎬ其关键在于信息的集成与共享ꎮ信息集成又可分为公共基础信息集成、物流业务信息集成、监管信息集成等方面ꎮ多式联运信息平台把系统所涉及到的所有参与者的信息、纳入自己的信息网络中ꎬ并构建用户信息中心ꎮ通过对用户信息审核ꎬ将用户与多式联运中的某一运输流程紧密关联ꎬ将运输流程参与者的信息高度共享ꎮ

连云港港的物流设备齐全ꎬ各单位相应信息系统完备ꎬ因此连云港港多式联运信息平台只需在原有基础上将现有各信息系统与中心信息平台相互连接ꎬ实现信息对接ꎮ当子系统接收到订单信息时ꎬ子系统第一时间将信息上传至中心信息

[３]崔晓迪.区域物流供需耦合系统的协同发展评价研究

(上接第１０１页)

[５]ＣｏｒｄｅａｕＪＦ.ＤｅｓａｕｌｎｉｅｒｓＧꎬＤｅｓｒｏｓｉｅｒｓＪꎬＳｏｌｏｍｏｎＭꎬＳｏｕｍｉｓ

Ｆ.ＶＲＰｗｉｔｈｔｉｍｅｗｉｎｄｏｗｓ[Ａ].ＴｏｔｈＰꎬＶｉｇｏＤ.ＴｈｅｖｅｈｉｃｌｅＤｉｓｃｒｅｔｅＭａｔｈｅｍａｔｉｃｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓꎬ２００２:１５７－１９４.

遗传算法的机器人路径规划方法研究[Ｊ].科技经济导刊ꎬ２０１９(１４).

[１０]余文曌ꎬ佘航宇ꎬ欧阳子路.基于弹性网格的改进遗传算

法在无人艇路径规划中的研究[Ｊ].中国航海ꎬ２０１８(０４):１０１－１０５.

[１１]蔡文涛ꎬ邓屹ꎬ张静ꎬ张永波ꎬ饶爽ꎬ阳康.基于改进ＲＲＴ

算法的机械臂路径规划[Ｊ].传感器与微系统ꎬ２０１９(０５):１２１－１２４.

[１２]王坤ꎬ曾国辉ꎬ黄勃ꎬ李晓斌.基于改进ＲＲＴ－Ｃｏｎｎｅｃｔ的

快速路径规划算法[Ｊ].武汉大学学报(理学版)ꎬ２０１９(０３):２８３－２８９.

[１３]王铭枫ꎬ李云伍ꎬ徐俊杰ꎬ刘得雄.基于Ａ算法的丘陵山

区田间路网路径规划[Ｊ].江苏农业科学ꎬ２０１９(０７):２３２－２３５＋２９６.

ｒｏｕｔｉｎｇｐｒｏｂｌｅｍ[Ｃ].Ｐｈｉｌａｄｅｌｐｈｉａ:ＳＩＡＭＭｏｎｏｇｒａｐｈｓｏｎ[６]ＧｅｎｄｒｅａｕＭꎬＬａｐｏｒｔｅＧꎬＭｕｓａｒａｇａｎｙｉＣꎬＴａｉｌｌａｒｄＥＤ.Ａｔａｂｕ

ｓｅａｒｃｈｈｅｕｒｉｓｔｉｃｆｏｒｔｈｅｈｅｔｅｒｏｇｅｎｅｏｕｓｆｌｅｅｔｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍ[Ｊ].Ｃｏｍｐｕｔｅｒｓ＆ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈꎬ１９９９ꎬ２６(１２):１１５３－１１７３.

[７]龚艺ꎬ冉金超ꎬ侯明明.基于遗传算法的多目标外卖路径

规划[Ｊ].电子技术于软件工程ꎬ２０１９(１０):１５７－１５９.[８]易欣ꎬ郭武士ꎬ赵丽.利用自适应选择算子结合遗传算法

的机器人路径规划方法[Ｊ].计算机应用研究ꎬ２０１９(５).[９]梁凯ꎬ王影ꎬ刘麒ꎬ李硕ꎬ苟垚ꎬ李宝华.基于粗糙集理论与