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

Egba, Anwaitu Fraser; Okonkwo, Obikwelu R

doi:10.29121/granthaalayah.v9.i5.2021.3906

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

1 Department of Computer Science, School of Science Education (SSE), Federal College of Education (Technical), Omoku, Rivers, Enugu, Nigeria

2 Department of Computer Science, Faculty of Natural Sciences, Nnamdi Azikiwe University, Awka, Anambra, Nigeria

How to cite this article (APA): Fraser, EA, & Obikwelu R, O (2021). Genetic algorithm approach for optimal cyclic tour round the state capitals in nigeria’s niger delta region. International Journal of Research - GRANTHAALAYAH, 9(5), 171. doi: 10.29121/granthaalayah.v9.i5.2021.3906

Abstract

The traveling salesman problem (TSP) is a classical simple optimization problem that aims at determining the total distance or cost of visiting (n-1) 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, & Martin-Vega, 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, Contreras-Bolton, & 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 (n-1) 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 NP-complete or NP-hard (Wiener, 2003). The NP-complete which simply means a non-deterministic polynomial-time complete problem (Pokharel & Np-Complete, 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, (n-1), 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, near-optimal 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 cost-effective 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 petroleum-derived waste stream discharges has caused diverse health and socio-economic 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 oil-rich 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 re-occurring thing over years. Quick intervention and access the timely information during disasters (both natural and man-made) 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 real-world 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 capital-city 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² (Elegbede & Guerrero, 2016) and has a total of 36 state capitals plus the federal state capital, Abuja. The country’s North-South extent is about 1050 km and its extreme East-West 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^oN, the Sudan Savannah belt around 10^oN to 12^oN and the Sahel Savannah in areas above latitude 12^oN.

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 (Akwa-Ibom, Bayelsa, Cross-rivers, Delta, Edo, and Rivers states with capitals at Uyo, Yenagoa, Calabar, Asaba, Benin, and Port Harcourt respectively) from the south-south geopolitical zone, one state (Ondo with capital at Akure) from the south-west 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² (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¹(lat.5.20E, long.7.25N), Asaba²(lat.6.18E, long.6.75N), Benin³(lat.5.60E, long.6.32N), Calabar⁴(lat.8.32E, long.4.95N), Owerri⁵(lat.7.02E, long.5.48N), PortHarcourt⁶(lat.7.00E, long.4.75N), Umuahia⁷(lat.7.48E, long.5.53N), Uyo⁸ (lat.7.93E, long.5.05N), and Yenagoa⁹ (lat.6.26E, long.4.92N). From the obtained coordinates listed, travel routes can be shown between the cities (Figure 2 ).

https://www.granthaalayahpublication.org/journals-html-galley/html-images/5215fbb3-cf0d-42ba-99d4-96cb7da5e218image1.png — **Figure 2: Map showing the capital cities in the Niger Delta, Nigeria**

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¹, Asaba², Benin³, Calabar⁴, Owerri⁵, Port Harcourt⁶, Umuahia⁷, Uyo^8, and Yenagoa⁹. Also obtained are the coordinates (longitude and latitude in decimals of degrees) of the locations of the state capitals in the world map.

Table 1: Distances between capital cities in the states of the Niger Delta, Nigeria.

	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:

Table 2: Matrix showing distances between city i and city j (Alkailany, 2016)

[\begin{matrix} d_{11} & d_{12} & d_{13} & d_{14} & . . . & d_{1 n} \\ d_{21} & d_{22} & d_{23} & d_{24} & . . . & d_{2 n} \\ d_{31} & d_{32} & d_{33} & d_{34} & . . . & d_{3 n} \\ . & . & . & . & . . . & . \\ d_{n 1} & d_{n 2} & d_{n 3} & d_{n 4} & . . . & d_{n n} \end{matrix}]

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/e9f394ac-999d-460a-8853-4146d3b693c2-u1.png

This leads to the following formulation:

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/06ca731d-263e-43b0-9c34-37a2b148b615-u2.png

The constraint, $d_{i j} = \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_{i j}$ represents the distance between city i and j, and the $x_{i j}' s$ represents the decision variables in which: $x_{i j}$ is set to 1 when arc (i,j) is included in the tour, and it is set to 0 if otherwise. Basically, $(x_{i j}) \in X$ designates the set of constraints that prevents sub-tours 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 NP-hard 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 next-generation, 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.

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/dacd40c9-3ba8-41f0-8cd2-d946cb0828af-u3.png

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:

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/4dbbcf1e-9465-4a33-9c59-68f3a644be21-u4.png

Further bits from the original parents can then be filled for values that has no conflict as shown in eq.5:

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/453d4ddb-db9a-4e9d-a645-c140e2717f5d-u5.png

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

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/f90d6023-eed2-402b-872d-0f2487bffb6d-u6.png

In the same vein, we complete second offspring as well:

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/f30981ba-9ddc-462e-9e6e-89e4f7dd2575-u7.png

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:

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/777497aa-3307-4149-8bff-87158356781d-u8.png

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:

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/24212e77-f693-4708-926c-2d9f1212118c-u2.png

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).

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/3b6ddf64-2d04-4466-be49-1b6798cf5188-u9.png

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

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/7a58b209-d216-4262-9002-67aa51e29f46-u4.png

SELECTION PHASE

Two parents with the least total tour values are selected for crossover. The parents with the least values include:

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/d0dbf6a5-2d97-45b6-8677-cd671f275fcc-u5.png

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.

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/1b6a418c-3f33-43ea-a46b-c15d6e413f9f-u6.png

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

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/11bbf173-585b-43ea-9b48-2b5391a7e47c-u2.png

Applying crossover operator, we obtain the first crossover

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/497343f8-ce08-4fcf-8c52-99a680e207db-u1.png

We obtain,

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/83e7435e-a0f4-4ef5-986b-3496c79f214c-u7.png

MUTATION PHASE

Applying the inversion mutation operator on each of the two parents yields a new set of offspring

https://typeset-prod-media-server.s3.amazonaws.com/article_uploads/c90b2da0-bd90-4b67-bd28-09384552ae55/image/ad9ae726-5bcb-4611-8e59-2d0028413188-u8.png

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, ${B e n i n X (3)}_{31} \to {A k u r e X (1)}_{19} \to {Y e n a g o a X (9)}_{96} \to {P o r t H a r c o u r t X (6)}_{68} \to {U y o X (8)}_{84} \to {C a l a b a r X (4)}_{47} \to {U m u a h i a X (7)}_{75} \to {O w e r r i X (5)}_{52} \to {A s a b a X (2)}_{23} \to {B e n i n X (3)}_{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 ${U y o X (8)}_{84} \to {{C a l a b a r X (4)}_{47} \to {U m u a h i a X (7)}_{75} \to {P o r t H a r c o u r t X (6)}_{68} \to}_{31} {A k u r e X (1)}_{19} \to {A s a b a X (2)}_{23} \to {O w e r r i X (5)}_{52} \to {B e n i n X (3)}_{31} \to {Y e n a g o a X (9)}_{96}$ with an optimal tour of 1124.0KMs.

https://www.granthaalayahpublication.org/journals-html-galley/html-images/5215fbb3-cf0d-42ba-99d4-96cb7da5e218image2.png — **Figure 20: MATLAB solution of the tour around the Niger Delta state capitals**

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.

[1] Adewale, P., Akinwale, A. J. & Otunbanowo, K. A. (2011). Genetic Algorithm For Solving Traveling Salesman Problem. International Journal Of Advanced Computer Science And Applications 2, 26–29.

[2] 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 11, 593–605.

[3] Akande, A., Costa, A. C., Mateu, J. & Henriques, R. (2017). Geospatial Analysis of Extreme Weather Events in Nigeria (1985–2015) Using Self-Organizing Maps. Advances in Meteorology 2017, 1–11. Retrieved from https://dx.doi.org/10.1155/2017/8576150 10.1155/2017/8576150

[4] Akindele, S.T. & 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 16(1), 55–62. Retrieved from https://dx.doi.org/10.1080/09709274.2004.11905716 10.1080/09709274.2004.11905716

[5] Alkailany, M. A. S. (2016). New Revised Ones Assignment Method For Solving Traveling Salesman Problem. International Journal Of Enhanced Research In Science 5, 169–174.

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

[7] Cacchiani, V., Contreras-Bolton, C. & Toth, P. (2020). Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times. European Journal of Operational Research 283(3), 825–843. Retrieved from https://dx.doi.org/10.1016/j.ejor.2019.11.046 10.1016/j.ejor.2019.11.046

[8] Chineke, T. & Idinoba, M. (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 2(2), 191–204. Retrieved from https://dx.doi.org/10.5251/ajsir.2011.2.2.191.204 10.5251/ajsir.2011.2.2.191.204

[9] Cook, W. J. (2001). The Traveling Salesman Problem. In The Traveling Salesman Problem. Available On:

[10] Danusaputro, S., Lee, C.-Y. & Martin-Vega, L. A. (1990). An efficient algorithm for drilling printed circuit boards. Computers & Industrial Engineering 18(2), 145–151. Retrieved from https://dx.doi.org/10.1016/0360-8352(90)90025-h 10.1016/0360-8352(90)90025-h

[11] Deep, K. & Mebrahtu, H. (2011). Combined Mutation Operators Of Genetic Algorithm For The Traveling Salesman Problem. International Journal Of Combinatorial Optimization Problems And Informatics 2(3), 1–23.

[12] Devi, R. B., Bariaskar, E. & Devi, O. B. (2014). Survey On Evolutionary Computation Tech Techniques And Its Application In Different Fields. International Journal On Information Theory 3, 73–82.

[13] E. Ite, A., J. Ibok, U., U. Ite, M. & W. Petters, S. (2013). Petroleum Exploration and Production: Past and Present Environmental Issues in the Nigeria’s Niger Delta. American Journal of Environmental Protection 1(4), 78–90. Retrieved from https://dx.doi.org/10.12691/env-1-4-2 10.12691/env-1-4-2

[14] Elegbede, I. & Guerrero, C. (2016). Algae Biofuel in the Nigerian Energy Context. Environmental and Climate Technologies 17, 44–60. Retrieved from https://dx.doi.org/10.1515/rtuect-2016-0005 10.1515/rtuect-2016-0005

[15] Fashona, M. J. & Omojola, A. S. (2005). Climate Change, Human Security And Communal Clashes In Nigeria. In Conference: Proceedings Of International Workshop On Human Security And Climate Change. (pp. 21-23)

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

[17] Gharib, A., Benhra, J. & Chaouqi, M. (2015). A Performance Comparison of PSO and GA Applied to TSP. International Journal of Computer Applications 130(15), 34–39. Retrieved from https://dx.doi.org/10.5120/ijca2015907188 10.5120/ijca2015907188

[18] Goldberg, D. & 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)

[19] Hacizade, U. & Kaya, I. (2018). GA Based Traveling Salesman Problem Solution and its Application to Transport Routes Optimization. In IFAC-PapersOnLine. (Vol. 51, pp. 620-625) Elsevier BV Retrieved from https://dx.doi.org/10.1016/j.ifacol.2018.11.224 10.1016/j.ifacol.2018.11.224

[20] Hariyadi, M., Nguyen, P., Iswanto, P. T., Sudrajat, I. & D. (2019). Traveling Salesman Problem Solution Using Genetic Algorithm. Journal Of Critical Reviews 7(1), 56–61.

[21] Huang, B., Yao, L. & Raguraman, K. (2006). Bi-level GA and GIS for Multi-objective TSP Route Planning. Transportation Planning and Technology 29(2), 105–124. Retrieved from https://dx.doi.org/10.1080/03081060600753404 10.1080/03081060600753404

[22] Hussain, E. & Al, (2017). Genetic Algorithm For Traveling Salesman Problem With Modified Cycle Crossover Operator. Computational Intelligence And Neuroscience 2017.

[23] Katoch, S., Chauhan, S. S. & Kumar, V. (2021). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications 80(5), 8091–8126. Retrieved from https://dx.doi.org/10.1007/s11042-020-10139-6 10.1007/s11042-020-10139-6

[24] Kirtiwant, P. G. & Yogesh, M. M. (2015). Traveling Salesman Problem With MATLAB Programming. International Journal Of Advances In Applied Mathematics And Mechanics 2, 258–266.

[25] Liu, F. & Zeng, G. (2009). Study Of Genetic Algorithm With Reinforcement Learning To Solve The TSP, Expert Systems With Applications. Study Of Genetic Algorithm With Reinforcement Learning To Solve The TSP, Expert Systems With Applications 36, 6995–7001.

[26] Nigeria, (2021). Nigeria Highway Code-Revised Nigeria Highway Code. Available Online At: Www.Highwaycode .

[27] Pekár, J., Brezina, I., Kultan, J., Ushakova, I. & Dorokhov, O. (2020). Computer tools for solving the traveling salesman problem. Development Management 18(1), 25–39. Retrieved from https://dx.doi.org/10.21511/dm.18(1).2020.03 10.21511/dm.18(1).2020.03

[28] Peng, P., Addam, O., Elzohbi, M., Özyer, S. T., Elhajj, A., Gao, S., Liu, Y., Özyer, T., Kaya, M., Ridley, M., Rokne, J. & Alhajj, R. (2014). Reporting and analyzing alternative clustering solutions by employing multi-objective genetic algorithm and conducting experiments on cancer data. Knowledge-Based Systems 56, 108–122. Retrieved from https://dx.doi.org/10.1016/j.knosys.2013.11.003 10.1016/j.knosys.2013.11.003

[29] Pokharel, M. ;. N. & Np-Complete, N. P. (2020). Computational Complexity Theory. Computational Complexity Theory .

[30] Taha, M. A. (2017). Operations Research. An Introduction. Operations Research. An Introduction .

[31] Taiwo, J. (2008). Yar’Adua Creates Ministry Of Niger Delta, This Day. Yar’Adua Creates Ministry Of Niger Delta, This Day .

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