Vehicle-ID sensor location for route flow recognition: Models and algorithms

We address an important problem in the context of traffic management and control related to the optimum location of vehicle-ID sensors on the links of a network to derive route flow volumes. We consider both the full observability version of the problem, where one seeks for the minimum number of sensors (or minimum cost) such that all the route flow volumes can be derived, and the estimation version of the problem, that arises when there is a limited budget in the location of sensors. Four mathematical formulations are presented. These formulations improve the existing ones in the literature since they better define the feasible region of the problem by taking into account the temporal dimension of the license plate scanning process. The resulting mathematical formulations are solved to optimality and compared with the existing mathematical formulations. The results show that new and better solutions can be achieved with less computational effort. We also present two heuristic approaches: a greedy algorithm and a tabu search algorithm that are able to efficiently solve the analyzed problems and they are a useful tool able to find a very good trade-off between quality of the solution and computational time.