Skip to main content
Top

2016 | OriginalPaper | Chapter

Reconstruct Underground Infrastructure Networks Based on Uncertain Information

Authors : Marco de Koning, Frank Phillipson

Published in: Innovations for Community Services

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

This paper focuses on developing methods to reconstruct the physical path of underground infrastructure networks. These reconstructions are based on the structure of the network, start and endpoints and the structure of an underlying network. This data is partly considered unreliable or uncertain. Two methods are presented to realise the reconstruction. The first method finds a path of given length in a directed graph by applying a modified version of Yen’s algorithm for finding K-shortest simple paths in a directed graph. A second, so-called Bottom-up approach is developed which aims to take advantage of the structure of the underlying network. The developed methods are applied on a series of examples for comparison.

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!

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!

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!

Literature
1.
go back to reference Aljazzar, H., Leue, S.: K\(^*\): a heuristic search algorithm for finding the \(k\) shortest paths. Artif. Intell. 175, 2129–2154 (2011). ElsevierMathSciNetCrossRefMATH Aljazzar, H., Leue, S.: K\(^*\): a heuristic search algorithm for finding the \(k\) shortest paths. Artif. Intell. 175, 2129–2154 (2011). ElsevierMathSciNetCrossRefMATH
3.
go back to reference Eppstein, D.: Finding the k shortest paths. In: 1994 Proceedings of 35th Annual Symposium on Foundations of Computer Science, pp. 154–165. IEEE (1994) Eppstein, D.: Finding the k shortest paths. In: 1994 Proceedings of 35th Annual Symposium on Foundations of Computer Science, pp. 154–165. IEEE (1994)
4.
go back to reference Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef
5.
go back to reference Hershberger, J., Maxel, M., Suri, S.: Finding the k shortest simple paths: a new algorithm and its implementation. ACM Trans. Algorithms (TALG) 3(4), 45 (2007)MathSciNetCrossRef Hershberger, J., Maxel, M., Suri, S.: Finding the k shortest simple paths: a new algorithm and its implementation. ACM Trans. Algorithms (TALG) 3(4), 45 (2007)MathSciNetCrossRef
6.
go back to reference Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth? In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science, pp. 252–259. IEEE (2001) Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth? In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science, pp. 252–259. IEEE (2001)
8.
go back to reference Jiménez, V.M., Marzal, A.: Computing the K shortest paths: a new algorithm and an experimental comparison. In: Vitter, J.S., Zaroliagis, C.D. (eds.) WAE 1999. LNCS, vol. 1668, pp. 15–29. Springer, Heidelberg (1999). doi:10.1007/3-540-48318-7_4 CrossRef Jiménez, V.M., Marzal, A.: Computing the K shortest paths: a new algorithm and an experimental comparison. In: Vitter, J.S., Zaroliagis, C.D. (eds.) WAE 1999. LNCS, vol. 1668, pp. 15–29. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48318-7_​4 CrossRef
9.
go back to reference Jiménez, V.M., Marzal, A.: A lazy version of Eppstein’s K shortest paths algorithm. In: Jansen, K., Margraf, M., Mastrolilli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol. 2647, pp. 179–191. Springer, Heidelberg (2003). doi:10.1007/3-540-44867-5_14 CrossRef Jiménez, V.M., Marzal, A.: A lazy version of Eppstein’s K shortest paths algorithm. In: Jansen, K., Margraf, M., Mastrolilli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol. 2647, pp. 179–191. Springer, Heidelberg (2003). doi:10.​1007/​3-540-44867-5_​14 CrossRef
10.
go back to reference Neumann, N., Phillipson, F.: Connecting points to a set of line segments in infrastructure design problems. In: 21st European Conference on Networks and Optical Communications (NOC 2016), Lisbon, Portugal (2016) Neumann, N., Phillipson, F.: Connecting points to a set of line segments in infrastructure design problems. In: 21st European Conference on Networks and Optical Communications (NOC 2016), Lisbon, Portugal (2016)
12.
go back to reference Phillipson, F.: Efficient algorithms for infrastructure networks: planning issues and economic impact. Ph.D. thesis, VU Amsterdam (2014) Phillipson, F.: Efficient algorithms for infrastructure networks: planning issues and economic impact. Ph.D. thesis, VU Amsterdam (2014)
Metadata
Title
Reconstruct Underground Infrastructure Networks Based on Uncertain Information
Authors
Marco de Koning
Frank Phillipson
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-49466-1_4

Premium Partner