模拟导弹制导的时间最短路径算法

龚 龚,李苏剑*,邢恩辉

(1.北京科技大学机械工程学院,北京100083；2.佳木斯大学机械工程学院,黑龙江佳木斯154007)

模拟导弹制导的时间最短路径算法

龚 龚1,李苏剑*1,邢恩辉2

(1.北京科技大学机械工程学院,北京100083；2.佳木斯大学机械工程学院,黑龙江佳木斯154007)

应用模拟导弹制导的方法,提出了一种考虑系统优化的单车实时动态路径算法.算法以单车时间最短为目标,通过使车辆避开拥堵,达到单车路径规划利于系统优化的目标.算法首先进行初步路径规划,即求解利于车流量平衡的理想路径生成点;然后,进行理想路径规划;最后,根据理想路径得出实际路径规划.在出行全程中,算法进行循环滚动的实时动态路径规划,同时根据交通状态数据实时修正未通行路段的路径规划.通过交通网数据动态模型和模拟导弹制导的算法仿真,结果表明,该算法能有效地解决车辆避开拥堵、节约出行时间,同时利于车流量平衡和系统优化.

交通工程;路径算法;模拟导弹制导;系统优化;理想路径

1 引 言

经典的路径算法最初以路径最短为目标,如Dijkstra算法[1,2]与A*算法[3,4]等.考虑到交通系统的动态特性,国内外学者对最小时间路径算法进行研究.针对时间依赖车辆路径规划问题代表性的算法有:有限动态规划启发式算法[5],遗传算法[6],蚁群优化算法[7],模拟退火算法[8]等.

以上算法以单车路径优化为目标即驾驶员目标要求,没有考虑系统优化目标即交通管理者目标.驾驶员目标是满足用户需求,选择最短路径或节约用户出行时间等[9].交通管理者目标是实现交通系统最优,通过优化交通流分配,提高交通网整体通行能力,降低总体延误时间.在同一路网内,多车同时采用只考虑单车路径优化目标的算法,不利于交通系统最优化,可能造成城市交通的拥挤或堵塞[10].文献[11]等提出的路径算法考虑时间窗约束,部分考虑交通系统优化；当车辆数过大时,计算量过大且目标冲突,系统可能无法达到最优解.同时传统的单车动态路径算法需要进行路网交通流状态预测[12],在此基础上进行单车动态路径规划.路径规划的准确度依赖于交通流状态实时预测的精确度,而精确度要求大幅增加了交通流预测和路径规划的难度及计算量,不适于在大规模交通网络中多车的同时应用.

为解决以上问题,提出了一种考虑系统优化的单车实时动态路径算法.算法模拟导弹制导[13],兼顾驾驶员和交通管理者的要求[14],满足驾驶员对路径诱导避开拥堵路段且节约出行时间的要求.算法在进行理想路径规划时,根据交通网拥堵状况的动态变化,求解利于车流量平衡的理想路径生成点,以达到交通管理者系统优化目标.在进行实际路径规划时,协调满足系统优化目标的理想路径和满足单车目标的路径.得出的实际路径,符合算法要求.在车辆行驶过程中,算法进行循环滚动的路径规划,根据信息平台提供的实时交通拥堵状态信息实时修正未通行路段的路径规划[14].

2 模拟导弹制导的动态路径算法

算法目标是使单车避开拥堵路段,降低出行时间；使路径符合平衡车流量要求,利于系统优化目标.

2.1 算法原理和步骤

文献[15]认为一个导弹精确制导问题的目标是双重的:一是尽可能接近击中目标；二是从一个特定的方向.原因是:导弹理想运行路线是到达目标的时间最短路线.导弹受地心引力等影响,不可能按照理想路线运行.按照克服地心引力等空间状态条件运行,导弹空间运行路线过远或时间过长.导弹制导问题产生的根本原因在于导弹在运行过程中需克服地心引力等问题.实质上,导弹制导提供的路线为协调理想运行和空间状态条件运行的路线.

车辆路径规划问题与导弹制导问题异曲同工,两者均以到达终点为最终目标；运行过程中均需克服一定阻力或影响因素.车辆路径规划的阻力或影响因素为交通系统交通流状态,尤其是拥堵状态.车辆单车路径规划目标为时间最短.受交通流状态影响,车辆按照单车路径规划目标运行可能导致交通拥堵.按照平衡交通流状态等系统优化目标行驶,车辆路径规划可能过度绕远或时间过长.为协调单车路径规划目标和系统优化目标的冲突,模拟导弹制导进行车辆路径规划.

车辆路径规划问题与导弹制导问题的区别在于:①交通系统交通流状态时变,在路网内处处不均衡；空间环境中地心引力不变且处处相等.②车辆路径规划问题受路网结构、交通限速、路径规划范围等的限制；导弹制导问题在空间环境中不受限制.

为解决这两个问题,首先需要实时表征交通系统交通流状态(相当于导弹制导地心引力项)；且在模拟导弹制导得到利于系统优化的单一车辆理想路径规划后,再根据实际路网结构、交通限速、路径规划范围等,得出协调单车路径规划目标和系统优化目标的实际路径规划.

具体原理如下:

首先求解单车理想路径.理想路径指不考虑实际交通网约束,根据交通系统交通流状态,满足平衡车流量目标及系统优化目标,使车辆避开拥堵路段和降低运行时间的理论最佳路径.

算法原理图如图1所示.假设交叉口a点、b点、c点和f点的车流量大,相连路段车流量也较大,交叉口c点、d点和g点的车流量小,其他路段车流量较小.从路径起点A到终点B的理想路径为两者间的曲线,避开车流量大的交叉口和路段.假设各交叉口间均有实际路段连接,与理想路径拟合度最好的路径,符合避开拥堵路段的路径规划目标.

图1 算法原理图Fig.1 Schematic diagram of algorithm

路径算法步骤如下:

步骤1 初步路径规划实质上是求解理想路径生成点,目的是根据交通系统车流量和拥堵状况,实时表征系统中满足系统优化目标的各畅通点.系统优化目标即使车流量平衡的目标.

步骤2 通过车辆到达终点的运动方程判断理想路径生成点是否符合路径规划要求和实际交通要求.连接所有符合要求的生成点作为理想路径.

步骤3 以理想路径为中心,向纵坐标方向等幅度逐步搜索,直至搜索出符合路径规划目标的实际路径.

步骤4 在车辆行驶全程中,以车辆所在路段的起点为路径规划起点,以到达目标为终点,根据交通状态数据进行实时动态路径规划.车辆到达下一路段时,进行新的路径规划.如此循环滚动,形成实时动态算法,至车辆达到目标终点为止.

2.2 初步路径规划算法和步骤

初步路径规划要求是理想路径生成点避开拥堵路段,接近畅通路段.将路网看作关于交通系统拥堵状态的重力场(相当于导弹制导中的空间引力场).这一步骤也称为求解理想路径生成点,目的是根据交通系统的车流量和拥堵状况,实时地表征系统中理想路径生成点交通流状态(相当于导弹制导地心引力项).理想路径生成点即利于系统优化的畅通点.

步骤如下:

步骤1 以城市中心为原点,经纬方向为坐标轴方向.根据实际位置,实时标出各交叉口和交通灯信号配时.

步骤2 将车辆所处路段的起点和目标终点实时标注.将两者横坐标之间的区域划分出来作为初步路径规划区域.

步骤3 在初步路径区域内,求解理想路径生成点方法如下:

图2是理想路径生成点原理图.路径规划终点z坐标不变,记为(xz,yz).除去路径起点和终点,按照横坐标值从小到大的顺序,搜索所有与横坐标值相同的点.所有横坐标值相同的点为一个集合.需要说明的是,为了进行路径规划,认为相同路段不同车道为不同集合点,进行独立计算.集合F中的点记为fe,e=1,2,…,n,各点对应的拥堵程度mfe,与通过该路段的时间成正比,与路段长度成反比.

通过该路段的时间包括通过车道的时间和交叉口的时间,路段车道长度指路段中车辆行驶长度.当fe点位于路段车道上或交叉口c时,有

集合中每一点的坐标,记为(xf,yfe).生成路径点f的横坐标与这些点相同,记为xf；纵坐标yf(t)为

生成点理想拥堵程度mf为

图2 理想路径生成点原理图Fig.2 Schematic diagram of ideal path point

2.3 理想路径规划算法和步骤

根据理想路径的含义,应将所有理想路径生成点(利于系统优化的畅通点)作为理想路径的备选点.文献[16]提出制导算法设计规范为①轨迹平滑,②加速度受限,③大冲击角.这是因为导弹制导要求导弹行驶曲线光滑或速度、动力性能稳定.在实际的交通环境中,路网是固定的,不要求车辆行驶路线“曲线光滑”.理想路径点选择条件为:与其前后选取点在空间和时间上“相对连续”,即空间上符合路径规划要求；时间上符合实际交通要求.为判断理想路径生成点是否符合要求,模拟导弹导引运动学方程,建立车辆到达终点的运动方程.连接由车辆所在的路段起点至终点的所有符合要求的生成点作为理想路径.

步骤1 模拟导弹制导的导弹运动方程,建立车辆到达终点的运动方程.理想路径生成点是“离散的”,为了保证理想路径“连续性”,选择符合要求的理想路径生成点.

图3是车辆到达终点的运动方程原理图,坐标系oxy为城市交通坐标系,终点z为不动点.假设在车辆运行的过程中某一时刻,车辆位于生成点j,车辆行驶速度为vf.Rf(t)为该时刻车辆与终点z之间的距离.

图3中,θ为车辆的速度矢量与ox轴的夹角；φ为车辆和终点连线与ox轴的夹角；β为车辆的速度矢量与车辆和终点连线的夹角.

建立车辆到达终点的运动方程:

在路径规划中,vf起到避免拥堵的作用, g′(xf)项与生成点理想拥堵程度mf成正比.

角度间的几何关系方程:

将车辆到达终点的运动方程和角度间的几何关系方程结合建立方程组.解出vf,φ,θ,β.vf应符合交通限速要求.φ,θ,β关系应符合路径规划范围要求.

图3 运动方程原理图Fig.3 Schematic diagram of motion equation

步骤2 判断理想路径生成点是否符合路径规划要求和实际交通要求.

实际交通路网是固定的,如不考虑路径范围要求会导致路径规划过长和过度绕远问题,降低驾驶员诱导接受率.根据驾驶员要求,路径规划范围是将起点和终点连线,以连线为对角线的正方形区域,以连线为直径的圆形区域,或以连线为中线的正方形区域.

图4是路径规划区域范围,假设生成路径点为f,j点为路径规划起点,z点为路径规划终点.

当路径规划范围是以连线为对角线的正方形区域时,角度取值范围为

式中α1和α2为生成路径点与交叉口连线和起点与终点连线的夹角.

当路径规划范围是圆形区域时,角度取值范围为

当路径规划范围是以连线为中线的正方形区域时,角度取值范围为

式中Djz为f点到j点和z点连线的距离；Ljz为j点和z点连线的距离.

后文仿真中选择圆形区域作为路径规划范围.

图4 路径规划区域范围Fig.4 Path planning area

实际交通要求主要指路段及交叉口限速.当运动方程解符合取值范围要求和限速要求时,留下路径生成点,否则去掉路径生成点.

步骤3 按照横坐标轴由小至大方向,将所有符合路径规划要求和实际交通要求的生成点连接,作为理想路径.

2.4 实际路径规划选择标准

制导中的导引律反映了角度关系应符合的规律.导引律的目标是协调理想路线(时间最短路径)和克服地心引力路线(空间优化路径).导引律以导弹导引运动学方程为基础,得出导弹实际运行路线.文献[17]设计了一个集成模糊制导律来解决多目标优化问题.多目标优化问题将到达时间,能量消耗和脱靶量视为竞争目标.再通过权衡曲线采用模糊机制得出最佳折衷解决方案.本文模拟导弹导引律,根据路网结构,以理想路径为中心,向纵坐标方向等幅度逐步搜索,直至搜索出符合路径规划目标的实际路径.实际路径协调单车路径规划目标和系统优化目标.

2.3节得出的理想路径为利于系统优化的理想路径,称为系统优化理想路径.本文单车路径规划目标为路径时间最短,符合单车路径规划目标的理想路径称为时间理想路径.时间理想路径与系统优化理想路径的算法相似,区别在于式(1)中路网各点对应的拥堵程度变为

实际路径规划选择标准为:

以两条理想路径(系统优化理想路径和时间理想路径)为中心,向纵坐标方向等幅度逐步搜索,理想搜索区域为两条理想路径搜索区域的重叠区域.对理想搜索区域内的各路径进行实际路径规划,分别以两条理想路径为标准,选择与理想路径所围的面积最小的,以车辆所在的路段起点至终点的,实际路径.

图5 实际路径规划示意图Fig.5 Schematic diagram of actual path planning

如图5所示.A点为路径规划起点,B点为路径规划终点.A点和B点间的实曲线为系统优化理想路径,A点和B点间的虚曲线为时间理想路径.理想搜索区域内的交叉口点为b点、c点、d点和g点.以系统优化理想路径为标准,与理想路径所围的面积最小的实际路径为AgeB.以距离理想路径为标准,与理想路径所围的面积最小的实际路径为AgeB.路径AgeB符合时间最短路径的实际路径选择标准.

3 算例分析

3.1 模型参数

以北京某区域为例对算法进行仿真.仿真区域为奥林匹克公园附近路段,路网包含Kehui Road, Kehui South Road,Tatun North Road,Tatun Road.路段位置及路网结构如图6所示.

图6中,交通网共22个交叉口,包含起点和终点.在未进行仿真时,所有交叉口及路网内所有路段均假设不拥堵.各交叉口用圆圈表示,各路段用虚线表示.

为保证交通数据的随机动态特性,仿真时,各路段及各交叉口车辆数随机,各车辆目的地随机.为保证仿真的有效运行,不至使交通网陷入整体拥堵,初始车辆数满足两个条件,即各车道交叉口车间距大于1 m和各路段车道车间距大于6 m.采用元胞传输模型对交通流状态进行描述.车辆通过交叉口限速60 km/h；各路段车辆限速80 km/h.各交叉口的配时方案与实际路网信号配时相同.

提出的方法用matlab软件验证,仿真时间为1 800 s,每秒仿真一次.

图6 路网图Fig.6 Road network diagram

3.2 仿真结果及分析

将各车道、交叉口的拥堵程度及路径规划标注在一张仿真结果图上,如图7所示.标注方法如下:

路径规划各交叉口用“△”表示,各路段用直线表示.除路径规划外且需要标注的其他路段及交叉口,顺畅的交叉口用圆圈表示,顺畅的路段用虚线表示；不顺畅的交叉口用“●”表示,不顺畅的路段用点划线表示；拥堵的交叉口用“╳”表示,拥堵的路段用“┿┿”线表示.除路径规划外不需要标注的其他路段及交叉口按照顺畅的状态进行标注.

为体现算法优势,对交通状态进行定性表述.本文交通拥堵定义为:路段上平均车速小于10 km/h,则路段拥堵；交叉口处车辆超出信号周期通行能力2倍,则交叉口拥堵.交通不顺畅定义为:路段上平均车速大于10 km/h小于35 km/h,则路段不顺畅；交叉口处车辆大于信号周期通行能力1倍小于信号周期通行能力2倍,则交叉口拥堵.交通顺畅定义为:路段上平均车速大于35 km/h,则路段顺畅；交叉口处车辆小于信号周期通行能力1倍,则交叉口顺畅.

如图7所示,由起点交叉口1至终点交叉口22的路径规划为:1-3-4-5-7-10-11-18-19-20-22.在行驶过程中,标注的不顺畅的交叉口有9、12、14、16、21,不顺畅的路段有3-7、6-13、8-12、9-14、12-16、13-17、14-15、15-21、16-22；拥堵的交叉口有8和15,拥堵的路段有1-8、2-9.标注的其他各路段及交叉口为顺畅.

路径规划中,除路段5-7为不顺畅路段外,其余各路段及交叉口均为顺畅.路径规划避开各拥堵及不顺畅路段和交叉口,利于系统优化.

车辆通过算法路径规划所需的时间为881.7 s.选择其它几个路径进行仿真:通过最短路径1-8-12-16-22所需时间为1 747.5 s；通过路径1-3-7-6-13-17-20-22所需时间为923.9 s；通过路径1-3-4-5-7-6-13-17-20-22所需时间为1 110.2 s.通过比较,这些路径所需时间均比算法所得路径时间长.说明算法得出的路径规划能够节约出行时间,符合单车路径规划目标.

图7 仿真结果图Fig.7 Simulation result diagram

4 研究结论

针对单车路径规划目标与系统路径规划目标的冲突问题,模拟导弹制导的方法,提出了一种考虑系统优化的单车实时动态路径算法.算法提出的理想路径规划,利于交通系统优化和车流量平衡,避免车辆陷入拥堵,节约出行时间.在理想路径基础上,根据实际路网限制和单车路径规划要求,选择出实际路径规划.在车辆行驶过程中,根据交通网交通状态循环滚动地进行未通过路段的路径规划修正,实现单车路径规划的实时动态.仿真结果表明,算法达到使车辆避开拥堵路段,节约出行时间和系统优化(平衡车流量)的预期目标.由此可以预见,交通网中,运用该算法的车辆越多,越利于交通系统优化和车流量平衡.在交通网中,相应的多车路径规划算法有待进一步研究.

[1] Dijkstra E.A note on two problems with graphs[J]. Numer Math,1959(1):269-271.

[2] Zhan F B,Noon C E.Shortest path algorithms:an evaluation using real road networks[J].Transportation Science,1998,31(1):65-73.

[3] Hart P,Nilsson N,Raphael B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Trans Syst Science and Cybernetics,1968(2):100-107.

[4] Brinkho T.A framework for generating network-based moving objects[J].Geolnformatica.2002,6(2): 153-180.

[5] Malandraki C,Daskin M S.Time dependent vehicle routing problems:for-mulations,properties and heuristicalgorithms[J].Transportation Science,1992,26(3): 185-200.

[6] Donati A V,Montemanni R,Casagrande N,et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal of Operational Research,2008,185(3):1174-1191.

[7] Donati A V,Montemanni R,Casagrande N,et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal of Operational Research,2008,185(3):1174-1191.

[8] Tavakkoli-Moghaddam R,Gazanfari M,Alinaghian M, et al.A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing[J].Journal ofManufacturing Systems,2011,30(2):83-92.

[9] 龚龚,李苏剑,刘启生.驾驶员分类的路径诱导系统及评价指标[J].武汉理工大学学报,2013,35(1): 75-81.[GONG Y,LI SJ,LIU QS.Route guidance systemandevaluationindexbasedondrivers' classification[J].JournalofWuhanUniversityof Technology,2013,35(1):75-81.]

[10] Ma J,Fukuda D,Schm?cker J D.Faster hyperpath generating algorithmsforvehiclenavigation[J]. Transportmetrica,2012:1-24.

[11] 戚铭尧,丁国祥,周游,等.一种基于时空距离的带时间窗车辆路径问题算法[J].交通运输系统工程与信息.2011,11(1):85-89.[QI MY,DING G X, ZHOU Y,et al.Vehicle routing problem with time windows based on spatiotemporal distance[J].Journal of Transportation Systems Engineering and Information Technology,2011,11(1):85-89.]

[12] 蓝金辉,郭敏,卢海锋,等.基于协整理论的短时交通流组合预测研究[J].交通运输系统工程与信息. 2011,11(3):71-75.[LAN JH,GUO M,LU HF,et al Short-term traffic flow combination forecast by cointegration theory[J].JournalofTransportation SystemsEngineeringandInformationTechnology, 2011,11(3):71-75.]

[13] 龚龚.模拟导弹制导的车辆路径规划方法:中国, 201210195401.8[P].2012-11-07.[GONGY. Simulated missile guidance for vehicle path planning method:China,201210195401.8[P].2012-11-07.]

[14] GONG Yan,LI Su-Jian.Fusion framework of urban traffic control and route guidance based on cyberphysical system theory[J].Journal of Highway and Transportation Research and Developmen.2013,7(1): 82-89.

[15] Malyavej V,Manchester I R,Savkin A V.Precision missile guidanceusingradar/multiple-videosensor fusionviacommunicationchannelswithbit-rate constraints[J].Automatica,2006,42(5):763-769.

[16] Leng G.Missile guidance algorithm design using inverse kinematics and fuzzy logic[J].Fuzzy Sets and Systems,1996,79(3):287-295.

[17] Omar H M,Abido M A.Designing integrated guidance law for aerodynamic missiles by hybrid multi-objective evolutionary algorithm and tabu search[J].Aerospace Science and Technology,2010,14(5): 356-363

Least-time Path Algorithm Based on Missile Guidance

GONG Yan1,LI Su-jian1,XING En-hui2
(1.School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China；2.School of Mechanical Engineering,Jiamusi University,Jiamusi 154007,HeiLongjiang,China)

A dynamic and real-time single-vehicle path algorithm considering system optimization is proposed by the method of simulating missile guidance.Targeted at minimizing the run-time of a single vehicle,the algorithm plans a path for the vehicle to avoid traffic congestion and help optimize the overall traffic state.This algorithm begins with preliminary path planning to find the points from which ideal paths that help balance the vehicle traffic flow can be generated.Then the algorithm plans for the ideal paths before the actual path is derived from the ideal ones.Throughout the driving process,the algorithm dynamically and cyclically plans the path in real-time,and dynamically revises the plan of the path covering the sections ahead based on the traffic state.Simulation showed that the proposed algorithm effectively enables vehicles to avoid congestion and save travel time,and helps balance the vehicle traffic flow and optimize the traffic state.

traffic engineering；path algorithm；simulating missile guidance；system optimization；ideal path

U491

A

U491

A

1009-6744(2013)06-0094-07

2013-04-24

2013-09-05录用日期:2013-10-12

国家自然科学基金(50908101).

龚龚(1984-),女,吉林通化人,博士生.

*通讯作者:lisujian@me.ustb.edn.cn