A^＊算法在公共交通诱导系统中的应用研究

Research in the Application of A^＊ algorithm to Public Transportation Guidance model

由于在采用以往的公交路网描述方法的公交网络中，存在大量两节点有多条同向边的情况，而这种情况使得无法求解公交网络中的最短路径问题。提出了公交路网描述方法和以其为基础的多目标公共交通诱导模型，并证明了此描述方法不仅能够完全的描述整个公交路网，而且还能够用于求解多目标的公交诱导问题；同时提出采用A^＊算法来求解公共交通诱导问题；最后，以广州市的公交线路网络为例，对公交诱导模型进行了试验，试验结果表明本文提出的算法是十分有效的，多目标模型的平均计算时间仅为0．1秒。

There is more than one link between two nodes with the same direction.in public transportation networks described by past description, which induces that shortest path problem in public transportation networks can not be solved. This paper brings forward the method of describing a public transportation networks and four kinds of public transportation guidance models based on it. It is also proved that the method can perfectly describe a public transportation networks and be used in the problem of multi-objective public transportation guidance. The paper extends the A^＊ algorithm to shortest route problem in public transportation guidance systems. Finally, the developed algorithms are implemented with Guangzhou＇s public networks containing 471 bus, 1040 stops and their computational performance is analyzed experimentally. The result indicates that A^＊ algorithm proposed in this paper are very efficient and the average computation time of A^＊ algorithm is only 0.1 second.