Efficient evaluation of shortest travel-time path queries in road networks by optimizing waypoints in route requests through spatial mashups

Detian Zhang, Chi Yin Chow, Qing Li, An Liu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

3 Citations (Scopus)


In the real world, the route with the shortest travel time in a road network is more meaningful than that with the shortest network distance for location-based services (LBS). However, not every LBS provider has adequate resources to compute/estimate travel time for routes by themselves. A cost-effective way for LBS providers to estimate travel time for routes is to issue external requests to Web mapping services (e.g., Google Maps, Bing Maps, and MapQuest Maps). Due to the high cost of processing such external requests and the usage limits of Web mapping services, we take the advantage of direction sharing and waypoints supported by Web mapping services to reduce the number of external requests and the query response time for shortest travel-time route queries in this paper. We model the problem of selecting the optimal waypoints for an external route request as finding the longest simple path in a weighted bipartite digraph. As it is a NP-complete problem, we propose a greedy algorithm to find the best set of waypoints in an external route request. We evaluate the performance of our approach using real Web mapping services, a real road network, real and synthetic data sets. Experimental results show the efficiency, scalability, and applicability of our approach.

Original languageEnglish
Title of host publicationWeb Technologies and Applications - 18th Asia-Pacific Web Conference, APWeb 2016, Proceedings
EditorsGuanfeng Liu, Feifei Li, Kyuseok Shim, Kai Zheng
Number of pages12
ISBN (Print)9783319458137
Publication statusPublished - 1 Jan 2016
Externally publishedYes
Event18th Asia-Pacific Web Conference on Web Technologies and Applications, APWeb 2016 - Suzhou, China
Duration: 23 Sep 201625 Sep 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9931 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th Asia-Pacific Web Conference on Web Technologies and Applications, APWeb 2016


  • Direction sharing
  • Location-based services
  • Spatial mashups
  • Waypoints
  • Web mapping services

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this