An Improved Ant Colony Algorithm for the Shortest Path Problem in Time-Dependent Networks

• CHANG Qing

  School of Electronic and Information Engineering of BeiHang University

• LIU Yongqiang

  School of Electronic and Information Engineering of BeiHang University

• XIONG Huagang

  School of Electronic and Information Engineering of BeiHang University

抄録

Research of the shortest path problem in time-dependent networks has important practical value. An improved pheromone update strategy suitable for time-dependent networks was proposed. Under this strategy, the residual pheromone of each road can accurately reflect the change of weighted value of each road. An improved selection strategy between adjacent cities was used to compute the cities' transfer probabilities, as a result, the amount of calculation is greatly reduced. To avoid the algorithm converging to the local optimal solution, the ant colony algorithm was combined with genetic algorithm. In this way, the solutions after each traversal were used as the initial species to carry out single-point crossover. An improved ant colony algorithm for the shortest path problem in time-dependent networks based on these improved strategies was presented. The simulation results show that the improved algorithm has greater probability to get the global optimal solution, and the convergence rate of algorithm is better than traditional ant colony algorithm.

収録刊行物

• IEICE Transactions on Communications

  IEICE Transactions on Communications E92-B (9), 2996-2999, 2009

  一般社団法人 電子情報通信学会

キーワード

• time-dependent networks
• shortest path problem
• ant colony algorithm (ACO)

詳細情報

• CRID: 1390001204373424896
• NII論文ID: 10026840830
• NII書誌ID: AA10826261
• DOI: 10.1587/transcom.e92.b.2996
• ISSN: 17451345
• ISSN: 09168516
• Web Site: http://www.jstage.jst.go.jp/article/transcom/E92.B/9/E92.B_9_2996/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可