https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
731
OPTIMIZATION APPROACHES AND APPLICATION OF MATHEMATICAL
MODEL OF THE TRAVELING SALESMAN PROBLEM IN TOURISM COMPANIES
Mamatova Zilolakhon Khabibullokhonovna
Associate Professor of Fergana State University,
Doctor of Philosophy in Pedagogical Sciences (PhD)
E-mail:
ORCID ID
Turgunova Gulsanam Murodil's daughter
Student of Fergana State University
E-
mail:
Annotation:
This article analyzes the Travelling Salesman Problem (TSP) and its optimization
approaches, which play a significant role in the efficient operation of tourism companies. In
particular, factors such as planning travel routes, reducing transportation costs, and saving time
increase the relevance of this problem.The paper presents the classical formulation of the TSP
and examines its mathematical model and combinatorial optimization methods. In particular,
approaches such as dynamic programming, genetic algorithms, and approximation algorithms are
analyzed, with a focus on their applicability to the activities of tourism companies, supported by
practical examples.In addition, the article provides the results of a software simulation based on
real-world data from a tourism company and demonstrates the effectiveness of modern
algorithms in determining optimal routes.The results of the study can be beneficial in increasing
competitiveness in the tourism sector, improving logistics systems, and enhancing the quality of
service delivery.
Аннотация:
В данной статье рассматривается задача коммивояжёра (Travelling Salesman
Problem, TSP) и подходы к её оптимизации, которые играют важную роль в эффективной
деятельности туристических компаний. Особенно актуальной эта проблема становится
при планировании туристических маршрутов, снижении транспортных расходов и
экономии времени.В статье приводится классическая формулировка задачи TSP, а также
рассматриваются математическая модель и методы комбинаторной оптимизации. В
частности, анализируются такие подходы, как динамическое программирование,
генетические алгоритмы и аппроксимационные алгоритмы, а также их применение в
деятельности туристических фирм на основе практических примеров.Кроме того, в работе
представлены результаты программной симуляции, разработанной на основе реальных
данных туристической компании, что позволяет продемонстрировать эффективность
современных алгоритмов при выборе оптимальных маршрутов.Результаты исследования
могут быть полезны для повышения конкурентоспособности в туристической отрасли,
совершенствования логистических систем и улучшения качества предоставляемых услуг.
Annotatsiya:
Mazkur maqolada turizm firmalarining samarali faoliyat yuritishida muhim
ahamiyatga ega bo‘lgan kommivoyajyor masalasi (travelling salesman problem, TSP) va uning
optimallashtirish yondashuvlari tahlil qilinadi. Ayniqsa, sayyohlik yo‘nalishlarini rejalashtirish,
transport xarajatlarini kamaytirish va vaqtni tejash kabi omillar bu masalaning dolzarbligini
oshiradi.
Maqolada TSP masalasining klassik formulasi keltirilib, uning matematik modeli va kombinator
https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
732
optimallashtirish usullari asosida yechim usullari ko‘rib chiqiladi. Shu jumladan, dinamik
dasturlash, genetika algoritmi, yaqinlashtirish algoritmlari kabi yondashuvlar tahlil qilinib,
ularning turizm firmalari faoliyatiga qo‘llanish imkoniyatlari amaliy misollar orqali
yoritiladi.Shuningdek, maqolada real hayotdagi turizm firmasi ma'lumotlari asosida ishlab
chiqilgan matematik modelning dasturiy tajribasi (simulyatsiyasi) natijalari taqdim etiladi va u
orqali
optimal
yo‘nalishlar
aniqlashda
zamonaviy
algoritmlarning
samaradorligi
asoslanadi.Maqola natijalari turizm sohasida raqobatbardoshlikni oshirish, logistika tizimlarini
takomillashtirish va xizmat ko‘rsatish sifatini yuksaltirishda foydali bo‘lishi mumkin.
Keywords:
Travelling Salesman Problem (TSP), Optimization, Combinatorics, Optimal routes,
Tourism companies, Mathematical model, Travel routes, Time saving, Algorithm efficiency.
Ключевые слова:
Задача коммивояжёра (TSP), Оптимизация, Комбинаторика,
Оптимальные
маршруты,
Туристические
компании,
Математическая
модель,
Туристические маршруты, Экономия времени, Эффективность алгоритмов.
Kalit so‘zlar:
Kommivoyajyor masalasi (TSP), optimallashtirish, kombinatorika, optimal
yo‘nalishlar, turizm firmalari, matematik model, sayyohlik yo‘nalishlari, vaqtni tejash,
algoritm samaradorligi.
Introduction.
The Traveling Salesman Problem (TSP) is a popular and research-intensive
problem in combinatorial optimization. Its main goal is to find the shortest route that will take
you from one city to another and return to your starting point. This problem is used in many
areas, including transportation logistics, manufacturing process optimization, electronic circuit
design, and computer network planning. The TSP is, in fact, of great importance in finding
solutions to real-world problems and creating efficient systems. Optimization approaches to this
problem also play a significant role in the organization of tourism companies and travel services,
as the need to plan tourist routes, reduce costs and save time is increasing day by day. There are
various methods for solving it, such as: Bruteforce (Full Review), dynamic programming (Held-
Karp algorithm), Greedy algorithm (Greedy Algorithm), genetic algorithm, simulated annealing
(Simulated Annealing), linear programming and chess (Branch and Bound)
The goal of the traveling salesman problem is to find the shortest and most efficient route for a
salesman to visit a given number of cities. Each city must be visited only once, and at the end,
the salesman must return to the starting city. The main goal of the problem is to minimize the
distance traveled to the cities, thereby reducing time and cost. Solving the TSP, by optimizing
the objective, increases efficiency in real-world applications such as transportation, logistics, and
resource management. The algorithms and methods developed for solving the TSP can also be
applied to many other optimization problems.
Find a cycle that can traverse the given nine cities in the shortest time (distance, cost) by visiting
each of them only once. In this case, the number of cycles is at most ta. This problem is related
to the problem of finding a Hamilton cycle of minimum length. The "Networks and Boundaries"
method can be used to solve the traveling salesman problem. This method is carried out using a
graph with no cycles and a path, and by constructing tables.
Example.
Let us introduce the concept of table insertion. To do this, first the table rows are
inserted, that is, the smallest element of each row of the table is subtracted from the
corresponding row element. Then the same operation is performed for the table columns, and the
table columns are inserted. A table in which all rows and columns are inserted is called inserted.
The sum of the smallest elements of the table rows and columns is denoted by h and is called the
insertion coefficient of that table. We solve the problem of minimizing the total travel cost by
visiting each of the following 8 countries only once and returning to the starting point (for
example, Uzbekistan).
List of countries:
https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
733
1. Uzbekistan (UZ)
2. Saudi Arabia (SA)
3. South Korea (KR)
4. China (CN)
5. Iran (IR)
6. Russia (RU)
7. United States (US)
8. Turkey (TR)
B/T
UZ
SA
KR
CN
IR
RU
US
TR
Smallest by
row
UZ(Tashkent)
450
550
500
300
250
900
250
250
IN(Riot)
450
700
650
400
500
950
300
300
KR(Seoul)
550
700
300
600
100
1000 750
100
CN(Beijing)
500
650
300
550
500
950
700
300
IR(Tehran)
300
400
600
550
350
850
200
200
RU (Moscow)
250
500
600
500
350
800
200
200
US(Nyu-York)
900
950
1000 950
850
800
850
800
TR(Istanbul)
250
300
750
700
200
200
850
200
Table 1.
To get the rows of Table 1, we write the smallest element of the corresponding row on its right
side and subtract it from the row elements, resulting in the following table 2.
https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
734
Table 2
In order to bring the columns of the resulting table 2, the smallest element of the corresponding
column is written below the table and subtracted from the elements of the column, resulting in
the following table 3.
Table 3
191
238
191
3500
3250
Figure 1.
Table 3 is given, each row and column of which has at least one zero element. The coefficient of
occurrence h of the table under consideration is equal to the following number
1
250 300 100 300 200 200 800 200 50 100 150 600 3250
h
=
+
+
+
+
+
+
+
+
+
+
+
=
B/T
UZ
SA
KR
CN
IR
RU
US
TR
UZ
200
300
250
50
0
650
0
SA
150
400
350
100
200
650
0
KR
450
600
200
500
0
900
650
CN
200
350
0
250
200
650
400
IR
100
200
400
350
150
650
0
RU
50
300
400
300
150
600
0
US
100
150
200
150
50
0
50
TR
50
100
550
500
0
0
650
smallest element
by column
50
100
0
150
0
0
600
0
B/T
UZ
SA
KR
CN
IR
RU
US
TR
UZ
100
300
100
50
(0)
0
50
(0)
0
SA
100
400
200
100
200
50
(50)
0
KR
400
500
50
500
(50)
0
300
650
CN
150
250
(250)
0
250
200
50
400
IR
50
100
400
200
150
50
(50)
0
RU
(0)
0
200
400
150
150
(50)
0
(0)
0
US
50
50
200
(50)
0
50
(50)
0
50
TR
(4,7)
(50)
0
550
350
(50)
0
(0)
0
50
https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
735
'
1
1
250 3500
h h
= +
=
In general, the method of branches and boundaries consists of two important stages:
1) branching;
2) determination of lower bounds.
During the solution of the problem, both stages are carried out in parallel. To implement these
stages, the following steps must be performed sequentially. A) derive the initial table; B)
determine the coefficient of the derivative h; C) determine the level of the zero elements of the
derived table; D) perform branching based on these levels; E) determine the lower bounds of the
cycles that make up the branching results; F) reduce the size of the table by one; G) avoid the
formation of incomplete cycles; H) continue this process until a (2x2) table is formed; I)
determine the cycle corresponding to the last branching result; J) compare all the bounds (values);
K) if necessary, restore the table corresponding to the lowest boundary result and continue
branching.
When using this method, all calculations are carried out using a given table, and the results are
displayed on a separate graph. At the end of this process, the perfect (minimum cost) cycle is
determined.
The graph consists of interconnected circles, each of which defines a set of cycles with a certain
property. The boundary numbers written next to these circles indicate the lower limit of the costs
corresponding to the cycles belonging to this circle. The initial part of the graph looks like Figure
1. Here, the first initial circle defines the set containing all cycles and indicates that the cost of an
arbitrary cycle cannot be less than the number h. In the example above, h=3250, which means
that there is no cycle with a cost less than 3250.
The row with the highest rank containing zero
i
and column
j
are found,
( , )
i j
If there are
multiple high-order zeros, one of them is chosen at random. Here, the circle on the right
represents the set of all cycles that include a transition from city i to city j, and it
( , )
i j
is
denoted by , while the circle on the left, on the contrary, denotes the set of routes that do not
include a transition from city i to city j, and it
( , )
i j
is denoted by .
The zero element with the highest degree 250
(250)
3,4
0
c
=
, so the branching graph is as shown in
Figure 1. The coefficient of least cost for the left-hand path is
3250
h
=
The greatest degree of
zero in 250 formed by joining 3500 the number is written.
'
1
( )
h
To determine the lower limit of
the costs corresponding to the circle on the right, row 3 and column 2 of table 3 are deleted (i.e.,
the size of the table is reduced by one). It should be noted that the ordinal numbers of the cities
must be preserved, otherwise there will be confusion. After that, all incomplete cycles are
prohibited, for example
(
i
j
i i
j
® ®
®
(the sign indicates the transition from city to city) is
lost, for this
ji
c
element
is replaced by the symbol and written,
43
c
=
).
We will continue our work by creating more tables.
B/T
1
2
4
5
6
7
8
1
100
100
50
0
50
0
0
2
100
200
100
200
50
0
0
3
400
500
500
0
300
650
0
5
50
100
200
150
50
0
0
6
0
200
150
150
0
0
0
https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
736
7
50
50
0
50
0
50
0
8
0
0
350
0
0
50
0
0
0
0
0
0
0
0
Table 4.
2
h
= 3250+0=3250
'
2
h
=
2
h
+100=3350
3250
3500
3250
3350
Figure 2.
Table 5.
(300)
63
0
c
=
We can also compile Figure 2 and similar graphs at the end.
B/T
1
2
4
5
6
7
8
1
100
100
50
0
50
0
2
100
200
100
200
50
(50)
0
3
400
500
500
(0)
0
300
0
5
50
100
200
150
50
(50)
0
6
(0)
0
200
150
150
(50)
0
(0)
0
7
50
50
(100)
0
50
(0)
0
50
8
(0)
0
(50)
0
350
(50)
0
(0)
0
50
B/T
1
2
5
6
7
8
1
100
50
(0)
0
50
(0)
0
0
2
100
100
200
50
(50)
0
0
3
400
500
500
(400)
0
0
0
5
50
100
150
50
(50)
0
0
6
(0)
0
200
150
(50)
0
(0)
0
0
8
(0)
0
0
(30)
0
(0)
0
50
0
0
0
0
0
0
0
https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
737
Table 6.
3
3250
h
=
'
3
3250 400 3650
h
=
+
=
(400)
63
0
c
=
Table 7
B/T
1
2
5
7
8
1
100
50
(0)
0
(0)
0
2
100
100
(0)
0
(0)
0
5
50
100
(0)
0
(0)
0
6
(0)
0
200
150
(0)
0
8
(0)
0
(100)
0
(50)
0
(0)
0
Table 8
4
3250 50 3300
h
=
+
=
'
4
3300 100 3400
h
=
+
=
(100)
28
0
c
=
Table 9
B/T
1
5
7
8
1
(100)
0
(0)
0
(0)
0
2
100
50
(50)
0
5
50
(0)
0
(0)
0
6
(50)
0
100
(0)
0
Table 10
B/T
1
2
5
7
8
1
100
50
50
0
0
2
100
100
50
0
0
5
50
100
50
0
0
6
0
200
150
0
0
7
0
0
0
50
0
0
0
0
50
0
B/T
1
5
7
8
1
50
0
0
0
2
100
100
0
0
5
50
0
0
0
6
0
150
0
0
0
50
0
0
https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
738
5
3300 50 3350
h
=
+
=
5
3300 50 3350
h
=
+
=
(50)
51
0
c
=
Table 11
6
3350
h
=
'
6
3450
h
=
(100)
72
0
c
=
3500
3250
3250
3250
3650
3250
268
3300
3400
3350
3450
3350
Shortest path (optimal route):
1 6
3
4
7
2 8 5 1
® ® ® ® ® ® ® ®
Minimum distance:3850 unity.
Conclusion.
The traveling salesman problem is a classic mathematical problem used in
modeling and optimizing many real-world logistics and planning problems. Due to its
computational complexity, heuristic or approximate algorithms are often used in practical
B/T
1
7
8
2
100
(100)
0
0
5
(0)
0
(0)
0
0
6
(100)
0
(0)
0
0
0
0
0
B/T
1
8
5
0
6
0
https://ijmri.de/index.php/jmsi
volume 4, issue 3, 2025
739
solutions. In this work, the theoretical and practical aspects of the problem were studied and an
effective result was achieved by determining the optimal path.
References:
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.
