Day-to-day learning, feedback, and relaxation

The interaction between the modules can lead to logical deadlocks. For example, plans depend on congestion, but congestion depends on plans. As said before, widely accepted method to resolve this is systematic relaxation (e.g. [3]) - that is, make preliminary plans, run the traffic micro-simulation, adjust the plans, run the traffic micro-simulation again, etc., until consistency between modules is reached. The method is somewhat similar to a standard relaxation technique in numerical analysis.

Fig. 1.2 shows an example of the effect of this. The scenario here is that 50000 travelers, distributed randomly throughout Switzerland, all want to travel to Lugano, which is indicated by the circle. The scenario is used as a test case, but it has some resemblance with vacation traffic in Switzerland,

The left figure shows traffic when every driver selects the route which would be fastest on an empty network. The micro-simulation here uses the so-called queue model [7], which is a queuing model with an added link storage constraint. That is, links are characterized by a service rate (capacity), and a maximum number of cars on the link. If the link is full, no more vehicles can enter, causing spill-back. Compared to the original version of Ref [8], our model has an improved intersection dynamics [7]. After the initial routing and the initial micro-simulation, iterations are run as follows:

1. During the micro-simulation, one collects link travel times, averaging over, say, 15 minutes. That is, all vehicles entering a link between, say, 8am and 8:15am, will contribute to the average for that time period.

2. For a randomly selected fraction of, say, 10% of the travelers, the old routes are replaced by new routes which are generated based on these averaged link travel times.

3. The traffic micro-simulation is run again based on the new set of routes

4. Another 10% of the travelers obtains new routes.

5. Etc., until some kind of convergence criterion is fulfilled.

The routing is done by running a time-dependent Dijkstra algorithm. The time-dependency is included by using the time-dependent averaged link travel times every time a link is considered. That is, for each link $a$, there is a time-dependent cost function, $c_a(t)$, which we obtain as a piece-wise constant approximation of the averaged link travel times returned from the simulation. When a standard Dijkstra algorithm is used in the forward direction, i.e. starting at the starting point of the trip at the corresponding starting time and expanding into all directions as standard in Dijkstra, one just has to replace the fixed link costs by $c_a(t)$ in the standard algorithm. In principle, the time dependency adds the possibility that a faster route could be obtained by waiting at a node, but since this is not realistic for car traffic, this possibility can be ignored.

Fig. 1.2 right is the result after 49 such iterations. Quite visibly traffic has spread out over many more different routes.

Fig. 1.3 shows the relaxation behavior for a scenario in Dallas [9,10]. The plot shows the sum of all travel times as a function of the iteration number. From this plot and from other observations it seems that here, broken ergodicity is not a problem, and all relaxation methods go to the same state, although with different convergence speeds.

The result is in fact similar to a fixed strategy Nash Equilibrium: for a single run in the relaxed state, it is approximately true that no traveler could improve by changing routes. The players follow a ``best reply'' dynamics (i.e. find the best answer to yesterday's traffic), and for some (non-traffic) systems it can even be proven that this converges to a Nash equilibrium [11].

As mentioned above, traffic has a tendency to spread out in reaction to congestion. That is, people shift from congested to uncongested links, even if under uncongested conditions the new route would take more time. One would expect that one could note this in the strategy landscape, i.e. that the performance difference between the first $k$ fastest path is smaller under congested than under uncongested conditions. This conjecture is in fact correct [12]. Fig. 1.4 (left) shows performance decrease incurred by selecting the $k$-best route instead of the best one, once for an uncongested network and once for a congested one. Clearly, the strategy landscape is much flatter in the congested situation. It is however equally flat in the relaxed and in the unrelaxed situation. Fig. 1.4 (right) shows that the additional options under relaxed congested conditions are truly different from the best option, which is not true for the unrelaxed congested situation. This, in summary: Under uncongested conditions, deviating from the fastest path incurs a high penalty. Under unrelaxed congested conditions, there are many good options, but they are all similar to each other. Only under relaxed congested conditions do we find many truly different options with similar performance.

The above results were obtained with a Dallas/Fort Worth scenario within the TRANSIMS project. ``Uncongested'' refers to the empty network, where free speeds were used to compute link travel times. ``Unrelaxed congested'' refers to the zeroth iteration traffic in the middle of the rush hour. ``Relaxed congested'' refers to a situation after many iterations; in fact, link travel times were averaged over 10 iterations. All curves in Fig. 1.4 refer to an average over 955 randomly selected OD (origin-destination) pairs in the study area which are between 7 km and 7.01 km apart.

Figure 1.2: Result of day-to-day learning in a test example. The scenario is a test case, using a network of Switzerland, where 50000 vehicles from all over the system start between 6am and 7am and simultaneously attempt to reach a destination within the circle. Green shows free flowing traffic; red shows traffic jams. LEFT: Situation at 9:00am in the zeroth iteration. RIGHT: Situation at 9:00am in the 49th iteration. Clearly, traffic has spread out and the system is using more different routes in the 49th iteration.

Figure 1.3: Different relaxation paths in day-to-day replanning. The plot shows the sum of all travel times as a function of the iteration for different relaxation methods. All methods seem to lead to the same relaxed state. From [13].

Figure 1.4: Flatness of the strategic landscape for route choice behavior. LEFT: Ratio of the travel times of the fastest path to the $k$-fastest path as a function of $k$. Clearly, this measure decreases more quickly in an uncongested than in a relaxed congested network, meaning that in a relaxed congested network, there are many more alternatives at about the same system performance. RIGHT: Under relaxed congested conditions, the additional options are truly dissimilar. Shows is the similarity to the best option as function of the additional travel time. - From [12].