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
Soft Computing
Published in: Soft Computing 4/2020

05-01-2019 | Focus

Uncertain random shortest path problem

Authors: Yuhong Sheng, Xuehui Mei

Published in: Soft Computing | Issue 4/2020

Log in

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

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.
previous article Uncertain pursuit-evasion game
next article A novel uncertain bimatrix game with Hurwicz criterion

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

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

Other articles of this Issue 4/2020

Soft Computing 4/2020 Go to the issue

Focus

A hybrid combinatorial approach to a two-stage stochastic portfolio optimization model with uncertain asset prices

Focus

Sustainability efficiency evaluation of seaports in China: an uncertain data envelopment analysis approach

Focus

Benchmarking framework for command and control mission planning under uncertain environment

Editorial

Special issue on decision making and uncertainty

Focus

Green investment in a supply chain based on price and quality competition

Focus

Chance constrained programming models for uncertain hub covering location problems

Premium Partner

    Image Credits