遗传算法的时相关动态车辆路径规划模型.pdf
《遗传算法的时相关动态车辆路径规划模型.pdf》由会员分享，可在线阅读，更多相关《遗传算法的时相关动态车辆路径规划模型.pdf（6页珍藏版）》请在冰点文库上搜索。
第33卷第8期2008年8月武汉大学学报信息科学版Geomaticsand1nfomationScienceofWuhanUniversityV0133No8Aug2008文章编号：
16718860（2008）08一0875一05文献标志码：
A基于遗传算法的时相关动态车辆路径规划模型唐健12史文中2孟令奎1（1武汉大学遥感信息工程学院，武汉市珞喻路129号，430079）（2香港理工大学土地测量与地理资讯学系，香港九龙红确）摘要：
动态车辆路径规划是智能交通和商业物流领域中的一个重要研究方面，其最大的优点是就是综合考虑了各种实时信息。
及时优化更新配送车辆的行驶路径，进一步降低物流成本。
提出了一种基于遗传算法的时相关动态车辆路径规划模型。
该模型将时变的交通信息和动态客户订单考虑在内，可以获得比较好的动态更新效率和优化结果，为此类动态车辆路径规划探索出了一条可行的途径。
关键词：
动态车辆路径规划；智能交通系统；物流；遗传算法，时相关中图法分类号：
P22842；Pz379；P208在新的信息技术的推动下，各种动态信息的获取成为可能，如智能交通系统（intelligenttransportationsystem，ITS）、GPS和GIS。
ITS、GPS和GIS等技术的广泛使用，使得车辆管理系统中车辆货物运送的全程实时监控得以实现。
已有众多的学者对实时动态车辆的路径规划问题进行了研究1。
对于动态车辆路径的规划而言，动态性的描述不仅在于客户需求的变化，其一个重要的动态特点就是时间依赖性（time-dependentVRP）。
它可描述为如下情况：
一个车队在指派车辆服务的所有节点中，以全部行驶时间最短为最优化条件。
但车辆在节点之间行驶的时间不是常量，而是依赖于每天不同的时间交通状况发生变化，即交通网络中弧段L（i，）的代价随时间不同而发生变化。
目前，对时间依赖路径规划（TDTSP）问题的处理大致可以分为两类：
一类为两节点间的旅行时间依赖于一天中所处的具体时段，即把一天分为几个不同的时段，在不同的时段，任意两节点间的旅行时间不同，这种方式的计算相对简单6；另一类将弧（i，歹）的旅行时间依赖于节点i在哈密顿圈中所处的位置。
对这类问题，任意两个节点间的旅行时间为一时段，因此，在旅行过程中，不会涉及跨时段的问题7。
10。
本文在文献11的基础上提出了一种基于遗传算法的时相关动态路径规划模型。
1问题描述本文考虑的是一个交通网络G一（NUO），A），N=1，2，咒）是一组客户位置点，O是所有车辆的出发点，A是网络边的集合；对于所有的边ij；A，代表从节点i到歹的行驶时间，它是随着时间和实际路况动态变化的。
每一个从节点i到节点歹的客户的运货量为dd，如果从i到J没有货物信息，则如一o。
对于所有的N，客户的货运情况可由矩阵D=也）表达，矩阵行表示取货节点，列表示收货节点，则如就表示所J=l有从i节点取的货物量，也表示所有运送到歹i=l节点的货物量。
为简单起见，这里假设所有的节点都是简单的一个用户的取货节点和收货节点；。
在实际应用中，如果在同一个节点，既是取货点，又是收货点的复杂节点，则可将节点人为地拆分为两个简单节点。
在上述前提下，本文所提问题的解决目标是：
任何时候，车辆装载不超过K的货物量；取货节点必须在收货节点之前；所有车辆必须在限定的时间内完成货物的运送。
收稿日期：
2008一0615硬目来源：
国家863计划资助项目（2007AAl22309）；香港理工大学研究基金资助项目（GYEl3）876武汉大学学报信息科学版2008年8月2算法模型动态路径规划算法可以被划分为初始路径规划和动态更新两个阶段。
初始路径构造阶段，将预知的客户需求信息通过遗传算法全局寻优和路径内寻优后生成初始路径；动态更新阶段，首先执行初始路径，当有新的客户需求到达时，将新的客户需求动态插入已有路径中，同时通知车辆执行新的路径，循环等待新的客户需求到达，直至所有的客户需求都运送完成。
算法流程如图1所示。
初始路径构造动态路径更新遗传算法令局寻优车辆执行规划路径，1直至货物运送完毕n改进启发式的随机I最邻近搜索路径内优化有新客户需求到达是l输m初始优化结果_一动态更新路径卜J图1动态路径规划算法流程Fig1FlowChartofDynamicVehicleRouting21初始路径规划211遗传算法全局寻优已有事实证明，利用遗传算法求解VRP问题是比较成功的解决方案。
本文所解决的问题涉及多车辆、车辆载货量以及时变的道路交通信息、路径节点顺序必须满足取货节点在收货节点之前等限制条件，因此，利用遗传算法的全局优化必须要经过特殊的染色体编码处理。
模型的矩阵染色体编码模式为：
D=D，=O10002KO矩阵D是货运情况，矩阵的行表示取货节点，列表示收货节点，也为货运量。
D中每一个d。
!
一。
的位置就是染色体的基因，其值由运送货物的车辆ID代替，每个基因用三元组形式表示为，Ni、M为取货节点和收货节点编号，K为车辆编号。
在D。
矩阵中，d。
：
由车辆1运送，dj由车辆K运送。
每一组D，就表示了一种可能的解决方案。
然而，这样的编码只能表达车辆经过了哪些节点，并不能表达某一车辆通过节点的次序关系，因此，在路径内采用与一般TSP问题一致的编码，从左向右的节点序号表达一种可能的规划路径。
基因的交叉（crossover）运算操作采用随机选择的方式。
首先，从选择池L条染色体中随机地选取一对矩阵染色体，为染色体中每个基因加编序号（假设有挖个基因）。
然后随机产生一个常数Il（竹+1）2，以和竹一位置分别为交换操作点，为了加速迭代的收敛，必须保证所选择的丘对基因有两对以上的值不同。
基因的突变（mutation）是为了防止在寻优过程中陷入局部最优而将基因值转变为值域范围内的其他值。
对每一个染色体中的基因il，2，g，给定一个突变概率值缸o，1，随机地选取一个矩阵染色体的基因i，计算一个概率，若值在O“内，则将其车辆编号变化为其他车辆，即由其他车辆来运送。
也就是说，每个基因突变的概率是“g。
交叉和突变运算后，产生了一对新的染色体，计算新染色体的适应度函数，如果新染色体的适应度函数小于（优于）父染色体，则用新染色体取代旧染色体；反之，保留旧染色体。
矩阵染色体的适应度函数可以表示为每条经过内部寻优后的路径所花费的行驶时间之和，即I，=C劬。
通过对每一代染色体进行交叉、突变以及路径内寻优操作后，模型将更新记录每一代中的适应度函数最优的一组解决方案。
迭代过程将在进行一个给定的计算次数后停止。
212TDTSP路径内局部寻优通过遗传算法的交叉和变异操作，可以确定路径数和每条路径所包含的节点数。
在单条路径内，确定节点的次序问题就是TSP，由于道路交通流量是变化的，因此，路径内局部优化就是TDTSP问题。
为便于分析计算，Malandraki等提出的时间分段策略一直是现有大多数研究所采用的方法。
该方法通过将一天划分为不同的时间段，而每一条弧段在同一时间段内的代价为一个固定的常数，从而将问题转化为相对静态的问题。
本文在这一分段策略的前提下，将一天划分为三个时段，同时为了便于更新计算，不考虑道路O耵d2磊OO0第33卷第8期唐健等：
基于遗传算法的时相关动态车辆路径规划模型877交通信息跨时段的变化。
由于本文所解决的问题包含有取货和收货节点区分的问题，因此，采用改进的启发式随机最邻近搜索（nearestneighborrandom）进行寻优。
具体算法描述如下：
在给定的时间从出发点出发；将当前最后一个节点到所有未访问节点的边按照权值大小升序排列。
从这一组边列表中，按照给定的概率分布随机选择一条边添加入路径中。
由于节点有取货节点和卸货节点的区分，随机选取节点也需考虑取货节点优先的原则；重复步骤，直到所有的节点被访问到或达到时间限制和载货量限制条件，返回出发节点；重复步骤L次，选择一条最佳的路径。
22动态更新过程若有新的客户需求到达时，原有路径就需要被有效地重新优化。
假设新数据在时刻到达，为了重新优化路径，下面的基本信息是必须获取的：
每辆车在时刻的位置和车辆未完成的节点；时刻车辆的载货量情况。
若在时刻有一个新的订单到达，运货量为d，系统首先为这个订单生成一个取货节点和一个卸货节点，用三元组表示为。
由于RFID和GPS技术的使用，模型系统根据实时获取当前车辆的载货量信息和实时位置信息，在初始路径规划结果的基础上，将新节点对插入原始路径。
在动态更新过程中，首先考虑将新的节点插入已存在的路径，检查所有车辆的当前位置，新的节点必须插入车辆位置之后。
检查每一种可能的插人情况，计算插入后对原路径的影响JclCD，G为插入新节点后的路径行驶时间，Co为原始路径行驶时间，取J最小的路径插入新节点。
若所有的新路径都无法插入，则要创建一条新路径。
3试验及分析31路径初始化实例为测试上述方法的有效性，本文利用生成的一组随机点数据分别进行了初始路径规划和动态更新的测试。
其中，节点产生的范围是在单位1的方形区域内，节点数设为，l=50，车辆载货量为K=10，行驶速度设为单位1，因而车辆行驶时间可由几何距离表示。
取货节点和卸货节点由试验系统随机配对，运货量d在110之间随机生成。
一天的送货总时间限制A设为4。
同时将A分为3个均等的时间段，每个时间段内的车辆行驶时间由O1随机产生，以表达变化的道路交通信息。
在这些参数设置下，测试了多组数据，当遗传迭代终止代数设置为1ooo时，进行的路径规划结果如图2所示。
重督酃妊增次图2四组试验初始路径规划结果曲线图Fig2F0urPh胁ultsby“tialRouteC0璐trumon图2中，A、B、C、D四条曲线分别表示路径初始化算法在上述相同条件设置下重复4次寻优的过程曲线，横轴为寻优迭代次数，纵轴为寻优结果。
从图中可以看出，4次优化过程在迭代约500次之前下降迅速，之后则趋于平稳，递减过程的单调性比较一致，表明该算法具有较好的稳定性。
在4次寻优结果中，最优结果为15001668个单位，它比最坏的初始结果（25017174个单位）降低了约40，均值初始结果约降低了35。
在相同条件下，经过多次重复测试，寻优后的最终结果相对标准偏差小于3，这表明初始路径寻优的解的质量是比较高的。
表1记录了在其他参数设置相同、节点规模变化的情况下，道路交通信息分段与不分段时经多次计算后所找到的均值最优解的对比。
表1时间分段路径规划对比寰Tab1RoutingResultswithandWithoutTimePeriod从表1可知，交通时间分段后，所找到的均值最优解要比不分段时的解有一定程度的优化提高。
特别是当节点规模小于100时，提高率超过10。
显然，已分段形式考虑了交通车流量的变化，在一定程度上可更好地体现真实的动态交通信息对道路优化结果的影响，从而降低物流成本。
32动态更新实例假设J为一次测试实例，令Z（D为静态路径的规划结果，Z（J7）为动态更新后的结果，Z（r）为直接用静态方法规划计算的加入更新节点后的878武汉大学学报信息科学版2008年8月结果。
模型采用公式R=（Z（，）一Z（f。
）Z（，。
）*100来表达模型更新的有效性。
R值越小，则更新的有效性越高。
如当n=50、K=10时，初始路径规划的最优结果为Z（J）=14786；动态插入两对节点后，规划结果变为Z（17）一1617845；将插入的两对节点加入原始结果进行初始优化，规划结果为Z（r）=154685，则R=458。
表2是在节点数，l=50、100、200和K=10、20、30，更新节点Nf分别为2对、4对、6对时的一组R值。
裹2动态更新结果分析衰Tab2AnaIysisResuItforDynamicUpdatingRN，=4NJ=64587088905259OO3991550536457409201080615920469136260449957112412108281187565360101O57从表2结果可以看出，当节点数小于等于100时，绝大部分的有效性（R值）都小于10，同时，R值随节点规模的增大而逐渐减小；当节点数咒和车辆载货量K相同时，随着动态插入节点数的增加，更新结果的R值又有所增加，表明模型在更新的节点数相对原始节点较少时，有效性比较高。
上述规律也是与实际情况相符的，动态更新只是局部更新，并非全局优化。
当动态插入的节点数增多时，对原先全局优化的路径冲击就会变大，有效性也会相应降低。
但总体上来说，本文所提出的动态更新机制在小规模的节点插人更新时，是具有较高的更新效率和有效性的。
4结语动态车辆路径规划是智能交通和商业物流领域中的一个重要研究方面，其最大的优点就是综合考虑了各种实时信息，及时优化更新配送车辆的行驶路径，从而进一步降低物流成本。
本文提出的遗传算法的初始优化和局部动态更新的方法同时解决了客户需求变化和交通信息变化两种动态因素同时影响下的路径规划问题。
试验结果表明，初始优化的稳定性和解的质量和动态更新的有效性均都有很大的改进。
该方法适合于现代通信技术和ITS交通信息支持下的动态车辆管理。
同时，该方法也还有许多不足，特别是当动态插入的节点数比较多时，节点更新的有效性会下降，不适合问题规模比较小的情况。
对该问题的优化将是今后继续关注和研究的重点。
参考文献1GendreauM，PotvinJYDynamicVehicleRoutingandDispatchingCFleetManagementandLogistics，Kluwer，Boston，19982YallgJi锄，J枷etP，Mahma黝面HRe小timeMultivehicle1hckhdPickupaIldDeliveryProblemsJ1hnsportationSdence2004（38）：
1351483FabriA，RechtP0nDyrlamicPickupandDeliVeryVehicleRoutingwithSeveralTimeWindowsandwaitingTimesJTransportationResearchPartB，2006（40）：
3353504FleischmannB，GnutzmannS，sandvossEDy一尬micVehicleRoutingBasedonOnlineTrafficInfo兀nationJTransportationScience，2004（38）：
420一4335李兵，郑四发，曹剑东，等求解客户需求动态变化的车辆路径规划方法Jl交通运输工程学报，2007，7
（1）：
1061106Malandrakic，DaskinMsTimeDependentVehicleRoutingProblems：
Formulations，Properties，andHeuristicAlgorithmsJTransportationscience，1992（26）：
1852007PicardJC，QueryranneMTheTimeDependentTravelingSalesmanProblemandItsApplicationtotheTardinessProblemin0neMachineScheduling口0perationsResearch，1978（26）：
861108FoxKR，GavishB，GravesscA矿constraintFormulationofthe（Time_Dependent）TravelingsalesmanProblemJ0perationsResearch，1980（28）：
101810219LuceATime-DependentTmvelingsalesmanProblerntheDeliverymancaseJNetworks，1990（120）：
75376310wielRJV，sahinidisNVHeuristicB0undsandTestProblemGenerationfortheTime_DependentTmvelingSaIesmanProblemJTransportationScience，1995（29）：
16718311CheungBKS，ChoyKL。
LiCL，eta1DynamicRoutingModeIandSolutionMethodsforFleetManagementwithMobiIeTechnologiesJIntel舱一tionalJournalofProductionEconomics，2008，113
（2）：
694705第一作者简介：
唐键。
博士生。
研究方向为车载导航和路径规划。
EnuiI：
tangjianwin163comm趵加趵m瑚mm枷猢枷第33卷第8期唐健等：
基于遗传算法的时相关动态车辆路径规划模型879Time-DependentDynamicVehicleRoutingBasedonGeneticAlgorithmTANGJi口九1，2SHI19矿P咒2hD咒92ME。
NGLi竹g七甜i1（1SchoolofRemoteSen8ingandInfomationEngineering，WuhanUniversity，129LuoyuRoad，Wuhan430079Chilla）（2DepartmentofLandSurveyingandGeo_Infomatics，TheHongKoIlgPolytechnicUniVersity，HungHom，Kowloon，HongKoT瑶）Abstract：
DynamicvehicleroutingplaysanimportantroleintheintelligenttransportationandlogisticsAUkindsofrealtimeinformationisusedtore-optimizetheVehiclerouteAdynamicvehicleroutingmodelbasedongeneticalgorithm，time-dependenttraVelinformationanddynamiccustomrequests，isproposedThenewmodelcanachieveabetterre_optimizingresultKeywords：
dynamicvehicleroutingplan；intelligenttransportationsystem；logistics；geneticalgorithm；timedependentAbo吡t雠nr砒加t-l钾：
TANGJI锄，PhD旷一i凼Ite，majors虮VehjcIen甜igatiandrou忙pI卸E帕：
协ng
升级会员 