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 1213
IMPLEMENTATION OF OPTIMIZATION APPROACHES AND MATHEMATICAL
MODEL OF THE KOMMIVOYAJOR ISSUE IN TOURISM FIRMS
Mamatova Zilolaxon Xabibulloxonovna
Associate professor of Fergana State University,
doctor of Philosophy (PhD)in Pedagogical Sciences
E-mail:
mamatova.zilolakhon@gmail.com
ORCID ID
Abdusalomova Mubinaxon Otabek kizi
Fergana State University student
E-mail:
mubinaxonabdusalomova90@gmail.com
Annotation:
the Commivoyager issue (TSP) is one of the most common and studied issues
in mathematical optimization and computer science. The goal of the matter is to find the
shortest route by which one kom-mivoyajor goes to the designated cities, visiting each city
only once, and eventually returning to his starting point.TSP is known for its complete
combinatorial properties and high level of complexity. This issue is considered an NP-
complete issue, meaning that finding an exact solution is greatly complicated as the number
of issues increases. A variety of algorithms have been developed to find solutions through
computers, including network search algorithms, genetic algorithms, and simulated annealing
techniques.The kommivoyajor issue is used in practice in many areas, such as logistics,
transport, robotics and various resource management systems. He also optimizes issues and
increases efficiency
Annotation:
The Traveling Salesman Problem (TSP) is one of the most well-known and
studied problems in mathematical optimization and computer science. The objective of the
problem is to find the shortest possible route that allows a traveling salesman to visit a set of
specified cities, visiting each city only once, and ultimately returning to the starting point.
TSP is famous for its fully combinatorial nature and high complexity. It is classified as an
NP-complete problem, meaning that finding an exact solution becomes increasingly difficult
as the number of cities grows. Various algorithms have been developed to find solutions
using computers, including network search algorithms, genetic algorithms, and simulated
annealing methods. The Traveling Salesman Problem is applied in many practical fields, such
as logistics, transportation, robotics, and various resource management systems. It is also of
great theoretical importance as a tool used for optimization and improving efficiency.
Аннотация
: Задача коммивояжера (TSP) — одна из самых известных и изученных
задач в математической оптимизации и информатике. Цель задачи — найти
кратчайший маршрут, позволяющий коммивояжеру посетить заданные города, посетив
каждый город только один раз, и в конце концов вернуться в исходную точку. TSP
известна своими полностью комбинаторными свойствами и высокой сложностью. Эта
задача является NP-полной, что означает, что нахождение точного решения становится
всё сложнее по мере увеличения числа городов. Для нахождения решений с помощью
компьютеров разработаны различные алгоритмы, включая алгоритмы поиска в сети,
генетические алгоритмы и методы симулированного отжига. Задача коммивояжера
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 1214
применяется в различных областях, таких как логистика, транспорт, робототехника и
системы управления ресурсами. Она также имеет большое теоретическое значение как
инструмент для оптимизации и повышения эффективности.
Keywords:
Commivoyajor issue (TSP), optimization, combinatorics, NP-complete issue,
shortest path, algorithms, logistics, transport, robotics, resource management, simulated
annealing, genetic algorithms, network search algorithms, solution topping.
Keywords:
Traveling Salesman Problem (TSP), optimization, combinatorics, NP-complete
problem, shortest path, algorithms, logistics, transportation, robotics, resource management,
simulated annealing, genetic algorithms, network search algorithms, solution finding.
Ключевые слова:
Задача коммивояжера (TSP), оптимизация, комбинаторика, NP-
полная задача, кратчайший путь, алгоритмы, логистика, транспорт, робототехника,
управление ресурсами, симулированный отжиг, генетические алгоритмы, алгоритмы
поиска в сети, нахождение решения.
Introduction.
The kommivoyajor issue is one of the most important issues in the field
of combinatorial optimization, the purpose of which is to visit several cities and find the
shortest route back to the starting point with a minimum path length. This issue is used in
areas such as transport logistics, optimization of production processes and the design of
electronic circuits
Solving methods:
Bruteforce (full review),Dynamic Programming (Held-Karp
algorithm),greedy algorithm (Greedy Algorithm),genetic algorithm, simulated annealing
(Simulated Annealing), linear programming, and chess be (Branch and Bound
Purpose:
the purpose of the Kommivoyajor issue is to find the shortest and most
effective way of Kom – mivoyajor to visit the given cities. In this case, each city should be
visited only once, and in the end the kom-mivoyajyor should return to the starting city. The
main goal of the issue is to keep the distance from visiting cities to a minimum and thus
reduce time and costs. In solving tsp, by optimizing the goal, it is to increase efficiency in
real-world areas such as transport, logistics and resource management. Also, algorithms and
methods developed to solve TSP can be extended to many other optimization issues.
With only one visit to each of the n cities given, a tour for the shortest time(road, cost)
can be found in sik li. Where the number of cycles is at most ta. This issue has been linked to
the question of finding the minimum length Hamilton cycle. The "networks and
boundaries"method can be used to solve the commivoyajor issue. This method is performed
using a cycle-free and surface graph to which you are connected, as well as drawing up tables.
Sample option.
We introduce the concept of quoting a table. To do this, the table
rows are first quoted, that is, the smaller of that row is subtracted from each row element of
the table accordingly. After that, the same action is performed with respect to the table
columns and the table columns are brought. A table in which all lines and columns are listed
is called quoted. The sum of the smallest elements of the rows and columns of the table is
determined by h, which is called the quotient of the table. As an example, let's see the
following train travel schedule throughout Uzbekistan:
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 1215
We enter the marks.
1.Paris-Berlin – 1050
Paris -Rome – 1420
Paris - Madrid – 1260
Paris -Amsterdam – 510
Paris -Vienna – 1230
Paris -Prague – 1030
Paris -Zurich – 615
2.Berlin-Paris – 1050
Berlin -Rome – 1180
Berlin - Madrid – 1860
Berlin - Amsterdam – 650
Berlin - Vienna – 680
Berlin - Prague – 350
Berlin - Zurich – 820
3.Rome-Paris – 1420
Rome - Berlin – 1180
Rome - Madrid – 1360
Rome - Amsterdam – 1530
Rome - Vienna – 760
Rome - Prague – 850
Rome - Zurich – 550
4. Madrid - Paris – 1260
Madrid - Berlin – 1860
Madrid - Rome – 1360
Madrid - Amsterdam – 1480
Madrid - Vienna – 1730
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 1216
Madrid - Prague –1820
Madrid - Zurich - 1320
5. Amsterdam - Paris – 510
Amsterdam - Berlin – 650
Amsterdam - Rome – 1530
Amsterdam - Madrid – 1480
Amsterdam - Vienna – 1150
Amsterdam - Prague – 780
Amsterdam - Zurich – 760
6. Vienna - Paris – 1230
Vienna - Berlin – 680
Vienna - Rome – 760
Vienna - Madrid – 1730
Vienna - Amsterdam – 1150
Vienna - Zurich – 590
Vienna - Prague – 330
7. Prague - Paris – 1030
Prague - Berlin – 350
Prague - Rome – 920
Prague - Madrid – 1820
Prague - Amsterdam – 780
Prague - Vienna – 330
Prague - Zurich – 590
8. Zurich - Paris – 615
Zurich - Berlin – 820
Zurich - Rome – 850
Zurich - Madrid – 1320
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 1217
Zurich - Amsterdam – 760
Zurich - Vienna – 670
Zurich - Prague – 590
B/S
1
2
3
4
5
6
7
8
Satr bo‘yicha
eng kichik
1
1050
1420
1260
510
1230
1030
615
510
2
1050
1180
1860
650
680
350
820
350
3
1420
1180
1360
1530
760
850
550
550
4
1260
1860
1265
1480
1730
1820
1320
1260
5
510
650
1530
1480
1150
780
760
510
6
1230
680
760
1730
1150
330
590
330
7
1030
350
920
1820
780
330
590
330
8
615
820
850
600
760
670
590
590
Table 1
To cite the lines of Table 1, let's write down the smallest element of the line corresponding to
its right, and subtract it from the elements of the line to get to Table 2 below.
B/S
1
2
3
4
5
6
7
8
1
540
910
750
0
720
520
105
2
700
830
1510
300
330
0
470
3
870
630
810
980
210
300
0
4
0
600
5
220
470
560
60
5
0
140
1020
970
640
270
250
6
900
350
430
1400
820
0
260
7
700
20
590
1490
450
0
260
8
25
230
260
10
170
80
0
ustun bo‘yicha
eng
kichik
element
0
20
5
10
0
0
0
0
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 1218
Table 2
In order to cite the columns of the resulting Table 2, the smallest element of the
corresponding column is written under the table and subtracted from the column elements,
resulting in the following table 3.
Table 3
4465
238
4465
1-rasm.
Table 3 is listed, with at least one zero element in each row and column. The quotient of the
table under consideration H is equal to the following number
1
510 350 550 1260 510 330 330 590 0 20 5 10 0 0 0 0 4465
h
=
+
+
+
+
+
+
+
+ +
+ +
+ + + + =
'
1
1
740 5205
h h
= +
=
In general, the method of networks and boundaries consists of two important stages:
1) branching;
2) determination of lower boundaries.
During the solution of the issue, both stages are carried out in parallel. To carry out
these stages, it is necessary to carry out the following work in a row. A) to cite the starting
Table; B) to determine the quotient h; C) to determine the degree of zero elements of the
cited Table; D) to carry out the branching based on these levels; E) to determine the lower
B/S
1
2
3
4
5
6
7
8
1
520
905
740
(275)
0
720
520
105
2
700
825
1500
300
330
(300)
0
470
3
870
610
800
980
210
300
(270)
0
4
(0)
0
680
(255)
0
220
470
560
60
5
(120)
0
120
1015
960
640
270
250
6
900
330
425
1390
820
(260)
0
260
7
700
0
585
1480
450
(80)
0
260
8
25
210
255
(740)
0
170
80
(0)
0
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 1219
limits of the cycles that make up the branching results; F) to reduce the size of the table by
one; G) to avoid continue networking.
During the use of this method, all calculations are carried out using a given table, the
results of which are shown in a separately compiled graph. At the end of this process, a
perfect(minimum cost) cycle is determined.
A graph consists of a set of interconnected circles, each of which determines a set of
cycles with a certain property. The limit-numbers written next to these circles denote the
lower limit of the costs corresponding to the cycles belonging to that circle. The initial part of
the graph will be in the form of Figure 1. In this, the first initial circle defines a set containing
all the cycles and states that the cost per arbitrary cycle will not be less than the number H. In
the example seen above, h=4465, which means that there is no cycle with a cost less than
4465.
The rows and columns in which the Zero is located, the level of which is the largest, are
found and branched on. Location, when there are several large-level zeros, an optional one is
selected. In this case, the right-hand circle denotes and is marked by the set of all cycles that
involve the transition from city I to city j, while the left-hand circle, on the contrary, denotes
and is marked by the set of routes that do not involve the transition from city I to city J.
The degree is the zero element of which the most kata is 740, which means that the
branching graph is in Figure 1.The minimum cost factor for the chapdoirachayoni is written
to h=4465, the number 5205, which is formed by adding the largest level of zero 740. To
determine the lower limit of costs corresponding to the right-hand Circle, Line 8 and Column
4 of Table 3 are discarded(deleted) (which means that the size of the table is reduced by one).
In this case, it should be noted that the ordinal numbers of the cities will definitely
remain(written), while other, will turn out to be. After that,the formation of all incomplete
cycles is prohibited, the issue is lost) denotes the transition from belgii-city to City-City, for
which the element is replaced and written on the sign,
48
c
=
).
We will continue our work by making tables again.
B/S
1
2
3
5
6
7
8
1
520
905
(325)
0
720
520
105
0
2
700
825
300
330
(300)
0
470
0
3
870
610
980
210
300
(315)
0
0
4
(315)
0
680
(425)
0
220
470
560
0
5
(120)
0
120
1015
640
270
250
0
6
900
330
425
820
(260)
0
260
0
7
700
(340)
0
585
450
(210)
0
260
0
0
0
0
0
0
0
0
Table 4
2
h
= 4465+0=4465
'
2
h
=
2
h
+425=4885
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 1220
(425)
43
0
c
=
34
c
=
Table 5
3
4465
h
=
'
3
4465 700 5165
h
=
+
=
(700)
51
0
c
=
Table 7
4
4465 210 300 4975
h
=
+
+
=
'
4
5650
h
=
(675)
18
0
c
=
B/S
1
2
5
6
7
8
1
520
(405)
0
720
520
(145)
0
0
2
700
300
330
(300)
0
365
0
3
870
610
980
210
300
0
5
(730)
0
120
640
270
145
0
6
900
330
820
(260)
0
155
0
7
700
(120)
0
450
(210)
0
155
0
0
0
0
0
0
0
B/S
2
5
6
7
8
1
520
720
520
(675)
0
0
2
(150)
0
330
(0)
0
365
0
3
400
470
(90)
0
90
0
6
330
520
(155)
0
155
0
7
(330)
0
150
(0)
0
155
0
0
0
0
0
0
B/S
2
5
6
7
2
(150)
0
330
(0)
0
0
3
400
(90)
0
90
0
6
330
520
(330)
0
0
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 1221
Table 8
5
4975
h
=
'
5
4975 330 5305
h
=
+
=
(330)
67
0
c
=
Table 9.
6
4975
h
=
'
6
4975 730 5705
h
=
+
=
(730)
36
0
c
=
7
(330)
0
150
(0)
0
0
0
0
0
0
B/S
2
5
6
2
(480)
0
330
0
3
400
(730)
0
0
7
(550)
0
150
0
0
0
0
B/S
2
5
2
0
7
0
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 1222
5705
4975
Shortest route (optimal route):
5
2 1 6 8 3
4 1 5
® ® ® ® ® ® ® ®
Minimum distance: 4975 units.
Conclusion.
The commivoyager problem is a classical mathematical problem used to model
and optimize many real-life problems. Due to the computational complexity of finding an
Optimal solution, approximation algorithms or heuristic approaches are used in most cases.
Literature used:
1. Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial Optimization: Algorithms
and Complexity. Dover Publications.
2. Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (2006). The Traveling Salesman
Problem: A Computational Study. Princeton University Press.
3. Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1985). The
Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley.
4. Gutin, G., & Punnen, A. P. (2002). The Traveling Salesman Problem and Its Variations.
Springer.
5. Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP
Applications. Springer.
