# Sensor Location Problem for Network Traffic Flow Derivation Based on Turning Ratios at Intersection

Authors: Minhua Shao; Lijun Sun; Xianzhi Shao
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

The sensor location problem (SLP) discussed in this paper is to find the minimum number and optimum locations of the flow counting points in the road network so that the traffic flows over the whole network can be inferred uniquely. Flow conservation system at intersections is formulated firstly using the turning ratios as the prior information. Then the coefficient matrix of the flow conservation system is proved to be nonsingular. Based on that, the minimal number of counting points is determined to be the total number of exclusive incoming roads and dummy roads, which are added to the network to represent the trips generated on real roads. So the task of SLP model based on turning ratios is just to determine the optimal sensor locations. The following analysis in this paper shows that placing sensors on all the exclusive incoming roads and dummy roads can always generate a unique network flow vector for any network topology. After that, a detection set composed of only real roads is proven to exist from the view of feasibility in reality. Finally, considering the roads importance and cost of the sensors, a weighted SLP model is formulated to find the optimal detection set. The greedy algorithm is proven to be able to provide the optimal solution for the proposed weighted SLP model.


---

## Body

## 1. Introduction

Link flow data in the road network is the valuable information in many applications of traffic planning and management, such as the road network planning and the congestion analysis. Placing traffic sensors on every link is usually not realistic, because there are thousands of links in the urban road network normally and the investment on sensors installation and maintenance will be huge. So it is important to identify the subset of links so that the traffic flow on every link in the network can be inferred if sensors are installed on this subset of links to collect flow data. The sensor location problem (SLP) was proposed to address this problem.The SLP has attracted increasing interest in the past few years for its importance in the area of transportation system analysis. Two main classes of SLP were summarized by Gentili and Mirchandani [1]: sensor location flow-observability problems and sensor location flow-estimation problems. The objective of the first-class SLP is to find the optimal sensor locations so that all link flows (or partial link flows) can be determined uniquely. The second-class SLP is trying to improve the accuracy of the estimation by optimizing the sensors locations. Early research in the literature mainly focused on the second-class SLP as a subproblem of origin-destination (OD) estimation. The “OD Covering Rule” was given by Yang et al. [2, 3] to guarantee the upper-bounded OD estimation error. Several other rules were also proposed to improve the estimation accuracy, like the “maximal flow fraction rule,” the “maximal flow-intercepting rule,” and so on (for details, see [1–5]). The first-class SLP was not formally defined until 2001. Bianco et al. [6] defined SLP as determining the minimum number and locations of counting points to infer all traffic flows in the network. We will focus on the first-class SLP in this paper.The first-class SLP was proposed in the context of traffic planning and also was developed in this domain in most of the following research. So, essentially, it is a static optimization problem addressing the method of network sensor deployment under the steady-state traffic condition. Generally, in the sensor location flow-observability problems, a system of linear equations will be formulated at first, which represents the relationship of different link flows or the relationship between link flows and route flows (or OD trip) under the law of flow conservation. This system of equations is defined as the flow conservation system in this paper. Then, by deploying the sensors, equations representing the detected link flows will be added. These equations are defined as the detecting equations. The number of the detecting equations is equal to the number of sensors. Basically, the main idea of the first-class SLP is to find the optimal detecting equations so that all the variables are solvable. According to this idea, the SLP was normally designed as an integer linear programming model in the existing studies. The difference among these studies lies in the assumptions on the prior information, which lead to different formulations of the flow conservation system. According to the prior information, three kinds of flow conservation systems are formulated: OD-link based system, route-link based system, and link-link based system [1]. The OD-link based system uses the link choice proportions as the prior information, which is defined as the proportion of trips between one OD pair that uses a given link in the network. Similarly, the route-link based system uses the link-route coefficients as the prior information. When a link is used by a route, the corresponding coefficient will be 1; otherwise, the coefficient will be zero [7]. These two kinds of systems use the OD trips or route flows as the bridge between detected link flows and undetected link flows. So the OD matrix and route flows will be obtained at the same time. However, in the scenarios when the link flow is the only information we care about, the effort used in calculating the OD trips and route flows is not necessary. In particular for the route-based system, enumerating all routes is not easy for a large-scale network. At the same time, if we are only interested in the link flows of one small local network, the whole network still needs to be considered in the SLP since the OD trip and route flow are defined over the network. The third kind of system uses the relationship of the link flows directly. Without using the concept of OD trip or route flow, this kind of system can be used to formulate the SLP for local network. Bianco et al. [6] proposed the first system of this kind in 2001, using the split ratios of outgoing roads at intersections as the prior information. The split ratio of an outgoing link at an intersection is defined as the fraction of the flow on the outgoing link over the total incoming flow of the intersection. With the assumption of symmetrical network and node-based detection (the sensors are located on every in- and out-link of the intersection), a necessary condition was given to guarantee that the number of equations in the system is not less than the number of variables. They also presented a couple of greedy heuristics to find the lower and upper bounds on the number of sensors for random networks. After that, Bianco et al. [8] proved that the SLP proposed in 2001 is NP-hard in the computation complexity. Linear algorithms were invented for several special graphs, including the paths, circles, and combs. Based on the work of Bianco, Morrison et al. [9, 10] gave a stricter necessary condition for general graphs and proved the condition to be also sufficient for the special network with trees as its unmonitored components. Essentially, the network structure-driven logic is used in the link-link based sensor location flow-observability problems. So the traffic flows over the network are calculated based on the network topology and any behavior assumption of the road users is not required [6].Until now, most discussions on the link-link based sensor location problems used the split ratios as the prior information. The network was assumed to be symmetrical and the detection was assumed to be node based. However, in reality, unidirectional roads normally exist, which leads to an asymmetrical network. At the same time, road-based detection is more reasonable. In this paper, the network is allowed to be asymmetrical and the detection is assumed to be road based. Turning ratios at intersections are used as the prior information. The turning ratio is defined as the ratios of flow turning from an incoming link to an outgoing link over the total flow of the incoming link. Turning ratio is used as a popular parameter in many applications. Many methods were designed to obtain the turning ratios (for details, see [11–13]), which make the estimation of turning ratios from historical data possible. Using turning ratios as the prior information, an integer linear programming model is designed in this paper to address the sensor location flow-observability problem under steady-state traffic conditions.The present paper is organized as follows. In Section2, the definition and assumptions of the road network used in this paper are specified. Then, the flow conservation system is formulated in Section 3 based on the turning ratios. After that, the coefficient matrix of the flow conservation system is proven to be full rank in row space. Based on that, in Section 5, the SLP model is given and the greedy algorithm is set up to solve the model. Finally, some conclusions are summarized.


## 2. Definitions and Assumptions

Suppose the road network is composed ofn directed roads. The roads are numbered by 1,2,…,n. Represent the roads set as RD=1,2,…,n. Six assumptions are used in this paper.Assumption 1.
The road network which we are interested in is taken from a bigger one so that on the boundary there are directed roads whose upstream or downstream intersections are missing.Definitions for Three Categories of Roads. Under Assumption 1, there must be three categories of roads in a network: incoming/outgoing road, which connects two adjacent intersections; exclusive incoming road, whose downstream intersection is in the network but the upstream intersection is not; exclusive outgoing road, whose upstream intersection is in the network but the downstream intersection is not. Figure 1 gives an example of a simple network including only two intersections.Figure 1
A simple network example.In the network of Figure1, roads 4 and 8 are the incoming/outgoing roads, roads 9, 10, 11, 12, 13, and 14 are the exclusive incoming roads, and roads 1, 2, 3, 5, 6, and 7 are the exclusive outgoing roads.Represent the set of the incoming/outgoing roads asRDio, the set of exclusive incoming roads as RDein, and the set of exclusive outgoing roads as RDeout. Let RDout=RDio∪RDeout and RDin=RDio∪RDein, which represent the set of the outgoing roads and the set of incoming roads, respectively. We have RD=RDio∪RDein∪RDeout=RDout∪RDein=RDin∪RDeout. Suppose there are m roads in RDout and n-m roads in RDein.Assumption 2.
Turning ratios for any road inRDin are known.Definition for Turning Ratios. The turning ratio is defined as the proportion of the flow on an incoming road which turns to an outgoing road at the intersection. Denote the turning ratio of traffic flow turning from road j to road i at intersection as aij and the traffic flow on road j as xj. The traffic flow turning from road j to road i at intersection is aij×xj.Assumption 3.
Flow conservation law is satisfied at the intersection.For an outgoing roadi without trips originating or terminating, the traffic flow is equal to the sum of the flows turning into it from all the incoming roads at the intersection. Using xi as the traffic flow on outgoing road i, we have(1)xi=∑j∈RDin,j≠iaijxj.Definition for Net Balancing Flow. For the outgoing roads which have trips originating or terminating, the net balancing flow of the outgoing roads is defined as the originating trips minus the terminating trips. Denote the net balancing flow on road k as sk and then for road k, we have(2)xk=∑j∈RDin,j≠kakjxj+sk.Suppose there areg roads in set RDout which have nonzero net balancing flows. Normally, g is far smaller than the size of RDout, especially when the analysis period is long enough.Assumption 4.
For any road setA⊆RDio, there must be at least one road j∈A which has a turning ratio aij>0, where road i∉A.If in road setA⊆RDio, all the turning ratios are directed to the roads inside the set, and then the traffic inside the set will never flow out. So Assumption 4 is actually to say that the turning ratios should not define a self-circulation system. This assumption is reasonable because any part of the road network has to be able to exchange traffic with another part.Assumption 5.
Traffic flows are assumed to be detected based on roads.Once a road is detected, the traffic flow on the road is known.Assumption 6.
The detecting flows and turning ratios are both assumed to be error-free.


## 3. Flow Conservation System Based on the Turning Ratios

From Assumption3 in Section 2, we know that, for any road in set RDout, either (1) or (2) can be formulated. In order to simplify the expressions of the flow conservation system and the corresponding parameters, we renew RD by numbering all the roads in RDout at first so that RDout=1,2,…,m and RDein=m+1,m+2,…,n. On the other hand, the nonzero net balancing variable si is looked at as the traffic flow on a dummy road which is an incoming road of the corresponding outgoing road with 1 as the turning ratio. The dummy roads can be looked at as the exclusive incoming roads. Compared to the real exclusive incoming roads, the dummy roads may have negative flows. To illustrate the method to add the dummy roads into the network, we suppose that there is a nonzero net balancing flow on road 4 in the network of Figure 1. Dummy road 15 is added to the network as shown in Figure 2. The turning ratio from dummy road 15 to road 4 is set to be 1, which means all the flow on dummy road 15 will turn into road 4.Figure 2
A dummy road example.The dummy roads are numbered after exclusive incoming roads. Theg roads compose set F=n+1,n+2,…,n+g. Using X=x1,x2,…,xj,…,xn+g′ to represent the traffic flow vector of the network, where xj is the traffic flow on road j, j∈RD∪F, the flow conservation system can be formulated as follows:(3)∑j∈RDin∪F,j≠1a1jxj-x1=0,∑j∈RDin∪F,j≠2a2jxj-x2=0,⋮∑j∈RDin∪F,j≠mamjxj-xm=0.The coefficient matrixC1 of system (3) can be expressed as follows:(4)C1=a11a12⋯a1j⋯a1m⋯a1n⋯a1n+ga21a22⋯a2j⋯a2m⋯a2n⋯a2n+g⋮⋱⋮ai1ai2⋯aij⋯aim⋯ain⋯ain+g⋮⋱⋮am1am2⋯amj⋯amm⋯amn⋯amn+g.C
1 is m×(n+g) matrix. The entries aij are given as follows:(5)aij=-1wheni=j0<aij≤1wheni≠jand  roadjhas  flows  turning  onto  roadiat  an  intersection0otherwise.And we have∑1≤i≤m,i≠jaij=1 for j∈RDin∪F and ∑1≤i≤m,i≠jaij=0 for j∈RDeout.The flow conservation system can also be written in the following form:(6)C1X=0.


## 4. Proof for the Full Row Rank of Coefficient Matrix

The objective of sensor location flow-observability problem is to find the minimum number and locations of counting points to infer all traffic flows in the network. If we can prove that the coefficient matrixC1 of the flow conservation system is full rank in the row space, then the minimum number of counting points will be determined. The task of corresponding SLP will be reduced to optimize the sensors location only.According to the knowledge of linear algebra, if we can find a nonsingularm×m sub matrix in C1, then matrix C1 is proven to be full rank in the row space.Let us select the firstm columns from C1 to compose a square matrix C2:(7)C2=a11a12⋯a1j⋯a1ma21a22⋯a2j⋯a2m⋮⋱ai1ai2⋯aij⋯aim⋮⋱am1am2⋯amj⋯amm.The column vector of matrixC1 is denoted as aj, aj=a1j,a2j,…,amj′. C1 can be written as C1=a1,a2,…,a(n+g). C2 can be written as C2=a1,a2,…,am. The flow conservation system can be rewritten as follows:(8)∑j=1majxj=0-∑k=m+1n+gakxk.The variablesxj, j∈RDout, on the left side correspond to the traffic flows on outgoing roads. On the right side, xk, k∈RDein, correspond to the traffic flows on incoming roads; xk, k∈F, correspond to the net balancing flows.If we can prove that the traffic flows on the outgoing roads must be zero when the right side vector of (8) equals 0, then the column vectors are proven to be linear independent, which means C2 must be nonsingular.Proposition 7.
If the right side vector of (8) equals 0, then the traffic flows on all the exclusive outgoing roads must be zero.Proof.
According to the analysis above, we have(9)∑1≤i≤m,i≠jaij=1,j∈RDio∪RDein∪F∑1≤i≤m,i≠jaij=0,j∈RDeoutaij=-1,i=j.
Adding all the equations in system (8) together, we will easily get that the sum of the left side of (8) is minus total traffic flows in set RDeout and the sum of the right side of (8) is minus total traffic flows in set RDein∪F. Set the right side vector of (8) 0. So total traffic flows in set RDein∪F are zero. Then, total traffic flows in set RDeout are zero too, which determines that all the exclusive outgoing roads have no traffic on them.Actually, this is an obvious result under the assumption of traffic flow conservation. For a road network, all the traffic flows (including the net balancing flows here) entering the network must equal the traffic flows leaving the network.Proposition 8.
If the right side vector of (8) equals 0, then the traffic flows on all the incoming/outgoing roads must be zero too.Proof.
Proof by contradiction is used here to prove Proposition8.Suppose there are incoming/outgoing roads which have nonzero traffic flows on them. All these roads compose a road setA′. We have A′⊆RDio. According to Assumption 4 in Section 2, there must be at least one road j∈A′ which has a turning ratio aij>0, where road i∉A′. Since the traffic flow on road j is not zero, there must be aij×xj traffic flow turning from road j into road i. Then, the traffic flows on road i must not be zero. This can be proved as follows.For any roadi in set RDout, the incoming traffic flows at the intersection can be divided into two parts: traffic flows coming from the exclusive incoming roads or/and dummy roads which correspond to the right side of (8) and traffic flows coming from the incoming/outgoing roads. So for a road i in set RDout, if the right side of (8) is set to zero and there are traffic flows turning from the incoming/outgoing roads into it, the traffic flows on it must be nonzero.If roadi is still an incoming/outgoing road, set A′=A′∪i. Then, we can still find at least one outgoing road outside A′, whose traffic flow is not zero. Since RDout=RDio∪RDeout, there must be at least one exclusive outgoing road which has nonzero flow. This cannot happen according to Proposition 7. So if the right side vector of (8) equals 0, then the traffic flows on all the incoming/outgoing roads must be zero too.Now we have proven that if the right side vector of (8) equals 0, the traffic flows on the outgoing roads must be zero. So C2 is nonsingular, which means that the coefficient matrix C1 of the flow conservation system is full rank in the row space.


## 5. Sensor Location Optimization Model and Solution Algorithm

### 5.1. Full Flow-Observability SLP Based on Turning Ratios

#### 5.1.1. SLP Description

As we stated above, the objective of full flow-observability SLP is to determine the minimum number and locations of the sensors over the network so that all the traffic flows can be inferred.Based on turning ratios,m linear equations can be formulated to compose the flow conservation system as system (6). The number of variables in the system is n+g, which is larger than m. It is easy to know that at least other n+g-m equations are needed to derivate all the variables uniquely. By installing sensors on road, detecting equation can be formulated as xj=bj, where bj is the detected traffic flow. So at least n+g-m roads need to be detected. Denote the coefficient matrix for the n+g-m detecting equations as C3. Matrix C3 is a (n+g-m)×(n+g) matrix where only one entry equals one and the others equal zero in each row. For the undetected roads, the corresponding column vectors are zero vectors. Adding all the detecting equations, the complete system can be formulated as follows:(10)C1C3×X=0B,where B is the detected flows vector, composed of the detected traffic flows bj.System (10) will generate a unique solution if and only if the coefficient matrix is nonsingular. So the objective of full flow-observability SLP here is to find a detecting coefficient matrix C3 so that the coefficient matrix of system (10) is nonsingular.In Section4, matrix C1 is proven to have full row rank. So we can always find a matrix C3 with n+g-m to generate a nonsingular coefficient matrix for system (10), which means only n+g-m roads are required to be detected.


#### 5.1.2. SLP Modeling

Usingδj as the decision variable in the model to determine whether road j will be detected or not, δj=1 means road j will be detected; δj=0 means road j will not be detected. We design a matrix C as follows:(11)C=a11a12⋯a1j⋯a1m⋯a1n⋯a1n+ga21a22⋯a2j⋯a2m⋯a2n⋯a2n+g⋮⋱⋮ai1ai2⋯aij⋯aim⋯ain⋯ain+g⋮⋱⋮am1am2⋯amj⋯amm⋯amn⋯amn+gδ1δ2⋱δm⋱δn+g.Letδ=δ1,δ2,…,δj,…,δn+g′. The full flow-observability SLP based on turning ratios can be described as follows.Determineδ which satisfy(12)rank⁡C=n+g∑j=1n+gδj=n+g-m,where rank⁡(C) is the rank of matrix C.The solutions of model (12) must exist according to the analysis in Section 5.1.1.


#### 5.1.3. A Special Design: Closing Ring

Shao et al. [14, 15] introduced a special design of sensor location over the network called “closing ring,” which is given in Figure 3.Figure 3
Closing ring sensors location design.The “closing ring” is designed to install counting sensors on every exclusive incoming road of the network with the assumption that no net balancing flows exist. No proof was given in [14, 15] to guarantee a unique flow solution. By the analysis above, the assumption can be released by adding dummy roads into the network to represent the net balancing flows. So here the “closing ring” is designed to detect the flows on all exclusive incoming roads and dummy roads. This design can be easily proven to be a solution of model (12).InC1, the last n+g-m columns correspond to the exclusive incoming roads and dummy roads of the network. So the corresponding coefficient matrix for the detecting equations of closing ring design is C3=OI, where I is an (n+g-m)×(n+g-m) identity square matrix and O is (n+g-m)×m zero matrix. The whole coefficient matrix Cf of system (10) can be written as follows:(13)Cf=C2C′′OI,where C′′ is the submatrix composed of the last n+g-m columns of C1.Obviously, the determinant ofCf can be calculated as det⁡(Cf)=det⁡(C2)×det⁡(I)=det⁡(C2). Since C2 has been proven to be nonsingular, we have det⁡(Cf)≠0. So we have rank⁡(Cf)=n+g. Obviously, ∑j=1n+gδj=n+g-m is satisfied.We do not use any assumption of the network topology here. So, if possible, “closing ring” can always be a sensor location design for any road network, which can be given without any calculation.


#### 5.1.4. Feasibility for Detecting Only Real Roads

In the “closing ring” design, all exclusive incoming roads and dummy roads are supposed to be detected. But, in reality, it is not easy to detect the net balancing flows. If we can always findn+g-m real roads as a detection set in the above SLP, the solution will be more applicable in reality.RenewRDout by numbering the roads with nonzero net balancing flows after others. It is equivalent to permute rows and first m columns in matrix C1. After that, permute the last g columns in matrix C1 so that the coefficient matrix for dummy roads is expressed by C4=OIg, where Ig is an g×g identity square matrix and O is a m-g×g zero matrix. After all the permutations, the coefficient matrix C1p of the flow conservation system is as follows:(14)C1p=a11a12⋯a1m⋯a1na21a22⋯a2m⋯a2nO⋮⋮⋱⋮⋮am-g1am-g2⋯am-gm⋯am-gmam-g+11am-g+12⋯am-g+1m⋯am-g+1m⋮⋮⋱⋮⋮Igam1am2⋯amm⋯amn.Denote the firstm columns of C1p as C2p. Submatrix C2p is also the permutations result of matrix C2. Since C2 is nonsingular, C2p is nonsingular too. So the row vectors in C2p are linear independent. Consequently, the first m-g row vectors are linear independent. We can always find a m-g×m-g nonsingular subsquare matrix C5 in the first m-g rows of C2p. Represent the submatrix, which is composed of m-g columns in C2p with C5 as its first m-g rows, as C6=C5C7, where C7 is the submatrix composed of the last g rows of C6. Also, represent the submatrix composed of the other g columns of C2p as C8 and represent the submatrix composed of the columns from m+1th to nth in C1p as C9. By exchanging the columns in C8 and C4 and some columns permutations, C1p can be written as C1pp:(15)C1pp=C6C4C9C8.As a subsquare matrix ofC1pp, matrix C10=C6C4 is a m×m matrix. We have(16)C10=C5OC7Ig.SinceC5 is a nonsingular square matrix, Ig is an identity square matrix and matrix C10 is also nonsingular. According to the analysis in “closing ring” design, if we place the sensors on all the roads corresponding to the columns in C8 and C9, the traffic flow vector can be inferred uniquely. Because all the roads corresponding to the columns in C8 and C9 are real roads, we can always find n+g-m real roads as a detection set for the SLP based on turning ratios.


### 5.2. Weighted Full Flow-Observability SLP Model Based on Turning Ratios

#### 5.2.1. Model Formulation

Obviously, many combinations of roads in the network can be used as the solution detection sets for the full flow-observability SLP based on turning ratios. How to choose the detection set among all the feasible solutions depends on people’s evaluation on the importance of the roads and the cost of the sensors’ installation and maintenance. For example, an artery road is usually more important than a local street for the traffic management. So people maybe want to detect the traffic flow on it such that they can know its detailed traffic condition. Also lower cost of installation and maintenance could be preferred. A weight can be given to the road by integrating people’s evaluation on its importance and cost. A higher weight means that a road has higher importance and needs lower investment. For the whole network, a weight vector could be given asW=w1,w2,…,wj,…,wn+g, where wj is the weight of the road j. Here the dummy roads are included too. To get rid of dummy roads, we can simply set δj=0, j∈n+1,…,n+g. Discussion in Section 5.1.4 shows that we can always find the feasible solutions even though δj=0, j∈n+1,…,n+g.The objective of the weighted SLP here is to find the optimal detection set so that the total weight of all the roads in the detection set is maximal. The weighted SLP model can be formulated as follows:(17)max⁡W×δs.t.rank⁡C=n+g∑j=1n+gδj=n+g-mδj∈0,1.All the variables and parameters have been defined before.


#### 5.2.2. Solution Algorithm

Let us changeδj in C into 1; then we get C′:(18)C′=a11a12⋯a1j⋯a1m⋯a1n⋯a1n+ga21a22⋯a2j⋯a2m⋯a2n⋯a2n+g⋮⋱⋮ai1ai2⋯aij⋯aim⋯ain⋯ain+g⋮⋱⋮am1am2⋯amj⋯amm⋯amn⋯amn+g11⋱1⋱1.Denote theith row vector in C′ as rwi. The first m row vectors compose matrix C1, C1′=rw1′rw2′⋯rwm′. The last n+g row vectors compose identity matrix In+g, In+g′=rwm+1′rwm+2′⋯rwm+n+g′. Every row vector rwm+j in In+g is given a weight wj. If n+g-m row vectors of In+g and m row vectors in C1 can compose a maximal independence row vector group of C′, then these n+g-m row vectors are called feasible vector group.Solving model (17) is essential to find the optimal feasible vector group whose total weight is maximal among all the feasible vector groups.Greedy approach is used here to solve the SLP model (17). The algorithm is designed as follows.Step 1.
Set matrixS=C1.Step 2.
Sort row vectors inIn+g into monotonically decreasing order by the given weight w.Step 3.
For each row vectorrwm+j, j∈1,2,…,n+g in In+g, taken in monotonically decreasing order by weight ωj, consider the following.Calculate the rank ofS∪rwm+j to see if S∪rwm+j has full row rank. If S∪rwm+j has full row rank, then set S=S∪rwm+j. When the rank of S is equal to n+g, stop the calculation and return S.The nonzero entries in the lastn+g-m rows of S give the optimal solution of SLP model (17). The corresponding roads compose the optimal detection set.The greedy algorithm can provide the optimal solution to model (17). This can be proven as follows.Proposition 9.
Letrwm+k be the row vector with the maximum weight wk among all the row vectors rwm+j∈Ig which satisfy that C1∪rwm+j has full row rank. Then, rwm+k must belong to the optimal feasible vector group.Proof.
Denote the optimal feasible vector group asQ=rwm+q1,…,rwm+qj,…,rwm+qn+g-m, where qj∈1,2,…,n+g. Obviously, any row vector in Q will satisfy that C1∪rwm+qj has full rank. Assume that rwm+k∉Q. Since rwm+k has the maximal weight among all the row vectors rwm+j∈Ig which satisfy that C1∪rwm+j has full row rank, we have wk≥wqj.Because the vectors inQ can compose a maximal independence row vector group of C′ with row vectors in C1, the following equation must hold:(19)rwm+k=k1rw1+k2rw2+⋯+kmrwm+km+1rwm+q1+km+2rwm+q2+⋯+kn+grwm+qn+g-m,where at least one kj≠0. Since C1∪rwm+k has full rank, there must be one kj∈km+1,km+2,…,kn+g which has a nonzero value. Otherwise, if all kj∈km+1,km+2,…,kn+g is zero, then, from (19), rwm+k is the linear combination of rwj, j∈1,2,…,m, which is inconsistent with the fact that C1∪rwm+k has full rank.Supposekm+j1≠0, j1∈1,2,…,n+g-m; then, C1∪rwm+k can compose a maximal independence row vector group of C′ with all the vectors in Q except rwm+qj1. Otherwise, the following equation must hold:(20)rwm+k=k1′rw1+⋯+km′rwm+km+1′rwm+q1+⋯+km+j1-1′rwm+qj1-1+km+j1+1′rwm+qj1+1+⋯+kn+g′rwm+qn+g-m.From (19) and (20), we have(21)0=k1-k1′rw1+⋯+km-km′rwm+km+1-km+1′rwm+q1+⋯+km+j1-1-km+j1-1′rwm+qj1-1+km+j1+1-km+j1+1′rwm+qj1+1+⋯+kn+g-kn+g′rwm+qn+g-m+km+j1rwm+qj1.Sincekm+j1≠0, (21) is not consistent with the fact that Q∪C1 is a maximal independence row vector group of C′.SoC1∪rwm+k∪(Q-{rwm+qj1}) is a maximal independence row vector group of C′. Because wk≥wqj1, the total weights of rwm+k∪(Q-{rwm+qj1}) must be not smaller than the total weights of Q. If Q is the optimal feasible vector group, then rwm+k∪(Q-{rwm+qj1}) must be the optimal feasible vector group too.Sorwm+k must belong to the optimal feasible vector group.Proposition 10.
For anyS in the algorithm steps whose rank is smaller than n+g, suppose all the row vectors in S belong to the optimal feasible vector group. Let rwm+k∉S be the row vector with the maximum weight wk among all the row vectors rwm+j∈Ig-S which satisfy that S∪rwm+j has full row rank. rwm+k must belong to the optimal feasible vector group.Proposition10 can be easily proven if we look at S here as C1 in Proposition 9. All the proved procedure will be the same with Proposition 9.Proposition9 shows that the first row vector which is selected from Ig into S according to the proposed greedy algorithm must belong to the optimal feasible vector group. Proposition 10 shows that if all the row vectors, which have been selected from Ig into S, compose a subset of the optimal feasible vector group, then the next row vector, which will be selected from Ig into S according to the proposed greedy algorithm, must belong to the optimal feasible vector group too. So, by the method of mathematical induction, the proposed greedy algorithm is proven to be able to produce the optimal solution to model (17).


#### 5.2.3. Numerical Examples

In this part, a simple road network composed of one exclusive incoming road, two exclusive outgoing roads, and six incoming/outgoing roads is used to examine the greedy algorithm. Another bigger road network with different number of dummy roads is used to show the computation performance.The simple road network is given in Figure4.Figure 4
A simple road network for SLP model.
(a)
Original road network
(b)
Road network with dummy roadThere is nonzero net balancing flow generated on road 7. The net balancing flow can be transferred to a dummy road 10 as shown in Figure4(b) with 1 as the turning ratio from road 10 to road 7.The turning ratios for each road are given by Table1.Table 1
Turning ratios.
Link number
Downstream links: corresponding turning ratios
3
1: 0.7; 6: 0.3
4
2: 1.0
5
2: 1.0
6
2: 1.0
7
1: 0.4; 6: 0.6
8
5: 0.2; 7: 0.8
9
3: 0.5; 4: 0.2; 8: 0.3
10
7: 1.0The weight vector is given byW=w1,w2,…,w10=4.2,5.3,7.8,7.5,4.8,6.5,3,7.2,8.0,1.5.According to the descending order of weights, the checking order of the roads is9,3,4,8,6,2,5,1,7,10. By calculating the ranks of matrices, the final optimal detection set is 9,6, and the maximal weight is 14.5. Actually, after road 9 is determined to be detected, the flows on roads 3, 4, and 8 are also determined.A bigger network is given to show the computation performance of the algorithm. The network is shown in Figure5. This network is composed of 120 directed roads and 25 intersections.Figure 5
Network A: example road network for SLP model.Based on the road network in Figure5, three scenarios are generated:(a)
No net balancing flow exists in the network.(b)
There are 20 roads whose net balancing flows are nonzero.(c)
There are 40 roads whose net balancing flows are nonzero.We implemented the algorithm for 200 times under each scenario in C# programming language on a Thinkpad (X201s). Every time we generate the turning ratios and weights randomly. The average CPU time for three scenarios is shown in Table2.Table 2
CPU time for three scenarios of network A.
Scenarios
CPU time (seconds)
Average
Maximum
Minimum
(a) No dummy roads
10.546
12.125
7.313
(b) 20 dummy roads
16.093
17.594
14.391
(c) 40 dummy roads
21.121
22.734
19.781


## 5.1. Full Flow-Observability SLP Based on Turning Ratios

### 5.1.1. SLP Description

As we stated above, the objective of full flow-observability SLP is to determine the minimum number and locations of the sensors over the network so that all the traffic flows can be inferred.Based on turning ratios,m linear equations can be formulated to compose the flow conservation system as system (6). The number of variables in the system is n+g, which is larger than m. It is easy to know that at least other n+g-m equations are needed to derivate all the variables uniquely. By installing sensors on road, detecting equation can be formulated as xj=bj, where bj is the detected traffic flow. So at least n+g-m roads need to be detected. Denote the coefficient matrix for the n+g-m detecting equations as C3. Matrix C3 is a (n+g-m)×(n+g) matrix where only one entry equals one and the others equal zero in each row. For the undetected roads, the corresponding column vectors are zero vectors. Adding all the detecting equations, the complete system can be formulated as follows:(10)C1C3×X=0B,where B is the detected flows vector, composed of the detected traffic flows bj.System (10) will generate a unique solution if and only if the coefficient matrix is nonsingular. So the objective of full flow-observability SLP here is to find a detecting coefficient matrix C3 so that the coefficient matrix of system (10) is nonsingular.In Section4, matrix C1 is proven to have full row rank. So we can always find a matrix C3 with n+g-m to generate a nonsingular coefficient matrix for system (10), which means only n+g-m roads are required to be detected.


### 5.1.2. SLP Modeling

Usingδj as the decision variable in the model to determine whether road j will be detected or not, δj=1 means road j will be detected; δj=0 means road j will not be detected. We design a matrix C as follows:(11)C=a11a12⋯a1j⋯a1m⋯a1n⋯a1n+ga21a22⋯a2j⋯a2m⋯a2n⋯a2n+g⋮⋱⋮ai1ai2⋯aij⋯aim⋯ain⋯ain+g⋮⋱⋮am1am2⋯amj⋯amm⋯amn⋯amn+gδ1δ2⋱δm⋱δn+g.Letδ=δ1,δ2,…,δj,…,δn+g′. The full flow-observability SLP based on turning ratios can be described as follows.Determineδ which satisfy(12)rank⁡C=n+g∑j=1n+gδj=n+g-m,where rank⁡(C) is the rank of matrix C.The solutions of model (12) must exist according to the analysis in Section 5.1.1.


### 5.1.3. A Special Design: Closing Ring

Shao et al. [14, 15] introduced a special design of sensor location over the network called “closing ring,” which is given in Figure 3.Figure 3
Closing ring sensors location design.The “closing ring” is designed to install counting sensors on every exclusive incoming road of the network with the assumption that no net balancing flows exist. No proof was given in [14, 15] to guarantee a unique flow solution. By the analysis above, the assumption can be released by adding dummy roads into the network to represent the net balancing flows. So here the “closing ring” is designed to detect the flows on all exclusive incoming roads and dummy roads. This design can be easily proven to be a solution of model (12).InC1, the last n+g-m columns correspond to the exclusive incoming roads and dummy roads of the network. So the corresponding coefficient matrix for the detecting equations of closing ring design is C3=OI, where I is an (n+g-m)×(n+g-m) identity square matrix and O is (n+g-m)×m zero matrix. The whole coefficient matrix Cf of system (10) can be written as follows:(13)Cf=C2C′′OI,where C′′ is the submatrix composed of the last n+g-m columns of C1.Obviously, the determinant ofCf can be calculated as det⁡(Cf)=det⁡(C2)×det⁡(I)=det⁡(C2). Since C2 has been proven to be nonsingular, we have det⁡(Cf)≠0. So we have rank⁡(Cf)=n+g. Obviously, ∑j=1n+gδj=n+g-m is satisfied.We do not use any assumption of the network topology here. So, if possible, “closing ring” can always be a sensor location design for any road network, which can be given without any calculation.


### 5.1.4. Feasibility for Detecting Only Real Roads

In the “closing ring” design, all exclusive incoming roads and dummy roads are supposed to be detected. But, in reality, it is not easy to detect the net balancing flows. If we can always findn+g-m real roads as a detection set in the above SLP, the solution will be more applicable in reality.RenewRDout by numbering the roads with nonzero net balancing flows after others. It is equivalent to permute rows and first m columns in matrix C1. After that, permute the last g columns in matrix C1 so that the coefficient matrix for dummy roads is expressed by C4=OIg, where Ig is an g×g identity square matrix and O is a m-g×g zero matrix. After all the permutations, the coefficient matrix C1p of the flow conservation system is as follows:(14)C1p=a11a12⋯a1m⋯a1na21a22⋯a2m⋯a2nO⋮⋮⋱⋮⋮am-g1am-g2⋯am-gm⋯am-gmam-g+11am-g+12⋯am-g+1m⋯am-g+1m⋮⋮⋱⋮⋮Igam1am2⋯amm⋯amn.Denote the firstm columns of C1p as C2p. Submatrix C2p is also the permutations result of matrix C2. Since C2 is nonsingular, C2p is nonsingular too. So the row vectors in C2p are linear independent. Consequently, the first m-g row vectors are linear independent. We can always find a m-g×m-g nonsingular subsquare matrix C5 in the first m-g rows of C2p. Represent the submatrix, which is composed of m-g columns in C2p with C5 as its first m-g rows, as C6=C5C7, where C7 is the submatrix composed of the last g rows of C6. Also, represent the submatrix composed of the other g columns of C2p as C8 and represent the submatrix composed of the columns from m+1th to nth in C1p as C9. By exchanging the columns in C8 and C4 and some columns permutations, C1p can be written as C1pp:(15)C1pp=C6C4C9C8.As a subsquare matrix ofC1pp, matrix C10=C6C4 is a m×m matrix. We have(16)C10=C5OC7Ig.SinceC5 is a nonsingular square matrix, Ig is an identity square matrix and matrix C10 is also nonsingular. According to the analysis in “closing ring” design, if we place the sensors on all the roads corresponding to the columns in C8 and C9, the traffic flow vector can be inferred uniquely. Because all the roads corresponding to the columns in C8 and C9 are real roads, we can always find n+g-m real roads as a detection set for the SLP based on turning ratios.


## 5.1.1. SLP Description

As we stated above, the objective of full flow-observability SLP is to determine the minimum number and locations of the sensors over the network so that all the traffic flows can be inferred.Based on turning ratios,m linear equations can be formulated to compose the flow conservation system as system (6). The number of variables in the system is n+g, which is larger than m. It is easy to know that at least other n+g-m equations are needed to derivate all the variables uniquely. By installing sensors on road, detecting equation can be formulated as xj=bj, where bj is the detected traffic flow. So at least n+g-m roads need to be detected. Denote the coefficient matrix for the n+g-m detecting equations as C3. Matrix C3 is a (n+g-m)×(n+g) matrix where only one entry equals one and the others equal zero in each row. For the undetected roads, the corresponding column vectors are zero vectors. Adding all the detecting equations, the complete system can be formulated as follows:(10)C1C3×X=0B,where B is the detected flows vector, composed of the detected traffic flows bj.System (10) will generate a unique solution if and only if the coefficient matrix is nonsingular. So the objective of full flow-observability SLP here is to find a detecting coefficient matrix C3 so that the coefficient matrix of system (10) is nonsingular.In Section4, matrix C1 is proven to have full row rank. So we can always find a matrix C3 with n+g-m to generate a nonsingular coefficient matrix for system (10), which means only n+g-m roads are required to be detected.


## 5.1.2. SLP Modeling

Usingδj as the decision variable in the model to determine whether road j will be detected or not, δj=1 means road j will be detected; δj=0 means road j will not be detected. We design a matrix C as follows:(11)C=a11a12⋯a1j⋯a1m⋯a1n⋯a1n+ga21a22⋯a2j⋯a2m⋯a2n⋯a2n+g⋮⋱⋮ai1ai2⋯aij⋯aim⋯ain⋯ain+g⋮⋱⋮am1am2⋯amj⋯amm⋯amn⋯amn+gδ1δ2⋱δm⋱δn+g.Letδ=δ1,δ2,…,δj,…,δn+g′. The full flow-observability SLP based on turning ratios can be described as follows.Determineδ which satisfy(12)rank⁡C=n+g∑j=1n+gδj=n+g-m,where rank⁡(C) is the rank of matrix C.The solutions of model (12) must exist according to the analysis in Section 5.1.1.


## 5.1.3. A Special Design: Closing Ring

Shao et al. [14, 15] introduced a special design of sensor location over the network called “closing ring,” which is given in Figure 3.Figure 3
Closing ring sensors location design.The “closing ring” is designed to install counting sensors on every exclusive incoming road of the network with the assumption that no net balancing flows exist. No proof was given in [14, 15] to guarantee a unique flow solution. By the analysis above, the assumption can be released by adding dummy roads into the network to represent the net balancing flows. So here the “closing ring” is designed to detect the flows on all exclusive incoming roads and dummy roads. This design can be easily proven to be a solution of model (12).InC1, the last n+g-m columns correspond to the exclusive incoming roads and dummy roads of the network. So the corresponding coefficient matrix for the detecting equations of closing ring design is C3=OI, where I is an (n+g-m)×(n+g-m) identity square matrix and O is (n+g-m)×m zero matrix. The whole coefficient matrix Cf of system (10) can be written as follows:(13)Cf=C2C′′OI,where C′′ is the submatrix composed of the last n+g-m columns of C1.Obviously, the determinant ofCf can be calculated as det⁡(Cf)=det⁡(C2)×det⁡(I)=det⁡(C2). Since C2 has been proven to be nonsingular, we have det⁡(Cf)≠0. So we have rank⁡(Cf)=n+g. Obviously, ∑j=1n+gδj=n+g-m is satisfied.We do not use any assumption of the network topology here. So, if possible, “closing ring” can always be a sensor location design for any road network, which can be given without any calculation.


## 5.1.4. Feasibility for Detecting Only Real Roads

In the “closing ring” design, all exclusive incoming roads and dummy roads are supposed to be detected. But, in reality, it is not easy to detect the net balancing flows. If we can always findn+g-m real roads as a detection set in the above SLP, the solution will be more applicable in reality.RenewRDout by numbering the roads with nonzero net balancing flows after others. It is equivalent to permute rows and first m columns in matrix C1. After that, permute the last g columns in matrix C1 so that the coefficient matrix for dummy roads is expressed by C4=OIg, where Ig is an g×g identity square matrix and O is a m-g×g zero matrix. After all the permutations, the coefficient matrix C1p of the flow conservation system is as follows:(14)C1p=a11a12⋯a1m⋯a1na21a22⋯a2m⋯a2nO⋮⋮⋱⋮⋮am-g1am-g2⋯am-gm⋯am-gmam-g+11am-g+12⋯am-g+1m⋯am-g+1m⋮⋮⋱⋮⋮Igam1am2⋯amm⋯amn.Denote the firstm columns of C1p as C2p. Submatrix C2p is also the permutations result of matrix C2. Since C2 is nonsingular, C2p is nonsingular too. So the row vectors in C2p are linear independent. Consequently, the first m-g row vectors are linear independent. We can always find a m-g×m-g nonsingular subsquare matrix C5 in the first m-g rows of C2p. Represent the submatrix, which is composed of m-g columns in C2p with C5 as its first m-g rows, as C6=C5C7, where C7 is the submatrix composed of the last g rows of C6. Also, represent the submatrix composed of the other g columns of C2p as C8 and represent the submatrix composed of the columns from m+1th to nth in C1p as C9. By exchanging the columns in C8 and C4 and some columns permutations, C1p can be written as C1pp:(15)C1pp=C6C4C9C8.As a subsquare matrix ofC1pp, matrix C10=C6C4 is a m×m matrix. We have(16)C10=C5OC7Ig.SinceC5 is a nonsingular square matrix, Ig is an identity square matrix and matrix C10 is also nonsingular. According to the analysis in “closing ring” design, if we place the sensors on all the roads corresponding to the columns in C8 and C9, the traffic flow vector can be inferred uniquely. Because all the roads corresponding to the columns in C8 and C9 are real roads, we can always find n+g-m real roads as a detection set for the SLP based on turning ratios.


## 5.2. Weighted Full Flow-Observability SLP Model Based on Turning Ratios

### 5.2.1. Model Formulation

Obviously, many combinations of roads in the network can be used as the solution detection sets for the full flow-observability SLP based on turning ratios. How to choose the detection set among all the feasible solutions depends on people’s evaluation on the importance of the roads and the cost of the sensors’ installation and maintenance. For example, an artery road is usually more important than a local street for the traffic management. So people maybe want to detect the traffic flow on it such that they can know its detailed traffic condition. Also lower cost of installation and maintenance could be preferred. A weight can be given to the road by integrating people’s evaluation on its importance and cost. A higher weight means that a road has higher importance and needs lower investment. For the whole network, a weight vector could be given asW=w1,w2,…,wj,…,wn+g, where wj is the weight of the road j. Here the dummy roads are included too. To get rid of dummy roads, we can simply set δj=0, j∈n+1,…,n+g. Discussion in Section 5.1.4 shows that we can always find the feasible solutions even though δj=0, j∈n+1,…,n+g.The objective of the weighted SLP here is to find the optimal detection set so that the total weight of all the roads in the detection set is maximal. The weighted SLP model can be formulated as follows:(17)max⁡W×δs.t.rank⁡C=n+g∑j=1n+gδj=n+g-mδj∈0,1.All the variables and parameters have been defined before.


### 5.2.2. Solution Algorithm

Let us changeδj in C into 1; then we get C′:(18)C′=a11a12⋯a1j⋯a1m⋯a1n⋯a1n+ga21a22⋯a2j⋯a2m⋯a2n⋯a2n+g⋮⋱⋮ai1ai2⋯aij⋯aim⋯ain⋯ain+g⋮⋱⋮am1am2⋯amj⋯amm⋯amn⋯amn+g11⋱1⋱1.Denote theith row vector in C′ as rwi. The first m row vectors compose matrix C1, C1′=rw1′rw2′⋯rwm′. The last n+g row vectors compose identity matrix In+g, In+g′=rwm+1′rwm+2′⋯rwm+n+g′. Every row vector rwm+j in In+g is given a weight wj. If n+g-m row vectors of In+g and m row vectors in C1 can compose a maximal independence row vector group of C′, then these n+g-m row vectors are called feasible vector group.Solving model (17) is essential to find the optimal feasible vector group whose total weight is maximal among all the feasible vector groups.Greedy approach is used here to solve the SLP model (17). The algorithm is designed as follows.Step 1.
Set matrixS=C1.Step 2.
Sort row vectors inIn+g into monotonically decreasing order by the given weight w.Step 3.
For each row vectorrwm+j, j∈1,2,…,n+g in In+g, taken in monotonically decreasing order by weight ωj, consider the following.Calculate the rank ofS∪rwm+j to see if S∪rwm+j has full row rank. If S∪rwm+j has full row rank, then set S=S∪rwm+j. When the rank of S is equal to n+g, stop the calculation and return S.The nonzero entries in the lastn+g-m rows of S give the optimal solution of SLP model (17). The corresponding roads compose the optimal detection set.The greedy algorithm can provide the optimal solution to model (17). This can be proven as follows.Proposition 9.
Letrwm+k be the row vector with the maximum weight wk among all the row vectors rwm+j∈Ig which satisfy that C1∪rwm+j has full row rank. Then, rwm+k must belong to the optimal feasible vector group.Proof.
Denote the optimal feasible vector group asQ=rwm+q1,…,rwm+qj,…,rwm+qn+g-m, where qj∈1,2,…,n+g. Obviously, any row vector in Q will satisfy that C1∪rwm+qj has full rank. Assume that rwm+k∉Q. Since rwm+k has the maximal weight among all the row vectors rwm+j∈Ig which satisfy that C1∪rwm+j has full row rank, we have wk≥wqj.Because the vectors inQ can compose a maximal independence row vector group of C′ with row vectors in C1, the following equation must hold:(19)rwm+k=k1rw1+k2rw2+⋯+kmrwm+km+1rwm+q1+km+2rwm+q2+⋯+kn+grwm+qn+g-m,where at least one kj≠0. Since C1∪rwm+k has full rank, there must be one kj∈km+1,km+2,…,kn+g which has a nonzero value. Otherwise, if all kj∈km+1,km+2,…,kn+g is zero, then, from (19), rwm+k is the linear combination of rwj, j∈1,2,…,m, which is inconsistent with the fact that C1∪rwm+k has full rank.Supposekm+j1≠0, j1∈1,2,…,n+g-m; then, C1∪rwm+k can compose a maximal independence row vector group of C′ with all the vectors in Q except rwm+qj1. Otherwise, the following equation must hold:(20)rwm+k=k1′rw1+⋯+km′rwm+km+1′rwm+q1+⋯+km+j1-1′rwm+qj1-1+km+j1+1′rwm+qj1+1+⋯+kn+g′rwm+qn+g-m.From (19) and (20), we have(21)0=k1-k1′rw1+⋯+km-km′rwm+km+1-km+1′rwm+q1+⋯+km+j1-1-km+j1-1′rwm+qj1-1+km+j1+1-km+j1+1′rwm+qj1+1+⋯+kn+g-kn+g′rwm+qn+g-m+km+j1rwm+qj1.Sincekm+j1≠0, (21) is not consistent with the fact that Q∪C1 is a maximal independence row vector group of C′.SoC1∪rwm+k∪(Q-{rwm+qj1}) is a maximal independence row vector group of C′. Because wk≥wqj1, the total weights of rwm+k∪(Q-{rwm+qj1}) must be not smaller than the total weights of Q. If Q is the optimal feasible vector group, then rwm+k∪(Q-{rwm+qj1}) must be the optimal feasible vector group too.Sorwm+k must belong to the optimal feasible vector group.Proposition 10.
For anyS in the algorithm steps whose rank is smaller than n+g, suppose all the row vectors in S belong to the optimal feasible vector group. Let rwm+k∉S be the row vector with the maximum weight wk among all the row vectors rwm+j∈Ig-S which satisfy that S∪rwm+j has full row rank. rwm+k must belong to the optimal feasible vector group.Proposition10 can be easily proven if we look at S here as C1 in Proposition 9. All the proved procedure will be the same with Proposition 9.Proposition9 shows that the first row vector which is selected from Ig into S according to the proposed greedy algorithm must belong to the optimal feasible vector group. Proposition 10 shows that if all the row vectors, which have been selected from Ig into S, compose a subset of the optimal feasible vector group, then the next row vector, which will be selected from Ig into S according to the proposed greedy algorithm, must belong to the optimal feasible vector group too. So, by the method of mathematical induction, the proposed greedy algorithm is proven to be able to produce the optimal solution to model (17).


### 5.2.3. Numerical Examples

In this part, a simple road network composed of one exclusive incoming road, two exclusive outgoing roads, and six incoming/outgoing roads is used to examine the greedy algorithm. Another bigger road network with different number of dummy roads is used to show the computation performance.The simple road network is given in Figure4.Figure 4
A simple road network for SLP model.
(a)
Original road network
(b)
Road network with dummy roadThere is nonzero net balancing flow generated on road 7. The net balancing flow can be transferred to a dummy road 10 as shown in Figure4(b) with 1 as the turning ratio from road 10 to road 7.The turning ratios for each road are given by Table1.Table 1
Turning ratios.
Link number
Downstream links: corresponding turning ratios
3
1: 0.7; 6: 0.3
4
2: 1.0
5
2: 1.0
6
2: 1.0
7
1: 0.4; 6: 0.6
8
5: 0.2; 7: 0.8
9
3: 0.5; 4: 0.2; 8: 0.3
10
7: 1.0The weight vector is given byW=w1,w2,…,w10=4.2,5.3,7.8,7.5,4.8,6.5,3,7.2,8.0,1.5.According to the descending order of weights, the checking order of the roads is9,3,4,8,6,2,5,1,7,10. By calculating the ranks of matrices, the final optimal detection set is 9,6, and the maximal weight is 14.5. Actually, after road 9 is determined to be detected, the flows on roads 3, 4, and 8 are also determined.A bigger network is given to show the computation performance of the algorithm. The network is shown in Figure5. This network is composed of 120 directed roads and 25 intersections.Figure 5
Network A: example road network for SLP model.Based on the road network in Figure5, three scenarios are generated:(a)
No net balancing flow exists in the network.(b)
There are 20 roads whose net balancing flows are nonzero.(c)
There are 40 roads whose net balancing flows are nonzero.We implemented the algorithm for 200 times under each scenario in C# programming language on a Thinkpad (X201s). Every time we generate the turning ratios and weights randomly. The average CPU time for three scenarios is shown in Table2.Table 2
CPU time for three scenarios of network A.
Scenarios
CPU time (seconds)
Average
Maximum
Minimum
(a) No dummy roads
10.546
12.125
7.313
(b) 20 dummy roads
16.093
17.594
14.391
(c) 40 dummy roads
21.121
22.734
19.781


## 5.2.1. Model Formulation

Obviously, many combinations of roads in the network can be used as the solution detection sets for the full flow-observability SLP based on turning ratios. How to choose the detection set among all the feasible solutions depends on people’s evaluation on the importance of the roads and the cost of the sensors’ installation and maintenance. For example, an artery road is usually more important than a local street for the traffic management. So people maybe want to detect the traffic flow on it such that they can know its detailed traffic condition. Also lower cost of installation and maintenance could be preferred. A weight can be given to the road by integrating people’s evaluation on its importance and cost. A higher weight means that a road has higher importance and needs lower investment. For the whole network, a weight vector could be given asW=w1,w2,…,wj,…,wn+g, where wj is the weight of the road j. Here the dummy roads are included too. To get rid of dummy roads, we can simply set δj=0, j∈n+1,…,n+g. Discussion in Section 5.1.4 shows that we can always find the feasible solutions even though δj=0, j∈n+1,…,n+g.The objective of the weighted SLP here is to find the optimal detection set so that the total weight of all the roads in the detection set is maximal. The weighted SLP model can be formulated as follows:(17)max⁡W×δs.t.rank⁡C=n+g∑j=1n+gδj=n+g-mδj∈0,1.All the variables and parameters have been defined before.


## 5.2.2. Solution Algorithm

Let us changeδj in C into 1; then we get C′:(18)C′=a11a12⋯a1j⋯a1m⋯a1n⋯a1n+ga21a22⋯a2j⋯a2m⋯a2n⋯a2n+g⋮⋱⋮ai1ai2⋯aij⋯aim⋯ain⋯ain+g⋮⋱⋮am1am2⋯amj⋯amm⋯amn⋯amn+g11⋱1⋱1.Denote theith row vector in C′ as rwi. The first m row vectors compose matrix C1, C1′=rw1′rw2′⋯rwm′. The last n+g row vectors compose identity matrix In+g, In+g′=rwm+1′rwm+2′⋯rwm+n+g′. Every row vector rwm+j in In+g is given a weight wj. If n+g-m row vectors of In+g and m row vectors in C1 can compose a maximal independence row vector group of C′, then these n+g-m row vectors are called feasible vector group.Solving model (17) is essential to find the optimal feasible vector group whose total weight is maximal among all the feasible vector groups.Greedy approach is used here to solve the SLP model (17). The algorithm is designed as follows.Step 1.
Set matrixS=C1.Step 2.
Sort row vectors inIn+g into monotonically decreasing order by the given weight w.Step 3.
For each row vectorrwm+j, j∈1,2,…,n+g in In+g, taken in monotonically decreasing order by weight ωj, consider the following.Calculate the rank ofS∪rwm+j to see if S∪rwm+j has full row rank. If S∪rwm+j has full row rank, then set S=S∪rwm+j. When the rank of S is equal to n+g, stop the calculation and return S.The nonzero entries in the lastn+g-m rows of S give the optimal solution of SLP model (17). The corresponding roads compose the optimal detection set.The greedy algorithm can provide the optimal solution to model (17). This can be proven as follows.Proposition 9.
Letrwm+k be the row vector with the maximum weight wk among all the row vectors rwm+j∈Ig which satisfy that C1∪rwm+j has full row rank. Then, rwm+k must belong to the optimal feasible vector group.Proof.
Denote the optimal feasible vector group asQ=rwm+q1,…,rwm+qj,…,rwm+qn+g-m, where qj∈1,2,…,n+g. Obviously, any row vector in Q will satisfy that C1∪rwm+qj has full rank. Assume that rwm+k∉Q. Since rwm+k has the maximal weight among all the row vectors rwm+j∈Ig which satisfy that C1∪rwm+j has full row rank, we have wk≥wqj.Because the vectors inQ can compose a maximal independence row vector group of C′ with row vectors in C1, the following equation must hold:(19)rwm+k=k1rw1+k2rw2+⋯+kmrwm+km+1rwm+q1+km+2rwm+q2+⋯+kn+grwm+qn+g-m,where at least one kj≠0. Since C1∪rwm+k has full rank, there must be one kj∈km+1,km+2,…,kn+g which has a nonzero value. Otherwise, if all kj∈km+1,km+2,…,kn+g is zero, then, from (19), rwm+k is the linear combination of rwj, j∈1,2,…,m, which is inconsistent with the fact that C1∪rwm+k has full rank.Supposekm+j1≠0, j1∈1,2,…,n+g-m; then, C1∪rwm+k can compose a maximal independence row vector group of C′ with all the vectors in Q except rwm+qj1. Otherwise, the following equation must hold:(20)rwm+k=k1′rw1+⋯+km′rwm+km+1′rwm+q1+⋯+km+j1-1′rwm+qj1-1+km+j1+1′rwm+qj1+1+⋯+kn+g′rwm+qn+g-m.From (19) and (20), we have(21)0=k1-k1′rw1+⋯+km-km′rwm+km+1-km+1′rwm+q1+⋯+km+j1-1-km+j1-1′rwm+qj1-1+km+j1+1-km+j1+1′rwm+qj1+1+⋯+kn+g-kn+g′rwm+qn+g-m+km+j1rwm+qj1.Sincekm+j1≠0, (21) is not consistent with the fact that Q∪C1 is a maximal independence row vector group of C′.SoC1∪rwm+k∪(Q-{rwm+qj1}) is a maximal independence row vector group of C′. Because wk≥wqj1, the total weights of rwm+k∪(Q-{rwm+qj1}) must be not smaller than the total weights of Q. If Q is the optimal feasible vector group, then rwm+k∪(Q-{rwm+qj1}) must be the optimal feasible vector group too.Sorwm+k must belong to the optimal feasible vector group.Proposition 10.
For anyS in the algorithm steps whose rank is smaller than n+g, suppose all the row vectors in S belong to the optimal feasible vector group. Let rwm+k∉S be the row vector with the maximum weight wk among all the row vectors rwm+j∈Ig-S which satisfy that S∪rwm+j has full row rank. rwm+k must belong to the optimal feasible vector group.Proposition10 can be easily proven if we look at S here as C1 in Proposition 9. All the proved procedure will be the same with Proposition 9.Proposition9 shows that the first row vector which is selected from Ig into S according to the proposed greedy algorithm must belong to the optimal feasible vector group. Proposition 10 shows that if all the row vectors, which have been selected from Ig into S, compose a subset of the optimal feasible vector group, then the next row vector, which will be selected from Ig into S according to the proposed greedy algorithm, must belong to the optimal feasible vector group too. So, by the method of mathematical induction, the proposed greedy algorithm is proven to be able to produce the optimal solution to model (17).


## 5.2.3. Numerical Examples

In this part, a simple road network composed of one exclusive incoming road, two exclusive outgoing roads, and six incoming/outgoing roads is used to examine the greedy algorithm. Another bigger road network with different number of dummy roads is used to show the computation performance.The simple road network is given in Figure4.Figure 4
A simple road network for SLP model.
(a)
Original road network
(b)
Road network with dummy roadThere is nonzero net balancing flow generated on road 7. The net balancing flow can be transferred to a dummy road 10 as shown in Figure4(b) with 1 as the turning ratio from road 10 to road 7.The turning ratios for each road are given by Table1.Table 1
Turning ratios.
Link number
Downstream links: corresponding turning ratios
3
1: 0.7; 6: 0.3
4
2: 1.0
5
2: 1.0
6
2: 1.0
7
1: 0.4; 6: 0.6
8
5: 0.2; 7: 0.8
9
3: 0.5; 4: 0.2; 8: 0.3
10
7: 1.0The weight vector is given byW=w1,w2,…,w10=4.2,5.3,7.8,7.5,4.8,6.5,3,7.2,8.0,1.5.According to the descending order of weights, the checking order of the roads is9,3,4,8,6,2,5,1,7,10. By calculating the ranks of matrices, the final optimal detection set is 9,6, and the maximal weight is 14.5. Actually, after road 9 is determined to be detected, the flows on roads 3, 4, and 8 are also determined.A bigger network is given to show the computation performance of the algorithm. The network is shown in Figure5. This network is composed of 120 directed roads and 25 intersections.Figure 5
Network A: example road network for SLP model.Based on the road network in Figure5, three scenarios are generated:(a)
No net balancing flow exists in the network.(b)
There are 20 roads whose net balancing flows are nonzero.(c)
There are 40 roads whose net balancing flows are nonzero.We implemented the algorithm for 200 times under each scenario in C# programming language on a Thinkpad (X201s). Every time we generate the turning ratios and weights randomly. The average CPU time for three scenarios is shown in Table2.Table 2
CPU time for three scenarios of network A.
Scenarios
CPU time (seconds)
Average
Maximum
Minimum
(a) No dummy roads
10.546
12.125
7.313
(b) 20 dummy roads
16.093
17.594
14.391
(c) 40 dummy roads
21.121
22.734
19.781


## 6. Conclusions

The network sensor location problem based on the turning ratios discussed in this paper essentially uses the topology-driven logic to infer the traffic flow over the network. So no assumptions about the route choice are needed. The findings of this paper can be summarized as follows.First of all, the coefficient matrix of the flow conservation system based on turning ratios is proven to be nonsingular. So the minimal number of the roads required to infer all the traffic flows is determined to be the total number of exclusive incoming roads and the outgoing roads with nonzero net balancing flows.Second of all, a special sensors location design called “closing ring” is improved in this paper. The analysis shows that if we can detect the traffic flows on all the exclusive incoming roads and all the net balancing flows in the network, then the whole traffic flow vector can be inferred no matter what topology structure the network has. The analysis also shows that we can always find a feasible solution including only real roads for the proposed SLP model, which is useful because the net balancing flow is usually difficult to be detected.And finally, a weighted SLP model to find the optimal detecting set considering the roads importance and cost of sensors is formulated. Greedy algorithm is designed to solve the model, which is proven to be able to provide the optimal solution. Two numerical examples are given to test the algorithm. The computation performance is reported.



---

*Source: 9012724-2016-02-25.xml*