Skip to main content
SpringerLink
Log in

On Multi-objective Fuzzy Shortest Path Problem

  • Conference paper
  • First Online:
Advances in Data Science and Computing Technologies (ADSC 2022)

Part of the book series: Lecture Notes in Electrical Engineering ((LNEE,volume 1056))

  • 231 Accesses

Abstract

Being a network optimization problem, the shortest path problem (SPP) is considered as one of the popular and frequently encountered optimization problems to address real-world problems. In this paper, we investigate a multi-objective SPP under the paradigm of fuzzy set theory. The proposed problem minimizes both cost and time of a given network, where every edges are associated with cost and time parameters represented as fuzzy triangular numbers to incorporate uncertainty involved with real-world phenomenon. Here, we have modeled a fuzzy chance-constrained model of multi-objective SPP and eventually solved the deterministic transformation of the model using weighted sum method.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, New Jersey

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  3. Floyd RW (1962) Algorithm 97: shortest path. Commun Assoc Comput Mach 5(6):345

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  5. Shi N, Zhou S, Wang F, Tao Y, Liu L (2017) The multi-criteria constrained shortest path problem. Transp Res Part E Logistics Transp Rev 101:13–29

    Article  Google Scholar 

  6. Majumder S, Saha B, Anand P, Kar S, Pal T (2018) Uncertainty based genetic algorithm with varying population for random fuzzy maximum flow problem. Expert Syst 35(4):e12264

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  10. Zockaie A, Nie YM, Mahmassani HS (2014) Simulation-based method for finding minimum travel time budget paths in stochastic networks with correlated link times. Transp Res Rec 2457(1):140–148

    Google Scholar 

  11. Huang X (2007) Chance-constrained programming models for capital budgeting with NPV as fuzzy parameters. J Comput Appl Math 198(1):149–159

    Article  MathSciNet  MATH  Google Scholar 

  12. Liu B (2007) Uncertainty theory, 2nd edn. Springer-Verlag, Berlin, Heidelberg

    MATH  Google Scholar 

  13. Dubois D, Prade H (1980) Fuzzy sets and systems: theory and applications. Academic Press, New York

    MATH  Google Scholar 

  14. Klein CM (1991) Fuzzy shortest paths. Fuzzy Sets Syst 39(1):27–41

    Google Scholar 

  15. Okada S, Gen M (1994) Fuzzy shortest path problem. Comput Ind Eng 27(1–4):465–468

    Article  Google Scholar 

  16. Okada S (2004) Fuzzy shortest path problems incorporating interactivity among paths. Fuzzy Sets Syst 142(3):335–357

    Article  MathSciNet  MATH  Google Scholar 

  17. Ji X, Iwamura K, Shao Z (2007) New models for shortest path problem with fuzzy arc lengths. Appl Math Model 31(2):259–269

    Article  MATH  Google Scholar 

  18. Hernandes F, Lamata MT, Verdegay JL, Yamakami A (2007) The shortest path problem on networks with fuzzy parameters. Fuzzy Sets Syst 158(14):1561–1570

    Article  MathSciNet  MATH  Google Scholar 

  19. Mahdavi I, Nourifar R, Heidarzade A, Amiri NM (2009) A dynamic programming approach for finding shortest chains in a fuzzy network. Appl Soft Comput 9(2):503–511

    Article  Google Scholar 

  20. Tajdin A, Mahdavi I, Mahdavi-Amiri N, Sadeghpour-Gildeh B (2010) Computing a fuzzy shortest path in a network with mixed fuzzy arc lengths using α-cuts. Comput Math Appl 60(4):989–1002

    MathSciNet  MATH  Google Scholar 

  21. Dou Y, Zhu L, Wang HS (2012) Solving the fuzzy shortest path problem using multi-criteria decision method based on vague similarity measure. Appl Soft Comput 12(6):1621–1631

    Article  Google Scholar 

  22. Deng Y, Chen Y, Zhang Y, Mahadevan S (2012) Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. Appl Soft Comput 12(3):1231–1237

    Article  Google Scholar 

  23. Hassanzadeh R, Mahdavi I, Mahdavi-Amiri N, Tajdin A (2013) A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. Math Comput Model 57(1–2):84–99

    Article  MathSciNet  MATH  Google Scholar 

  24. Ebrahimnejad A, Karimnejad Z, Alrezaamiri H (2015) Particle swarm optimization algorithm for solving shortest path problems with mixed fuzzy arc weights. Int J Appl Decis Sci 8(2):203–222

    Google Scholar 

  25. Anusuya V, Sathya R (2014) A new approach for solving type-2 fuzzy shortest path problem. Ann Pure Appl Math 8(1):83–92

    Google Scholar 

  26. Kumar R, Jha S, Singh S (2017) Shortest path problem in network with type-2 triangular fuzzy arc length. J Appl Res Ind Eng 4(1):1–7

    Google Scholar 

  27. Mahdavi I, Mahdavi-Amiri N, Nejati S (2011) Algorithms for biobjective shortest path problems in fuzzy networks. Iran J Fuzzy Syst 8(4):9–37

    MathSciNet  MATH  Google Scholar 

  28. Kumar MK, Sastry VN (2013) A new algorithm to compute Pareto-optimal paths in a multi objective fuzzy weighted network. Opsearch 50(3):297–318

    Article  MathSciNet  MATH  Google Scholar 

  29. Zadeh LA (1965) Fuzzy sets. Inf Control 8(3):338–353

    Article  MATH  Google Scholar 

  30. Nahmias S (1978) Fuzzy variable. Fuzzy Sets Syst 1(2):97–110

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  32. Gao J, Lu M (2005) Fuzzy quadratic minimum spanning tree problem. Appl Math Comput 164(3):773–788

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We are indebted to the technical program committee and the anonymous reviewers for accepting our manuscript in the International Conference on Advances in Data Science and Computing Technologies (ADSC-2022) held at Kazi Nazrul University (Public University), Asansol, West Bengal, India 713340, during 23rd–24th June 2022.

Author information

Authors and Affiliations

  1. Centre for IOT and AI Integration with Education–Industry–Agriculture, Kazi Nazrul University, Asansol, West Bengal, India

    Swapna Halder & Arindam Biswas

  2. Department of Computer Science and Engineering, St. Thomas’ College of Engineering and Technology, West Bengal, Kolkata, India

    Swapna Halder

  3. Department of Computer Science and Engineering (Data Science), Dr. B.C. Roy Engineering College, Durgapur, West Bengal, India

    Saibal Majumder

  4. School of Mines and Metallurgy, Kazi Nazrul University, Asansol, West Bengal, India

    Arindam Biswas

  5. Department of Computer Science and Engineering, NSHM Knowledge Campus, Durgapur, West Bengal, India

    Bijoy Kumar Mandal

  6. Department of Creative Technologies and Product Design, National Taipei University of Business, Taoyuan, 32462, Taiwan

    Sheng-Lung Peng

Authors
  1. Swapna Halder
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Saibal Majumder
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Arindam Biswas
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Bijoy Kumar Mandal
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Sheng-Lung Peng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Swapna Halder .

Editor information

Editors and Affiliations

  1. School of Computing, Madanapalle Institute of Technology and Science, Angallu, Andhra Pradesh, India

    Basabi Chakraborty

  2. Kazi Nazrul University, Asansol, West Bengal, India

    Arindam Biswas

  3. A.K. Choudhury School of Information Technology, University of Calcutta, Kolkata, West Bengal, India

    Amlan Chakrabarti

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Halder, S., Majumder, S., Biswas, A., Mandal, B.K., Peng, SL. (2023). On Multi-objective Fuzzy Shortest Path Problem. In: Chakraborty, B., Biswas, A., Chakrabarti, A. (eds) Advances in Data Science and Computing Technologies. ADSC 2022. Lecture Notes in Electrical Engineering, vol 1056. Springer, Singapore. https://doi.org/10.1007/978-981-99-3656-4_51

Download citation

Publish with us

Policies and ethics

Search

Navigation