Locating active sensors on traffic networks.

*(English)*Zbl 1114.90067Summary: Sensors are used to monitor traffic in networks. For example, in transportation networks, they may be used to measure traffic volumes on given arcs and paths of the network. This paper refers to an active sensor when it reads identifications of vehicles, including their routes in the network, that the vehicles actively provide when they use the network. On the other hand, the conventional inductance loop detectors are passive sensors that mostly count vehicles at points in a network to obtain traffic volumes (e.g., vehicles per hour) on a lane or road of the network.

This paper introduces a new set of network location problems that determine where to locate active sensors in order to monitor or manage particular classes of identified traffic streams. In particular, it focuses on the development of two generic locational decision models for active sensors, which seek to answer these questions: (1) ”How many and where should such sensors be located to obtain sufficient information on flow volumes on specified paths?”, and (2) ”Given that the traffic management planners have already located count detectors on some network arcs, how many and where should active sensors be located to get the maximum information on flow volumes on specified paths?”

The problem is formulated and analyzed for three different scenarios depending on whether there are already count detectors on arcs and if so, whether all the arcs or a fraction of them have them. Location of an active sensor results in a set of linear equations in path flow variables, whose solution provide the path flows. The general problem, which is related to the set-covering problem, is shown to be NP-Hard, but special cases are devised, where an arc may carry only two routes, that are shown to be polynomially solvable. New graph theoretic models and theorems are obtained for the latter cases, including the introduction of the generalized edge-covering by nodes problem on the path intersection graph for these special cases. An exact algorithm for the special cases and an approximate one for the general case are presented.

This paper introduces a new set of network location problems that determine where to locate active sensors in order to monitor or manage particular classes of identified traffic streams. In particular, it focuses on the development of two generic locational decision models for active sensors, which seek to answer these questions: (1) ”How many and where should such sensors be located to obtain sufficient information on flow volumes on specified paths?”, and (2) ”Given that the traffic management planners have already located count detectors on some network arcs, how many and where should active sensors be located to get the maximum information on flow volumes on specified paths?”

The problem is formulated and analyzed for three different scenarios depending on whether there are already count detectors on arcs and if so, whether all the arcs or a fraction of them have them. Location of an active sensor results in a set of linear equations in path flow variables, whose solution provide the path flows. The general problem, which is related to the set-covering problem, is shown to be NP-Hard, but special cases are devised, where an arc may carry only two routes, that are shown to be polynomially solvable. New graph theoretic models and theorems are obtained for the latter cases, including the introduction of the generalized edge-covering by nodes problem on the path intersection graph for these special cases. An exact algorithm for the special cases and an approximate one for the general case are presented.

##### Keywords:

location theory; sensors; traffic networks; network covering problems; linearly independent equations
PDF
BibTeX
XML
Cite

\textit{M. Gentili} and \textit{P. B. Mirchandani}, Ann. Oper. Res. 136, 229--257 (2005; Zbl 1114.90067)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Bianco, L., G. Confessore, and P. Reverberi. (2001). ”A Network Based Model for Traffic Sensor Location with Implications on O/D Matrix Estimates.” Transportation Science 35(1), 50–60. · Zbl 1069.90503 |

[2] | Bianco, L., G. Confessore, M. Gentili. (2003). ”Combinatorial Aspects of the Sensor Location Problem.” Annals of Operations Research (to appear). · Zbl 1162.90492 |

[3] | Cascetta, E. and S. Nguyen. (1988). ”A Unified Framework for Estimating or Updating Origin/Destination Trip Matrices from Traffic Counts.” Transportation Research B 22, 437–455. |

[4] | Conforti, M. and M.R. Rao. (1987). ”Some New Matroids on Graphs: Cut Sets and the Max Cut problem.” Mathematics of Operations Research 12(2), 193–204. · Zbl 0631.90080 |

[5] | Feremans, C. (2001). ”Generalized Spanning Trees and Extensions.” PhD Thesis, Université Libre de Bruxelles, Institut de Statistique et de Recherche Opérationelle. · Zbl 0990.90120 |

[6] | Gentili, M. (2002). ”New Models and Algorithms for the Location of Sensors on Traffic Networks.” PhD Thesis. Department of Statistic, Probability and Applied Statistics, University of Rome ”La Sapienza”. |

[7] | Lam, W.H.K. and H.P. Lo.(1990). ”Accuracy of O-D Estimates from Traffic Counts.” Traffic Engineering and Control 31, 358–367. |

[8] | Nemhauser, G.L. and L.A. Wolsey. (1988). Integer and Combinatorial Optimization. New York, N.Y: J. Wiley and Sons. · Zbl 0652.90067 |

[9] | Wardrop, J.G. (1952). ”Some Theoretical Aspects of Road Traffic Research.” In Proceedings of the Institute of Civil Engineering, Part II, pp. 325–378. |

[10] | Yang, H., Y. Iida, and T. Sasaki. (1991). ”An Analysis of the Reliability of an Origin/Destination Trip Matrix Estimated from Traffic Counts.” Transportation Research B 25, 351–363. |

[11] | Yang, H. and J. Zhou. (1998). ”Optimal Traffic Counting Locations for Origin-Destination Matrix Estimation.” Transportation Research 32B(2), 109–126. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.