Çoxçəkili Adaptiv Depo Optimallaşdırması (Multi-Weight Adaptive Depot Optimization, MADO), tək depolu çoxsaylı səyyar satıcı problemində müştəri düyünlərini klasterlərə ayıran, hər klasteri bir səyyar satıcıya təyin edən və ortaq depo mövqeyini marşrut səmərəliliyi ilə iş yükü balansını birlikdə nəzərə alacaq şəkildə iterativ olaraq dəyişdirən optimallaşdırma yanaşmasıdır. Tədqiqat TSPLIB benchmark verilənlər dəstləri üzərində səkkiz müxtəlif klasterləşdirmə alqoritmini, OR-Tools əsaslı TSP həllini, depo mövqeyinin optimallaşdırılmasını və Total-Sum Distance, Min-Max Distance, Workload Balance, Cluster Separability, Robustness və Running Time olmaqla altı performans göstəricisini birləşdirir.

Metodun əsas ideyası böyük bir SD-MTSP-ni birbaşa bütöv şəkildə həll etmək əvəzinə müştəri düyünlərini klasterlərə ayıraraq onu daha kiçik TSP alt problemlərinə bölməkdir. Daha sonra ortaq depo mövqeyi klasterlərin ölçüsünü və məkan/marşrut yükünü təmsil edən çəkilər vasitəsilə yenilənir. Hər namizəd depo üçün klasterdaxili TSP marşrutları yenidən həll edilir və yeni mövqe marşrut uzunluğu ilə balans meyarlarına görə qiymətləndirilir.

İlk beş verilənlər dəsti müqayisəsində att48, eil76, gr229, pr299 və dsj1000 istifadə edilmişdir. Total-Sum Distance baxımından att48-də BIRCH, gr229-da Fuzzy C-Means; eil76, pr299 və dsj1000-də isə Bisecting K-Means ən aşağı qiymətləri vermişdir. Bu nəticə heç bir klasterləşdirmə alqoritminin hər verilən paylanmasında üstün olmadığını göstərir.

pr299 hal tədqiqatında başlanğıc depo ilə Total-Sum Distance 55.145,51 olduğu halda optimallaşdırılmış depoda 54.533,97-yə; Min-Max Distance isə 21.130,08-dən 20.624,04-ə enmişdir. Mənbə eyni müqayisədə Workload Balance qiymətinin 0,98-dən 0,99-a və Robustness qiymətinin 0,88-dən 0,90-a yüksəldiyini; Cluster Separability-nin 0,24-dən 0,21-ə endiyini və işləmə vaxtının 7,71 saniyədən 7,87 saniyəyə artdığını bildirir.

Daha sonrakı altı verilənlər dəstli ablasiya tədqiqatında Full MADO, att48, eil76, gr229, rat575, dsj1000 və pcb1173 üzərində Geometric, Midpoint, S-shaped, Node-only MADO və Route-only MADO yanaşmaları ilə müqayisə edilmişdir. Mənbə Full MADO-nun altı nümunənin hamısında ən aşağı və ya bərabər ən aşağı Total-Sum Distance; beşində isə ən aşağı və ya bərabər ən aşağı Min-Max Distance əldə etdiyini bildirir. dsj1000 və pcb1173-də ən yaxşı statik başlanğıc strategiyasına nisbətən Total-Sum Distance azalması müvafiq olaraq təxminən %2,3 və %1,6 kimi hesabatlandırılmışdır.

Bununla belə, tədqiqat real paylama donanması, real trafik, nəqliyyat vasitəsinin tutumu, vaxt pəncərəsi və ya dinamik sifariş axını üzərində sahə doğrulaması deyil. Nəticələr TSPLIB əsaslı hesablama benchmark şərtlərində əldə edilmişdir. Mənbə həmçinin metod təsvirinin müxtəlif hissələrində çəkinin hesablanması, klaster üzvlüklərinin iterasiya zamanı sabit qalıb-qalmaması və Workload Balance metrikində yüksək/aşağı qiymətin necə şərh edilməsi barədə bir-biri ilə tam uyğun gəlməyən ifadələr ehtiva edir. Buna görə bu məqamlar dəqiqləşdirilmiş kimi təqdim edilməməlidir.

1. Səyyar Satıcı Problemi nədir?

Traveling Salesman Problem (TSP), satıcının və ya nəqliyyat vasitəsinin müəyyən şəhərlərin hər birini bir dəfə ziyarət edib başlanğıc nöqtəsinə qayıtmasını və ümumi yol xərcini mümkün qədər azaltmasını hədəfləyən klassik kombinator optimallaşdırma problemidir.

Bir marşrut:

\[ v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n \rightarrow v_1 \]

şəklində qapalı tur yaradır.

TSP-nin mühüm xüsusiyyəti həll fəzasının şəhərlərin sayı artdıqca çox sürətlə böyüməsidir. \(n\) şəhər üçün mümkün sıralamaların sayı faktorial artım göstərir. Buna görə düyünlərin sayı yüzlərlə və ya minlərlə olduqda bütün marşrutları bir-bir sınaqdan keçirmək praktik deyil.

2. MTSP nədir?

Multiple Traveling Salesman Problem (MTSP), TSP-nin birdən çox səyyar satıcı və ya əməliyyat vahidi olan genişləndirilmiş formasıdır. Bir şəxsin bütün nöqtələri ziyarət etməsi əvəzinə tapşırıqlar bir neçə satıcı arasında bölüşdürülür.

Burada yalnız ümumi məsafənin qısa olması kifayət etməyə bilər. Məsələn, dörd nəqliyyat vasitəsindən üçü qısa marşrutlarda işləyərkən dördüncü vasitə bütün uzaq nöqtələri daşımalı olarsa, ümumi yol məqbul olsa belə tapşırıq bölgüsü əməliyyat baxımından balanssız ola bilər.

3. SD-MTSP nədir?

Single-Depot Multiple Traveling Salesman Problem (SD-MTSP), bütün səyyar satıcıların eyni ortaq depodan başladığı, özlərinə təyin edilmiş müştəri düyünlərini ziyarət etdiyi və yenidən eyni depoya qayıtdığı MTSP növüdür.

Beləliklə, iki qərar bir-biri ilə əlaqəlidir:

• Hansı müştərinin hansı satıcıya təyin ediləcəyi,
• ortaq deponun harada yerləşəcəyi.

Depo mövqeyi dəyişdikdə hər satıcının marşrutunun başlanğıc və son bağlantıları da dəyişir. Beləliklə, ümumi məsafə və ən uzun marşrut birlikdə dəyişə bilər.

4. Depo niyə yalnız həndəsi mərkəzdə yerləşdirilmir?

Müştəri nöqtələrinin həndəsi mərkəzini götürmək sadə və sürətlidir; lakin həndəsi mərkəz müştəri klasterlərinin neçə düyün ehtiva etdiyini, klasterlərin nə qədər yayıldığını və ya real TSP marşrutlarının nə qədər uzun olduğunu birbaşa nəzərə almır.

Məsələn, iki klasterin mərkəzləri depodan eyni məsafədə olsa belə, bir klasterdə 20, digərində 100 müştəri ola bilər. Eyni şəkildə, eyni sayda müştərisi olan iki klasterdən biri dar ərazidə, digəri isə geniş coğrafiyada yayılmış ola bilər.

MADO-nun əsas motivasiyası bu fərqləri depo yeniləməsinə çəki kimi daxil etməkdir.

5. Klasterləşdirmə niyə istifadə olunur?

Klasterləşdirmə böyük SD-MTSP problemini daha kiçik alt problemlərə bölmək üçün istifadə olunur. Hər klaster bir səyyar satıcıya təyin edilir və klaster daxilindəki marşrut ayrıca TSP kimi həll edilir.

Mənbə statik və bərabər ölçülü bölünmə üçün \(n=k\,m\) fərziyyəsi altında tamölçülü problemin nəzəri faktorial quruluşunu:

\[ O(n!) \]

əvəzinə təxminən:

\[ O(k\cdot m!) \]

şəklində nəzərdən keçirir.

Burada:

• \(n\): ümumi düyün sayı,
• \(k\): klaster və ya satıcı sayı,
• \(m=n/k\): hər klasterə düşən orta düyün sayıdır.

Bu ifadə böyük problemin kiçik TSP-lərə bölünməsinin nəzəri motivasiyasını açıqlayır. Lakin tədqiqatdakı real TSP alt problemləri OR-Tools ilə həll edilir; buna görə \(O(m!)\) ifadəsi istifadə olunan OR-Tools evristikasının real işləmə vaxtı mürəkkəbliyi kimi şərh edilməməlidir.

6. Tədqiqatda müqayisə edilən klasterləşdirmə alqoritmləri

MADO Depo Mövqeyini Necə Yeniləyir?

MADO ortaq depodan hər klasterin mərkəzinə yönələn vektorları klasterin tapşırıq ölçüsünü və məkan/marşrut yükünü təmsil edən çəkilərlə birləşdirərək depo hərəkəti istiqaməti yaradır; lakin mənbədə bu ikinci çəki erkən metod bölməsində qabarıq örtük, daha sonrakı Route-Feedback MADO axınında isə cari TSP marşrut uzunluğu kimi müəyyən edildiyi üçün bu iki təsvirin eyni riyazi alqoritm olduğu fərz edilməməlidir.

7. İlk depo necə seçilir?

Mənbədə əvvəlcə bütün müştəri düyünlərinin həndəsi centroid-i hesablanır. Bu nöqtə nəzəri depo adlandırılır.

Lakin real depo mövqeyinin problemdəki uyğun nümunə düyünlərindən biri olması istəndiyi üçün nəzəri centroid-ə ən yaxın nümunə nöqtəsi seçilir və ilk real depo mövqeyi kimi istifadə olunur.

8. Tənlik (1): Erkən MADO çəkili istiqamət vektoru

Mənbənin metod bölməsindəki Tənlik (1):

\[ V= \frac{N(C_1)}{N}\frac{L_1}{L}V_1+ \frac{N(C_2)}{N}\frac{L_2}{L}V_2+ \cdots+ \frac{N(C_n)}{N}\frac{L_n}{L}V_n \tag{1} \]

Burada:

• \(V\): deponun ümumi vəziyyət/mövqe dəyişmə vektoru,
• \(N\): ümumi müştəri düyünlərinin sayı,
• \(N(C_i)\): \(i\)-ci klasterdəki müştəri düyünlərinin sayı,
• \(L_i\): bu erkən tərifdə \(i\)-ci klasterin qabarıq örtüyü,
• \(L\): bütün klasterlərin qabarıq örtüklərinin cəmi,
• \(V_i\): cari depodan \(i\)-ci klasterin mərkəzinə yönələn vektordur.

\(N(C_i)/N\) və \(L_i/L\) ölçüsüz nisbətlərdir. Bu iki nisbət vurulduqda yenə ölçüsüz çəki alınır. Bu çəki \(V_i\) mövqe vektoru ilə vurulduğuna görə nəticə \(V\) mövqe koordinatları ilə eyni ölçüyə malik olur.

Düyün nisbəti böyük olduqda çoxlu tapşırığa malik klasterin depo üzərində təsiri artır. Qabarıq örtük nisbəti böyük olduqda məkan baxımından daha geniş yayılmış klasterin təsiri artır.

Mənbə real TSP marşrut uzunluğunun bu erkən formulda istifadə edilməməsini xüsusilə onunla əsaslandırır ki, marşrut uzunluğu artıq depo mövqeyindən asılıdır və bu, yeniləmə zamanı dövri asılılığı artıra bilər.

9. Tənlik (2): Yeni depo

\[ Updated\_depot = Last\_depot + V \tag{2} \]

Bu tənlik çəkili istiqamət vektorunun cari depo koordinatına əlavə edilməsini ifadə edir. \(V\) sıfıra yaxınlaşdıqca təklif olunan depo hərəkəti kiçilir.

10. Tənlik (3): Erkən dayandırma tərifi

\[ Updated\_depot == Last\_depot \tag{3} \]

Mənbənin erkən dörd addımlı təsvirində yeni depo əvvəlki depo ilə eyni nümunə düyününə proyeksiya olunarsa, alqoritm dayandırılır.

Lakin sonrakı Algorithm 1 daha geniş dayandırma məntiqindən istifadə edir: depo dəyişmirsə, addım ölçüsü çox kiçilibsə, dövr və ya təkrarlanan vəziyyət aşkarlanıbsa, yaxud maksimum iterasiya sayına çatılıbsa alqoritm dayanır.

11. Mənbənin sonrakı Route-Feedback MADO tərifi

Məqalənin sonrakı səkkiz mərhələli axını və Algorithm 1 yeniləmə mexanizmini fərqli şəkildə təsvir edir. Burada klasterlər bir dəfə yaradılır və depo optimallaşdırılması boyunca sabit saxlanılır. Hər iterasiyada çəkilər:

• klaster düyünlərinin sayı \(n_i\),
• cari depoda hesablanan TSP marşrut uzunluğu \(L_i^{(t)}\)

istifadə edilməklə yaradılır.

Mənbə eyni bölmədə namizəd depo yeniləməsini:

\[ p^{(t+1)} = p^{(t)} + s_t \frac{D^{(t)}}{\|D^{(t)}\|_2+\varepsilon} \]

şəklində verir.

Burada:

• \(p^{(t)}\): \(t\)-ci iterasiyadakı depo koordinatı,
• \(D^{(t)}\): sintez edilmiş depo yeniləmə istiqaməti,
• \(\|D^{(t)}\|_2\): istiqamət vektorunun Evklid norması,
• \(s_t\): adaptiv effektiv addım ölçüsü,
• \(\varepsilon\): sıfıra bölünmə və ya çox kiçik norma probleminə qarşı istifadə olunan tolerantlıq həddidir.

Vektorun normasına bölünməsi istiqamət məlumatını böyük ölçüdə normallaşdırır; real hərəkət böyüklüyünü \(s_t\) müəyyən edir.

Lakin mənbə \(T_{max}\), \(\varepsilon\) və başlanğıc addımı \(\eta_0\) üçün ədədi qiymət vermir. Namizədin qəbulunda “əvvəlcədən müəyyən edilmiş lexicographic objective” istifadə edildiyi bildirilir, amma bu leksikoqrafik qəbul qaydasının dəqiq riyazi prioritet sırası ayrıca tənlik kimi hesabatlandırılmır.

12. İki metod təsviri arasındakı fərq niyə vacibdir?

Qabarıq örtük yalnız klasterin həndəsi yayılmasından asılıdır və depo hərəkət etdikcə birbaşa dəyişmir. TSP marşrut uzunluğu isə cari depo mövqeyindən asılıdır və hər depo dəyişikliyindən sonra yenidən hesablana bilər.

Beləliklə:

Düyün sayı + qabarıq örtük

ilə:

Düyün sayı + cari TSP marşrut uzunluğu

eyni optimallaşdırma qaydası deyil.

Mənbə Table 6 ablasiyasında “Node-only”, “Route-only” və “Full MADO” ifadələrindən istifadə etdiyi və müzakirədə route-length terminini real routing burden məlumatını təmin edən hissə kimi açıqladığı üçün bu sonrakı təcrübələr route-feedback təsvirinə aiddir. Buna baxmayaraq, dərc edilmiş erkən Tənlik (1) qorunmalı və nəzərdən qaçırılmamalıdır.

13. Klasterlər yenidən yaradılırmı?

Mənbə burada da iki fərqli təsvir verir. Erkən dörd addımlı bölmə yeni nəzəri depo müəyyən edildikdən sonra “cluster the dataset again” ifadəsindən istifadə edir. Buna qarşılıq, sonrakı Şəkil 2 izahı və Algorithm 1 klasterləşdirmənin bir dəfə aparıldığını və klaster üzvlüklərinin depo optimallaşdırılması boyunca sabit qaldığını açıq şəkildə bildirir.

Buna görə Verianla mənbənin bu iki təsvirindən birini səssizcə silərək alqoritmi yenidən müəyyən etmir. Təkrar istehsal edilə bilən tətbiqdə hansı variantın əsas götürüləcəyinin ayrıca dəqiqləşdirilməsi lazımdır.

14. Dövrün qarşısının alınması və dayandırma

Depo namizədi davamlı olaraq uyğun müştəri düyünlərinə proyeksiya edildikdə alqoritm iki və ya daha çox düyün arasında gedib-gələ bilər. Mənbə bunun qarşısını almaq üçün:

• ziyarət edilmiş depo vəziyyətlərinin hash vasitəsilə qeydə alınması,
• təkrarlanan vəziyyətin aşkarlanması,
• iki-vəziyyətli davamlı dövrün aşkarlanması,
• projection stall aşkarlanması,
• namizəd yaxşılaşma verməzsə addımın kiçildilməsi/rejection damping,
• minimum displacement,
• maksimum iterasiya həddi

kimi təhlükəsizlik mexanizmlərini müəyyən edir.

Müəlliflər bu mexanizmlərin alqoritmin praktikada sonlu sayda iterasiyada dayanmasını təmin etdiyini bildirirlər. Lakin mənbə açıq şəkildə qlobal optimuma yaxınlaşma zəmanəti vermir.

15. Böl-və-idarə et mürəkkəbliyi

Mənbənin tam MADO çərçivəsi üçün verdiyi ümumi mürəkkəblik ifadəsi:

\[ O\left( nkI_c+ T\left(n+k\,f(m)\right) \right) \]

şəklindədir.

Burada:

• \(n\): ümumi düyün sayı,
• \(k\): klaster sayı,
• \(I_c\): klasterləşdirmə metodunun daxili iterasiya sayı,
• \(T\): MADO depo yeniləmə iterasiyalarının sayı,
• \(m=n/k\): hər klasterə düşən orta düyün sayı,
• \(f(m)\): \(m\) düyünlü bir TSP alt problemini həll etməyin xərcidir.

Mənbə \(T\)-nin praktikada kiçik sabit olaraq qaldığını fərz edərək depo optimallaşdırılmasının yüksək dərəcəli əlavə yük yaratmadığını müdafiə edir. Bununla belə, \(f(m)\)-in istifadə olunan OR-Tools parametrlərindən və həll strategiyasından asılı olduğu unudulmamalıdır.

Workload Balance Qiyməti Necə Şərh Edilməlidir?

Mənbənin dərc olunmuş forması bu məsələdə daxili baxımdan ardıcıl deyil: metod mətni Tənlik (7) üçün daha kiçik qiyməti daha yaxşı balans kimi qəbul etdiyi halda, nəticələr bölməsi və cədvəllər daha yüksək Workload Balance qiymətini daha yaxşı balans kimi şərh edir; buna görə müəyyən qiymətin istiqamətini mənbəni düzəldirmiş kimi qəti müəyyən etmək əvəzinə formul, cədvəl nəticələri və bu hesabat uyğunsuzluğu birlikdə nəzərdən keçirilməlidir.

16. Tənlik (4): Bir klasterin qapalı TSP marşrut uzunluğu

\[ D_k= \sum_{i=1}^{n-1} d(v_i,v_{i+1}) + d(v_n,v_1) \tag{4} \]

\(D_k\), \(k\)-cı klasterə təyin edilmiş satıcının qapalı tur uzunluğudur. \(d(v_i,v_{i+1})\) ardıcıl iki düyün arasındakı məsafədir. Son termin son düyündən başlanğıc düyününə qayıdışı əlavə etməklə marşrutu bağlayır.

17. Tənlik (5): Min-Max Distance

\[ D_{\mathrm{Min\_Max}} = \max_{k\in\{1,\ldots,M\}} (D_k) \tag{5} \]

Bu metrik bütün satıcı marşrutları içərisindəki ən uzun marşrutu seçir. Məqsəd bu maksimum qiyməti mümkün qədər azaltmaqdır.

Məsələn, üç marşrut 100, 105 və 250 vahiddirsə, Min-Max Distance 250-dir. Ümumi yol məqbul olsa belə, bir satıcının üzərinə 250 vahidlik həddindən artıq yük düşə bilər. Buna görə Min-Max metrikası ən ağır yüklənmiş vahidə nəzarət etmək baxımından vacibdir.

18. Tənlik (6): Total-Sum Distance

\[ D_{\mathrm{Sum}} = \sum_{k=1}^{M}D_k \tag{6} \]

Total-Sum bütün satıcıların qət etdiyi marşrut uzunluqlarını toplayır. Daha kiçik qiymət ümumi əməliyyat məsafəsinin daha aşağı olduğunu göstərir.

Min-Max və Total-Sum eyni məqsəd deyil. Bir həll ümumi məsafəni bir qədər artırarkən ən uzun marşrutu ciddi şəkildə azalda bilər. MADO-nun çoxməqsədli balans problemi bu gərginlikdən yaranır.

19. Tənlik (7) və (8): Workload Balance

Mənbədə:

\[ balance= \frac{ \frac{1}{M} \sum_{k=1}^{M}(D_k-\bar{D})^2 }{ \max\left((D_k-\bar{D})^2\right) } \tag{7} \]

və:

\[ \bar{D} = \frac{1}{M} \sum_{k=1}^{M}D_k \tag{8} \]

verilmişdir.

\(\bar D\), bütün marşrut uzunluqlarının orta qiymətidir. Surət marşrut uzunluqlarının ortadan kvadratik yayınmalarının orta qiymətidir. Məxrəc isə kvadratik yayınmaların ən böyüyüdür.

Həm surət, həm də məxrəc məsafənin kvadratı vahidindədir; buna görə nisbət ölçüsüzdür.

Lakin bu normallaşdırma mühüm riyazi nəticə yaradır: bütün yayınmalar eyni əmsalla kiçildilir və ya böyüdülürsə, surət və məxrəc eyni əmsalın kvadratı ilə dəyişir və nisbət eyni qala bilər. Buna görə Tənlik (7) marşrut fərqlərinin mütləq böyüklüyünü təkbaşına ölçən klassik dispersiya və ya standart sapma deyil.

Tam bərabər marşrutlarda bütün \(D_k-\bar D\) qiymətləri sıfır olduğuna görə dərc edilmiş formula nəzəri olaraq \(0/0\) vəziyyətinə gəlir. Mənbə bu sərhəd vəziyyəti üçün ayrıca tərif vermir.

Metodun izahı “kiçik qiymət = daha balanslı” dediyi halda, Figure 3 izahı “yüksək qiymət = daha balanslı” deyir və Table 5-də 0,98 → 0,99 dəyişməsi yaxşılaşma kimi şərh olunur. Buna görə nəticə cədvəllərindəki Workload Balance qiymətləri mənbə müəlliflərinin nəticələr bölməsindəki şərh istiqaməti ilə ötürülmüş, lakin formula ilə mətn arasındakı ziddiyyət açıq saxlanılmışdır.

20. Tənlik (9) və (10): Silhouette / Cluster Separability

Mənbə ümumi silhouette skorunu:

\[ S_{\mathrm{global}} = \frac{1}{M} \sum_{k=1}^{M}S(k) \tag{9} \]

və bir nöqtə üçün silhouette qiymətini:

\[ S(k) = \frac{b(k)-a(k)} {\max\{a(k),b(k)\}} \tag{10} \]

şəklində verir.

\(a(k)\), nöqtənin öz klasterindəki digər nöqtələrə orta məsafəsidir. Klasterdaxili nöqtələr bir-birinə yaxınsa \(a(k)\) kiçilir.

\(b(k)\), nöqtənin digər klasterlərin hər birinə olan orta məsafələri arasındakı ən kiçik qiymətdir. Digər klasterlər yaxşı ayrılıbsa \(b(k)\) daha böyük ola bilər.

Silhouette qiyməti −1 ilə +1 arasındadır:

• +1-ə yaxınlaşmaq: daha kompakt və daha yaxşı ayrılmış klaster,
• 0 ətrafı: klaster sərhədində və ya üst-üstə düşməyə yaxın struktur,
• mənfi qiymət: nöqtənin başqa klasterə daha yaxın ola biləcəyini düşündürən struktur.

Mənbədə dsj1000 verilənlər dəstinin aydın klasterləşmiş məkan quruluşuna görə ən yüksək separability qiymətlərini göstərdiyi bildirilir.

21. Tənlik (11) və (12): Robustness

Mənbə stabillik ölçüsünü:

\[ CV = 1- \frac{ \sqrt{ \frac{1}{T} \sum_{t=1}^{T} \left( D_{\mathrm{Min\_Sum}}^{t} - \overline{D}_{\mathrm{Min\_Sum}} \right)^2 } }{ \overline{D}_{\mathrm{Min\_Sum}} } \tag{11} \]

və orta qiyməti:

\[ \overline{D}_{\mathrm{Min\_Sum}} = \frac{1}{T} \sum_{t=1}^{T} D_{\mathrm{Min\_Sum}}^{t} \tag{12} \]

kimi müəyyən edir.

Kəsrin daxilindəki quruluş standart sapmanın orta qiymətə nisbətinə bənzəyir. Mənbə bunun əvvəlinə \(1-\) əlavə etdiyi üçün dəyişkənlik azaldıqca skor 1-ə yaxınlaşır. Beləliklə, burada “CV” adı istifadə olunsa da dərc edilmiş ölçü klassik coefficient of variation-un özü deyil, 1 çıxılmış normallaşdırılmış dəyişkənlik formasında stabillik skorudur.

Mənbə nəticələr bölməsində bütün verilənlər dəstlərində orta Robustness qiymətinin təxminən 0,81 olduğunu bildirir.

Lakin təkrarlanan təcrübələrin sayı \(T\)-nin dəqiq ədədi qiyməti və istifadə olunan random seed mənbənin metod bölməsində açıq şəkildə hesabatlandırılmayıb.

22. Tənlik (13): İşləmə vaxtı

\[ T_{\mathrm{abs}} = t_{\mathrm{end}} - t_{\mathrm{start}} \tag{13} \]

Bu metrik alqoritmin başlanmasından yekun həll çıxışına qədər keçən divar saatı vaxtıdır. Vahidi saniyədir.

Mənbə düyünlərin sayı artdıqca işləmə vaxtının ümumilikdə yüksəldiyini və təcrübə qrafikində təxminən xətti meyl müşahidə edildiyini bildirir. Bu müşahidə nəzəri mürəkkəbliyin riyazi sübutu deyil; hesabatlandırılmış benchmark şərtlərindəki empirik işləmə vaxtı meylidir.

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

23. Verilənlər dəstləri

İlk əsas müqayisədə beş TSPLIB benchmark nümunəsindən istifadə edilmişdir:

pr299 xüsusilə vizual hal tədqiqatı üçün seçilmişdir. Müəlliflər bunun orta miqyaslı olması, məkan quruluşunun depo mövqeyinin təsirini vizuallaşdırmağa uyğun olması və ümumi məsafə ilə iş yükü balansı arasındakı güzəşti göstərməsi səbəbilə seçildiyini bildirirlər.

24. Proqram təminatı infrastrukturu

Təcrübələr Python 3.10 ilə həyata keçirilmişdir.

Klasterləşdirmə alqoritmləri:

scikit-learn v1.3.0

ilə; TSP alt problemləri:

OR-Tools v9.10

ilə həll edilmişdir.

Mənbənin nəticələr bölməsində 2-opt lokal optimallaşdırma alqoritmindən də bəhs edilir. Lakin 2-opt-un metod zəncirində dəqiq çağırılma nöqtəsi, iterasiya limiti və ya axtarış parametrləri ayrıca hesabatlandırılmayıb.

Mənbə istifadə olunan CPU/GPU modelini, əməliyyat sistemini, RAM miqdarını və random seed məlumatını bildirmir. Bu vəziyyət işləmə vaxtı nəticələrinin başqa sistemlərdə eynilə təkrar istehsalını məhdudlaşdırır.

25. Səkkiz mərhələli əsas həll axını

1. Giriş: TSPLIB düyün koordinatları, məsafə məlumatı və satıcı/klaster sayı \(k\) yüklənir.
2. Klasterləşdirmə: Düyünlər seçilmiş alqoritmlə \(k\) klasterə ayrılır.
3. İlk depo: Bütün düyünlərin həndəsi centroid-i tapılır və ən yaxın uyğun düyünə proyeksiya edilir.
4. İlk TSP həlli: Hər klasterin başlanğıc və son nöqtəsi ortaq depo olacaq şəkildə marşrut həll edilir.
5. MADO yeniləməsi: Dinamik çəkilərlə depo yeniləmə istiqaməti yaradılır və namizəd depo hesablanır.
6. Yenidən qiymətləndirmə: Namizəd depo üçün bütün klaster marşrutları yenidən həll edilir; Total-Sum, Min-Max və marşrut paylanması qiymətləndirilir.
7. Performansın qiymətləndirilməsi: Altı metrika hesablanır.
8. Çıxış: Best-so-far depo, marşrutlar və performans ölçüləri qaytarılır.

26. İlk beş verilənlər dəstində Total-Sum nəticələri

Bisecting K-Means xüsusilə eil76, pr299 və dsj1000-də Total-Sum baxımından ən aşağı nəticəni vermişdir. Bununla belə, att48 və gr229-da fərqli alqoritmlərin daha yaxşı olması klasterləşdirmə metodunun verilənlərin paylanmasından asılı olduğunu göstərir.

27. İlk beş verilənlər dəstində Min-Max nəticələri

Bu cədvəl ilə Total-Sum cədvəlinin qalibləri eyni deyil. Bu, ümumi əməliyyat məsafəsini azaltmaqla bir satıcının üzərinə düşən ən uzun marşrutu azaltmağın fərqli məqsədlər olduğunu birbaşa göstərir.

28. Workload Balance, separability və robustness qrafiklərinin əsas mesajı

Mənbə Figure 3-də Workload Balance qiymətlərinin əksəriyyətinin yüksək səviyyədə olduğunu və bütün alqoritm/verilənlər dəsti kombinasiyalarında orta qiymətin təxminən 0,95 olduğunu bildirir. Daha əvvəl izah edilən formula-istiqamət ziddiyyətinə görə bu qrafikin şərhi nəticələr bölməsində istifadə olunan “yüksək qiymət daha yaxşıdır” istiqamətində ötürülür.

Figure 4-də Cluster Separability verilənlər dəstindən güclü şəkildə asılıdır. dsj1000 aydın klasterləşmiş məkan quruluşuna görə ən yüksək silhouette qiymətlərini göstərir.

Figure 5 üçün mənbə orta Robustness qiymətinin təxminən 0,81 olduğunu bildirir. Lakin bəzi alqoritmlərin müəyyən verilənlər dəstlərindəki skorları nəzərəçarpacaq dərəcədə aşağı düşür; buna görə orta qiymət hər bir alqoritmin eyni stabilliyi göstərdiyi anlamına gəlmir.

29. Radar qrafiki və heatmap necə şərh edilməlidir?

Mənbə altı metrikanı birlikdə göstərmək üçün radar qrafiklərindən və orta sıralamalardan ibarət heatmap-dən istifadə etmişdir.

Radar qrafikinin izahında “K-Means ən böyük poliqon sahəsinə malikdir” ifadəsindən dərhal sonra Agglomerative üçün də “ən böyük poliqon sahəsinə malikdir” deyilir. Eyni bölmə Spectral üçün həm müsbət, həm də “worst comprehensive performance” istiqamətində bir-birinə uyğun gəlməyən ifadələr ehtiva edir.

Buna görə Verianla radar qrafikindən vahid universal “ən yaxşı alqoritm” nəticəsi çıxarmır.

Mənbənin heatmap müzakirəsinin daha ehtiyatlı nəticəsi qoruna bilər: heç bir klasterləşdirmə alqoritmi bütün verilənlər dəstləri və bütün ölçülər üzrə mütləq üstün deyil. Alqoritm seçimi verilənlərin paylanmasından və hansı metrikanın prioritetləşdirilməsindən asılıdır.

30. pr299 hal tədqiqatı

pr299 K-Means ilə üç klasterə ayrılmışdır. Mənbənin Şəkil 9–14 ardıcıllığı:

1. orijinal düyün paylanmasını,
2. başlanğıc deponun seçilməsini,
3. üç klasterin yaranmasını,
4. ilk TSP marşrutlarını,
5. MADO ilə depo mövqeyinin köçürülməsini,
6. yeni depodan həll edilən son marşrutları

göstərir.

Mənbə bu qrafiklərin bütün koordinatlarını və marşrut düyünlərinin sırasını mətn/cədvəl şəklində vermədiyi üçün Verianla daxilində saxta pr299 marşrut xəritəsi yenidən çəkilməyib.

Bu hal tədqiqatı mühüm çoxməqsədli güzəşti göstərir: marşrut uzunluğu və mənbədə istifadə olunan balans/stabillik göstəriciləri yaxşılaşarkən cluster separability bir qədər azalmış və işləmə vaxtı bir qədər artmışdır.

31. Table 3 ilə pr299 hal rəqəmləri niyə tam eyni deyil?

Table 3-də K-Means/pr299 üçün Total-Sum Distance 53.848,32 verildiyi halda, Table 5 hal tədqiqatının optimallaşdırılmış depo nəticəsi 54.533,97-dir. Mənbə bu iki qiymətin niyə fərqli olduğunu açıq şəkildə izah etmir. K-Means başlanğıc şərtlərinin və ya təcrübə prosedurunun fərqli təkrarları mümkün izah ola bilər, lakin mənbə bunu təsdiqləmədiyi üçün Verianla belə bir səbəbi fakt kimi aid etmir.

32. Full MADO ablasiyasının məqsədi

Ablasiya tədqiqatı iki çəki komponentinin rolunu ayırmağı hədəfləyir:

• Node-only MADO: yalnız klaster ölçüsü,
• Route-only MADO: yalnız marşrut yükü,
• Full MADO: düyün sayı və marşrut yükü birlikdə.

Müəlliflərin şərhinə görə marşrut uzunluğu termini real routing burden məlumatını, düyün sayı termini isə tapşırıq miqyasını və tənzimləyici/balanslaşdırıcı təsiri təmin edir.

33. Table 6-dakı tam ablasiya nəticələri

Bu cədvəlin mühüm nəticəsi Full MADO-nun hər ölçüdə və hər verilənlər dəstində təkbaşına mütləq üstün olmamasıdır. Məsələn, rat575-də Node-only MADO daha aşağı Total-Sum Distance əldə etdiyi halda, Full MADO eyni və ya daha yaxşı Min-Max performansı və fərqli balans kombinasiyası təmin edir. Oxşar şəkildə bəzi statik metodlar işləmə vaxtında daha sürətlidir.

Beləliklə, MADO-nun töhfəsi yalnız “hər sütunda ən kiçik rəqəm” deyil; o, marşrut cəmi, ən uzun marşrut və mənbədə istifadə olunan balans göstəricisi arasında daha uyğun kompromis axtarır.

34. Table 3/4 ilə Table 6 məsafə miqyasları niyə birbaşa müqayisə edilməməlidir?

Mənbənin Table 3 və Table 4 qiymətləri ilə Table 6 qiymətləri eyni adlı verilənlər dəstlərində belə bəzi hallarda çox fərqli ədədi miqyaslara malikdir. Məsələn, gr229 Total-Sum qiymətləri Table 3-də təxminən 1.800–2.300 aralığında olduğu halda Table 6-da təxminən 164.000–192.000 səviyyəsindədir.

Mənbə bu fərq üçün məsafə çevrilməsi, fərqli TSPLIB edge-weight tətbiqi və ya başqa preprocessing izahı vermir. Buna görə Verianla bu cədvəlləri vahid ümumi ədədi miqyasda birləşdirmir.

35. Ablasiyanın elmi mesajı

Müəlliflər Node-only ilə Full MADO-nu müqayisə etdikdə marşrut uzunluğu termininin yalnız düyün sayından görünməyən real routing-cost məlumatını təmin etdiyini müdafiə edirlər.

Route-only ilə Full MADO müqayisəsində isə düyün sayı termininin miqyas kompensasiyası və tənzimləyici təsir təmin etdiyi irəli sürülür.

gr229 nümunəsində Route-only Workload Balance 0,861 olduğu halda Full MADO 0,912-yə çatmışdır. Mənbə bunu məkan baxımından geniş bir klasterin deponu həddindən artıq özünə çəkməsini düyün sayı termininin məhdudlaşdırması ilə əlaqələndirir.

36. Tədqiqatın dəstəklədiyi nəticələr

• MADO sınaqdan keçirilmiş TSPLIB benchmark nümunələrində ortaq depo mövqeyini dəyişdirərək marşrut nəticələrinə təsir göstərə bilir.
• pr299 hal tədqiqatında optimallaşdırılmış depo daha aşağı Total-Sum və Min-Max Distance vermişdir.
• Klasterləşdirmə alqoritminin seçimi nəticələri əhəmiyyətli dərəcədə dəyişir; heç bir klasterləşdirmə metodu bütün verilənlər dəstlərində üstün deyil.
• Bisecting K-Means ilk beş verilənlər dəstinin bir neçəsində Total-Sum baxımından güclü nəticə vermişdir.
• Full MADO Table 6-dakı altı benchmark-ın hamısında minimum və ya bərabər minimum Total-Sum nəticəsi əldə etmişdir.
• Full MADO xüsusilə dsj1000 və pcb1173-də statik başlanğıc metodlarına nisbətən daha aşağı Total-Sum və Min-Max qiymətləri təmin etmişdir.
• Node-count və route-length komponentlərinin ablasiya nəticələri onların bir-birini tamamlayan rollar daşıdığı barədə müəllif şərhini dəstəkləyir.
• Klasterləşdirmə əsaslı böl-və-idarə et yanaşması böyük SD-MTSP-nin daha kiçik TSP alt problemlərinə ayrılmasını təmin edir.

37. Tədqiqatın birbaşa dəstəkləmədiyi nəticələr

• MADO-nun bütün SD-MTSP nümunələrində qlobal optimum tapdığı göstərilməyib.
• Real vaxt trafiki altında sahə doğrulaması aparılmayıb.
• Dinamik şəkildə əlavə edilən və ya silinən müştəri nöqtələri eksperimental olaraq qiymətləndirilməyib.
• Fərqli tutumlu nəqliyyat vasitələrindən ibarət heterogen donanma birbaşa sınaqdan keçirilməyib.
• Vaxt pəncərələri və nəqliyyat vasitəsi tutumu əsas benchmark modelinin məhdudiyyətləri arasında deyil.
• Real logistika şirkətinə aid xərc, yanacaq, sürücünün iş vaxtı və ya çatdırılma SLA məlumatları qiymətləndirilməyib.
• Qrafiklərdəki yüksək Robustness qiyməti real sahə qeyri-müəyyənliklərinə qarşı sübut edilmiş dayanıqlıq demək deyil.
• Empirik işləmə vaxtı qrafikinin təxminən xətti görünməsi alqoritmin bütün şərtlərdə xətti zaman mürəkkəbliyinə malik olduğunu sübut etmir.
• Table 6 nəticələri Table 3/4-ün ədədi miqyası ilə izah verilmədən birbaşa birləşdirilə bilməz.

38. Mənbənin öz gələcək tədqiqat təklifləri

Müəlliflər metodun daha mürəkkəb dinamik mühitlərdə inkişaf etdirilməli olduğunu bildirirlər. Təklif olunan istiqamətlər:

• real vaxt trafik dəyişikliklərinə cavab vermək üçün reinforcement learning və ya online optimization əlavə etmək,
• müştəri/tapşırıq nöqtələrinin dinamik şəkildə əlavə edilməsini və ya çıxarılmasını nəzərə almaq,
• heterogen səyyar satıcı/nəqliyyat vasitəsi tiplərini dəstəkləmək,
• nəqliyyat vasitəsinin tutumu kimi real əməliyyat məhdudiyyətlərini əlavə etmək,
• klasterləşdirmə ilə marşrut planlaşdırması arasındakı birgə optimallaşdırma mexanizmini inkişaf etdirmək

şəklindədir.

Bu gələcək tədqiqat təklifləri eyni zamanda mövcud məqalənin sahədə tətbiqolunma imkanlarına qoyduğu sərhədi göstərir. Metod birbaşa “mühəndislikdə tam doğrulanmış logistika sistemi” səviyyəsində deyil; müəlliflər də nəzəri tətbiqolunmadan engineering reliability səviyyəsinə keçid üçün əlavə inkişafın lazım olduğunu bildirirlər.

Mənbə və Metod Qeydi

Orijinal başlıq: A Clustering-Based Multi-Task Balancing Method for Depot Optimization in Single-Depot Multiple Traveling Salesman Problems

Müəlliflər: Chunlong Fu, Jiaxin Zou, Guofang Liu, Pingli Zheng, Kaiwen Xiao, Yang Deng, Hongxia He və Qi Jiang.

Məsul müəllif: Chunlong Fu.

Bərabər töhfə: Mənbədə bərabər töhfə bəyanatı yoxdur.

Qurum: Department of Computer Science, Sichuan University Jinjiang College, Meishan 620860, China.

Jurnal: Mathematics.

Nəşriyyat: MDPI.

Biblioqrafik qeyd: Mathematics 2026, 14(15), 2811.

DOI: 10.3390/math14152811.

Təqdim tarixi: 5 iyun 2026.

Reviziya tarixi: 18 iyul 2026.

Qəbul tarixi: 28 iyul 2026.

Nəşr tarixi: 5 avqust 2026.

Rəsmi keçid: DOI 10.3390/math14152811 vasitəsilə MDPI nəşr qeydi.

Mənbə növü: Resenziyalı elmi jurnalda dərc olunmuş orijinal tədqiqat məqaləsi; kombinator optimallaşdırma, klasterləşdirmə və marşrut planlaşdırmasına əsaslanan hesablama tədqiqatı.

Preprint statusu: Təqdim edilmiş mənbə dərc olunmuş jurnal versiyasıdır. PDF daxilində ayrıca preprint identifikatoru bildirilməyib.

Lisenziya: Creative Commons Attribution (CC BY).

Açar sözlər: SD-MTSP; clustering algorithm; task balancing; depot location optimization.

MSC: 05B05; 90B50.

Proqram təminatı: Python 3.10, scikit-learn v1.3.0 və OR-Tools v9.10.

Benchmark mənbəyi: TSPLIB.

İlk əsas verilənlər dəstləri: att48, eil76, gr229, pr299 və dsj1000.

Ablasiya verilənlər dəstləri: att48, eil76, gr229, rat575, dsj1000 və pcb1173.

Qiymətləndirmə metrikləri: Total-Sum Distance, Min-Max Distance, Workload Balance, Cluster Separability, Robustness və Running Time.

Maliyyələşdirmə: Opening Foundation of the State Key Laboratory of Cognitive Intelligence, Anhui iFLYTEK Co., Ltd., Grant No. COGOS-2024HE03; həmçinin Sichuan University Jinjiang College 2024 Young Teacher Research Fund Project, Grant No. QNJJ-2024-B08.

Verilənlərin əlçatanlığı: Müəlliflər tədqiqat verilənlərinin TSPLIB əsaslı olaraq açıq əlçatan olduğunu və Data Availability bölməsində GitCode giriş keçidi təqdim etdiklərini bildirmişlər.

Maraqlar toqquşması: Müəlliflər maraqlar toqquşması bildirməyiblər.

Süni intellektdən istifadə bəyanatı: Müəlliflər məqalənin hazırlanması zamanı ChatGPT-5.4-dən qrammatikanın yaxşılaşdırılması və dil redaktəsi məqsədilə istifadə etdiklərini; son məzmunu özlərinin nəzərdən keçirib redaktə etdiklərini və nəşr məzmununa görə məsuliyyəti üzərlərinə götürdüklərini bildirmişlər.

Müəllif töhfələri: Konseptuallaşdırma Qi Jiang; metod Jiaxin Zou, Chunlong Fu, Pingli Zheng və Kaiwen Xiao; proqram təminatı Guofang Liu və Hongxia He; doğrulama Jiaxin Zou, Chunlong Fu və Hongxia He; formal analiz Guofang Liu və Yang Deng; tədqiqat Chunlong Fu; resurslar Pingli Zheng və Qi Jiang; verilənlərin kurasiyası Jiaxin Zou, Pingli Zheng və Kaiwen Xiao; ilkin layihə Jiaxin Zou; nəzərdən keçirmə və redaktə Chunlong Fu; vizuallaşdırma Yang Deng; nəzarət Chunlong Fu və Guofang Liu tərəfindən həyata keçirilmişdir.

Mühüm metodoloji uyğunsuzluq 1 — çəki tərifi: Erkən Tənlik (1) düyün nisbəti ilə qabarıq örtük nisbətindən istifadə edir. Daha sonrakı Route-Feedback MADO axını, Algorithm 1 və Table 6 müzakirəsi düyün sayı ilə cari TSP marşrut uzunluğundan istifadə edir. Mənbə bu iki təsviri açıq reviziya əlaqəsi ilə bir-birinə bağlamır.

Mühüm metodoloji uyğunsuzluq 2 — klasterləşdirmə: Erkən dörd addımlı izah yenilənmiş depodan sonra yenidən klasterləşdirmədən bəhs etdiyi halda, Şəkil 2 və Algorithm 1 klaster üzvlüklərinin bir dəfə yaradılıb depo optimallaşdırılması boyunca sabit saxlanıldığını bildirir.

Mühüm metrik uyğunsuzluğu — Workload Balance: Tənlik (7)-dən əvvəlki izah daha kiçik qiymətlərin daha yaxşı balansı göstərdiyini bildirir. Nəticələr bölməsi, Şəkil 3 və Table 5–6 isə daha yüksək qiyməti daha yaxşı kimi şərh edir. Verianla bu ziddiyyəti səssizcə düzəltməyib.

Verilənlər dəstinin əhatə qeydi: Section 5.1 beş benchmark nümunəsini müəyyən edir; Table 6 isə pr299 əvəzinə rat575 və pcb1173-ü ehtiva edən altı nümunəli ayrıca müqayisədən istifadə edir.

Məsafə miqyası qeydi: Table 3/4 və Table 6-da eyni TSPLIB adlarını daşıyan bəzi verilənlər dəstlərinin məsafə böyüklükləri fərqli miqyaslardadır. Mənbə bunun üçün açıq çevrilmə və ya preprocessing izahı vermir; cədvəllər birbaşa vahid miqyaslı verilənlər dəsti kimi birləşdirilməyib.

pr299 rəqəm qeydi: Table 3-də K-Means/pr299 Total-Sum Distance 53.848,32 olduğu halda, hal tədqiqatının Table 5 optimallaşdırılmış depo nəticəsi 54.533,97-dir. Mənbə fərqin səbəbini açıq şəkildə izah etmir.

2-opt qeydi: Nəticələr bölməsində 2-opt lokal optimallaşdırmanın OR-Tools həllinə daxil edildiyi bildirilir; lakin metod bölməsində 2-opt-un ətraflı konfiqurasiyası verilməyib.

Təkrar istehsal oluna bilmə qeydi: Algorithm 1, \(T_{max}\), \(\varepsilon\) və başlanğıc addımı \(\eta_0\) parametrlərini giriş kimi müəyyən edir; mənbə bu parametrlərin istifadə edilmiş ədədi qiymətlərini bildirmir. Repeated-experiment sayı, random seed və hesablama avadanlığı da açıq şəkildə hesabatlandırılmayıb.

Yaxınlaşma sərhədi: Müəlliflər qlobal optimum zəmanəti vermirlər. State hashing, cycle detection, projection-stall nəzarəti və addım kiçiltmə mexanizmləri iterasiyanın praktikada sonlandırılmasını hədəfləyir.

Real dünya sərhədi: Tədqiqat TSPLIB benchmark doğrulamasıdır. Real logistika donanması, canlı trafik, nəqliyyat vasitəsinin tutumu, vaxt pəncərəsi, dinamik müştəri girişi və heterogen nəqliyyat vasitələri üzərində əməliyyat sahə doğrulaması aparılmayıb.