[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Uncertain programming models for multi-objective shortest path problem with uncertain parameters

  • Methodologies and Application
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

The shortest path problem is considered as one of the essential problems in network optimization with a wide range of real-world applications. Modelling such real-world applications involves various indeterminate phenomena which can be estimated through human beliefs. The uncertainty theory proposed by Liu (Uncertain theory, 2nd edn., Springer, Berlin, 2007) is widely regarded as a legitimate tool to deal with such uncertainty. This paper presents an uncertain multi-objective shortest path problem (UMSPP) for a weighted connected directed graph (WCDG), where every edge weight is associated with two uncertain parameters: cost and time. These parameters are represented as uncertain variables. Here, we have formulated the expected value model and chance-constrained model of the proposed UMSPP, and the corresponding deterministic transformation of these models is also presented. Subsequently, the deterministic models are solved with a classical multi-objective solution method, namely the global criterion method. Furthermore, two multi-objective genetic algorithms (MOGAs): nondominated sorting genetic algorithm II (NSGA-II) and multi-objective cross-generational elitist selection, heterogeneous recombination and cataclysmic mutation (MOCHC), are employed to solve these models. A suitable example is provided to illustrate the proposed model. Finally, the performance of MOGAs is compared for five randomly generated instances of UMSPP.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Bellman E (1958) On a routing problem. Q Appl Math 16(1):87–90

    MATH  Google Scholar 

  • Charnes A, Cooper WW (1959) Chance-constrained programming. Manage Sci 6(1):73–79

    MathSciNet  MATH  Google Scholar 

  • Chen P, Nie Y (2013) Bi-criterion shortest path problem with a general nonadditive cost. Transp Res Part B Methodol 57:419–435

    Google Scholar 

  • Chen BY, Lam WHK, Sumalee A, Li Z (2012) Reliable shortest path finding in stochastic networks with spatial correlated link travel times. Int J Geogr Inf Sci 26(2):365–386

    Google Scholar 

  • Chen B, Liu Y, Zhou T (2017a) An entropy based solid transportation problem in uncertain environment. J Ambient Intell Humaniz Comput. https://doi.org/10.1007/s12652-017-0535-z

    Article  Google Scholar 

  • Chen L, Peng J, Zhang B (2017b) Uncertain goal programming models for bicriteria solid transportation problem. Appl Soft Comput 51:49–59

    Google Scholar 

  • Dalman H (2016) Uncertain programming model for multi-item solid transportation problem. Int J Mach Learn Cybernet. https://doi.org/10.1007/s13042-016-0538-7

    Article  MATH  Google Scholar 

  • Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197

    Google Scholar 

  • Dijkstra EW (1959) A note on two problems in connection with graphs. Numer Math 1(1):269–271

    MathSciNet  MATH  Google Scholar 

  • Ding S (2014) Uncertain minimum cost flow problem. Soft Comput 18:2201–2207

    MATH  Google Scholar 

  • Dreyfus S (1969) An appraisal of some shortest path algorithms. Oper Res 17(3):395–412

    MATH  Google Scholar 

  • Durillo JJ, Nebro AJ (2011) jMetal: a Java framework for multi-objective optimization. Adv Eng Softw 42(10):760–771

    Google Scholar 

  • Eshelman LJ (1991) The CHC adaptive search algorithm: how to have safe search when engaging. Found Genet Algorithm 1:265–283

    Google Scholar 

  • Floyd RW (1962) Algorithm-97-shortest path. Commun ACM 5(6):345

    Google Scholar 

  • Fonseca CM, Fleming PJ (1993) Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. In: Proceedings of the fifth international conference on genetic algorithms, San Francisco, CA, USA, pp 416–423

  • Frank H (1969) Shortest paths in probability graphs. Oper Res 17(4):583–599

    MATH  Google Scholar 

  • Frank H, Hakimi SL (1965) Probabilistic flows through a communication network. IEEE Trans Circuit Theory 12(3):413–414

    Google Scholar 

  • Gandibleux X, Beugnies F, Randriamasy S (2006) Martins’ algorithm revisited for multi-objective shortest path problems with a MaxMin cost function. 4OR 4(1):47–59

    MathSciNet  MATH  Google Scholar 

  • Gao Y (2011) Shortest path problem with uncertain arc lengths. Comput Math Appl 62:2591–2600

    MathSciNet  MATH  Google Scholar 

  • Gao Y (2012) Uncertain models for single facility location problems on networks. Appl Math Model 36(6):2592–2599

    MathSciNet  MATH  Google Scholar 

  • Gao X (2013) Cycle index of uncertain graph. Information 15(12):270–277

    Google Scholar 

  • Gao X, Gao Y (2013) Connectedness index of uncertain graphs. Int J Uncertain Fuzziness Knowl Based Syst 21(1):127–137

    MathSciNet  MATH  Google Scholar 

  • Gao Y, Kar S (2017) Int J Fuzzy Syst 19(6):1916–1926

    MathSciNet  Google Scholar 

  • Gao Y, Qin Z (2016) On computing the edge-connectivity of an uncertain graph. IEEE Trans Fuzzy Syst 24(2):981–991

    Google Scholar 

  • Gao Y, Yang L, Li S, Kar S (2015) On distribution function of the diameter in uncertain graph. Inf Sci 296:61–74

    MathSciNet  MATH  Google Scholar 

  • Guo C, Gao J (2017) Optimal dealer pricing under transaction uncertainty. J Intell Manuf 28(3):657–665

    Google Scholar 

  • Hall R (1986) The fastest path through a network with random time-dependent travel time. Transp Sci 20(3):182–188

    Google Scholar 

  • Han S, Peng Z, Wang S (2014) The maximum flow problem of uncertain network. Inf Sci 265:167–175

    MathSciNet  MATH  Google Scholar 

  • Hansen P (1980) Bi-criterion path problems. In: Fandel G, Gal T (eds) Multiple criteria decision making theory and application, vol 177. Lecture Notes in Economics and Mathematical Systems. Springer, Berlin, pp 109–127

    Google Scholar 

  • Horn J, Nafploitis N, Goldberg DE (1994) A niched Pareto genetic algorithm for multi-objective optimization. In: Proceedings of the first IEEE conference on evolutionary computation, Piscataway, NJ, pp 82–87

  • Hu Z, Gao J (2018) Uncertain Gompertz regression model with imprecise observations. Soft Comput. https://doi.org/10.1007/s00500-018-3611-1

    Article  Google Scholar 

  • Kahneman D, Tversky A (1979) Prospect theory: an analysis of decision under risk. Econometrica 47(2):263–292

    MathSciNet  MATH  Google Scholar 

  • Kar MB, Majumder S, Kar S, Pal T (2017) Cross-entropy based multi-objective uncertain portfolio selection problem. J Intell Fuzzy Syst 32(6):4467–4483

    MATH  Google Scholar 

  • Kostreva MM, Wiecek MM (1993) Time dependency in multiple objective dynamic programming. J Math Anal Appl 173(1):289–307

    MathSciNet  MATH  Google Scholar 

  • Liu B (2002) Theory and practice of uncertain programming. Springer, Berlin

    MATH  Google Scholar 

  • Liu B (2007) Uncertainty theory, 2nd edn. Springer, Berlin

    MATH  Google Scholar 

  • Liu B (2009a) Some research problems in uncertainty theory. J Uncertain Syst 3(1):3–10

    Google Scholar 

  • Liu B (2009b) Theory and practice of uncertain programming, 2nd edn. Springer, Berlin

    MATH  Google Scholar 

  • Liu B (2010) Uncertainty theory: a branch of mathematics for modeling human uncertainty. Springer, Berlin

    Google Scholar 

  • Liu B (2012) Why is there a need for uncertainty theory? J Uncertain Syst 6(1):3–10

    Google Scholar 

  • Liu YH, Ha MH (2010) Expected value of function of uncertain variables. J Uncertain Syst 4(3):181–186

    Google Scholar 

  • Liu B, Liu YK (2002) Expected value of fuzzy variable and fuzzy expected value models. IEEE Trans Fuzzy Syst 10(4):445–450

    Google Scholar 

  • Liu L, Zhang B, Ma W (2018) Uncertain programming models for fixed charge multi-item solid transportation problem. Soft Comput 22(17):5825–5833

    MATH  Google Scholar 

  • Majumder S, Kundu P, Kar S, Pal T (2018a) Uncertain multi-objective multi-item fixed charge solid transportation problem with budget constraint. Soft Comput. https://doi.org/10.1007/s00500-017-2987-7

    Article  MATH  Google Scholar 

  • Majumder S, Kar S, Pal T (2018b) Mean-entropy model of uncertain portfolio selection problem. In: Mandal JK, Mukhopadhyay S, Dutta P (eds) Multi-objective optimization: evolutionary to hybrid framework. Springer, Singapore https://doi.org/10.1007/978-981-13-1471-1_2

  • Majumder S, Kar S, Pal T (2018c) Uncertain multi-objective Chinese postman problem. Soft Comput. https://doi.org/10.1007/s00500-018-03697-3

    Article  Google Scholar 

  • Mirchandani PB (1976) Shortest distance and reliability of probabilistic networks. Comput Oper Res 3(4):347–676

    Google Scholar 

  • Mou D, Zhao W, Chen X (2013) Transportation problem with uncertain truck times and unit costs. Ind Eng Manage Syst 12(1):30–35

    Google Scholar 

  • Nag K, Pal T, Pal NR (2015) ASMiGA: an archive-based steady-state micro genetic algorithm. IEEE Trans Cybernet 45(1):40–52

    Google Scholar 

  • Nebro AJ, Alba E, Molina G, Chicano F, Luna F, Durillo JJ (2007) Optimal antenna placement using a new multi-objective CHC algorithm. In: GECCO ‘07 proceedings of the 9th annual conference on genetic and evolutionary computation, New York, NY, USA, pp 876–883

  • Nie Y, Wu X (2009) Shortest path problem considering on-time arrival probability. Transp Res Part B Methodol 43(6):597–613

    Google Scholar 

  • Papadimitriou CH, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. In: Proceedings 41st annual IEEE symposium on foundations of computer science, Redondo Beach, CA, USA, pp 86–92

  • Rao SS (2006) Engineering optimization-theory and practice, 3rd edn. New Age International Publishers, New Delhi

    Google Scholar 

  • Sedeño-Noda A, Raith A (2015) A Dijkstra-like method computing all extreme supported nondominated solutions of the bi-objective shortest path problem. Comput Oper Res 57:83–94

    MathSciNet  MATH  Google Scholar 

  • Sheng Y, Gao Y (2016) Shortest path problem of uncertain random network. Comput Ind Eng 99:97–105

    Google Scholar 

  • Sheng Y, Yao K (2012) A transportation model with uncertain costs and demands. Information 15(8):3179–3186

    MathSciNet  MATH  Google Scholar 

  • Shi G, Sheng Y, Cui Q (2015) Relative entropy model of uncertain random shortest path. Int J e-Navigation Marit Econ 2:87–100

    Google Scholar 

  • Van Veldhuizen DA, Lamont GB (1998) Multi-objective evolutionary algorithm research: a history and analysis, Technical Report TR-98-03, Dept. Elec. Comput. Eng., Graduate School of Eng., Air Force Inst. Technol., Wright-Patterson, AFB, OH

  • Yang X, Gao J (2016) Linear-quadratic uncertain differential game with application to resource extraction problem. IEEE Trans Fuzzy Syst 24(4):819–826

    MathSciNet  Google Scholar 

  • Yang X, Gao J (2017) Bayesian equilibria for uncertain bimatrix game with asymmetric information. J Intell Manuf 28(3):515–525

    Google Scholar 

  • Yao K (2010) Expected value of lognormal uncertain variable. In: Proceedings of the first international conference on uncertainty theory, Urumchi, China, pp 241–243

  • Zhang X, Chen X (2012) A new uncertain programming model for project scheduling problem. Information 15(10):3901–3910

    MathSciNet  MATH  Google Scholar 

  • Zhang Q, Li H (2007) MOEA/D: a multi-objective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731

    Google Scholar 

  • Zhang B, Peng J (2012) Uncertain programming model for Chinese postman problem with uncertain weights. Ind Eng Manage Syst 11(1):18–25

    Google Scholar 

  • Zhang B, Peng J (2013) Uncertain programming model for uncertain optimal assignment problem. Appl Math Model 37(9):6458–6468

    MathSciNet  MATH  Google Scholar 

  • Zhang B, Peng J, Li S, Chen L (2016) Fixed charge solid transportation problem in uncertain environment and its algorithm. Comput Ind Eng 102(2016):186–197

    Google Scholar 

  • Zhang B, Li H, Li S, Peng J (2018a) Sustainable multi-depot emergency facilities location-routing problem with uncertain information. Appl Math Comput 333:506–520

    MathSciNet  MATH  Google Scholar 

  • Zhang Y, Gao J, An Q (2018b) International investing in uncertain financial market. Soft Comput 22(16):5335–5346

    MATH  Google Scholar 

  • Zhou A, Jin Y, Zhang Q, Sendho B, Tsang E (2006) Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion. In: IEEE congress on evolutionary computation, Sheraton Vancouver Wall Center Vancouver, BC, Canada, pp 3234–3241

  • Zhou J, Yang F, Wang K (2014a) An inverse shortest path problem on an uncertain graph. J Netw 9(9):2353–2359

    Google Scholar 

  • Zhou J, He X, Wang K (2014b) Uncertain quadratic minimum spanning tree problem. J Commun 9(5):385–390

    Google Scholar 

  • Zhou J, Chen L, Wang K (2015) Path optimality conditions for minimum spanning tree problem with uncertain edge weights. Int J Uncertain Fuzziness Knowl Based Syst 23(1):49–71

    MathSciNet  MATH  Google Scholar 

  • Zitzler E, Thiele L (1999) Multi-objective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271

    Google Scholar 

  • Zockaie A, Nie Y, Mahmassani HS (2014) Plan B: a simulation-based method for finding minimum travel time budget paths in stochastic networks with correlated link times. Transportation Research Record: Journal of the Transportation Research Board (2467, pp 140–148). Washington, DC: Transportation Research Board of the National Academies

Download references

Author information

Authors and Affiliations

  1. Genomics and Molecular Medicine, CSIR-Institute of Genomics and Integrative Biology, New Delhi, 110025, India

    Saibal Majumder

  2. Department of Computer Science and Engineering, Heritage Institute of Technology, Kolkata, 700107, India

    Mohuya B. Kar

  3. Department of Mathematics, National Institute of Technology, Durgapur, 713209, India

    Samarjit Kar

  4. Department of Computer Science and Engineering, National Institute of Technology, Durgapur, 713209, India

    Tandra Pal

Authors
  1. Saibal Majumder
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohuya B. Kar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Samarjit Kar
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tandra Pal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Samarjit Kar.

Ethics declarations

Conflict of interest

The authors declare that there is no conflict of interest regarding the publication of this article.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Informed consent

Informed consent is obtained from all individual participants included in the study.

Additional information

Communicated by V. Loia.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

In this section, the list of abbreviations used in our study is presented in Table 15.

Table 15 List of abbreviations
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Majumder, S., Kar, M.B., Kar, S. et al. Uncertain programming models for multi-objective shortest path problem with uncertain parameters. Soft Comput 24, 8975–8996 (2020). https://doi.org/10.1007/s00500-019-04423-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-019-04423-3

Keywords

Search

Navigation