INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1204
THE TRAVELING SALESMAN PROBLEM: MATHEMATICAL MODELING AND
OPTIMAL SOLUTIONS
Mamatova Zilolakhan Khabibullokhanovna
Fergana state university associate professor , pedagogy sciences according to philosophy
Doctor of Philosophy (PhD)
Orchid : 0009-0009-9247-3510
E-mail:
Abdumajidova Mukaramkhan Iqbaljon kizi
Fergana State University Practical mathematics 3rd year of study
Email:
mukarramaabdumajidova1@gmail.com
Abstract:
Salesman issues trade in the field of products distribution , sales and transportation
costs to calculate These issues trade representative planned routes and work efficiency
increase for important is considered . Within the scope of the issue salesman work time ,
every one the store product sell opportunities , and various to cities to go time determination
through total sold products or done affairs This type is issues not only trade representatives
efficiency increase , maybe the company general business strategies to optimize help gives .
Key words :
distances matrix , route , closed route , route length , whole valuable variables ,
graph , Hamilton outline ( Hamilton cycle ), networks and borders method , cited matrix ,
backpack ( bomber aircraft (issue about ) , resources , cargo, loads transportation ( flight ).
Introduction .
Processes research and optimal management – decision acceptance to
do and systems to optimize scientific fields oriented .
1-Process research resources effective distribution for mathematician models , linear
programming , games theory and networks optimization such as from methods uses .
2-Optimal management systems the most good management strategies determination
with He is engaged in his work . main methods Pontryagin's Maximum principle and
Bellman's dynamic programming .
Literature analysis
Salesman issue and his/her solution according to many scientific research , articles
and books They exist . most issue solution for various mathematician and algorithmic
approaches offer does. Dantzig , FG, Fulkerson, RW, & Johnson, S. (1954). "Solution of a
large-scale traveling-salesman
problem." This The work is about the TSP problem .
historical beginning Danzig and
his/her colleagues this issue mathematician optimization
problem as seeing
came out and him/her solution for special algorithms create necessity
They emphasized . method through the issue of multiple cities for solved . Keller, DM, &
Matheson, JE (1972). "The Traveling Salesman Problem: A Survey." This article TSP in
solution used various kind approaches , that including heuristic
and algorithmic methods
about in detail information gives . TSP solution for used solutions efficiency analysis did
Applegate, D., Bixby, R., Chvatal , V., & Cook, W. (2006). "The Traveling Salesman
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1205
Problem: A Computational Study." In this book TSP solution for modern computer
algorithms application in detail statement done .
Research methodology
Salesman The Traveling Salesman Problem is one or one how many the city visit
ordered , every one the city only one times pilgrimage so , the most short the way find The
research is methodology this issue solution for various mathematician methods and
algorithms using The problem is solved . mathematician Expression : Problem graph to the
theory is based on . Each the city as a knot , their between distances and to look at as edges
This problem is linear . programming and other mathematician methods is modeled using the
heuristic Methods : Heuristic methods issue fast to solve help These methods every always
the optimal solution even if it doesn't , it's fast and effective results For example , the Greedy
algorithm or Simulation with to add methods used . Computer Simulation : In research
computer programs and algorithms using issue solution practice Python or
other
programming TSP algorithms in languages used . Experimental Analysis : At this stage
various cities and roads for issues is created and their The effectiveness of the algorithms is
tested . in practice how results to give from the test Analysis
and Compare : In the
study various algorithms and methods This is done using which method the most effective
that determined.To practice Application : Research in the end , found solutions real world to
the conditions applies and working release or logistics in the processes how benefit to take
possibility is displayed .
Analyses and results
1. Salesman
There are
cities .
n
Each city the rest transportation route with with
connected . Cities between distances matrix
n
j
i
c
C
j
i
,1
,
),
(
=
=
given (
n
i
c
i
i
,1
,
=
=
we assume ). Salesman somehow from the city out every one in the city
only one once become initial to the city return need . To the cities to go route so choice must
route Let the length be minimal . This problem mathematician model to compose for
-
-
=
.
holda
aks
,
0
,
borilsa
shaharga
shahardan
a
,1
j
i
gar
x
j
i
(1)
such as we define this on the ground The issue
j
i
n
j
i
=
,
,...,
2
,1
,
is as follows . is
written : (1) by formula determined
j
i
x
of variables so values find must ,
n
j
x
n
i
j
i
,1
,1
1
=
=
=
,
(2)
n
i
x
n
j
j
i
,1
,1
1
=
=
=
,
(3)
j
i
n
j
i
n
nx
u
u
j
i
j
i
=
-
+
-
,
,1
,
,1
,
(4)
conditions be done and in this
( )
=
=
=
n
i
n
j
j
i
j
i
x
C
x
f
1
1
(5)
function to a minimum achieve .
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1206
(4) in condition
i
u
variables desired values acceptance they do possible , but
commonality without breaking them negative whole we consider it valuable . (2) condition
salesman every one to the city only one times entrance possible if (3) is the condition his/her
every one from the city only one times exit possible means . (4) condition
n
cities
own
inside recipient of the route closed and
1
ii
x
that provides .
(4) condition when done cities number
n
from the div small was closed route
( cycle ) available It won't . Indeed ,
k
if
(
)
n
k
<
the city binder closed route assuming that
exists if we do , this route according to (4) condition
(
)
=
=
-
+
-
n
i
n
j
j
i
k
n
nk
u
u
1
1
1
(6)
come comes out .
=
=
=
n
j
j
n
i
i
u
u
1
1
happened for (6) from
(
)
0
,
1
-
k
k
n
nk
relationship
we get , that is This is
1
-
n
n
a contradiction . said the idea Finally, condition (4) is
satisfied . satisfactory
i
u
numbers every one closed route for the existence we show . Indeed ,
if
0
=
j
i
x
if ( i.e.
i
from the city
j
to the city if not possible ) (4) condition
1
-
-
n
u
u
j
i
appearance takes , this and
i
u
of voluntary because of is executed . If any
k
At the -th step
i
from the city
j
to the city if it goes , that is
1
=
j
i
x
if ,
i
u
of voluntary because of ,
1
,
+
=
=
k
u
k
u
j
i
we can say . At that time
(
)
1
1
-
=
+
+
-
=
+
-
n
n
k
k
nx
u
u
j
i
j
i
, i.e.
condition (4) equality become is done .
The problem is simple. mathematician to the model has although him/her solution to
do one row to difficulties Of course , this issue solution for there is was all routes found ,
their lengths if found out enough . But cities number growth with routes the number is also fast
grows . Present in the period salesman about issue solution to do many methods These
methods are available . inside networks and borders method his/her own efficiency with
separated Below this the method statement we will .
Cities
n
,...,
3
,
2
,1
numbers with number them
count The ends of the roads and
count We consider the arcs of the graph as all from the ends only one once
( ) (
) ( )
{
}
1
3
2
2
1
,
,...,
,
,
,
i
i
i
i
i
i
n
=
m
to the outline Hamilton outline or is called a cycle . Therefore ,
the problem under consideration is to find the minimum length in the graph . has Hamilton
outline from finding consists of .
If
( )
j
i
с
j
i
,
-
arc length if it represents
m
cycle length
( )
( )
=
m
m
j
i
j
i
с
Z
,
(7)
will be .
m
to cycle in the sum of (7)
( )
j
i
с
C
=
matrix every line and Only one element from
each column is involved . Networks and borders method for route length
( )
m
Z
of lower border
determination important importance has .
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1207
2. Cited matrix and to bring process
concepts We enter . If
C
matrix any
i
– line
or
j
- column from the elements this of elements the most the youngest let's separate so
matrix harvest We will do it . His every one line and on the column no unless one zero there
is will be . Harvest was matrix cited matrix , it harvest to do and to bring We call this process .
in the process separable elements to the sum bringer immutable it is said and
k
h
It is said that
this on the ground
k
- to bring process order number .
Bring
process
more
detailed
statement
Let's
do
it
.
Let
( )
n
j
с
с
j
i
j
i
j
i
,...,
2
,1
,
min
,
=
=
it be . At that time
( )
i
j
i
j
i
j
i
с
с
с
,
'
-
=
(8)
will be .
( )
n
i
с
с
j
i
i
j
j
i
,...,
2
,1
,
'
min
,
=
=
*
Let it be . At that time
( )
*
-
=
j
j
i
j
i
j
i
с
с
с
,
'
"
.
(9)
As a result
( )
j
i
с
C
=
from the matrix
( )
j
i
с
C
"
=
cited matrix harvest we do . In this
bringer immutable
( )
( )
=
*
=
+
=
n
j
j
j
i
n
i
i
j
i
с
с
h
1
,
1
,
(10)
from the sum consists of will be . If
C
matrix
C
matrix with If we substitute (7) by a
similar formula
( )
m
z
the sum harvest we do . As a result
( )
( )
'
'
h
z
z
+
=
m
m
(11)
the formula we can , this on the ground
h
According to (10) is determined .
( )
0
'
m
z
happened for (11) from
( )
'
h
z
m
what harvest we do , that is
'
h
the length of the route
( cycle ) lower border be takes .
Networks and borders method main the idea We will bring . Initially all Hamilton
contours package
R
for salesman route length lower border
( )
R
j
This is determined by the
following limit (10) by formula is . Then
R
collection two to the collection is separated .
First collection so Hamilton from the contours consists of , they somehow
( )
j
i
,
bow own
inside This set
j
i
R
We denote it as . The second collection
( )
j
i
,
bow own inside did not
receive Hamilton contours package will be .
j
i
R
We denote it as . Each
j
i
R
and
j
i
R
sets for
Hamilton contours lengths lower borders
( )
j
i
R
j
and
( )
j
i
R
j
is determined . Each new lower
border
( )
R
j
smaller than not . That is
j
i
R
and
j
i
R
from the collections small lower
borderline collection is selected and this collection again two to the collection separated and
process will be returned . Next harvest was Hamilton is the only one in the collection . to the
contour has until this process continue It is delivered . as follows tree in appearance to
describe possible .
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1208
( )
( ) ( ) ( )
( )
( )
( )
( )
( )
( )
.
,
,
;
l
s
l
s
m
k
m
k
j
i
j
i
l
s
m
k
j
i
R
R
R
R
R
R
R
R
R
R
j
j
j
j
j
j
j
j
j
j
>
>
>
The method algorithm is as follows :
1.
1
=
k
that we will get
2.
C
matrix for
k
C
cited matrix We'll see .
3. Bringer immutable sum
( )
k
h
what We count . He
R
for lower border will be , that is
( )
( )
k
h
R
=
j
.
4.
j
i
R
to the collection to be included the applicants we define , that is so
( )
j
i
n
j
n
i
j
i
=
=
,
,...,
2
,1
,
,...,
2
,1
,
,
numbers we find
0
=
k
j
i
C
Let it be .
5. Separated
( )
j
i
,
for the
( )
k
j
i
i
i
k
j
i
j
j
k
C
C
j
i
,
,
min
min
,
+
=
q
numbers let's count .
6.
( )
( )
( )
0
,
,
max
,
,
=
=
k
j
i
k
j
i
k
C
j
i
l
m
q
q
by formula
( )
l
m
,
the couple we will find and
( )
l
m
,
bow keeper Hamilton outline package
me
R
what and
( )
l
m
,
what unsaved
Hamilton contours package
me
R
what we will find .
7.
me
R
collection for lower the border We define this limit .
( )
( )
( )
l
m
R
R
k
me
,
q
j
j
+
=
will be .
8.
k
C
from the matrix
-
m
line and
-
l
the column we will erase and
l
to move from
m
to we prohibit , that is
=
k
lm
C
we can say .
9. Harvest was shrunken matrix somehow in step
2
2
measurable from the matrix
consists of become left and of cities only two possible was couple in itself These
pairs
using closed route Hamilton contours harvest to do possible . If the
shortened matrix
2
2
matrix if so, refer to point 11 to point 10 without Let's go .
If the harvest made matrix cited matrix if ,
me
R
of the collection lower border this
collection harvest made
R
of the collection lower to the border equal , that is
( ) ( )
R
R
me
j
j
=
. Opposite without harvest made from the matrix cited matrix
R
R
ij
R
km
R
sl
ij
R
sl
R
km
R
1- rasm
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1209
harvest will be done and
(
)
1
+
k
h
is considered ,
( ) ( )
(
)
1
+
+
=
k
me
h
R
R
j
j
is found ,
1
+
=
k
k
it goes to point 4 .
10. Hamilton contours from taken after branching of the tree disconnected networks is
considered and their lower borders outline with length ( Record -
ec
R
) compared .
If disconnected to networks suitable sets lower borders
ec
R
smaller than if so , this
networks above rule according to continue This process is new harvest was sets lower borders
ec
R
smaller than until continue Networks
continue to hold on time new Hamilton
contours harvest to be possible . In this case
ec
R
as Hamilton contours length the most small
happened is taken .
If the length networks lower borders
ec
R
smaller than Otherwise, the issue is
resolved. The optimal route of a traveling salesman is as the most small to length has was
route is taken .
Issue
Salesman visits 7 cities (A, B, C, D, E, F, G) order Every to the city only one
times Go ahead and start . to the city return The goal is general . distance minimize .
Cities between distances matrix as follows given :
A
B
C
D
E
F
G
A
–
12
10
19
8
11
14
B
12
–
13
7
9
15
10
C
10
13
–
20
6
18
12
D
19
7
20
–
17
9
11
E
8
9
6
17
–
16
7
F
11
15
18
9
16
–
13
G
14
10
12
11
7
13
–
Step 1: Matrix to bring ( Line according to )
Each
row according to the most small element define it
row from the elements We
subtract . This is the lower to calculate the limit (H) help gives .
New matrix
A
B
C
D
E
F
G
A
–
4
2
11
0
3
6
B
5
–
6
0
2
8
3
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1210
C
4
7
–
14
0
12
6
D
12
0
13
–
10
2
4
E
2
3
0
11
–
10
1
F
2
6
9
0
7
–
4
G
7
3
5
4
0
6
–
Lower limit (H):
H = 8 + 7 + 6 + 7 + 6 + 9 + 7 = 50
Step 2: Columns to bring
Each column according to the most small the element let's divide :
New matrix
A
B
C
D
E
F
G
A
–
4
2
11
0
1
5
B
3
–
6
0
2
6
2
C
2
7
–
14
0
10
5
D
10
0
13
–
10
0
3
E
0
3
0
11
–
8
0
F
0
6
9
0
7
–
3
G
5
3
5
4
0
4
–
Updated H:
H = 50 + (2 + 0 + 0 + 0 + 0 + 2 + 1) = 50 + 5 = 55
Step 3: Results calculation
Each zero for row and column according to the most small values take let's add let's count :
line and on the column other the most small values sum
The most big result : 3 (D, B or G, E). (D, B ) we choose .
Step 4:
D → B path if selected :
Row D and column B It will be removed .
B → D is forbidden (∞ is set ).
Abbreviated matrix (5x5)
A
C
E
F
G
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1211
A
–
2
0
1
5
C
2
–
0
10
5
E
0
0
–
8
0
F
0
9
7
–
3
G
5
5
0
4
–
E → C is chosen , the matrix again This process
continue is delivered , but calculations
uncomplicated for complete the route try we see : Route : A → E → C → G → F → D →
B → A
Distance : 8 (A→E) + 6 (E→C) + 12 (C→G) + 13 (G→F) + 9 (F→D) + 7 (D→B) + 12
(B→A) = 67
H = 55 ( previous border ).
D → B path if not selected :
(D, B) = ∞ is set .
New matrix
A
B
C
D
E
F
G
A
–
4
2
11
0
1
5
B
3
–
6
0
2
6
2
C
2
7
–
14
0
10
5
D
10
∞
13
–
10
0
3
E
0
3
0
11
–
8
0
F
0
6
9
0
7
–
3
G
5
3
5
4
0
4
–
F → D is chosen , the matrix This way longer route to give possible ( for example , 70+).
Step 5: Optimal route test
Above the process continue to hold instead of , one how many possible was routes try let's
see :
INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE
ISSN: 2692-5206, Impact Factor: 12,23
American Academic publishers, volume 05, issue 04,2025
Journal:
https://www.academicpublishers.org/journals/index.php/ijai
page 1212
A → E → G → B → D → F → C → A:
Distance : 8 (A→E) + 7 (E→G) + 10 (G→B) + 7 (B→D) + 9 (D→F) + 18 (F→C) + 10
(C→A) = 69
A → E → C → G → F → D → B → A:
Distance : 67 ( above calculated ).
Networking during lower limits (H) less than 67 was route not found , so for the most good
route as 67 we will get
Answer :
The most short route :
A → E → C → G → F → D → B → A
, length
67
.
Conclusion
Salesman optimization problem (TSP) in the field the most important and wide
learned from issues This is one of them . The issue in the article is graph. theory , linear
programming and heuristic algorithms using mathematician in terms of modeled and his/her
solution for networks and borders method such as effective methods seeing was released .
Research results this shows that cities
number increase The complexity of the issue with
exponential accordingly increases , but modern computer algorithms and heuristic approaches
real world using under the circumstances satisfactory solutions find possible . The issue
practical importance logistics , transportation and business processes in optimization obvious
manifestation to be , to be various in the fields application opportunities in the future further
expansion is expected . With this together , backpack issue such as additional optimization
issues with integration TSP further complicated forms research to do for new opportunities
opens .
Literature:
1. Lin, S., & Kernighan, BW (1973). "An effective heuristic algorithm for the traveling
salesman problem." Operations Research, 21(2), 498-516.
2. Applegate, DL, Bixby, RE, Chvátal , V., & Cook, WJ (2006). "The Traveling Salesman
Problem: A Computational Study." Princeton University Press.
3. Keller, DM, & Matheson, JE (1972). "The Traveling Salesman Problem: A Survey."
Management Science, 18(10), B224-B235.
4. Wagner, G. (1972-1973). "Foundations of operations research" (Vols. 1-3). Moscow: Mir.
5. Zaichenko, Yu. P. (1979). "Operations Research." Kiev: Higher School.
