Notes on a Mixed Integer Linear Programming Formulation of the Dynamic Traffic Routing Problem Robert L. Smith Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109 April 22, 1991 Technical Report 91-18

RLS 4/22/91 Notes on a Mixed Integer Linear Programming Formulation of the Dynamic Traffic Routing Problem Let G = (N,A) be the traffic network with node set N and link set A with origindestination pairs (si, ti), i = 1,2,...,I. We model the problem with horizon p periods each of duration At as a time expanded version of G, G(p) = (J, A). Corresponding to node x of G, G(p) has p + 1 nodes x(r), r= 0,1,...,p; corresponding to arc (x, y) of G, G(p) has arcs (x(r), y(r + s)),O < r p -1. (See Figure 1.) Every arc (x(r), y(r + s)) E A has an associated 0-1 variable S(x(r), y(T + s)) = 0 or 1 according as the total flow f(x(r), y(T +s)) equals 0 or is greater than 0 respectively (x ^ y). A constraint associated with every arc (x, y) E A and every time r is Zs>o 6(x(r), y(r +s)) < 1 (x: y). Note that vehicles are not forced to go from x to y at time r. Let c(X(r), y(T + s)) be the capacity associated with arc (x(r), y(r+s)) E A so that up to c(x(Tr), y(r+s)) vehicles could leave node x at time r and still get to node y by time r + s. In particular, if aoXy(v) is the speed attained by v vehicles entering node x at time r along link (x, y) E A and d(x, y) is the length of link (x, y), then c(x(r), y(r + s)) = a7(d(x, y)/s). Key Assumption: The time to traverse a link (x, y) at time r is determined by the number of vehicles already on (x, y) plus sent at time r through x along (x, y). This time remains fixed independent of vehicles routed along (x, y) after time r. For each commodity k, Sk is the singleton set of sources, Tk is the set of sinks, and Rk is the set of other nodes respectively. In particular, if x(r) G Sk and y(r + s) E Tk for s > 0, then Vk trips originate at node x at time r and terminate at node y. The source set Sk is a singleton consisting of x(r) if the kth trip originates at node x at time r and Tk consists of {y(r + s)Is > 0} where y is the destination node. The flow fk(x(T), y(r + s)) is the number of vehicles taking trip k along (x,y) at time T in time s. The total flow f x(r),y(r + s)) of vehicles along link (x, y) departing node x at time r and arriving at node y at time r + s is then f(x(r), y(r + s)) = EK=i fk(x(r), y(r + s)). We set the travel time ak(r(T),y(T + s)) for trip k along arc (x(T), y(T + s)) to be 0 if x = y E Tk (since we've arrived at the destination and can just sit at the node until the end of the horizon) and s otherwise. This brings us to the formulation of the problem. 1

MILP Formulation (System optimal criterion) K min E E ak ( (T), (r + S))f (X (), y(r + s)) k=l (Z(T),y(r+s))E.A (Minimum total vehicle time) s.t. Vk if x(r) Sk fk(x(T), Y(r + S)) - fk(Y(r - S), (r)) = -vk if x() E Tk, (1) 0 if x(r) E Rk x(Tr)e A, k 1,2,...,VK (Flow balance at node x(r) for the kth O-D pair) f(x(T), Y(r + s)) < c(x(r), y(r + s)) - f(x(r - S), y(T + S)), (2) (x(r), Y(r + S)) E A, (Impedance capacity constaint for each arc (x(r), y(r + s))) f(x(T),y(T + s)) < 6(x(r), Y(r + s))c(x(r), y(T + S)), (3) (x(T), y(r + s)) e A, X - y S(x(r), y(r + S)) < 1, (4) x(r) e A, (x, y) E A,x y. (All vehicles that enter link (x, y) E A at time r must exit the link at the same tinie r + s) fk(x(r), Y(7 + s)) > 0,1 > 6(x(T), y(T + s)) > 0 integer for all (x(T), y(T + 3)) E A. (Variable restrictions) 2

Note that for S(x(r),y(r + s)) = 1, constraint (3) is redundant in the presence of (2) and hence is only binding if 6(x(r),y(r + s)) = 0 in which case f(x(r),y(r + s)) = 0 so that no vehicles are allowed to travel over arc (x, y) at time r in time s. Indeed, if 8(x(r),y(r + S)) = 0 for x $ y, no vehicles take arc (xy) out of x at time T. They either take another arc (x, y') or they hold at node x. Note also that S = {sls > 0} and Y ={z E Nl(x,z) E A for somex EN or (z,y) E A for some y E N}. Convention: Substituting a capital letter Z for small letter z in f(z) requires summing f(z) over all z E Z, i.e., f(Z) -E W f(z). zEZ Remarks: 1. We have a MILP since removing the integer variable restriction yields a LP. This is the contribution of the formulation. The MILP may be solved by the Branch-and-Bound algorithm. Most codes automatically branch to exploit the "multiple choice" structure of constraint (4). Since there is a 0-1 integer variable associated with every arc in G(p), there are O(INl2p2) in all. However, by binary encoding the arc number (x(r), y(r+s)) taken by vehicles leaving node x at time r for y, we can reduce this th o O(IN2plogp). For a micro-level transportation network, there are at most 4 arcs per node so that there are at most (4INI plog p) 0-1 integer variables. For example, for a horizon of 10 periods, we get at most (1201N1) 0-1 variables or 12,000 for a 100-node network. What is the largest transportation network that we can solve? How good is the solution to the LP relaxation? 2. Since the arc costs ak(x(r),y(r + s)) depend on the O-D pair k only through the corresponding destination and not the origin node or time, we may as in the dynamical system model redefine fk(x(7), y(7 + S)) as the number of vehicles going to destination tk along (xy) departing node x at time r in time s, k = 1,2,...,. This considerably reduces the number of continuous variables in the formulation. 3. Since the set of feasible solutions is closed and bounded, and the objective function is continuous, there exist a system optimal dynamic routing: 6*(.), fk*(*), k = 1,2,..., IK. 4. Given 6*(.), fk*(),k = 1,2,...,K is an optimal solution to a (nontrivial?) linear program. For example, fk*(.), k = 1,2,..., IK is without loss of generality an extreme point solution. Properties? 5. Remark 3 suggests an iterative heuristic. Clearly, 6* (or fk*, = 1,2,..., IK) yields a fixed point of the iterative method by Remark 3 that given 6 = 6*,fk = fk is LP optimal. 3

6. Is it possible for S(x(r), y(r + s)) > 0 in the optimal relaxed LP for more than two values of s > 0 for strictly convex impedance functions? 7. It seems clear that it may be optimal to wait at a node other than a destination, i.e. that the optimal flow fk(x(r), (r + 1)) > 0 for x(r) T Tk. (Note however that all waiting can be eliminated by setting ak(x(r), y(r + s)) = oo.) Does the optimal flow have to satisfy f*(x(r), y(r + s))f*(x(r'),y(r + s')) = 0 for r' < r and s' > s? That is, is the consistency condition necessarily satisfied that you cannot arrive at the end of a link sooner by arriving at the beginning of the link later? 8. To insure accuracy of the impedance model, we could without loss of optimality require, that if f*(x(r), y(r + s)) > 0, then c(x(r), y(r + s - 1)) < f*(x(r),y(r + s)) < c(x(r), y(r + s)). (5) Otherwise all vehicles could feasibly take arc (x(r), yr + s - 1)) say and get to node y one period earlier. However, if it were optimal to arrive at node y at time r + s, they could wait at node y for one period so that (5) is not forced. We could insure (5) by adding the constaint: 5(X((), y(r + s))c(x(r), y(r + s - 1)) < f*((r), yr( + s)) < 6(x(7), y(r + s))c(x(r), y(r + s)). (6) 9. If we define S _ {sls > 0}, constraint (2) simplifies to f(x(r - S), y(r + S)) < c(x(r), y(T + s)). This formally suggests several alternative impedance models. Is there a more natural one than (2)? 10. Suppose we replace the objective function by K s min E E E ak(x(), y(r + s'))c(x(r), y(r + s'))6(x(r), y(r + s)) k=1 (x(T),y(-r+))EA s'=l (Minimum average vehicle time) Note that the objective function remains linear. Do we get a user optimal formulation? That is, does an optimal solution have the property that a) all routes taken by the vehicles departing origin si for destination ti at time r experience the same trip times, and b) any vehicle would experience a greater trip time if it took an alternate route? If so, given an optimal link loading 6* for this formulation, can it be shown that a single pass of the Dynamic Router recovers the associated optimal routing fk, k = 1,2,..., K? (Assume here as elsewhere that the At period error is negligible.) 4

y (N, A) = G x z y z (N, A) = G(p) 0 1 2 3 p Figure I - Triangle network with two alternate routes