The Detector Layout Based On Graph Theory

Under budgetary constraints,it is impractical to install fixed detectors on all sections of the road network in order to obtain the flow of all sections of the road network.How to use the minimum number of detectors to infer the traffic volume of the whole road network is an important problem in this paper.Different from other methods of calculating with the correlation matrix,this paper uses graph theory to determine the minimum number and position of the detector,and simplifies the solving process,which makes the method more convenient to be applied to large-scale networks.Firstly,the description of the traffic network and the basic knowledge of graph theory are introduced.In determining the traffic network,considering the directivity of the traffic flow,the method of solving the directed graph and the minimum tree is introduced in describing the traffic network.When determining the detector layout,we do not need to consider the direction of the road.We introduce the undirected graph and the method of solving the minimum spanning tree.Secondly,in order to make all the nodes in the whole network meet the conditions of traffic flow conservation,a virtual center of gravity method is proposed to reset the traffic network in the network with center of gravity.The topology of the detector is determined by the spanning tree method based on the network satisfying the conservation condition,and the method for estimating the traffic of all the sections of the road network under the detector layout condition is given.Thirdly,considering the actual problem,we often consider the cost of installation.Therefore,this paper gives the method of determining the layout of the detector by using the least spanning tree method after taking the opposite weights of all links in the network.The result of the detector layout is the only conclusion when the weight values are not equal.After determining the layout of the detector with the minimum installation cost,the problem of the placement of detectors under the priority condition is put forward according to the actual needs.Three priority conditions are proposed,which are:1.The priority is to minimize the installation cost,we can install the minimum cost to solve.2.The priority is to install the detector for special sections as early as possible.We can set the weight of these special links to a larger real number and set the weight of the remaining links to a smaller real number.3.In consideration of the minimum installation cost and special road conditions,we can first set the weight of the map to the opposite number,and then set up special sections of roads a positive number.Finally,the feasibility of the methods are verified by using the methods of the detector layout without the center of gravity.Those methods include the method of the detector layout,the layout of the detector with the lowest installation cost,and the placement of the detector under the priority condition.