期刊文献+

带杂交算子的蚁群算法求解动态网络中的最短路径问题 被引量:9

An Ant Colony Algorithm with Crossover Operators for the Shortest Path Problem in Dynamic Networks
下载PDF
导出
摘要 动态网络与传统的网络模型相比更具有现实意义,具有广泛的应用领域。本文对动态网络模型进行了描述,用实例证明了著名的Dijkstra算法在动态网络中不能有效地求解最短路径问题,提出了一种用带杂交算子的蚁群算法来求解动态网络最短路径问题的新算法。此算法不仅能够以较大的概率找到最优解而且对网络没有任何约束条件,即对离散和连续的动态网络模型都有效,而且用实例证明了算法的稳定性。 Time-dependent dynamic networks are more practical or significant compared with traditional network models. An illumination of dynamic networks is given, and instances are adopted to prove that the famous Dijkstra algorithm cannot be effectively used to solve the shortest path problems in dynamic networks. A new algorithm for the shortest path problem in dynamic networks based on the improved ant colony algorithm is presented. This method can find the excellent path based on bigger probability and does not need any constraint condition, which can also solve the problem on continuous and discrete dynamic networks. The algorithm proposed is proved to be stable by examples.
出处 《计算机工程与科学》 CSCD 2007年第5期81-82,146,共3页 Computer Engineering & Science
基金 山西省自然科学基金资助项目(20051044)
关键词 动态网络 最短路径 遗传算法 蚁群算法 dynamic network shortest path genetic algorithm ant colony algorithm
  • 相关文献

参考文献8

二级参考文献27

  • 1谭国真.最短路径算法设计、分析、实现和实验评价.大连理工大学计算机科学与工程系:技术报告[M].,1999..
  • 2[2]Stefano Pallottino, Maria Grazia Scutella. Shortest path algorithmsin transportation models: classical and innovative aspects[ EB/OL]. http://ftp. di. unipi/it/pub/techreports/TR - 97 - 06. ps. Z, 1997 - 06 - 25.
  • 3[3]Hall R W. The fastest path through a network with random time-dependent travel time [J]. Transportation Science,1986,20(3): 182 - 188.
  • 4[4]Liping Fu, L R Rilett. Expected shortest paths in dynamic and stochastic traffic networks[J]. Transpn Res. - B, 1998,32(7): 499 - 516.
  • 5[5]Ariel Orda, Raphael Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length [ J].Journal of the Association for computing Machinery, 1990,37(3) :607 - 625.
  • 6[6]Jun Inagaki, Miki Haseyama, Hideo Kitajema. A new genetic algorithm for routing the shortest route via designated points [J]. IEEE,2001, (2) :217 - 220.
  • 7[7]Chang Wook Ahn , R S Ramakrishn. A genetic algorithm for shortest path routing problem and the sizing of populations [J]. IEEE Transactions on Evolutionary Computation, 2002,6(6) :566 - 579.
  • 8[8]Mitsuo Gen , Runwei Cheng , Dingwei Wang. Genetic algorithms for solving shortest path problems [ J ]. IEEE International conference on Evolutionary Computing, 1997, 401 -406.
  • 9[11]Liping Fu, Bruce Hellinga. Prediction of arrival time dependent delay variability at signalized intersections (Technical Report 990560) [ R]. Washington, D. C: Transportation Research board ,78th Annual Meeting , 1999.
  • 10SUNG K,MICHAEL GH,SEONG BM.Shortest paths in a network with time-dependent flow speeds[J].European Journal of Operational Research,2000,121(12):32-39.

共引文献117

同被引文献80

引证文献9

二级引证文献27

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部