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

• Main Authors: Wang, Sibo, Xiao, Xiaokui, Yang, Yin, Lin, Wenqing
• Other Authors: School of Computer Science and Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2017
• Subjects: Constrained shortest path; Large road networks
• Online Access: https://hdl.handle.net/10356/81353; http://hdl.handle.net/10220/43454
• Institution: Nanyang Technological University

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...