GENETIC ALGORITHM APPROACH FOR OPTIMAL CYCLIC TOUR ROUND THE STATE CAPITALS IN NIGERIA’S NIGER DELTA REGION
Abstract
The traveling salesman problem (TSP) is a classical simple optimization problem that aims at determining the total distance or cost of visiting (n1) points and returning to the starting point. This research uses the Genetic Algorithm (GA) technique to find an optimal tour around the nine Niger Delta state capitals cities in Nigeria. The partially mapped (PMX) crossover operator and the inversion mutation operator techniques were employed. The method provides an approximated optimal result in time. The data for the research was obtained through an online google map where the distances between the cities and their coordinates (longitude and latitudes) were obtained. The MATLAB software 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}) in 9 iteration circles. While the GA with the population size, maximum iteration, crossover probability, and mutation probability set to 30, 10, 0.8, and 0.1 respectively, yielded an optimal path and an optimal tour 8476125398, that is
and 1124.0kms respectively. An improved result was achieved using the GA technique.
Keywords
Traveling Salesman Problem, Genetic Algorithm, Parameters, Crossover Probability, Mutation Probability, Population Size
INTRODUCTION
Routing models, according to (Pekár, Brezina, Kultan, Ushakova, & Dorokhov, 2020), are one of the most common discrete and combinatorial optimization problems in practice. They are models used in organizing a collection of things like positions, job schedules, towns, places, and so on, into orders or paths that could sometimes form all points into a single sequence or requiring several routes (Danusaputro, Lee, & MartinVega, 1990). The Traveling Salesman Problem (TSP) is adjudged as the simplest and most popular of routing problems that seeks the smallest total distance of cyclic travel through an N set of points or cities such that each point or city is visited precisely once and the traveler returning to the starting city (Nigeria, 2021). It was also defined as “a call for determining a Hamiltonian tour (i.e., a tour visiting each customer exactly once) that minimizes the total tour duration, given by the sum of travel and service times” (Cacchiani, ContrerasBolton, & Toth, 2020). Thus, its objective is in searching for an optimal “tour” through n number of locations or towns that starts at one location, visiting each of the (n1) remaining locations once and only one time, and then returning to the starting location. The tour whose total distance or cost is the least is the optimal solution.
The importance of the TSP cannot be overemphasized as it represents a class of problems in computational complexity theory, known as NPcomplete or NPhard (Wiener, 2003). The NPcomplete which simply means a nondeterministic polynomialtime complete problem (Pokharel & NpComplete, 2020), are problems whose computation time for an exact solution increases exponentially with problem size and thus intractable. Thus, the exhaustive search procedure fails because of time requirements and since cyclic permutations grow exponentially with N, the number of cities, points, or nodes. According to Cook (2004), a visit to 2 cities is trivial and a visit to 4 cities will require 6 potential routes (that is, (n1), where n indicates the number of towns or nodes. Implying that, if a travel 12 cities are intended, then 39 million possible routes will be confronted. And for 16 cities, a total of more than 653 billion paths will be required. Consequently, three major problems are faced by researchers in solving the TSP problem:

Determining an optimal solution spending a lot of time in solving

Determining an optimal solution using up a large chunk of the computer’s memory and

Determining an optimal solution timely but with an approximated solution, that is, nearoptimal solution.
The application of TSP can be in a widespread area of societal problems like mathematicians, computer scientists, and science researchers, and other areas such as town planners, traffic control managers, security checks, manufacturers of circuit boards, easy electrification of cities, and so on. No doubt, this study will add to the number of literatures under this topic as well as provide an answer to a costeffective way of navigating around, monitoring projects or election processes, and trading in the region.
In Nigeria, the Niger Delta area that is seen as the ‘oil hub’ of the nation has attracted a lot of attention home and abroad, recently. Petroleum exploration, production, and oil and gas exportation by the petroleum sector in this region have over the years boosted the economy of the nation (Ite, Ibok, Ite, & Petters, 2013). The nation virtually depends on the resources from this area. However, these activities have local disadvantageous and significant impacts on the atmospheric condition, soil and sediments, surface and groundwater, marine environment, and terrestrial ecosystems in the region. Environmental pollution as a result of hydrocarbons and petroleumderived waste stream discharges has caused diverse health and socioeconomic problems, as well as the degradation of the host communities in the region. These challenges triggered the establishment of agencies such as the Niger Delta Development Commission (NDDC) in 2000 which was given the mandate to develop the oilrich region, and the formation of the Ministry of Niger Delta Affairs with the NDDC becoming a parastatal under the Ministry (Taiwo, 2008). Other Federal government agencies established to operate in this region include the National Emergency Management Agency (NEMA), Niger Delta Basin Development Authority (NDBDA) mandated to “improve agriculture and rural development through irrigation, control of river pollution and flooding, and assist farmers in processing food crops” (Akindele & Adebo, 2004) and so on. A common problem faced by these bodies is easy to access and reaching out in time to all the suburbs that make up the area, thus poor monitoring of projects resulting in abandonment projects as well as poorly executed projects is a common reoccurring thing over years. Quick intervention and access the timely information during disasters (both natural and manmade) are almost at zero levels of response. Private activities such as Trading and other businesses within the region is also affected by the travel cost and the nature of the terrain and bad road built by the government. This study is therefore timely as some of these identified problems will be examined and solutions proffered.
The genetic algorithm (GA)  an evolutionary computation (EC) and soft computing technique that is employed for the estimation of realworld problems and decision making based on methods adapted from the field of genetics in biology (Devi, Bariaskar, & Devi, 2014) is the model of focus in this study. The model allows the encoding of possible model behaviors into “genes” like it is done in biological genetics. Current models are rated and allowed to mate after each generation, an exchange is made on the genes, and selections, crossovers, and mutations can occur. We then discard the current population and its offspring forms the next generation. Also, GA describes a variety of modeling or optimization techniques that claim to mimic some aspects of biological modeling in choosing an optimum solution to a problem (Adewale, Akinwale, & Otunbanowo, 2011). Naturally, the model’s objective is represented in an easy way such that modifications can be easily made, automatically. A large number of candidate models are then generated and tested against the existing data. Each of the models is graded and the “best” among them are retained for the next generation. These models are then perturbed randomly and a repeat of the process is continued until there is convergence. The winners can “mate” to reproduce the next generation when the model is constructed such that they have “genes”.
This study is aimed at (a) determining the optimum value and the optimal path for a cyclic tour around the state capital cities of the nine states in the Niger Delta area using the Genetic Algorithm (GA) technique; (b) determining the best path distance of the tour by testing parameter values of different population sizes and numbers of generations while maintaining the same crossover and mutation probabilities in the genetic algorithm for the capitalcity states.
MATERIALS AND METHOD
CASE DESCRIPTION AND THE GEOGRAPHY OF THE NIGER DELTA AREA
According to (Akande, Costa, Mateu, & Henriques, 2017), Nigeria is a country located in the tropical zone of West Africa between latitudes 4° N to 14 °N and longitudes 2° 2’E to 14° 30’E. It covers an area totaling 923 770 km^{2} (Elegbede & Guerrero, 2016) and has a total of 36 state capitals plus the federal state capital, Abuja. The country’s NorthSouth extent is about 1050 km and its extreme EastWest extent is about 1150 km. The borders of the country include the Chad Republic to the northeast, the Benin Republic to the west, the Niger Republic to the northwest and north, and the east is Cameroon, while the southern part of the country’s territory is bordered by the Atlantic Ocean forms the southern limits (Figure 2 ). According to (Chineke & Idinoba, 2011), “Nigeria is indeed a unique tropical country that cuts across all tropical ecological zones, stating that, from the Atlantic Ocean down to the edge of the Sahara, all tropical ecological zones are found”. (Fashona & Omojola, 2005), pointed out that the southern zone of Mangrove swamp located between latitude 4^{o} and 6^{o} 30’ N, the Tropical rainforest found around latitude 6^{o} 30’ to 7^{o} 45’ stretching from the southwest to the southeast, the Guinea Savannah belt around latitude 7^{o} 45’ N to 10^{o}N, the Sudan Savannah belt around 10^{o}N to 12^{o}N and the Sahel Savannah in areas above latitude 12^{o}N.
The Niger Delta region of the country is located in the delta of the Niger River sitting directly on the Gulf of Guinea on the Atlantic Ocean in Nigeria. It is made up of nine coastal southern states which include all six states (AkwaIbom, Bayelsa, Crossrivers, Delta, Edo, and Rivers states with capitals at Uyo, Yenagoa, Calabar, Asaba, Benin, and Port Harcourt respectively) from the southsouth geopolitical zone, one state (Ondo with capital at Akure) from the southwest geopolitical zone and two other states (Abia and Imo with capitals at Umuahia and Owerri respectively) from the southeast geopolitical zone of Nigeria. The region, which is now officially defined by the Nigerian government, extends over 70,000km^{2} (27,000 sq mi) and makes up 7.5% of Nigeria’s landmass. This region is the oil and natural gas hub of the nation therefore, a tour around the region from time to time by authorities is a must. It is estimated that over 38 billion barrels of crude oil still resides under the delta as of early 2012.
The coordinates of the capital cities of the Nigeria’s Niger Delta ,according to (Chineke et al., 2011) include, Akure^{1}(lat.5.20E, long.7.25N), Asaba^{2}(lat.6.18E, long.6.75N), Benin^{3}(lat.5.60E, long.6.32N), Calabar^{4}(lat.8.32E, long.4.95N), Owerri^{5}(lat.7.02E, long.5.48N), PortHarcourt^{6}(lat.7.00E, long.4.75N), Umuahia^{7}(lat.7.48E, long.5.53N), Uyo^{8} (lat.7.93E, long.5.05N), and Yenagoa^{9} ^{ }(lat.6.26E, long.4.92N). From the obtained coordinates listed, travel routes can be shown between the cities (Figure 2 ).
Movements and means of transportation in this region are mainly by land(road) and water. In this study, we consider the only movement by land(road). The state capitals are all linked and accessible by roads.
DATA SOURCE
The data for this research is the driving distances and land distances between the nine capital cities in the Niger Delta, Nigeria (Table 1 ), sourced from an online google map calculator (www.distancecalculator.net/country/nigeria). The distances are measured in kilometers. The nine capital cities, arranged in alphabetic order include, Akure^{1}, Asaba^{2}, Benin^{3}, Calabar^{4}, Owerri^{5}, Port Harcourt^{6}, Umuahia^{7}, Uyo^{8,} and Yenagoa^{9}. Also obtained are the coordinates (longitude and latitude in decimals of degrees) of the locations of the state capitals in the world map.

Aku 
Asa 
Ben 
Cal 
Owe 
PH 
Umu 
Uyo 
Yen 
Aku 
 
279 
153 
582 
374 
454 
416 
500 
397 
Asa 
279 
 
130 
307 
99 
199 
139 
227 
224 
Ben 
153 
130 
 
432 
225 
285 
267 
352 
229 
Cal 
582 
307 
432 
 
208 
216 
163 
95 
320 
Owe 
374 
99 
225 
208 
 
99 
61 
127 
128 
PH 
454 
199 
285 
216 
99 
 
116 
135 
118 
Umu 
139 
139 
267 
163 
61 
116 
 
82 
189 
Uyo 
500 
227 
352 
95 
127 
135 
82 
 
238 
Yen 
397 
224 
229 
320 
128 
118 
189 
238 
 
Table 1 shows thedata items of the capital cities of the states in the Niger Delta area of Nigeria. The distances are classified as symmetrical because the distance, time of travel, or cost of passing from any point i to any other point j is the same as that of a journey from point j to point i, that is, ( ${d}_{i,j}={d}_{j,i}$ ), otherwise, it is asymmetric. In this instance, factors such as nature of the road, traffic jam, weather condition or rainy day, and other factors that can alter the distance and time of travel from one city to the other are not considered, thus we are dealing with the symmetric case. If these factors were considered, the cost of travel to and from two points or cities will not have been the same which would have resulted in an asymmetric case. In the given data in Table 1 , the recommended driving speed limit by Federal Road Safety Commission (FRSC), Nigeria which is 80km/hrs. is used in the measuring of the driving distances between capital cities, measured in Kilometers (Nigeria, 2021).
FORMULATING THE SYMMETRIC TSP
The traveling salesman problem can be modeled and formulated in different forms, though none is straightforward. According to (Alkailany, 2016), the integer linear programming (ILP) model of the symmetric case employ decision variables, $i<j$ . Now considering Table 2 , where the distance matrix ${d}_{i,j}$ represents a distance between city i and city j.
A simple formulation of the TSP model based on the model of (Taha, 2017) and (Pekár et al., 2020) is as follows:
$\left[\begin{array}{cccccc}{d}_{11}& {d}_{12}& {d}_{13}& {d}_{14}& ...& {d}_{1n}\\ {d}_{21}& {d}_{22}& {d}_{23}& {d}_{24}& ...& {d}_{2n}\\ {d}_{31}& {d}_{32}& {d}_{33}& {d}_{34}& ...& {d}_{3n}\\ .& .& .& .& ...& .\\ {d}_{n1}& {d}_{n2}& {d}_{n3}& {d}_{n4}& ...& {d}_{nn}\end{array}\right]$

This leads to the following formulation:
The constraint, ${d}_{ij}=\infty $ ensures that the salesman is always on the move to cities that he or she has not yet visited.
In the above model, n represents the number of cities or points, ${d}_{ij}$ represents the distance between city i and j, and the ${x}_{ij}\text{'}s$ represents the decision variables in which: ${x}_{ij}$ is set to 1 when arc (i,j) is included in the tour, and it is set to 0 if otherwise. Basically, $\left({x}_{ij}\right)\in X$ designates the set of constraints that prevents subtours in the feasible solutions, especially those consisting of a single tour.
SOLVING TSP WITH GENETIC ALGORITHM METHOD
The genetic algorithm (GA) is one among the number of search optimization techniques in artificial intelligence that offers heuristic methods solutions for NPhard problems such as TSP. GA as an evolutionary algorithm is inspired by Darwin’s theory of biological or evolutionary changes (Katoch, Chauhan, & Kumar, 2021). It uses random search techniques. It works using a population of individuals. Thus, it starts searching the set of the points, until reaches the global optimum. It utilizes operators such as natural selection, crossover, and mutation for the evolution of a population. Its solutions can be exact or approximate (Peng et al., 2014), (Geetha, Bouvanasilan, & Seenuvasan, 2009), (Liu & Zeng, 2009).
In the logic of GAs, solution vectors are identified as chromosomes or persons. Each of the chromosomes is made of disconnected units known genes. Each of the gene controls one or many elements of a person or chromosome. A chromosome is usually seen as a unique solution in the outcome space. GA commonly functions with a set of chromosomes, that is, a population that is normally randomly initialized before processing.
GENETIC ALGORITHM’S BASIC SOLUTION STEPS
In this study, the algorithm proposed for this study combines a simple and pure genetic algorithm as defined by (Gharib, Benhra, & Chaouqi, 2015), (Hussain & Al, 2017). The algorithm is as follows:

Initialization: Generate an initial population of P chromosomes. This population can be of any size and is generally generated randomly.

Evaluation: Evaluation of each chromosome or member of the population is carried out and the ‘fitness’ value for that member is determined.

Choose Selection of a pair (P/2) of parents from the recent population through proportional selection is done.

Selection: Discard the bad designs and two parents are randomly selected to create offspring. Only the best members or chromosomes are retained in the population.

Crossover: By combining the characteristics of the selected chromosomes or members, we generate new chromosomes or members using crossover operators. This is like imitating nature’s reproduction system. This is done so that certain traits from two or more chromosomes or persons, and even ‘fitter’ offspring are created.

Mutation: Here, small changes are made to the genomes of chromosomes to maintain the diversity of genetics from one generation of a population to the other.

Repeat: On obtaining the population’s nextgeneration, steps four, five, and six are started again until all parents in the population are selected and reproduced.

Replace the previous population of chromosomes or members with a new one.

Evaluate each chromosome or member’s fitness for the new population.

Terminate the process if the number of generations meets the set upper bound target result; otherwise, go to step three.
When the termination criteria are satisfied, the search process is stopped. In general, the preset maximum generation set is used as the criteria for stopping the search process. The best chromosome or member found in the current population is the optimum solution to the problem.
Three things are very important in genetic algorithms. They include the criteria for selection, crossover, and mutation (Hussain et al., 2017). Among these, the most crucial is the crossover operator. In literature, several crossover techniques have been proposed and all are of significant importance. In this research, we employ a type of path representation crossover technique known as the Partially Mapped Crossover (PMX) operator. The path representation technique is the most suitable for TSP problems which is a tour problem. For instance, a tour $1\to 5\to 7\to 3\to 6\to 2\to 4\to 8$ can be represented as (15736248).
PARTIALLY MAPPED CROSSOVER OPERATOR
The partially mapped (PMX) operator is a crossover technique originally proposed by Goldberg and Lingle in their study titled “Alleles, Loci and Traveling Salesman Problem” (Goldberg & Lingle, 1985) in 1985. On each of the two parents selected, two cut points are chosen randomly to build a new offspring. The portion between the cut points of one parent’s thread is mapped onto the other parent’s thread and an exchange is made on the remaining information.
For instance, consider two parents’ tours with randomly one cut point between 3rd and 4th bits and another cut point between 6th and 7th bits as shown in eq.3. Vertical lines like (“”) are used to mark the two cut points as in eq3.
The mapping is done between values within the cut points (Ahmed, 2020). In the examples in eq.3, 3↔1, 6↔7, and 2↔8 forms the mapping systems. Two mapping segments are copied with each other to form offspring as shown in eq.4:
Further bits from the original parents can then be filled for values that has no conflict as shown in eq.5:
Accordingly, the first × in the first offspring(O1) in eq.4 is 1 which is obtained from the first parent (P1) nonetheless 1 is in this offspring already, so mapping 3↔1 is checked, and value 3 occupies the first x. Likewise, in the second ×, the first offspring is 7 which is obtained from the first parent(P1), however, 7 is in this offspring; thus, mapping 6↔7is checked, so 6 occupies the second x. Lastly, we consider the last x in the first offspring which is 8. 8 exists in the offspring, consequently, mapping 2↔8 is checked and 2 occupies the last x on the first offspring.
Thus the offspring 1 is
In the same vein, we complete second offspring as well:
INVERSION MUTATION OPERATOR
The inversion mutation operator was employed in this research since it is one of the methods most suitable for traveling salesman problems (Deep & Mebrahtu, 2011). It assists in selecting two positions within a chromosome/ tour at random and then the cities or nodes in the substring between these two positions (Huang, Yao, & Raguraman, 2006). Consider the chromosomes/tours (P1) listed in eq.8, for example:
If a sub tour 3 6 2 is selected at random using two positions, i.e.,
𝑃1 = (1 5 7  3 6 2 4 8), and inverting the sub tour, the mutated tour (M) will be
M = (1 5 7 2 6 3 1 7 9 8), meaning the positions of the first and the last of the randomly selected sub tour is swapped.
RESULTS AND DISCUSSION
Here, the sourced sample data given below is solved using the Genetic Algorithm (GA) techniques, and optimal solutions are presented. The results were obtained using an Intel i8 CPU PC with 16GB of RAM, Windows XP operating system, and MATLAB software.
SOLUTION TO TSP USING GENETIC ALGORITHM METHOD
The optimal tour/travel solution for a tour around the Niger Delta Development state capitals using the genetic algorithm and its MATLAB simulated result is presented.
1 
2 
3 
4 
5 
6 
7 
8 
9 
Akure 
Asaba 
Benin 
Calabar 
Owerri 
Port H. 
Umuahia 
Uyo 
Yenagoa 
INITIALIZATION PHASE
At point t = 0 in G(t) generation, a population size with N number of chromosomes is randomly generated. Each of the generated chromosomes is a possible solution to the problem. Suppose, we take N as 6 for this problem. Each chromosome holds 9 genes representing the number of cities in the problem being solved. The population contains 6 chromosomes generated randomly as follows:
EVALUATION OF FITNESS FUNCTION PHASE
For all Vi, i Є [1…6] chromosomes, F(Vi) which is the conformity value is calculated with the formula in eq.8 (Hacizade & Kaya, 2018).
In eq.8, G(Vi) represents the overall distance toured by the salesman. Since we are solving for the shortest distance, the smaller the value of G(Vi) gets the chromosome’s conformity value higher proportionality.
For
SELECTION PHASE
Two parents with the least total tour values are selected for crossover. The parents with the least values include:
CROSSOVER PHASE
Applying the partially mapped Crossover on the two least optimal values of the sum of distances between all cities, obtain a new set of offspring.
cutting from the value between the 3^{rd} and 4^{th} bit; and cutting from the value between the 6^{th} and 7^{th} bit, we obtain
Applying crossover operator, we obtain the first crossover
We obtain,
MUTATION PHASE
Applying the inversion mutation operator on each of the two parents yields a new set of offspring
REPEAT
Steps 4 and 5 are repeated until the optimal path and optimum distance value is obtained.
EXPERIMENTAL SOLUTION TO TSP USING MATLAB
The genetic algorithm in MATLAB software is applied to provide a solution to the cyclic tour around the 9 state capitals cities in the Niger Delta region. The transition distances between the 9 capital cities n Table 1 are imposed into the code. The experimentation using the branch and bound (BB) method on the same set of data yielded an optimal solution of 1351KMs and an optimal path of (36847523). That is, ${BeninX\left(3\right)}_{31}\to {AkureX\left(1\right)}_{19}\to {YenagoaX\left(9\right)}_{96}\to {PortHarcourtX\left(6\right)}_{68}\to {UyoX\left(8\right)}_{84}\to {CalabarX\left(4\right)}_{47}\to {UmuahiaX\left(7\right)}_{75}\to {OwerriX\left(5\right)}_{52}\to {AsabaX\left(2\right)}_{23}\to {BeninX\left(3\right)}_{31}$ . In solving the same problem using the genetic algorithm, four parameters (i.e., population size (N_{p}), maximum generation (G_{m}), crossover probability (P_{c}), and mutation probability (P_{n})) were used and each set to 30; 10; 0.8; and 0.1 respectively. This yielded an optimal path of (8476125398) which is ${UyoX\left(8\right)}_{84}\to {{CalabarX\left(4\right)}_{47}\to {UmuahiaX\left(7\right)}_{75}\to {PortHarcourtX\left(6\right)}_{68}\to}_{31}{AkureX\left(1\right)}_{19}\to {AsabaX\left(2\right)}_{23}\to {OwerriX\left(5\right)}_{52}\to {BeninX\left(3\right)}_{31}\to {YenagoaX\left(9\right)}_{96}$ with an optimal tour of 1124.0KMs.
The genetic algorithm (GA) finds a better improved optimum path and shortest tour/distance results for the cyclic tour problem. However, it was observed that the optimal solution largely depends on the technique employed in the encoding of the problem, the values of population size and maximum generation are chosen, and the method of crossover and mutation that is used.
CONCLUSION AND RECOMMENDATIONS
This research confirms the assertion by (Hariyadi, Nguyen, Iswanto, Sudrajat, & D, 2019) that “the problem of the Traveling Salesman Problem can be adequately solved using the genetic algorithms” and exposes the effectiveness and efficiency of the genetic algorithm technique especially in cases where the number of cities involved is large. The genetic algorithm can determine the optimal solution path and the optimum global value of the entire mileage with several iterations without affecting time and space complexity. The starting point or initial route of the tour does not have to start from a particular city only but any other city can be the starting point. The results reported in this research is quite interesting and would be of great benefit to transport and logistic planners, traders plying their trade within the region, and other government bodies which include Niger Delta Development Company (NDDC), The Niger Delta Ministry, town planners, goods distributors, air transport companies, rural and urban electrification, and road construction companies in Nigeria.
FUTURE STUDY
It was observed that the optimal solution of a traveling salesman problem using a genetic algorithm rests very much on the set values of the 4 genetic parameters (size of the population, maximum number of generation/iterations, the crossover probability, and the mutation probability). Also, there are variations of the crossover and mutation technique which also affects the results. These factors make the determination of target solutions difficult. Consequently, the researchers suggest that further studies should be carried out to overcome these challenges.