高速公路标识站选址模型与算法研究

以路网拓扑结构为基础，采用图论中的支撑树理论来研究高速公路标识站数量及选址问题。基于支撑树任意两点之间恰有一条路径的性质，定义了余边集的概念，在此基础上提出了标识站确定理论，从根本上确立了标识站最优数量，并将破圈法与展开树法有机结合，提出了适合大型路网的标识站选址算法。标识站数量确定理论和展开树算法，从根本上解决了路网收费中二义性路径的标识问题，可以直接用于高速公路及城市轨道的标识站设计与建设中，能够确定所有标识站选址方案。给出了一个试验实例以证明该理论与算法的可行性。

Study on Positioning Model and Algorithm of Identifier of Expressway

An identifier-selection theory was presented to decide the number and position of identifiers on expressway. It is based on the property of spanning tree that there is only one path between any two nodes as well as the concept of residual edge set put forward by the author, which decides the optimal number of identifier and comes to the conclusion that identifiers should locate on the residual edge set, In addition, an effective algorithm adaptable to huge network was presented in order to find the whole residual edge set. The basic consideration of the algorithm is to combine the ring-destroying algorithm with developed tree algorithm. The theory put forward in the article is in favor of the resolve of optimal identifier in on-line charge, it can be used for optimal identifier design and construction of expressway and urban rail. A result was provided to demonstrate the feasibility of the theory and the algorithm.