A Discrete Optimization Approach to Solve a Reader Location Problem for Estimating Travel Times

Abstract

Traffic incidents routinely impact the flow of vehicles on roadways. These incidents need to be identified, and responded to in a timely fashion in order to keep traffic moving safely and efficiently. One of the main areas of transportation research that remains of contemporary interest is the study of travel times. Travel time information technologies, until very recently, have not been efficient enough to provide instantaneous information for managing traffic flow.

The Virginia Department of Transportation (VDOT) currently operates a number of surveillance technologies. Of particular interest to us are Automatic Vehicle Identification (AVI) tag readers to assimilate travel time information. One of VDOT's latest research thrusts has been to develop efficient algorithms for estimating link travel times using such advanced technologies. To achieve this purpose, VDOT is currently monitoring volunteer tagged cars by using AVI tag readers fixed at certain specific locations.

This thesis focuses on devising an efficient methodology to capture as much travel time information as possible, by solving a Reader Location Problem that maximizes the benefit accruing from measuring travel time variability with respect to freeways. This problem is formulated as a quadratic 0-1 optimization problem. The objective function parameters in the optimization problem represent certain benefit factors resulting from the ability to measure travel time variability along various origin-destination paths. A simulation study using the INTEGRATION package is performed to derive these benefit factors for various types of freeway sections, and two composite functions that measure benefits for O-D paths that are comprised of several such sections are presented. The simulation results are presented as generic look-up tables, and can be used for any freeway section for the purpose of computing the associated benefit factor coefficient.

An optimization approach based on the Reformulation-Linearization Technique coupled with Semidefinite Programming concepts is designed to solve the formulated reader location problem. This approach can be used to derive alternative equivalent formulations of the problem that vary in the degree of tightness of their underlying linear programming relaxations. Four such model representations are explored by using the software package, AMPL-CPLEX 6.5.3, to solve them for some sample transportation networks.

The sensitivity of the reader locations to the different proposed benefit factor composite functions is also investigated. The results indicate that the first level continuous RLT relaxation to problem RL produces a tight underlying representation and that the optimal solution obtained for this relaxation tends to be very close to the actual integer optimum. Moreover, it is found that the optimal locations of the readers are insensitive to either the traffic, or the benefit factor used, or the density of the graph, when these factors are considered individually. However, a combination of two or more of these factors can lead to a change in the optimal locations of the readers.