A computational study of routing algorithms for realistic transportation networks.
We carry out an experimental analysis of a number of shortest-path (routing) algorithms investigated in the context of the TRANSIMS (TRansportation ANalysis and SIMulation System) project. The main focus of the paper is to study how various heuristic as well as exact solutions and associated data structures affect the computational performance of the software developed for realistic transportation networks. For this purpose we have used a road network representing, with high degree of resolution, the Dallas Fort-Worth urban area.We discuss and experimentally analyze various one-to-one shortest-path algorithms. These include classical exact algorithms studied in the literature as well as heuristic solutions that are designed to take into account the geometric structure of the input instances.Computational results are provided to compare empirically the efficiency of various algorithms. Our studies indicate that a modified Dijkstra's algorithm is computationally fast and an excellent candidate for use in various transportation planning applications as well as ITS related technologies.
Introduction
TRANSIMS is a multi-year project at the Los Alamos National Laboratory and is funded by the
Department of Transportation and by the Environmental Protection Agency. The main purpose
of TRANSIMS is to develop new methods for studying transportation planning questions. A
prototypical question considered in this context would be to study the economic and social
impact of building a new freeway in a large metropolitan area. We refer the reader to [TR+95a]
and the web-site http://transims.tsasa.lanl.gov to obtain extensive details about the
TRANSIMS project.
The main goal of the paper is to describe the computational experiences in engineering various
path finding algorithms in the context of TRANSIMS. Most of the algorithms discussed
here are not new; they have been discussed in the Operations Research and Computer Science
community. Although extensive research has been done on theoretical and experimental evaluation
of shortest path algorithms, most of the empirical research has focused on randomly
generated networks and special classes of networks such as grids. In contrast, not much work
has been done to study the computational behavior of shortest path and related routing algorithms
on realistic traffic networks. The realistic networks differ from random networks as well
as from homogeneous (structured networks) in the following significant ways:
(i) Realistic networks typically have a very low average degree. In fact in our case the average
degree of the network was around 2.6. Similar numbers have been reported in [ZN98]. In
contrast random networks used in [Pa84] have in some cases average degree of up to 10.
(ii) Realistic networks are not very uniform. In fact, one typically sees one or two large clusters
(downtown and neighboring areas) and then small clusters spread out throughout the entire
area of interest.
(iii) For most empirical studies with random networks, the edge weights are chosen independently
and uniformly at random from a given interval. In contrast, realistic networks typically
have short links.
With the above reasons and specific application in mind, the main focus of this paper is to
carry out experimental analysis of a number of shortest path algorithms on real transportation
network and subject to practical constraints imposed by the overall system. See also Section 6,
the point "Peculiarities of the network and its Effect" for some intuition what features of the
network we consider crucial for our observations.
The rest of the report is organized as follows. Section 2 contains problem statement and
related discussion. In Section 3, we discuss the various algorithms evaluated in this paper. Section
4 summarizes the results obtained. Section 5 describes our experimental setup. Section 6
describes the experimental results obtained. Section 7 contains a detailed discussion of our re-
sults. Finally, in Section 8 we give concluding remarks and directions for future research. We
have also included an Appendix (Section 8.1) that describes the relevant algorithms for finding
shortest paths in detail.
Problem specification and justification
The problems discussed above can be formally described as follows: let G(V; E) be a (un)directed
graph. Each edge e 2 E has one attribute w(e) denoting the weight (or cost) of the edge e. Here,
we assume that the weights are non-negative floating point numbers.
Definition 2.1 One-to-One Shortest
Given a directed weighted, graph G, a source destination pair (s; d) find a shortest (with respect to w)
path p in G from s to d.
Note that our experiments are carried out for shortest path between a pair of nodes, as
against finding shortest path trees. Much of the literature on experimental analysis uses the
second measure to gauge the efficiency. Our choice to consider the running time of the one-to-
one shortest path computation is motivated by the following observations:
1. In our setting we need to compute shortest paths for roughly a million travelers. In highly
detailed networks, most of these travelers have different starting points (for example, in
Portland we have 1.5 million travelers and 200 000 possible starting locations). Thus, for
any given starting location, we could re-use the tree computation only for about ten other
travelers.
2. We wanted our algorithms to be extensible to take into account additional features/constraints
imposed by the system. For example, each traveler typically has a different starting time
for his/her trip. Since we use our algorithms for time dependent networks (networks
in which edge weights vary with time), the shortest path tree will be different for each
traveler. As a second example we need to find paths for travelers with individual mode
choices in a multi-modal network. Formally, we are given a directed labeled, weighted,
graph G representing a transportation network with the labels on edges representing the
various modal attributes (e.g. a label t might represent a rail line). There the goal is to find
shortest (simple) paths subject to certain labeling constraints on the set of feasible paths.
In general, the criteria for path selection varies so much from traveler to traveler that the
additional overhead for the "re-use" of information is unlikely to pay off.
3. The TRANSIMS framework allows us to use paths that are not necessarily optimal. This
motivates investigation of very fast heuristic algorithms that obtain only near optimal
paths (e.g. the modified A  algorithm discussed here). For most of these heuristics, the
idea is to bias a more focused search towards the destination - thus naturally motivating
the study of one-one shortest path algorithms.
4. Finally, the networks we anticipate to deal with contain more than 80 000 nodes and
around 120 000 edges. For such networks storing all shortest path trees amounts to huge
memory overheads.
3 Choice of algorithms
Important objectives used to evaluate the performance of the algorithms include (i) time taken
for computation on real networks, (ii) quality of solution obtained, (iii) ease of implementation
and (iv) extensibility of the algorithm for solving other variants of the shortest path problem. A
number of interesting engineering questions were encountered in the process. We experimentally
evaluated a number of variants of Dijkstra's algorithm. The basic algorithm was chosen
due to the recommendations made in Cherkassky, Goldberg and Radzik [CGR96] and Zhan
and Noon [ZN98]. The algorithms studied were:
Dijkstra's algorithm with Binary Heaps [CGR96],
A  algorithm proposed in AI literature and analyzed by Sedgewick and Vitter [SV86],
a modification of the A  algorithm that we will describe below, and alluded to in [SV86].
A bidirectional version of Dijkstra's algorithm described in [Ma, LR89] and analyzed by [LR89]
was also considered. We briefly recall the A  algorithm and the modification proposed. Details
of these algorithms can be found in the Appendix.
When the underlying network is (near) Euclidean it is possible to improve the average case
performance of Dijkstra's algorithm by exploiting the inherent geometric information that is
ignored by the classical path finding algorithms. The basic idea behind improving the performance
of Dijkstra's algorithm is from [SV86, HNR68] and can be described as follows. In order
to build a shortest path from s to t, we use the original distance estimate for the fringe vertex
such as x, i.e. from s to x (as before) plus the Euclidean distance from x to t. Thus we use global
information about the graph to guide our search for shortest path from s to t. The resulting
algorithm runs much faster than Dijkstra's algorithm on typical graphs for the following intuitive
reasons: (i) The shortest path tree grows in the direction of t and (ii) The search of the
shortest path can be terminated as soon as t is added to the shortest path tree.
We note that the above algorithms, only require that the Euclidean distance between any
two nodes is a valid lower bound on the actual shortest distance between these nodes. This is
typically the case for road networks; the link distance between two nodes in a road network
typically accounts for curves, bridges, etc. and is at least the Euclidean distance between the
two nodes. Moreover in the context of TRANSIMS, we need to find fastest paths, i.e. the cost
function used to calculate shortest paths is the time taken to traverse the link. Such calculations
need an upper bound on the maximum allowable speed. To adequately account for all these
inaccuracies, we determine an appropriate lower bound factor between Euclidean distance and
assumed delay on a link in a preprocessing step.
We can now modify this algorithm by giving an appropriate weight to the distance from
x to t. By choosing an appropriate multiplicative factor, we can increase the contribution of
the second component in calculating the label of a vertex. From a intuitive standpoint this
corresponds to giving the destination a high potential, in effect biasing the search towards
the destination. This modification will in general not yield shortest paths, nevertheless our
experimental results suggest that the errors produced can be kept reasonably small.
4 Summary of Results
We are now ready to summarize the main results and conclusions of this paper. As already
stated the main focus of the paper is the engineering and tuning of well known shortest path
algorithms in a practical setting. Another goal of this paper to provide reasons for and against
certain implementations from a practical standpoint. We believe that our conclusions along
with the earlier results in [ZN98, CGR96] provide practitioners a useful basis to select appropriate
algorithms/implementations in the context of transportation networks. The general re-
sults/conclusions of this paper are summarized below.
1. We conclude that the simple Binary heap implementation of Dijkstra's algorithm is a
good choice for finding optimal routes in real road transportation networks. Specifically,
we found that certain types of data structure fine tuning did not significantly improve the
performance of our implementation.
2. Our results suggest that heuristic solutions using the underlying geometric structure of
the graphs are attractive candidates for future research. Our experimental results motivated
the formulation and implementation of an extremely fast heuristic extension of the
basic A  algorithm. The parameterized time/quality trade-off the algorithm achieves in
our setting appears to be quite promising.
3. Our study suggests that bidirectional variation of Dijkstra's algorithm is not suitable for
transportation planning. Our conclusions are based on two factors: (i) the algorithm is not
extensible to more general path problems and (ii) the running time does not outperform
the other exact algorithms considered.
5 Experimental Setup and Methodology
In this section we describe the computational results of our implementations. In order to anchor
research in realistic problems, TRANSIMS uses example cases called Case studies (See [CS97]
for complete details). This allows us to test the effectiveness of our algorithms on real life data.
The case study just concluded focused on Dallas Fort-Worth (DFW) Metropolitan area and was
done in conjunction with Municipal Planning Organization (MPO) (known as North Central
Texas Council of Governments (NCTCOG)). We generated trips for the whole DFW area for a
hour period. The input for each traveler has the following format: (starting time, starting
location, ending location). 4 There are 10.3 million trips over 24 hours. The number of nodes
4 This is roughly correct, the reality is more complicated, [NB97, CS97].
and links in the Dallas network is roughly 9863, 14750 respectively. The average degree of a
node in the network was 2.6. We route all these trips through the so-called focused network. It
has all freeway links, most major arterials, etc. Inside this network, there is an area where all
streets, including local streets, are contained in the data base. This is the study area. We initially
routed all trips between 5am and 10am, but only the trips which went through the study area
were retained, resulting in approx. 300 000 trips. These 300 000 trips were re-planned over and
over again in iteration with the micro-simulation(s). For more details, see, e.g., [NB97, CS97].
A 3% random sample of these trips were used for our computational experiments.
Preparing the network. The data received from DFW metro had a number of inadequacies
from the point of view of performing the experimental analysis. These had to be corrected
before carrying out the analysis. We mention a few important ones here. First, the network was
found to have a number of disconnected components (small islands). We did not consider (o; d)
pairs in different components. Second, a more serious problem from an algorithmic standpoint
was the fact that for a number of links, the length was less than the actual Euclidean distance
between the the two end points. In most cases, this was due to an artificial convention used
by the DFW transportation planners (so-called centroid connectors always have length 10 m,
whatever the Euclidean distance), but in some cases it pointed to data errors. In any case,
this discrepancy disallows effective implementation of A  type algorithms. For this reason
we introduce the notion of the "normalized" network: For all links with length less than the
Euclidean distance, we set the reported length to be equal to the Euclidean distance. Note here,
that we take the Euclidean distance only as a lower bound on shortest path in the network.
Recall that if we want to compute fastest path (in terms of time taken) instead of shortest,
we also have to make assumptions regarding the maximum allowable speed in the network
to determine a conservative lower bound on the minimal travel time between points in the
network.
Preliminary experimental analysis was carried out for the following network modifications
that could be helpful in improving the efficiency of our algorithms. These include: (i) Removing
nodes with degrees less than 3: (Includes collapsing paths and also leaf nodes) (ii) Modifying
nodes of degree 3: (Replace it by a triangle)
Hardware and Software Support. The experiments were performed on a Sun UltraSparc CPU
with 250 MHz, running under Solaris 2.5. 2 gigabyte main memory were shared with 13 other
CPUs; our own memory usage was always 150 MB or less. In general, we used the SUN Workshop
CC compiler with optimization flag -fast. (We also performed an experiment on the influence
of different optimization options without seeing significant differences.) The advantage of
the multiprocessor machine was reproducibility of the results. This was due to the fact that the
operating system does not typically need to interrupt a live process; requests by other processes
were assigned to other CPUs.
Experimental Method 10,000 arbitrary plans were picked from the case study. We used the
timing mechanism provided by the operating system with granularity .01 seconds (1 tick). Experiments
were performed only if the system load did not exceed the number of available
processors, i.e. processors were not shared. As long as this condition was not violated during
the experiment, the running times were fairly consistent, usually within relative errors of 3%.
We used (a subset) of the following values measurable for a single or a specific number of
computations to conclude the reported results
(average) running time excluding i/o
number of fringe/expanded nodes
pictures of fringe/expanded nodes
maximum heap size
number of links and length of the path
Software Design We used the object oriented features as well as the templating mechanism
of C++ to easily combine different implementations. We also used preprocessor directives and
macros. As we do not want to introduce any unnecessary run time overhead, we avoid for
example the concept of virtual inheritance. The software system has classes that encapsulate
the following elements of the computation:
network (extensibility and different levels of detail lead to a small, linear hierarchy)
plans: (o; d) pairs and complete paths with time stamps
priority queue (heap)
labeling of the graph and using the priority queue
storing the shortest path tree
Dijkstra's algorithm
As expected, this approach leads to an apparent overhead of function calls. Nevertheless,
the compiler optimization detects most such overheads. Specifically, an earlier non templated
implementation achieved roughly the same performance as the corresponding instance of the
templated version. The results were consistent with similar observations when working on
mini-examples. The above explanation was also confirmed by the outcome of our experiments:
We observed, that reducing the instruction count does not reduce the observed running time as
might be expected. Assuming we would have a major overhead from high level constructs, we
would expect to see a strong influence of the number of instructions executed on the running
time observed.
6 Experimental Results
Design Issues about Data Structures We begin with the design decisions regarding the data
structures used.
A number of alternative data structures were considered to investigate if they results in substantial
improvement in the running time of the algorithm. The alternatives tested included
the following. (i) Arrays versus Heaps , (ii) Deferred Update, (iii) Hash Tables for Storing
Graphs, (iv) Smart Label Reset (v) Heap variations, and (vi) struct of arrays vs. array of structs.
Appendix contains a more detailed discussion of these issues. We found, that indeed good
programming practice, using common sense to avoid unnecessary computation and textbook
knowledge on reasonable data structures are useful to get good running times. For the alternatives
mentioned above, we did not find substantial improvement in the running time. More
precisely, the differences we found were bigger than the unavoidable noise on a multi-user
computing environment. Nevertheless, they were all below 10% relative difference. A brief
discussion of various data structures tried can be found in the Appendix.
Analysis of results. The plain Dijkstra, using static delays calculated from reported free flow
speeds, produced roughly 100 plans per second. Figure 1 illustrates the improvement obtained
by the A  modification. The numbers shown in the corner of the network snapshots tell an
average (of 100 repetitions to destroy cache effects between subsequent runs) running time for
this particular O-D-pair, in system ticks. It also gives the number of expanded and fringe nodes.
Note that we have used different scales in order to clearly depict the set of expanded nodes.
Overall we found that A  on the normalized network (having removed network anomalies as
explained above) is faster than basic Dijkstra's algorithm by roughly a factor of 2.
Modified A  (Overdo Heuristic) Next consider the modified A  algorithm - the heuristic is
parameterized by the multiplicative factor used to weigh the Euclidean distance to the destination
against the distance from the source in the already computed tree. We call this the
overdo parameter. This approach, can be seen as changing the conservative lower bound used
for in the A  algorithm into an "expected" or "approximated" lower bound. Experimental evidence
suggests that even large overdo factors usually yield reasonable paths. Note that this
nice behavior might fail as soon as the link delays are not at all directly related to the link
length (Euclidean distance between the endpoints), as might be expected in a network with
link lengths proportional to travel times in a partially congested city. As a result it is natural to
discuss the time/quality trade-off of the heuristic as a function of the overdo parameter. Figure 2
summarizes the performance. In the figure the X-axis represents the overdo factor, being varied
from 0 to 100 in steps of 1. The Y-axis is used for multiple attributes which we explain below.
First, the Y axis is used to represent the average running time per plan. For this attribute, we
use the log scale with the unit denoting 10 milliseconds. As depicted by the solid line, the average
time taken without any overdo at all is 12.9 milliseconds per plan. This represents the
base measurement (without taking the geometric information into account, but including time
taken for computing of Euclidean distances). Next, for overdo value of 10 and 99 the running
times are respectively 2.53 and .308 milliseconds. On the other hand, the quality of the solution
produced by the heuristic worsens as the overdo factor is increased. We used two quantities
to measure the error - (i) the maximum relative error incurred over 10000 plans and (ii) the
ticks 2.40, #exp 6179, #fr 233
ticks 0.64, #exp 1446, #fr 316

Figure

1: Figure illustrating the number of expanded nodes while running (i) Dijkstra (ii) A
algorithms. The figures clearly show the A  heuristic is much more efficient in terms of the
nodes it visits. In both the graphs, the path is outlined as a dark line. The fringe nodes and the
expanded nodes are marked as dark spots. The underlying network is shown in light grey. The
source node is marked with a big circle, the destination with a small one. Notice the different
scales of the figures. 9
time

Figure

2: Figure illustrating the trade-off between the running time and quality of paths as a
function of the overdo-paramameter. The X axis represents the overdo factor from 0 to 100.
The Y axis is used to represent three quantities plotted on a log scale - (i) running time, (ii)
Maximum relative error and (iii) fraction of plans with relative error greater than a threshold
value. The threshold values chosen are 0%,
time
Figure

3: Figure illustrating the trade-off between the running time and quality of paths as
a function of the overdo-parameter on the normalized network. The meaning of the axis and
depicted things is the same as in the previous figure.
fraction of plans with errors more than a given threshold error. Both types of errors are shown
on the Y axis. The maximum relative error (plot marked with *) ranges from 0 for overdo factor 0
to 16% for overdo value 99. For the other error measure, we plot one curve for each threshold
error of 0%, 10%. The following conclusions can be drawn from our results.
1. The running times improve significantly as the overdo factor is increased. Specifically the
improvements are a factor 5 for overdo parameter 10 and almost a factor 40 for overdo
parameter 99.
2. In contrast, the quality of solution worsens much more slowly. Specifically, the maximum
error is no worse than 16% for the maximum overdo factor. Moreover, although the
number of erroneous plans is quite high (almost all plans are erroneous for overdo factor
of 99), most of them have small relative errors. To illustrate this, note that only around
15% of them have relative error of 5% or more.
3. The experiments and the graphs suggest an "optimal" value of overdo factor for which
the running time is significantly improved while the solution quality is not too bad. These
experiments are a step in trying to find an empirical time/performance trade-off as a
function of the overdo parameter.
4. As seen in Figure 3 the overall quality of the results shows a similar tradeoff if we switch
to the normalized network. The only difference is that the errors are reduced for a given
value of the overdo parameter.
5. As depicted in Figure 4, the number of plans worse than a certain relative error decreases
(roughly) exponentially with this relative error. This characteristic does not depend on
the overdo factor.
6. We also found that the near-optimal paths produced were visually acceptable and represented
a feasible alternative route guiding mechanism. This method finds alternative
paths that are quite different than ones found by the k-shortest path algorithms and seem
more natural. Intuitively, the k-shortest path algorithms, find paths very similar to the
overall shortest path, except for a few local changes.
7. The counterintuitive local maximum for overdo value 3.2 in Figure 3 can be explained by
the example depicted in Figure 5.
the optimal length is 21,
for overdo parameter 2 we get a solution of length 22 Here node B gets inserted with
a value of 24 opposed to values 29 and 25 of A and C. As these values for A and B
are bigger than the resulting path using B, this path stays final.
for overdo parameter 4 we get again a solution of length 21. This stems from the fact
that now C gets inserted into the heap with the value 33 where as B with a value of
overdo factor 3.0
overdo factor 2.0
overdo factor 1.5
overdo factor 1.2
overdo factor 1.1

Figure

4: The distribution of wrong plans for different overdo-parameters in the normalized
network for Dallas Ft-Worth. In X direction we change the "notion of a bad plan" in terms of
relative error, in Y direction we show the fraction of plans that is classified to be "bad" with the
current notion of "wrong".
It is easy to see that such examples can be scaled and embedded into larger graphs. Since
the maximum error stems from one particular shortest path question, it is not too surprising
to encounter such a situation.
Peculiarities of the network and its Effect In the context of TRANSIMS, where we needed to
find one-to-one shortest paths, we observed possibly interesting influence of the underlying
network and its geometric structure on the performance of the algorithms. We expect similar
characteristics to be visible in other road networks as well, possibly modified by the existence of
rivers or other similar obstacles. Note that the network is almost Euclidean and (near) homogenous
to justify the following intuition: Dijkstra's algorithm explores the nodes of a network in
a circular fashion. During the run we see roughly a disc of expanded nodes and a small ring
of fringe nodes (nodes in the heap) around them. For planar and near panar graphs it has
been observed that the heap size is O(
n) with high probability. This provides one possible
explanation of why the maximum heap sizes in our experiments was close to 500. In particular,
even if the area of the circular (in number of nodes) reaches the size of the network (10 000),
the ring of fringe nodes is roughly proportional to the circumference of the circular region (and
thus roughly proportional to
We believe that this homogenous and almost Euclidean
structure is also the reason for our observations about the modified A  algorithm. The above
discussion provides at least an intuitive explanation of why special algorithms such as A  might
perform better on Euclidean and close to Euclidean networks.
A

Figure

5: Example network having a local maximum for the computed path length for increasing
overdo parameter; the edges are marked with (Euclidean distance, reported length).
Effect of Memory access times In our experiments we observed, that changes in the implementation
of the priority queue have minimal influence on the overall running time. In contrast,
the instruction count profiling (done with a program called "quantify") pinpoints the priority
queue to be the main contributer to the overall number of instructions. Combining these two
facts, we conclude that the running time we observe is heavily dependent on the time it takes
to access the graph representation that do do not fit the cache. Thus the processor spends a
significant amount of time waiting.
We expect further improvement of the running time by concentrating on the memory ac-
cesses, for example by making the graph representation more compact, or optimize accesses
by choosing memory location of a node according to the topology of the graph. In general the
conclusions of our paper motivate the need for design and analysis of algorithms that take the
memory access latency into account.
7 Discussion of Results
First, we note that the running times for the plain Dijkstra are reasonable as well as sufficient in
the context of the TRANSIMS project. Quantitatively, this means the following: TRANSIMS is
run in iterations between the micro-simulation, and the planner modules, of which the shortest
path finding routine is one part. We have recently begun research for the next case study
project for TRANSIMS. This case study is going to be done in Portland, Oregon and was chosen
to demonstrate the validate our ideas for multi-modal time dependent networks with public
transportation following a scheduled movement. Our initial study suggests that we now take
sec/trip as opposed to .01 sec/trip in the Dallas Ft-Worth case [Ko98]. All these extensions
are important from the standpoint of finding algorithms for realistic transportation routing
problems. We comment on this in some detail below. Multi-modal networks are an integral
part of most MPO's. Finding optimal (or near-optimal) routes in this environment therefore
constitutes a real problem. In the past, solutions for routing in such networks was handled
ticks 0.10, #exp 140, #fr 190

Figure

Figure illustrating two instances of Dijkstra's algorithms with a very high overdo
parameter start at origin and destination respectively. One of them really creates the shown
path, the beginning of the other path is visible as a "cloud" of expanded nodes
in an ad hoc fashion. The basic idea (discussed in detail in [BJM98]) here is to use regular
expressions to specify modal constraints. In [BJM98, JBM98], we have proposed models and
polynomial time algorithms to solve this and related problems. Next consider another important
extension - namely to time dependent networks. We assume that the edge lengths are
modeled by monotonic non-decreasing, piecewise linear functions. These are called the link
traversal functions. For a function f associated with a link denotes the time
of arrival at b when starting at time x at a. By using an appropriate extension of the basic
Dijkstra's algorithm, one can calculate optimal paths in such networks. Our preliminary results
on these topics in the context of TRANSIMS can be found in [Ko98, JBM98]. The Portland
network we are intending to use has about 120 000 links and about 80 000 nodes. Simulating
hours of traffic on this network will take about 24 hours computing time on our 14 CPU ma-
chine. There will be about 1.5 million trips on this network. Routing all these trips should take
9 days on a single CPU and thus less than 1 day on our 14 CPU
machine. Since re-routing typically concerns only 10% of the population, we would need less
than 3 hours of computing time for the re-routing part of one iteration, still significantly less
than the micro-simulation needs.
Our results and the constraints placed by the functionality requirement of the overall system
imply that bidirectional version of Dijkstra's algorithm is not a viable alternative. Two
reasons for this are: (i) The algorithm can not be extended in a direct way to path problems in a
multi-modal and time dependent networks, and (ii) the running times of A  is better than the
bidirectional variant; the modified A  is much more faster.
Conclusions
The computational results presented in the previous sections demonstrate that Dijkstra's algorithm
for finding shortest paths is a viable candidate for compute route plans in a route
planning stage of a TRANSIMS like system. Thus such an algorithm should be considered
even for ITS type projects in which we need to find routes by an on-board vehicle navigation
systems.
The design of TRANSIMS lead us to consider one-to-one shortest path algorithms, as opposed
to algorithms that construct the complete shortest-path tree from a given starting (or
destination) point. As is well known, the worst-case complexity of one-to-one shortest path
algorithms is the same as of one-to-all shortest path algorithms. Yet, in terms of our practical
problem, this is not applicable. First, a one-to-one algorithm can stop as soon as the destination
is reached, saving computer time especially when trips are short (which often is the case in our
setting). Second, since our networks are roughly Euclidean, one can use this fact for heuristics
that reduce computation time even more. The A  with an appropriate overdo parameter
apperas to be an attractive candidate in this regard.
Making the algorithms time-dependent in all cases slowed down the computation by a
factor of at most two. Since we are using a one-to-one approach, adding extensions that for
example include personal preferences (e.g. mode choice) are straightforward; preliminary tests
let us expect slow-downs by a factor of 30 to 50. This significant slowdown was caused by a
number of factors including the following:
(i) The network size increased by a factor of 4 and was caused by addition and splitting of
nodes and/or edges and adding public transportation. This was done to account for
activity locations, parking locations, adding virtual links joining these locations, etc.
(ii) The time dependency functions used to represent transit schedules and varying speed of
street traffic, implied increased memory and computational requirement. Initial estimates
are that the memory requirement increases by a factor of 10 and the computational time
increases by factor of 5. Moreover, different type of delay functions were used for inducing
a qualitatively different exploration of the network by the algorithm. This seems to
prohibit keeping a small number of representative time dependency functions.
(iii) The algorithm for handling modal constraints works by making multiple copies of the
original network. The algorithm is discussed in [JBM98] and preliminary computational
results are discussed in [Ko98]. This increased the memory requirement by a factor of 5
and computation time by an additional factor of 5.
Extrapolations of the results for the Portland case study show that, even with this slowdown
the route planning part of TRANSIMS still uses significantly less computing time than the
micro-simulation.
Finally, we note that under certain circumstances the one-to-one approach chosen in this
paper may also be useful for ITS applications. This would be the case when customers would
require customized route suggestions, so that re-using a shortest path tree from another calculation
may no longer be possible.

Acknowledgments

Research supported by the Department of Energy under Contract W-7405-
ENG-36. We thank the members of the TRANSIMS team in particular, Doug Anson, Chris
Barrett, Richard Beckman, Roger Frye, Terence Kelly, Marcus Rickert, Myron Stein and Patrice
Simon for providing the software infrastructure, pointers to related literature and numerous
discussions on topics related to the subject. The second author wishes to thank Myron Stein
for long discussion on related topics and for his earlier work that motivated this paper. We
also thank Joseph Cheriyan, S.S. Ravi, Prabhakar Ragde, R. Ravi and Aravind Srinivasan for
constructive comments and pointers to related literature. Finally, we thank the referees for
helpful comments and suggestions.



--R


The Design and Analysis of Computer Algo- rithms
Formal Language Constrained Path Problems to be presented at the Scandinavian Workshop on Algorithmic Theory
An Operational Description of TRANSIMS

Shortest Path algorithms: Theory and Experimental Evaluation
Computational Study of am Improved Shortest Path Algorithm
"Route Finding in Street Maps by Computers and People,"
"A Formal Basis for the Heuristic Determination of Minimum Cost Paths,"
Highway Research Board

Experimental Analysis of Routing Algorithms in in Time Dependent and Labeled Networks
"A Bidirectional Shortest Path Algorithm with Good Average Case Behavior,"
"Approximation schemes for the restricted shortest path problem,"
"A Shortest Path Algorithm with Expected Running time O( p V log V ),"
Shortest Path Algorithms: A Computational Study with C Programming Language
Using Microsimulation Feedback for trip Adaptation for Realistic Traffic in Dallas
Experiences with Iterated Traffic Microsimulations in Dallas
Implementation and Efficiency of Moore Algorithm for the Shortest Root Problem
Shortest Path Algorithms: Complexity
"Bidirectional Searching,"
"Shortest Paths in Euclidean Graphs,"
"Finding Realistic Detour by AI Search Techniques,"
Shortest Path Algorithms: An Evaluation using Real Road Networks Transportation Science
--TR
Shortest paths in Euclidean graphs
Shortest path algorithms: a computational study with the C programming language
Network flows
Approximation schemes for the restricted shortest path problem
Shortest paths algorithms
The Design and Analysis of Computer Algorithms
Formal Language Constrained Path Problems
Shortest Path Algorithms

--CTR
Michael Balmer , Nurhan Cetin , Kai Nagel , Bryan Raney, Towards Truly Agent-Based Traffic and Mobility Simulations, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.60-67, July 19-23, 2004, New York, New York
L. Fu , D. Sun , L. R. Rilett, Heuristic shortest path algorithms for transportation applications: state of the art, Computers and Operations Research, v.33 n.11, p.3324-3343, November 2006
shortest-paths algorithms;transportation planning;design and analysis of algorithms;network design;experimental analysis