Səyyar Satıcı Problemi optimallaşdırma ədəbiyyatının ən tanınmış və ən çətin problemlərindən biridir. Klassik formasında problem sadə görünür: Satıcı müəyyən şəhərlərin hər birini dəqiq bir dəfə ziyarət edəcək, sonra başlanğıc nöqtəsinə qayıdacaq və ümumi məsafəni minimum edəcək. Lakin şəhərlərin sayı artdıqca mümkün marşrutların sayı çox sürətlə böyüyür. Buna görə TSP NP-hard problem hesab olunur.

Tədqiqatın diqqət mərkəzindəki problem isə TSP-nin daha çətin variantı olan Asymmetric Traveling Salesman Problem, yəni ATSP-dir. Klassik simmetrik TSP-də iki şəhər arasındakı məsafə hər iki istiqamətdə eynidir. ATSP-də isə istiqamət önəmlidir. A-dan B-yə getməyin xərci ilə B-dən A-ya getməyin xərci fərqli ola bilər. Bu fərq real dünyada çox yayğındır. Birtərəfli yollar, trafik sıxlığı, külək istiqaməti, zaman pəncərələri, teleskopların göydəki hədəflərə çıxış ardıcıllığı, DNT fraqmentlərinin istiqamətdən asılı örtüşmələri və ya istehsal xətlərində əməliyyat ardıcıllığı asimmetrik xərclər yarada bilər.

Bu səbəbdən ATSP yalnız riyazi oyun deyil. Logistikada çatdırılma ardıcıllıqlarını, astronomiyada müşahidə planlarını, genomikada sekvensləmə və assembly proseslərini, sənayedə istehsal axınlarını və böyükmiqyaslı şəbəkə planlaşdırmasını təsir edən əsas optimallaşdırma problemidir. Lakin ATSP-nin istiqamətdən asılılığı həll fəzasını daha mürəkkəb edir. Simmetrik TSP üçün hazırlanmış bəzi üsullar birbaşa ATSP-yə tətbiq edilə bilməz və ya ciddi uyğunlaşdırma tələb edir.

Tədqiqatın əsas problemi budur: Böyükmiqyaslı ATSP nümunələri standart kompüterlərdə həm sürətli, həm də dəqiq şəkildə həll edilə bilərmi? Buradakı “dəqiq” ifadəsi önəmlidir. Bir çox heuristik üsul sürətli həll yaradır, lakin bu həllin qlobal optimum olduğuna zəmanət verilmir. Digər tərəfdən exact MIP həllediciləri nəzəri olaraq optimumu tapa bilər, lakin böyük ATSP nümunələrində hesablama müddəti və yaddaş istifadəsi sürətlə artır. Tədqiqat bu iki uc arasında körpü qurmağı hədəfləyir: heuristik sürəti exact solver dəqiqliyi ilə eyni arxitekturada birləşdirmək.

Müəlliflərin təklif etdiyi üsul GTA adlandırılır. GTA Gurobi Tabu Algorithm ifadəsinin qısaltmasıdır. Adından da göründüyü kimi, üsul kommersiya və geniş istifadə olunan MIP həll edicisi Gurobi ilə Tabu Search heuristikasını birləşdirir. Lakin tədqiqat bu komponentləri sadəcə yanaşı qoymadığını, böyükmiqyaslı ATSP üçün strateji şəkildə yenidən təşkil etdiyini müdafiə edir.

GTA-nın mərkəzində üçlü quruluş var:

• Tabu Search warm start: Çox qısa vaxtda yaxşı başlanğıc turu yaradır. Tədqiqatda bu başlanğıc həllərinin adətən 1%–5% optimality gap intervalında, konservativ olaraq 10% altında olduğu bildirilir.
• Gurobi MIP həlli: Başlanğıc turundan istifadə edərək exact axtarış aparır və 0% optimality gap hədəfinə çatmağa çalışır.
• MTZ-siz subtour elimination: Miller–Tucker–Zemlin məhdudiyyətləri əvəzinə lazy constraint callback istifadə edilərək alt turlar dinamik şəkildə aradan qaldırılır.

Bu üç komponentin birlikdə işləməsi vacibdir. Tabu Search təkbaşına sürətli, lakin təxmini nəticə verir. Gurobi təkbaşına böyük ATSP-də soyuq başlanğıcla çox uzun çəkə bilər. MTZ məhdudiyyətləri isə klassik TSP formulyasiyalarında alt turları maneə etmək üçün istifadə olunsa da, böyük problemlərdə model ölçüsünü və həll yükünü artıra bilər. GTA yaxşı başlanğıc turu verərək Gurobi-nin axtarış ağacını daraldır; MTZ məhdudiyyətlərini çıxararaq model strukturunu yüngülləşdirir; lazy constraints ilə yalnız lazım olduqda subtour kəsikləri əlavə edir.

ATSP-nin standart MIP məntiqini izah etmək üçün əsas formulyasiya belə düşünülə bilər. Bu formul tədqiqatın istifadə etdiyi MTZ-siz MIP yanaşmasını başa düşməyə kömək edən fon izahıdır:

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

Burada N düyün sayıdır. c_ij i düyünündən j düyününə getməyin xərcidir. ATSP-də ümumiyyətlə c_ij ≠ c_ji ola bilər. x_ij i-dən j-yə gedilib-gedilmədiyini göstərən ikili dəyişəndir. Əgər marşrut i-dən j-yə keçirsə [ x_{ij}=1 ], keçmirsə [ x_{ij}=0 ] olur.

Hər düyündən dəqiq bir çıxış olmasını təmin edən əsas dərəcə məhdudiyyəti:

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

Hər düyünə dəqiq bir giriş olmasını təmin edən məhdudiyyət:

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

Bu iki məhdudiyyət hər düyünün bir dəfə çıxış və bir dəfə giriş almasını təmin edir. Lakin bunlar təkbaşına yetərli deyil. Çünki həll bütün düyünləri əhatə edən tək tur əvəzinə bir neçə kiçik dövrəyə, yəni subtour-lara ayrıla bilər. Məsələn 1-2-3-1 və 4-5-6-4 kimi iki ayrı qapalı marşrut yarana bilər. TSP/ATSP-nin əsas çətinliyi bütün düyünləri vahid Hamilton turunda birləşdirməkdir.

Klassik MTZ yanaşması əlavə sıralama dəyişənləri ilə bu alt turların qarşısını almağa çalışır. Lakin böyük miqyaslarda bu əlavə dəyişənlər və məhdudiyyətlər həlli ağırlaşdıra bilər. Tədqiqatın təklif etdiyi yanaşmada MTZ məhdudiyyətləri əvəzinə lazy constraint callback istifadə olunur. Bu məntiqdə solver əvvəlcə dərəcə məhdudiyyətləri ilə həll yaradır; əgər həll alt turlardan ibarətdirsə, yalnız həmin alt turları kəsən yeni məhdudiyyətlər sonradan əlavə edilir. Ümumi subtour elimination məntiqi bu fon formulu ilə izah edilə bilər:

\[ \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 \]

Burada S bütün düyünlərin yalnız alt çoxluğudur. Bu məhdudiyyət S çoxluğu daxilindəki düyünlərin öz aralarında qapalı kiçik tur yaratmasına mane olur. Lakin bütün mümkün S çoxluqları üçün bu məhdudiyyətləri əvvəlcədən əlavə etmək praktik deyil. Lazy constraint yanaşması məhz buna görə istifadə edilir: yalnız solver-in tapdığı həllərdə həqiqətən ortaya çıxan alt turlar kəsilir.

Tədqiqatın GTA-nı güclü etdiyini müdafiə etdiyi nöqtə budur. MIP həll edicisi çox böyük həll fəzasında sıfırdan dolaşmağa başlamır. Tabu Search əvvəlcə yaxşı marşrut verir. Bu marşrut Gurobi üçün incumbent, yəni başlanğıc həlli olur. Əgər incumbent optimuma yaxındırsa, branch-and-cut axtarışı daha dar sahədə işləyə bilər; zəif budaqlar daha erkən budana bilər; cut generation daha effektiv ola bilər. Tədqiqat warm start keyfiyyətinin buna görə kritik olduğunu vurğulayır.

Müəlliflər zəif warm start həllərinin faydadan çox zərər verə biləcəyini xüsusilə qeyd edir. Tədqiqatda 10%–15%-dən böyük gap-i olan başlanğıcların MIP həll edicisini yanlış istiqamətləndirə, hətta soyuq başlanğıcdan daha pis performans yarada biləcəyi bildirilir. Bunun səbəbi pis incumbent-ın axtarış ağacını yanlış yönləndirməsi, daha yaxşı həllərin erkən tapılmasına mane olması və solver-in daxili heuristikalarını basdırmasıdır. Buna görə GTA üçün sadəcə “bir başlanğıc həlli” deyil, struktur baxımından tutarlı və kifayət qədər yaxın başlanğıc turu lazımdır.

Tədqiqatda Tabu Search warm start-ın ümumiyyətlə saniyələr ərzində 1%–9% intervalında gap yaratdığı, əksər hallarda 5% altında qaldığı müdafiə olunur. Eyni mətndə genetik alqoritm və simulated annealing kimi digər heuristikaların böyük ATSP nümunələrində 30 dəqiqəni aşa bilən müddətlərdən sonra belə 50%-i aşan gap-lər verə bildiyi qeyd olunur. Buna görə müəlliflər GTA arxitekturasında Tabu Search seçiminin təsadüfi olmadığını, warm start keyfiyyəti ilə sürət balansından qaynaqlandığını müdafiə edir.

Tədqiqatın performans iddiaları olduqca güclüdür. Cədvəl 1-də GTA-nın 5.000 düyünlü ATSP üçün N^2.01–N^2.03 intervalında empirik mürəkkəblik göstərdiyi və 350–850 saniyə ərzində 0% optimality gap əldə etdiyi bildirilir. Buna qarşı warm start olmadan Gurobi lazy-constraint yanaşması üçün N^2.1–N^2.2 və 3.750–6.750 saniyə intervalı verilir. Bu müqayisə GTA-nın sadəcə Gurobi istifadə etməkdən ibarət olmadığını; warm start və model dizaynının iş vaxtını ciddi şəkildə dəyişdirdiyini göstərmək üçün istifadə olunur.

Lakin burada diqqətli elmi ayrım edilməlidir. Tədqiqatda verilən N^2.01–N^2.03 davranışı formal alqoritmik mürəkkəblik sübutu deyil. Müəlliflər də bunu açıq qeyd edir: yaxın-kvadratik davranış müxtəlif düyün saylarında ölçülən iş vaxtı məlumatlarının log-log reqressiyası ilə modelləşdirilməsindən əldə edilib. NP-hard ATSP üçün belə empirik miqyaslama hesabatları ədəbiyyatda geniş yayılsa da, bunlar riyazi worst-case mürəkkəblik zəmanəti deyil, eksperimental benchmark kimi oxunmalıdır.

Tədqiqatın ilk mühüm vizual müqayisəsi GTA-nı exact və heuristic həll edicilərlə mövqeləndirən runtime qrafikidir. Bu qrafikdə exact solver kateqoriyası yaşıl, heuristic üsullar mavi, GTA isə ATSP üçün xeyli aşağı müddətlə göstərilir. Mətnə görə GTA 5.000 düyünlü ATSP-də təxminən 600 saniyəlik orta iş vaxtı səviyyəsində mövqelənir, exact solver-lərin və heuristikaların isə müxtəlif trade-off-ları olduğu izah edilir. Bu vizual tədqiqatın əsas iddiasını sadə şəkildə təqdim edir: GTA heuristic sürətinə yaxınlaşarkən exact optimality, yəni 0% gap hədəfini qorumağa çalışır.

Tədqiqatdakı log-log və lin-log performans qrafikləri düyün sayı artdıqca GTA runtime məlumatlarının ənənəvi exact üsullara nisbətən daha aşağı meylli miqyaslama göstərdiyini izah edir. Log-log qrafikdə GTA məlumatları qırmızı nöqtələrlə, heuristic 50% gap əyrisi və best-case exact 0% gap əyrisi ilə müqayisə olunur. Bu vizual GTA-nın empirik olaraq təxminən [ y = 10^{-5}x^{2.0368} ] xəttinə yaxın davranış göstərdiyi iddiasını dəstəkləmək üçün istifadə edilir. Yenə də bu, eksperimental məlumat uyğunlaşdırmasıdır; bütün ATSP nümunələri üçün nəzəri zəmanət deyil.

Tədqiqatın öz Gurobi müqayisəsi də vacibdir. Bir qrafikdə GTA lazy constraint istifadə edən Gurobi və MTZ əsaslı həll ilə müqayisə olunur. GTA əyrisi həm lazy-only, həm də MTZ yanaşmasına nisbətən daha aşağı qalır. Mətn warm start olmadan Gurobi-nin lazy constraint ilə belə bəzi hallarda 24 saatı aşa bildiyini, MTZ formulyasiyasının isə böyük miqyaslarda daha da ağırlaşdığını bildirir. Bu, GTA-dakı performansın əsas mənbəyinin komponentlərin sinerjisi olduğu iddiasını gücləndirmək üçün istifadə olunur.

Tədqiqatda şəbəkə vizuallaşdırma bölməsi də var. Düyün sayı 10, 100, 1.000 və 2.000 olduqda optimal marşrut xəritələri göstərilir. 10 düyünlü nümunə asan izlənilir, 100 düyündə bağlantılar sıxlaşır; 1.000 və 2.000 düyündə marşrut sıx şəbəkə görünüşünə çevrilir. Böyük yaşıl və mavi nöqtələr başlanğıc və orta yol düyünlərini təmsil edir. Bu vizuallar TSP/ATSP-nin düyün sayı artdıqca vizual və struktur olaraq necə mürəkkəbləşdiyini izah edir.

Bu vizuallaşdırma yalnız estetik əlavə deyil. Tədqiqat marşrut xəritələrinin istifadəçiyə həllin məkan strukturunu, qruplaşma davranışını, başlanğıc-orta yol əlaqəsini və düyünlərin optimal ardıcıllıqdakı yerini intuitiv şəkildə anlamaqda kömək etdiyini müdafiə edir. Logistika planlaşdırması, müşahidə cədvəlləşdirməsi və bioloji məlumat sıralaması kimi sahələrdə istifadəçi yalnız ümumi xərci deyil, marşrutun necə formalaşdığını da görmək istəyə bilər. GTA interfeysinin buna görə real vaxt iterasiya izləmə və marşrut sıxlığı vizuallaşdırması təqdim etdiyi bildirilir.

Tədqiqatın digər mühüm test qrupu seed dəyişməsi ilə bağlıdır. ATSP xərc matrisi təsadüfi yaradılır və seed dəyişdikdə xərc əmsalları, nəticədə qlobal optimum və axtarış sahəsi dəyişir. Əgər alqoritm yalnız müəyyən seed-də sürətli işləyir, başqa seed-lərdə pisləşirsə etibarlı hesab edilə bilməz. Tədqiqatda əvvəlcə S = 42 və S = 65 seed dəyərləri, sonra 133, 29 və 7 seed dəyərləri ilə müxtəlif düyün saylarında iş vaxtları müqayisə edilib.

Seed dəyişməsi nəticələri GTA-nın iş vaxtının müxtəlif təsadüfi xərc matrislərində yaxın miqyaslama göstərdiyini müdafiə edir. Qrafiklərdə kiçik düyün saylarında kiçik dalğalanmalar görünür, böyük düyün saylarında isə runtime əyriləri bir-birinə yaxınlaşır. Bu tapıntı tədqiqatda runtime seed-invariance kimi şərh edilir. Yəni alqoritmin performansı təsadüfi xərc matrisinin müəyyən xüsusi formasından asılı görünmür.

Lakin burada da diqqətli olmaq lazımdır. Tədqiqat müxtəlif seed-lərlə təsadüfi yaradılmış ATSP nümunələrində stabil performans göstərdiyini müdafiə edir; amma bu, bütün real dünya ATSP nümunələrinin eyni asanlıqla həll ediləcəyi demək deyil. Real tətbiqlərdəki xərc matrisləri təsadüfi və müstəqil paylanmış olmaya bilər; coğrafi, zaman, əməliyyat və ya bioloji asılılıqlar daşıya bilər. Buna görə seed dayanıqlığı mühüm mühəndislik göstəricisidir, lakin real məlumat benchmarklarının yerini tam tuta bilməz.

Tədqiqatda xərc əmsallarının miqyası da sınaqdan keçirilir. Əvvəl xərclər [1,10] intervalında, sonra [10,100] intervalında yaradılır. Müəlliflər bu miqyas dəyişikliyinin nəzəri olaraq normallaşdırıla biləcəyini qəbul edir; lakin praktikada daha böyük əmsal intervallarının solver davranışına təsir edə biləcəyini bildirir. Figure 6-da iki intervaldakı runtime əyriləri log-log, log-lin və lin-lin görünüşlərdə müqayisə olunur. Tədqiqatın şərhi GTA-nın xərc əmsalı miqyasına qarşı böyük ölçüdə stabil olmasıdır.

Bu nəticə tətbiq baxımından vacibdir. Real dünyada xərclər müxtəlif vahidlərdə ola bilər: kilometr, dəqiqə, yanacaq, risk balı, astronomik görünmə əmsalı, genetik örtüşmə balı və ya prioritet çəkisi. Əgər alqoritm müəyyən ədədi intervala həssasdırsa, hər tətbiqdə xüsusi normallaşdırma və parametr tənzimləməsi tələb olunur. Tədqiqat GTA-nın [1,10] ilə [10,100] intervallarında oxşar davranış göstərdiyini bildirərək belə əlavə ön emala daha az ehtiyac ola biləcəyini müdafiə edir.

Tədqiqatın ən diqqətçəkən iddialarından biri darboğazın alqoritmik mürəkkəblikdən RAM-a keçməsidir. Müzakirə bölməsində təcrübələrin 16 GB RAM-li standart kompüterlərdə, GPU və paralelləşdirmə olmadan aparıldığı bildirilir. İstifadə olunan sistemlərdən biri 4 nüvə və 8 logical processor olan Intel maşınıdır; yoxlama üçün isə 12-ci nəsil i5, 8 nüvə və 16 processor quruluşu istifadə olunub. Müəlliflər böyük nümunələrdə runtime-ın üfüqə yaxın davranmağa başladığını və artıq əsas məhdudlaşdırıcının RAM/sistem yaddaşı olduğunu müdafiə edir.

Bu iddia elmi baxımdan vacibdir, lakin diqqətlə ifadə olunmalıdır. ATSP kimi NP-hard problemdə “alqoritmik mürəkkəblik aradan qalxdı” demək düzgün olmaz. Tədqiqatın iddiası daha məhdud oxunmalıdır: GTA-nın mühəndislik dizaynı araşdırılan təsadüfi ATSP nümunələrində Gurobi-nin axtarış fəzasını o qədər daraldır ki, praktik darboğaz müəyyən böyük N dəyərlərində hesablama müddətindən daha çox yaddaş idarəetməsinə keçir. Bu worst-case nəzəri mürəkkəblik iddiası deyil, eksperimental performans müşahidəsidir.

Davamlı yaxşılaşdırma bölməsində GTA kodundan qrafik interfeys qatının və diagonal dəyişənlərin çıxarılması ilə iş vaxtlarında mühüm azalma əldə edildiyi bildirilir. GUI-nin kodun təxminən 30%–35%-ni təşkil etdiyi, istifadəçi dostu istifadə üçün vacib olduğu, lakin RAM tələbini artırdığı müdafiə edilir. Bundan əlavə, diagonal girişlərə böyük M dəyəri vermək əvəzinə bu dəyişənlərin ümumiyyətlə yaradılmaması təklif olunur.

Bu məqam mühəndislik baxımından çox konkretdir. N = 2.000 üçün tam matris yanaşması 2.000 × 2.000 = 4.000.000 dəyişən yarada bilər. Diagonal dəyişənlər çıxarıldıqda bu say 3.998.000 olur. Ədədi fərq yalnız 2.000 kimi görünsə də, solver-in dəyişən yaratması, matris saxlaması, presolve və yaddaş idarəetməsi baxımından təsirləri daha böyük ola bilər. Tədqiqatda GUI və diagonal dəyişənlərin çıxarılması ilə orta hesabla təxminən 50% runtime yaxşılaşması bildirilir.

Figure 7 bu yaxşılaşmanı göstərir. Yuxarı paneldə müxtəlif düyün sayları üçün başlanğıc GTA müddətləri ilə GUI/diagonal çıxarılmış versiyanın müddətləri müqayisə olunur. Aşağı paneldə başlanğıc GTA məlumatı ilə optimallaşdırılmış versiyanın runtime əyriləri görünür. Mətn alqoritmin əsas iterasiyalarının eyni qaldığını, əsas fərqin kod sadələşdirməsi və problem formulyasiyası optimallaşdırmasından gəldiyini bildirir. Bu da tədqiqatın “darboğaz RAM və problem təqdimatıdır” iddiasını dəstəkləmək üçün istifadə olunur.

Tədqiqatın tətbiq sahələri geniş şəkildə müzakirə edilir. Logistikada ATSP istiqamətdən asılı çatdırılma və marşrut planlaşdırması üçün vacibdir. Astronomiyada teleskop müşahidə ardıcıllığı, göydəki hədəflərin görünürlük pəncərələri, mövqe məhdudiyyətləri və elmi prioritet çəkiləri ilə TSP/ATSP törəmələrinə çevrilə bilər. Genomikada DNT sekvensləmə və ya assembly problemləri istiqamətdən asılı örtüşmə və sıralama strukturları səbəbilə ATSP tipli optimallaşdırmalara bağlana bilər. Tədqiqat GTA-nın zaman pəncərələri, görünürlük və mövqe məhdudiyyətləri kimi variantlara genişləndirilə biləcəyini bildirir.

Lakin bu tətbiq iddiaları da diqqətlə ayrılmalıdır. Tədqiqat bu sahələrdəki bütün real məlumat problemlərini həll etməyib. Bəzi variantların hazırlanmış və ya mövcud olduğu bildirilir; bəziləri isə gələcək uyğunlaşdırma kimi təqdim edilir. Xüsusilə multi-agent TSP və gene overlap sequencing kimi sahələrdə GTA-nın birbaşa sınaqdan keçirilmədiyi mətndə qeyd olunur. Buna görə bu sahələr sübut edilmiş nəticələrdən çox potensial tətbiq sahələri kimi oxunmalıdır.

Tədqiqatın güclü tərəflərindən biri praktik mühəndislik detallara önəm verməsidir. Sadəcə “yeni nəzəri alqoritm” təqdim etmək əvəzinə solver parametrləri, warm start keyfiyyəti, GUI, diagonal dəyişənlər, seed dəyişməsi, xərc miqyaslaması, runtime logları və vizuallaşdırma kimi real istifadədə performansa təsir edən elementləri müzakirə edir. Bu yanaşma optimallaşdırma proqramlarında çox vaxt gözdən qaçan, lakin tətbiqdə həlledici olan detallara fokuslanır.

Digər güclü tərəf ATSP-nin simmetrik TSP-dən ayrılmasını daim vurğulamasıdır. Ədəbiyyatda Concorde və TSPLIB kimi benchmarkların çoxu simmetrik TSP üçün güclüdür; lakin ATSP tərəfində 5.000 düyünlü standart benchmarkların çatışmadığı bildirilir. Tədqiqat GTA-nı bu boşluğu dolduran namizəd çərçivə kimi təqdim edir. Xüsusilə TSPLIB-dəki böyük simmetrik nümunələrlə ATSP nəticələrinin birbaşa eyni olmadığını vurğulaması metodoloji baxımdan düzgündür.

Məhdudiyyətlər də aydındır. Birincisi, tədqiqatın hakemliyi mətn üzərindən təsdiqlənməyən layihədir. İkincisi, yaxın-kvadratik iş vaxtı üçün formal nəzəri sübut yoxdur; nəticə empirik reqressiyaya əsaslanır. Üçüncüsü, 5.000 düyünlü ATSP üçün birbaşa standartlaşdırılmış xarici benchmark çatışmadığına görə müqayisələr simmetrik TSP benchmarkları və ya müəlliflərin öz Gurobi variantları ilə aparılır. Dördüncüsü, təsadüfi yaradılan xərc matrisləri real sənaye, bioloji və ya astronomik məlumat strukturlarının hamısını təmsil etməyə bilər.

Beşinci məhdudiyyət Gurobi kimi kommersiya solver-dən asılılıqdır. Tədqiqat Gurobi-ni açıq giriş fəlsəfəsi və ATSP-yə uyğunluğu səbəbilə seçdiyini bildirir; lakin Gurobi lisenziyası, istifadəçi çıxışı və solver versiyası fərqləri reproduksiyaya təsir edə bilər. Altıncı olaraq tədqiqatda “source code and variants are or will be made open-access” ifadəsi yer alır; bu, kodun əlçatanlığı və müstəqil təkrar üçün kritik nöqtədir. Kod, parametrlər və loglar həqiqətən açıq şəkildə təqdim edildikdə iddiaların yoxlanması daha güclü olacaq.

Tədqiqatın nə dediyi ilə nə demədiyi aydın ayrılmalıdır. Tədqiqat GTA-nın böyük təsadüfi ATSP nümunələrində standart avadanlıq üzərində 0% gap-ə sürətlə çatdığını bildirir. Tabu Search warm start, Gurobi MIP və lazy subtour elimination birləşməsinin güclü mühəndislik sinerjisi yaratdığını müdafiə edir. Lakin tədqiqat ATSP-nin worst-case NP-hard çətinliyini aradan qaldırdığını nəzəri olaraq sübut etmir. Bütün real dünya ATSP nümunələrində eyni müddətləri zəmanət vermir. Gurobi-dən müstəqil, solver-agnostic alqoritm təqdim etdiyini də demir. Ən düzgün oxunuş budur: GTA böyükmiqyaslı ATSP üçün praktik, deterministik, mühəndislik yönümlü və güclü performans iddiaları olan hibrid həll çərçivəsidir; bu iddiaların dəyəri müstəqil reproduksiya və real məlumat benchmarkları ilə daha aydın olacaq.

Tədqiqatın Metodu və Nəticələri

Tədqiqatın metodu təsadüfi asimmetrik xərc matrisləri yaratmaq, Tabu Search ilə yüksək keyfiyyətli warm start hazırlamaq, MTZ-siz Gurobi MIP modeli qurmaq, lazy constraint callback ilə subtour elimination tətbiq etmək, runtime/optimality gap/iteration/node metadata qeydə almaq və müxtəlif seed, xərc miqyası, problem ölçüsü və kod sadələşdirməsi şərtlərində performansı müqayisə etmək addımlarından ibarətdir.

1. Problem tipi və məlumat yaradılması

2. ATSP-nin əsas MIP məntiqi

Tədqiqatın istifadə etdiyi MTZ-siz Gurobi yanaşmasını izah etmək üçün standart ATSP məqsədi bu əsas əlaqə ilə başa düşülə bilər:

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

Çıxış məhdudiyyəti:

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

Giriş məhdudiyyəti:

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

Subtour elimination məntiqi:

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

3. GTA-nın alqoritmik komponentləri

4. Warm start keyfiyyəti

5. Cədvəl 1 performans müqayisəsi

6. Şəkillərin texniki mənası

• Cədvəl 1 və ilk performans qrafiki: GTA-nın exact solver və heuristic üsullar arasında mövqeləndirildiyini göstərir. Tədqiqat GTA-nın ATSP-də 0% gap ilə heuristic sürətinə yaxın runtime təqdim etdiyini müdafiə edir.
• Log-log və lin-log performans qrafikləri: GTA runtime məlumatlarının düyün sayına qarşı empirik olaraq yaxın-kvadratik miqyaslama göstərdiyi iddiasını dəstəkləyir. Bu nəticə formal sübut deyil, reqressiyaya əsaslanan eksperimental müşahidədir.
• GTA-LAZY-MTZ müqayisəsi: Warm start və MTZ-siz lazy subtour elimination birləşməsinin warm start-sız lazy və MTZ yanaşmalarından daha aşağı runtime verdiyini göstərir.
• Optimal route xəritələri: 10, 100, 1.000 və 2.000 düyün üçün marşrut mürəkkəbliyinin vizual olaraq necə böyüdüyünü göstərir. Böyük yaşıl və mavi nöqtələr başlanğıc və orta yol düyünlərini təmsil edir.
• Seed invariance qrafiki: S = 42, 65, 7, 29 və 133 kimi fərqli seed dəyərlərində runtime əyrilərinin oxşar davrandığını göstərir.
• Cost range qrafiki: [1,10] və [10,100] xərc intervallarında iş vaxtının oxşar miqyaslama göstərdiyini müdafiə edir.
• GUI və diagonal dəyişən çıxarma qrafiki: Kod sadələşdirməsi və modeldən diagonal dəyişənlərin çıxarılması ilə orta hesabla təxminən 50% runtime yaxşılaşması bildirilir.

7. Seed və xərc miqyası testləri

8. RAM və kod sadələşdirmə təsiri

9. Tətbiq sahələri

10. Tədqiqatın əsas tapıntıları

• GTA Tabu Search warm start ilə Gurobi MIP exact həllini birləşdirir.
• MTZ məhdudiyyətləri əvəzinə lazy constraint callback ilə subtour elimination tətbiq olunur.
• Tədqiqatda 5.000 düyünə qədər ATSP nümunələrində 0% optimality gap bildirilir.
• Cədvəl 1-də GTA üçün 5.000 düyünlü ATSP-də 350–850 saniyə intervalı verilir.
• Warm start olmadan Gurobi lazy constraints yanaşması üçün 3.750–6.750 saniyə intervalı bildirilir.
• Yaxın-kvadratik N^2.01–N^2.03 davranışı empirik log-log reqressiya ilə müdafiə olunur.
• Fərqli seed dəyərlərində runtime miqyaslamasının oxşar qaldığı bildirilir.
• [1,10] və [10,100] xərc intervallarında runtime sabitliyi göstərilir.
• GUI və diagonal dəyişənlərin çıxarılması ilə təxminən 50% runtime yaxşılaşması bildirilir.
• Müəlliflər böyük miqyaslarda əsas darboğazın hesablama müddətindən RAM/sistem yaddaşına keçdiyini müdafiə edir.

11. Güclü tərəflər

• ATSP-nin simmetrik TSP-dən fərqli və daha çətin problem olduğunu aydın şəkildə vurğulayır.
• Heuristik sürətlə exact MIP optimality hədəfini eyni arxitekturada birləşdirir.
• Warm start keyfiyyətinin MIP performansına təsirini praktik şəkildə işləyir.
• MTZ-siz lazy subtour elimination ilə model ölçüsünü və həll yükünü azaltmağı hədəfləyir.
• Seed, xərc intervalı və kod sadələşdirmə testləri ilə mühəndislik dayanıqlığını göstərməyə çalışır.
• Marşrut vizuallaşdırması və istifadəçi interfeysi ilə üsulu yalnız nəzəri deyil, tətbiq oluna bilən alət kimi təqdim edir.

12. Məhdudiyyətlər

• Tədqiqat hakemliyi mətn üzərindən təsdiqlənməyən tədqiqat layihəsi / preprint xarakterindədir.
• Yaxın-kvadratik mürəkkəblik formal nəzəri sübutla deyil, empirik runtime reqressiyası ilə dəstəklənir.
• 5.000 düyünlü ATSP üçün birbaşa standartlaşdırılmış xarici benchmark çatışmazlığı var.
• Müqayisələrin bir hissəsi simmetrik TSP benchmarkları ilə aparılır; bu məlumatlar ATSP ilə eyni problem sinfi deyil.
• Təsadüfi yaradılan xərc matrisləri real logistika, genomika və ya astronomiya məlumatlarındakı asılılıq strukturunu tam təmsil etməyə bilər.
• GTA-nın uğuru Gurobi solver-ə, solver parametrlərinə, RAM tutumuna və warm start tətbiqinə bağlıdır.
• Kodun və solver loglarının açıq girişi müstəqil təkrar üçün kritikdir; mətndə açıq giriş niyyəti bildirilir.
• Multi-agent TSP, gene overlap sequencing və bəzi qabaqcıl variantlar bu tədqiqatda tam sınaqdan keçirilmiş nəticələr kimi təqdim olunmur.

Mənbə və Metod Qeydi

Bu məqalə Wissam Nakhle, Gaby Abou Haidar, Elie Al Ahmar və Roger Achkar tərəfindən hazırlanmış “GTA - An ATSP Method: Shifting the Bottleneck from Algorithm to RAM” adlı tədqiqata əsasən hazırlanıb. Tədqiqatda müəllif əlaqələri Concordia University, American University of Science and Technology, Université La Sagesse və Antonine University kimi göstərilib.

Mənbə növü mətnin quruluşu və təqdimat forması nəzərə alınmaqla akademik tədqiqat məqaləsi layihəsi / preprint xarakterli texniki tədqiqat kimi qiymətləndirilməlidir. Mətn daxilində hakemli jurnal qəbulu, DOI, konfrans qəbulu və ya açıq hakem qiymətləndirməsi məlumatı təsdiqlənmədiyi üçün bu tədqiqat üçün hakemliyi mətn üzərindən təsdiqlənməyən tədqiqat ifadəsi işlədilməlidir.

Bu məzmun hazırlanarkən tədqiqatda verilən GTA arxitekturası, Tabu Search warm start yanaşması, Gurobi MIP istifadəsi, MTZ-siz lazy subtour elimination strategiyası, ATSP-nin simmetrik TSP-dən fərqi, Cədvəl 1 performans müqayisəsi, log-log və lin-log runtime qrafiklərinin şərhi, seed dəyişməsi, xərc intervalının miqyaslanması, şəbəkə vizuallaşdırması, GUI/diagonal dəyişən sadələşdirmə təcrübələri və nəticə bölməsindəki iddia və məhdudiyyətlər əsas götürülüb.

Mətndə olmayan müstəqil doğrulama, hakemli nəşr qəbulu, bütün real dünya ATSP nümunələri üçün zəmanət, worst-case nəzəri mürəkkəblik sübutu, Gurobi-dən müstəqil uğur, bütün TSP variantlarında avtomatik işləmə və ya dəqiq kommersiya/əməliyyat uğuru kimi iddialar əlavə edilməyib. Tədqiqatın nəticələri böyükmiqyaslı təsadüfi ATSP nümunələrində GTA-nın güclü və təkrarlana bilən performans göstərə biləcəyini müdafiə edir; lakin bu iddiaların elmi etibarlılığı açıq kod, tam solver logları, müstəqil təkrarlar və real məlumat benchmarkları ilə daha da gücləndirilməlidir.