解决路网检测器布局问题的数形结合方法

An Algebraic and Graphic Combination Approach to Solve Network Sensor Location Problems

为了获取各路段的交通流量,本文提出一种解决任意路网中检测器布局优化问题的数形结合方法.首先基于交通网络的拓扑结构与代数关联矩阵间的联系定义平衡矩阵和基本平衡矩阵;然后根据基本平衡矩阵的特点,找到n-1阶数(比网络节点数少1)可逆矩阵M,该矩阵所对应的路段集合就构成路网的一个支撑树(不需要安装检测器的路段集合);最后根据流量守恒原理进行矩阵运算,全面、准确、快速地推算出未安装检测器路段的交通流量.该方法揭示了路网中各路段流量间的数形联系,并避免了单独利用代数或图论方法的操作复杂性,以及获取交通信息不及时性.通过具体算例验证了此方法的可行性和有效性.

To obtain the traffic flows on the uninstalled links, an algebraic and graphic combinational approach to determining the optimal sensor locations is proposed. Firstly, based on the connection between the topological structure of traffic network and the algebraic adjacent matrix, the definitions of the equilibrium matrix and the basic balance matrix are presented. Secondly, based on the property of the basic balance matrix, an invertible matrix whose order is one less than the number of nodes can be found out. The set of links corresponding to the above invertible matrix forms a spanning tree of the traffic network. All the links in the spanning tree need not to install sensors. At last, according to the flow conservation principle, the traffic flows on all the uninstalled links can be deduced quickly and accurately through matrix operations.The new method uncovers the algebraic and graphic connections among the link flows and avoids the complexity due to the independent application of algebraic or graphic method. The feasibility and effectiveness of this new method is verified by numerical analysis.