Active Traffic Sensor Location Problem for the Uniqueness of Path Flow Identification in Large-Scale Networks

Abstract

Over time, traffic sensors have become recognized as a leading source of traffic flow data. Despite their solid capabilities for measuring various types of traffic flow information, they cannot be implemented at all intersections or mid-blocks within the transportation network. Consequently, the traffic sensor location problem (TSLP) emerged to address the questions of how many sensors are needed and where they should be installed. This study presents a new formulation that combines path covering and differentiation into a single sensor location strategy using vehicle identification sensors. The solution strategy ensures the uniqueness of path flow identification. The problem’s complexity has two main dimensions: its mathematical formulation, which is known to be NP-hard, and the inherent combinatorial complexity resulting from the need for complete network path enumeration. Therefore, finding an efficient solution algorithm for large-scale networks is challenging. In this article, the problem is recast as a set-covering problem. The dual formulation is then considered, demonstrating that a shortest path-based column generation strategy can produce as many paths as needed, avoiding existing intractability. This path-building process resolves the problem using a combination of heuristics and exact solution methods. The scalability of the proposed strategies was evaluated using two networks of varying sizes. A benchmark network demonstrated the results’ uniqueness compared to those in the literature. Additionally, the method proved highly effective in managing a network with more than 10,000 demand node pairs, producing practical solutions under normal traffic flow circumstances.

Keywords

• Active sensing
• meta-heuristics
• path flow observability
• screen line problem
• traffic sensors