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.
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- M. Sharifzadeh, M. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. The VLDB journal, pages 765--787, 2008. Google ScholarDigital Library
- Web site. http://db64.cs.technion.ac.il/tars/.Google Scholar
- 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 Scholar
Index Terms
Interactive traffic-aware route search on smartphones
Recommendations
WISER: a web-based interactive route search system for smartphones
WWW '12 Companion: Proceedings of the 21st International Conference on World Wide WebMany smartphones, nowadays, use GPS to detect the location of the user, and can use the Internet to interact with remote location-based services. These two capabilities support online navigation that incorporates search. In this demo we presents WISER---...
TARS: traffic-aware route search
In a traffic-aware route search (TARS), the user provides start and target locations and sets of search terms. The goal is to find the fastest route from the start location to the target via geographic entities (points of interest) that correspond to ...
Interactive route search in the presence of order constraints
A route search is an enhancement of an ordinary geographic search. Instead of merely returning a set of entities, the result is a route that goes via entities that are relevant to the search. The input to the problem consists of several search queries, ...
Comments