Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

A wave time-varying neural network for solving the time-varying shortest path problem

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

In this paper, we propose a wave time-varying neural network (WTNN) to solve the time-varying shortest path problem (TSPP). The complexity of the TSPP is NP-hard, so it is difficult to solve this problem using traditional algorithms, such as the Dijkstra algorithm. In contrast, the proposed WTNN can arrive at the global optimal solution of three TSPP variant problems with different waiting polices (viz. arbitrary waiting, restricted waiting, and zero waiting at nodes). The WTNN is a novel neural network framework based on time-varying neurons, the structure of which depends on the network topology of the problem to be solved. All neurons on the WTNN are computed in parallel, and each neuron consists of seven parts: input, wave receiver, status updater, status memorizer, wave generator, wave sender, and output. Waves are vehicles for transmitting information between neurons. The underlying idea of the WTNN is based on the following mechanism: all neurons are updated in steps; after updating, each neuron calculates the temporary shortest path and transmits that temporary path to its successor through the wave; and the destination neuron then calculates the final shortest path among all the received waves and outputs optimal solution. The performance evaluation results are based on three public data sets and demonstrate that the proposed WTNN outperforms other existing algorithms.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

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

Similar content being viewed by others

Explore related subjects

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

Notes

References

  1. Cai XQ, Kloks T, Wong C (1997) Time-varying shortest path problems with constraints. Networks 29:141–150

    Article MathSciNet  Google Scholar 

  2. Chen Y (2020) Application of improved dijkstra algorithm in coastal tourism route planning. J Coast Res 106(sp1):251–254

    Article  Google Scholar 

  3. Cho JH, Kim HS, Choi HR (2012) An intermodal transport network planning algorithm using dynamic programming—a case study: from busan to rotterdam in intermodal freight routing. Appl Intell 36 (3):529–541

    Article  Google Scholar 

  4. Cooke KL, Halsey E (1966) The shortest route through a network with time-dependent internodal transit times. J Math Anal Appl 14(3):493–498

    Article MathSciNet  Google Scholar 

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

    Article MathSciNet  Google Scholar 

  6. Ebrahimnejad A, Tavana M, Alrezaamiri H (2016) A novel artificial bee colony algorithm for shortest path problems with fuzzy arc weights. Measurement 93:48–56

    Article  Google Scholar 

  7. Enayattabar M, Ebrahimnejad A, Motameni H (2019) Dijkstra algorithm for shortest path problem under interval-valued pythagorean fuzzy environment. Complex Intell Syst 5(2):93–100

    Article  Google Scholar 

  8. Eroglu H, Aydin M (2018) Solving power transmission line routing problem using improved genetic and artificial bee colony algorithms. Electr Eng 100(3):2103–2116

    Article  Google Scholar 

  9. Eshaghnezhad M, Rahbarnia F, Effati S, Mansoori A (2019) An artificial neural network model to solve the fuzzy shortest path problem. Neural Process Lett 50(2):1527–1548

    Article  Google Scholar 

  10. Fazlollahtabar H, Hassanli S (2018) Hybrid cost and time path planning for multiple autonomous guided vehicles. Appl Intell 48(2):482–498

    Article  Google Scholar 

  11. Gendreau M, Ghiani G, Guerriero E (2015) Time-dependent routing problems: a review. Comput Oper Res 64:189–197

    Article MathSciNet  Google Scholar 

  12. Guo D, Wang J, Zhao JB, Sun F, Gao S, Li CD, Li MH, Li CC (2019) A vehicle path planning method based on a dynamic traffic network that considers fuel consumption and emissions. Sci Total Environ 663:935–943

    Article  Google Scholar 

  13. Guo Y, Li S, Jiang W, Zhang B, Ma Y (2017) Learning automata-based algorithms for solving the stochastic shortest path routing problems in 5g wireless communication. Phys Commun 25:376–385

    Article  Google Scholar 

  14. Hamacher HW, Ruzika S, Tjandra SA (2006) Algorithms for time-dependent bicriteria shortest path problems. Discret Optim 3(3):238–254

    Article MathSciNet  Google Scholar 

  15. Hansknecht C, Joormann I, Stiller S (2021) Dynamic shortest paths methods for the time-dependent tsp. Algorithms 14(1):1–23

    Article MathSciNet  Google Scholar 

  16. Huang W, Ding L (2012) The shortest path problem on a fuzzy time-dependent network. IEEE Trans Commun 60(11):3376–3385

    Article  Google Scholar 

  17. Huang W, Gao L (2020) A time wave neural network framework for solving time-dependent project scheduling problems. IEEE Trans Neural Netw Learn Syst 31(1):274–283

    Article MathSciNet  Google Scholar 

  18. Huang W, Wang J (2016) The shortest path problem on a time-dependent network with mixed uncertainty of randomness and fuzziness. IEEE Trans Intell Transp Syst 17(11):3194–3204

    Article  Google Scholar 

  19. Huang W, Yan C, Wang J, Wang W (2017) A time-delay neural network for solving time-dependent shortest path problem. Neural Netw 90:21–28

    Article  Google Scholar 

  20. Idri A, Oukarfi M, Boulmakoul A, Zeitouni K, Masri A (2017) A new time-dependent shortest path algorithm for multimodal transportation network. Procedia Comput Sci 109:692–697

    Article  Google Scholar 

  21. Kolovsky F, Jezek J, Kolingerova I (2019) Theε-approximation of the time-dependent shortest path problem solution for all departure times. ISPRS Int J Geo-Inform 8(12):1–14

    Article  Google Scholar 

  22. Lacomme P, Moukrim A, Quilliot A, Vinot M (2017) A new shortest path algorithm to solve the resource-constrained project scheduling problem with routing from a flow solution. Eng Appl Artif Intell 66:75–86

    Article  Google Scholar 

  23. Lawin H (2014) Dynamic shortest path routing in mobile adhoc networks using modified artificial bee colony optimization algorithm. Int J Comput Sci Inform Technol 5:7423–7426

    Google Scholar 

  24. Li X, Ma Y, Feng X (2013) Self-adaptive autowave pulse-coupled neural network for shortest-path problem. Neurocomputing 115:63–71

    Article  Google Scholar 

  25. Li Z, Xiao F, Wang S, Pei T, Li J (2018) Achievable rate maximization for cognitive hybrid satellite-terrestrial networks with af-relays. IEEE J Select Areas Commun 36(2):304– 313

    Article  Google Scholar 

  26. Liu G, Qiu Z, Qu H, Ji L (2015) Computing k shortest paths using modified pulse-coupled neural network. Neurocomputing 149:1162–1176

    Article  Google Scholar 

  27. Nip K, Wang Z, Talla Nobibon F, Leus R (2015) A combination of flow shop scheduling and the shortest path problem. J Comb Optim 29(1):36–52

    Article MathSciNet  Google Scholar 

  28. Orda A, Rom R (1991) Minimum weight paths in time-dependent networks. Networks 21 (3):295–319

    Article MathSciNet  Google Scholar 

  29. Riva A, Rufi A, Banfi J, Amigoni F (2019) Algorithms for limited-buffer shortest path problems in communication-restricted environments. Robot Auton Syst 119:221–230

    Article  Google Scholar 

  30. Sang Y, Lv J, Qu H, Yi Z (2016) Shortest path computation using pulse-coupled neural networks with restricted autowave. Knowledge-based Systems 114:1–11

    Article  Google Scholar 

  31. Szczesniak I, Jajszczyk A, Wozna-Szczesniak B (2019) Generic dijkstra for optical networks. J Opt Commun Netw 11(11):568–577

    Article  Google Scholar 

  32. Thamaraikannan N, Kamalraj S (2019) Utilization of compact genetic algorithm for optimal shortest path selection to improve the throughput in mobile ad-hoc networks. Clust Comput 22(2):3715–3726

    Article  Google Scholar 

  33. Veneti A, Konstantopoulos C, Pantziou G (2015) Continuous and discrete time label setting algorithms for the time dependent bi-criteria shortest path problem. In: 14th INFORMS Computing Society Conference, pp 62–73

  34. Wang L (2020) Path planning for unmanned wheeled robot based on improved ant colony optimization. Measurement and Control 53(5-6):1014–1021

    Article  Google Scholar 

  35. Wen L, Çatay B, Eglese R (2014) Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge. Eur J Oper Res 236(3):915–923

    Article MathSciNet  Google Scholar 

  36. Wu H, Cheng J, Ke Y, Huang S, Huang Y, Wu H (2016) Efficient algorithms for temporal path computation. IEEE Trans Knowl Data Eng 28(11):2927–2942

    Article  Google Scholar 

  37. Yang L, Zhou X (2017) Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations. Transp Res B Methodol 96:68–91

    Article  Google Scholar 

  38. Yen CT, Cheng MF (2018) A study of fuzzy control with ant colony algorithm used in mobile robot for shortest path planning and obstacle avoidance. Microsyst Technol 24(1):125–135

    Article  Google Scholar 

  39. Yu L, Jiang H, Hua L (2019) Anti-congestion route planning scheme based on dijkstra algorithm for automatic valet parking system. Appl Sci 9(23):1–14

    Article  Google Scholar 

  40. Zhou J, Liu B (2003) New stochastic models for capacitated location-allocation problem. Comput Indust Eng 45(1):111–125

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Tianjin Key Laboratory of Intelligent and Novel Software Technology, Tianjin University of Technology, 300384, Tianjin, China

    Zhilei Xu & Jinsong Wang

  2. School of Computer Science and Engineering, Tianjin University of Technology, 300384, Tianjin, China

    Zhilei Xu, Wei Huang & Jinsong Wang

Authors
  1. Zhilei Xu

    You can also search for this author inPubMed Google Scholar

  2. Wei Huang

    You can also search for this author inPubMed Google Scholar

  3. Jinsong Wang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toWei Huang.

Additional information

Publisher’s note

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

This work was supported by the National Natural Science Foundation of China under grant 61673295, by the Natural Science Foundation of Tianjin for Distinguished Young Scholars under grant 19JCJQJC61500, by the Natural Science Foundation of Tianjin (General Program) under grant 18JCYBJC85200, by the Natural Science Foundation of Tianjin (Key Program) under grant 18JCZDJC30700, and by the National Key R&D Program of China under grant 2018YFC0831405.

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp