Skip to main content
Erschienen in: Soft Computing 4/2020

05.01.2019 | Focus

Uncertain random shortest path problem

verfasst von: Yuhong Sheng, Xuehui Mei

Erschienen in: Soft Computing | Ausgabe 4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The shortest path is an important problem in network optimization theory. This paper considers the shortest path problem under the situation where weights of edges in a network include both uncertainty and randomness and focuses on the case that the weights of edges are expressed by uncertain random variables. Some optimization models based on chance theory are proposed in order to find the shortest path which fully reflects uncertain and random information. This paper proposes also an intelligent algorithm to calculate the shortest path for an uncertain random network. A numerical example is given to illustrate its effectiveness.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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 "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!

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!

Literatur
Zurück zum Zitat Balinski ML (1961) Fixed cost transportation problem. Nav Res Logist Q 8(1):41–54MATH Balinski ML (1961) Fixed cost transportation problem. Nav Res Logist Q 8(1):41–54MATH
Zurück zum Zitat Bellman E (1958) On a routing problem. Q Appl Math 16(1):87–90MATH Bellman E (1958) On a routing problem. Q Appl Math 16(1):87–90MATH
Zurück zum Zitat Dijkstra EW (1959) A note on two problems in connection with graphs. Numer Math 1(1):269–271MathSciNetMATH Dijkstra EW (1959) A note on two problems in connection with graphs. Numer Math 1(1):269–271MathSciNetMATH
Zurück zum Zitat Ding SB (2014) Uncertain minimum cost flow problem. Soft Comput 18(11):2201–2207MATH Ding SB (2014) Uncertain minimum cost flow problem. Soft Comput 18(11):2201–2207MATH
Zurück zum Zitat Dreyfus S (1969) An appraisal of some shortest path algorithms. Oper Res 17(3):359–412MATH Dreyfus S (1969) An appraisal of some shortest path algorithms. Oper Res 17(3):359–412MATH
Zurück zum Zitat Dubois D, Prade H (1980) Fuzzy sets and systems: theory and applications. Academic Press, New YorkMATH Dubois D, Prade H (1980) Fuzzy sets and systems: theory and applications. Academic Press, New YorkMATH
Zurück zum Zitat Floyd RW (1962) Algorithm-97-shortest path. Comm Assoc Comput Mach 5(6):345 Floyd RW (1962) Algorithm-97-shortest path. Comm Assoc Comput Mach 5(6):345
Zurück zum Zitat Frank H (1969) Shortest paths in probability graphs. Oper Res 17(4):583–599MATH Frank H (1969) Shortest paths in probability graphs. Oper Res 17(4):583–599MATH
Zurück zum Zitat Frank H, Hakimi SL (1965) Probabilistic flows through a communication network. IEEE Trans Circuit Theory 12:413–414 Frank H, Hakimi SL (1965) Probabilistic flows through a communication network. IEEE Trans Circuit Theory 12:413–414
Zurück zum Zitat Fu L, Rilett LR (1998) Expected shortest paths in dynamic and stochastic traffic networks. Transp Res Part B Methodol 32(7):499–516 Fu L, Rilett LR (1998) Expected shortest paths in dynamic and stochastic traffic networks. Transp Res Part B Methodol 32(7):499–516
Zurück zum Zitat Gao X (2009) Some properties of continuous uncertain measure. Int J Uncertain Fuzziness Knowl Based Syst 17(3):419–426MathSciNetMATH Gao X (2009) Some properties of continuous uncertain measure. Int J Uncertain Fuzziness Knowl Based Syst 17(3):419–426MathSciNetMATH
Zurück zum Zitat Gao Y (2011) Shortest path problem with uncertain arc lengths. Comput Math Appl 62:2591–2610MathSciNetMATH Gao Y (2011) Shortest path problem with uncertain arc lengths. Comput Math Appl 62:2591–2610MathSciNetMATH
Zurück zum Zitat Guo HY, Wang XS (2014) Variance of uncertain random variables. J Uncertain Anal Appl 2:6 Guo HY, Wang XS (2014) Variance of uncertain random variables. J Uncertain Anal Appl 2:6
Zurück zum Zitat Hall R (1986) The fastest path through a network with random time-dependent travel time. Transp Sci 20(3):182–188MathSciNet Hall R (1986) The fastest path through a network with random time-dependent travel time. Transp Sci 20(3):182–188MathSciNet
Zurück zum Zitat Han SW, Peng ZX, Wang SQ (2014) The maximum flow problem of uncertain network. Inf Sci 265:167–175MathSciNetMATH Han SW, Peng ZX, Wang SQ (2014) The maximum flow problem of uncertain network. Inf Sci 265:167–175MathSciNetMATH
Zurück zum Zitat Hou YC (2014) Subadditivity of chance measure. J Uncertain Anal Appl 2:14 Hou YC (2014) Subadditivity of chance measure. J Uncertain Anal Appl 2:14
Zurück zum Zitat Jia LF, Yang XF, Gao X (2018) A new definition of cross entropy for uncertain random variables and its application. J Intell Fuzzy Syst 35(1):1193–1204 Jia LF, Yang XF, Gao X (2018) A new definition of cross entropy for uncertain random variables and its application. J Intell Fuzzy Syst 35(1):1193–1204
Zurück zum Zitat Ke H, Su TY (2015) Uncertain random multilevel programming with application to product control problem. Soft Comput 19(6):1739–1746MATH Ke H, Su TY (2015) Uncertain random multilevel programming with application to product control problem. Soft Comput 19(6):1739–1746MATH
Zurück zum Zitat Liu B (2007) Uncertainty theory, 2nd edn. Springer, BerlinMATH Liu B (2007) Uncertainty theory, 2nd edn. Springer, BerlinMATH
Zurück zum Zitat Liu B (2009a) Some research problems in uncertainty theory. J Uncertain Syst 3(1):3–10 Liu B (2009a) Some research problems in uncertainty theory. J Uncertain Syst 3(1):3–10
Zurück zum Zitat Liu B (2009b) Theory and practice of uncertain programming, 2nd edn. Springer, BerlinMATH Liu B (2009b) Theory and practice of uncertain programming, 2nd edn. Springer, BerlinMATH
Zurück zum Zitat Liu B (2010) Uncertainty theory: a branch of mathematics for modeling human uncertainty, 2nd edn. Springer, Berlin Liu B (2010) Uncertainty theory: a branch of mathematics for modeling human uncertainty, 2nd edn. Springer, Berlin
Zurück zum Zitat Liu B (2012) Why is there a need for uncertainty theory. J Uncertain Syst 6(1):3–10 Liu B (2012) Why is there a need for uncertainty theory. J Uncertain Syst 6(1):3–10
Zurück zum Zitat Liu YH (2013a) Uncertain random variables: a mixture of uncertainty and randomness. Soft Comput 17(4):625–634MATH Liu YH (2013a) Uncertain random variables: a mixture of uncertainty and randomness. Soft Comput 17(4):625–634MATH
Zurück zum Zitat Liu YH (2013b) Uncertain random programming with applications. Fuzzy Optim Decis Mak 12(2):153–169MathSciNetMATH Liu YH (2013b) Uncertain random programming with applications. Fuzzy Optim Decis Mak 12(2):153–169MathSciNetMATH
Zurück zum Zitat Liu B (2014) Uncertain random graph and uncertain random network. J Uncertain Syst 8(1):3–12 Liu B (2014) Uncertain random graph and uncertain random network. J Uncertain Syst 8(1):3–12
Zurück zum Zitat Liu YH, Ha MH (2010) Expected value of function of uncertain variables. J Uncertain Syst 4(3):181–186 Liu YH, Ha MH (2010) Expected value of function of uncertain variables. J Uncertain Syst 4(3):181–186
Zurück zum Zitat Liu YH, Ralescu DA (2014) Risk index in uncertain random risk analysis. Int J Uncertain Fuzziness Knowl Based Syst 22(4):491–504MathSciNetMATH Liu YH, Ralescu DA (2014) Risk index in uncertain random risk analysis. Int J Uncertain Fuzziness Knowl Based Syst 22(4):491–504MathSciNetMATH
Zurück zum Zitat Loui P (1983) Optimal paths in graphs with stochastic or multidimensional weights. Commun Assoc Comput Mach 26(9):670–676MathSciNetMATH Loui P (1983) Optimal paths in graphs with stochastic or multidimensional weights. Commun Assoc Comput Mach 26(9):670–676MathSciNetMATH
Zurück zum Zitat Mirchandani PB (1976) Shortest distance and reliability of probabilistic networks. Comput Oper Res 3(4):347–676 Mirchandani PB (1976) Shortest distance and reliability of probabilistic networks. Comput Oper Res 3(4):347–676
Zurück zum Zitat Okada S (2004) Fuzzy shortest path problems incorporating interactivity among paths. Fuzzy Sets Syst 142(3):335–357MathSciNetMATH Okada S (2004) Fuzzy shortest path problems incorporating interactivity among paths. Fuzzy Sets Syst 142(3):335–357MathSciNetMATH
Zurück zum Zitat Peng ZX, Iwamura K (2010) A sufficient and necessary condition of uncertainty distribution. J Interdiscip Math 13(3):277–285MathSciNetMATH Peng ZX, Iwamura K (2010) A sufficient and necessary condition of uncertainty distribution. J Interdiscip Math 13(3):277–285MathSciNetMATH
Zurück zum Zitat Sheng YH, Gao JW (2014) Chance distribution of the maximum flow of uncertain random network. J Uncertain Anal Appl 2:15 Sheng YH, Gao JW (2014) Chance distribution of the maximum flow of uncertain random network. J Uncertain Anal Appl 2:15
Zurück zum Zitat Sheng YH, Gao Y (2016) Shortest path problem of uncertain random network. Comput Ind Eng 99:97–105 Sheng YH, Gao Y (2016) Shortest path problem of uncertain random network. Comput Ind Eng 99:97–105
Zurück zum Zitat Sheng YH, Yao K (2014) Some formulas of variance of uncertain random variable. J Uncertain Anal Appl 2:12 Sheng YH, Yao K (2014) Some formulas of variance of uncertain random variable. J Uncertain Anal Appl 2:12
Zurück zum Zitat Sheng YH, Qin ZF, Shi G (2017) Minimum spanning tree problem of uncertain random network. J Intell Manuf 28(3):565–574 Sheng YH, Qin ZF, Shi G (2017) Minimum spanning tree problem of uncertain random network. J Intell Manuf 28(3):565–574
Zurück zum Zitat Shi G, Sheng YH, Cui Q (2015) Relative entropy model of uncertain random shortest path. Int J e-Navig Marit Econ 2:87–100 Shi G, Sheng YH, Cui Q (2015) Relative entropy model of uncertain random shortest path. Int J e-Navig Marit Econ 2:87–100
Zurück zum Zitat Sigal CL, Pritsker AAB, Solberg JJ (1980) The stochastic shortest route problem. Oper Res 5(28):1122–1129MathSciNetMATH Sigal CL, Pritsker AAB, Solberg JJ (1980) The stochastic shortest route problem. Oper Res 5(28):1122–1129MathSciNetMATH
Zurück zum Zitat Yang XF, Gao JW, Ni YD (2018) Resolution principle in uncertain random environment. IEEE Trans Fuzzy Syst 26(3):1578–1588 Yang XF, Gao JW, Ni YD (2018) Resolution principle in uncertain random environment. IEEE Trans Fuzzy Syst 26(3):1578–1588
Zurück zum Zitat Zhang B, Peng J (2012) Uncertain programming model for Chinese postman problem with uncertain weights. Ind Eng Manag Syst 11(1):18–25 Zhang B, Peng J (2012) Uncertain programming model for Chinese postman problem with uncertain weights. Ind Eng Manag Syst 11(1):18–25
Zurück zum Zitat Zhou J, Yang F, Wang K (2014) Multi-objective optimization in uncertain random environments. Fuzzy Optim Decis Mak 13(4):397–413MathSciNetMATH Zhou J, Yang F, Wang K (2014) Multi-objective optimization in uncertain random environments. Fuzzy Optim Decis Mak 13(4):397–413MathSciNetMATH
Metadaten
Titel
Uncertain random shortest path problem
verfasst von
Yuhong Sheng
Xuehui Mei
Publikationsdatum
05.01.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
Soft Computing / Ausgabe 4/2020
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-018-03714-5

Weitere Artikel der Ausgabe 4/2020

Soft Computing 4/2020 Zur Ausgabe