A discrete optimization approach for locating Automatic Vehicle Identification readers for the provision of roadway travel times

This paper develops an algorithm for optimally locating Automatic Vehicle Identification tag readers by maximizing the benefit that would accrue from measuring travel times on a transportation network. The problem is formulated as a quadratic 0–1 optimization problem where the objective function parameters represent benefit factors that capture the relevance of measuring travel times as reflected by the demand and travel time variability along specified trips. An optimization approach based on the Reformulation–Linearization Technique coupled with semidefinite programming concepts is designed to solve the formulated reader location problem. To illustrate the proposed methodology, we consider a transportation network that is comprised of freeway segments that might include merge, diverge, weaving, and bottleneck sections. In order to derive benefit factors for the various origin–destination pairs on this network, we employ a simulation package (INTEGRATION) in combination with a composite function, which estimates the travel time variability along a trip that is comprised of links that include any of the four identified sections. The simulation results are actually recorded as generic look-up tables that can be used for any such section for the purpose of computing the associated benefit factor coefficients. Computational results are presented using data pertaining to a freeway section in San Antonio, Texas, as well as synthetic test cases, to demonstrate the effectiveness of the proposed approach, and to study the sensitivity of the quality of the solution to variations in the number of available readers.