基于交通流的车辆路径选择优化方法.pdf

《基于交通流的车辆路径选择优化方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第30卷第6期2013年6月计算机应用研究ApplicationResearchofComputeI_sV01．30No．6Jun．2013基于交通流的车辆路径选择优化方法于洪玲8，王洪国6．，曲建华8，孟春华8(山东师范大学a．管理科学与工程学院；b．信息科学与工程学院，济南250014)摘要：针对交通流变化对车辆路径选择的影响，寻找在交通流变化情况下对出行路线进行规划的方法。采用粒子群算法与动态规划相结合的方法对路径进行优化，可得各车辆在交通流影响下的优秀路线。基于真实环境中的路网结构和交通数据进行模拟，结果表明，该方法可增加路径优化的真实性和动态性，而且道路交通流及车

2、辆出行时间都对车辆路径选择产生重要影响。关键词：交通流；粒子群算法；动态规划；路径优化；时间依赖中图分类号：TPl5文献标志码：A文章编号：1001-3695(2013)06—1675．03doi：10．3969“．issn．1001—3695．2013．06．018OptimizationmethodtovehicleroutingbasedontramcnowYUHong—lin98，wANGHong—gu06，QUJian．hua8，MENGChun．hua8(Ⅱ．胁m眦矿讹舳酽Mm＆如，啪＆E，画聊e一增，6．胁mm0，蜘mdfion&拓n傀＆E昭in贸^增，s舰，

3、协昭Ⅳo丌眦f踟沁m盼，如mn250014．吼iM)Abstract：ResponsetotheimpactoftmfEicnowforvehiclerouting，thispaperfoundamethodtosolvethevehicleroutingwhileknowingthechangeoftra伍cnow．ItmadedyIl枷icpmgmImingcombingwiththechangesofthet捌五cnowtooptiIIlizetheroutebetweencustomers．Itsimulatedroadstmctureandtr棚cdatabase

4、donI℃alworld．whichshowedthatthemethodin—tmducingtralfEicnowwouldadvaIlcethetmtllanddyn砌icofroutingoptimi龃tion，andtllattlletmfficnowandtlledepanuretimeofthevehiclewouldafkctroutingselection．1【eywor‘ls：tIjafhcnow；particlesw姗algorithm；dynamicpmgr咖Illing；IDute叩timization；timedependence0引言Dantz

5、ig等人⋯于1959年提出VRP(vehiclemutingprob—lem)的概念，之后很多学者都对VRP问题展开了研究，但多数研究集中在静态路径优化方面，即路况信息、车辆信息及客户信息等都是确定的，且信息与时间无关。显然，实际环境中，车辆速度是变化的，车辆路径规划时如果忽略这种变化，将导致得到的优化方案失去实际意义。当前，已有一些考虑时间影响的车辆路径规划问题研究，称为TDVRP(timedependentve．hiclemutingpmblem)。，IDVItP来源于rI’D髑P(timedependenttravelingsalesmanpmblem)¨JoMala

6、ndmk等人¨1给出了TD—VRP的严格数学模型，并设计了最邻近法和割平面启发式算法；Ichoua等人‘41在解决时间依赖性车辆路径问题时，对时间依赖性速度进行处理，把规划周期划分为三个时间段，对速度建立阶梯函数，通过速度的阶梯函数将旅行时问处理为一个连续的时间函数；HagIlania等人怕。提出用连续的速度时间函数模型来表示道路的速度变化趋势；Donati等人∞1采用蚁群算法解决时间依赖性问题，释放两个人工蚁群以优化路线的数量和花费的时间，通过信息交换合作取得最终的最优解；u等人一。采用拉格朗日松弛算法进行实时的车辆路径规划；Kritzinger等人坤1使用Dijkstr

7、a算法和可变邻域搜索算法来解决车辆路径问题，首先使用Di_jkstm算法计算具有时间依赖性的距离矩阵，降低了算法的运行时间，提高了方案的质量；Kok等人一。通过改善文献[8]中提到的用于解决时间依赖性车辆路径问题的算法，并将这一方法应用在路径规划时如何避免交通堵塞。关于时间依赖性车辆路径问题的研究能够提高路径规划方案的质量，增强方案的应用能力。国内外对于时间依赖性的车辆路径问题的研究主要集中在基于旅行时间的时间依赖和基于旅行速度的时间依赖，关于交通流在时间依赖性车辆问题中产生的影响的研究尚不多见。交通流的大小能直观