GENETIC ALGORITHM APPROACH FOR OPTIMAL CYCLIC TOUR ROUND THE STATE CAPITALS IN NIGERIA’S NIGER DELTA REGION

Egba Anwaitu Fraser; Obikwelu R. Okonkwo

doi:10.29121/granthaalayah.v9.i5.2021.3906

Authors

Egba Anwaitu Fraser Department of Computer Science, School of Science Education (SSE), Federal College of Education (Technical), Omoku, Rivers State, in Affiliation to University of Nigeria, Nsukka, Enugu State, Nigeria https://orcid.org/0000-0001-5742-307X
Okonkwo, Obikwelu R. Department of Computer Science, Faculty of Natural Sciences, Nnamdi Azikiwe University, Awka, Anambra State, Nigeria

DOI:

https://doi.org/10.29121/granthaalayah.v9.i5.2021.3906

Keywords:

Traveling Salesman Problem, Genetic Algorithm, Parameters, Crossover Probability, Mutation Probability, Population Size

Abstract [English]

The classical traveling salesman problem(TSP) is simple to state but difficult a problem to solve. TSP seeks to determine the total distance or cost of visiting (n-1) cities or points and returning to the starting city or point. In this research, the Genetic Algorithm (GA) technique is utilized for solving the problem of finding the optimal tour around the nine Niger Delta state capitals in Nigeria which is an example of a traveling salesman problem. The partially mapped(PMX) crossover operator and the inversion mutation operator techniques were employed due to their simplicity. Genetic algorithms are evolutionary techniques used in solving optimization problems according to the survival of the fittest. The method does not provide an optimal exact solution, rather, it gives an approximated result in time. Data required for the tour were obtained from an online google map website where the distances between the state capitals and their coordinates (longitude and latitudes) were obtained. The MATLAB software which is suitable for scientific computations was used in coding the results show that the BB algorithm yielded an optimal tour of 1351km with a cyclic tour of (X_3,1), (X_1,9), (X_9,6), (X_6,8), (X_8,4), (X_4,7), (X_7,5), (X_5,2), (X_2,3) and then (X_3,1) after nine (9) iterations. Solving using the genetic algorithm with the four genetic parameters population size(N), maximum generation(G), crossover probability (P_c), and mutation probability(P_n) were used and set to 30; 10; 0.8; and 0.1 respectively yielded an optimal path of (8476125398) which is with an optimal tour of 1124.0KMs. genetic algorithm yielded an improved result.

Downloads

Download data is not yet available.

References

Adewale P., Akinwale A.J., And Otunbanowo K. A. (2011). Genetic Algorithm For Solving Traveling Salesman Problem, International Journal Of Advanced Computer Science And Applications, Vol. 2, Issue 1, Pp. 26 - 29

Ahmed Z.H. (2020). Adaptive Sequential Constructive Crossover Operator In A Genetic Algorithm For Solving The Travelling Salesman Problem, International Journal Of Advanced Computer Science And Applications, Vol. 11, Issue 2,Pp. 593 – 605. DOI: https://doi.org/10.14569/IJACSA.2020.0110275

Akande A., Costa A.C., Mateu J., And Henriques R. (2017). Geospatial Analysis Of Extreme Weather Events In Nigeria (1985 – 2015) Using Self-Organizing Maps, Hindawi Advances In Meteorology, Vol. 2017, Pp. 11. Available At: Https://Doi.Org/10.1155/2017/8576150 DOI: https://doi.org/10.1155/2017/8576150

Akindele S.T. And Adebo, A. (2004). The Political Economy Of River Basin And Rural Development Authority In Nigeria: A Retrospective Case Study Of Owena-River Basin And Rural Development Authority (ORBRDA), Journal Of Human Ecology, Vol.16, Issue 1, Pp. 55-62. Doi:10.1080/09709274.11905716. DOI: https://doi.org/10.1080/09709274.2004.11905716

Alkailany M. A. S. (2016). New Revised Ones Assignment Method For Solving Traveling Salesman Problem, International Journal Of Enhanced Research In Science, Technology & Engineering, Vol. 5, Issue 6, Pp. 169 – 174.

Braune R., Wagner S., & Affenzeller M. (2005). Applying Genetic Algorithms To The Optimization Of Production Planning In A Real-World Manufacturing Environment, Institute Of Systems Theory And Simulation, Johannes Kepler University.

Cacchiani, V., Contreras-Bolton, C., And Toth, P. (2020). Models And Algorithms For The Traveling Salesman Problem With Time-Dependent Service Times, European Journal Operational Research, Vol. 283, Issue 3, Pp 825 – 843. DOI: https://doi.org/10.1016/j.ejor.2019.11.046

Chineke, T.C., Idinoba, M.E., And Ajayi, O.C. (2011). Seasonal Evapotranspiration Signatures Under A Changing Landscape And Ecosystem Management In Nigeria. Implications For Agriculture And Food Security, American Journal Of Scientific And Industrial Research, Vol. 2, Issue 2, Pp. 191 – 204. DOI: https://doi.org/10.5251/ajsir.2011.2.2.191.204

Cook, W.J. (2001). The Traveling Salesman Problem. Available On:

Http:/Www.Tsp.Gatech.Edu/Methods/Talks/Cook01/Slide3.Html.20/10/2007.

Danusaputro S., Lee C., And Martin-Vega L.A. (1990). An Efficient Algorithm For Drilling Printed Circuit Boards, Computer And Industrial Engineering, Vol. 18, Issue 2, Pp. 145 – 151. DOI: https://doi.org/10.1016/0360-8352(90)90025-H

Deep, K. And Mebrahtu, H. (2011). Combined Mutation Operators Of Genetic Algorithm For The Traveling Salesman Problem, International Journal Of Combinatorial Optimization Problems And Informatics, Vol. 2, No. 3, Pp. 1 – 23. Available In: Http://Www.Redalyc.Org/Articulo.Oa?Id=265219635002

Devi R.B., Bariaskar E., And Devi O.B. (2014). Survey On Evolutionary Computation Tech Techniques And Its Application In Different Fields, International Journal On Information Theory, Vol. 3, Issue 3, Pp. 73 – 82. DOI: 10.5121/Ijit.2014.3308. DOI: https://doi.org/10.5121/ijit.2014.3308

Elegbede I. And Guerrero C. (2016). Algae Biofuel In The Nigeria Energy Context, Environmental And Climate Technologies, Pp. 44 – 60. DOI: 10.1515/Rtuect-2016-0005. Available At: Https://Www.Researchgate.Net/Publication/304003929 DOI: https://doi.org/10.1515/rtuect-2016-0005

Fashona M.J. And Omojola A.S.(2005). Climate Change, Human Security And Communal Clashes In Nigeria, Conference: Proceedings Of International Workshop On Human Security And Climate Change, Asker, Oslo, 21 – 23 June, 2005. DOI: 10.13140/ 2.1.2218.5928

Gharib A., Benhra J., And Chaouqi M. (2015). A Performance Comparison Of PSO And GA Applied To TSP, International Journal Of Computer Application, Vol. 130, Issue 15. DOI:10.5120/Ijca2015907188, Available At: Http://Www.Ijcaonline.Org /Research/ Volume130/ Number15/Gharib-2015-Ijca-907188.Pdf DOI: https://doi.org/10.5120/ijca2015907188

Geetha, R.R., Bouvanasilan, N., Seenuvasan, V. (2009). A Perspective View On Travelling

Salesman Problem Using Genetic Algorithm, World Congress On Nature & Biologically Inspired Computing, Coimbatore.

Goldberg D. And Lingle, R., (1985) “Alleles, Loci And The Traveling Salesman Problem,” In Proceedings Of The 1st International Conference On Genetic Algorithms And Their Applications, Vol. 1985, Pp. 154–159, Los Angeles, USA.

Hacizade U., And Kaya I. (2018). GA Based Traveling Salesman Problem Solution And Its Application To Transportation Routes Optimization, In 18th IFAC Conference On Technology, Culture And International Stability TECIS 2018: Baku, Azerbaijan, 13 – 15 September 2018

Hariyadi, Mutira, P., Nguyen, P.T., Iswanto, I., And Sudrajat,D. (2019). Traveling Salesman Problem Solution Using Genetic Algorithm, Journal Of Critical Reviews, Vol 7, Issue 1, Pp. 56 – 61. Https://Dx.DOI.Org/10.22159/Icr.07.01.10

Huang B., Yao L., Raguraman K. (2005). Bi-Level GA And GIS For Multi-Objective TSP Route Planning, Transportation Planning, And Technology, Vol 29, Issue 2, Pp. 105 – 124. DOI: https://doi.org/10.1080/03081060600753404

Hussain, Et Al. (2017). Genetic Algorithm For Traveling Salesman Problem With Modified Cycle Crossover Operator, Computational Intelligence And Neuroscience, Vol.2017. Https://Doi.Org/10.1155/2017/7430125 DOI: https://doi.org/10.1155/2017/7430125

Ite A.E., Ibok U.J., Ite M.U., And Petters S.W. (2013). Petroleum Exploration And Production: Past And Present Environment Issues In Nigeria’s Niger Delta, American Journal Of Environmental Protection, Vol. 1, Issue 4, Pp. 74 – 90. DOI: 10.12691/Env-1-4-2 DOI: https://doi.org/10.12691/env-1-4-2

Katoch S., Chauhan S.S., And Kumar V. (2020). A Review On Genetic Algorithm: Past, Present, And Future, Multimedia Tools And Applications, Vol. 80, Pp. 8091 – 8126. Https://Doi.Org/10.11042-020-10139-6 DOI: https://doi.org/10.1007/s11042-020-10139-6

Kirtiwant P.G. And Yogesh M.M. (2015). Traveling Salesman Problem With MATLAB Programming, International Journal Of Advances In Applied Mathematics And Mechanics, Vol. 2, Issue 3, Pp. 258 – 266.

Liu, F., Zeng, G. (2009). Study Of Genetic Algorithm With Reinforcement Learning To Solve The TSP, Expert Systems With Applications, 36, Pp.6995–7001. DOI: https://doi.org/10.1016/j.eswa.2008.08.026

Nigeria Highway Code-Revised Nigeria Highway Code (2021). Available Online At: Www.Highwaycode.Com.Ng

Pehn P., Addam O., Elzohbi M., Ozyer S.T., Alhajj A., Gao S., Liu Y., Ozyer T, And Kaya M. (2014). Reporting And Analyzing Alternative Clustering Solutions In Employing Multi-Objective Genetic Algorithm And Conducting Experiments On Cancer Data, Knowledge-Based Systems, Vol. 56, Issue C. Https://Dl.Acm.Org/Doi/10.5555/2842045.2842370 DOI: https://doi.org/10.1016/j.knosys.2013.11.003

Pekar, J., Brenzina, I., Kultan, J., And Dorokhov, O. (2020). Computer Tools For Solving The Traveling Salesman Problem, Development Management, Vol. 81, Issue 1, Pp. 25 – 39. DOI: 10.21511/Dm.18(1).2020.03. DOI: https://doi.org/10.21511/dm.18(1).2020.03

Pokharel M. (2020). Computational Complexity Theory (N, NP, NP-Complete, NP-Hard Problems). Available At: Https://Www.Researchgate.Net/Publication/342335335

Taha, M.A. (2017). Operations Research. An Introduction (10th Edition). Pearson Publishers, Arkansas.

Taiwo, J. (2008). Yar’Adua Creates Ministry Of Niger Delta, This Day. Retrieved 2019-09-20.

Wiener, R. (2003). Branch And Bound Implementations For The Traveling Salesperson

Problem - Part 1, In Journal Of Object Technology, Vol. 2, No. 2, Pp. 65-86. Http://Www.Jot.Fm/Issues/Issue_2003_03/Column7 DOI: https://doi.org/10.5381/jot.2003.2.2.c7