Network Sensor Location Problem with Monitored Lanes: Branch-and-Cut and Clustering Search Solution Techniques

Abstract This paper presents a mathematical model for the network sensor location problem where traffic sensors are installed in road segments considering constraints related to the maximum number of devices and the maximum number of monitored lanes. Furthermore, we propose a Branch-and-Cut (B&C) algorithm and a Clustering Search (CS) heuristic to find solutions for this problem. The B&C algorithm considers a relaxed mathematical model of the problem and generates cuts based on integer solutions found during the branch-and-bound tree. Our CS heuristic partitions the search space into clusters and applies local search on the promising ones. Based on real data of the Brazilian road network, computational tests were conducted to assess the behaviour of the two solution approaches. Different scenarios were created using variations for the maximum number of sensors and for the number of monitored lanes. The results show that CS heuristics provides good solutions in 92.31% of the studied scenarios.