Koʻp vaznli adaptiv depo optimallashtirish (Multi-Weight Adaptive Depot Optimization, MADO), bitta depoli ko‘p sayyor sotuvchi masalasida mijoz tugunlarini klasterlarga ajratadigan, har bir klasterni bitta sayyor sotuvchiga biriktiradigan va umumiy depo joylashuvini marshrut samaradorligi hamda ish yukining muvozanatini birgalikda hisobga olgan holda iterativ tarzda o‘zgartiradigan optimallashtirish yondashuvidir. Tadqiqot TSPLIB benchmark ma’lumotlar to‘plamlarida sakkiz xil klasterlash algoritmini, OR-Tools asosidagi TSP yechimini, depo joylashuvini optimallashtirishni va Total-Sum Distance, Min-Max Distance, Workload Balance, Cluster Separability, Robustness hamda Running Time kabi oltita samaradorlik ko‘rsatkichini birlashtiradi.

Usulning asosiy g‘oyasi katta SD-MTSP ni bevosita yaxlit holda yechish o‘rniga, mijoz tugunlarini klasterlarga ajratib, uni kichikroq TSP quyi masalalariga bo‘lishdir. Keyin umumiy depo joylashuvi klasterlar o‘lchami va fazoviy/marshrut yukini ifodalovchi vaznlar yordamida yangilanadi. Har bir nomzod depo uchun klaster ichidagi TSP marshrutlari qayta yechiladi va yangi joylashuv marshrut uzunligi hamda muvozanat mezonlari bo‘yicha baholanadi.

Dastlabki besh ma’lumotlar to‘plami taqqoslovida att48, eil76, gr229, pr299 va dsj1000 ishlatilgan. Total-Sum Distance bo‘yicha att48 da BIRCH, gr229 da Fuzzy C-Means; eil76, pr299 va dsj1000 da esa Bisecting K-Means eng past qiymatlarni bergan. Bu natija bitta klasterlash algoritmi barcha ma’lumot taqsimotlarida ustun emasligini ko‘rsatadi.

pr299 holat tadqiqotida boshlang‘ich depo bilan Total-Sum Distance 55.145,51 bo‘lgan bo‘lsa, optimallashtirilgan depoda 54.533,97 ga; Min-Max Distance esa 21.130,08 dan 20.624,04 ga tushgan. Manba ayni taqqoslashda Workload Balance qiymati 0,98 dan 0,99 ga va Robustness qiymati 0,88 dan 0,90 ga oshganini; Cluster Separability 0,24 dan 0,21 ga kamayganini va ishlash vaqti 7,71 soniyadan 7,87 soniyaga ko‘payganini bildiradi.

Keyingi oltita ma’lumotlar to‘plamli ablatsiya tadqiqotida Full MADO att48, eil76, gr229, rat575, dsj1000 va pcb1173 da Geometric, Midpoint, S-shaped, Node-only MADO hamda Route-only MADO yondashuvlari bilan taqqoslangan. Manba Full MADO oltita misolning barchasida eng past yoki teng eng past Total-Sum Distance; beshtasida esa eng past yoki teng eng past Min-Max Distance olganini bildiradi. dsj1000 va pcb1173 da eng yaxshi statik boshlang‘ich strategiyaga nisbatan Total-Sum Distance kamayishi mos ravishda taxminan %2,3 va %1,6 deb qayd etilgan.

Shunga qaramay, tadqiqot haqiqiy taqsimot avtoparki, real trafik, transport vositasi sig‘imi, vaqt oynasi yoki dinamik buyurtma oqimida dala sharoitidagi tekshiruv emas. Natijalar TSPLIB asosidagi hisoblash benchmark sharoitlarida olingan. Manba shuningdek usul ta’rifining turli qismlarida vaznni hisoblash, klaster a’zoliklarining iteratsiya davomida o‘zgarmas qolishi yoki qolmasligi va Workload Balance metrikasidagi yuqori/past qiymatni talqin qilish bo‘yicha bir-biriga to‘liq mos kelmaydigan bayonotlarni o‘z ichiga oladi. Shu sababli bu nuqtalar aniqlashtirilgandek taqdim etilmasligi kerak.

1. Sayyor sotuvchi masalasi nima?

Traveling Salesman Problem (TSP), sotuvchi yoki transport vositasi berilgan shaharlarning har biriga bir martadan tashrif buyurib, boshlang‘ich nuqtaga qaytishini va umumiy yo‘l xarajatini imkon qadar kamaytirishni maqsad qilgan klassik kombinator optimallashtirish masalasidir.

Bir marshrut:

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

ko‘rinishida yopiq tur hosil qiladi.

TSP ning muhim xususiyati shundaki, yechim fazosi shaharlar soni bilan juda tez o‘sadi. \(n\) ta shahar uchun mumkin bo‘lgan tartiblar soni faktorial o‘sishni ko‘rsatadi. Shu sababli tugunlar soni yuzlab yoki minglab bo‘lganda barcha marshrutlarni bittalab sinab ko‘rish amaliy emas.

2. MTSP nima?

Multiple Traveling Salesman Problem (MTSP), TSP ning bir nechta sayyor sotuvchi yoki operatsion birlikka ega kengaytirilgan shaklidir. Bitta shaxs barcha nuqtalarga tashrif buyurishi o‘rniga vazifalar bir nechta sotuvchi o‘rtasida taqsimlanadi.

Bu yerda faqat umumiy masofaning qisqa bo‘lishi yetarli bo‘lmasligi mumkin. Masalan, to‘rtta transport vositasidan uchtasi qisqa marshrutlarda ishlayotganida to‘rtinchi vosita barcha uzoq nuqtalarga xizmat qilishi kerak bo‘lsa, umumiy yo‘l maqbul bo‘lsa ham vazifalar taqsimoti operatsion jihatdan nomuvozanatli bo‘lishi mumkin.

3. SD-MTSP nima?

Single-Depot Multiple Traveling Salesman Problem (SD-MTSP), barcha sayyor sotuvchilar bir xil umumiy depodan yo‘lga chiqadigan, o‘zlariga biriktirilgan mijoz tugunlariga tashrif buyuradigan va yana shu depoga qaytadigan MTSP turidir.

Shunday qilib, ikki qaror o‘zaro bog‘liq:

• Qaysi mijoz qaysi sotuvchiga biriktirilishi,
• umumiy depo qayerda joylashishi.

Depo joylashuvi o‘zgarganda har bir sotuvchining marshrutidagi boshlanish va tugash bog‘lanishlari ham o‘zgaradi. Natijada umumiy masofa va eng uzun marshrut birgalikda o‘zgarishi mumkin.

4. Nega depo faqat geometrik markazga joylashtirilmaydi?

Mijoz nuqtalarining geometrik markazini olish sodda va tez; biroq geometrik markaz mijoz klasterlarida nechta tugun borligini, klasterlar qanchalik yoyilganini yoki haqiqiy TSP marshrutlari qanchalik uzunligini bevosita hisobga olmaydi.

Masalan, ikki klaster markazi depodan teng masofada bo‘lsa ham, bir klasterda 20, boshqasida 100 mijoz bo‘lishi mumkin. Xuddi shuningdek, mijozlar soni bir xil bo‘lgan ikki klasterning biri tor hududda, ikkinchisi esa keng geografik maydonda tarqalgan bo‘lishi mumkin.

MADO ning asosiy motivatsiyasi ana shu farqlarni depo yangilanishiga vazn sifatida qo‘shishdir.

5. Nega klasterlash qo‘llanadi?

Klasterlash katta SD-MTSP masalasini kichikroq quyi masalalarga bo‘lish uchun qo‘llanadi. Har bir klaster bitta sayyor sotuvchiga biriktiriladi va klaster ichidagi marshrut alohida TSP sifatida yechiladi.

Manba statik va teng o‘lchamli bo‘linish uchun \(n=k\,m\) farazi ostida to‘liq ko‘lamli masalaning nazariy faktorial tuzilishini:

\[ O(n!) \]

o‘rniga taxminan:

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

ko‘rinishida qaraydi.

Bu yerda:

• \(n\): umumiy tugunlar soni,
• \(k\): klaster yoki sotuvchi soni,
• \(m=n/k\): har bir klasterga to‘g‘ri keladigan o‘rtacha tugunlar soni.

Bu ifoda katta masalani kichik TSP larga bo‘lishning nazariy motivatsiyasini tushuntiradi. Biroq tadqiqotdagi haqiqiy TSP quyi masalalari OR-Tools bilan yechiladi; shu sababli \(O(m!)\) ifodasi foydalanilgan OR-Tools evristikasining haqiqiy ishlash vaqti murakkabligi sifatida talqin qilinmasligi kerak.

6. Tadqiqotda taqqoslangan klasterlash algoritmlari

MADO depo joylashuvini qanday yangilaydi?

MADO umumiy depodan har bir klaster markaziga yo‘nalgan vektorlarni klasterning vazifa miqyosi va fazoviy/marshrut yukini ifodalovchi vaznlar bilan birlashtirib, depo siljishi yo‘nalishini hosil qiladi; biroq manbada bu ikkinchi vazn dastlabki usul bo‘limida qavariq qobiq, keyingi Route-Feedback MADO oqimida esa joriy TSP marshrut uzunligi sifatida ta’riflanganligi sababli, ikki ta’rif aynan bir matematik algoritm deb faraz qilinmasligi kerak.

7. Dastlabki depo qanday tanlanadi?

Manbada avval barcha mijoz tugunlarining geometrik centroid-i hisoblanadi. Bu nuqta nazariy depo deb ataladi.

Biroq haqiqiy depo joylashuvi masaladagi mos namuna tugunlaridan biri bo‘lishi talab etilgani uchun nazariy centroid-ga eng yaqin namuna nuqtasi tanlanadi va dastlabki haqiqiy depo joylashuvi sifatida ishlatiladi.

8. Tenglama (1): Dastlabki MADO vaznli yo‘nalish vektori

Manbaning usul bo‘limidagi Tenglama (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} \]

Bu yerda:

• \(V\): depodagi umumiy holat/joylashuv o‘zgarishi vektori,
• \(N\): mijoz tugunlarining umumiy soni,
• \(N(C_i)\): \(i\)-klasterdagi mijoz tugunlari soni,
• \(L_i\): ushbu dastlabki ta’rifda \(i\)-klasterning qavariq qobig‘i,
• \(L\): barcha klasterlar qavariq qobiqlarining yig‘indisi,
• \(V_i\): joriy depodan \(i\)-klaster markaziga yo‘nalgan vektordir.

\(N(C_i)/N\) va \(L_i/L\) o‘lchovsiz nisbatlardir. Bu ikki nisbat ko‘paytirilganda yana o‘lchovsiz vazn hosil bo‘ladi. Bu vazn \(V_i\) joylashuv vektori bilan ko‘paytirilgani sababli natija \(V\) joylashuv koordinatalari bilan bir xil o‘lchamga ega bo‘ladi.

Tugunlar nisbati katta bo‘lganda ko‘p vazifaga ega klasterning depoga ta’siri ortadi. Qavariq qobiq nisbati katta bo‘lganda fazoviy jihatdan kengroq yoyilgan klasterning ta’siri ortadi.

Manba haqiqiy TSP marshrut uzunligi ushbu dastlabki formulada ishlatilmasligini aynan marshrut uzunligi allaqachon depo joylashuviga bog‘liq ekani va bu yangilanish vaqtida siklik bog‘liqlikni kuchaytirishi mumkinligi bilan izohlaydi.

9. Tenglama (2): Yangi depo

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

Bu tenglama vaznli yo‘nalish vektorining joriy depo koordinatasiga qo‘shilishini ifodalaydi. \(V\) nolga yaqinlashgan sari taklif etilgan depo siljishi kichrayadi.

10. Tenglama (3): Dastlabki to‘xtatish ta’rifi

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

Manbaning dastlabki to‘rt bosqichli ta’rifida yangi depo avvalgi depo bilan bir xil namuna tuguniga proyeksiya qilinsa, algoritm to‘xtatiladi.

Biroq keyingi Algorithm 1 bundan kengroq to‘xtatish mantiqidan foydalanadi: depo o‘zgarmasa, qadam kattaligi juda kichiklashsa, sikl yoki takroriy holat aniqlansa yoxud maksimal iteratsiyalar soniga erishilsa, algoritm to‘xtaydi.

11. Manbaning keyingi Route-Feedback MADO ta’rifi

Maqolaning keyingi sakkiz bosqichli oqimi va Algorithm 1 yangilash mexanizmini boshqacha tasvirlaydi. Bu yerda klasterlar bir marta hosil qilinadi va depo optimallashtirish davomida o‘zgarmas saqlanadi. Har bir iteratsiyada vaznlar:

• klaster tugunlari soni \(n_i\),
• joriy depoda hisoblangan TSP marshrut uzunligi \(L_i^{(t)}\)

yordamida hosil qilinadi.

Manba ayni bo‘limda nomzod depo yangilanishini:

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

ko‘rinishida beradi.

Bu yerda:

• \(p^{(t)}\): \(t\)-iteratsiyadagi depo koordinatasi,
• \(D^{(t)}\): sintez qilingan depo yangilash yo‘nalishi,
• \(\|D^{(t)}\|_2\): yo‘nalish vektorining Yevklid normasi,
• \(s_t\): adaptiv samarali qadam kattaligi,
• \(\varepsilon\): nolga bo‘lish yoki juda kichik norma muammosi uchun ishlatiladigan tolerantlik hadidir.

Vektorni uning normasiga bo‘lish yo‘nalish ma’lumotini katta darajada normallashtiradi; haqiqiy siljish kattaligini \(s_t\) belgilaydi.

Biroq manba \(T_{max}\), \(\varepsilon\) va boshlang‘ich qadam \(\eta_0\) uchun sonli qiymat bermaydi. Nomzodni qabul qilishda “oldindan belgilangan lexicographic objective” ishlatilishi aytiladi, ammo bu leksikografik qabul qoidasining aniq matematik ustuvorlik tartibi alohida tenglama sifatida qayd etilmagan.

12. Ikki usul ta’rifi o‘rtasidagi farq nega muhim?

Qavariq qobiq faqat klasterning geometrik yoyilishiga bog‘liq va depo siljiganda bevosita o‘zgarmaydi. TSP marshrut uzunligi esa joriy depo joylashuviga bog‘liq bo‘lib, depo har bir o‘zgargandan so‘ng qayta hisoblanishi mumkin.

Shunday qilib:

Tugunlar soni + qavariq qobiq

bilan:

Tugunlar soni + joriy TSP marshrut uzunligi

bir xil optimallashtirish qoidasi emas.

Manba Table 6 ablatsiyasida “Node-only”, “Route-only” va “Full MADO” iboralaridan foydalangani va muhokamada route-length hadi haqiqiy routing burden ma’lumotini berishini tushuntirgani uchun bu keyingi tajribalar route-feedback ta’rifiga tegishlidir. Shunga qaramay, chop etilgan dastlabki Tenglama (1) saqlanishi va e’tibordan chetda qolmasligi kerak.

13. Klasterlar qayta hosil qilinadimi?

Manba bu yerda ham ikki xil bayon beradi. Dastlabki to‘rt bosqichli bo‘lim yangi nazariy depo aniqlangandan keyin “cluster the dataset again” iborasidan foydalanadi. Bunga qarshi, keyingi 2-rasm izohi va Algorithm 1 klasterlash bir marta bajarilishini va klaster a’zoliklari depo optimallashtirish davomida o‘zgarmas qolishini aniq aytadi.

Shu sababli Verianla manbaning ushbu ikki bayonidan birini jimgina olib tashlab, algoritmni qayta ta’riflamaydi. Qayta ishlab bo‘ladigan amaliyotda qaysi variant asos qilib olinishi alohida aniqlashtirilishi kerak.

14. Siklning oldini olish va to‘xtatish

Depo nomzodi doim mos mijoz tugunlariga proyeksiya qilinganda algoritm ikki yoki undan ortiq tugun orasida qatnab qolishi mumkin. Manba buning oldini olish uchun:

• tashrif buyurilgan depo holatlarini hash orqali qayd etish,
• takroriy holatni aniqlash,
• ikki holatli doimiy siklni aniqlash,
• projection stall ni aniqlash,
• nomzod yaxshilanish bermasa qadamni kichraytirish/rejection damping,
• minimum displacement,
• maksimal iteratsiya chegarasi

kabi xavfsizlik mexanizmlarini belgilaydi.

Mualliflar bu mexanizmlar algoritmning amalda chekli sondagi iteratsiyalarda to‘xtashini ta’minlashini bildiradilar. Biroq manba ochiq ravishda global optimumga yaqinlashish kafolatini bermaydi.

15. Bo‘l-va-boshqar murakkabligi

Manbaning to‘liq MADO doirasi uchun bergan umumiy murakkablik ifodasi:

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

ko‘rinishidadir.

Bu yerda:

• \(n\): umumiy tugunlar soni,
• \(k\): klasterlar soni,
• \(I_c\): klasterlash usulining ichki iteratsiyalar soni,
• \(T\): MADO depo yangilash iteratsiyalari soni,
• \(m=n/k\): har bir klasterga to‘g‘ri keladigan o‘rtacha tugunlar soni,
• \(f(m)\): \(m\) tugunli bitta TSP quyi masalasini yechish xarajati.

Manba \(T\) amalda kichik doimiy son bo‘lib qoladi deb faraz qilib, depo optimallashtirish yuqori darajali qo‘shimcha yuk yaratmasligini ta’kidlaydi. Shu bilan birga, \(f(m)\) ishlatilgan OR-Tools sozlamalari va yechim strategiyasiga bog‘liqligini unutmaslik kerak.

Workload Balance qiymatini qanday talqin qilish kerak?

Manbaning chop etilgan shakli bu masalada ichki jihatdan izchil emas: usul matni Tenglama (7) uchun kichikroq qiymatni yaxshiroq muvozanat deb qabul qilsa, natijalar bo‘limi va jadvallar yuqoriroq Workload Balance qiymatini yaxshiroq muvozanat deb talqin qiladi; shu sababli muayyan qiymat yo‘nalishini manbani tuzatgandek qat’iylashtirish o‘rniga formula, jadval natijalari va ushbu hisobot nomuvofiqligini birgalikda ko‘rish kerak.

16. Tenglama (4): Bitta klasterning yopiq TSP marshrut uzunligi

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

\(D_k\), \(k\)-klasterga biriktirilgan sotuvchining yopiq tur uzunligidir. \(d(v_i,v_{i+1})\) ketma-ket ikki tugun orasidagi masofadir. Oxirgi had so‘nggi tugundan boshlang‘ich tugunga qaytishni qo‘shib, marshrutni yopadi.

17. Tenglama (5): Min-Max Distance

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

Bu metrika barcha sotuvchi marshrutlari ichidagi eng uzun marshrutni tanlaydi. Maqsad ushbu maksimal qiymatni imkon qadar kamaytirishdir.

Masalan, uchta marshrut 100, 105 va 250 birlik bo‘lsa, Min-Max Distance 250 ga teng. Umumiy yo‘l maqbul bo‘lsa ham, bitta sotuvchiga 250 birlik ortiqcha yuk tushishi mumkin. Shu sababli Min-Max metrikasi eng katta yuklangan birlikni nazorat qilish nuqtai nazaridan muhim.

18. Tenglama (6): Total-Sum Distance

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

Total-Sum barcha sotuvchilar bosib o‘tgan marshrut uzunliklarini yig‘adi. Kichikroq qiymat umumiy operatsion masofa pastroq ekanini ko‘rsatadi.

Min-Max va Total-Sum bir xil maqsad emas. Bir yechim umumiy masofani biroz oshirgan holda eng uzun marshrutni keskin qisqartirishi mumkin. MADO ning ko‘p maqsadli muvozanat masalasi ana shu qarama-qarshilikdan kelib chiqadi.

19. Tenglama (7) va (8): Workload Balance

Manbada:

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

va:

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

berilgan.

\(\bar D\), barcha marshrut uzunliklarining o‘rtacha qiymatidir. Surat marshrut uzunliklarining o‘rtachadan kvadratik og‘ishlari o‘rtachasidir. Maxraj esa kvadratik og‘ishlarning eng kattasidir.

Surat ham, maxraj ham masofaning kvadrati birligida; shu sababli nisbat o‘lchovsiz.

Biroq bu normallashtirish muhim matematik natijani keltirib chiqaradi: barcha og‘ishlar bir xil koeffitsiyent bilan kamaytirilsa yoki oshirilsa, surat va maxraj o‘sha koeffitsiyentning kvadrati bilan o‘zgaradi va nisbat o‘zgarmasligi mumkin. Shu sababli Tenglama (7) marshrutlar farqining mutlaq kattaligini o‘zi alohida o‘lchaydigan klassik dispersiya yoki standart og‘ish emas.

Marshrutlar to‘liq teng bo‘lganda barcha \(D_k-\bar D\) qiymatlari nol bo‘lgani uchun chop etilgan formula nazariy jihatdan \(0/0\) holatiga keladi. Manba bu chegara holati uchun alohida ta’rif bermaydi.

Usul izohi “kichik qiymat = yaxshiroq muvozanat” desa, Figure 3 izohi “yuqori qiymat = yaxshiroq muvozanat” deydi va Table 5 da 0,98 → 0,99 o‘zgarishi yaxshilanish sifatida talqin qilinadi. Shu sababli natijalar jadvallaridagi Workload Balance qiymatlari manba mualliflarining natijalar bo‘limidagi talqin yo‘nalishi bilan berilgan, biroq formula bilan matn o‘rtasidagi ziddiyat ochiq qoldirilgan.

20. Tenglama (9) va (10): Silhouette / Cluster Separability

Manba umumiy silhouette skorini:

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

va bitta nuqta uchun silhouette qiymatini:

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

ko‘rinishida beradi.

\(a(k)\), nuqtaning o‘z klasteridagi boshqa nuqtalargacha bo‘lgan o‘rtacha masofasidir. Klaster ichidagi nuqtalar bir-biriga yaqin bo‘lsa, \(a(k)\) kamayadi.

\(b(k)\), nuqtaning boshqa klasterlarning har birigacha bo‘lgan o‘rtacha masofalari ichidagi eng kichik qiymatdir. Boshqa klasterlar yaxshi ajralgan bo‘lsa, \(b(k)\) kattaroq bo‘lishi mumkin.

Silhouette qiymati −1 dan +1 gacha:

• +1 ga yaqinlashish: yanada ixcham va yaxshiroq ajralgan klaster,
• 0 atrofida: klasterlar chegarasida yoki ustma-ust tushishga yaqin tuzilma,
• manfiy qiymat: nuqta boshqa klasterga yaqinroq bo‘lishi mumkinligini ko‘rsatuvchi tuzilma.

Manbada dsj1000 ma’lumotlar to‘plami aniq klasterlangan fazoviy tuzilishga ega bo‘lgani sababli eng yuqori separability qiymatlarini ko‘rsatishi aytiladi.

21. Tenglama (11) va (12): Robustness

Manba barqarorlik mezonini:

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

va o‘rtacha qiymatni:

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

sifatida ta’riflaydi.

Kasr ichidagi tuzilma standart og‘ishning o‘rtacha qiymatga nisbatiga o‘xshaydi. Manba uning oldiga \(1-\) qo‘shgani uchun o‘zgaruvchanlik kamaygan sari skor 1 ga yaqinlashadi. Demak, bu yerda “CV” nomi ishlatilgan bo‘lsa-da, chop etilgan mezon klassik coefficient of variation ning o‘zi emas, balki 1 minus normallashtirilgan o‘zgaruvchanlik ko‘rinishidagi barqarorlik skoridir.

Manba natijalar bo‘limida barcha ma’lumotlar to‘plamlaridagi o‘rtacha Robustness qiymati taxminan 0,81 ekanini bildiradi.

Biroq takroriy tajribalar soni \(T\) ning aniq sonli qiymati va ishlatilgan random seed manbaning usul bo‘limida ochiq qayd etilmagan.

22. Tenglama (13): Ishlash vaqti

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

Bu metrika algoritm boshlanishidan yakuniy yechim chiqishigacha o‘tgan devor soati vaqtidir. Birligi soniya.

Manba tugunlar soni oshgan sari ishlash vaqti umuman ortishini va tajriba grafigida taxminan chiziqli tendensiya kuzatilganini bildiradi. Bu kuzatuv nazariy murakkablikning matematik isboti emas; qayd etilgan benchmark sharoitlaridagi empirik ishlash vaqti tendensiyasidir.

Tadqiqot usuli va natijalari

23. Ma’lumotlar to‘plamlari

Dastlabki asosiy taqqoslashda beshta TSPLIB benchmark namunasi ishlatilgan:

pr299 ayniqsa vizual holat tadqiqoti uchun tanlangan. Mualliflar buning o‘rta ko‘lamli bo‘lishi, fazoviy tuzilishi depo joylashuvi ta’sirini vizuallashtirishga mosligi va umumiy masofa bilan ish yukining muvozanati o‘rtasidagi murosani ko‘rsatishi sabab tanlanganini bildiradilar.

24. Dasturiy ta’minot infratuzilmasi

Tajribalar Python 3.10 da amalga oshirilgan.

Klasterlash algoritmlari:

scikit-learn v1.3.0

bilan; TSP quyi masalalari:

OR-Tools v9.10

bilan yechilgan.

Manbaning natijalar bo‘limida 2-opt mahalliy optimallashtirish algoritmi ham tilga olinadi. Biroq 2-opt ning usul zanjiridagi aniq chaqirilish nuqtasi, iteratsiya chegarasi yoki qidiruv parametrlari alohida qayd etilmagan.

Manba foydalanilgan CPU/GPU modeli, operatsion tizim, RAM miqdori va random seed ma’lumotini bermaydi. Bu holat ishlash vaqti natijalarini boshqa tizimlarda aynan qayta ishlab chiqishni cheklaydi.

25. Sakkiz bosqichli asosiy yechim oqimi

1. Kirish: TSPLIB tugun koordinatalari, masofa ma’lumoti va sotuvchi/klaster soni \(k\) yuklanadi.
2. Klasterlash: Tugunlar tanlangan algoritm bilan \(k\) ta klasterga ajratiladi.
3. Dastlabki depo: Barcha tugunlarning geometrik centroid-i topiladi va eng yaqin mos tugunga proyeksiya qilinadi.
4. Dastlabki TSP yechimi: Har bir klasterning boshlanish va tugash nuqtasi umumiy depo bo‘ladigan tarzda marshrut yechiladi.
5. MADO yangilanishi: Dinamik vaznlar bilan depo yangilash yo‘nalishi hosil qilinadi va nomzod depo hisoblanadi.
6. Qayta baholash: Nomzod depo uchun barcha klaster marshrutlari qayta yechiladi; Total-Sum, Min-Max va marshrut taqsimoti baholanadi.
7. Samaradorlikni baholash: Oltita metrika hisoblanadi.
8. Chiqish: Best-so-far depo, marshrutlar va samaradorlik o‘lchovlari qaytariladi.

26. Dastlabki besh ma’lumotlar to‘plamidagi Total-Sum natijalari

Bisecting K-Means ayniqsa eil76, pr299 va dsj1000 da Total-Sum bo‘yicha eng past natijani bergan. Shunga qaramay, att48 va gr229 da boshqa algoritmlarning yaxshiroq bo‘lishi klasterlash usuli ma’lumotlar taqsimotiga bog‘liq ekanini ko‘rsatadi.

27. Dastlabki besh ma’lumotlar to‘plamidagi Min-Max natijalari

Bu jadval bilan Total-Sum jadvalining g‘oliblari bir xil emas. Bu holat umumiy operatsion masofani kamaytirish bilan bitta sotuvchiga tushadigan eng uzun marshrutni kamaytirish turli maqsadlar ekanini bevosita ko‘rsatadi.

28. Workload Balance, separability va robustness grafiklarining asosiy xabari

Manba Figure 3 da Workload Balance qiymatlarining aksariyati yuqori darajada ekani va barcha algoritm/ma’lumotlar to‘plami kombinatsiyalarida o‘rtacha qiymat taxminan 0,95 ekanini bildiradi. Avval tushuntirilgan formula-yo‘nalish ziddiyati tufayli bu grafik natijalar bo‘limida qo‘llangan “yuqori qiymat yaxshiroq” yo‘nalishida talqin qilinadi.

Figure 4 da Cluster Separability ma’lumotlar to‘plamiga kuchli bog‘liq. dsj1000 aniq klasterlangan fazoviy tuzilishi sabab eng yuqori silhouette qiymatlarini ko‘rsatadi.

Figure 5 uchun manba o‘rtacha Robustness qiymatini taxminan 0,81 deb bildiradi. Biroq ayrim algoritmlarning muayyan ma’lumotlar to‘plamlaridagi skorlari sezilarli pasayadi; demak, o‘rtacha qiymat har bir algoritm aynan bir xil barqarorlik ko‘rsatadi degani emas.

29. Radar grafik va heatmap qanday talqin qilinishi kerak?

Manba oltita metrikani birgalikda ko‘rsatish uchun radar grafiklari va o‘rtacha reytinglardan tashkil topgan heatmap dan foydalangan.

Radar grafik izohida “K-Means eng katta poligon maydoniga ega” degan iboradan darhol keyin Agglomerative uchun ham “eng katta poligon maydoniga ega” deyiladi. Shu bo‘limda Spectral haqida ham ijobiy, ham “worst comprehensive performance” yo‘nalishida bir-biriga mos kelmaydigan bayonlar mavjud.

Shu sababli Verianla radar grafikdan yagona universal “eng yaxshi algoritm” xulosasini chiqarmaydi.

Manbaning heatmap muhokamasidagi ehtiyotkorroq xulosa saqlanishi mumkin: hech bir klasterlash algoritmi barcha ma’lumotlar to‘plamlari va barcha o‘lchovlarda mutlaq ustun emas. Algoritm tanlovi ma’lumotlar taqsimotiga va qaysi metrikaga ustuvorlik berilishiga bog‘liq.

30. pr299 holat tadqiqoti

pr299 K-Means bilan uchta klasterga ajratilgan. Manbaning 9–14-rasmlar ketma-ketligi:

1. asl tugun taqsimotini,
2. boshlang‘ich depo tanlanishini,
3. uchta klaster hosil bo‘lishini,
4. dastlabki TSP marshrutlarini,
5. MADO bilan depo joylashuvi ko‘chirilishini,
6. yangi depodan yechilgan yakuniy marshrutlarni

ko‘rsatadi.

Manba bu grafiklarning barcha koordinatalari va marshrut tugunlari tartibini matn/jadval ko‘rinishida bermagani uchun Verianla ichida soxta pr299 marshrut xaritasi qayta chizilmagan.

Bu holat tadqiqoti muhim ko‘p maqsadli murosani ko‘rsatadi: marshrut uzunligi va manbada qo‘llangan muvozanat/barqarorlik ko‘rsatkichlari yaxshilanganda cluster separability biroz kamaygan va ishlash vaqti biroz oshgan.

31. Nega Table 3 va pr299 holatidagi sonlar aynan bir xil emas?

Table 3 da K-Means/pr299 uchun Total-Sum Distance 53.848,32 berilgan bo‘lsa, Table 5 holat tadqiqotidagi optimallashtirilgan depo natijasi 54.533,97 ga teng. Manba bu ikki qiymat nega farq qilishini aniq tushuntirmaydi. K-Means boshlang‘ich shartlari yoki tajriba jarayonining turli takrorlari ehtimoliy izoh bo‘lishi mumkin, biroq manba buni tasdiqlamagani uchun Verianla bunday sababni fakt sifatida keltirmaydi.

32. Full MADO ablatsiyasining maqsadi

Ablatsiya tadqiqoti ikki vazn komponentining vazifasini ajratishni maqsad qiladi:

• Node-only MADO: faqat klaster o‘lchami,
• Route-only MADO: faqat marshrut yuki,
• Full MADO: tugunlar soni va marshrut yuki birgalikda.

Mualliflar talqiniga ko‘ra, marshrut uzunligi hadi haqiqiy routing burden ma’lumotini, tugunlar soni hadi esa vazifa ko‘lamini va tartibga soluvchi/muvozanatlashtiruvchi ta’sirni beradi.

33. Table 6 dagi to‘liq ablatsiya natijalari

Bu jadvalning muhim natijasi shundaki, Full MADO har bir o‘lchov va har bir ma’lumotlar to‘plamida yakka holda mutlaq ustun emas. Masalan, rat575 da Node-only MADO pastroq Total-Sum Distance bersa, Full MADO bir xil yoki yaxshiroq Min-Max samaradorligi va boshqa muvozanat kombinatsiyasini ta’minlaydi. Xuddi shuningdek, ayrim statik usullar ishlash vaqti bo‘yicha tezroq.

Shunday qilib, MADO ning hissasi faqat “har bir ustundagi eng kichik son” emas; u marshrutlar yig‘indisi, eng uzun marshrut va manbada qo‘llangan muvozanat ko‘rsatkichi o‘rtasida maqbulroq murosani izlaydi.

34. Nega Table 3/4 va Table 6 masofa masshtablarini bevosita taqqoslamaslik kerak?

Manbaning Table 3 va Table 4 qiymatlari bilan Table 6 qiymatlari bir xil nomli ma’lumotlar to‘plamlarida ham ayrim hollarda juda turli sonli masshtablarga ega. Masalan, gr229 Total-Sum qiymatlari Table 3 da taxminan 1.800–2.300 oralig‘ida bo‘lsa, Table 6 da taxminan 164.000–192.000 darajasidadir.

Manba bu farq uchun masofa o‘zgartirishi, boshqa TSPLIB edge-weight qo‘llanilishi yoki boshqa preprocessing izohini bermaydi. Shu sababli Verianla bu jadvallarni bitta umumiy sonli masshtabda birlashtirmaydi.

35. Ablatsiyaning ilmiy xabari

Mualliflar Node-only va Full MADO ni taqqoslaganda marshrut uzunligi hadi faqat tugunlar sonidan ko‘rinmaydigan haqiqiy routing-cost ma’lumotini berishini ta’kidlaydilar.

Route-only va Full MADO taqqoslovida esa tugunlar soni hadi masshtab kompensatsiyasi va tartibga soluvchi ta’sir berishi ilgari suriladi.

gr229 misolida Route-only Workload Balance 0,861 bo‘lganida Full MADO 0,912 ga yetgan. Manba buni fazoviy jihatdan keng bitta klasterning depotni haddan tashqari tortishini tugunlar soni hadi cheklashi bilan bog‘laydi.

36. Tadqiqot qo‘llab-quvvatlaydigan xulosalar

• MADO sinovdan o‘tkazilgan TSPLIB benchmark misollarida umumiy depo joylashuvini o‘zgartirish orqali marshrut natijalariga ta’sir qilishi mumkin.
• pr299 holat tadqiqotida optimallashtirilgan depo pastroq Total-Sum va Min-Max Distance bergan.
• Klasterlash algoritmini tanlash natijalarni sezilarli darajada o‘zgartiradi; bitta klasterlash usuli barcha ma’lumotlar to‘plamida ustun emas.
• Bisecting K-Means dastlabki besh ma’lumotlar to‘plamining bir nechtasida Total-Sum bo‘yicha kuchli natija bergan.
• Full MADO Table 6 dagi oltita benchmark ning barchasida minimal yoki teng minimal Total-Sum natijasini olgan.
• Full MADO ayniqsa dsj1000 va pcb1173 da statik boshlang‘ich usullarga nisbatan pastroq Total-Sum va Min-Max qiymatlarini ta’minlagan.
• Node-count va route-length komponentlarining ablatsiya natijalari ularning bir-birini to‘ldiruvchi rollarga ega ekani haqidagi mualliflar talqinini qo‘llab-quvvatlaydi.
• Klasterlashga asoslangan bo‘l-va-boshqar yondashuvi katta SD-MTSP ni kichikroq TSP quyi masalalariga ajratishga imkon beradi.

37. Tadqiqot bevosita qo‘llab-quvvatlamaydigan xulosalar

• MADO barcha SD-MTSP misollarida global optimumni topishi ko‘rsatilmagan.
• Real vaqt trafik sharoitida dala tekshiruvi o‘tkazilmagan.
• Dinamik ravishda qo‘shilgan yoki olib tashlangan mijoz nuqtalari tajribaviy ravishda baholanmagan.
• Turli sig‘imdagi transport vositalaridan iborat geterogen park bevosita sinovdan o‘tkazilmagan.
• Vaqt oynalari va transport vositasi sig‘imi asosiy benchmark modelining cheklovlari qatoriga kirmaydi.
• Haqiqiy logistika kompaniyasiga oid xarajat, yoqilg‘i, haydovchi ish vaqti yoki yetkazib berish SLA ma’lumotlari baholanmagan.
• Grafiklardagi yuqori Robustness qiymati haqiqiy dala noaniqliklariga qarshi isbotlangan chidamlilikni anglatmaydi.
• Empirik ishlash vaqti grafigining taxminan chiziqli ko‘rinishi algoritm barcha sharoitlarda chiziqli vaqt murakkabligiga ega ekanini isbotlamaydi.
• Table 6 natijalarini Table 3/4 ning sonli masshtabi bilan izohsiz bevosita birlashtirib bo‘lmaydi.

38. Manbaning o‘z kelgusi tadqiqot takliflari

Mualliflar usulni yanada murakkab dinamik muhitlarda rivojlantirish zarurligini bildiradilar. Taklif etilgan yo‘nalishlar:

• real vaqt trafik o‘zgarishlariga javob berish uchun reinforcement learning yoki online optimization qo‘shish,
• mijoz/vazifa nuqtalarini dinamik ravishda qo‘shish yoki olib tashlashni ko‘rib chiqish,
• geterogen sayyor sotuvchi/transport vositasi turlarini qo‘llab-quvvatlash,
• transport vositasi sig‘imi kabi haqiqiy operatsion cheklovlarni qo‘shish,
• klasterlash bilan marshrut rejalashtirish o‘rtasidagi qo‘shma optimallashtirish mexanizmini rivojlantirish

ko‘rinishidadir.

Bu kelgusi tadqiqot takliflari ayni paytda mavjud maqolaning dala sharoitida qo‘llanishiga qo‘yilgan chegarani ko‘rsatadi. Usul bevosita “muhandislikda to‘liq tasdiqlangan logistika tizimi” darajasida emas; mualliflar ham nazariy qo‘llanuvchanlikdan engineering reliability darajasiga o‘tish uchun qo‘shimcha rivojlantirish zarurligini bildiradilar.

Manba va usul haqida izoh

Asl sarlavha: A Clustering-Based Multi-Task Balancing Method for Depot Optimization in Single-Depot Multiple Traveling Salesman Problems

Mualliflar: Chunlong Fu, Jiaxin Zou, Guofang Liu, Pingli Zheng, Kaiwen Xiao, Yang Deng, Hongxia He va Qi Jiang.

Mas’ul muallif: Chunlong Fu.

Teng hissa: Manbada teng hissa to‘g‘risida bayonot mavjud emas.

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

Jurnal: Mathematics.

Nashriyot: MDPI.

Bibliografik yozuv: Mathematics 2026, 14(15), 2811.

DOI: 10.3390/math14152811.

Topshirilgan sana: 5 iyun 2026.

Tahrir sanasi: 18 iyul 2026.

Qabul sanasi: 28 iyul 2026.

Nashr sanasi: 5 avgust 2026.

Rasmiy havola: DOI 10.3390/math14152811 orqali MDPI nashr yozuvi.

Manba turi: Taqrizdan o‘tgan ilmiy jurnalda chop etilgan original tadqiqot maqolasi; kombinator optimallashtirish, klasterlash va marshrut rejalashtirishga asoslangan hisoblash tadqiqoti.

Preprint holati: Taqdim etilgan manba chop etilgan jurnal versiyasidir. PDF ichida alohida preprint identifikatori ko‘rsatilmagan.

Litsenziya: Creative Commons Attribution (CC BY).

Kalit so‘zlar: SD-MTSP; clustering algorithm; task balancing; depot location optimization.

MSC: 05B05; 90B50.

Dasturiy ta’minot: Python 3.10, scikit-learn v1.3.0 va OR-Tools v9.10.

Benchmark manbasi: TSPLIB.

Dastlabki asosiy ma’lumotlar to‘plamlari: att48, eil76, gr229, pr299 va dsj1000.

Ablatsiya ma’lumotlar to‘plamlari: att48, eil76, gr229, rat575, dsj1000 va pcb1173.

Baholash metrikalari: Total-Sum Distance, Min-Max Distance, Workload Balance, Cluster Separability, Robustness va Running Time.

Moliyalashtirish: Opening Foundation of the State Key Laboratory of Cognitive Intelligence, Anhui iFLYTEK Co., Ltd., Grant No. COGOS-2024HE03; shuningdek Sichuan University Jinjiang College 2024 Young Teacher Research Fund Project, Grant No. QNJJ-2024-B08.

Ma’lumotlarning ochiqligi: Mualliflar tadqiqot ma’lumotlari TSPLIB asosida ochiq foydalanish uchun mavjudligini va Data Availability bo‘limida GitCode ga kirish havolasini taqdim etganliklarini bildirganlar.

Manfaatlar to‘qnashuvi: Mualliflar manfaatlar to‘qnashuvi yo‘qligini bildirganlar.

Sun’iy intellektdan foydalanish bayonoti: Mualliflar maqola tayyorlanishi davomida ChatGPT-5.4 dan grammatika yaxshilash va tilni tahrirlash maqsadida foydalanganliklarini; yakuniy mazmunni o‘zlari ko‘rib chiqib tahrir qilganliklarini va nashr mazmuni uchun javobgarlikni o‘z zimmalariga olganliklarini bildirganlar.

Mualliflar hissasi: Konseptuallashtirish Qi Jiang; usul Jiaxin Zou, Chunlong Fu, Pingli Zheng va Kaiwen Xiao; dasturiy ta’minot Guofang Liu va Hongxia He; tekshirish Jiaxin Zou, Chunlong Fu va Hongxia He; formal tahlil Guofang Liu va Yang Deng; tadqiqot Chunlong Fu; resurslar Pingli Zheng va Qi Jiang; ma’lumotlarni kuratsiya qilish Jiaxin Zou, Pingli Zheng va Kaiwen Xiao; dastlabki qoralama Jiaxin Zou; ko‘rib chiqish va tahrirlash Chunlong Fu; vizuallashtirish Yang Deng; nazorat Chunlong Fu va Guofang Liu tomonidan bajarilgan.

Muhim metodologik nomuvofiqlik 1 — vazn ta’rifi: Dastlabki Tenglama (1) tugunlar nisbati bilan qavariq qobiq nisbatidan foydalanadi. Keyingi Route-Feedback MADO oqimi, Algorithm 1 va Table 6 muhokamasi tugunlar soni bilan joriy TSP marshrut uzunligidan foydalanadi. Manba bu ikki ta’rifni ochiq reviziya munosabati bilan bog‘lamaydi.

Muhim metodologik nomuvofiqlik 2 — klasterlash: Dastlabki to‘rt bosqichli izoh yangilangan depodan keyin qayta klasterlash haqida gapiradi, 2-rasm va Algorithm 1 esa klaster a’zoliklari bir marta hosil qilinib, depo optimallashtirish davomida o‘zgarmas saqlanishini aytadi.

Muhim metrik nomuvofiqligi — Workload Balance: Tenglama (7) dan oldingi izoh kichikroq qiymatlar yaxshiroq muvozanatni ko‘rsatishini aytadi. Natijalar bo‘limi, 3-rasm va Table 5–6 esa yuqoriroq qiymatni yaxshiroq deb talqin qiladi. Verianla bu ziddiyatni jimgina tuzatmagan.

Ma’lumotlar to‘plami qamrovi haqida izoh: Section 5.1 beshta benchmark misolini belgilaydi; Table 6 esa pr299 o‘rniga rat575 va pcb1173 ni o‘z ichiga olgan oltita misolli alohida taqqoslashdan foydalanadi.

Masofa masshtabi haqida izoh: Table 3/4 va Table 6 da bir xil TSPLIB nomlariga ega ayrim ma’lumotlar to‘plamlarining masofa kattaliklari turli masshtablardadir. Manba buning uchun aniq o‘zgartirish yoki preprocessing izohini bermaydi; jadvallar bevosita bitta masshtabli ma’lumotlar to‘plamidek birlashtirilmagan.

pr299 sonlari haqida izoh: Table 3 da K-Means/pr299 Total-Sum Distance 53.848,32 bo‘lsa, holat tadqiqotining Table 5 dagi optimallashtirilgan depo natijasi 54.533,97 ga teng. Manba farq sababini ochiq tushuntirmaydi.

2-opt haqida izoh: Natijalar bo‘limida 2-opt mahalliy optimallashtirish OR-Tools yechimiga kiritilgani aytiladi; biroq usul bo‘limida 2-opt ning batafsil konfiguratsiyasi berilmagan.

Qayta ishlab chiqarish mumkinligi haqida izoh: Algorithm 1, \(T_{max}\), \(\varepsilon\) va boshlang‘ich qadam \(\eta_0\) parametrlarini kirish sifatida belgilaydi; manba bu parametrlarning ishlatilgan sonli qiymatlarini bermaydi. Repeated-experiment soni, random seed va hisoblash uskunasi ham ochiq qayd etilmagan.

Yaqinlashuv chegarasi: Mualliflar global optimum kafolatini bermaydilar. State hashing, cycle detection, projection-stall nazorati va qadamni kichraytirish mexanizmlari iteratsiyaning amalda yakunlanishini maqsad qiladi.

Haqiqiy dunyo chegarasi: Tadqiqot TSPLIB benchmark tekshiruvidir. Haqiqiy logistika parki, jonli trafik, transport vositasi sig‘imi, vaqt oynasi, dinamik mijoz kirishi va geterogen transport vositalarida operatsion dala tekshiruvi o‘tkazilmagan.