More Web Proxy on the site http://driver.im/

research-article

Navigation made personal: inferring driving preferences from GPS traces

Authors:

Daniel Delling,

Andrew V. Goldberg,

Moises Goldszmidt,

Renato F. WerneckAuthors Info & Claims

SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

Article No.: 31, Pages 1 - 9

https://doi.org/10.1145/2820783.2820808

Published: 03 November 2015 Publication History

Abstract

All current navigation systems return efficient source-to-destination routes assuming a "one-size-fits-all" set of objectives, without addressing most personal preferences. Although they allow some customization (like "avoid highways" or "avoid tolls"), the choices are very limited and require some sophistication on the part of the user. In this paper we present, implement, and test a framework that generates personalized driving directions by automatically analyzing users' GPS traces. Our approach learns cost functions using coordinate descent, leveraging a state-of-the-art route planning engine for efficiency. In an extensive experimental study, we show that this framework infers user-specific driving preferences, significantly improving the route quality. Our approach can handle continental-sized inputs (with tens of millions of vertices and arcs) and is efficient enough to be run on an autonomous device (such as a car navigation system) preserving user privacy.

References

[1]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical hub labelings for shortest paths. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), volume 7501 of Lecture Notes in Computer Science, pages 24--35. Springer, 2012.

Digital Library

[2]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Alternative Routes in Road Networks. ACM Journal of Experimental Algorithmics, 18(1):1--17, 2013.

Digital Library

[3]

M. Agrawala and C. Stolte. Rendering effective route maps: improving usability through generalization. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, pages 241--249. ACM, 2001.

Digital Library

[4]

A. Auslender. Optimisation Métodes Numériques. Masson, Paris, 1976.

[5]

R. Bader, J. Dees, R. Geisberger, and P. Sanders. Alternative Route Graphs in Road Networks. In A. Marchetti-Spaccamela and M. Segal, editors, Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS'11), volume 6595 of Lecture Notes in Computer Science, pages 21--32. Springer, 2011.

Digital Library

[6]

H. Bast, D. Delling, A. V. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route Planning in Transportation Networks. CoRR, abs/1504.05140, 2015.

[7]

H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast Routing in Road Networks with Transit Nodes. Science, 316(5824):566, 2007.

[8]

D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, Massachusetts, second edition, 1999.

[9]

J. Biagioni and J. Eriksson. Map inference in the face of noise and disparity. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, pages 79--88. ACM, 2012.

Digital Library

[10]

S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. On map-matching vehicle tracking data. In Proceedings of the 31st International Conference on Very Large Data Bases, pages 853--864. VLDB Endowment, 2005.

Digital Library

[11]

K.-P. Chang, L.-Y. Wei, M.-Y. Yeh, and W.-C. Peng. Discovering personalized routes from trajectories. In Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Location-Based Social Networks, pages 33--40. ACM, 2011.

Digital Library

[12]

N. Cohn. Real-time traffic information and navigation. Transportation Research Record: Journal of the Transportation Research Board, 2129(1):129--135, 2009.

[13]

E. R. da Silva, C. de Baptista, L. Menezes, and A. Paiva. Personalized path finding in road networks. In Proceedings of the Fourth International Conference on Networked Computing and Advanced Information Management, volume 2, pages 586--591. IEEE, 2008.

Digital Library

[14]

D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 376--387. Springer, 2011.

Digital Library

[15]

D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable Route Planning in Road Networks. Transportation Science, 2015. online preprint.

[16]

D. Delling, M. Kobitzsch, and R. F. Werneck. Customizing driving directions with GPUs. In Proceedings of the 20th International Conference on Parallel Processing (Euro-Par 2014), volume 8632 of Lecture Notes in Computer Science, pages 728--739. Springer, 2014.

[17]

D. Delling and R. F. Werneck. Faster customization of road networks. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 30--42. Springer, 2013.

[18]

E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numer. Math., 1:269--271, 1959.

Digital Library

[19]

M. Dimond, G. Smith, and J. Goulding. Improving route prediction through user journey detection. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 466--469. ACM, 2013.

Digital Library

[20]

D. H. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 10:112--122, 1973.

[21]

M. Duckham and L. Kulik. "simplest" paths: Automated route selection for navigation. In Spatial Information Theory. Foundations of Geographic Information Science, pages 169--185. Springer, 2003.

[22]

S. Funke, A. Nusser, and S. Storandt. On k-path covers and their applications. In Proceedings of the 40th International Conference on Very Large Databases (VLDB 2014), pages 893--902, 2014.

Digital Library

[23]

R. Geisberger, M. Rice, P. Sanders, and V. Tsotras. Route Planning with Flexible Edge Restrictions. ACM Journal of Experimental Algorithmics, 17(1):1--20, 2012.

Digital Library

[24]

M. Kobitzsch. HiDAR: An alternative approach to alternative routes. In Proceedings of the 21st Annual European Symposium on Algorithms (ESA'13), volume 8125 of Lecture Notes in Computer Science, pages 613--624. Springer, 2013.

[25]

J. Krumm and D. Rouhana. Placer: semantic place labels from diary data. In Proceedings of the 2013 ACM international Joint Conference on Pervasive and Ubiquitous Computing, pages 163--172. ACM, 2013.

Digital Library

[26]

J. Letchner, J. Krumm, and E. Horvitz. Trip router with individualized preferences (trip): Incorporating personalization into route planning. In Proceedings of the National Conference on Artificial Intelligence, volume 21, page 1795. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.

Digital Library

[27]

R. Maxunder, J. H. Friedman, and T. Hastie. SparseNet: Coordinate descent with nonconvex penalties. Journal of the American Statistical Association, 106(495), 2011.

[28]

P. Newson and J. Krumm. Hidden markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 336--343. ACM, 2009.

Digital Library

[29]

S. Rogers, P. Langley, and C. Wilson. Mining GPS data to augment road models. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 104--113. ACM, 1999.

Digital Library

[30]

R. E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197--227, 1990.

Digital Library

[31]

C. Sommer. Shortest-path queries in static networks. ACM Computing Surveys, 46:547--560, 2014.

Digital Library

[32]

J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive: driving directions based on taxi trajectories. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 99--108. ACM, 2010.

Digital Library

[33]

B. D. Ziebart, A. L. Maas, A. K. Dey, and J. A. Bagnell. Navigate like a cabbie: Probabilistic reasoning from observed context-aware behavior. In Proceedings of the 10th International Conference on Ubiquitous Computing, pages 322--331. ACM, 2008.

Digital Library

Cited By

Yang BXiong YChen XFeng XWang MMa JSerra ESpezzano F(2024)ST-ECP: A Novel Spatial-Temporal Framework for Energy Consumption Prediction of Vehicle TrajectoryProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679807(2807-2816)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679807
Liu SWang ZZhang YYang H(2024)Anomalous ride-hailing driver detection with deep transfer inverse reinforcement learningTransportation Research Part C: Emerging Technologies10.1016/j.trc.2023.104466159(104466)Online publication date: Feb-2024
https://doi.org/10.1016/j.trc.2023.104466
Canoy RBucarey VMandi JMulamba MMolenbruch YGuns T(2024)Probability estimation and structured output prediction for learning preferences in last mile deliveryComputers & Industrial Engineering10.1016/j.cie.2024.109932189(109932)Online publication date: Mar-2024
https://doi.org/10.1016/j.cie.2024.109932
Show More Cited By

Index Terms

Navigation made personal: inferring driving preferences from GPS traces
1. Computing methodologies
  1. Machine learning
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics

Recommendations

Rating Bias and Preference Acquisition

Personalized systems and recommender systems exploit implicitly and explicitly provided user information to address the needs and requirements of those using their services. User preference information, often in the form of interaction logs and ratings ...
Personalized recommendation based on the personal innovator degree
RecSys '09: Proceedings of the third ACM conference on Recommender systems

This paper proposes a novel Collaborative Filtering scheme; it focuses on the dynamics and precedence of user preference to recommend items that match the latest preference of the target user. In predicting which items this user will purchase in the ...
New Recommendation Techniques for Multicriteria Rating Systems

Traditional single-rating recommender systems have been successful in a number of personalization applications, but the research area of multicriteria recommender systems has been largely untouched. Taking full advantage of multicriteria ratings in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2015

646 pages

ISBN:9781450339674

DOI:10.1145/2820783

General Chairs:
Mohamed Ali
University of Washington, Tacoma
,
Yan Huang
University of North Texas
,
Program Chairs:
Michael Gertz
Heidelberg University, Germany
,
Matthias Renz
LMU Munich, Germany
,
Jagan Sankaranarayanan
NEC Labs

Copyright © 2015 ACM.

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 the author(s) 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].

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSPATIAL'15

Sponsor:

SIGSPATIAL

SIGSPATIAL'15: 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 3 - 6, 2015

Washington, Seattle

Acceptance Rates

SIGSPATIAL '15 Paper Acceptance Rate 38 of 212 submissions, 18%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
342
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang BXiong YChen XFeng XWang MMa JSerra ESpezzano F(2024)ST-ECP: A Novel Spatial-Temporal Framework for Energy Consumption Prediction of Vehicle TrajectoryProceedings of the 33rd ACM International Conference on Information and Knowledge Management10.1145/3627673.3679807(2807-2816)Online publication date: 21-Oct-2024
https://dl.acm.org/doi/10.1145/3627673.3679807
Liu SWang ZZhang YYang H(2024)Anomalous ride-hailing driver detection with deep transfer inverse reinforcement learningTransportation Research Part C: Emerging Technologies10.1016/j.trc.2023.104466159(104466)Online publication date: Feb-2024
https://doi.org/10.1016/j.trc.2023.104466
Canoy RBucarey VMandi JMulamba MMolenbruch YGuns T(2024)Probability estimation and structured output prediction for learning preferences in last mile deliveryComputers & Industrial Engineering10.1016/j.cie.2024.109932189(109932)Online publication date: Mar-2024
https://doi.org/10.1016/j.cie.2024.109932
Mesa JMontoya ARamos-Pollán RToro M(2023)A two-stage data-driven metaheuristic to predict last-mile delivery route sequencesEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106653125:COnline publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.106653
Canoy RBucarey VMandi JGuns T(2023)Learn and route: learning implicit preferences for vehicle routingConstraints10.1007/s10601-023-09363-228:3(363-396)Online publication date: 11-Oct-2023
https://doi.org/10.1007/s10601-023-09363-2
Hou XLuo LCai W(2022)Distribution-Based Weights Estimation for Map Matching AlgorithmsIEEE Systems Journal10.1109/JSYST.2022.315026716:3(4256-4266)Online publication date: Sep-2022
https://doi.org/10.1109/JSYST.2022.3150267
Goje BNayak P(2022)A Deep Survey on Vehicular Route Guidance Algorithms and Implemented Systems2022 3rd International Conference on Smart Electronics and Communication (ICOSEC)10.1109/ICOSEC54921.2022.9951975(689-696)Online publication date: 20-Oct-2022
https://doi.org/10.1109/ICOSEC54921.2022.9951975
Liu SJiang H(2022)Personalized route recommendation for ride-hailing with deep inverse reinforcement learning and real-time traffic conditionsTransportation Research Part E: Logistics and Transportation Review10.1016/j.tre.2022.102780164(102780)Online publication date: Aug-2022
https://doi.org/10.1016/j.tre.2022.102780
Tavakoli ABoukhechba MHeydarian A(2021)Leveraging Ubiquitous Computing for Empathetic Routing: A Naturalistic Data-driven ApproachExtended Abstracts of the 2021 CHI Conference on Human Factors in Computing Systems10.1145/3411763.3451693(1-6)Online publication date: 8-May-2021
https://dl.acm.org/doi/10.1145/3411763.3451693
Rehrl KKranzinger SGröchenig S(2020)Which quality is a route? A methodology for assessing route quality using spatio‐temporal metricsTransactions in GIS10.1111/tgis.1270525:2(869-896)Online publication date: 13-Nov-2020
https://doi.org/10.1111/tgis.12705
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents