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

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.