research-article

A new perspective on efficient and dependable vehicle routing

Authors:

Dieter Pfoser,

Alexandros Efentakis,

Agnès Voisard,

Carola WenkAuthors Info & Claims

GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Pages 388 - 391

https://doi.org/10.1145/1653771.1653826

Published: 04 November 2009 Publication History

Get Access

Abstract

The essential elements of any navigation system are a shortest-path algorithm and accurate map data. The contribution of this work is two-fold. First, the HBA* algorithm, an efficient shortest-path algorithm is presented that mimics human driving behavior by exploiting road network hierarchies. Second, in a thorough performance study dynamic travel times are introduced to replace the unreliable static speed types currently used in connection with road network datasets.

References

[1]

P. Bovy and E. Stern. Route Choice: Wayfinding in Transportation Networks. Kluwer Academic Publishers, Dordrecht, 1990.

Crossref

Google Scholar

[2]

S. Brakatsoulas, D. Pfoser, R. Sallas, and C. Wenk. On Map-Matching Vehicle Tracking Data. In Proc. 31st VLDB conf., pages 853--864, 2005.

Digital Library

Google Scholar

[3]

A. Car and A. U. Frank. General principles of hierarchical spatial reasoning - the case of wayfinding. In Proc. 6th SDH symp., 1994.

Google Scholar

[4]

E. W. Dikjstra. A Note on two Problems in Connexion with Graphs. Numerische Mathematik, 1:269--271, 1959.

Digital Library

Google Scholar

[5]

L. Fu, D. Sun, and L. R. Rilett. Heuristic shortest path algorithms for transportation applications: state of the art. Comput. Oper. Res., 33(11):3324--3343, 2006.

Digital Library

Google Scholar

[6]

P. Hart, N. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Trans. Syst. Science and Cybernetics, 4(2):100--107, 1968.

Crossref

Google Scholar

[7]

N. Nilsson. Principles of Artificial Intelligence. Tioga, Palo Alto, California, 1980.

Digital Library

Google Scholar

[8]

D. Pfoser, N. Tryfona, and A. Voisard. Dynamic Travel Time Maps - Enabling Efficient Navigation. In Proc. 18th SSDBM conf., pages 369--378, 2006.

Digital Library

Google Scholar

[9]

D. Pfoser, S. Brakatsoulas, P. Brosch, M. Umlauft, N. Tryfona, and G. Tsironis. Dynamic Travel Time Provision for Road Networks. In Proc. 16th ACM SIG SPATIAL conf., pages 475--478, 2008.

Digital Library

Google Scholar

[10]

I. Pohl. Bi-directional search. Machine Intelligence, 6, 1971.

Google Scholar

[11]

P. Sanders and D. Schultes. Highway hierarchies hasten exact shortest path queries. In Proc. 17th ESA symp., pages 568--579, 2005.

Digital Library

Google Scholar

[12]

S. Shekhar, A. Fetterer, and B. Goyal. Materialization trade-offs in hierarchical shortest path algorithms. In Proc. 5th SSD smyp., pages 94--111, 1997.

Digital Library

Google Scholar

Cited By

View all

IMIS research team (2012)Institute for the management of information systems Athena research centerACM SIGMOD Record10.1145/2206869.220688141:1(61-66)Online publication date: 25-Apr-2012
https://dl.acm.org/doi/10.1145/2206869.2206881
Efentakis APfoser DVoisard A(Vonu) P(2011)Efficient data management in support of shortest-path computationProceedings of the 4th ACM SIGSPATIAL International Workshop on Computational Transportation Science10.1145/2068984.2068990(28-33)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1145/2068984.2068990

Index Terms

A new perspective on efficient and dependable vehicle routing
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Autonomous vehicle routing in multiple intersections
ASPDAC '19: Proceedings of the 24th Asia and South Pacific Design Automation Conference

Advancements in artificial intelligence and Internet of Things indicates the realization of commercial autonomous vehicles is almost ready. With autonomous vehicles comes new approaches in solving some of the current traffic problems such as fuel ...
Connected Vehicle Enhanced Vehicle Routing with Intersection Turning Cost Estimation
2018 21st International Conference on Intelligent Transportation Systems (ITSC)
On arterial corridors, due to traffic signals and vehicle demands at all different approaches, traffic conditions can be very different across lanes. Vehicular queues and average speed at different lanes, especially lane groups with different turns, can ...
Modeling and analysis of the coordinated vehicle routing problem

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2009

575 pages

ISBN:9781605586496

DOI:10.1145/1653771

General Chairs:
Ouri Wolfson
University of Illinois at Chicago
,
Divyakant Agrawal
University of California, Santa Barbara
,
Chang-Tien Lu
Virginia Tech

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

GIS '09

Sponsor:

SIGSPATIAL

GIS '09: 17th SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 4 - 6, 2009

Washington, Seattle

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
16
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

IMIS research team (2012)Institute for the management of information systems Athena research centerACM SIGMOD Record10.1145/2206869.220688141:1(61-66)Online publication date: 25-Apr-2012
https://dl.acm.org/doi/10.1145/2206869.2206881
Efentakis APfoser DVoisard A(Vonu) P(2011)Efficient data management in support of shortest-path computationProceedings of the 4th ACM SIGSPATIAL International Workshop on Computational Transportation Science10.1145/2068984.2068990(28-33)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1145/2068984.2068990

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Autonomous vehicle routing in multiple intersections

Connected Vehicle Enhanced Vehicle Routing with Intersection Turning Cost Estimation

Modeling and analysis of the coordinated vehicle routing problem