ON THE CONVERGENCE OF ITERATIVE ROUTINGASSIGNMENT PROCEDURES IN DYNAMIC TRAFFIC NETWORKS* Alfredo Garcia Robert L. Smith Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 95-26 November 1995 *This work was supported in part by the Intelligent Transportation Systems Research Center of Excellence at the University of Michigan.

On the Convergence of Iterative Routing-Assignment Procedures in Dynamic Traffic Networks. Alfredo GARCIA and Robert L. SMITH Department Of Industrial and Operations Engineering University of Michigan, Ann Arbor Abstract We show that if a traffic network satisfies a certain property, called submodularity then there exists a user-optimal pure routing policy, and under some other slightly more restrictive assumptions this policy can be obtained by an iterative routing-assignment procedure. 1 Introduction We consider the problem of finding a user-optimal routing vector in a dynamic traffic network, i.e. a set of routes, one for every vehicle in the network such that there is no other way for any driver to reduce his expected travel time, by independently taking another route. This problem can also be formulated as that of finding a fixed point of the composition of two mappings. One, called the Assignment Mapping that given a routing vector calculates the expected dynamic travel times for every link and the second, is called the Routing Mapping finds the optimal route for each driver(shortest path on a network),given a set of expected dynamic travel times per link. In order to find a user-optimal routing policy, an iterative procedure that alternates between these two mappings has been implemented (SAVaNT Kaufman, Smith, Wunderlich 1991). Experimental results have been favorable but -difficult to justify theoretically, for there is no theoretical proof for the convergence of-such an algorithm. In this paper, we tackle the problem of validating such algorithm and at the same time to gain some helpful insights on its possible improvements. Our work builds on the work done by Topkis (1979) and Vives (1990). When a traffic network satisfies a condition called submodularity one can prove the existence of a user-optimal pure routing choice policy. Pure means a extreme point of the convex hull generated by available routes. Then, with some slightly more restrictive assumption, one can prove the convergence of the iterative routing-assignment procedure to a user-optimal pure routing choice policy. 1

2 Preliminaries. 2.1 Notation. We consider a traffic network where * N = {1,2,..., n} is the index set of vehicles. * Every vehicle has a finite number of routing choices, that is to say: for every i E N there is a set IIi = {ril, ri2,...., rimi} of possible routes to take. Then, the space HII is the convex hull generated by these routes, i.e all possible convex combinations of routes and we have II, C II. ri E Ii is the routing decision for driver/vehicle i E N, i.e it is a path in the network joining origin and destination nodes. We note II = XijENII and II = XiENHi as the cartesian product spaces. A very helpful notation is _r-i E II-,, which means a vector of all routing decisions except ri. * A: H C, C C 3I? is the assignment mapping. For any ir routing policy vector, Ai(7r) is the sum over the path determined by 7ri of the expected dynamic travel times per link, that is to say, the total expected travel time for vehicle i. * Ri: C -- Hi is the routing mapping. For any set of expected dynamic travel times per link in the network, we let c be the vector of expected travel times for all possible routes for vehicle i, then, Ri(c) is the route for vehicle i that yields the least expected travel time. 2.2 Pure and Mixed routing decisions. A pure routing choice is any extreme point of the space II, i.e any element of II. Any other point in the convex hull is called a mixed routing choice. Note that, by construction the product space II is compact and convex. A word of caution is worth: the framework here used is more general than that of considering all or nothing or multipath policies. All or nothing means that all vehicles entering a link at some time must take the link specified by the routing policy. A slightly more general consideration leads to multipath policies, i.e. a routing policy such that for all vehicles entering a link at some time, they then take different links according to some convex combination (platoon split). Our framework goes even further, for when entering a link at some time we allowed vehicles to take any possible link, i.e multipath policy with the largest possible platoon split. Furthermore, we allowed drivers to draw routes from a "lottery" that assigns a probability distribution on each vehicle routing decision space HII. Outcomes from that "lottery" are called mixed routing decisions. When the probability distribution is degenerate we called the outcome a pure routing decision. 2

User-optimal routing We say that a routing vector ir* is user-optimal if for every vehicle i E N the route chosen in ir* is the shortest path or minimum total travel time route, provided that rl*, the choice of all other vehicles is held fixed. rt = arg min Ai(ri, r_) (1) iE IIi Now, having in mind the way we defined Ri(.), the routing mapping, it turns out that (1) can also be expressed as: 7r = Ri(A,(7ri,, r)) (2) Finally, in vector notation (2) is: Tr* = R(A(r')) (3) from where we can see the very familiar definition of a fixed point. Therefore, a user-optimal routing vector is a fixed point of the composition of the routing and assignment mappings. 2.3 Existence of User-Optimal Routings in Mixed Decisions. A mixed routing decision ir E IH is a convex combination of routing decisions in the space II. If we note p, to be the measure defined on H that assigns for every r' E II the coefficient of the convex combination to obtain ir, then the domain of the assignment mapping is extended in the following way: A(T) = A(r').(T) (4) Equation (4) provides the total expected travel time for any interior point ( i.e points in II but not in H ). In the same manner one can also thne oink of the routing mapping to be the stochastic shortest path mapping, and thus it is also defined on II. 3

Theorem 1: Any Traffic Network has a user-optimal routing in mixed routing decisions. Proof: This characterization of user-optimal routings parallels Nash (1950), the fundamental existence theorem in game theory. We use Kakutani's fixed point theorem, to prove that (3) has a fixed point 7r*. The hypothesis on this theorem are: (a) Compactness and convexity of the product space I. (b) Non-emptyness of the composition Ri(A(.)). This follows from the fact that (4) implies that the assignment mapping is linear(therefore, continuous) on each Ii. Continuous functions attains minima on a compact set. Non-emptyness follows. (c) R(A(.)) is convex on II. If R(A(.)) were not convex there would be r', Ir E R(A(7r)) and a A E (0, 1) such that Ar' + (1 - A)ir" R(A(7r)). But for each vehicle i E N we have: Ai(A7r; + (1 - A)7r,, 7r_) = AA(7ri, r-i) + (1 - A)A(7r', 7r_,) (5) So that if 7r', i7r are optimal routes given r-_i so is their weighted average. (d) R(A(.)) is lower semi-continuous. Suppose it is not. Then, there is a sequence (cn", r") - (cr, ir) such that *r" E R(A(irn)) but X* B R(A(7r)). Then for some vehicle i, there is a e > 0 and a.rT, such that: Ai(r', 7r-_) > Ai(ri, Hij) + 3e (6) Now, since Ai(.) is continous for n large we have: Ai(ri, 7r, ) > Ai(r,, ri) - e > A,(7ri, 7r_) + 2c > Ai(7ri, r_) + E (7) Here, we say that art does better than 7r' given irns which is a contradiction. 3 Some Concepts and Results on Lattice Theory In this section we briefly describe some definitions and powerful tools in lattice theory. A classical reference is Birkhoff(1967). Lattices, Sublattices, Completeness. In order to be able to compare different routing vectors one assume an arbitrary partial ordering (i.e binary relation that is reflexive, antisymmetric and transitive )">", for every vehicle in the space of routing choices. For instance, one could think of the natural ordering to be the preferences over the different routes given some prior knowledge of the efficiency of these ones. But this would only provide a partial ordering in IIi. An easy way of 4

constructing a partial ordering on II is by means of a one-to-one mapping from IIi to a compact subset of the real line. Then, the "natural" ordering on the reals will provide via the one-to-one mapping a partial ordering on the whole space II As every routing decision space HI, i E N is compact there are 77ri, ~ E HI such that V7ri E Ii Ti W_ iri, 7ri t Z,. A Lattice is a partially ordered set such that it contains for every pair of its elements an "upper" and "lower" bounds. Then, every routing decision space II, is a lattice. We now define the partial ordering on the product space H to be: 7r,'E, 7r' > i > 7r' Vi E N (8) Similarly, one can define the meet and the join for any two vectors in the product space II, to be the min and the max taken componentwise. min(7r, r'):= (min(7rl, 7rl),.., min(7ri, r),..., min(7r,, 7rn)) (9) max(7r, r ):= (max(7ri, 7r),.., max(ri, r),..., max(7n, 7r)) (10) Then, II is a Lattice, because for any two vectors 7r,lr E II then the meet, min(r, 7r') and the join, max(r, 7r) are also in II. A lattice is said to be complete if for any subset of it there are "greatest" and "least" elements. As we have seen, each routing decision space II, is a non-empty, complete lattice and so must the product space I. A Sublattice is a subset of a lattice such that for every pair of elements their "meet" and their "join" are also in the subset. A complete lattice(sublattice) is compact in the interval topology ( Topkis 1976 ). The following is the basic. theorem for this work: Tarski's Fixed Point Theorem (1955): Let H C Rn be a non-empty,compact sublattice. If f: H -I H is non-decreasing, i.e if 7r 7r' implies f(ir) > f(r'), then f has a fixed-point in H, i.e f ( T) = 7r Submodularity. The assignment mapping is said to be submodular if for all 7r,l' E II, for all i E N then: Ai(7r) + Ai(r') > Ai(min(7r, r')) + Ai(max(7r, r')) (11) It is hard to interpret this condition without some idea of what the partial ordering in each driver/vehicle decision space means. If we take for instance, the natural ordering then submodularity yields some hope for compromise between any two routings, for if drivers are given their 5

highest preference and their lowest between two routings and we take the average of the expected travel times experienced, this average is less than or equal to the average of the travel times for these two routings. One can also look at (7) not in the product space,but in each routing decision space for each driver/vehicle. For that, the following lemma is very useful. Lemma 1: If A, the assignment mapping, is submodular in H then, for all i E N, we have: (a) For any _ri E II-i and ri,irI E II: Ai(7ri, 7r_-) + Ai(r,, i.,) > A,(min(7r,, r'), 7ri) + Ai(maz(7ri, r,), r-i) (12) and (b) If 7ri _ 7r and 7r-i _> ri then: Ai(7ri, 7ri) - Ai(7r, 7r1,) > Ai(ri, 7r-) - Ai(7,, ri) (13) Proof: (a) Take 7r,r' E II such that 7rj = 7rj for all j E Nj i, then apply (7). (b) Define u = (r,ir_i) and v = (7ri,7ri) so that min(u,v) = (7r'i,7ri) and max(u,v) = (ri,7r-i) Then, if we apply (7) to u and v we get (b). In the litterature, (a) is also called submodularity on 7ri and (b), isotone differences on 7ri. 4 Existence of a Pure Routing User-Optimal Solution We now show that if a traffic network satisfies submodularity i.e the assignment mapping is submodular, and Ai() is lower-semicontinuos on 7ri, then with the help of Tarski's fixed point theorem there is a pure routing user-optimal solution. Furthermore, the proof is constructive, so we characterize this pure routing user-optimal solution. Theorem 2: Any Traffic Network that satisfies (1) Submodularity (2) Vi E N Ai() is lower semi-continuos on Hi has a User-Optimal solution in Pure routings. Proof: 6

(1) Ri(Ai(,7ri)) is a sublattice on II,. Suppose r and r, are both in Ri(Ai(, 7r.)). Then, by optimality we have: Ai(ri, 7r_i):= Ai(r,, 7ri) < Ai(max(ri, r'), 7r_i) (14) Submodularity on II implies then: Ai(min(7ri, 7r,), ri) < Ai(7ri, ri) (15) Ai(min(7ri, 7r'), vr-i) < Ai(.ri, ri) (16) which is a contradiction, therefore, min(ri, ir), max(ri, ri) E Ri(Ai(, r-i)) (2) R,(Ai(, 7ri)) is non-empty. Consider a sequence gr' such that: inf Ai(r', 7r._):= lim A,(7rJ, 7r_,) (17) ErEnL n —oo The space IIi is compact thus there is a converging subsequence {lr}k, i.e lim {rIk} = r, (18) k — oo Then,lower semi-continuity of Ai(, 7ri) on Ii implies: lim inf Ai(7ri"k, 7r-i) > Ai,(r, ri) (19) k -+00 therefore,;ri E Ri(Ai(, r_i)). (3) So finally as R,(Ai(, r_i)) is a non-empty,compact sublattice of HII there are'K and Ti, least and greatest element on the sublattice. Since, A() is submodular on II, Ai() has isotone differences on HII,and this implies that both, and TFi are non-decreasing in H.-,. Hence,defining f() to be: f(r) (= (7r-i)..,n(7r-n)) (20) Conditions on Tarki's fixed point theorem are met, and by construction 7r is the user-optimal pure routing choice. It is worth noticing that T is also a user-optimal pure routing choice. 5 On the convergence of an Iterative Routing-Assignment Procedure. A straightforward question on this approach is the question of when the Iterative Routing-Assignment Procedure will converge, and if so if it converges to a pure routing user-optimal solution. This 7

Iterative mechanism is also known as fictitious play for at each iteration, all driver/vehicles take their optimal route given that the choices of all other drivers of the last iteration are held fixed. The proof makes use of Lemma 2, which states the monotonicity in the partial ordering of each player of the composition of the routing and assignment mappings. This property looks very much alike the contraction property, in other contexts(for instance, dynamic programming ). Lemma 2: If r, E Ri(Ai(, 7-i)), a compact,non-empty sublattice of Hi and Ai() has strictly isotone differences on Hi, then: r-it >- 7r-i *, Tri > ri (21) proof It is implied by the following sequence of inequalities: Ai(7ri, tr-i) < Ai(max('ri, 7ri), iTi) (22) Ai(7ri, r'_i) < Ai(max(ri, lri), rkli) (23) Ai(min(7ri, 4r), 7ri) < Ai(7r, ri) (24) Ai(min(7ri, 4r,), rli) = Ai(7', 7-i) (25) (16) means optimality of Iri against 7r_,,(17) follows from isotone differences on iri and the fact max(7ri, 7r) >- ir. (18) comes from submodularity on 7ri and (20) is optimality of 7r, against 7r-i. Now,let us recall the simple algorithm structure of an iterative routimg- assignment method. Pick any 7r~ starting routing vector then, rk:= R(A(7rk-l)) and so on, we stop when for some k > j,'k = T7i. Theorem 3: In Any Traffic Network that satisfies, Vi E N (1) Submodularity on HII and strict isotone differences on Hi ( i.e (b) in lemma 1, with strict inequality.) (2) Ai() is lower semi-continuous on Hi and continuous on HI,. an Iterative Routing-Assignment Mapping converges to an User-Optimal solution in Pure routings. Proof: Let ir9 > sup Ri(Ai(, 7r~i)). That is to say, under partial ordering on II the starting point is above the best response to 7r_,( i.e Ri(A,(, r,))). Then, 7r > sup Ri(Ai(, 7r_)) > r1 (26) recalling that, i7r, E Ri(Ai(, 7r~,)). Therefore, Lemma 2 implies that 7ri > 7rT,since 7rw E Ri(Ai(, 7r.)) and rT? E Ri(Ai(, r))) for rr~ > ri. If 7r~i = r, then 7r = r? Hence, the iterative routing-assignment mapping generates a "decreasing" sequence in II, say.k. 8

The intersection of closed sets of the form, Ck:= {r E H; rTk > r} is non-empty and equal to the infimum of the sequence _r. r= inf rk (27) ir is also an user-equilibrium solution because, Vk Ai(tri, -') > Ai(;r, 7r-1) (28) using, lower semi-continuity on;ri and continuity on r-i: Ai(7ri,,k-1) > liminf Ai(, r-) > i(A,n -1 ) (29) k —-oo 00 In the same manner, one can prove that if the starting point is such that, inf Ri(Ai(, ir),)) > 7r~ then the algorithm converges to T. 6 Some final comments. The submodularity condition, is very restrictive in our context (although in some economic applications it seems to arise naturally, Vives(1990)). To see this, take for instance the case in which n drivers/vehicles enter the network all at the same node, and all have the same final destination. Suppose there are two routes available, a freeway and a sideroad. Furthermore, all drivers "prefer" the freeway. Now, submodularity would imply that no matter what the routings of the n vehicles between these two choices are, if you take the average of the expected travel times this one must be greater than or equal to the average of "allowing" every driver to take their highest preference, (freeway) and their lowest (side-road). This condition clearly suggests some sort of complementarity in a network, although it goes beyond this, for if the two routings of the n vehicles are such that in one, driver i gets the freeway all alone, and the second, drivers i and i + 1 get the freeway, the two of them only, then it is hard to require the average of the travel times that driver i would experience to. be greater than or equal to what he would experience under the "highest" and "lowest" routings. Experimental results have shown that using a rather simple assignment rule such as "the link travel time that the vehicle entering the link will experience is equal to the travel time experienced by the last vehicle that left the link ", convergence is obtained very frequently. This empirical fact would eventually lead to an easy way of "constructing" submodularity. Finally, one could also pose the question in the opposite sense, and try to find partial orderings in every driver/vehicle decision space II such that the partial ordering induced in the product space II satisfies the submodularity condition. These are topics of further research. 9

REFERENCES Vives X. (1990). Nash Equilibrium with strategic complementarities Journal of Math. Economics 49, pp. 304-321 Topkis D. (1979). Equilibrium points in Non-zero sum n-person submodular games, SIAM J. of Control and Optim. 17, pp. 773-787'Topkis D. (1978). Minimizing a submodular function on a lattice Operations Research. 26 no. 2, pp. 305-321 Tarski A. (1955). A lattice theoretical fixed-point theorem and its applications,Pacific Journal of Mathematics 5, pp. 285-308 Fudenberg D. and Tirole J. (1991).Game Theory, MIT Press., pp. 490-498 Birkhoff G. (1967). Lattice Theory,3rd ed.,American Mathematical Society 15, Colloquium Publications, Providence RI Nash J. (1950). Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36: 48-49. Kaufman D., Smith R., Wunderlich K. Dynamic User-Equilibrium properties of Fixed-Points in Iterative Routing-Assignment Methods. IVHS Technical Report 92-12 University of Michigan. 10