Link travel times and congestion

So far, the router is not sensitive to congestion. In order to make the routes sensitive to congestion, delays caused by congestion need to show up in the link travel times. This can be achieved via getting the link travel times from a separate file. Links which are congested will have link travel times which are longer than the free speed travel times.

In practice, we will achieve this via the events file. The events file, as discussed in Sec. 9.11, contains for each vehicle the time when it enters and the time when it leaves each link. We will aggregate this information as a function of the link entry times. The procedure consists of the following steps:

• Conversion of events to link travel times. For each enter-link-event, the corresponding leave-link-event is searched. As a result, one obtains for each link entry time a corresponding link travel time.

• Aggregation. Link travel times are aggregated into time slices, of e.g. 15 min. For this, the link travel times of all vehicles entering a link during a certain time slice are averaged. For example, if there are vehicles entering at 9:03:22, 9:05:56, and 9:07:23, and their link travel times are 1 min, 2 min, and 3 min, then the average link travel time for all vehicles entering between 9 and 9:14:59 will be 2 min.

  This type of data aggregation is the simplest method possible and it has certain drawbacks. This will be discussed in more detail in Sec. 19.1. [[check if done]]

Let us consider why this method works. The Dijkstra algorithm, as explained in Sec. 11.2, proceeds by ``expanding'' a node when no faster path to that node can be found. For that reason, the ``current time'' at that node, denoted by now, is the time-of-day when the node is reached via the fastest path. It is therefore also the time-of-day then the outgoing links from that node are entered.

Note: With time-dependence as explained above, it could happen that ``waiting at a node'' yields a faster path. This can happen when the link travel time in the following time bin is shorter than the link travel time in the current time bin plus the remaining time in the current time bin. In such a situation, the above algorithm would not return the path that is technically the fastest. In real traffic, however, this is rarely an issue: Links are approximately FIFO (first-in first-out), which means that entering at a later time also means leaving at a later time. In other words: If the time-dependent algorithm ``thinks'' that waiting at a node would pay off, then this is normally an artifact of the routing algorithm - more specifically, of the time aggregation - and not a feature of the traffic system. For those reasons, using the algorithm as described above will normally describe plausible routes, even if they may not be the technically fastest.

Yet, there is at least one situation where indeed waiting at a node could pay off: This is if links are opened at a certain time-of-day. We will not assume such complications here.

Implementation