skip to main content
10.1145/2442810.2442812acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
research-article

Interactive traffic-aware route search on smartphones

Authors Info & Claims
Published:06 November 2012Publication History

ABSTRACT

Route search is an application for planning an efficient route via points of interest specified by search terms. Essentially, the search requires to find the fastest route, from the location of the user to a specified destination, through geographical entities whose type is indicated by the search terms, e.g., a route via a "Coffee Shop" and a "Pharmacy". To that end, it is essential to take into account traffic conditions and temporal constraints, such as opening and closing hours of institutes and businesses. We assume that the search is applied under conditions of uncertainty where a user may discover that she is unsatisfied with the visited entity only upon arrival at the point of interest. Thus, it may be required to visit several entities of the same type till discovering one that satisfies the user. In an interactive search, the user provides feedback after visiting an entity, to indicate when there is no need to go via additional entities of the same type. We show how interactive route search, suitable to be applied on smartphones, can be used for traffic aware route search under conditions of uncertainty and we provide effective heuristics for computing a route interactively.

References

  1. D. Bertsimas and D. Simchi-Levi. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Journal of Operational Research, 44(2):286--304, 1996.Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. H. Chen, W.-S. Ku, M.-T. Sun, and R. Zimmermann. The multi-rule partial sequenced route query. In Proceedings of the 16th ACM SIGSPATIAL GIS, pages 1--10, Irvine, California, 2008. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. H. Chen, W.-S. Ku, M.-T. Sun, and R. Zimmermann. The partial sequenced route query with traveling rules in road networks. Geoinformatica, 15(3):541--569, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. F. Cheng, D. Hadjieleftheriou, M. Kollios, and G. Teng. On trip planning queries in spatial databases. In Proceedings of the 9th International Symposium on Spatial and Temporal Databases, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. L. Feifei, C. Dihan, H. Marios, K. George, and T. Shang-Hua. On trip planning queries in spatial databases. In SSTD, pages 923--923, 2005.Google ScholarGoogle Scholar
  6. R. Friedman, I. Hefez, Y. Kanza, R. Levin, E. Safra, and Y. Sagiv. Wiser: a web-based interactive route search system for smartphones. In Proceedings of the 21st international conference on World Wide Web, pages 337--340, Lyon, France, 2012. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. I. Hefez, Y. Kanza, and R. Levin. Tarsius: a system for traffic-aware route search under conditions of uncertainty. In ACM SIGSPATIAL GIS, Chicago, IL, USA, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. A. Hill and W. Benton. Modeling intra-city time-dependent travel speeds for vehicle scheduling problems. The Journal of the Operational Research Society, 43(4):343--351, 1992.Google ScholarGoogle ScholarCross RefCross Ref
  9. Y. Kanza, R. Levin, E. Safra, and Y. Sagiv. An interactive approach to route search. In Proceedings of the 17th ACM SIGSPATIAL GIS, Seattle, Washington, USA, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Y. Kanza, R. Levin, E. Safra, and Y. Sagiv. Interactive route search in the presence of order constraints. Proc. VLDB Endow., 3(1-2), Sept. 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Y. Kanza, E. Safra, and Y. Sagiv. Route search over probabilistic geospatial data. In Proceedings of the 11th International Symposium on Advances in Spatial and Temporal Databases, SSTD '09, pages 153--170, Aalborg, Denmark, 2009. Springer-Verlag. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Y. Kanza, E. Safra, Y. Sagiv, and Y. Doytsher. Heuristic algorithms for route-search queries over geographical data. In Proceedings of the 16th ACM SIGSPATIAL GIS, pages 1--10, Irvine, California, USA, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. E. Safra, Y. Kanza, N. Dolev, Y. Sagiv, and Y. Doytsher. Computing a k-route over uncertain geographical data. In Proceedings of the 10th International Symposium on Advances in Spatial and Temporal Databases (SSTD), Boston (MA, USA), pages 276--293, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. M. Sharifzadeh, M. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. The VLDB journal, pages 765--787, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Web site. http://db64.cs.technion.ac.il/tars/.Google ScholarGoogle Scholar
  16. T. V. Woensel, L. Kerbache, H. Peremans, and N. Vandaele. A queuing framework for routing problems with time-dependent travel times. Journal of Mathematical Modeling and Algorithms Special Issue on Quantitative Aspects of Transportation and Logistics, 2005.Google ScholarGoogle Scholar

Index Terms

  1. Interactive traffic-aware route search on smartphones

      Recommendations

      Comments

      Login options

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

      Sign in
      • Published in

        cover image ACM Conferences
        MobiGIS '12: Proceedings of the First ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems
        November 2012
        112 pages
        ISBN:9781450316996
        DOI:10.1145/2442810
        • Conference Chair:
        • Chi-Yin Chow

        Copyright © 2012 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 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: 6 November 2012

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader