In this paper, we study Resource Constrained Best Upgrade Plan (BUP) computation in road network databases. Consider a transportation network (weighted graph) G where a subset of the edges are upgradable, i.e., for each such edge there is a cost, which if spent, the weight of the edge can be reduced to a specific new value. In the single-pair version of BUP, the input includes a source and a destination in G, and a budget B (resource constraint). The goal is to identify which upgradable edges should be upgraded so that the shortest path distance between source and destination (in the updated network) is minimized, without exceeding the available budget for the upgrade. In the multiple-pair version of BUP, a set Q of source-destination pairs is given, and the problem is to choose for upgrade those edges that lead to the smallest sum of shortest path distances across all pairs in Q, subject to budget constraint B. In addition to transportation networks, the BUP query arises in other domains too, such as telecommunications. We propose a framework for BUP processing and evaluate it with experiments on large, real road networks.
Road network, Resource constraint, Network upgrade
Computer Sciences | Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
GeoInformatica: Special Issue on the Best of SSTD 2013
Lin, Yimin and MOURATIDIS, Kyriakos.
Best Upgrade Plans for Single and Multiple Source-Destination Pairs. (2015). GeoInformatica: Special Issue on the Best of SSTD 2013. 19, (2), 365-404. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2274
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.