Application of Reactive Tabu Search for Combined Dynamic User Equilibrium and Traffic Signal Optimization Problem

Abstract

A new mixed-zero-one continuous linear bilevel formulation is presented. It simultaneously solves the traffic signal optimization problem and the dynamic user equilibrium problem and yields a mutually consistent solution. The upper-level problem finds optimal traffic signal settings (cycle lengths, green times, time offsets, and phase sequences) for prespecified signalized intersections such that the total system travel time is minimized. The lower-level problem is the existing user-optimal dynamic traffic assignment (UODTA) linear program that embeds Daganzo's cell transmission model (CTM). The reactive tabu search (RTS), based on the analogy between the direct search and the dynamical systems theory, is modified to solve the problem. There are three major modifications. First, the binary-string solution representation is chosen, and the associated encoding and decoding procedures are developed for three-, four-, and five-leg intersections. Second, three neighborhood definitions for RTS are proposed; they yield three variations of the algorithm: RTS-MT0, RTS-MT1, and RTS-MT2. RTS-MT0 uses the deterministic neighborhood definition, and the others are based on probabilistic neighborhood definitions. Third, the functional evaluation uses the existing simulation-based UODTA that uses the CTM. Comparisons of algorithm performance are conducted on a hypothetical grid network and a modified Sioux Falls, Iowa, network. The performances are compared by using three criteria: solution quality, convergence speed, and CPU time. The CPU times for RTS-MT0, RTS-MT1, and RTS-MT2 on the two test networks are approximately equal. On the other two criteria, RTS-MT2 appeared to be the best, and RTS-MT1 and RTS-MT0 were the second and the third best, respectively.

Get full access to this article

View all access options for this article.

References

Daganzo

C. F.

The Cell Transmission Model: A Simple Dynamic Representation of Highway Traffic Consistent with the Hydro-dynamic Theory. Transportation Research B, Vol. 28, No. 4 1994, pp. 269–287.

Karoonsoontawong

A. A.

Robustness Approach to the Integrated Network Design Problem, Signal Optimization and Dynamic Traffic Assignment Problem. PhD dissertation. Department of Civil Engineering, University of Texas at Austin, 2006.

Lee

Combined Traffic Signal Control and Traffic Assignment: Algorithms, Implementation and Numerical Results. PhD dissertation. University of Texas at Austin, 1998.

Yang

and Yagar

Traffic Assignment and Signal Control in Saturated Road Networks. Transportation Research A, Vol. 29, No. 2 1995, pp. 125–139.

Wong

S. C.

and Yang

Reserve Capacity of a Signal-Controlled Road Network. Transportation Research B, Vol. 31, No. 5 1997, pp. 397–402.

Chiou

S. W.

Optimization of Area Traffic Control for Equilibrium Network Flows. Transportation Science, Vol. 33, No. 3 1999, pp. 279–289.

Gao

Z. Y.

and Song

Y. F.

A Reserve Capacity Model of Optimal Signal Control with User-Equilibrium Route Choice. Transportation Research B, Vol. 36, No. 4 2002, pp. 313–323.

Waller

S. T.

Optimization and Control of Stochastic Dynamic Transportation Systems: Formulations, Solution Methodologies, and Computational Experience. PhD thesis. Northwestern University, Evanston, Ill., 2000.

Beard

and Ziliaskopoulos

System Optimal Signal Optimization Formulation. In Transportation Research Record: Journal of the Transportation Research Board, No. 1978, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 102–112.

10.

Sun

Benekohal

R. F.

and Waller

S. T.

Bi-level Programming Formulation and Heuristic Solution Approach for Dynamic Traffic Signal Optimization. Computer-Aided Civil and Infrastructure Engineering, Vol. 21, 2006, pp. 321–333.

11.

Park

Development of Genetic Algorithm-Based Signal Optimization Program for Oversaturated Intersections. PhD dissertation. Texas A&M University, College Station, 1998.

12.

Ukkusuri

S. V.

and Waller

S. T.

Linear Programming Models for the User and System Optimal Dynamic Network Design Problem: Formulations, Comparisons and Extensions. Networks and Spatial Economics, Vol. 8, No. 4 2007, pp. 383–406.

13.

Karoonsoontawong

and Waller

S. T.

Integrated Network Capacity Expansion and Traffic Signal Optimization Problem: Robust Bi-level Dynamic Formulation. Networks and Spatial Economics, DOI 10.1007/s11067-008-9071-x, 2008.

14.

Battiti

and Tecchiolli

The Reactive Tabu Search. ORSA Journal on Computing, Vol. 6, No. 2 1994, pp. 126–140.

15.

Goldberg

D. E.

Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, Mass., 1989.

16.

Ziliaskopoulos

A. K.

and Waller

S. T.

An Internet-Based Geographic Information System that Integrates Data, Models and Users for Transportation Applications. Transportation Research C, Vol. 8, 2000, pp. 427–444.