Gezgin savdogar masalasi optimallashtirish adabiyotining eng mashhur va eng murakkab masalalaridan biridir. Klassik ko‘rinishda masala sodda tuyuladi: bir savdogar ma’lum shaharlarning har birini aynan bir marta aylanadi, so‘ng boshlang‘ich nuqtaga qaytadi va umumiy masofani eng kichik qiladi. Ammo shaharlar soni oshgani sari mumkin bo‘lgan marshrutlar soni juda tez ko‘payadi. Shu sababli TSP NP-hard masala sifatida qabul qilinadi.

Ish markazidagi masala esa TSP ning yanada qiyinroq ko‘rinishi bo‘lgan Asymmetric Traveling Salesman Problem, ya’ni ATSPdir. Klassik simmetrik TSP da ikki shahar orasidagi masofa har ikki yo‘nalishda bir xil bo‘ladi. ATSP da esa yo‘nalish muhim. A dan B ga borish xarajati bilan B dan A ga borish xarajati farqli bo‘lishi mumkin. Bu farq real hayotda juda keng tarqalgan. Bir tomonlama yo‘llar, tirbandlik, shamol yo‘nalishi, vaqt oynalari, teleskoplarning osmondagi nishonlarga murojaat tartibi, DNK bo‘laklarining yo‘nalishga bog‘liq qoplanishi yoki ishlab chiqarish liniyalaridagi amal ketma-ketligi asimmetrik xarajatlar tug‘dirishi mumkin.

Shu sababli ATSP faqat matematik o‘yin emas. U logistika, astronomiya, genomika, sanoat jarayonlari va katta hajmli tarmoq rejalashtirishiga ta’sir qiladigan asosiy optimallashtirish masalasidir. Biroq ATSP ning yo‘nalishga bog‘liqligi yechim fazosini yanada murakkablashtiradi. Simmetrik TSP uchun ishlab chiqilgan ayrim usullar ATSP ga to‘g‘ridan-to‘g‘ri qo‘llanmaydi yoki jiddiy moslashtirish talab qiladi.

Ishning asosiy savoli shunday: katta hajmli ATSP misollarini standart kompyuterlarda ham tez, ham aniq yechish mumkinmi? Bu yerda “aniq” so‘zi muhim. Ko‘plab sezgir usullar tez yechim beradi, ammo bu yechim global optimum ekanini kafolatlamaydi. Aksincha, exact MIP solverlar nazariy jihatdan optimumni topa oladi, biroq katta ATSP misollarida ish vaqti hamda xotira sarfi tez o‘sadi. Ish ana shu ikki chekka orasida ko‘prik qurishni maqsad qiladi: sezgir tezlik va exact solver aniqligini bitta arxitekturada birlashtirish.

Mualliflar taklif qilgan usul GTA deb ataladi. GTA Gurobi Tabu Algorithm iborasining qisqartmasidir. Nomidan ko‘rinib turibdiki, usul keng qo‘llaniladigan tijoriy MIP solver Gurobi ni Tabu Search sezgirligi bilan birlashtiradi. Biroq ish bu qismlarni shunchaki yonma-yon qo‘ymaydi; katta ATSP uchun ularni strategik ravishda qayta tashkil etadi.

GTA ning markazida uchlik tuzilma bor:

• Tabu Search warm start: Juda qisqa vaqt ichida yaxshi boshlang‘ich tur hosil qiladi. Ishda bu boshlang‘ich yechimlar odatda 1%–5% optimality gap oralig‘ida, ehtiyotkor hisobda esa 10% dan past bo‘lishi aytiladi.
• Gurobi MIP yechimi: Boshlang‘ich turni ishlatib, exact qidiruv bajaradi va 0% optimality gap maqsadiga intiladi.
• MTZsiz subtour elimination: Miller–Tucker–Zemlin cheklovlari o‘rniga lazy constraint callback orqali kichik aylanishlar dinamik tarzda yo‘q qilinadi.

Bu uch komponentning birga ishlashi muhim. Tabu Search yolg‘iz o‘zi tez, ammo taxminiy natija beradi. Gurobi yolg‘iz o‘zi katta ATSP da sovuq boshlang‘ich bilan juda uzoq davom etishi mumkin. MTZ cheklovlari esa klassik TSP formulatsiyalarida subtourlarni to‘sish uchun ishlatilsa-da, katta masalalarda model o‘lchamini va yechim yukini oshirishi mumkin. GTA yaxshi boshlang‘ich tur berib Gurobi ning qidiruv daraxtini toraytiradi; MTZ cheklovlarini olib tashlab modelni yengillashtiradi; lazy constraints yordamida esa faqat kerak bo‘lganda subtour kesimlari qo‘shadi.

ATSP ning standart MIP mantig‘ini tushuntirish uchun asosiy formulatsiya quyidagicha tasavvur qilinadi. Bu formula ishda qo‘llangan MTZsiz MIP yondashuvini tushunishga yordam beradigan fon izohidir:

\[ \min \sum_{i=1}^{N}\sum_{j=1, j\neq i}^{N} c_{ij}x_{ij} \]

Bu yerda N tugunlar soni. c_ij i tugundan j tugunga borish xarajatidir. ATSP da odatda c_ij ≠ c_ji bo‘lishi mumkin. x_ij i dan j ga o‘tilgan-o‘tilmaganini ko‘rsatuvchi ikkilamchi o‘zgaruvchidir. Agar marshrut i dan j ga o‘tsa [ x_{ij}=1 ], o‘tmasa [ x_{ij}=0 ] bo‘ladi.

Har bir tugundan aynan bir chiqishni ta’minlovchi asosiy daraja cheklovi:

\[ \sum_{j=1, j\neq i}^{N} x_{ij} = 1 \quad \forall i \]

Har bir tugunga aynan bir kirishni ta’minlovchi cheklov:

\[ \sum_{i=1, i\neq j}^{N} x_{ij} = 1 \quad \forall j \]

Bu ikki cheklov har bir tugunning bir marta chiqish va bir marta kirish olishini kafolatlaydi. Ammo ular yolg‘iz o‘zlari yetarli emas. Chunki yechim barcha tugunlarni qamrab olgan bitta tur o‘rniga bir nechta kichik aylanishlarga, ya’ni subtourlarga bo‘linib ketishi mumkin. Masalan, 1-2-3-1 va 4-5-6-4 kabi ikkita alohida yopiq marshrut hosil bo‘lishi mumkin. TSP/ATSP ning asl qiyinligi barcha tugunlarni bitta Hamilton turida birlashtirishdir.

Klassik MTZ yondashuvi qo‘shimcha tartiblash o‘zgaruvchilari bilan bu subtourlarni to‘sishga urinadi. Ammo katta hajmda bu qo‘shimcha o‘zgaruvchilar va cheklovlar yechimni og‘irlashtiradi. Ish taklif qilgan yondashuvda MTZ cheklovlari o‘rniga lazy constraint callback ishlatiladi. Bu mantiqda solver avval daraja cheklovlari bilan yechim hosil qiladi; agar yechim subtourlardan iborat bo‘lsa, faqat o‘sha subtourlarni kesadigan yangi cheklovlar keyinroq qo‘shiladi. Umumiy subtour elimination mantiqi quyidagi fon formula bilan ifodalanadi:

\[ \sum_{i\in S}\sum_{j\in S, j\neq i} x_{ij} \leq |S|-1 \quad \forall S \subset \{1,\ldots,N\},\; 2\leq |S| < N \]

Bu yerda S — barcha tugunlarning faqat bir qism to‘plami. Bu cheklov S ichidagi tugunlarning o‘z ichida yopiq kichik tur hosil qilishini to‘sadi. Ammo barcha mumkin bo‘lgan S to‘plamlari uchun bunday cheklovlarni oldindan qo‘shish amaliy emas. Lazy constraint yondashuvi aynan shuning uchun ishlatiladi: faqat solver topgan yechimda haqiqatan paydo bo‘lgan subtourlar kesiladi.

Ish GTA ni kuchli qiladigan nuqta aynan shu ekanini ta’kidlaydi. MIP solver juda katta yechim fazosida noldan yurib boshlamaydi. Tabu Search avval yaxshi marshrut beradi. Bu marshrut Gurobi uchun incumbent, ya’ni boshlang‘ich yechim bo‘ladi. Agar incumbent optimumga yaqin bo‘lsa, branch-and-cut qidiruvi torroq hududda ishlashi mumkin; yomon shoxlar erta kesiladi; cut generation samaraliroq bo‘ladi. Ish warm start sifati shu sababli juda muhimligini urg‘ulaydi.

Mualliflar kuchsiz warm start yechimlari foydadan ko‘ra zarar yetkazishi mumkinligini alohida ta’kidlaydi. Ishda 10%–15% dan katta gap ga ega boshlang‘ichlar MIP solver ni chalg‘itishi, hatto sovuq boshlang‘ichdan ham yomonroq natija berishi mumkinligi aytiladi. Buning sababi — yomon incumbent qidiruv daraxtini noto‘g‘ri yo‘naltirishi, yaxshiroq yechimlarning erta topilishiga to‘sqinlik qilishi va solver ning ichki sezgilarini bosib qo‘yishidir. Shu sababli GTA uchun shunchaki “bir boshlang‘ich yechim” emas, tuzilmaviy jihatdan mos va yetarlicha yaqin boshlang‘ich tur kerak bo‘ladi.

Ishda Tabu Search warm start odatda soniyalar ichida 1%–9% oralig‘ida gap hosil qilishi, ko‘p hollarda 5% dan pastda qolishi aytiladi. Xuddi shu matnda genetik algoritm va simulated annealing kabi boshqa sezgir usullar katta ATSP misollarida 30 daqiqani oshgan vaqt o‘tsa ham 50% dan yuqori gap berishi mumkinligi qayd etiladi. Shu sababli mualliflar GTA arxitekturasida Tabu Search tanlovi tasodifiy emas, warm start sifati va tezligi muvozanatidan kelib chiqqanini aytadi.

Ishning ishlash bo‘yicha da’volari juda kuchli. 1-jadvalda GTA ning 5.000 tugunli ATSP uchun N^2.01–N^2.03 oralig‘ida empirik murakkablik ko‘rsatgani va 350–850 soniya ichida 0% optimality gap ga erishgani qayd etiladi. Bunga qarshi warm start siz Gurobi lazy-constraint yondashuvi uchun N^2.1–N^2.2 va 3.750–6.750 soniya oralig‘i beriladi. Bu taqqoslash GTA faqat Gurobi dan iborat emasligini; warm start va model dizayni ish vaqtiga sezilarli ta’sir qilishini ko‘rsatish uchun ishlatiladi.

Biroq bu yerda ilmiy farqni ehtiyotkor qilish kerak. Ishda berilgan N^2.01–N^2.03 xulqi formal algoritmik murakkablik isboti emas. Mualliflar ham buni ochiq aytadi: yaqin-kvadratik xulq turli tugun sonlarida olingan ish vaqti ma’lumotlarining log-log regressiyasi orqali modellangan. NP-hard ATSP uchun bunday ampirik masshtablash hisobotlari adabiyotda odatiy bo‘lsa-da, ular matematik worst-case murakkablik kafolati o‘rniga benchmark sifatida o‘qilishi kerak.

Ishning birinchi muhim vizual taqqoslashida GTA exact va heuristic yechuvchilar bilan solishtirilgan runtime grafigida joylashtiriladi. Ushbu grafika bo‘yicha exact solver sinfi yashil, heuristic usullar ko‘k, GTA esa ATSP uchun ancha past vaqt bilan ko‘rsatiladi. Matnga ko‘ra GTA 5.000 tugunli ATSP da o‘rtacha 600 soniya atrofida joylashar ekan, exact solverlar va heuristiklar turli trade-offlarga ega ekani tushuntiriladi. Bu ko‘rinish ishning asosiy g‘oyasini sodda ifodalaydi: GTA heuristic tezligiga yaqinlashar ekan, exact optimality, ya’ni 0% gap maqsadini saqlab qolishga urinadi.

Log-log va lin-log unumdorlik grafiklari tugunlar soni oshgani sari GTA runtime ma’lumotlari an’anaviy exact usullarga qaraganda pastroq nishab bilan masshtablanishini ko‘rsatadi. Log-log grafikasida GTA ma’lumotlari qizil nuqtalar bilan, heuristic 50% gap egri chizig‘i va best-case exact 0% gap egri chizig‘i bilan taqqoslanadi. Bu tasvir GTA ning ampirik jihatdan taxminan [ y = 10^{-5}x^{2.0368} ] chizig‘iga yaqin harakat qilishini ko‘rsatish uchun ishlatiladi. Yana bir bor aytish kerakki, bu tajriba ma’lumotiga moslashtirish; barcha ATSP misollari uchun nazariy kafolat emas.

Mualliflarning Gurobi bilan taqqoslash natijasi ham muhim. Bir grafikda GTA, lazy constraint ishlatadigan Gurobi va MTZ asosidagi yechim bilan solishtiriladi. GTA egri chizig‘i ham lazy-only, ham MTZ yondashuvlaridan pastda qoladi. Matnda warm start bo‘lmagan Gurobi ning lazy constraint bilan ham ayrim hollarda 24 soatdan oshib ketishi, MTZ formulatsiyasi esa katta hajmda yanada og‘irroq bo‘lishi aytiladi. Bu GTA dagi ishlashning asl manbai komponentlar sinergiyasi ekanini ko‘rsatish uchun ishlatiladi.

Ishda tarmoq vizualizatsiyasi bo‘limi ham mavjud. Tugunlar soni 10, 100, 1.000 va 2.000 bo‘lganda optimal marshrut xaritalari ko‘rsatiladi. 10 tugunli misol oson kuzatilsa, 100 tugunda bog‘lanishlar zichlashadi; 1.000 va 2.000 tugunda marshrut zich tarmoq ko‘rinishiga aylanadi. Katta yashil va ko‘k nuqtalar boshlang‘ich va o‘rta yo‘l tugunlarini bildiradi. Bu tasvirlar TSP/ATSP ning tugun soni oshgani sari qanday vizual va tuzilmaviy murakkablashishini ko‘rsatadi.

Bu vizualizatsiya faqat estetik qo‘shimcha emas. Ish marshrut xaritalari foydalanuvchiga yechimning fazoviy tuzilishini, klasterlanish xulqini, boshlang‘ich-o‘rta yo‘l aloqasini va tugunlarning optimal ketma-ketlikdagi o‘rnini sezgili tushunishga yordam berishini ta’kidlaydi. Logistika rejalashtirish, kuzatuv jadvalini tuzish va biologik ma’lumotlarni tartiblash kabi sohalarda foydalanuvchi faqat umumiy xarajatni emas, balki marshrutning qanday hosil bo‘layotganini ham ko‘rishni istashi mumkin. GTA interfeysi shu sababli real vaqt iteratsiya kuzatuvi va marshrut zichligini vizuallashtirishni taklif etadi.

Ishning yana bir muhim test guruhi seed o‘zgarishi bilan bog‘liq. ATSP xarajat matritsasi tasodifiy hosil qilinadi va seed o‘zgarganda xarajat koeffitsientlari, demakki global optimum va qidiruv maydoni ham o‘zgaradi. Agar algoritm faqat bitta seed da tez ishlasa, boshqa seed larda buzilsa, u ishonchli hisoblanmaydi. Ishda avval S = 42 va S = 65 seed qiymatlari, so‘ng 133, 29 va 7 seed qiymatlari bilan turli tugun sonlarida ish vaqtlarini taqqoslashgan.

Seed o‘zgarish natijalari GTA ning ish vaqti turli tasodifiy xarajat matritsalarida yaqin masshtablanish ko‘rsatishini ta’kidlaydi. Grafiklarda kichik tugun sonlarida mayda tebranishlar ko‘rinsa-da, katta tugun sonlarida runtime egri chiziqlari bir-biriga yaqinlashadi. Bu topilma ishda runtime seed-invariance deb talqin qilinadi. Ya’ni algoritmning ishlashi xarajat matritsasining ma’lum bir maxsus shakliga bog‘liq ko‘rinmaydi.

Biroq bu yerda ham ehtiyot bo‘lish kerak. Ish turli seed lar bilan hosil qilingan tasodifiy ATSP misollarida barqaror ishlash ko‘rsatganini da’vo qiladi; ammo bu barcha real dunyo ATSP muammolari bir xil osonlikda yechiladi degani emas. Haqiqiy qo‘llanmalardagi xarajat matritsalari tasodifiy va mustaqil taqsimlangan bo‘lmasligi mumkin; ular geografik, vaqtli, operatsion yoki biologik bog‘liqliklarni olib yuradi. Shuning uchun seed mustahkamligi muhim muhandislik ko‘rsatkichidir, ammo haqiqiy data benchmarklarining o‘rnini to‘liq bosa olmaydi.

Ishda xarajat koeffitsientlari masshtabi ham sinovdan o‘tkaziladi. Avval xarajatlar [1,10] oralig‘ida, so‘ng [10,100] oralig‘ida hosil qilinadi. Mualliflar bu masshtab o‘zgarishi nazariy jihatdan normallashtirilishi mumkinligini tan oladi; biroq amalda kattaroq koeffitsient oraliqlari solver xulqiga ta’sir qilishi mumkinligini aytadi. 6-shaklda ikki oraliqdagi runtime egri chiziqlari log-log, log-lin va lin-lin ko‘rinishlarda taqqoslanadi. Ishning talqiniga ko‘ra GTA xarajat koeffitsienti masshtabiga nisbatan katta darajada barqarordir.

Bu natija amaliy jihatdan muhim. Haqiqiy hayotda xarajatlar turli birliklarda bo‘lishi mumkin: kilometr, daqiqa, yoqilg‘i, xavf balli, astronomik ko‘rinuvchanlik koeffitsienti, genetik qoplanish balli yoki ustuvorlik vazni. Agar algoritm ma’lum sonli oraliq uchun sezgir bo‘lsa, har qo‘llanishda alohida normallashtirish va parametr sozlash kerak bo‘ladi. Ish GTA ning [1,10] bilan [10,100] oraliqlarida o‘xshash xulq ko‘rsatishini aytib, bunday qo‘shimcha oldindan ishlovga kamroq ehtiyoj bo‘lishi mumkinligini ta’kidlaydi.

Ishning eng diqqatga sazovor da’volaridan biri — to‘siqning algoritmik murakkablikdan RAM ga siljishi. Muhokama bo‘limida tajribalar 16 GB RAM li oddiy kompyuterlarda, GPU yoki parallel hisoblashsiz o‘tkazilgani aytiladi. Ishlatilgan tizimlardan biri 4 yadroli va 8 logical processor li Intel mashinasi; tekshiruv uchun esa 12-avlod i5, 8 yadro va 16 processor tuzilmasi keltiriladi. Mualliflar katta misollarda runtime ning yotiqroq xulq ko‘rsata boshlaganini va endi asosiy cheklov hisoblash vaqtidan ko‘ra xotira/bellek bo‘lib qolayotganini ta’kidlaydi.

Bu da’vo ilmiy jihatdan muhim, ammo ehtiyotkor ifodalanishi kerak. ATSP kabi NP-hard masalada “algoritmik murakkablik yo‘qoldi” deb aytish to‘g‘ri emas. Ishning da’vosi torroq o‘qilishi lozim: GTA ning muhandislik dizayni o‘rganilgan tasodifiy ATSP misollarida Gurobi qidiruv maydonini shunchalik toraytiradiki, amaliy to‘siq ayrim katta N qiymatlarida hisoblash vaqtidan ko‘ra xotira boshqaruviga siljiydi. Bu worst-case nazariy murakkablik da’vosi emas, balki tajribaviy kuzatuvdir.

Davomiy yaxshilash bo‘limida GTA kodidan grafik interfeys qatlami va diagonal o‘zgaruvchilar olib tashlangani natijasida ish vaqti sezilarli kamayganligi aytiladi. GUI kodning taxminan 30%–35% ini tashkil qilgani, foydalanuvchi uchun qulay bo‘lsa-da, xotira talabini oshirgani ta’kidlanadi. Bundan tashqari diagonal kirishlarga katta M qiymati berish o‘rniga bu o‘zgaruvchilar umuman yaratilmasligi tavsiya qilinadi.

Bu nuqta muhandislik jihatdan juda aniq. N = 2.000 uchun to‘liq matritsa yondashuvi 2.000 × 2.000 = 4.000.000 o‘zgaruvchi hosil qilishi mumkin. Diagonal o‘zgaruvchilar olib tashlanganda bu son 3.998.000 ga tushadi. Raqam farqi kichik ko‘rinsa-da, solver ning o‘zgaruvchi yaratishi, matritsa saqlashi, presolve va xotira boshqaruvi nuqtayi nazaridan ta’siri kattaroq bo‘lishi mumkin. Ishda GUI va diagonal o‘zgaruvchilar chiqarib tashlangani bilan o‘rtacha taxminan 50% runtime yaxshilanishi qayd etiladi.

7-shakl bu yaxshilanishni ko‘rsatadi. Yuqori panelda turli tugun sonlari uchun dastlabki GTA va GUI/diagonal chiqarilgan versiya ishlari vaqti taqqoslanadi. Past panelda dastlabki GTA ma’lumotlari bilan optimallashtirilgan versiya runtime egri chiziqlari ko‘rinadi. Matn algoritmning asosiy iteratsiyalari o‘zgarmaganini, asosiy farq kodni soddalashtirish va masala formulatsiyasini optimallashtirishdan kelib chiqqanini bildiradi. Bu ham ishning “to‘siq RAM va masala tasviriga siljidi” degan da’vosini kuchaytiradi.

Ishning qo‘llanilish sohalari keng muhokama qilinadi. Logistikada ATSP yo‘nalishga bog‘liq yetkazib berish va marshrut rejalashtirish uchun muhim. Astronomiyada teleskop kuzatuv tartibi, osmondagi maqsadlarning ko‘rinish oynalari, joylashuv cheklovlari va ilmiy ustuvorlik vaznlari bilan TSP/ATSP hosilalari paydo bo‘ladi. Genomikada DNK sekvenslash yoki assembly muammolari yo‘nalishli qoplanish va tartiblash tuzilmalari sababli ATSP ga o‘xshash optimallashtirishga ulanadi. Ish GTA ni vaqt oynalari, ko‘rinuvchanlik va pozitsion cheklovlar kabi variantlarga kengaytirish mumkinligini aytadi.

Ammo bu qo‘llanish da’volari ham ehtiyotkor ajratilishi kerak. Ish bu sohalardagi barcha real data muammolarini hal qilganini aytmaydi. Ba’zi variantlar tasvirlangan yoki mavjudligi aytiladi; boshqalari esa kelajak moslashtirish sifatida beriladi. Ayniqsa multi-agent TSP va gene overlap sequencing kabi sohalarda GTA to‘g‘ridan-to‘g‘ri sinovdan o‘tkazilmaganligi matnda qayd etiladi. Shuning uchun bu sohalar isbotlangan natijalar emas, balki ehtimoliy qo‘llanilish yo‘nalishlari sifatida o‘qilishi kerak.

Ishning kuchli tomonlaridan biri, amaliy muhandislik tafsilotlariga e’tibor berishidir. Faqat “yangi nazariy algoritm” bermasdan, solver parametrlari, warm start sifati, GUI, diagonal o‘zgaruvchilar, seed o‘zgarishi, xarajat masshtabi, runtime loglari va vizuallashtirish kabi haqiqiy ishlashga ta’sir qiluvchi jihatlarni muhokama qiladi. Bu yondashuv optimallashtirish dasturlarida ko‘pincha e’tibordan chetda qoladigan, ammo amaliyotda hal qiluvchi bo‘lgan tafsilotlarga e’tibor qaratadi.

Yana bir kuchli tomon — ATSP ning simmetrik TSP dan farqli ekanini uzluksiz ta’kidlashidir. Adabiyotdagi Concorde va TSPLIB kabi benchmarklarning ko‘pi simmetrik TSP uchun kuchli; ammo ATSP tomonida 5.000 tugunli standart benchmarklar kamligi qayd etiladi. Ish GTA ni shu bo‘shliqni to‘ldiruvchi nomzod ramka sifatida taqdim etadi. Ayniqsa TSPLIB dagi katta simmetrik misollar bilan ATSP natijalarini bevosita bir xil deb qabul qilmaslik kerakligini metodik jihatdan to‘g‘ri ta’kidlaydi.

Cheklovlar ham aniq. Birinchidan, ish hakamligi matn orqali tasdiqlanmagan loyihadir. Ikkinchidan, yaqin-kvadratik ish vaqti formal nazariy isbot bilan emas, balki ampirik runtime regressiyasi bilan qo‘llab-quvvatlangan. Uchinchidan, 5.000 tugunli ATSP uchun to‘g‘ridan-to‘g‘ri standartlashtirilgan tashqi benchmark yetishmaydi, shuning uchun taqqoslashlarning bir qismi simmetrik TSP benchmarklari yoki mualliflarning o‘z Gurobi variantlari bilan qilinadi. To‘rtinchidan, tasodifiy hosil qilingan xarajat matritsalari real sanoat, biologik yoki astronomik ma’lumotlarning barcha tuzilishlarini ifodalamaydi.

Beshinchi cheklov Gurobi kabi tijoriy solver ga bog‘liqlikdir. Ish Gurobi ni ochiq kirish falsafasi va ATSP ga mosligi uchun tanlaganini aytadi; ammo Gurobi litsenziyasi, foydalanuvchi kirishi va solver versiyasi farqlari reproduksiya jarayoniga ta’sir qilishi mumkin. Oltinchidan, ishda source code and variants are or will be made open-access degan jumla bor; bu kodning kirish mumkinligi va mustaqil takrorlash uchun juda muhim nuqta. Kod, parametrlar va loglar haqiqatan ochiq shaklda berilganda, da’volarni tekshirish ancha kuchayadi.

Ish aytayotgani bilan aytmayotganini aniq ajratish kerak. Ish GTA ning katta tasodifiy ATSP misollarida standart donanma ustida 0% gap ga tez yetishini bildiradi. Tabu Search warm start, Gurobi MIP va lazy subtour elimination birlashmasi kuchli muhandislik sinergiyasini hosil qilishini ta’kidlaydi. Ammo ish ATSP ning worst-case NP-hard murakkabligini nazariy jihatdan yo‘qotganini isbotlamaydi. Barcha real dunyo ATSP misollarida bir xil vaqtlarni kafolatlamaydi. Gurobi dan mustaqil, solver-agnostic algoritm taklif qilganini ham aytmaydi. Eng to‘g‘ri o‘qish shuki: GTA katta hajmli ATSP uchun amaliy, deterministik, muhandislikka yo‘naltirilgan va kuchli ishlash da’volariga ega gibrid yechim ramkasidir; bu da’volarning qiymati mustaqil takrorlanish va real data benchmarklar bilan yanada aniqroq bo‘ladi.

Tadqiqot usuli va natijalari

Tadqiqot usuli tasodifiy asimmetrik xarajat matritsalarini yaratish, Tabu Search yordamida yuqori sifatli warm start hosil qilish, MTZsiz Gurobi MIP modeli qurish, lazy constraint callback bilan subtour elimination qo‘llash, runtime/optimality gap/iteration/node metadata ni qayd etish va turli seed, xarajat masshtabi, masala hajmi hamda kod soddalashtirish sharoitlarida natijalarni taqqoslash bosqichlaridan iborat.

1. Masala turi va ma’lumot yaratish

2. ATSP ning asosiy MIP mantig‘i

Ish qo‘llagan MTZsiz Gurobi yondashuvini tushuntirish uchun standart ATSP maqsadi quyidagi munosabat bilan anglashiladi:

\[ \min \sum_{i=1}^{N}\sum_{j=1, j\neq i}^{N} c_{ij}x_{ij} \]

Chiqish cheklovi:

\[ \sum_{j=1, j\neq i}^{N} x_{ij}=1 \quad \forall i \]

Kirish cheklovi:

\[ \sum_{i=1, i\neq j}^{N} x_{ij}=1 \quad \forall j \]

Subtour elimination mantiqi:

\[ \sum_{i\in S}\sum_{j\in S, j\neq i}x_{ij} \leq |S|-1 \]

3. GTA ning algoritmik komponentlari

4. Warm start sifati

5. 1-jadvaldagi ishlash taqqoslashlari

6. Shakllarning texnik ma’nosi

• 1-jadval va ilk ishlash grafigi: GTA ni exact solver va heuristic usullar o‘rtasida joylashtirilganini ko‘rsatadi. Ish GTA ning ATSP da 0% gap bilan heuristic tezligiga yaqin vaqt ko‘rsatishini ta’kidlaydi.
• Log-log va lin-log grafigi: GTA runtime ma’lumotlarining tugunlar soniga nisbatan ampirik yaqin-kvadratik masshtablanishini ko‘rsatish g‘oyasini qo‘llaydi. Bu natija formal isbot emas, balki regressiya asosidagi tajribaviy kuzatuvdir.
• GTA-LAZY-MTZ taqqoslash: Warm start va MTZsiz lazy subtour elimination birikmasi warm start siz lazy va MTZ yondashuvlaridan pastroq runtime berganini ko‘rsatadi.
• Optimal marshrut xaritalari: 10, 100, 1.000 va 2.000 tugun uchun marshrut murakkabligi vizual jihatdan qanday oshishini ko‘rsatadi. Katta yashil va ko‘k nuqtalar boshlang‘ich va o‘rta yo‘l tugunlarini bildiradi.
• Seed invariance grafigi: S = 42, 65, 7, 29 va 133 kabi turli seed qiymatlarida runtime egri chiziqlari o‘xshash ishlashini ko‘rsatadi.
• Cost range grafigi: [1,10] va [10,100] xarajat oralig‘ida ish vaqti o‘xshash masshtablanish ko‘rsatishini ta’kidlaydi.
• GUI va diagonal o‘zgaruvchilarni olib tashlash grafigi: Kod soddalashtirish va modeldan diagonal o‘zgaruvchilarni chiqarib tashlash bilan o‘rtacha taxminan 50% runtime yaxshilanishi qayd etiladi.

7. Seed va xarajat masshtabi sinovlari

8. RAM va kod soddalashtirish ta’siri

9. Qo‘llanilish sohalari

10. Ishning asosiy topilmalari

• GTA Tabu Search warm start ni Gurobi MIP exact yechim bilan birlashtiradi.
• MTZ cheklovlari o‘rniga lazy constraint callback bilan subtour elimination qo‘llanadi.
• Ishda 5.000 tugungacha bo‘lgan ATSP misollarida 0% optimality gap qayd etiladi.
• 1-jadvalda GTA ning 5.000 tugunli ATSP uchun 350–850 soniya oralig‘i beriladi.
• Warm start siz Gurobi lazy constraints yondashuvi uchun 3.750–6.750 soniya oralig‘i bildiriladi.
• Yaqin-kvadratik N^2.01–N^2.03 xulq ampirik log-log regressiya bilan qo‘llab-quvvatlanadi.
• Turli seed qiymatlarida runtime masshtablash o‘xshash qolishi qayd etiladi.
• [1,10] va [10,100] xarajat oralig‘ida runtime barqarorligi ko‘rsatiladi.
• GUI va diagonal o‘zgaruvchilarni olib tashlash bilan taxminan 50% runtime yaxshilanishi qayd etiladi.
• Mualliflar katta masshtablarda asosiy to‘siq hisoblash vaqtidan RAM/tizim xotirasiga siljishini ta’kidlaydi.

11. Kuchli tomonlar

• ATSP ning simmetrik TSP dan farqli va yanada qiyin masala ekanini aniq ko‘rsatadi.
• Sezgir tezlik va exact MIP optimality maqsadini bitta arxitekturada birlashtiradi.
• Warm start sifatining MIP ishlashiga ta’sirini amaliy tarzda ko‘rib chiqadi.
• MTZsiz lazy subtour elimination bilan model o‘lchami va yechim yukini kamaytirishni maqsad qiladi.
• Seed, xarajat masshtabi va kod soddalashtirish sinovlari bilan muhandislik mustahkamligini ko‘rsatishga urinadi.
• Marshrut vizualizatsiyasi va foydalanuvchi interfeysi bilan usulni faqat nazariy emas, balki qo‘llash mumkin bo‘lgan vosita sifatida taqdim etadi.

12. Cheklovlar

• İsh hakamligi matn orqali tasdiqlanmagan tadqiqot loyihasi / preprint xarakteridadir.
• Yaqin-kvadratik murakkablik formal nazariy isbot bilan emas, ampirik runtime regressiyasi bilan qo‘llab-quvvatlanadi.
• 5.000 tugunli ATSP uchun to‘g‘ridan-to‘g‘ri standartlashtirilgan tashqi benchmark yo‘q.
• Taqqoslashlarning bir qismi simmetrik TSP benchmarklari bilan amalga oshiriladi; bu ma’lumotlar ATSP bilan bir xil masala sinfi emas.
• Tasodifiy hosil qilingan xarajat matritsalari real logistika, genomika yoki astronomiya ma’lumotlaridagi bog‘liqlik tuzilmasini to‘liq ifodalamaydi.
• GTA ning muvaffaqiyati Gurobi solver ga, solver parametrlari, RAM sig‘imi va warm start qo‘llanishiga bog‘liq.
• Kod va solver loglarining ochiq kirishli bo‘lishi mustaqil takrorlash uchun juda muhim; matnda ochiq kirish niyati bildirilgan.
• Multi-agent TSP, gene overlap sequencing va ayrim ilg‘or variantlar bu ishda to‘liq sinovdan o‘tgan natijalar sifatida ko‘rsatilmaydi.

Manba va usul izohi

Ushbu maqola Wissam Nakhle, Gaby Abou Haidar, Elie Al Ahmar va Roger Achkar tomonidan tayyorlangan “GTA - An ATSP Method: Shifting the Bottleneck from Algorithm to RAM” nomli ishga asoslanib tayyorlangan. Ishda muallif aloqalari Concordia University, American University of Science and Technology, Université La Sagesse va Antonine University sifatida ko‘rsatilgan.

Manba turi, matn tuzilmasi va taqdimot shakli inobatga olinganda akademik tadqiqot maqolasi loyihasi / preprint xarakteridagi texnik ish sifatida baholanishi kerak. Matn ichida hakamli jurnal qabulі, DOI, konferensiya qabulі yoki ochiq hakamlik bahosi tasdiqlanmaganligi sababli bu ish uchun matn orqali hakamligi tasdiqlanmagan ish iborasi ishlatilishi kerak.

Bu kontent tayyorlanayotganda ishda berilgan GTA arxitekturasi, Tabu Search warm start yondashuvi, Gurobi MIP qo‘llanilishi, MTZsiz lazy subtour elimination strategiyasi, ATSP ning simmetrik TSP dan farqi, 1-jadvaldagi ishlash taqqoslashlari, log-log va lin-log runtime grafiklarining talqini, seed o‘zgarishi, xarajat oralig‘i masshtablanishi, tarmoq vizualizatsiyasi, GUI/diagonal o‘zgaruvchi soddalashtirish tajribalari va xulosa hamda cheklovlar asos qilib olindi.

Matnda mavjud bo‘lmagan mustaqil tasdiq, hakamli nashr qabulі, barcha real dunyo ATSP misollari uchun kafolat, worst-case nazariy murakkablik isboti, Gurobi dan mustaqil muvaffaqiyat, barcha TSP variantlarida avtomatik ishlash yoki aniq tijoriy/operatsion muvaffaqiyat kabi iboralar qo‘shilmagan. Ishning topilmalari katta hajmli tasodifiy ATSP misollarida GTA ning kuchli va takrorlanuvchi ishlash ko‘rsatishi mumkinligini ta’kidlaydi; ammo bu da’volarning ilmiy ishonchliligi ochiq kod, to‘liq solver loglari, mustaqil takrorlashlar va real data benchmarklar bilan yanada mustahkamlanishi kerak.