Sigma J Eng Nat Sci, Vol. 42, No. 6, pp.

1876−1883, December, 2024

Sigma Journal of Engineering and Natural Sciences

Web page info: [Link]
DOI: 10.14744/sigma.2023.00105

Research Article

Modified genetic algorithm with novel crossover and mutation operator

for travelling salesman problem
M.K. SHARMA1 , Sadhna CHAUDHARY1 , Laxmi RATHOUR2 , Vishnu Narayan MISHRA3,*
Department of Mathematics, Chaudhary Charan Singh University, Meerut, 250004, India
1

Department of Mathematics, National Institute of Technology, Chaltlang, Aizawl Mizoram, 796012, India
2

3
Department of Mathematics, Faculty of Science, Indira Gandhi National Tribal University, Lalpur, Amarkantak, Anuppur,
Madhya Pradesh 484887,India

ARTICLE INFO
ABSTRACT
Article history
Received: 11 July 2023 In this study, Genetic Algorithm (GA), a sort of randomized direct, iterative search methodol-
Revised: 19 September 2023 ogy built around natural selection, is employ in computers to discover approximations of solu-
Accepted: 11 October 2023 tions to optimisation and search issues. GA employs operators including selection, crossover,
and mutation to tackle. In case of NP-hard issues, particularly for travelling salesman problem
Keywords: (TSP), the GAs is beneficial. To reduce the overall distance, we propose a novel crossover
Crossover Operator, Genetic operator with its python code for the TSP. Along with the Python pseudo coding, we addi-
Algorithm, Muation Operator, tionally introduced a mutation operator to enhance the consummation of GA in determining
Python Coding, Travelling the shortest distance in the TSP. To emphasize the proposed crossover and mutation operator,
Salesman Problem we also illustrate different steps using examples. We integrated path representation with our
developed crossover and mutation operator as it is apparent method to represent a tour.

Cite this article as: Sharma MK, Chaudhary S, Rathour L, Mishra VN. Modified genetic al-
gorithm with novel crossover and mutation operator for travelling salesman problem. Sigma
J Eng Nat Sci 2024;42(6):1876−1883.

INTRODUCTION disciplines, comprises of soft computing, machine learning,

and operations research. It can optimise for continuous or
Almost The basic concept of genetic algorithms (GA) is
a search-based optimisation approach and is introduced by discrete variables without needing to know the derivatives.
Holland [1]. The ‘survival of the fittest’ premise is the foun- Additionally, it works with numerically generated data,
dation for GA, which are metaheuristics relies on natural experimental data, or analytical data and delivers a set of
selection and Genetics principles. GA are often utilised to optimal variables rather than simply one solution. GA pro-
produce high quality and superior solutions for search and cesses sustain a population of individuals and are iterative
optimisation challenges. In other words, GA tend to find and in character. In essence, GAs can be described as composed
offer near-optimal solutions to scenarios that could require of two primary phases: the first is “Selection” for produc-
a lot of time. GA are frequently employed in numerous ing the next generation, and the second is “Manipulation,”

*Corresponding author.
*E-mail address: vnm@[Link]; vishnunarayanmishra@[Link]
This paper was recommended for publication in revised form by
Regional Editor Ahmet Selim Dalkilic

Published by Yıldız Technical University Press, İstanbul, Turkey

Copyright 2021, Yıldız Technical University. This is an open access article under the CC BY-NC license ([Link]
Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024 1877

which manipulates the selected individuals to produce the

next generation using various techniques, including cross-
over and mutation. Each iteration in GA is referred to as “a
generation,” and a population of new candidate solutions
is created utilising various biologically inspired operators
including mutation, crossover, and selection. In GA, each
individual is represented by a string known as chromosome
and may also be regarded as a problem-solving strategy.
These strings comprise characters known as genes, which
contain certain values known as alleles. GAs is appropri-
ate candidate to tackle the constrained, unconstrained and
combinatorial problem.
Using genetic operations like selection, fitness, cross-
over, and mutation processes, GA seeks for the optimal
results.
• Fitness: The fitness value quantifies the similarity
between two individuals and is a favourable utility
metric that is determined for every individual in the
population.
• Selection: Each member of the population receives
several copies, which are used up in the mating pool to
create an entirely novel population. Therefore, the like-
lihood that an individual will produce additional copies
in the mating pool increases as fitness value increases.
• Crossover: Recombination of individuals generates
new individuals known as offspring or children. One-
point and two-point crossover are popular recombina-
tion strategies. Figure 1. Flow chart of GA.
• Mutation: Maintaining diversity in the population can
be done through mutation. Each individual is mutated
with a minute or extremely low chance, such as less than
III. Proportionally pick n/2 parents of the present
1.0.
population.
The procedures below can be used to define an uncom-
IV. Use the crossover operator to produce children by
plicated genetic algorithm and the flow chart for illustrat-
picking two parents at random.
ing various steps is shown in Figure 1. The 2-diemnsional
V. Employ mutation to vary findings a little bit.
array encompassing population size and chromosome size VI. Until all parents have been chosen and mated, repeat
defined the population. Here, population initialization can steps 4 and 5.
be done by utilizing two methods namely random and heu- VII. An entirely new population of chromosomes will
ristic [Link] fitness function ought to be quick replace the old one.
enough to calculate. It must quantify the degree to which a VIII. Determine each chromosome’s level of fitness in novel
given solution is fit or the degree to which fit people can be population.
created from the provided solution. IX. Stop when the number of generations reaches a pre-
When a GA run ends, a lot depends on the termina- determined maximum; otherwise, proceed to Step III.
tion condition of the GA. In general, we want a termination We have numerous representations in literature employ-
condition that, at the end of the run, puts the outcome very ing the GAs. Path, binary, adjacency,ordinal and matrix-
near to the bestone. The following are the termination cri- representation are some significant representations and
teria’s for the GA- the summary of these representation with novel crossover
• when X iterations have passed with no population operator is given in Table 1.
improvement. Arqub et al. [13] employ the continuous GA to solve
• when the number of generations is fixed. singular two-point boundary value problems. Arqub and
• when the value of the objective function reaches a spe- Hammour [14] discussed a method for employing con-
cific, predetermined value. tinuous GA for solving systems of second-order boundary
I. Using n chromosomes, create a starting generation. value problems. In order to validate this method, a few test
Here the population is initialized. problems were created and solved. Hammour et al. [15]
II. Assess each chromosome’s fitness. presented a GA approach for the modelling of dynamical
1878 Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

Table 1. List of different representations Table 2. Summary of approaches for TSP

Representation Crossover operator Author Exact Approach Heuristic approach

Binary Classical, repair Lidd[2] Branch and bound Genetic algorithm
Path Partially-mapped Goldberg and Lingle [3] Cutting Planes Neural network
Order Davis [4] Branch and Cut Simulated annealing
Sorted match Brady [5] Others Tabu search
Heuristic Grefenstette [6] Particle swarm optimization
Maximal preservative Muhlenbein et al. [7] Ant colony optimization
Voting recombination Muhlenbein et al. [8]
Order based Syswerda [9]
Heuristic Grefenstette [6] to optimize symmetric TSP with 532 cities. On the other
Order based Syswerda [10] hand, various heuristic algorithms are also introduced in
Position based Syswerda [10] order to tackle the TSP. Initially, Brady [5] proposed a GA
Alternating-positions Larranaga et al. [11] approach deal with TSP. Bhide et al. [23] proposed a Boolean
Adjacency Alternative edge Grefenstette et al. [12] approach with the help of neural network to deal with TSP.
Heuristic 1 Grefenstette et al. [12] Dorigo and Gambardella [24] proposed an approach with
Subtour chunks Grefenstette et al. [12] the help of ant colony system to tackle the TSP. Knox [25]
proposed the tabu search approach to solve the symmet-
Ordinal Classical operator Grefenstette et al. [12]
ric TSP. Later, Chiang and Russell [26] proposed simulated
annealing algorithms to cope with vehicle routing problem.
Thereafter, Focacci et al. [27] developed a hybrid exact
systems. For numerically approximating the solutions of method for TSP. A local search strategy was presented by
Troesch’s and Bratu’s problems, Hammour et al. [16] intro- Ibarki et al. [28] for addressing and arranging issues with
duce continuous GA. Recently, to approximate a class of extensive time window limitations. Larranaga et al. [11]
Lebesgue integrable functions, Raiz et al. [17] introduced reviewed the various methodologies used to resolve TSP
a novel sequence of linear positive operators. Schurer Beta by utilizing GA. Also, presented different crossover and
bivariate operators were initially developed by Mishra et al. mutation operators which are proposed to tackle the TSP
[18] in terms of generalisation exponential functions and with the GA. Thereafter, An amalgam GA was suggested by
their approximation characteristics. Nguyen et al. [29] to discover the TSP solution. Ghadle and
The Travelling Salesman Problem (TSP) is one of the Muley [30] proposed a modified version of GA encoded by
most well-known combinatorial issues in optimising. The using MATLAB to tackle the TSP. Kumar and Gupta [31]
TSP is one of the most recent optimisation problems to proposed a methodology to solve the TSP with fuzzy L-R
have undergone extensive deliberation. It was initially for- parameters. Majumdar and Bhunia [32] modelled an asym-
mulated as an optimisation problem in 1930. In TSP, the metric TSP in a way that the distance between each pair
objective is to determine probable tour such that a travelling of cities travelled is denoted as an interval value instead of
salesman visits each city exactly once and back to the ini- a precise value. Thereafter, Changdar et al. [33] modelled
tial city in order to minimize the total cost devoted or total a multi-objective TSP with triangular fuzzy parameters
distance covered. Since there are n! various approaches to and, proposed an effectual GA to tackle this modelled TSP.
locate the tour for n cities, specifically for 11 cities, there are Maity et al. [34] proposed a modified GA to cope with con-
39916 800 possible route to optimize the total cost. So, the strained solid TSP in different settings including fuzzy and
complexity of finding the best route increases as the num- crisp.
ber of cities increases. Thus, TSP is a candidate of NP (Non- We suggest a novel crossover operator for the TSP along
Polynomial) hard combinatorial optimization problems. with its Python source code. We entailed a mutation opera-
In existing literature, exact and metaheuristic algo- tor in addition to the Python pseudo coding to improve the
rithms are two approaches to tackle TSP as shown in table effectiveness of GA in calculating the shortest distance in
1. In case of exact algorithms, following are major exact the TSP. We additionally employ examples to demonstrate
algorithms in literature introduced to encounter with TSP; the proposed crossover and mutation operator at various
Dantzig et al. [19] introduced a methodology to solve the stages. We combined our newly designed crossover and
large-scale TSP. Later, Petberg [20] proposed a branch and mutation operator with path representation because this is
cut method to get the optimal solution of symmetric TSP. A an obvious way to express a tour.
cutting plane approach is proposed by Fleischmann [21] in This article is organized as follows; Section one is com-
order to tackle the TSP in case of a road network. Thereafter, pletely devoted to the basics of GA and the literature review
Petberg and Homg [22] proposed branch and cut method of GA and TSP. The mathematical formulation of the TSP
Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024 1879

is described in section two. Several types of representa- DIFFERENT TYPES OF REPRESENTATION

tion involved in GA are described in section three. Major
There have been a wide range of representations of a
crossover operators for path representation are presented in
chromosome to solve TSP problem by employing GA.
section four. Novel crossover operator is illustrated in sec-
Binary, path, adjacency, ordinal and matrix representation
tion five. On the other hand, the novel mutation operator is
are major representation forms available in literature.
given in section six. Finally, the section seven is devoted to
the conclusion of the article. Binary Representation
Each city in the n-cities TSP is represented in binary as
Mathematical Formulation of TSP
a string of [log2n] bits, and an individual is represented as a
One way to represent the TSP is as an integer linear pro-
string of n[log2n] bits.
gramming. The Dantzig-Fulkerson-Johnson (DFJ) formu-
Example: In case of a 6-cities TSP, each city assigned
lation and the Miller-Tucker-Zemlin (MTZ) formulation
by 3-bit string. The tour 2-1-3-6-5-4 depicted as by using
are well-known formulations of TSP available in the liter-
Table 3.
ature (Dantzig [35] & Velednitsky [36]). In some circum-
(001 000 010 011 100 101)
stances, the MTZ formulation is still beneficial, although
the DFJ formulation is stronger.
Table 3. An illustration of a visit of six cities in binary
Let n be the number of cities, cij be the cost (distance)
form ith to jth city, and ui be the dummy variable. i City i i City i
xij is a binary variable and defined as:
1 000 4 101
2 001 5 100
3 010 6 011

The MTZ formulation of TSP is as follows:

Path Representation
The elementary representation of a tour in TSP can be
done in a more appropriate way by using path representa-
tion. For a tour of n cities, if city i is the jth element of the
list, city i is the jth city to be visited.
Example:If n = 8. Then the tour is 4-2-3-1-7-5-8-6 is
represented as a string (4 2 3 1 7 5 8 6).

Ordinal Representation
In ordinal representation, ith member in set is a integer
between 1 to n - i + 1 and an ordered set consisting of vari-
ous destinations act as guide also exists.
Example: Let n = 8 and O = (1 2 3 4 5 6 7 8) be a refer-
ence list, then the tour 1-5-3-2-8-4-7-6 is represented by T
= (1 4 1 2 1 4 1 2 1)
The DFJ formulation of TSP is as follows:
Matrix Representation
In matrix representation, member ith row and jth col-
umn is 1 iff city i is visited before the city j
Example: The matrix representation of tour 2-3-1-4 is

CROSSOVER OPERATORS FOR TSP IN PATH

REPRESENTATOION
Here, the last constraint, known as a subtour elimina-
tion constraint, assures that no appropriate subset Q can Partially Mapped (PMX), Cycle (CX), Cycle (CX2) are
form a sub-tour, resulting in a single tour as the solution predominantly used crossover operators of path represen-
and not a union of smaller tours. tation in the current literature.
1880 Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

Partially Mapped (PMX) for the 5th, 6th, and 7th components of offspring because they
Partially Mapped Crossover operator (PMX) was intro- make up another cycle. As a result, we discover the follow-
duced by Goldberg and Lingle [3] for path representation of ing offspring:
chromosomes in path representation. In PMX, after choos- O1 = (1 2 6 4 7 5 3 8)
ing two random cut locations on the parents to produce off-
spring, one parent’s string is mapped onto the other parent’s Cycle Crossover Operator (CX) 2
string. Thereafter, a remaining bit are filled with the help of Hussain et al. [38] proposed cycle crossover operator 2
mapping with the constraint that no bit is repeated in the (CX2) for TSP to optimize distance travelled.
offspring. Step 1. Let us consider two parents for mating. Choose
Example:Let us consider two parents P1 and P2 with the 1st bit of the 1st offspring using 2nd parent string.
two random cut points Step 2. The bit selected in Step 1 is present in the 1st par-
P1 = (1 2 | 3 4 5 6 | 7 8) ent, followed by the same similar location bit selected in the
P2 = (2 7 | 5 8 4 1 | 6 3) 2nd parent, which is present in the 1st parent, and the similar
Then, the mapping segment between the cut points rep- location bit selected in the 2nd parent, which is then selected
licated with each other in order to build offspring, the map- for the first bit of the 2nd offspring.
↔ ↔ ↔
ping is 2 1,7 6,1 8. Step 3. The 1st parent will have the chosen bit from Step
3, and the 1st offspring would contain the following bit in
O1 = ( × × | 1 4 5 8 | × ×)
O2 = (× × | 3 4 5 6 | × ×) the 2nd parent’s identical place.
Step 4. Continue Steps 2 and 3 until the 1st bit of the 1st
Cycle Crossover Operator (CX) parent does not appear in the 2nd offspring, at which point
Cycle crossover (CX) operator was first introduced by the procedure may be stopped.
Oliver et al. [37]. Any bit in this operator is obtained via Step 5. If any bits remain, they will be similar in the 1st
any of the parents to determine its position. Let P1 and P2 parent and the 2nd offspring up to this point, and vice versa
be two parent string to illustrate the operator for both parents.
P1 = (1 2 3 4 5 6 7 8) Example:
P2 = (2 4 6 8 7 5 3 1) Let us consider two parent chromosomes for mating
Now, select 1st element of offspring from first element P1 = (3 4 8 2 7 1 6 5 )
of either of P1 or P2. Here from two options (1or 2), we will P2 = (4 2 5 1 6 8 3 7)
choose 1. For last element of O1, we must consider 8, as if 1 By employing above steps, the two offspring initiated
is taken then it would not result as a legal tour. are as follows:
O1 = (1 × × × × × × 8) O1 = (4 8 6 2 5 3 1 7)
Similarly, for 2nd and 4th element, we have 2 and 4 O2 = ( 1 7 4 8 6 2 5 3)
respectively.
O1 = (1 2 × 4 × × × 8)
PROPOSED CROSSOVER OPERATOR
The relative positions of the elements selected up until
this point are considered to form a tour. Think about the 3rd In this section we will propose the Increasing partially
element of the O1. Any of the parents can be the source for mapped crossover operator (IPMX) and the python coding
this component. Let’s say we choose it to come from parent of the proposed operator is given in Figure 2. The proposed
2. This indicates that the second parent must also be picked operator is defined by the following steps.

Figure 2. Python coding of proposed crossover operator.

Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024 1881

Table 4. Summary of mutation operator in GA

Mutation Operator Author

Simple Holland [1]
Insertion Fogel [39]
Exchange Banzhaf [40]
Scramble Syswerda [10]
Displacement Michalewicz [41]
Inversion Fogel [42]

Step 1. Select a pair of chromosome parents for mating.

Step 2. Pick out two random cut points on each parent
to construct two offspring.
Figure 3. Python coding of proposed mutation operator.
Step 3. First arrange the bits between two random cuts
in the increasing order for each parent chromosome
Step 4. Now these portions between cut points are
operators is presented in Table 4. In this section, we propose
mapped onto other parent strings.
a novel mutation operator of path representation in GA.
Step 5. Fill the remaining bits from the primary parent
This operator is completely defined by a linear function
such that there is no dispute.
Step 6. To fill the bits with conflict, use the notion of and is mathematically defined as follows:
partial mapping. Let xi be the bits in chromosome of n size
Example: Let us consider two parent chromosomes for L(xi)= xi + 1 ∀xi where xi represent bits in chromosome
mating with randomly two cut points marked by “|”. The python coding of the proposed operator is pre-
P1 = (1 2 | 3 4 5 6 | 7 8) sented in Figure 3.
P2 = (2 7 | 5 8 4 1 | 6 3) Example: Let us consider p = (2 3 5 6 1 4 7 8) be a parent
The two children O1 and O2 are constructed as follows: chromosome to emphasize the proposed mutation operator
Initially arrange all bits of randomly selected segment in a better way.
in the increasing order. Then mapped the resulted strings By applying the Linear function of mutation operator,
between cut points onto other parents. we get a child chromosome as
O1 = (× × | 1 4 5 8 | × ×)
C = (3 4 6 7 2 5 78 1)
O2 = (× × | 3 4 5 6 | × ×)
Now, fill the bits from original parent which does not
have any conflict. Here for O1, 2,7 are filled and for O2, 2,7 CONCLUSION
are filled.
Utilising the survival of the fittest principle, GA a form
O1 = (× 2 | 1 4 5 8 | 7 ×)
O2 = (2 7 | 3 4 5 6 | × ×) of evolution method to deal with optimisation issues. They
To fill the remaining bits, use the notion of partially have been effectively utilized in several types of optimi-
mapping. The first × in first offspring O1 is 1 which comes zation issues, including the TSP. In TSP, our main aim to
from P1 but 1 is already present in O1. So, in P1 we check locate a tour of every node in a weighted network and min-
the element corresponding to 1 of P2, here 1 ↔ 6, first × imise the overall weight, we must solve the TSP. We have
is occupies by 6. Again, the second × in the O1 is 8 but 8 is examined various methods of representations of a tour in
already present in O1. So, in P1 we check the element corre- TSP which are available in literature that could be employed
sponding to 8 of P2, here 8 ↔ 4, but 4 is present in O1, again in genetic algorithms attempting to solve the TSP. We also
check mapping 4 ↔ 5. But 5 is existing in O1, again check 5 reviewed partially mapped (PMX), cycle (CX) and cycle
↔ 3, 3 occupies the second × of in P1 crossover 2 (CX2) available in literature for path represen-
O1 = ( 6 2 | 1 4 5 8 | 7 3)
tation as it the any form of tour is originally represented as
O2 = (2 7 | 3 4 5 6 | 1 8)
path. In this article, we proposed modified version of GA
Similarly, we complete the second offspring O1.
by introducing an increasing partially mapped crossover
operator (IPMX) and a mutation operator to get optimize
PROPOSED MUTATION OPERATOR solution of a TSP. We also, provide python coding of our
GAs employ mutation to help the procedure evade local novel crossover and mutation operator for the better imple-
solutions and give the population newly developed, com- mentation of modified version of GA. GA and its modified
pletely improbable instances. The summary of mutation versions are applicable in different types of optimization
1882 Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024

problems other than TSP such as transportation problem, [9] Syswerda G. Schedule optimization using genetic
vehicle routing problem, neural networks, and so on. algorithms. In L. Davis (Ed.), Handbook of genetic
algorithms. USA: Van Nostrand Reinhold; 1991. p.
AUTHORSHIP CONTRIBUTIONS 332–349.
[10] Grefenstette JJ. Incorporating Problem Specific
Authors equally contributed to this work. Knowledge into Genetic Algorithms. In Davis, L.
(ed.) Genetic Algorithms and Simulated Annealing,
DATA AVAILABILITY STATEMENT Los Altos, CA: Morgan Kaufmann; 1987. p. 42–60.
The authors confirm that the data that supports the [11] Larranaga P, Inza I, Kuijpers CMH, Grana M, Lozano
findings of this study are available within the article. Raw JA. Algoritmos Geneticos en el Problema del Viajante
data that support the finding of this study are available from de Comercio. ‘ Informatica y Automatica (submit-
the corresponding author, upon reasonable request. ted). 1966.
[12] Grefenstette J, Gopal R, Rosmaita B, Van Gucht D.
Genetic Algorithms for the TSP. In Grefenstette,
CONFLICT OF INTEREST J. J. (ed.) Proceedings of the First International
The author declared no potential conflicts of interest Conference on Genetic Algorithms and Their
with respect to the research, authorship, and/or publication Applications, Hillsdale, New Jersey: Lawrence
of this article. Erlbaum; 1986. p. 160–165.
[13] Abu Arqub O, Abo-Hammour Z, Momani S,
ETHICS Shawagfeh N. Solving singular two-point boundary
value problems using continuous genetic algorithm.
There are no ethical issues with the publication of this Abstr Appl Anal 2012;2012:205391. [CrossRef]
manuscript. [14] Arqub OA, Abo-Hammour Z. Numerical solution
of systems of second-order boundary value prob-
REFERENCES lems using continuous genetic algorithm. Inf Sci
2014;279:396–415. [CrossRef]
[1] Holland J. Adaption in Natural and Artificial Systems.
[15] Abo-Hammour ZE, Alsmadi O, Momani S, Abu
Ann Arbor: University of Michigen Press; 1975. Arqub O. A genetic algorithm approach for predic-
[2] Lidd ML. The travelling Salesman Problem Domain tion of linear dynamical systems. Math Probl Eng
Application of a Fundamentally New Approach to 2013;2013:1–12. [CrossRef]
Utilizing Genetic Algorithms. Technical Report, [16] Abo-Hammour Z, Abu Arqub O, Momani S,
MITRE Corporation, 1991. Shawagfeh N. Optimization solution of Troesch’s
[3] Goldberg DE, Lingle Jr. R. Alleles, Loci and the TSP. and Bratu’s problems of ordinary type using novel
In Grefenstette, J. J. (Ed.). Proceedings of the First continuous genetic algorithm. Discrete Dyn Nat Soc
International Conference on Genetic Algorithms 2014;2014:401696. [CrossRef]
and Their Applications,Hillsdale, New Jersey: [17] Raiz M, Kumar A, Mishra VN, Rao N. Dunkl ana-
Lawrence Erlbaum; 1985. p. 154–159. logue of Sz $\acute {a} $ sz-Schurer-Beta operators
[4] Davis L. Applying Adaptive Algorithms to Epistatic and their approximation behaviour. Math Found
Domains. Proceedings of the International Joint Comput 2022;5:315–330. [CrossRef]
Conference on Artificial Intelligence. New York, [18] Mishra VN, Raiz M, Rao N. Dunkl analouge of Sz $\
USA: ACM Digital Library; 1985. p. 162–164. acute {a} $ sz Schurer Beta bivariate operators. Math
[5] Brady RM. Optimization strategies gleaned from bio- Found Comput 2023;6:651–669. [CrossRef]
logical evolution. Nature 1985;317:804–806. [CrossRef] [19] Dantzig G, Fulkerson R, Johnson S. Solution of a
[6] Grefenstette JJ. Incorporating Problem Specific large-scale traveling-salesman problem. J Oper Res
Knowledge into Genetic Algorithms. In Davis, Soc Am 1954;2:393–410. [CrossRef]
L. (ed.) Genetic Algorithms and Simulated [20] Petberg MW, Homg S. On the symmetric traveling
AnnealingLos Altos, CA: Morgan Kaufmann; 1987. salesman problems: a computational study. Math
p. 42–60. Prog Stud 1980;12:61–77. [CrossRef]
[7] Muhlenbein H, Gorges-Schleuter M, Kramer O. [21] Fleischmann B. A cutting plane procedure for the
Evolution algorithms in combinatorial optimiza- travelling salesman problem on road networks. Eur
tion. Paral Comput 1988;7:65–85. [CrossRef] J Oper Res 1985;21:307–317. [CrossRef]
[8] Muhlenbein H. Parallel Genetic Algorithms, [22] Padberg M, Rinaldi G. Optimization of a 532-city
Population Genetics and Combinatorial ¨ symmetric traveling salesman problem by branch
Optimization. In Schaffer, J. (ed.) Proceedings on and cut. Oper Res Lett 1987;6:1–7. [CrossRef]
the Third International Conference on Genetic [23] Bhide S, John N, Kabuka MR. A Boolean neural net-
Algorithms, Los Altos, CA: Morgan Kaufmann work approach for the traveling salesman problem.
Publishers; 1988. p. 416–421. IEEE Trans Comput 1993;42:1271–1278. [CrossRef]
Sigma J Eng Nat Sci, Vol. 42, No. 6, pp. 1876−1883, December, 2024 1883

[24] Dorigo M, Gambardella LM. Ant colony system: a salesman problem under fuzziness. Swarm Evol
cooperative learning approach to the traveling sales- Comput 2014;15:27–37. [CrossRef]
man problem. IEEE Trans Evol Comput 1997;1:53– [34] Maity S, Roy A, Maiti M. A modified genetic algo-
66. [CrossRef] rithm for solving uncertain constrained solid
[25] Knox JE. The application of tabu search to the travelling salesman problems. Comput Ind Eng
symmetric traveling salesman problem. Colarado: 2012;83:273–296. [CrossRef]
University of Colorado at Boulder; 1989. [35] Dantzig GB. Linear programming and extensions.
[26] Chiang WC, Russell RA. Simulated annealing meta- Princeton, NJ: Princeton University Press; 1993.
heuristics for the vehicle routing problem with time [36] Velednitsky M. Short combinatorial proof that the
windows. Ann Oper Res 1996;63:3–27. [CrossRef] DFJ polytope is contained in the MTZ polytope for
[27] Focacci F, Lodi A, Milano M. A hybrid exact the Asymmetric Traveling Salesman Problem. arXiv
algorithm for the TSPTW. Informs J Comput preprint arXiv 2018:1805.06997.
2013;14:403–417. [CrossRef] [37] Oliver IM, Smith D, Holland JR. A study of permu-
[28] Ibaraki T, Imahori S, Kubo M, Masuda T, Uno T, tation crossover operators on the traveling salesman
Yagiura M. Effective local search algorithms for problem. In Oliver IM, Smith DJ, Holland JRC (Ed.).
routing and scheduling problems with general Genetic Algorithms and their Applications. Sussex,
time-window constraints. Transp Sci 2007;39:206– London: Psychology Press; 2013. p. 224–230.
232. [CrossRef] [38] Hussain A, Muhammad YS, Nauman Sajid M,
[29] Nguyen HD, Yoshihara I, Yamamori K, Yasunaga M. Hussain I, Mohamd Shoukry A, Gani S. Genetic
Implementation of an effective hybrid GA for large- algorithm for traveling salesman problem with
scale traveling salesman problems. IEEE Trans Syst modified cycle crossover operator. Comput Intell
Man Cybern Part B (Cybernetics) 2007;37:92–99. Neurosci 2017;2017:430125. [CrossRef]
[CrossRef] [39] Fogel DB. An evolutionary approach to the traveling
[30] Ghadle KP, Muley YM. Travelling salesman problem salesman problems. Biol Cybrn 1988;60:139–144.
with MATLAB programming. Int J Adv Appl Math [CrossRef]
Mech 2015;2:258–266. [40] Banzhaf W. The ‘molecular’ traveling salesman. Biol
[31] Kumar A, Gupta A. Assignment and travelling sales- Cybrn 1990;64;7–14. [CrossRef]
man problems with coefficients as LR fuzzy parame- [41] Michalewicz Z. Genetic Algorithms + Data
ters. Int J Appl Sci 2015;10:155–170. Structures = Evolution Programs. Berlin Heidelberg:
[32] Majumdar J, Bhunia AK. Genetic algorithm for Springer Verlag; 1992. [CrossRef]
asymmetric traveling salesman problem with [42] Fogel DB. Empirical estimation of the computation
imprecise travel times. J Comput Appl Math required to discovery approximate solutions to the
2011;235:3063–3078. [CrossRef] traveling salesman problem using evolutionary pro-
[33] Changdar C, Mahapatra GS, Pal RK. An efficient gramming. Proceedings of 2nd Annual Conference
genetic algorithm for multi-objective solid travelling on Evolutionary Programming. 1993. p. 56–61.