Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
GeoInformatica
Published in: GeoInformatica 2/2015

01-04-2015

Best upgrade plans for single and multiple source-destination pairs

Authors: Yimin Lin, Kyriakos Mouratidis

Published in: GeoInformatica | Issue 2/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article A Dilution-matching-encoding compaction of trajectories over road networks
next article High performance FPGA and GPU complex pattern matching over spatio-temporal streams

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
In case of tie between two alternative paths, we keep as p ∗ the one with the smallest C(R p*).
 
2
Note that in A(G c ) it is unambiguous whether the path passes via an upgraded or un-upgraded link between two nodes – similarly, it is clear how to measure the upgrade cost.
Table 2
Ranked paths for the two source-destination pairs in running example
No.
Dis.
Path
Cost
U p
p 1−1
53
{s 1, a 1, a 2, a 3, a 6, t 1}
24
(a 1, a 2),(a 2, a 3),(a 6, a 7)
p 1−2
58
{s 1, b 4, b 5, b 6, t 1}
10
(b 4, b 5)
p 1−3
58
{s 1, c 3, c 4, c 6, a 6, t 1}
31
(c 3, c 4),(a 6, a 7)
p 1−4
59
{s 1, c 4, c 6, a 6, t 1}
9
(a 6, a 7)
p 1−5
59
{s 1, b 4, c 7, t 1}
0
∅
p 1−6
59
{s 1, b 4, c 6, a 6, t 1}
9
(a 6, a 7)
p 1−7
60
{s 1, c 3, a 3, a 6, t 1}
9
(a 6, a 7)
p 1−8
60
{s 1, c 3, c 4, c 6, t 1}
9
(a 6, a 7)
p 1−9
60
{s 1, a 1, a 2, a 3, a 6, t 1}
14
(a 2, a 3),(a 6, a 7)
p 1−10
60
{s 1, a 1, a 2, a 3, a 6, t 1}
19
(a 1, a 2),(a 6, a 7)
p 1−11
60
{s 1, a 1, a 2, a 3, a 6, t 1}
15
(a 1, a 2),(a 2, a 3)
p 2−1
49
{s 2, a 3, a 6, a 7, t 2}
14
(a 2, a 3),(a 6, a 7)
p 2−2
56
{s 2, a 3, a 6, a 7, t 2}
5
(a 2, a 3)
p 2−3
56
{s 2, a 3, a 6, a 7, t 2}
9
(a 6, a 7)
 
3
Note that here SP is an umbrella concept covering any path that passes via the same nodes as SP, regardless of which edges are chosen for upgrade.
 
4
Note that Lemma 7 uses U c instead of U because it is applied on G c (not on G).
 
5
For completeness, we mention that a brute force evaluation of subsets of U c (after “Pruning+Preserver” reduction) in our default setting for single-pair BUP takes longer than 20sec, which is orders of magnitude slower than our methods, evaluated shortly.
 
Literature
1.
Alumur SA, Kara BY (2008) Network hub location problems: the state of the art. Eur J Oper Res 190(1):1–21CrossRef
2.
Amaldi E, Capone A, Cesana M, Malucelli F (2007) Optimization models for the radio planning of wireless mesh networks. In: Networking, pp 287–298
3.
Beasley JE, Christofides N (1989) An algorithm for the resource constrained shortest path problem. Networks 19:379–394CrossRef
4.
Ben-Moshe B, Omri E, Elkin M (2011) Optimizing budget allocation in graphs. In: CCCG
5.
Boorstyn R, Frank H (1977) Large-scale network topological optimization. IEEE Trans Commun 25(1):29–47CrossRef
6.
Campbell AM, Lowe TJ, Zhang L (2006) Upgrading arcs to minimize the maximum travel time in a network. Networks 47(2):72–80CrossRef
7.
Capone A, Elias J, Martignon F (2008) Models and algorithms for the design of service overlay networks. IEEE Trans Netw Serv Manag 5(3):143–156CrossRef
8.
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. The MIT Press and McGraw-Hill Book Company
9.
Deng K, Zhou X, Shen HT (2007) Multi-source skyline query processing in road networks. In: ICDE, pp 796–805
10.
Ding B, Yu JX, Qin L (2008) Finding time-dependent shortest paths over large graphs. In: EDBT, pp 205–216
11.
Dumitrescu I, Boland N (2003) Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem. Networks 42:135–153CrossRef
12.
Fan J, Ammar MH (2006) Dynamic topology configuration in service overlay networks: a study of reconfiguration policies. In: INFOCOM
13.
Handler GY, Zang I (1980) A dual algorithm for the constrained shortest path problem. Networks 10:293–309CrossRef
14.
Hassin R (1992) Approximation schemes for the restricted shortest path problem. Math Oper Res 17(1):36–42CrossRef
15.
Hills A (2001) Mentor: an algorithm for mesh network topological optimization and routing. IEEE Trans Commun 39(11):98–107
16.
Jain R, Walrand J (2010) An efficient nash-implementation mechanism for network resource allocation. Automatica 46(8):1276–1283CrossRef
17.
Jensen CS, Kolárvr J, Pedersen TB, Timko I (2003) Nearest neighbor queries in road networks. In: GIS, pp 1–8
18.
Johari R, Tsitsiklis JN (2004) Efficiency loss in a network resource allocation game. Math Oper Res 29(3):407–435CrossRef
19.
Jung S, Pramanik S (2002) An efficient path computation model for hierarchically structured topographical road maps, vol 14
20.
Kershenbaum A, Kermani P, Grover GA (1991) Mentor: an algorithm for mesh network topological optimization and routing. IEEE Trans Commun 39(4):503–513CrossRef
21.
Kriegel HP, Kröger P, Renz M, Schmidt T (2008) Hierarchical graph embedding for efficient query processing in very large traffic networks. In: SSDBM, pp 150–167
22.
Li Z, Mohapatra P (2007) On investigating overlay service topologies. Comput Netw 51(1):54–68CrossRef
23.
Lin Y, Mouratidis K (2013) Best upgrade plans for large road networks. In: SSTD, pp 223–240
24.
Lorenz DH, Raz D (2001) A simple efficient approximation scheme for the restricted shortest path problem. Oper Res Lett 28(5):213–219CrossRef
25.
Maillé P, Tuffin B (2004) Multi-bid auctions for bandwidth allocation in communication networks. In: INFOCOM
26.
Mehlhorn K, Ziegelmann M (2000) Resource constrained shortest paths. In: Algorithms - ESA 2000, vol 1879, pp 326–337
27.
Minoux M (1989) Networks synthesis and optimum network design problems: Models, solution methods and applications. Networks 19:313–360CrossRef
28.
Nepal KP, Park D, Choi CH (2009) Upgrading arc median shortest path problem for an urban transportation network. J Transp Eng 135(10):783–790CrossRef
29.
Papadias D, Zhang J, Mamoulis N, Tao Y (2003) Query processing in spatial network databases. In: VLDB, pp 802–813
30.
de Queirós Vieira Martins E, Pascoal MMB (2003) A new implementation of yen’s ranking loopless paths algorithm. 4OR 1 (2)
31.
Ratnasamy S, Handley M, Karp RM, Shenker S (2002) Topologically-aware overlay construction and server selection. In: INFOCOM
32.
Ribeiro CC, Minoux M (1985) A heuristic approach to hard constrained shortest path problems. Discret Appl Math 10(2):125–137CrossRef
33.
Roy S, Pucha H, Zhang Z, Hu YC, Qiu L (2007) Overlay node placement: Analysis, algorithms and impact on applications. In: ICDCS, p 53
34.
Shahabi C, Kolahdouzan MR, Sharifzadeh M (2003) A road network embedding technique for k-nearest neighbor search in moving object databases. GeoInformatica 7(3):255–273CrossRef
35.
Stojanovic D, Papadopoulos AN, Predic B, Djordjevic-Kajan S, Nanopoulos A (2008) Continuous range monitoring of mobile objects in road networks. Data Knowl Eng 64(1):77–100CrossRef
36.
Zhang L (2005) Upgrading arc problem with budget constraint. In: 43rd annual Southeast regional conference - vol 1, pp 150–152
Metadata
Title
Best upgrade plans for single and multiple source-destination pairs
Authors
Yimin Lin
Kyriakos Mouratidis
Publication date
01-04-2015
Publisher
Springer US
Published in
GeoInformatica / Issue 2/2015
Print ISSN: 1384-6175
Electronic ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-014-0219-1

Other articles of this Issue 2/2015

GeoInformatica 2/2015 Go to the issue

OriginalPaper

Adaptive generation of variable-scale network maps for small displays based on line density distribution

OriginalPaper

Impact of data representation rules on the robustness of topological relation evaluation

OriginalPaper

On reverse-k-nearest-neighbor joins

EditorialNotes

Special issue on spatial and temporal database management

OriginalPaper

A Dilution-matching-encoding compaction of trajectories over road networks

OriginalPaper

GMOBench: Benchmarking generic moving objects