In our approach, each new route was generated as what would have been the fastest route on the previous iteration.19.1 It is improbable that real people solve this problem exactly, and for that reason alternative route generation algorithms are desirable. Somewhat interestingly, it turns out that finding alternative routes is considerably more difficult than finding the fastest path alone.
One option is to systematically compute the second-fastest,
third-fastest, ..., 
-fastest path. This is however much more
compute-intensive than computing the shortest path alone
(32,130,27,96). In addition,
most of these paths are not plausible for the real world. Often, they
are just small variations of already existing paths, with for example
leaving the freeway and returning to it at the same entry/exit point.
Only very few of the paths generated in this way are true innovations.
As an alternative, one could attempt to generate routes heuristically, instead of systematically. This is also not a simple problem (94). Typical heuristic approaches start searching in the geographic direction of the destination, and in consequence often miss freeway connections which demand some backtracking in order to reach them. More sophisticated approaches will be necessary here.
One may think that heuristic approaches might also be desirable for computational speed reasons in very large road networks. In practice, we have never found this to be a problem. In a typical transportation planning network, with a size of about 10000 nodes and 20000 links, a straightforward implementation of the time-dependent Dijkstra algorithm allows the computation of 10000 new routes per second on a typicaly 500 MHz CPU (57), which is fast enough for practical cases. In much larger networks, this may no longer be sufficient. In such cases, some hierarchical pre-processing can help. This is a topic of ongoing research.