U,,,Ce. K.:t k / K^ /' I il LINK TRAVEL TIME PREDICTION TECHNIQUES FOR CONVERGENT ITERATIVE ANTICIPATORY ROUTE GUIDANCE METHODS KARL E. WUNDERLICH Mitretek Systems, Inc. Washington, DC 20024 DAVID E. KAUFMAN University of Massachausetts Amherst, MA 01003 ROBERT L. SMITH Department of Industrial and Operations engineering University of Michigan, Ann Arbor, MI 48109, USA Technical Report 97-17 December 2, 1997.7^, ' { J) led t.e a/- /' C I'-,5Wt K" * / Kevpjl~y~~p ll -!::-M (

LINK TRAVEL TIME PREDICTION TECHNIQUES FOR CONVERGENT ITERATIVE ANTICIPATORY ROUTE GUIDANCE METHODS Karl E. Wunderlich Mitretek Systems, Inc. 600 Maryland Avenue, SW, Suite 755 Washington, DC 20024 Tel: (202) 488-5707 Fax: (202) 863-2988 kwunderl @mitretek.org David E. Kaufman University of Massachusetts Marston Hall Amherst, MA 01003-52220 Tel: (413) 545-1615 Fax: (413) 545-0724 kaufman@sml9.ecs.umass.edu Robert L. Smith University of Michigan Department of Industrial and Operations Engineering Ann Arbor, MI 48109 Tel: (313) 763-2060 Fax: (313) 764-3451 Abstract Anticipatory route guidance methods have been demonstrated to provide a higher level of travel time savings than non-predictive methods, particularly as the percentage of vehicles receiving route guidance (market penetration) increases. In application, however, both predictive and non-predictive methods reach market penetration thresholds where system performance begins to deteriorate. In addition, iterative simulation-assignment methods are not always convergent. For the Simulation of Anticipatory Network Vehicle Traffic (SAVaNT) iterative simulation-assignment method, it is demonstrated here that both market penetration threshold effects and non-convergence can be directly related to the manner in which link time profiles are constructed. A method is presented which ensures that SAVaNT will terminate with a convergent solution through incremental adjustments in the accuracy of link time prediction. In addition, since this incrementalimprovement approach identifies the most accurate link time forecasts SAVaNT can produce, performance of guided vehicles are significantly enhanced, particularly at higher market penetration levels.

Wunderlich, Kaufman, and Smith LINK TRAVEL TIME PREDICTION TECHNIQUES FOR CONVERGENT ITERATIVE ANTICIPATORY ROUTE GUIDANCE METHODS 1. Introduction. Iterative simulation-assignment methods have been increasingly employed in transportation-related applications. Examples include Jayakrishnan and Mahmassani (1991) and Rillet and Van Aerde (1991). The CONTRAM/ROGUS traffic simulation model contains an iterative method for the identification of equilibrium assignment (TRL publications, 1993). Kaufman, Smith and Wunderlich (1991) demonstrated that the SAVaNT simulation-assignment method could be employed to provide dynamic traffic assignment which anticipates future network congestion. When the number of vehicles on the network receiving route guidance is small, then the effect of route guided vehicles on overall network congestion conditions is negligible. In this case, we may simply route them according to dynamic fastest-paths using a modified version of Dijkstra's algorithm (Kaufman and Smith, 1993). However, as an ever larger share of vehicles on the network receive route guidance, the guided vehicles may cause unanticipated congestion on the network and thus render the route-guidance sub-optimal. SAVaNT uses an assignment module and a traffic simulation together in a feedback loop in an attempt to resolve this interdependence between predicted travel times and route guidance. Anticipatory route guidance can be defined as paths calculated from a set of predicted future link travel times, which when disseminated to drivers cause the same set of predicted link travel times to be realized by vehicles in the network. Thus the paths distributed as route guidance were based on a correct assumption about future congestion conditions on the network, corresponding to a user-optimal equilibrium condition (Kaufman, Smith and Wunderlich, 1992). Chen and Underwood (1991) provide a detailed general overview of anticipatory route guidance and its implementation. Wunderlich (1992, 1993) and others 1

Wunderlich, Kaufman, and Smith (Kaufman et al, 1991) demonstrated that anticipatory route guidance can be employed effectively in large-scale application, particularly as the percentage of vehicles receiving route guidance (market penetration) increases. Predictive route guidance was often, but not always, superior to non-predictive route guidance methods. Dynamic Complete Routing Policy_ Simulation Router A Link Travel Link Travel Time Profile Link Travel t C Time Profile C ixed Stop NO Point? YES Figure 1. The SAVaNT iterative method. The SAVaNT concept is illustrated in Figure 1. Combining a time-dependent fastest-path calculation, R, with a traffic simulation, A, in an iterative manner, we can identify a routing policy, 7r, as a "fixed point" if in consecutive iterations, the dynamic link travel time profiles, C, are identical, i.e., a stable set of predicted dynamic link travel times have been identified. Because we restrict our attention in this paper to "all-or-nothing" policies (i.e., giving the same route to all vehicles having common location and destination at a given time), the set of possible policies is finite. Thus, if execution of SAVaNT does not result in a fixed point, the result must be the generation of a repeating sequence of policies, r, tr2, ttl, 7r2, 7t1, 72, L, rather than convergence to a fixed point. We call this situation crcling. For an investigation of this issue under multipath (as opposed to all-or-nothing) routing, see Kaufman, Smith and Wunderlich (1995). SAVaNT uses a version of the INTEGRATION traffic simulation (Van Aerde et al, 1989) for link-time prediction, INTEGRATION-UM. The INTEGRATION model was originally 2

Wunderlich, Kaufman, and Smith developed by Michel Van Aerde and modified by researchers at the University of Michigan. INTEGRATION-UM retains the basic scope and modeling approach of the model: a strongly deterministic mesoscopic approach employing macroscopic travel-time and flow relationships and microscopic individual vehicle control and link queuing. Critically, INTEGRATION allows the user to vary the fraction of vehicles on the network receiving route guidance. Non-equipped (background) vehicles are routed according to a static fastest-path route. 2. Accuracy of Predicted Link Travel Times in SAVaNT. As observed in Kaufman et al (1991), there is an inherent inaccuracy introduced into SAVaNT by a difference in the way the simulation produces predicted time-dependent travel times and interpretation of that data by the routing module. Note that we impose a discrete-time lattice over the solution horizon, H, that we are predicting link travel times over. Let At be the number of seconds in each time slice, and let t;t = 1,2K H correspond the tth time slice in the horizon. Let cl(t) be defined as the predicted link travel time for link 1 during time-slice t. c, (t) c (t) c (t) c, (t) At Simulation Clock time slice t (seconds) Figure 2. Link Departures Reporting Link Travel times during Time Slice t Consider the problem of constructing a link travel time profile C = {c,(t): V 1, t}. As shown in Figure 2, the simulation reports experienced link travel times when vehicles finish traversing links. Let c'(t) represent the travel time reported by the vehicle making 3

Wunderlich, Kaufman, and Smith the i th departure from link 1 during time-slice t. Let zf(t) be the simulation clock time when c'(t) is reported. In the version of SAVaNT employed by Kaufman et al (1991), cl(t) is updated each time a departure occurs according to an exponential smoothing function, c(t) = acl(t)+ (1 - a)c(t), where 0 < a < 1. Kaufman et al set a = 0.4. Note that cl(t) could be computed through a variety of methods, and that the exponential smoothing method is just one of these possibilities. For example, cl(t) could be determined through averaging the departures reported in the time-slice, or simply be set to the last observed value. c;(t) T, (t)- c, (t) W (t) Simulation Clock time slicet (seconds) Figure 3. Link Departures Accurately Predict Past Travel Times The dynamic router interprets cl(t) as the expected average travel time required to traverse link 1 for vehicles which begin travel on link 1 during time slice t. But the value of cl(t) is computed based on vehicle reports made by vehicles finishing travel on the link during time slice t. As illustrated in Figure 3, when a link departure reports a travel time for a link, it is more precisely giving an estimate of vehicle travel time which begins earlier, at zr (t) - c (t). Note that reducing the length of each time slice At does not correct for this particular kind of error. Thus our estimating procedure is inherently inaccurate, but as we will see, this inaccuracy is a crucial component in forcing convergence of the SAVaNT iterative process. 3. Benefit Reduction Related to Inaccuracy in Link Time Prediction. 4

Wunderlich, Kaufman, and Smith As stated above, routing policies are generated in SAVaNT by interpreting cl(t) as the expected average travel time for vehicles beginning travel on link 1 during time slice t. This inaccuracy has the effect of causing a lag in the feedback control of vehicles under route guidance. For example, if travel time is dynamically rising on a particular path, there will be a lag in accurate reporting of that change in that path time equal to the maximum individual link travel time in the path. Consider the situation where, based on perfect information in the system, a path currently identified by the route as optimal becomes congested and an alternative path becomes more attractive. In the next iteration, then, vehicles currently on this path cannot be re-directed to the alternate path until the router sees reports of travel times in the constructed travel time profiles. These profiles contain the time lag associated with link-departure travel time estimates, and thus the router misdirects vehicles for the duration of that time lag. Vehicles on our initially optimal path will be erroneously routed on what will be experienced as a slower path but which appears from the predicted travel time profile as the fastest path. This inaccuracy cannot be corrected in an future iteration of SAVaNT, since the travel time profile generated on all paths will be constructed with identical lag time. Thus, the inaccuracy is carried forward from iteration to iteration, and cannot be corrected within the current SAVaNT concept. Hence, a fixed point in SAVaNT corresponds to a routing policy which is consistent with the reproduced travel time profile, a travel time profile which necessarily contains some inaccurate information. Thus the routings identified by SAVaNT are the minimum travel time paths with respect to a predicted travel time profile, but not necessarily consistent with experienced travel time. 5

Wunderlich, Kaufman, and Smith This inaccuracy can be compared to the error encountered in routing vehicles in a nonpredictive manner. These methods provide a shortest-path routing policy based on the assumption that currently reported conditions persist indefinitely. The policies generated are consistent with the expected (static) travel time profile, but not consistent with experienced travel time. SAVaNT Travel Time Reduction in Troy Mid-Day Loading Scheme: 16,000 vehicles 9.9 - e 9.7-. 9.5 -E 9.3 -E i 9.1 > 8.9 -L ^ 8.7 -8.5 - I 0 10 20 30 40 Percent Anticipatory I ~ 50 60 Vehicles 70 80 background guided average Figure 4. Link Prediction Error and Benefits of Route Guidance The result of inaccurate link travel time prediction is a reduction in benefits to both the traffic system as a whole and to the individuals on the network route guidance. Figure 4 illustrates the benefits seen in a 500-link, 200-node network of Troy, Michigan. Note that at near 50 percent guided vehicles on the network, the performance of anticipatory vehicles drops to the same level as the background (unguided) vehicles. At 80 percent, the guided vehicles have longer trips on average than the background vehicles. If SAVaNT were provided with accurate link times, then this situation would never occur. As noted in 6

Wunderlich, Kaufman, and Smith Kaufman et al (1991), an earlier version of SAVaNT was configured to correct for this inaccuracy, but when this was done, SAVaNT always terminated with the construction of a cycle, rather than a fixed point. We will discuss the nature of this phenomenon in more detail in section 5. 4. Improved Predictive Fixed Point Solutions SAVaNT can be constructed to provide accurate predictive link times. The link travel time estimated by link departures which occur in time slice t can be "backdated" to the time at which travel on the link began, namely CT(t) - cl(t). There may be several link travel time estimates for each time slice, so these values are averaged together to come up with a value for cI(t') where rz(t) - cl(t) is contained in time slice t'. These values of link travel time can be used in SAVaNT in the place of values identified above in Section 2. However, such an implementation invariably results with SAVaNT terminating in a cycle, even for market penetration levels which have fixed points for SAVaNT implemented without backdating. The dilemma of SAVaNT can be summarized by the following: the inaccurate link time forecasts cause the method to identify sub-optimal solutions for anticipatory route guidance, yet the inaccuracy in link time forecasting seems to provide SAVaNT with a measure of stability in identifying fixed points. One goal for SAVaNT might be to reduce the inaccuracy to the smallest amount without incurring a cycle to occur. This would allow for the maximum amount of benefit to accrue to both the system and the guided vehicles without cycling. Define 6, 0 < < 1, as the fractional amount of backdating implemented in SAVaNT. As illustrated in Figure 5, as 6 increases, the accuracy of the link time prediction scheme increases. When 3 = 0, SAVaNT is configured as in Kaufman et al (1991). When 3 = 1, 7

Wunderlich, Kaufman, and Smith SAVaNT is configured as divergent approach described in Kaufman et al (1991). To test the behavior of SAVaNT under additional values of 3, a corridor subnetwork (TroyCor) of the Troy, Michigan network was constructed (20 links, 10 nodes). This network corresponds to a pair of parallel, six-mile long arterial segments of John R and Dequindre Roads. Vehicles were routed along the southbound section of the corridor, which is signalized and it timed for a greenwave progression based on free-flow link travel times. Accuracy in link-time prediction is especially important in signalized corridors since the link travel time experienced can be strongly influenced by the coordination of node arrival and the signal phasing., (t -c;(t ), (t)I- c,(t) //A I I (t) I { Tl( ISimulation Clock (seconds) time slice t Figure 5. Fractional Backdating in SAVaNT An experiment was performed on the TroyCor network using 50 percent guided and 50 percent unguided vehicles. The unguided vehicles were assumed to take the fastest freeflow path, that is, the fastest expected path when the network is empty of vehicles. Over 2000 vehicles were introduced onto the network over a 30 minute period. The network (Figure 8) was initially empty of vehicles. Travel times were measured for all the vehicles generated in the 30 minute period in ten second time slices. An initial travel time forecast corresponding to a 100 percent unguided vehicle loading was used to seed each run of the test. Under no backdating, 6 = 0, a fixed point was identified using SAVaNT. The value of 6 was then incremented by 0.1 to 0.7 until a cycle appeared at 0.8. A cycle also results when 8

Wunderlich, Kaufman, and Smith 6 = 0. 75. The results are graphically illustrated in Figure 6. In comparison with the initial SAVaNT fixed point, a 12 percent improvement in benefits was obtained for the system as a whole, and travel time for guided vehicles improved by 6 percent. Note that the progression was not monotonic, since average aggregate travel time is a system-optimal measure of effectiveness and each fixed point corresponds to a user-optimal routing policy. An average aggregate travel time of 10.30 minutes was observed for guided vehicles and 10.29 for unguided vehicles when 8 = 0.7. The system travel time was also 10.30 minutes. Accuracy in Link Time Prediction and Experienced Travel Times 1 3 For delta = 0.7:,,, 13-. X> 12 5 12% improvement in system travel time (5 125;. ' 12 6% improvement for guided vehicles 11 112 I' E 11.5 ~. 10.5 ei 10 9.5 cycle appears at delta = 0.75, 9 I I5 I- I- I - i -I 0 0 0 0 0 0 0 0 o O O 00 0 0 V j o co ) Ln o ( Percent Backdating Applied to Link Travel Time Estimates X guided -- unguided ~ system Figure 6. Benefits of Improved Link Time Prediction in SAVaNT The number of iterations to convergence trended upwards with an increasing level of accuracy in the link time prediction method (Table 4.1). SAVaNT appears to require fewer iterations to identify routing policies that remain relatively stable from time-slice to timeslice, and more iterations when identifying highly time-variant policies. The increased link 9

Wunderlich, Kaufman, and Smith time accuracy provides the router with the ability to implement new routing policies with a shorter time-lag on control, and for the Troy Corridor model, translates this into more frequent switching between identified fastest predicted paths. Benchmark values for travel time in the network under alternative routing schemes were also generated. A network of 100 percent unguided (fastest free-flow path) vehicles averaged 18.15 minutes to traverse the corridor. A test on the TroyCor network using 50 percent unguided and 50 percent non-predictive dynamic routing resulted in an average travel time of 10.99 minutes for the guided vehicles, 11.23 for the unguided vehicles, and 11.11 for the system as a whole. Note that the presence of signalization in TroyCor penalizes less accurate predictive methods vis a vis non-predictive methods. When 6 = 0, the SAVaNT returns a system travel time of 11.52 minutes, compared with 11.11 for test case using non-predictive dynamic route guidance, an increase of 3.7 percent. However, when 8 = 0. 7 then system travel time under SAVaNT is 7.3 percent faster than the nonpredictive method. Table 4.1 Number of Iterations to Convergence Under Varying Predictive Accuracy 6 Iterations to Convergence 0.0 14 0.1 16 0.2 15 0.3 20 0.4 22 0.5 19 0.6 27 0.7 36 0.8+ CYCLE 5. Resolution of Cycling Through Delayed Link-Time Estimation The results described in section 4 suggest a method which is initialized with a convergent solution in SAVaNT and then seeks the maximum value of 3 where a convergent solution may still be obtained. From another perspective, we might consider the complement of that 10

Wunderlich, Kaufman, and Smith situation, namely when SAVaNT has terminated with a cycle, rather than a fixed point. We might then incrementally decrease the value of 8 until a convergent solution is obtained. As indicated in Figure 7, 8 is not necessarily bounded below at 8 =0. The effects of decreasing 8 are qualitatively the same whether 8 is positive or negative. The first effect is that link travel times generated are inherently less accurate. The second effect is that SAVaNT is made more likely to find a convergent solution. il (t) - Cli (t) i (t)i *' ~^(0,g, x[(t)- 6 c, (t) i I/!( Iz, ~(t) Simulation Clock time slice t (seconds) Figure 7. Induced Reporting Delay, 3 < 0 For example, SAVaNT does not find a fixed point with 8 = 0 in the Troy corridor model when 80 percent of the traffic on the network are guided vehicles. However, when 6 = -0.2, a fixed point is found resulting in a system travel time of 10.33 minutes. In general, the higher the fraction of guided vehicles traversing the network, the smaller the value of 6 required to force convergence in SAVaNT. If we consider the effect of travel time profiles in a sequence of iterations in SAVaNT, the effect of a changing the value of 6 becomes more clear. Consider the simple case where 3 = 1.0 and we have a single guided vehicle traversing the network. Let P1 be the fastest volume-independent path in the simulation, with predicted freeflow travel time C(P,). In the simulation, a guided vehicle traverses the set of links 4: 1 P1, and reports link travel times which are higher than freeflow times (because of the presence of traffic). Let the 11

Wunderlich, Kaufman, and Smith difference between these higher reported travel times and the predicted travel time be AC(P1). Assume there exists some alternative path, P2, which contains at least one link not contained in Lo. If C(P1) < C(P2) and C(P2) < C(P1) + AC(PI), then a cycle must develop. When 8 < 1.0, however, the single vehicle in the example above cannot impact its own route guidance decision in following iterations. But we may have many link departures within a time slice, so the marginal cost impact of our routing decision is also dependent on the number of vehicles getting the same next-link information. In this case, for virtually any 8, the marginal cost of a particular assignment can potentially yield a cycle. When 6 decreases, the marginal cost effects are pushed downstream in time, a subset of the vehicle population are routed onto paths thought to be "optimal" given the constructed link travel time profiles. These vehicles remain on the same paths in SAVaNT if the travel time profiles remain consistent, which allows SAVaNT to select paths for the remaining group of vehicles which have marginally smaller impact on the network. Figure 8. The Troy Corridor Network: Subset of the Troy Model 12

Wunderlich, Kaufman, and Smith Within SAVaNT, for example, if route guidance for all vehicles remains constant for two consecutive iterations through some intermediate period h, where h < H, our solution horizon, then that partial routing policy will remain stable even if SAVaNT fails to converge. In the case of a fixed point, stable routing forecasts are constructed with monotonically increasing values of h until finally h = H. 6. A Convergent Approach for SAVaNT Consider H, our solution horizon. If we set 8 to be strongly negative (j8\ large), then the effect in SAVaNT would be to push the delay downstream in time past the solution horizon. Thus, the simulated traffic would have no effect on the travel time forecasts generated in SAVaNT. SAVaNT would only construct travel time forecasts based on the default link time travel times (free flow) and converge immediately. A more precise proof of this claim is stated below. Claim: There exists some finite value of 6 such that SAVaNT must converge. Pf. Assume H finite. Let L be the set of links in any finite network. Under the non-restrictive assumption that c, (t) > 0 V 1 L, t = 1,2,L H, there exists some finite,l(t) s:,(t) c,(t)<-H V 1 L, t = 1,2,L H. Let 6 < 81(t) V 1,t. Then 6 is finite since every 38(t) is finite. If we set (1(t) < 6 V le L,t = 1,2,L H, the simulation module in SAVaNT produces link travel time estimates c1(t) = co V e EL, t = 1,2,L H, where co is the free-flow link travel time of link 1. In any two consecutive iterations of SAVaNT, the travel time profiles C,=C, =cOV 1L, t =1,2,L H. Since C,=C,, SAVaNT has converged to a fixed point. 13

Wunderlich, Kaufman, and Smith We may thus force convergence in SAVaNT by choosing a sufficiently small value of 8. However, we seek a value of 3 as close to 1.0 as possible to realize the highest link time prediction accuracy and the resulting improvement in travel time savings. The extreme case 8 = 3 corresponds to a prediction of free-flow travel times across the network for all time slices, the least accurate depiction of a network which has nonzero travel demand. A solution procedure exploiting a variable- 8 accuracy method is outlined in Algorithm 6.1. Algorithm 6.1 SAVaNT-CNV Method Step 1. Set 8 = 0 and i = 1, and choose some small increment value, a. Step 2. Run SAVaNT, generating result Si. Step 3a. If Si is a cycle, set 8 = 8 - oa. Goto Step 4. Step 3b. If Si is a fixed point, set 8 = 6 + a. Goto Step 4. Step 4. If Si, Si_ both cycles or both fixed points, set i = i + 1. Goto Step 2. Otherwise, STOP. This approach was tested on the Troy corridor model with a = 0.05. Note that we could have started from 8 = 1.00and monotonically decreased S. These approaches are equivalent if there exists 8* such that SAVaNT cycles for all 8 > 8* and converges for all 8 < 6*. Such a condition is difficult to prove, but is empirically borne out in TroyCor. Practically, very small values of 6 do not appear necessary for convergence. Convergence thresholds for SAVaNT-CNV are presented in Table 6.1. Table 6.1 Convergence of SAVaNT-CNV Maximum Convergent Pct. Guided Vehicles Value of 3 10% 0.90 20% 0.70 30% 0.70 40% 0.80 50% 0.70 60% 0.05 70% -0.10 80% -0.20 90% -0.20 100% 0.05 For TroyCor, S is observed to be roughly -50.0. However, SAVaNT obtained stable results with 6 as high as 0.9, and no worse than -0.2, operating at forecast accuracy far 14

Wunderlich, Kaufman, and Smith superior to the worst case 6. When 3 < 6, the percentage of links reported at free-flow over the entire horizon is 100%, whereas for 8 in the stable range identified for TroyCor, there were no links reported at free-flow over the entire horizon. Fixed points were identified at all market penetration levels. Comparable evaluations were made of both non-predictive route guidance and the version of SAVaNT employed by Kaufman et al (1991). As in the experiment from Section 4, link times are assumed to be distributed every 10 seconds over a solution horizon of 30 minutes. Guided Vehicle Travel Time Troy Corridor Model 12 C) E '~ D 10 >0 &r 9 ~ E 8 SAVaNT cycled at 70%, 80, 90% 7 6 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% Percentage Guided Vehicles - - NP - SAVaNT *-SAVaNT-CNV Figure 9. Guided Vehicle Travel Time Performance solutions than either non-predictive route guidance or the version of SAVaNT employed by Kaufman et al. Figure 9 graphically illustrates the benefit of improved link time prediction accuracy in SAVaNT. Under guidance from SAVaNT-CNV, equipped vehicles experienced up to 9% percent faster travel times when non-predictive methods were employed. SAVaNT-CNV also significantly outperformed the older version of SAVaNT. 15

Wunderlich, Kaufman, and Smith Travel time savings were most pronounced as the percentage of guided vehicles ranged between 40-90%. In all market penetration levels, SAVaNT-CNV returned faster travel times for guided vehicles than either of the two methods. System Travel Time Troy Corridor Model ~; 19 > 18;.,, 17 * ' 16 6 SAVaNT cycled at 70%, 80%, 90% - 5 W E 141 X 13 E 1 2 10 9 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% Percent Guided Vehicles --- NP -- SAVaNT -- SAVaNT-CNV Figure 10. System Travel Time Performance As indicated from Figure 10, SAVaNT-CNV also proved most effective in reducing system travel time. Solutions for SAVaNT-CNV provided 1-9% improvements over the solutions obtained by either of the other two competing methods. Note that the travel time reduction for SAVaNT-CNV is not monotonically decreasing both because the forecasts are not perfectly accurate, and because individual vehicles choose routes according to a useroptimal criterion rather than a system-optimal criterion. Table 6.2 summarizes the results obtained for each approach. 16

Wunderlich, Kaufman, and Smith Table 6.2 Summary of Travel Times Obtained in Troy Corridor Model Aggregate Ave. Travel Time Improvement vs. NP Mkt. Pen. NP SAVaNT SAVaNT-CNV SAVaNT SAVaNT-CNV 0% 18.15 18.15 18.15 0.00% 0.00% 10% 15.36 15.28 14.95 0.52% 2.67% 20% 13.25 13.45 12.72 -1.51% 4.00% 30% 11.71 12.48 11.28 -6.58% 3.67% 40% 11.04 11.99 10.44 -8.61% 5.43% 50% 11.11 11.72 10.30 -5.49% 7.29% 60% 11.13 11.51 11.01 -3.41% 1.08% 70% 11.16 CYCLE 10.74 NA 3.76% 80% 11.27 CYCLE 10.33 NA 8.34% 90% 11.53 CYCLE 11.06 NA 4.08% 100% 11.70 11.91 11.58 -1.79% 1.03% Guided Vehicle Travel Time Improvement vs. NP Mkt. Pen. NP SAVaNT SAVaNT-CNV SAVaNT SAVaNT-CNV 10% 6.75 6.70 6.68 0.74% 1.04% 20% 7.72 7.95 7.63 -2.98% 1.17% 30% 9.02 9.13 9.02 -1.22% 0.00% 40% 10.40 10.06 9.99 3.27% 3.94% 50% 10.99 10.95 10.3 0.36% 6.28% 60% 11.23 11.27 10.95 -0.36% 2.49% 70% 11.28 CYCLE 10.62 NA 5.85% 80% 11.38 CYCLE 10.46 NA 8.08% 90% 11.57 CYCLE 11.15 NA 3.63% 100% 11.70 11.91 11.58 -1.79% 1.03% 7. Conclusions and Future Work This work indicates that accuracy in link time prediction can have significant impact in improving travel time benefits for vehicles receiving anticipatory route guidance, as well as for the system as a whole. SAVaNT may be configured to produce the most accurate link time prediction possible before the onset of cycling, which even in the most difficult scenarios for predictive logic, is an improvement over non-predictive route guidance. In addition, the variable link-time prediction method may be employed in any iterative simulation-assignment routing approach -- it is not unique to the SAVaNT implementation. 17

Wunderlich, Kaufman, and Smith SAVaNT may require additional iterations to find fixed points given a more accurate method of link time prediction, however. The SAVaNT-CNV method can require the identification of several fixed points or cycles, since we are applying SAVaNT with different values of 8. In practice, this can be done in parallel, so SAVaNT-CNV can be implemented in the same real-time application as SAVaNT. Several issues remain to be addressed. Currently, variable link time prediction accuracy is being tested with SAVaNT on the large scale Troy, Michigan test network (Wunderlich and Smith 1992, 1993). A closer examination of benefits to the user and the system are being explored in relation to a wider choice of background routing algorithms. Another potential research area is the effect of initial point selection. The selection of a initial point which is "close" to the best solution will drastically speed the convergence of SAVaNT. However, this must be weighed against the possibility that many fixed point solutions may exist and that the selection of a fixed point may be critical in determining which of those solutions is identified. Finally, the impact of having S vary with time and location in the network has not yet been addressed. It may be fixed points may be identified wherein link travel time prediction is more accurate on some links and less accurate on others, yielding additional improvements in system average and guided vehicle travel time. REFERENCES Chen, K., and Underwood, S., (1991) "Research on Anticipatory Route Guidance", SAE Vehicle Navigation and Information Systems Conference Proceedings, P-253, pp.427-439. Jayakrishnan, R. and Mahmassani, H. (1991) "A Dynamic Modeling Framework of RealTime Route Guidance Systems in General Urban Traffic Networks", presented at Transportation Technologies Applications Conference, Minneapolis, Minnesota. 18

Wunderlich, Kaufman, and Smith Kaufman, D.E., Smith, R.L., and Wunderlich, K.E. (1995) "User-Equilibrium Properties of Fixed Points in Iterative Dynamic Routing/Assignment Methods", accepted for publication in Transportation Research. Part C. Kaufman, D.E. and Smith, R.L. (1993) "Fastest Paths in Time-Dependent Networks For Intelligent Vehicle-Highway Systems Application", IVHS Journal, Vol. 1(1), pp.1 -11. Kaufman, D.E., Smith, R.L, and Wunderlich, K.E. (1991) "An Iterative Routing/Assignment Method for Anticipatory Real-Time Route Guidance", SAE Vehicle Navigation and Information Systems Conference Proceedings, P-253, 701 -708. Rillet, L. and Van Aerde, M. (1991) "Routing Based on Anticipated Travel Times", presented at Transportation Technologies Applications Conference, Minneapolis, Minnesota. Van Aerde, M., Voss, J., and McKinnon, G. (1989) Integration Simulation Model User's Guide, Version 1.1. Department of Civil Engineering, Queen's University, Kingston, Ontario, Canada. Wunderlich, K.E and Smith, R.L. (1992) "Large Scale Traffic Modeling for RouteGuidance Evaluation: A Case Study", Univeristy of Michigan IVHS Program Technical Report #92-08. Wunderlich, K.E. and Smith, R.L. (1993) "Refinement and Calibration in the Troy Case Study Model for Anticipatory Route Guidance Evaluation", University of Michigan IVHS Program Technical Report #93-04. 19