Mathematical Models and Algorithms for the Location of Sensors on a Traffic Network.

摘要

We study the sensor location problem in the context of transportation planning. More specifically, we seek to answer the following question: "where to locate a limited number of traffic sensors on a highway network so as to obtain the best possible traffic data for the entire network?";We propose several integer programming models for solving this problem with two distinct objectives (namely, minimizing total dissimilarity and/or maximizing the minimum dispersion), and with two distinct types of restrictions, i.e., a fixed number (p) of sensors, or a cost (ci) associated with installing a sensor at each location i, and a total budget b.;We show that in their basic forms these models are comparable to two well-know problems in location theory, namely the p-median problem and the p-dispersion problem. We then propose new effective integer programming models and algorithms for solving the p-dispersion problem, the total dissimilarity problem with the budget constraint, and the bi-criteria p-median problem/ p-dispersion problem. We demonstrate the effectiveness of the proposed algorithms through comprehensive computational analysis.