Publication Type

Journal Article

Version

submittedVersion

Publication Date

4-2015

Abstract

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.

Keywords

Road network, Resource constraint, Network upgrade

Discipline

Computer Sciences | Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

GeoInformatica: Special Issue on the Best of SSTD 2013

Volume

19

Issue

2

First Page

365

Last Page

404

ISSN

1384-6175

Identifier

10.1007/s10707-014-0219-1

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1007/s10707-014-0219-1

Download

Share

COinS