SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
161
TURIZM FIRMALARIDA KOMMIVOYAJYOR MASALASINING
OPTIMALLASHTIRISH YONDASHUVLARI VA MATEMATIK
MODELINING TADBIQI
Ro‘zaliyev Sherzodjon Avazjonovich
Farg‘ona davlat universiteti axborot texnologiyalari kafedrasi mudiri,
pedagogika fanlari bo‘yicha falsafa doktori (PhD)
E-mail: sherzodjonruzaliyev@gmail.com
ORCID ID 0000-0002-0019-8446
Nozimov Hayotillo Baxtiyorjon o’g’li
Farg‘ona davlat universiteti talabasi
E-mail:tdaxshat@gmail.com
Jo‘rayev Ahliddin Ravshanjon o‘g‘li
Farg‘ona Davlat Universiteti talabasi
E-mail: tdaxshat@gmail.com
https://doi.org/10.5281/zenodo.15305087
Annotatsiya:
Kommivoyajyor masalasi (TSP) — bu matematik
optimallashtirish va kompyuter fanlarida eng keng tarqalgan va o'rganilgan
masalalardan biridir. Masalaning maqsadi bir kom-mivoyajyorning belgilangan
shaharlarga borib, har bir shaharga faqat bir marta tashrif buyurib, oxir-oqibat
o'zining boshlang'ich nuqtasiga qaytib keladigan eng qisqa yo'lni topishdir.TSP,
o'zining to'liq kombinatorik xususiyatlari va yuqori darajadagi murakkabligi
bilan mashhur. Bu masala NP-to'liq masala hisoblanadi, ya'ni uning aniq
yechimini topish, masalalar soni ortgan sari juda murakkablashadi.
Kompyuterlar orqali yechim topish uchun turli xil algoritmlar ishlab chiqilgan,
jumladan, tarmoqni qidirish algoritmlari, genetik algoritmlar va simulyatsiya
qilingan annealing metodlari.Kommivoyajyor masalasi amaliyotda ko'plab
sohalarda, masalan, logistika, transport, robototexnika va har xil resurslarni
boshqarish tizimlarida qo'llaniladi. U shuningdek, masalalarni optimallashtirish
va samaradorlikni oshirish uchun qo'llaniladigan nazariy vosita sifatida juda
muhim ahamiyatga ega.
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
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
162
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-полной, что означает, что нахождение точного
решения становится всё сложнее по мере увеличения числа городов. Для
нахождения решений с помощью компьютеров разработаны различные
алгоритмы, включая алгоритмы поиска в сети, генетические алгоритмы и
методы симулированного отжига. Задача коммивояжера применяется в
различных областях, таких как логистика, транспорт, робототехника и
системы управления ресурсами. Она также имеет большое теоретическое
значение как инструмент для оптимизации и повышения эффективности.
Kalit so‘zlar:
Kommivoyajyor masalasi (TSP), optimallashtirish,
kombinatorika, NP-to'liq masala, eng qisqa yo'l, algoritmlar, logistika, transport,
robototexnika, resurslarni boshqarish, simulyatsiya qilingan annealing, genetik
algoritmlar, tarmoqni qidirish algoritmlari, yechim toppish.
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-полная задача, кратчайший путь, алгоритмы,
логистика,
транспорт,
робототехника,
управление
ресурсами,
симулированный отжиг, генетические алгоритмы, алгоритмы поиска в
сети, нахождение решения.
Kommivoyajyor masalasi – kombinatorik optimizatsiya sohasidagi muhim
masalalardan biri bo‘lib, uning maqsadi bir nechta shaharlarga tashrif buyurib,
minimal yo‘l uzunligi bilan boshlang‘ich nuqtaga qaytadigan eng qisqa
yo‘nalishni topishdir. Ushbu masala transport logistikasi, ishlab chiqarish
jarayonlarini optimallashtirish va elektron sxemalar loyihalash kabi sohalarda
qo‘llaniladi.
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
163
Yechish usullari:
Bruteforce (To‘liq ko‘rib chiqish),dinamik dasturlash
(Held-Karp algoritmi),ochko‘z algoritm (Greedy Algorithm),genetik algoritm,
simulyatsiyalangan tavlanish (Simulated Annealing), chiziqli dasturlash va
shaxmat bo‘lishi (Branch and Bound)
Maqsad:
Kommivoyajyor masalasining maqsadi – berilgan shaharlarga
tashrif buyurish uchun kom-mivoyajyorning eng qisqa va eng samarali yo‘lini
topishdir. Bunda, har bir shahar faqat bir marta ziyorat qilinishi kerak va oxirida
kom-mivoyajyor boshlang‘ich shaharga qaytib kelishi lozim. Masalaning asosiy
maqsadi, shaharlarga tashrif buyurishdagi masofani minimal qilish va shu orqali
vaqt
va
xarajatlarni
kamaytirishdir.
TSPni
yechishda,
maqsadni
optimallashtirish orqali, real dunyoda transport, logistika va resurslarni
boshqarish kabi sohalarda samaradorlikni oshirishdir. Shuningdek, TSPni
yechish uchun ishlab chiqilgan algoritmlar va metodlar boshqa ko'plab
optimallashtirish masalalariga ham tatbiq etilishi mumkin.
Berilgan n ta shaharni har biriga faqat bir marta tashrif etish bilan eng qisqa
vaqt(yo‘l, xarajat) davomida aylanib chiqish sik li topilsin. Bunda sikllar soni
ko‘pi bilan
(
1)!
n
ta bo‘ladi. Bu masala minimal uzunlikdagi Gamilton siklini
topish masalasi bilan bog‘langan. Kommivoyajyor masalasini yechishda
"Tarmoqlar va chegaralar"usulini qo‘llash mumkin. Bu usul siklsiz va sirtmoq siz
bog‘langan graf, hamda jadvallar tuzish yordamida olib boriladi.
Namunaviy variant.
Jadvalni keltirish tushunchasini kiritamiz. Buning
uchun, avval jadval satrlari keltiriladi, ya’ni jadvalning har bir satr
elementlaridan shu satrning kichigi mos ravishda ayirib tashlanadi. Shundan
so‘ng jadval ustunlariga nisbatan ham xuddi shu amal bajarilib, jadval ustunlari
keltiriladi. Barcha satrlari va ustunlari keltirilgan jadval keltirilgan deb ataladi.
Jadval satr va ustunlari eng kichik elementlarining yig‘indisi h bilan belgilanib, u
jadvalning keltirish koeffitsienti deyiladi. Misol sifatida quyidagi Yevropa bo‘ylab
poyezd sayohat jadvalini ko‘raylik:
Belgilashlarni kiritib olamiz.
1.London-Parij– 74 000
London-Madrid – 4 000
London-Rim – 50 000
London-Moskva – 500 000
London-Berlin – 50 000
London-Barselona – 20 000
London-Istambul – 112 000
2.Parij- London–74 000
Parij -Madrid – 15 000
Parij -Rim – 12 000
Parij -Moskva – 65 000
Parij -Berlin – 50 000
Parij -Barselona – 60 000
Parij -Istambul – 70 000
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
164
3.Madrid-London – 4 000
Madrid -Parij – 15 000
Madrid -Rim – 67 000
Madrid -Moskva – 75 000
Madrid -Berlin – 100 000
Madrid -Barselona – 22 000
Madrid -Istambul – 55 000
4.Rim-London – 50 000
Rim -Parij – 12 000
Rim -Madrid – 67 000
Rim -Moskva – 80 000
Rim -Berlin – 21 000
Rim -Barselona –8 000
Rim -Istambul – 80 000
5.Moskva-London – 100 000
Moskva -Parij – 65 000
Moskva -Madrid – 75 000
Moskva - Rim – 80 000
Moskva -Berlin – 45 000
Moskva -Barselona– 70 000
Moskva -Istambul– 30 000
6.Berlin -London – 50 000
Berlin -Parij– 50 000
Berlin -Madrid– 100 000
Berlin -Rim – 21 000
Berlin -Moskva – 45 000
Berlin -Barselona – 10 000
Berlin -Istambul – 95 000
7.Barselona -London – 20 000
Barselona -Parij – 60 000
Barselona -Madrid – 22 000
Barselona -Rim – 8 000
Barselona -Moskva – 70 000
Barselona -Berlin – 10 000
Barselona -Istambul – 48 000
8. Istambul -London– 112 000
Istambul -Parij – 70 000
Istambul -Madrid – 55 000
Istambul -Rim – 80 000
Istambul -Moskva – 30 000
Istambul -Berlin – 95 000
Istambul -Barselona – 48 000
B/S
1
2
3
4
5
6
7
8
Satr
bo‘yicha
eng kichik
1
74
4
50
100
50
20
112
4
2
74
15
12
65
50
60
70 12
3
4
15
67
75
100
22
55
4
4
50
12
67
80
21
8
80
8
5
100
65
75
80
45
70
30
30
6
50
50
100
21
45
10
95
10
7
20
60
22
8
70
10
48
8
8
112
70
55
80
30
95
48
30
1-jadval.
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
165
1-jadval satrlarini keltirish uchun uning o‘ng tarafiga mos satrning eng
kichik elementini yozib chiqamiz va satr elementlaridan uni ayirib quyidagi 2-
jadvalga ega bo‘lamiz.
2-jadval
Hosil bo‘lgan 2-jadvalning ustunlarini keltirish maqsadida jadval ostiga mos
ustunning eng kichik elementi yoziladi va ustun elementlaridan ayirib chiqiladi,
natijada quyidagi 3-jadval hosil bo‘ladi.
bo‘lamiz
B/S
1
2
3
4
5
6
7
8
1
70
0
46
96
46
16
108
2
62
3
0
53
38
48
58
3
0
11
63
71
96
18
51
4
42
4
59
72
13
0
72
5
70
35
45
50
15
40
0
6
40
40
90
11
35
0
85
7
12
52
14
0
62
2
40
8
82
40
25
50
0
65
18
ustun
bo‘yicha eng
kichik
element
0
4
0
0
0
2
0
0
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
166
3-jadval
112
165
112
1-rasm.
3-jadval keltirilgan bo‘lib, uning har bir satr va ustunida kamida bittadan
nol element bor. Ko‘rilayotgan jadvalning keltirish koeffitsienti h quyidagi songa
teng
4
12
4
8
30
10
8
30
4
2
112
h
'
1
1
53 165
h
h
Umuman, tarmoqlar va chegaralar usuli ikkita muhim bosqich dan iboratdir:
1) tarmoqlash;
2) quyi chegaralarni aniqlash.
Masalani yechish davomida ikkala bosqich parallel ravishda olib boriladi.
Bu bosqichlarni amalga oshirish uchun, quyidagi ishlarni ketma-ket bajarish
kerak. A) boshlang‘ich jadvalni keltirish; B) keltirish koeffitsenti h ni aniqlash; C)
keltirilgan jadvalning nol elementlari darajasini aniqlash; D) bu darajalar
asosida tarmoqlashni amalga oshirish; E) tarmoqlanish natijalarini tashkil
etuvchi sikllarning quyi chegaralarini aniqlash; F) jadval o‘lchamini bittaga
kamaytirish; G) to‘la bo‘lmagan sikllar hosil bo‘lib qolishdan saqlanish; H) bu
jarayonni (2x2) jadval hosil bo‘lgunga qadar davom ettirish; I) oxirgi tarmoq
B/S
1
2
3
4
5
6
7
8
1
66
0
(19)
46
96
44
16
108
2
62
3
0
(3)
53
36
48
58
3
0
(19)
7
63
71
94
18
51
4
42
0
(7)
59
72
11
0
(0)
72
5
70
31
45
50
12
40
0
(52)
6
40
36
90
11
35
(11)
85
7
12
48
14
0
(0)
62
0
(11)
40
8
82
36
25
50
0
(53)
63
18
Barcha
sikllar
(8,5)
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
167
natijasiga mos siklni aniqlash; J) barcha chegara (ba holarni) solishtirish; K)
zarurat bo‘lsa, eng kam chegaraviy natijaga mos jadval tiklanib tarmoqlashni
davom ettirish.
Bu usulni qo‘llash davomida, barcha hisob-kitoblar berilgan jadval
yordamida olib borilib, uning natijalari alohida tuzilgan grafda ko‘rsatib boriladi.
Bu jarayon oxirida mukammal(eng kam xarajatli) sikl aniqlanadi.
Graf o‘zaro birlashtirilgan doirachalardan iborat bo‘lib, ular ning har biri
ma’lum bir xossali sikllar to‘plamini aniqlaydi. Bu doirachalar yoniga yozilgan
chegara-sonlar esa, shu doiraga tegishli bo‘lgan sikllarga mos xarajatlarning quyi
chegarasini bildiradi. Grafning boshlang‘ich qismi 1-rasm ko‘rinishida bo‘ladi.
Bunda birinchi boshlang‘ich doiracha barcha sikllarni o‘z ichiga olgan to‘plamni
aniqlab, ixtiyoriy sikl bo‘yicha ketadigan xarajat h sonidan kichik bo‘lmasligini
bildiradi. Yuqorida ko‘rilgan misolda h=112 edi, demak, xarajati 112 dan kichik
bo‘lgan sikl yo‘q ekan.
Darajasi eng katta bo‘lgan nol joylashgan satr
i
va ustun
j
lar topilib,
( , )
i j
bo‘yicha tarmoqlanadi. Mabodo, katta darajali nollar bir nechta bo‘lsa, ularning
ixtiyoriy bittasi tanlab olinadi. Bunda, o‘ng tarafdagi doiracha i shahardan j
shaharga o‘tishni o‘z ichiga olgan barcha sikllarning to‘plamini bildiradi va u
( , )
i j
bilan belgilanadi, chap tarafdagi doiracha esa, aksincha, i shahardan j
shaharga o‘tishni o‘z ichiga olmagan marshrutlarning to‘plamini bildiradi va u
( , )
i j
bilan belgilanadi.
Darajasi eng kata 53 bo‘lgan nol element
(53)
85
0
c
dir, demak, tarmoqlanish
grafi1-rasmko‘rinishidabo‘ladi.Chapdoirachayoniga eng kam xarajat keltirish
koeffitsienti
112
h
ga nolning eng katta darajasi 53 qo‘shilib hosil bo‘lgan 165
soni yoziladi.
'
1
( )
h
O‘ng tarafdagi doirachaga mos keluvchi xarajatlarning quyi
chegarasini
aniqlash
uchun
3-jadvalning
8-satri
va
5-ustuni
tashlab(o‘chirib)yuboriladi(demak, jadvalning o‘lchami bittaga kamayadi).
Bunda,shuni alohida ta’kidlash lozimki, shaharlarning tartib raqamlari albatta
Saqlanib (yozilib) qolishishart, akshol dachal kashliklar kelib chiqadi. Shundan
so‘ng,barcha to‘la bo‘lmagan sikllar hosil bo‘lishi taqiqlanadi,masalani
(
i
j
i i
j
belgii-shahardanj-shaharga o‘tishni bildiradi) yo‘qotiladi, buning
uchun
ji
c
element
belgisiga almashtirilib yozib qo‘yiladi,
58
c
).
Yana jadvallarni tuzib ishimizni davom ettiramiz.
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
168
B/S
1
2
3
4
6
7
8
1
66
0
46
44
16
108
0
2
62
3
0
36
48
58
0
3
0
7
63
94
18
51
0
4
42
0
59
11
0
72
0
5
70
31
45
50
12
40
12
6
40
36
90
11
0
85
0
7
12
48
14
0
0
40
0
0
0
0
0
0
0
40
4-jadval.
2
h
= 112+52=164
'
2
h
=
2
h
+19=183
B/S
1
2
3
4
6
7
8
1
66
0
(19)
46
44
16
68
2
62
3
0
(3)
36
48
18
3
0
(19)
7
63
94
18
11
4
42
0
(18)
59
11
0
(0)
32
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
169
5
58
19
33
38
0
28
6
40
36
90
11
0
(11)
45
7
12
48
14
0
(0)
0
0
5-jadval.
(19)
31
0
c
13
c
2-rasmni va shunga o‘xshagan grafiklarni oxirida jamlab tuzib qo‘ysak ham
bo‘ladi.
6-jadval.
3
183
h
'
3
202
h
(19)
42
0
c
7-jadval.
4
183
h
'
4
222
h
(39)
67
0
c
B/S
2
3
4
6
7
8
1
66
46
44
16
68
16
2
3
0
(3)
36
48
18
0
4
0
(19)
59
11
0
(0)
32
0
5
19
33
38
0
(19)
28
0
6
36
90
11
0
(11)
45
0
7
48
14
0
(0)
0
0
(18)
0
0
3
0
0
0
0
B/S
3
4
6
7
8
1
30
28
0
(28)
52
0
2
0
(29)
36
48
18
0
5
30
38
0
(28)
28
0
6
87
11
0
(39)
45
0
7
11
0
(11)
0
(0)
0
(18)
0
0
0
0
0
0
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
170
8-jadval.
5
211
h
'
5
285
h
(74)
56
0
c
9-jadval.
6
231
h
'
6
260
h
(29)
78
0
c
165
112
183
164
203
183
B/S
3
4
6
8
1
30
28
52
28
2
0
(29)
36
18
0
5
30
38
0
(74)
0
7
11
0
(30)
0
(18)
0
0
0
0
0
B/S
3
4
8
1
2
24
2
2
0
(29)
18
0
7
11
0
(29)
0
0
0
18
B/S
3
4
1
0
2
0
B/S
SCIENCE AND INNOVATION IN THE
EDUCATION SYSTEM
International scientific-online conference
171
222
183
285
211
360
231
Eng qisqa yo‘l (optimal marshrut):
Xulosa
. Kommivoyajyor masalasi real hayotdagi ko‘plab muammolarni
modellashtirish va optimallashtirish uchun ishlatiladigan klassik matematik
masaladir. Optimal yechimni topishning hisoblash murakkabligi tufayli,
ko‘pchilik hollarda taxminiy algoritmlar yoki heuristik yondashuvlar qo‘llaniladi.
Foydalanilgan adabiyotlar:
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.
