The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
La recherche du problème du chemin le plus court dans les réseaux dépendant du temps présente une valeur pratique importante. Une stratégie améliorée de mise à jour des phéromones adaptée aux réseaux dépendant du temps a été proposée. Grâce à cette stratégie, la phéromone résiduelle de chaque route peut refléter avec précision le changement de valeur pondérée de chaque route. Une stratégie de sélection améliorée entre villes adjacentes a été utilisée pour calculer les probabilités de transfert des villes, ce qui a permis de réduire considérablement la quantité de calcul. Pour éviter que l’algorithme ne converge vers la solution optimale locale, l’algorithme des colonies de fourmis a été combiné avec l’algorithme génétique. De cette manière, les solutions après chaque parcours ont été utilisées comme espèces initiales pour effectuer un croisement en un seul point. Un algorithme amélioré de colonie de fourmis pour le problème du chemin le plus court dans les réseaux dépendant du temps, basé sur ces stratégies améliorées, a été présenté. Les résultats de la simulation montrent que l'algorithme amélioré a une plus grande probabilité d'obtenir la solution optimale globale et que le taux de convergence de l'algorithme est meilleur que l'algorithme traditionnel des colonies de fourmis.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Qing CHANG, Yongqiang LIU, Huagang XIONG, "An Improved Ant Colony Algorithm for the Shortest Path Problem in Time-Dependent Networks" in IEICE TRANSACTIONS on Communications,
vol. E92-B, no. 9, pp. 2996-2999, September 2009, doi: 10.1587/transcom.E92.B.2996.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.E92.B.2996/_p
Copier
@ARTICLE{e92-b_9_2996,
author={Qing CHANG, Yongqiang LIU, Huagang XIONG, },
journal={IEICE TRANSACTIONS on Communications},
title={An Improved Ant Colony Algorithm for the Shortest Path Problem in Time-Dependent Networks},
year={2009},
volume={E92-B},
number={9},
pages={2996-2999},
abstract={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.},
keywords={},
doi={10.1587/transcom.E92.B.2996},
ISSN={1745-1345},
month={September},}
Copier
TY - JOUR
TI - An Improved Ant Colony Algorithm for the Shortest Path Problem in Time-Dependent Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 2996
EP - 2999
AU - Qing CHANG
AU - Yongqiang LIU
AU - Huagang XIONG
PY - 2009
DO - 10.1587/transcom.E92.B.2996
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E92-B
IS - 9
JA - IEICE TRANSACTIONS on Communications
Y1 - September 2009
AB - 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.
ER -