车辆导航系统中多路径选择算法的研究

欧阳浩亚

(湖南省醴茶高速公路建设开发有限公司，湖南株洲 412000)

0 引言

车辆导航系统是在路网数字化地图的基础上，运用GPS、DR(Dead Reckoning)等定位技术进行车辆定位，为驾驶员提供路径引导信息，使车辆避开拥挤区域，沿最佳路线到达目的地。车辆导航系统由四个子系统组成，路线选择子系统是其核心组成部分之一，它的基本功能是在已知的路网上，按照一定的算法，为车辆驾驶员提供一条优化合理的行驶路线，引导车辆快速、安全到达目的地。

近年来，随着经济的快速发展，城市的车流量越来越大，城市交通状况日渐复杂化，交通拥堵现象日趋严重。为了缓解交通压力，国家相关部门提出大力投资交通基础设施建设，单行线、路口禁止转向等交通管制措施也被广泛的采用，但是，机动车的增长速度远远超过道路基础设施的建设速度，各种交通管制措施同时增加了出行的复杂性，于是，交通压力越来越繁重。而且，汽车在遇上交通拥堵的情况下，废气的排放量是平时的好几倍，燃油量也远远高于正常速度行驶的汽车，针对以上形势，如何引导出行者根据自己的需求选择最优的路线，使其能够尽量避免拥堵，避免违规驾驶，安全、顺利、便捷的到达目的地是我们迫切需要解决的问题。对于交通管理者来说，出行者合理的路径选择可以使交通流尽量合理地分配在整个路网上，达到在现有的道路基础设施中实现“路畅其行，货畅其流”的优化效果。因此，车辆导航系统中的路径选择子系统就应运而生了，并且拥有巨大的应用前景和市场前景。

目前，大多数的路径选择子系统都能根据一定的目标与约束条件(如出行距离)，在出行者指定的起讫点寻找一条最短行驶路径，但由于车辆行进中交通状态通常不稳定，出行者路径选择心里的复杂性，往往单一的仅考虑出行距离的行驶路线不能适应交通流分配的需要和出行者的心理需要。例如出行距离最短的路线上交通十分拥堵、出行者考虑必须通过某条路等。因此，一个先进、有效的路径选择子系统不能只为用户提供单一的路线优化方案，还应提供次优、次次优、...、K优等一系列合理的备选路径方案供出行者根据实际情况进行选择。

对于车辆导航系统中的路径选择算法，目前国内外已有一定的研究，一般情况下，路网节点较多的时候都需要用启发式算法来求解，在路径选择的遗传算法研究方面，文献［1～5］都进行了研究。David Eppstein［6］给出了一个新的简单路径的有效算法，M.H.Macgregor［7］考虑在通信网络中 K 最短路径问题。文献［8］作者提出了任意两点间K条最优路径问题的遗传算法。该方法采用节点的自然路径作为染色体编码，根据路径节点的连接实施染色体的交叉操作，将节点路径块作为染色体的变异基因块实施变异操作。为探索不同遗传算法在K最短路上的求解性能，为出行者更合理、有效的选择行驶路线，本文设计了单亲遗传算法来求解K最短路问题。

1 单亲遗传算法及算子设计

1.1 编码

将问题的解编码成为染色体是遗传算法使用中的关键问题，它直接影响到解码操、适应度计算和交叉、变异等算子的操作。设路网图为G=(V，E)，V为节点构成的集合，E为路网上边所构成的集合，节点由边相连，各边权值为dij，节点的序列为对应的路径。

个体编码采用自然数编码方式，如1-2-4-13则表示从起点1到终点13的一条路径，该路径途径节点2和节点4。由于起点到终点的路径上途径节点的个数不确定，所以个体编码采用变长度的染色体方式。

1.2 适应度函数

该问题的数学模型为最小化问题，故可以建立适应度函数和目标函数的映射关系，使得个体越优良其适应度值越大。具体为:

其中fitki代表第i代个体k的目标函数值，fik为第i代个体k的适应度值，P为一个足够大的常数，由于在程序测试过程中发现最差个体适应度值小于1 000，本文程序中的常数P值设置为1 500。

1.3 选择算子

遗传算法使用选择算子(或称复制算子)来实现对群体中的个体进行优胜劣汰操作:适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体，被遗传到下一代群体的概率小。

在本研究中我们用随机生成方法产生初始种群，然后按适应度比例方法(轮盘赌选择)从父代中每次挑选两个个体，以相应的概率参加下面的变异操作。但是考虑到变异操作会使得父代个体优良基因不能很好遗传到下一代，本文在采取轮盘赌选择的基础上，增加了最佳个体保留策略。也就是在交叉完成之后，将父代个体中的最优个体直接复制到下一代种群中。

1.4 变异算子

变异操作是为了在运算过程中能改变某些成员的值，以避免失去一些有用的基因，防止某些成员的值处于不变的状态，是一种防止算法早熟的措施。

考虑到在路径中有两种可能的方式使得路径的长度变短。首先，在某一路径中添加一个新的节点就有可能使得路径长度更短。假如有路径1-2-4-13，如果在节点2和节点4之间插入节点3使得路径变为1-2-3-4-13，而路径1-2-3-4-13有可能比路径1-2-4-13更短。其次，更多的时候删除路径中的一些节点也有可能使得路径长度变短。如路径1-2-4-13中删除节点2使得路径变为1-4-13。

基于这样两种思路，本文设置了两个变异算子。

设有路径a-b-c-d-e-f-g-h:

1)变异算子1:在初始路径中随机生成要插入的节点的位置，如为c，判断是否有节点和节点c以及节点d都相邻，若存在这类节点(如符合要求的节点为j，k)，则随机选择一个这类节点(如为j)插入到c和d之间，形成新的路径a-b-c-j-d-e-f-g-h。

2)变异算子2:在初始路径中随机生成要删除的节点的位置，如为c，顺序地从路径最后的节点h到c之间查找是否存在节点f(从最后的节点开始删除是基于更多节点的删除能带来路径长度更大的节省)，使得c和该节点相邻，若存在，则删除c和该位置节点之间的所有节点，形成新的路径a-b-c-f-g-h。

2 算法流程

单亲遗传算法流程如图1所示。

图1 单亲遗传算法流程图

3 算例验证

为了验证算法结果的正确性，本文选取湖南长沙市某区域的实际路网进行验证，图中的节点表示实际道路的路口，每两个节点之间的权值代表行驶距离。该算例路网有26个节点，其具体的路网结构图如图2所示。

第n次 符合数 第n次 符合数1 10 11 10 2 9 12 10 3 9 13 9 4 10 14 10 5 9 15 9 6 10 16 10 7 10 17 10 8 9 18 9 9 10 19 10 10 10 20 10

图2 路网结构图

在输入起点、终点和所要求的最短路的条数后，迭代200代，在CPU 1.66 GHz内存下运行约4 s可求出结果，结果如表1所示。

图3 收敛效果图

表1 路径表

用该程序连续运行20次，求解起点为1，终点为26的10条最短路径。为了检验本算法的效果，本文主要考虑两个方面。一是连续运行20次所得到的10条最短路与实际10条最短路相比符合的条数;二是20次运行中收敛效果最佳的一次迭代过程中每代个体中最佳的10个个体的适应度的平均值。

20次运行中，每次得到的十条最短路和实际的10条最短路相比符合的条数如表2所示。

20次运行过程中，收敛效果最佳的一次的迭代过程中，每代个体最佳的10个个体的适应度平均值收敛效果如图3所示。

通过以上计算结果和分析可以看出，本文所设计的单亲遗传算法在求解K最短路问题时能够一次生成多条备选优化路径供出行者根据实际情况进行路径选择，并且算法稳定性好，收敛速度快，求解质量高。

4 结论

车辆导航系统是交通发展的必然产物，本文主要对车辆导航系统中的路径选择子系统进行路径优化算法的研究，通过设计一种性能良好的单亲遗传算法来求解K最短路问题，并运用实际的算例进行了验证。结果表明，该算法能较好的根据出行者的实际需求生成多条路径供出行者选择。

此外，由于城市交通的复杂性，本文只对K最短路的算法进行了研究，很多影响交通出行的因素并没有和路径选择方案结合起来进行具体的分析，实际上，还有很多问题值得进一步探讨和研究。

1)出行者根据自己的客观需求选择行使路线是比较单一的选择方案，但是，在交通实时信息不断变化的情况下，如何把车辆导航系统中获取的关于道路的流量、速度与密度的关系等实时信息和K最短路结合起来进行路径选择的决策，仍待进一步研究。

2)在路线选择子系统中嵌入影响交通出行的因子，如道路畅通度，并设定当道路畅通度达到一定的值时才考虑该行驶路径，当每条路径的道路畅通度的值都很小时，我们可以初步判断该路网已接近饱和，亟需增加交通基础设施建设来缓解交通出行问题。

［1］李成银，江务学.VC环境下遗传算法在网络最短路径优化中的设计与实现［J］.电脑开发与应用，2007，20(11):55-56.

［2］王丽星，郜 巍.多条最短路算法的优化［J］.科技情报开发与经济，1999(2):32-33.

［3］邹 亮，徐建闽.基于遗传算法的动态网络中最短路径问题算法［J］.计算机应用，2005，25(4):742-744.

［4］刘汝正.基于遗传算法的最短路径的计算［J］.微计算机信息，2007，24(5):214-215.

［5］田奇君.基于遗传算法的最短路径问题求解实现［J］.中国科技信息，2005(10):33.

［6］John Hershberger，Matthew Maxely，Subhash Suriz.Finding the K shortest simple paths:A new algorithm and its implementation［Z］.ALENEX Baltimore，2003.

［7］Macgegor M H，Grover WD.Optimized k-shortest-paths algorithm for facility restoration［J］.Software Practice and Experience，1994，24(9):823-828.

［8］马 炫.求解k条最优路径问题的遗传算法［J］.计算机工程与应用，2006(12):100-101.