Optimization of Scanning and Counting Sensor Layout for Full Route Observability with a Bi-Level Programming Model

Donghui Shan, Xiaoduan Sun, Jianbei Liu, Ming Sun2018 · DOI

TL;DR

This paper tackles the challenge of optimally placing traffic sensors to fully understand traffic flow on road networks. It introduces a novel bi-level programming model that combines scanning (e.g., video) and counting (e.g., loop detectors) sensors to achieve complete route observability at a reduced cost compared to using only one type of sensor.

What Problem Does This Paper Address?

Efficiently managing traffic flow relies heavily on accurate data from sensors deployed on roadways. The "network sensor location problem" (NSLP) aims to determine the optimal number, type, and placement of these sensors. While previous research often focused on optimizing the placement of a single sensor type (either counting or scanning), this paper addresses the more complex problem of combining different sensor types. Specifically, it tackles how to strategically deploy a mix of scanning sensors (which provide detailed path data) and counting sensors (which provide point data) to ensure "full route observability" – meaning all traffic flows on all routes can be uniquely determined. This is crucial because a complete understanding of traffic flow is essential for effective traffic management, but deploying a large number of expensive scanning sensors across an entire network is often cost-prohibitive.

Methods

The paper proposes a novel bi-level programming model to solve the combined sensor deployment problem. This model operates in two distinct levels:

  • First Level (Scanning Sensor Optimization): This level focuses on determining the optimal placement of scanning sensors. It uses a "scanning map" concept and a mathematical program to find a near-optimal set of scanning sensors that can uniquely identify all route flows. A key innovation here is the introduction of a "differentiating matrix" and a "differentiating first" greedy algorithm. This algorithm prioritizes selecting links that provide the most unique route differentiation, aiming to maximize the information gained from each scanning sensor.
  • Second Level (Combined Deployment and Cost Minimization): This level takes the scanning sensor layout from the first level and explores how to replace some scanning sensors with less expensive counting sensors without losing full route observability. It uses matrix tools and enumerates various replacement schemes to find the combination that minimizes the total sensor cost. This involves ensuring that the combined set of scanning and counting sensors still provides a full-rank system of equations for route flow determination.

Datasets

The paper evaluates its proposed approach using two types of networks:

  • Nguyen-Dupuis Network: A well-known benchmark network used in many traffic studies, consisting of 13 nodes and 38 links.
  • Real-World Network (Xi'an, China): A larger and more complex network with 49 nodes and 150 links, representing a more realistic scenario for traffic management.

The paper does not introduce new datasets but uses these existing network topologies to demonstrate the effectiveness of its algorithms.

Key Insights and Ideas

  • Scanning sensors offer more information: The paper highlights that scanning sensors can provide more independent linear equations than counting sensors for the same number and location, leading to better route differentiation.
  • Counting sensors can substitute scanning sensors: In certain scenarios, counting sensors can effectively replace scanning sensors without sacrificing full route observability, offering a cost-saving opportunity.
  • "Differentiating first" is crucial: Prioritizing links that offer the most unique route differentiation when placing scanning sensors is a key strategy for maximizing information gain and minimizing the number of required sensors.
  • Bi-level optimization is effective: The two-level approach allows for a systematic way to first identify a robust scanning sensor layout and then optimize for cost by incorporating counting sensors.
  • Combined deployment is more cost-effective: The study strongly suggests that combining scanning and counting sensors leads to significantly lower overall deployment costs compared to relying solely on scanning sensors, especially for larger networks.

Key Results

  • The proposed bi-level model and algorithms were applied to both the Nguyen-Dupuis and a real-world traffic network.
  • For the Nguyen-Dupuis network, the first level algorithm identified a near-optimal set of 22 scanning sensors for full observability. The second level then demonstrated various combination schemes, showing that a significant number of scanning sensors could be replaced by counting sensors.
  • In the larger real-world network, the first level identified 79 scanning sensors. The second level analysis showed that the total cost of sensor deployment could be reduced by up to 75% by combining scanning and counting sensors, compared to using only scanning sensors. For instance, a scheme with 56 scanning and 21 counting sensors was found to be highly economical.

Limitations and Future Work

  • Computational Complexity: The authors acknowledge that the first-level model is computationally NP-hard, and while their greedy algorithm provides a near-optimal solution, improving the efficiency of the algorithm for very large networks is a key area for future research.
  • Focus on Flow Information: The current model primarily focuses on traffic flow information. Future work should extend this to include travel time and network reliability.
  • Dynamic Traffic Networks: The study does not explicitly address dynamic traffic networks where traffic conditions change rapidly. Future research should investigate how to handle these dynamic changes.
  • Practical Implementation: While the paper provides a theoretical framework and numerical experiments, further work on practical implementation considerations, such as sensor maintenance and stability, would be beneficial.

Summary updated

BibTeX
@misc{shan2018optimization,
  author = {Donghui Shan and Xiaoduan Sun and Jianbei Liu and Ming Sun},
  title = {{Optimization of Scanning and Counting Sensor Layout for Full Route Observability with a Bi-Level Programming Model}},
  year = {2018},
  doi = {10.3390/s18072286},
}
Figure