自适应代价函数的GPS路线决策研究

李中华，杨 进，倪明涛,王 慧

(1.乐山师范学院 智能信息处理及应用实验室，四川 乐山 614000；2.乐山师范学院 数信学院，四川 乐山 614000)

0 引 言

GPS是全球定位系统(Global Positioning System)的简称，利用导航卫星进行检测和数据交换[1-2]。GPS目前得到广泛应用，如航海，航空和道路运输等。其中道路运输最普遍，也即为车载GPS。

随着中国经济的发展，道路建设得到快速发展，同时人们对车辆的拥有量也在大幅度增加。从而导致城市交通拥堵，影响上班和出行，造成交通事故。因此，准确掌握道路交通状况，根据个人需求选择有效路径成为关键。然而，传统的路径规划方法和代价函数都很简单。文献[3-5]分别提出了采用蚁群算法优化路径的方法，考虑了通行时间、路径距离和路况信息，基于多参数优化理论进行寻优；姜钰梁，等[6]对GPS动态数据进行了分析，提出了有效避免干扰的动态数据提取算法；孙文彬，等[7]主要针对单源单汇网络提出了一种最短路径搜索的并行算法；文献[8-12]分别就路径优化的某单一领域进行了研究。

这些学者尽管对GPS路径优化进行了研究，但对目前复杂的GPS路径优化，仅考虑单一因素以及将道路状况简单化描述，或者固定代价目标等都是不够的。而且，不能实现由用户随时定制GPS路径决策的代价函数，从而在实际应用中缺乏灵活性。随着道路复杂度增加，影响到达目的地的因素也非常多。如何通过算法来根据需求对代价函数实现自适应调整，从而求解相应的最佳路径，是笔者的主要研究目标。

笔者将所有影响交通运行的道路状况指标，如路程，道路等级，堵车概率，临时通车政策，节假日通车情况，堵车时段等考虑为路况集，由这些集合的综合指标构成道路的网络边权，然后根据用户的目标函数采用路径寻优算法确定最佳路径。

1 GPS路线决策数学模型

1.1 GPS终端对电子地图路况分析

城市道路路况对车辆的行车消耗是不同的，不同条件将产生不同的结果。算法的目的就是根据用户最关心的目标内容，由GPS终端对每个路径进行分析，找出影响用户关心的目标函数最小的路径，称为最优路径。

定义1：假设描述一段路况的参数为G={g1，g2，…，gn}，其中：g1为路程；g2为道路等级；g3为交通拥挤率；g4为交通拥挤量；g5为假日交通状况；g6为交通禁令；…。

为得到线路对用户需求代价函数影响的综合指数，采用权重求和方式，算法如下。

假设权重向量P=[P1，P2，…，Pn]；线路综合路况指标为r，则：

r(i，j)=P×G=[P1g1+P2g2+…+Pngn]

(1)

式中：r(i，j)表示i，j间直接连接线路的路况综合指标；n为G中所包含元素个数；Pi∈[0，5]根据gi对代价函数的影响大小来确定；gi是根据路况条件对代价函数的影响将其转换成距离的兑换因子。

所以式(1)可以改写为：

r(i，j)=P×G=[g1+P2g2+…+Pngn]

(2)

由式(2)可知，r(i，j)实际上是考虑了其它路况等信息后得到的综合线路长度，其值是≥g1的。根据定义1，确定各路况信息的兑换因子数，如式(3)：

(3)

当道路存在交通禁止时或只能逆行时，g6=1；这时对应的P6=∞。

1.2 GPS终端最优路径计算

根据用户各个具体条件下对目标指数的要求不同，自适应调整代价函数。

用户代价函数集J={Jt，Jf，…}

(4)

式中：T[i,k]为i,k两点间的消耗时间；F[i,k]为i,k两点间的消耗费用；Jt(i，j)为i，j两点间的消耗时间；Jf(i，j)为i，j两点间的消耗费用；i为起始地；j为目的地；N为节点集。

当i，k之间出现禁止通行和逆行等临时交通规定或没有直接连接时，T[i,k]和F[i,k]等目标函数值为∞，但是为迭代能统一进行和保证计算的收敛性，可以将此时的T[i,k]和F[i,k]值取为远远大于其余路线的消耗值，如取1 000等。最具有代表性的算法就是DIJKSTRA，该算法主要用于解决图论中最优路径求解问题。对于GPS路径优化问题，只要将影响行车的路况条件数学模型建立起来，就是路径优化问题，采用DIJKSTRA算法是最有效的。

算法原理如下：假设网络中总节点数为N；计算节点集为Q；P0为路径计算时的初始节点；d(i，j)为节点i和j之间的距离；S(P)为源节点到P节点间最短距离；最初Q=[P0]。进行如下步骤：

步骤1: 读取各段线路的路况化模型参数，根据下式进行计算最短路径。

(5)

步骤2: 在N集中新增一个点，根据式(6)计算最短路径。

(6)

重复第2步，直到Q=N，结束。

2 仿真实验

假设有的城市道路交通拓扑图，如图1。

图1 城市道路网络Fig.1 City road network

图1中每个节点代表一个地点或道路岔口，两点之间的连线代表道路，道路的综合状况用边权描述。根据用户不同的代价函数要求，边权的含义不一样。如果用户要求两点之间所耗时间最短，则系统自动将道路状况转换为时间。如果用户要求两点之间油耗最少，则系统自动将各道路的状况转换为标准油耗指标作为边权，等等。

条件：假设道路状况信息如表1。道路的权重为[1,0.5,1,2,0.8,1]，根据图2的仿真计算结果，假设要从1节点到9节点，要求所消耗时间最少，则GPS自动确定的路径是：1→2→4→9。

表1 网络中各道路路况信息Table 1 Conditions of roads

(续表1)

g1g2g3g4g5g610．84800．61310．91530．2490010．08160．75190．64150．5902010．13990．16260．66130．3607010．28730．77300．01350．7196010．82800．77150．86360．3356010．55480．85460．18810．4780010．32040．54270．26470．2238010．77970．59430．18120．4244010．87740．26310．53970．6218110．57080．49570．51860．0913010．55950．99140．70090．1492010．71070．13460．78460．1495010．33210．33070．25550．0888010．93770．01510．91510．67800

图2代价函数J最小的路径
Fig.2ThesmallestrouteofcostfunctionJ

3 结 语

笔者将城市道路路况信息按照用户定义的目标不同转换成等价的路线长度指标，然后用道路长度指标作为拓扑图的边权，采用图论中最有效的求最优路径的方法求出满足用户要求的最优路径。该最优路径就是GPS导航仪指示的行车路线。经对14节点的道路系统进行仿真，得出了各对节点间的最优路线，仿真结果证明该方法是有效的。

[1] 朱玉玺,崔如春,黄峻艺.“GPS最短路径”搜索研究与实施[J].计算机工程与设计,2005,26(9):2437-2438.

Zhu Yuxi,Cui Ruchun,Huang Junyi.“GPS shortest path”search study and pratice[J].Computer Engineering and Design,2005,26(9):2437- 2438.

[2] 范晓燕,周乾.GPS测量中多路径效应研究综述[J].工程地球物理学报,2010,7(3):382-387.

Fan Xiaoyan,Zhou Qian.Review of multipath effects in GPS measurement[J].Chinese Journal of Engineering Geophysics,2010,7(3):382-387.

[3] 唐炉亮,常晓猛,李清泉,等.基于蚁群优化算法与出租车GPS数据的公众出行路径优化[J].中国公路学报,2011,24(2):89-96.

Tang Luliang,Chang Xiaomeng,Li Qingquan,et al.Public travel route optimization based on ant colony optimization algorithm and taxi GPS data[J].China Journal of Highway and Transport,2011,24(2):89-96.

[4] 伊廷华,张永恒,李宏男,等.基于改进粒子滤波算法的GPS多路径效应理论与试验研究[J].应用基础与工程科学,2011,19(3):429- 441.

Yi Tinghua,Zhang Yongheng,Li Hongnan,et al.Theoretical and experimental investigations of GPS multipath effect based on improved particle filtering algorithm[J].Journal of Basic Science and Engineering,2011,19(3):429-441.

[5] 王安保,胡小明.基于GPS的启发式Ad hoc路由算法研究[J].计算机应用研究,2010,27(12):4708-4710.

Wang Anbao,Hu Xiaoming.Heuristic routing algorithm based on GPS location information for Ad hoc networks[J].Application Research of Computers,2010,27(12):4708-4710.

[6] 姜钰梁,谭智力,黄玉金.基于GPS的移动平台路径控制方法研究[J].湖南科技大学学报：自然科学版,2010,25(4):43-46.

Jiang Yuliang,Tan Zhili,Huang Yujin.Investigation of path control method in GPS navigation[J].Journal of Hunan University of Science & Technology:Natural Science,2010,25(4):43-46.

[7] 孙文彬,谭正龙,王江,等.最短路径算法的并行化策略分析[J].地理与地理信息科学,2013,29(4):17-20.

Sun Wenbin,Tan Zhenglong,Wang Jiang,et al.An analysis of parallelizing shortest path algorithm[J].Geography and Geo-Information Science,2013,29(4):17-20.

[8] 李芳芳,刘栋,高宪文,等.基于多目标规划的WSN路径动态选择算法[J].东北大学学报：自然科学版,2013,34(8):1082-1085.

Li Fangfang,Liu Dong,Gao Xianwen,et al.Dynamic routing algorithm based on multi-objective programming for WSN[J].Journal of Northeastern University:Natural Science,2013,34(8):1082-1085.

[9] 李耀军,潘泉,赵春晖,等.基于空间关系几何约束的无人机景象匹配导航[J].计算机应用研究,2010,27(10):382-385.

Li Yaojun,Pan Quan,Zhao Chunhui,et al.Scene matching navigation for UAV based on spatial relationship geometric constraints[J].Application Research of Computers,2010,27(10):382-385.

[10] Lin Shuying,Cai Wenxue.Logistices vehicle routing problem between two objects based on real-time traffic data[C]// IEEE International Conference on Service Operations and Logistics and Informatics.New York:IEEE,2008:2989-2994.

[11] 王亚洁,贾顺平,蒋金亮.城市生活垃圾收运路线优化模型及算法研究[J].重庆交通大学学报：自然科学版,2012,31(5):1024-1026.

Wang Yajie,Jia Shunping,Jiang Jinliang.Model and algorithm study for route optimization of municipal solid waste collection and transportation[J].Journal of Chongqing Jiaotong University:Natural Science,2012,31(5):1024-1026.

[12] 任其亮,乔丹.灾后应急救援运输路径优化模型研究[J].重庆交通大学学报:自然科学版,2010,29(6):951-954.

Ren Qiliang,Qiao Dan.Emergency rescue transportation route optimization model after disaster[J].Journal of Chongqing Jiaotong University:Natural Science,2010,29(6):951-954.