Autosoft Journal

Online Manuscript Access


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


Authors



Abstract

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.


Keywords


Pages

Total Pages: 8
Pages: 235-242

DOI
10.1080/10798587.2016.1196926


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?


Published

Volume: 23
Issue: 2
Year: 2016

Cite this document


References

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. https://doi.org/10.1109/TEVC.2002.804323

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. https://doi.org/10.1016/j.jmsy.2013.09.006

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. https://doi.org/10.1080/19479832.2012.681401

Blum, Christian. "Ant Colony Optimization: Introduction and Recent Trends." Physics of Life Reviews 2.4 (2005): 353-373. Crossref. Web. https://doi.org/10.1016/j.plrev.2005.10.001

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. https://doi.org/10.1007/s11590-014-0742-x

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. https://doi.org/10.1016/j.comgeo.2014.02.004

Akin, H. Levent et al., eds. "Algorithmic Foundations of Robotics XI." Springer Tracts in Advanced Robotics (2015): n. pag. Crossref. Web. https://doi.org/10.1007/978-3-319-16595-0

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. https://doi.org/10.1016/j.ejor.2006.06.047

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. https://doi.org/10.1109/3477.484436

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. https://doi.org/10.1007/0-306-48056-5_9

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. https://doi.org/10.1016/j.ejor.2014.11.003

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. https://doi.org/10.1016/j.asoc.2009.09.014

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

Jaillet, L., and J.M. Porta. "Efficient Asymptotically-Optimal Path Planning on Manifolds." Robotics and Autonomous Systems 61.8 (2013): 797-807. Crossref. Web. https://doi.org/10.1016/j.robot.2013.04.012

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. https://doi.org/10.1016/j.eswa.2008.06.101

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. https://doi.org/10.1080/19479832.2011.642413

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. https://doi.org/10.1007/s10236-014-0757-y

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. https://doi.org/10.1080/19479832.2011.617318

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. https://doi.org/10.1109/TRO.2014.2351113

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. https://doi.org/10.1080/19479832.2011.645888

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. https://doi.org/10.1360/aas-007-0279

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. https://doi.org/10.3390/s150921033

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. https://doi.org/10.1080/01431161.2010.540587

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. https://doi.org/10.4304/jnw.9.9.2353-2359

JOURNAL INFORMATION


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




CONTACT INFORMATION


TSI Press
18015 Bullis Hill
San Antonio, TX 78258 USA
PH: 210 479 1022
FAX: 210 479 1048
EMAIL: tsiepress@gmail.com
WEB: http://www.wacong.org/tsi/