Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

8-2013

Abstract

In this paper, we consider a new problem in the context of road network databases, named Resource Constrained Best Upgrade Plan computation (BUP, for short). 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. Given a source and a destination in G, and a budget (resource constraint) B, the BUP problem 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 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

Real road networks, Resource Constraint, Road network, Shortest path, Transportation network, Weighted graph

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing | Transportation

Publication

Advances in Spatial and Temporal Databases: 13th International Symposium, SSTD 2013, Munich, Germany, August 21-23, 2013: Proceedings

Volume

8098

First Page

223

Last Page

240

ISBN

9783642402340

Identifier

10.1007/978-3-642-40235-7_13

Publisher

Springer Verlag

City or Country

Heidelberg

Additional URL

http://dx.doi.org/10.1007/978-3-642-40235-7_13

Download

Share

COinS