Autosoft Journal

Online Manuscript Access

A hybrid Genetic-Ant Colony Optimization Algorithm for the Optimal Path Selection



The shortest path problem lies at the heart of network flows that seeks for the paths with minimum cost from source node to sink node in networks. This paper presents a hybrid genetic-ant colony optimization algorithmic approach to the optimal path selection problem. First, some existing solutions for the optimal path selection problem are analyzed, and some shortages and flaws are pointed out. Second, the data organization method for road network based on the graph theory is proposed. Furthermore, the optimal path selection algorithm integrated of sinusoidal probability transfer rules, pheromone update strategy and dual population is presented. Finally, the experimental results show that the proposed algorithm speeds up the convergence rate and improves the efficiency.



Total Pages: 8
Pages: 235-242


Manuscript ViewPdf Subscription required to access this document

Obtain access this manuscript in one of the following ways

Already subscribed?

Need information on obtaining a subscription? Personal and institutional subscriptions are available.

Already an author? Have access via email address?


Volume: 23
Issue: 2
Year: 2016

Cite this document


Chang Wook Ahn, and R.S. Ramakrishna. "A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations." IEEE Transactions on Evolutionary Computation 6.6 (2002): 566-579. Crossref. Web.

Azimirad, Vahid, and Hamed Shorakaei. "Dual Hierarchical Genetic-Optimal Control: A New Global Optimal Path Planning Method for Robots." Journal of Manufacturing Systems 33.1 (2014): 139-148. Crossref. Web.

Barb, Adrian S., and Chi-Ren Shyu. "A Study of Factors That Influence the Accuracy of Content-Based Geospatial Ranking Systems." International Journal of Image and Data Fusion 3.3 (2012): 257-268. Crossref. Web.

Blum, Christian. "Ant Colony Optimization: Introduction and Recent Trends." Physics of Life Reviews 2.4 (2005): 353-373. Crossref. Web.

Bolívar, Manuel A., Leonardo Lozano, and Andrés L. Medaglia. "Acceleration Strategies for the Weight Constrained Shortest Path Problem with Replenishment." Optimization Letters 8.8 (2014): 2155-2172. Crossref. Web.

De Carufel, Jean-Lou et al. "A Note on the Unsolvability of the Weighted Region Shortest Path Problem." Computational Geometry 47.7 (2014): 724-727. Crossref. Web.

Akin, H. Levent et al., eds. "Algorithmic Foundations of Robotics XI." Springer Tracts in Advanced Robotics (2015): n. pag. Crossref. Web.

Di Caro G. Ant Colony Optimization and its application to adaptive routing in telecommunication networks

Donati, Alberto V. et al. "Time Dependent Vehicle Routing Problem with a Multi Ant Colony System." European Journal of Operational Research 185.3 (2008): 1174-1191. Crossref. Web.

Dorigo, M., V. Maniezzo, and A. Colorni. "Ant System: Optimization by a Colony of Cooperating Agents." IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) 26.1 (1996): 29-41. Crossref. Web.

Dorigo, Marco, and Thomas Stützle. "The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances." International Series in Operations Research & Management Science 250-285. Crossref. Web.

Duque, Daniel, Leonardo Lozano, and Andrés L. Medaglia. "An Exact Method for the Biobjective Shortest Path Problem for Large-Scale Road Networks." European Journal of Operational Research 242.3 (2015): 788-797. Crossref. Web.

Ghoseiri, Keivan, and Behnam Nadjari. "An Ant Colony Optimization Algorithm for the Bi-Objective Shortest Path Problem." Applied Soft Computing 10.4 (2010): 1237-1246. Crossref. Web.

Holland, John H. "Genetic Algorithms and the Optimal Allocation of Trials." SIAM Journal on Computing 2.2 (1973): 88-105. Crossref. Web.

Jaillet, L., and J.M. Porta. "Efficient Asymptotically-Optimal Path Planning on Manifolds." Robotics and Autonomous Systems 61.8 (2013): 797-807. Crossref. Web.

Juang, Chia-Feng, and Chi-Yen Wang. "A Self-Generating Fuzzy System with Ant and Particle Swarm Cooperative Optimization." Expert Systems with Applications 36.3 (2009): 5362-5370. Crossref. Web.

Lin, Xiangguo, Rui Zhang, and Jing Shen. "A Template-Matching Based Approach for Extraction of Roads from Very High-Resolution Remotely Sensed Imagery." International Journal of Image and Data Fusion 3.2 (2012): 149-168. Crossref. Web.

Lolla, Tapovan et al. "Time-Optimal Path Planning in Dynamic Flows Using Level Set Equations: Theory and Schemes." Ocean Dynamics 64.10 (2014): 1373-1397. Crossref. Web.

Lounis, Bahia et al. "Hybridisation of Fuzzy Systems and Genetic Algorithms for Water Quality Characterisation Using Remote Sensing Data." International Journal of Image and Data Fusion 4.2 (2013): 171-196. Crossref. Web.

Mohamed C. Electronic Notes in Discrete Mathematics

Pham, Quang-Cuong. "A General, Fast, and Robust Implementation of the Time-Optimal Path Parameterization Algorithm." IEEE Transactions on Robotics 30.6 (2014): 1533-1540. Crossref. Web.

Siddiqi U.F. Applied Soft Computing

Sidek, Othman, and S.A. Quadri. "A Review of Data Fusion Models and Systems." International Journal of Image and Data Fusion 3.1 (2012): 3-21. Crossref. Web.

TAN, Guan-Zheng. "Ant Colony System Algorithm for Real-Time GloballyOptimal Path Planning of Mobile Robots." ACTA AUTOMATICA SINICA 33.3 (2007): 0279. Crossref. Web.

Xu, Sheng-Hua et al. "A Combination of Genetic Algorithm and Particle Swarm Optimization for Vehicle Routing Problem with Time Windows." Sensors 15.9 (2015): 21033-21053. Crossref. Web.

Zhang, Jixian et al. "Semi-Automatic Road Tracking by Template Matching and Distance Transformation in Urban Areas." International Journal of Remote Sensing 32.23 (2011): 8331-8347. Crossref. Web.

Zhou, Jian, Fan Yang, and Ke Wang. "An Inverse Shortest Path Problem on an Uncertain Graph." Journal of Networks 9.9 (2014): n. pag. Crossref. Web.


ISSN PRINT: 1079-8587
ISSN ONLINE: 2326-005X
DOI PREFIX: 10.31209
10.1080/10798587 with T&F
IMPACT FACTOR: 0.652 (2017/2018)
Journal: 1995-Present


TSI Press
18015 Bullis Hill
San Antonio, TX 78258 USA
PH: 210 479 1022
FAX: 210 479 1048