Finding time-dependent shortest paths over large graphs
Published 25 March 2008
Bolin Ding, Jeffrey Xu Yu, Lu Qin
Citations255
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proposes a novel algorithm to find the minimum-travel-time path with the best departure time for a LTT(vs, v query over a large graph, which outperforms existing algorithms in terms of both time complexity in theory and efficiency in practice.
Abstract
The spatial and temporal databases have been studied widely and intensively over years. In this paper, we study how to answer queries of finding the best departure time that minimizes the total travel time from a place to another, over a road network, where the traffic conditions dynamically change from time to time. We study a generalized form of this problem, called the time-dependent shortest-path problem. A time-dependent graph GT is a graph that has an edge-delay function, wi, j(t), associated with each edge (vi, vj), to be stored in a database. The edge-delay function wi, j(t) specifies how much time it takes to travel from node vi to node vj, if it departs from vi at time t. A user-specified query is to ask the minimum-travel-time path, from a source node, vs, to a destination node, ve, over the time-dependent graph, GT, with the best departure time to be selected from a time interval T. We denote this user query as LTT(vs, ve, T) over GT. The challenge of this problem is the added complexity due to the time dependency in the time-dependent graph. That is, edge delays are not constants, and can vary from time to time. In this paper, we propose a novel algorithm to find the minimum-travel-time path with the best departure time for a LTT(vs, ve, T) query over a large graph GT. Our approach outperforms existing algorithms in terms of both time complexity in theory and efficiency in practice. We will discuss the design of our algorithm, together with its correctness and complexity. We conducted extensive experimental studies over large graphs and will report our findings.
Keywords
Computer ScienceSocial Sciences
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
Journal of the ACMShortest-path and minimum-delay algorithms in networks with time-dependent edge-length
476 Citations1990Ariel Orda, Raphaël Rom
The shortest-path problem in networks in which the delay (or weight) of the edges changes with time according to arbitrary functions is considered and algorithms for finding the shortest path and minimum delay under various waiting constraints are presented.
Journal of the ACMUndirected single-source shortest paths with positive integer weights in linear time
441 Citations1999Mikkel Thorup
A deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights, which avoids the sorting bottleneck by building a hierarchical bucketing structure.
Transportation Research Record Journal of the Transportation Research BoardDiscrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run Time
332 Citations1998Ismaïl Chabini
A new and simple solution algorithm is proposed for all-to-one, all departure time intervals, shortest paths problems and it is proved, theoretically, that the new solution algorithm has an optimal run time complexity that equals the complexity of the problem.
Journal of the ACMA new approach to dynamic all pairs shortest paths
270 Citations2004Camil Demetrescu, Giuseppe F. Italiano
A fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in O(n2log3n) amortized time per update and unit worst-case time per distance query, where n is the number of vertices.
Shortest Path Algorithms In Transportation Models: Classical and Innovative Aspects
266 Citations1998Stefano Pallottino, Maria Grazia Scutellà
The aim of this work is to present in a unifying framework both the main algorithmic approaches that have been proposed in the past years for solving the shortest path problems arising most frequently in the transportation field, and also some important implementaion techniques which allow one to derive efficient procedures from the general algorithmic schema, in line with trends in current research.
Finding Fastest Paths on A Road Network with Speed Patterns
254 Citations2006Evangelos Kanoulas, Yang Du +2 more
This paper proposes and solves the Time-Interval All Fastest Path (allFP) query, and proposes a solution based on novel extensions to the A* algorithm that is more efficient and more accurate than the discrete-time approach.
Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs
227 Citations2003Valerie King
The first fully dynamic algorithms for maintaining all-pairs shortest paths in digraphs with positive integer weights less than b are presented, which use simple data structures, and are deterministic.
IEEE/ACM Transactions on NetworkingNew dynamic algorithms for shortest path tree computation
209 Citations2000P. Narvaez, Kai‐Yeung Siu +1 more
An algorithmic framework is established that allows for a variety of dynamic SPT algorithms including dynamic versions of the well-known Dijkstra, Bellman-Ford, D'Esopo-Pape algorithms, and to establish proofs of correctness for these algorithms in a unified way.
IEEE Transactions on Knowledge and Data EngineeringHierarchical encoded path views for path query processing: an optimal model and its performance evaluation
197 Citations1998Jing Ning, Y.-W. Huang +1 more
This paper proposes a hierarchical encoded path view (HEPV) model, and presents complete solutions for all phases of the HEPV approach, including graph partitioning, hierarchy generation, path view encoding and updating, and path retrieval.
IEEE Transactions on Knowledge and Data EngineeringCCAM: a connectivity-clustered access method for networks and network computations
132 Citations1997Shashi Shekhar, Duen‐Ren Liu
Experiments with network computations on the Minneapolis road map show that CCAM outperforms existing access methods, even though the proposed modifications also substantially improve the performance of existing spatial access methods.
Lecture notes in computer scienceOn Dynamic Shortest Paths Problems
106 Citations2004Liam Roditty, Uri Zwick
NetworksTime-varying shortest path problems with constraints
100 Citations1997Xia Cai, Ton Kloks +1 more
The shortest path problem is considered with yet another extension and is obviously an NP-Complete problem as it is more difficult to solve than a problem with constant transit times and arc costs such as the previous problem which isNP-Complete.
European Journal of Operational ResearchShortest paths in a network with time-dependent flow speeds
99 Citations2000Kiseok Sung, Michael G.H. Bell +2 more
A new model for Time-dependent Networks where the flow speeds of each link depend on time interval, is suggested and is more realistic since its solution maintains the Non-passing Property.
IEEE/ACM Transactions on NetworkingNew dynamic SPT algorithm based on a ball-and-string model
97 Citations2001P. Narvaez, Kai‐Yeung Siu +1 more
ACM Transactions on AlgorithmsExperimental analysis of dynamic all pairs shortest path algorithms
96 Citations2006Camil Demetrescu, Giuseppe F. Italiano
The results of an extensive computational study on dynamic algorithms for all pairs shortest path problems suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations.
Hierarchical optimization of optimal path finding for transportation applications
91 Citations1996Jing Ning, Yun-Wu Huang +1 more
Experimental results reveal that HEPV is more efficient than previously known path-finding approaches.
European Journal of Operational ResearchTime depending shortest-path problems with applications to railway networks
81 Citations1995Karl Nachtigall
A label correcting method is used to calculate the desired transit function for all starting times with one path search procedure, and generalize AI search techniques to get a more efficient one-to-one method.
Lecture notes in computer scienceMaterialization trade-offs in hierarchical shortest path algorithms
70 Citations1997Shashi Shekhar, Andrew Fetterer +1 more
Experiments with the Twin Cities metropolitan road-map show that materializing the shortest-path-cost view for the boundary graph provides the best savings in computation time, for a given amount of storage and a small number of fragments.
Path computation algorithms for advanced traveller information system (ATIS)
66 Citations2002Shashi Shekhar, A. Kohli +1 more
The main hypothesis is that estimator functions can improve the average-case performance of single-pair path computation when the length of the path is small compared to the diameter of the graph.
ACM Journal of Experimental AlgorithmicsExperimental analysis of dynamic algorithms for the single source shortest paths problem
59 Citations1998Daniele Frigioni, Mario Ioffreda +2 more
This paper performs an experimental analysis of three different algorithms: Dijkstra's algorithm, and the two output bounded algorithms proposed by Ramalingam and Reps in [30] and by Frigioni, Marchetti-Spaccamela and Nanni in [18], respectively.
Effective graph clustering for path queries in digital map databases
55 Citations1996Yun-Wu Huang, Jing Ning +1 more
Experimental evahration indicates that the novel graph clustering technique, called Spatial Partition Clustering (SPC), performs the best for the high-locality graphs (such as GIS maps), whereas the two-way partitioning approach performs thebest for no- Locality random graphs.
HiTi graph model of topographical road maps in navigation systems
54 Citations2002Sungwon Jung, Sakti Pramanik
This work proposes a new graph model named HiTi (hierarchical multi graph model), for efficiently computing an optimal minimum cost path, based on HiTi graph model, and empirically shows that the proposed algorithm performs far better than the traditional A* algorithm.
IRIS Research product catalog (Sapienza University of Rome)Fully dynamic output bounded single source shortest path problem
48 Citations1996Daniele Frigioni, Alberto Marchetti-Spaccamela +1 more
Symposium on Discrete AlgorithmsExperimental analysis of dynamic all pairs shortest path algorithms
45 Citations2004Camil Demetrescu, Stefano Emiliozzi +1 more
Lecture notes in computer scienceFATES: Finding A Time dEpendent Shortest path
34 Citations2002Hae Don Chon, Divyakant Agrawal +1 more
A distributed system, FATES, to manage data for moving objects in a two-dimensional space based on a grid model is developed and shows that FATES yields shorter average trip time when there is a more congested route in the domain space.
I/O-efficiency of shortest path algorithms: an analysis
28 Citations2003Bin Jiang
To establish the behavior of algorithms in a paging environment, the author analyzes the input/output (I/O) efficiency) of several representative shortest path algorithms, including single-course, multisource, and all pairs ones.
Learning to predict the duration of an automobile trip
27 Citations1998Simon J. Handley, Pat Langley +1 more
The use of machine learning and data mining to improve the prediction of travel times in an automobile is explored and it is suggested that 3-nearest neighbour substantially outperforms predictions available from existing digital maps.
Spatial data traversal in road map databases
9 Citations1994Jun Zhao, Ahmed S. Zaki
Using a probabilistic analysis, this paper shows that the graph indexing technique significantly improves the efficiency of constrained spatial queries.
An improved network clustering method for I/O-efficient query processing
8 Citations2000Sung-Ho Woo, Sung-Bong Yang
A network clustering method, called Network-Traversal Clustering (NTC) method, which assigns the nodes of a given network to disk pages with optimal disk-space utilization and a low edge-cut ratio and is suitable for the bulk loading operation into a network indexing structure.
Fully Dynamic Output Bounded Single Source Shortest Path Problem (Extended Abstract).
8 Citations1996Daniele Frigioni, Alberto Marchetti-Spaccamela +1 more
This work considers the problem of maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions and cost updates of edges and proposes fully dynamic algorithms with optimal space requirements and query time.