Effective indexing for approximate constrained shortest path queries on large road networks

• Main Authors: Wang, Sibo, Xiao, Xiaokui, Yang, Yin, Lin, Wenqing
• 其他作者: School of Computer Science and Engineering
• 格式: Conference or Workshop Item
• 語言: English
• 出版: 2017
• 主題: Constrained shortest path; Large road networks
• 在線閱讀: https://hdl.handle.net/10356/81353; http://hdl.handle.net/10220/43454

In a constrained shortest path (CSP) query, each edge in the road network is associated with both a length and a cost. Given an origin s, a destination t, and a cost constraint θ, the goal is to find the shortest path from s to t whose total cost does not exceed θ. Because exact CSP is NP-hard, prev...