DYNAMIC PROGRAMMING HEURISTIC FOR SYSTEM OPTIMAL ROUTING IN DYNAMIC TRAFFIC NETWORKS Alfredo Garcia Robert L. Smith Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 and Raja Sengupta Institute for Transportation Studies University of California Berkeley, CA Technical Report 95-22 November 1995

Dynamic Programming Heuristic for System Optimal Routing in Dynamic Traffic Networks. Alfredo Garcia, Robert L. Smith. Industrial and Operations Engineering Department. University of Michigan, Ann Arbor, MI. 48109 and Raja Sengupta Institute for Transportation Studies University of California. Berkeley, CA. June 16, 1995 Abstract We propose a heuristic procedure to compute suboptimal routings ( system optimal ) in Dynamic Traffic Networks. The procedure is recursive which greatly simplifies and enhances. implementation and performance respectively. Finally, under mild assumptions on the modeling of congestion, the procedure is shown to compute system optimal routings. A first implementation is provided with computational results. 1. Introduction \\:e plrop)ose a new procedure to solve for suboptimal routings in Dynamic Traffic Networks. By op)timal. we mean "System Optimal"' i.e routings that minimize the total travel time experienced by all platoons. Since link travel times depend upon congestion level, they are time dynamic. which grleatly increases the complexity of the problem. Nonetheless, there is a growing body of work onI this pl)roblem in the literature ( see [1],[2] and [3] ). Various modeling and solution techniques have beel examiined. The critical issue however is tractability. since the goal is to provide with a fast an d reliable way of computing the desired routings. Ill view of this. and with eventual loss of optiInality, we concentrate in a. fast, and if possible suboptilmal pIroceldure. The motivation comes from Kaufman and Smith [4], in which the author iltrod(luce tlie "time consistency" assumption for congestion models on links. This assumptioll. whlichl turlns out to be easily satisfied by maniy models, ensures for a, forward solution of the single plalooll rolting problem. We extend their ideas to the multi-platoon case and show that tlle plroce(llIdue here proposed also solves for systemll optimal routings, when all links in the network satisfy the "time consistency" assumption. 2. Dynamic Programming "Efficient" Heuristic In this section. we provide theoretical basis for the proposed new procedure. To facilitate the analysis, a random traveler approach is taken. This allows to study the system optimality issues, 1

in terms of a single random platoon to be chosen. The rational of the procedure is as follows,: "Efficient" means that one wants to move platoons through the network so they reach intermediate destinations as soon as possible. However, to maintain tractability the procedure only keeps track of efficient routings through intermediate destinations, which raises the possibility of suboptiniality since for some intermediate destinations or macronode it is not necessarily true that the efficient routing provides the best (system-optimal) route to attain the given macronode. One can also view the procedure as an '"aggregative" one(see, for instance, Bean,Birge and Smith[6]) in which we solve the original problem, which in turn can be seen as a shortest path problem, by aggregating to a single macronode, all different possibilities to reach in time a given set of intermediate destinations, we fix the cost to reach that macronode by efficient routing. 2.1 Decision Network Definition We denote m C Z+. the total number of platoons to be considered and (N, A) the traffic network, consisting of a. set of nodes N, and links (i,j) C A with i,j C N. We also denote (O0D), be the origin destination pair associated with platoon p, (1 < p < m) with 0, D e N. Based on the actual network we define a decision network (macro-network) which represents the space of all admissible routing decisions for the m platoons to be routed. A decison network is defined to be a, pair (X, A) where X C Nr1 is the macro-node set and A C A x A is the macro-arc set. Let gi: X - N be the projection for the i-th node in an m-tuple of nodes. Then the set A is required to satisfy the following condition (X,Y) C A = (gi(X),gy(Y)) C A, 1 i < m i.e.. a Ilmacro-arc munst be constituted of arcs in A. A route wr in this decison network is any finite se(quence of Illacro-nodes X, = A(,A-1l... with the property that (Xj. -,Xj+1) C A for all j. Thus 7v is inot a1 route for aly one platoon but rather a routing prescription for the entire network. In other words given 7r the corresponding route for the p-th platoon is gp(YXo)gp(Xk1).... Observe that our assumptions ensure (gI,(Xj ).g,(XA+li)) C A for all j. The symbol |7r| will denote the length of the route 7T aind it will be the number of macro-nodes in the sequence 7. We also use the symbol 1.1 to (leiiote the cardinality of a set. We also indulge in a slight abuse of notation and write Y C Tw if a. Illlacr-llo(le ' lies on a route 7T. 2.2 Travel time function definition loir each ll aindl AX EC, we define the function t( X) to be the arrival time of the p-t\h platoon at. Aun11(1d' t lie roultillg p)rescription 7v. For a route 7 = - XoX... the following is true 1. (.(o) is the trip starting time of platooin p. 2. t(A.+ ) - t7i(X ) + T( x+1 ( (A ),... (Ai), )p,..P ) where p, is the size of platoon p,. ' = gp(Xi) and T(~x x,+1)(.) is the travel time function associated with the directed link (xz,.. +). 3. 0 < rT.y)(.) < oc for all x,y C A. 2.3 The random traveller Let Q ldenote the set of platoons. Then we assume that each platoon is identified with a unique number in the set {1.... m} and define a random variable Z: Q - R with a probability distribution PZ: I - [0, 1] such that 2

1. Pz(Z= p) = p >0, 1 p < m, i.e., each platoon can be picked as the random platoon with positive probability. 2 ll 2. -.%= 1. p=l Based on the random variable Z we define for any route 7r and macro-node X E C r the randoml variable To: R - R with the probability distribution P(Tr,(p) = t (X) =P 2.4 The consistency assumption Let (NX, ') C A and wr, 7r' be two routes to X from some origin node X0. Then we assume the following property. E[Th] < E[Tx ] = E[Ty] < E[Ty']. An immediate consequence of this assumption is that if an optimal route exists it must be an acyclic route. The precise definition of a cyclic route is as below. wr is a cyclic route to a macro-node X if for Tr = X0... XI1R-i there exists i, j with 0 < i < j < ITi - 1 such that Xi = Aj. In the subsequent develpment is will be assumed that Xo denotes the macro-node from which all trips originate. For any node X- X we assume 11x denotes the set of routes from X0 to X. IWe assume that X-o,0 (,A, A) are such that all nodes in A' are reachable from N0, i.e. HIx is non-empty for all X. We also define the projection function Ak(7r) to be the prefix of length k of the route v.,A1 optilal route in a set x i any route T c H such that E[T ] = min E[T]. 7r EI x Proposition 2..1 If an optimal route exists then there also exists an optimal route that is acyclic. Proof: Let there exist 7wr* = X... X-1i_1 E I Ix such that 7r* is cyclic. Then pick i,j with i < j such that X7 = X. Then from T(r,)(.) > 0 we get tV (XN) < tV (Xj*) for all platoons p wvliicli ilplies that E[T.:.] < E[T.-']. (onsider the route 7r' = i(r )\+ 1... i_. Then b) the (ollsisltelcv assumption E[T;,. ] < E[Tx'. ]. Repeated application of the consistency assumption '+1 X+ I gives E[T'._,]J < E[t? -] which implies that 7r' is also an optimal route. \Ve now use this argument for the following inductive construction. Assume that all optimal routes are cyclic. Pick some optimal 7r* E Hx. We know [7* < oc. Set 7o = r* and generate a sequence < 7r,, > in the following manner. Given an optimal ir, = Xo...Xni. _l since it is cyclic, there exists i,j, i < j with Xi = X=j. Thus as before construct 7Rn+1 = Ai(7n)Xjn+.. Xl.n _1. By the prior argument 7r1+l is also optimal and hence by hypothesis it is cyclic. Moreover 17rn+1 < 17,, 3

and the construction can continue. Since 17iol < 0o this implies that for n > |7Tol. 17\il = 0. This is absurd. Thus there exists some optimal route that is acyclic. f In the subsequent development we use 11x- to denote the set of all acyclic routes from X0 to X. Since each route is of finite length and A' is finite, HIx (the set of acyclic routes) is also finite. This together with the fact that r(x,y) < oo implies that for any X C X an optimal route exists. Note that by existence we understand that the minimum exists and is finite. 2.5 Efficient Routes Definition 2..2 For all X E,X such that X is reachable from Xo define II- C IH, to be the set of all 7r-= X... Xlll E 11x such that 1. AXlI2(T- ) CE nlrl p=m 2. E[T] min m+ EpPpTi(,,E)(t1 t,.. P Pm) [ (X,X) ] 7Wle X, + "ep P Then HI, is the set of all effcient routes to the node X. Proposition 2..3 Efficient routes have the following properties. 1. Ie- is non-empty for all X. 2. If T7 = XN...X|ll-l C Ie then Ak(7) E 1, for all k such that 0 < k < 7| - 1. 3. If w. r' E HI then E[T-] = E[Tj. Proof: The proofs of parts (2) and (3) are immediate from the definition of effcient routing. Therefore we prove only the first. part i.e., that the definition of efficient routing is not vacuous. For any X C X' the minimum in the definition of efficient routing is over the set,S'(X) = {X: 7r C H-,, (X', X) E A}. T'Ihus if I- =. 0 tllell eitler S('() is empty or S(X ) is non-empty and no minimum exists over tle set,S'(AY). ('onsider the case S(X) + 0. We show later that this must indeed be true. Since Uk-, C II"x a81(l IIx,l < x. we get |I|,I < 'c. Moreover,l' < i implies that I{X': (X', X) C A}\ < -x. Fron tlIese facts,S'(XN)l < oc. Moreover S(X) non-eImpty implies that there exists N' such that II,/ is noni-enlpty which in turn implies that there exists some 7r C nI', such that E[T-,] < oc. Since Tr(.r)(.) < xc for all (x,y) E A, we get E[T}X] < 00. From this fact and IS(,)l < xc we get tha.t the minimum over S(X) exists and is finite. We now show that S(X) is indeed non-empty. Pick any r = Xo...X1i_1 E 1x-. Obviously IT =- {X } ~ 0. Let nHx 0. Then S(Xi+,) 0 because {7rji+1: T C 1 } C S(X i+). Then by the prior argument 1e+1 0. Bv induction H- W 0. U Theorem 2..4 There exists an optimal route to XD that is also efficient. 4

Proof: Let T7* = X*...AiXi_1 C x1x- be an optimal route. We show by induction that there exists an optimal route (not necessarily 7*) that is also efficient. Induction hypothesis: For all k, 0 < k < 17* -1 there exists an optimal route A = Ak(r)X/.+1....XiA*. i such that Ak()) G HIX. The base case is k = 0. In this case we choose Tr = 7r* itself, since 7r* C 11, = {A0}. Assume w.l.o.g. that the induction hypothesis is true at some k but not at k + 1. Pick l as in the hypothesis. Then Ak+l(kr) IIH. By the definition of efficient routing there exists some k+1 7I' C nI,' ' 5 Ak+l(T) such that k+k E[TX;+] < E[Tk+; ] C'onsider now the route r = 7r'XY+,... A l_. By the consistency assumption E[Th+ ] < E[Tx;+: ] and by applying the consistency assumption repeatedly to the sequence < X^_+ >='1 Se get E[Ta+ E ] < E[T +] for all j. In particular for j = |T*|- 1 we get E[T. *11] < E[T i.-] which implies that *r is an optimal route. Since AX+1(r) = ' C nH+ is also true, * satisfies the k k+1 induction hypothesis for k + 1. By induction the hypothesis is true for all k. In particular if we choose k = I[I*l - 1 then we have an optimal route k such that Alrl_l(fr) C n* = n[I. Thus -r is both an optimal and an efficient route to XD. This proves that within the class of efficient routes there exists an optimal route. Theorem 2..5 Under Strong consistency assumption, all optimal routes are efficient. Proof: WNe show the contrapositive. Assume wr = X-oX.-.. XD-2XD-lXD X He, then there are tw o possibilities ( 1) -\).XD-1 E He11 _ and then by defilition. for any W' C Hfl we have: E[7'-,] > E[T-] lience. it is certainly not optimal. (2) X0 X... XD-1 HID-1I then we go backwards, and again we have two cases: (2.1) N-o.X-D_2 EC IID-2 then let AD-1(7) C n _D, for some 7T', it follows that: E[T{-1 _ > E[T,' ] and we set 7 = AD-1(7T')XD By strong consistency, it follows that E[T > D] > E[TkD] ID

(2.2) Xo...-XD-2 HxD-, we go backwards and again have two posibilities: (2.2.1) XAo.. XD-3 C II-_, then let AD-2(T7) eC H-_ for some 7', it follows that: E[T-D_2] > E[T' _2] and we set 7 = XD-2(7Tr)XD-1XD By strong consistency, it follows that: E[To-D_1] > E[ThDo_] One more iteration yields: E[Tr-D] > E[[T'] (2.2.2) AXo... XD-3 I-3, We go backwards... This inner loop will eventually reach the limiting situation: (2.2...1) X0oX C I1, then let A2(7r') C nI, for some "', it follows that: E[T-2] > E[TF-] and we set 7iI = A2( 7r')X3...XD-1XD By strong consistency, it follows that: E[T73] > E[T-3] Now iterating as above, we have: EI[TD] > E[T-,] (2.2...2) XoX ~i Il n, then let A1(7') C nI-, for some "r', it follows that: E[T77] > E[T-j] and we set 7- Al1(7T)X... _ D-1XD By strong consistency. it follows that E[TJ} > E[Tx-fl Now iterating as above. we hlave E[TD] > E[[TD] \\e fillally conclude that 7r 4 IISk1 6

3. Implementation of the Dynamic Programming "Efficient" Heuristic. In this section, we provide an algorithm to solve for an efficient routing. Weleave behind the random traveler scheme, and in order to fully specify the mechanics of the algorithm. we use nmore notation: 3.1 More Notation * We define Lij(.): Z - Z+to be the dynamic load function for link (i.j) G A, i.e evaluated at some time epoch it yields the total number of vehicles currently on the link. * We let Ii j(.): Z+ - Z+ be the link impedance funtion, i.e for a given number of vehicles in the network it provides the travel time to be experienced if the link is to be entered. The relation between this entities is the following:,j(.) = Ij o L,j(.) (i,j) c A * Let the m-tuple X = (x1, 2,..,n ) be amacronode, as defined in the previous section, where.X 1 N, 1 < p < m, i.e a feasible distribution of platoons across the network, for instance platoon 1 located at node xl, platoon 2 located at node x2 etc... Finally let f(x1, x,.., x,-) be the total trip time experienced for platoons leaving origins Xo = (01, 02., Onz) to intermediate destinations X (x1, x,.., x,,) through an Efficient routing, as defined above. W\e restate the definition of EfficientI routings as follows: 77} f(X) mill {f(X')+ pT(x,,(t.... t..7 p. )} 7r' ICl' s.t (XI X) E A Then. 17- is the argument of the above minimization problem. Now, suppose that the macronode.Y-* = (J..x,...., X*. ) is the attained by the argmin of the definition above, then the time updating goes as follows: t(X ) ) t(X') + T(,.;, )(t (XT)... *,m(X ), Pi...p.P2), 'Io copiil)lete the formulation we clearly l'ave f(OjI.0)... 0.,) = 0 and our problenl is to find /f( )1.L)',... l.),). O()e last set of equations to fully describe the recursion is the way dynamic loadings on links are updated(. 'Tlen. the loadings on the links reaclied( by an efficient routing are updated as follows: L(ipxP)(t) - L(x, r)(t) + p,; tp(X*) < t < tp(X) This last equation simply states the fact that to whatever the number of vehicles in link (xl, xX) C A. I < p < ni, we add the size of the platoon entering the link, namely pp, and since the platoon will take Pt *T( rp.rp)(tj(X*)...m(-X ) P1i... p. prn) time units to traverse the link, this addition 1must be carried out for time periods tp(X*) < tp(X). 7

Figure 1: Network 1 3.2 Example. We try to illustrate the notation with the following example. Consider the network on figure 1. Supp)ose that we have four platoons to consider. each of these leaving a different node to the node located in the "d(liagonal" respectively. Since the order in which we write the macronode m-tuple is arbitrary we set for instance, the order defined by node labels. Then our macronode origin is the four-tuple (01. 0-. 03. 04) = (1. 2 3,4) and the macronode destination is (D1, D, D3, D4) = (4, 3, 2.1). So it follows that our problem is to find f(4,3,2,1) with the boundary condition f(1, 2,3,4)= 0. 'I'lhe first iteration will examine one step macronodes reachables from (O1, 0 03 04) such as (2.1. 1.2). tllat is. the platoon leaving node 1 is routed to node 2, the platoon leaving node 2 is rollte(l to ilode 4. the platoon leaving node 3 is routed to node 1, and the platoon leaving node -I is lrouted to Inode 2. There are then a total of 24 of such macronodes. The first iteration of the I)roce ()( ' re is t iivial. l'o illustrate the updating procedure, let, us assume all platoons consist of one vehicle. all link t.ravel tihmes are constant and equal to 10 time units, and that all platoons leave their origins at tillle zero except for the platoon leaving node 4 at two time units. Then t4 (1,2.3.4)= 2 t (1.'2,3.4) - 0 / = 1.2,3 4 (2.4.1.2)- t4(1.2,:3.4)+ 1 T(4,2)(0)= 12 t1 (2,4.1.2)- t (1.2. 3,4)+.T(1,)(O) = 10.Now. if wNe further assume that to reach (D1. D,, D3, D4) the efficient intermediate destination m-tuple is (2.4. 1.2). the updating is as follows L(1,2)(t) =1 0 < t < 10 L(4,2(t)= 1 2 < t < 12 s

Figure 2: Decision Network for example. 3.3 Implementation The example given in section 1, shows that to solve for efficient routing requires a lot of updating and possibly alot of memory depending upon the size of the problem considered. For instance, the number of macronodes reachable from the origin in that example is exponential on the number of platoons to route. It is required then to avoid unnecessary updating, loadings and times along nonefficient paths, and it is vital to reduce the requirements of memory. For the latter concern, we will then consider one platoon at a, time. i.e a, different decision tree. In our example there will be tlheln only ftw o reachable macronodes from (1. O. 03 04 ). These are (2 2, 3,4) and (3.2,3. 4), since we first consider the platoon leaving node 1. From each of these we then have macronodes (2 1, 3. 4) alnd (2. 4-. 3. 4). andI (3. 1 3. 4) and (3.4, 3, 4), respectively. These are obtained by considering routing choices for the platoon leaving node 2. For the former concern we will use a. heuristic function that wvill lell) ill the forward solving to prune paths that are not efficient. 3.3.1 The Algorithm W\\' briefly explaiil the use of a, heuristic function in solving for the efficient routing. We (lefilne * (: \ x \ - R+ the euclidean geogral)llical distance betNween nodes in the inetwo-rk, e.gn (I(.. 1 1) is the distance betweeii niodes.1 ae(d 1D1. * \\Ve iinow define a heuristic function. that yields a lower bound on a system-optimlal routing total trip time from any macronode to the destination macronode as follows: "') d( xp,Dp) l(...,,, )= EP1 MAX SPEED whlere M4AXSPEED is the maximum speed allowed in the network. NWie now( define the order in which platoons are to be considered, that is, how to expand the decision tree. Since the intention is to use the procedure on real-time and the dynamic routing problem has no fixed horizon, rolling horizon procedures are to be considered. In view of this, we are mainly illterested in system-optimal routing decisions for the first ( in time ) platoons in the network. 9

Hence, the sequence according to which we expand the network is deduced from the times platoons enter the network. The algorithm then is the following: 1. Perform best first search to get a first feasible routing with related total trip time. Initialize a pointer at the macronode origin. 2. From pointer say (x1, x2,.. x,,) on: * Fathom all reachable macronodes (x'1, x...x ) from pointer that satisfy: n. i -pp* T( xP)(tp(X'))+ h(X') > Total Trip Time p=l Expand all dangling macronodes ( if accrued total trip time surpasses the current total trip time, then fathom ). * Since by the previous step we have identified a part of the efficient routing, update all the entities. 1. If pointer is at (D1, D,... D,,) stop. Else, update pointer and go to step 2. On the appendix, we give further detailed information on the computer code developed. 4. Computational Experiment In order to test the validity of the procedure we compared its performance, in a problem with known optimal solution. For that. we use the same network as in Kaufman et al. [4](the same as iln figure 1). where an optimal solution to the system-optimal dynamic routing problem was computed. Thellir model is richer in that they allow for platoon splitting but considerably limited to "small" examples. To test the size of problems that could be solved with the procedure, we enlarged that, nlet\work, into nletwsNorks 2 and 3. All the detailed information is given in the appendix. Comparison w.r.t Optimal Solution Routing time(min) c.p.u(sec) Ratio Network 1 4816.2 22 1.0003 ('omparison w.r.t Random Routings Routing time(min) c.p.u(sec) Ratio Network 1 6930 22 0.71 Network 2 9631.5 26 0.73 Network 3 19498.5 74 0.79 FoI network 1. Kaufman et al. were constrained to solve the problem to a very short time span. In colntrast. our p)rocedure is not constraint by time spans and it could solve until full clearance of t lie nletwork.Best yet, when compared up to a common time span, the "efficient" routing came 0.003%: short of optimality.It required 25 c.p.U seconds to solve it, whereas Kaufman et al. required mlore than 6 c.p.u minutes. For networks 2 and 3, the comparison is made to the average total trip time of a sample of 200 routings picked at random. In the table, the percentage value represents how good it was when compared to this average. It is interesting to note that under increasing congestion the procedure seems to perform better. One possible explanation is that under heavy congestion this assumption is more likely to hold. 10

References [1] Carey,Ml. Optimal time Varying flows on Congested Networks. Operations Research 35 (19 7) 1 58-69 [2] Friesz T.L, J. Luque, R.L.Tobin, and B. Wie. Dynamic Network Traffic Assignment considered as a Continuous Time Optimal Control Problem. Operations Research 37 (1989) 6 893-901 [3] Janson B.N., Dynamic Traffic Assignment for Urban Road Networks. Transportation ResearchC B 25B 2/3 143-161 [4] Kaufman D.E, and R.L. Smith. Fastest Paths in Time Dependent Networks for IVHS Application. IIVHS Journal 1 1 1-11 [5] Kaufman D.E 1 R.L Smith and J. Nonis. A Mixed Integer Linear Programming Model for Dynamic Traffic Assignment.ITS report, University of Michigan. [6] Bean,J.C, Birge, J and Smith R.L. Aggregation in Dynamic Programming. Operations Research 35 (1987) 1 58-69 11

5. Appendix 1 In this section we provide detailed information on the computer implementation of the procedure. Because of time constraints this implementation is not efficient at all, and needs further inmprovement. To avoid confusion, in the following we will assumme that the efficient routing is optimal. so that no distinctions apply. 5.1 General Setting The following definitions are used throughout the code. * MEMORY( Total memory requirement ),MAXs(Number of entries in link impedance functions). MAXPLAT( maximum number of plattons departing from any node ). MAXSPEED ( maximum speed allowed in the network ). HORIZON( number of time periods to be considered). PERIOD( time equivalence of one period unit ). * structnode{} contains all information referenced by nodes. * struct_link{} all information for links. * struct liste_link{} information on network topology. * struct_macronode{} information for macronodes as defined above. The details of each structure contents is carefully explained in the code. As an illustration: struct _lode( int code: /* Code number for node */ int Nbpred; /* total number of sucessors */ int platoon; /* total number of plattons departing */ ilit destination[MlAXPLAT]; /* Array with codes for destinations */ int size[MAXPLAT]; /* Sizes of plattons leaving node */ double departure[MAXPLAT]; /*departure times for plattoons leaving */ double *distance; /* pointer to array of geographical dist. */ struct listelink *predJlink; /* pointer to list of outward links */ }; I'oiilteis to array of each of these structures are thlen defined; e.g. *tabnode for the array of struct_node{ }. *tablink a(nl *tab-mnode. While the size of tlie niode and link arrays are fixed( we will denote NbN. total Ilunber of nodes and NbL. total inulIber of links) the size of the macronode array is choseni to be the constant MEMORY as defille above. This is due to the fact that we do not know ill advance how much pruning will be necessary to find the efficient routing. However, we consider that this step can be improved by using the c-command realloc() in order to ask for just about the memory requirements, as we prune the macro-network. 12

5.2 Input Data All the data that defines the problem setting must be provide through two input files, namely;node_data and linkdata. We give instances of these files, in the exemple given in the paper. Nodes and links are listed in increasing code number. The codes are arbitrarily chosen. For node_data: 4 /* Total number of nodes */ 1 2 1 /* node code-number of sucessors-number of platoons departing*/ 3 /* destination(s) code(s) for platoons departing */ 1 /* Total number of vehicles in platoon(s)*/ 0 /* platoon(s) departure(s) time(s) */ 22 /* code sucessor node-code link joining them */ 3 7 /* code sucessor node-code link joining them */ 0 15 5 30 /* Geographical distance between this node and others*/ 2 21 /* node code-number of sucessors-number of platoons departing */ 4 /* destinations for platoons departing */ /*... iterate */ For link_data S8 / * Total number of links */ 1 0 2 /* link code-current link loading-freeflow travel time */ 0 0 101.3 160.7 222.2 /* link impedance function (defined for MAXs) */ 2 0 1.768 /* link code-current link loading-freeflow travel time */ 0 24.2 55.1 85.2 116.8 /* link impedance function (defined for MAXs) */ /*... iterate */ 5.3 Subroutines \\:e give a list and a brief explanation of subroutines used. * lecturenode() and lecturelink() read and fill with the input data the array of structlures p)oillt e(l y *tabnodeand*tablink respectively. verification() prints to the stalldard outpullt thie contents of these structures to check for consistency. * initstructures() utilizes the informlation rnow pointed by *tabnodeand*tablink to ade(lquately initialize pointers between entries of the array of structures( that is, the network tot)ology ). The subroulltine init_tab mnode() initializes the array of structures pointed by *tab_mnode( tle inacronetwork). It is here that whten demanding too much memory, the execution can be aborted. There is a. special message for these error. * graphsearch(root) performs a best first depth search on the macronetwork from the Ilacroiod(e indexed by root ill the imacroniode array( pointed by tabmnode). The integer variable counter serves to index free space in *tab mnode to write on as it goes through a nmacropath. Since the first entry on *tab mnode (i.e tabmnode[O]) is the macro-origin, Root takes on the initial value of 0, and counter is set initially to be one. Since the procedure graph-search(root) is to be used extensively when pruning, the real numbers valuel and value2 denote respectively, the total routing time through the macronode reached by 13

the procedure and the best total routing time found so far. Then, when pruning one can stop, the depth search when valuel exceeds value2 or adequately update. * check_optimality() is the pruning procedure. It traverses the macronetwork (i.e *tabmnode). fixing optimal routing decisions from the macro-origin and on, by calling repeatedly graphsearch(root). In this case, the integer variable counter2, index the last optimal routing decision on the macronetwork. The procedure returns 1 if an optimal routing has been identified. With these procedures then the core of the code is: optimality = 0; counter = 1: root = 0; counter2 = 0; graph search(root); value2 = valuel1 for(i=0;optiInality!= l;i++) { optimality = check optimality(); 5.4 Output 5.4 Output /* setting initial values for basic variables */ /* First Depth Search for a feasible routing */ /* First Routing total cost is stored in value2 */ /* pruning sequentially to optimality */ TIlle )lpruning procedlure check-optimality marks as it goes through the macronodes reached by the efficient routing (i.e it modifies tabmnode[].optimality). So the print solution() procedure goes thlroughll the macronetwork reconstructing the efficient path. We recompute the travel times accruedl along the path have more information on its qualitative features.(Otherwise, one simply lias the optimlal routing cost stored in value2). 14

6. Appendix 2 In this appendix we provide all the information on the networks considered. 6.1 Links WNe use four different types of links, to be denoted A, B. C, D respectively. The following table gives the link impedance funtion for each link type(it is defined in 1.5 minute time units). I Link Impedance Function I Number of Vehicles Time Units s 0 s = 1 s = 2 s = 3 s = 4 freeflow time Type A 0 0 101.3 160.7 222.2 2 Type B 0 24.2 55.1 85.2 116.8 1.768 Type C 0 0 118.1 198.7 279.5 2.348 Type D 0 22.9 54.3 84.3 115.8 1.808 6.2 Network 1 This is the same network solved in Kaufman et al.[5].It is a four node network with sixty platoons departing along six time periods.In figure 3, the different codes assigned to links and nodes are shown.For further information, the input files are annexed and can be interpreted according to the guidelines given in appendix 1. We now list links codes according to types: * Type A:1,2 * Type B:3. * Type C:4.8 * Type D:5.6 6.3 Network 2 'Thl'is is ten nlode network with fifty platoons departing along one time period.In figure 4,. the different co(les assigned to links and nodes are showin.For furtler information. the input files are annexed a1l(1 (can b)e interpreted according to the guidelines given in appendix 1. We now list links codes accordilng to types: * Type A:1.2.9, 17,22,24 * Type B:3. 7. 13,1923,26 * Type C:4.8. 10,11. 12. 18 * Type D:5.6. 14, 15,'20,21, 16.25 15

6.4 Network 3 This is twelve node network with eighty four platoons departing along one time period.In figure 5. the different codes assigned to links and nodes are shown.For further information, the input files are annexed and can be interpreted according to the guidelines given in appendix 1. We now list links codes according to types: ~ Type A:1,2,9,17,22,24,27,28,29,30,31,32,33,34,35,36 * Type B:3,7, 13,19, 23,26 * Type C:4,, 10, 11,12, 18 * Type D:5,6,14,15,20,21, 16,25 16

Figure 3: Network 1. 17

24 Figure 4: Network 2. 18

10 / \ 25 5 jc 6 )<? 9 12 21 17\\ 9 18\\1 1 26\\ 23 2 27 1 2 11 1 28 7 3 4 8 29 30 6 31 3L 7 4 -C 12 (5 32 19\\ 1 3 20 15 22 24 (14, \ 33 7 < 8 ) 1 3 10 Y16 \ 34 Figure 5: Network 3. 19