不确定性交通网络中的top—k 路径查询

潘志安

摘要：该文将交通网络抽象为不确定性图模型，并用概率图的方式研究了不确定交通网络中的top-k路径查询，给出了求解概率图中top-k路径查询的数学模型，提出了一种基于遗传算法的不确定性交通网络top-k路径查询算法，并对算法进行了测试，得到了较好的结果。

关键词：不确定性交通网络；概率图；top-k路径查询；遗传算法

中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2015）04-0066-04

从一个地点出发到达目的地通常有多条路径，一般情况下人们希望选择一条能快速到达的路径，比如“查询从某宾馆到机场的用时最短的路径”。目前的地理信息系统GIS的一项主要功能——路径分析便是用来解决这类问题的[1]。这种问题本质上属于图论中的两点之间最短路径问题。早在GIS建立之前，最短路径问题已经被广泛和大量地研究。

然而现实中的交通网络状态处于不断变化中，不同时段的车流量存在差异，不同车辆的行驶速度也不同，这导致经过某一段路径的时间具有不确定性。用确定的图模型难以描述交通网络的这种不确定性。于是，我们经常会用这样的表述方式：

1） 查询能在30分钟内以至少90%的可能性从某宾馆到达机场的所有路径。

2） 查询能在30分钟内从某宾馆到达机场的可能性最高的[k]条路径；

3） 查询至少能以90%的可能性从某宾馆到达机场的用时最短的[k]条路径。这就表示，交通网络固有的不确定性可以用概率图的方法描述[2]。

3 不确定性交通网络中的[top-k]路径查询算法

传统的最短路径算法Dijstra、A*等不能直接用于概率图中top-k路径查询。该文提出了一种基于遗传算法的改进算法，用于求解概率图中的[top-k]路径查询。

遗传算法是一种仿生优化算法，它模仿的机制是‘一切生命与智慧的产生与进化过程。它通过模拟达尔文“优胜劣汰、适者生存”的原理激励的结构：通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构，同时寻求更好的结构。

3.1 染色体编码

遗传算法使用的染色体编码方式通常有二进制编码方式和实数编码方式。二进制编码方式下，染色体用一个长度为n的二进制串表示，其中n为图中顶点个数，每条染色体代表一条路径，染色体的第i位为1表示编号为i的顶点在此路径中。

3.2 初始化种群

遗传算法的鲁棒性建立在初始种群的多样性基础上，因此，在种群的初始化过程中加入随机因素能保证初始种群的多样性。

3.3 适应度函数

进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。

5 创新点

虽然目前在交通网络最短路径方面国内外已经有了大量研究，但是考虑到交通网络的不确定性因素的研究却很少。智能算法应用于不确定性交通网络的研究还没有。

本文在以上研究的基础上对不确定性交通网络中top-k路径查询进行了研究，并给出了解决这类问题的思路，进一步，提出了一种基于遗传算法的改进算法，实现了不确定性交通网络中的top-k路径查询。

参考文献：

[1] 刘学军，徐鹏.交通地理信息系统[M].北京：科学出版社，2006：28-54.

[2] M. Hua，J. Pei. Probabilistic Path Queries in Road Networks： Traffic Uncertainty Aware Path Selection[C].Proceedings of the 13th International Conference on Extending Database Technology （EDBT'10）， Lausanne， Switzerland， 2010 March ：22-26.

[3] Fu L.Heuristic shortest path algorithms for transportation applications： State of the art[J].Computers and Operations Research，2006，33（11）：3324-3343.

[4] 康晓军，王茂才.基于遗传算法的最短路径问题求解[J].计算机工程与应用，2008，44（23）：22-23，35.

[5] 邹亮，徐建闽.基于遗传算法的动态网络中最短路径问题算法[J].计算机应用，2005，4（25）：742-744.