6.2.4 Some Complications for Urban Travel

Certain complications arise when shortest-path algorithms, such as the two we have already discussed, are applied in the urban environment.

For instance, a motorist often suffers a penalty, in terms of increased travel time for right and, especially, for left turns when traveling on urban streets. If one wishes to take this into account in a network model and is careless in doing so, serious difficulties can result.

Example 4: Turn Penalties and Constraints

Consider the network of Figure 6.8 representing a small part of a downtown urban street grid. The numbers next to the arcs indicate average travel times on each street segment and nodes represent street corners. Suppose that each turn (right or left) carries a penalty of two time units. Then the shortest path from node A to node D is the path {A, B, D} of length equal to 12 time units (including the 2-unit penalty for the turn at D), whereas the shortest path from A to E is {A, C, D, E} of length 20 units. Thus, the path that one would follow in going from A to D along the shortest path from A to E does not coincide with (and is of different length from) the shortest path from A to D! This, of course, is inconsistent with the fundamental premise of all shortest-path algorithms (why?).

As Example 4 suggests, "naive" network models (such as that of Figure 6.8) must be modified somewhat to make them appropriate for application of our two shortest-path algorithms when turn penalties are to be taken into consideration. Along the same lines, shortest paths on a downtown urban grid may also include cycles (in the sense of passing through the same intersection twice). For instance, if turns to the left are prohibited at intersection D of Figure 6.8, the shortest path from E to F might be something like {E, D, B. A, C, D, F}. This again is not provided for by shortest-path algorithms thus requiring modification of the straightforward network model.

Similarly, in modeling the possible routes of a commuter--who may have a choice between, say, driving a car all the way to work or driving that car to the nearest subway station, parking the car there, and riding to the job on a train---care must be taken to account for any time losses that the commuter may face at any mode-changing points (or, for that matter, at stations where the commuter may have to change trains).

In conclusion, one should be aware of such complications. The level of detail of a model of an urban network must be consistent with the level of detail sought in the analysis, if one wishes to apply the shortest-path algorithms that we have already discussed (as well as the other algorithms to be presented later) to these models. Increasing the level of detail usually means creating "dummy" (or "artificial") nodes and arcs. These ideas are illustrated in Problems 6.2 and 6.3.