Uboreshaji wa Bohari Unaobadilika kwa Uzani Nyingi (Multi-Weight Adaptive Depot Optimization, MADO), ni mbinu ya uboreshaji ambayo, katika tatizo la wauzaji wasafiri wengi wenye bohari moja, hugawa nodi za wateja katika makundi, huipa kila kundi muuzaji msafiri mmoja, na hubadilisha kwa kurudia eneo la bohari ya pamoja kwa kuzingatia kwa pamoja ufanisi wa njia na usawazishaji wa mzigo wa kazi. Utafiti huu unaunganisha algoriti nane tofauti za ugawaji katika makundi, suluhisho la TSP linalotegemea OR-Tools, uboreshaji wa eneo la bohari, na viashiria sita vya utendaji—Total-Sum Distance, Min-Max Distance, Workload Balance, Cluster Separability, Robustness na Running Time—kwenye seti za data za benchmark za TSPLIB.

Wazo kuu la mbinu ni kugawa SD-MTSP kubwa kuwa matatizo madogo ya TSP kwa kugawa nodi za wateja katika makundi, badala ya kuitatua moja kwa moja kama tatizo moja kamili. Kisha eneo la bohari ya pamoja husasishwa kwa kutumia uzani unaowakilisha ukubwa wa makundi na mzigo wa kijiografia/njia. Kwa kila bohari inayopendekezwa, njia za TSP ndani ya makundi hutatuliwa upya na eneo jipya hutathminiwa kwa kuzingatia urefu wa njia na vipimo vya usawazishaji.

Katika ulinganisho wa kwanza wa seti tano za data, att48, eil76, gr229, pr299 na dsj1000 zilitumika. Kwa Total-Sum Distance, BIRCH ilitoa thamani ya chini zaidi katika att48, Fuzzy C-Means katika gr229; na Bisecting K-Means katika eil76, pr299 na dsj1000. Matokeo haya yanaonyesha kuwa hakuna algoriti moja ya ugawaji katika makundi iliyo bora kwa kila usambazaji wa data.

Katika uchunguzi kifani wa pr299, Total-Sum Distance ilipungua kutoka 55.145,51 kwa bohari ya awali hadi 54.533,97 kwa bohari iliyoboreshwa; Min-Max Distance ilipungua kutoka 21.130,08 hadi 20.624,04. Chanzo kinaripoti katika ulinganisho huo huo kwamba Workload Balance iliongezeka kutoka 0,98 hadi 0,99 na Robustness kutoka 0,88 hadi 0,90; Cluster Separability ilipungua kutoka 0,24 hadi 0,21, na muda wa utekelezaji uliongezeka kutoka sekunde 7,71 hadi sekunde 7,87.

Katika utafiti wa baadaye wa ablation wenye seti sita za data, Full MADO ililinganishwa na mbinu za Geometric, Midpoint, S-shaped, Node-only MADO na Route-only MADO kwenye att48, eil76, gr229, rat575, dsj1000 na pcb1173. Chanzo kinaripoti kwamba Full MADO ilipata Total-Sum Distance ya chini zaidi au iliyolingana na ya chini zaidi katika mifano yote sita; na Min-Max Distance ya chini zaidi au iliyolingana na ya chini zaidi katika mitano. Katika dsj1000 na pcb1173, upungufu wa Total-Sum Distance ikilinganishwa na mkakati bora wa awali wa tuli uliripotiwa kuwa takriban %2,3 na %1,6 mtawalia.

Hata hivyo, utafiti huu si uthibitishaji wa uwandani kwenye kundi halisi la magari ya usambazaji, trafiki halisi, uwezo wa gari, madirisha ya muda au mtiririko wa oda unaobadilika. Matokeo yalipatikana katika mazingira ya benchmark ya kimahesabu yanayotegemea TSPLIB. Chanzo pia kina kauli zisizolingana kikamilifu katika sehemu tofauti za ufafanuzi wa mbinu kuhusu hesabu ya uzani, iwapo uanachama wa makundi hubaki thabiti wakati wa marudio, na jinsi thamani ya juu/chini ya kipimo cha Workload Balance inavyofasiriwa. Kwa hiyo, hoja hizi hazipaswi kuwasilishwa kana kwamba zimeamuliwa kwa uhakika.

1. Traveling Salesman Problem ni nini?

Traveling Salesman Problem (TSP), ni tatizo la kawaida la uboreshaji wa kikombinatoria linalolenga muuzaji au gari kutembelea kila moja ya miji iliyobainishwa mara moja, kurudi katika mahali pa kuanzia, na kupunguza gharama ya jumla ya safari kadiri iwezekanavyo.

Njia moja:

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

huunda mzunguko uliofungwa.

Sifa muhimu ya TSP ni kwamba nafasi ya suluhisho hukua kwa kasi sana kadiri idadi ya miji inavyoongezeka. Kwa miji \(n\), idadi ya mipangilio inayowezekana hukua kwa kiwango cha factorial. Kwa hiyo, idadi ya nodi inapofikia mamia au maelfu, kujaribu kila njia moja baada ya nyingine si jambo la kiutendaji.

2. MTSP ni nini?

Multiple Traveling Salesman Problem (MTSP), ni toleo lililopanuliwa la TSP lenye wauzaji wasafiri au vitengo vya uendeshaji zaidi ya kimoja. Badala ya mtu mmoja kutembelea sehemu zote, majukumu hugawanywa kati ya wauzaji kadhaa.

Hapa, kuwa na umbali mfupi wa jumla pekee huenda kusiwe vya kutosha. Kwa mfano, ikiwa magari matatu kati ya manne yanafanya kazi kwenye njia fupi huku gari la nne likilazimika kuhudumia sehemu zote za mbali, mgawanyo wa majukumu unaweza kuwa usio na uwiano kiutendaji hata kama safari ya jumla inakubalika.

3. SD-MTSP ni nini?

Single-Depot Multiple Traveling Salesman Problem (SD-MTSP), ni aina ya MTSP ambapo wauzaji wasafiri wote huanzia kwenye bohari moja ya pamoja, hutembelea nodi za wateja walizopangiwa, na kurudi katika bohari hiyo hiyo.

Kwa hiyo, maamuzi mawili yanategemeana:

• Ni mteja gani anapangiwa muuzaji gani,
• bohari ya pamoja itawekwa wapi.

Eneo la bohari linapobadilika, miunganisho ya kuanzia na kumalizia ya njia ya kila muuzaji pia hubadilika. Hivyo, umbali wa jumla na njia ndefu zaidi zinaweza kubadilika kwa pamoja.

4. Kwa nini bohari haiwekwi tu kwenye kituo cha kijiometri?

Kuchukua kituo cha kijiometri cha sehemu za wateja ni rahisi na haraka; hata hivyo, kituo hicho hakizingatii moja kwa moja ni nodi ngapi zimo katika makundi ya wateja, makundi yamesambaa kiasi gani, au njia halisi za TSP zina urefu gani.

Kwa mfano, hata kama vituo vya makundi mawili viko umbali sawa kutoka bohari, kundi moja linaweza kuwa na wateja 20 na jingine 100. Vivyo hivyo, kati ya makundi mawili yenye idadi sawa ya wateja, moja linaweza kuwa limekusanyika katika eneo dogo na jingine likawa limesambaa katika eneo pana la kijiografia.

Msukumo mkuu wa MADO ni kujumuisha tofauti hizi kama uzani katika usasishaji wa bohari.

5. Kwa nini ugawaji katika makundi unatumiwa?

Ugawaji katika makundi hutumiwa kugawa tatizo kubwa la SD-MTSP kuwa matatizo madogo. Kila kundi hupewa muuzaji msafiri mmoja na njia ndani ya kundi hutatuliwa kama TSP tofauti.

Kwa mgawanyo wa tuli wenye ukubwa sawa, chanzo kinatazama muundo wa kinadharia wa factorial wa tatizo la kiwango kamili chini ya dhana ya \(n=k\,m\):

\[ O(n!) \]

badala yake takriban:

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

kwa namna hii.

Hapa:

• \(n\): jumla ya idadi ya nodi,
• \(k\): idadi ya makundi au wauzaji,
• \(m=n/k\): wastani wa idadi ya nodi kwa kila kundi.

Usemi huu unaeleza msukumo wa kinadharia wa kugawa tatizo kubwa katika TSP ndogo. Hata hivyo, matatizo halisi madogo ya TSP katika utafiti yanatatuliwa kwa OR-Tools; kwa hiyo, \(O(m!)\) haipaswi kufasiriwa kama uchangamano halisi wa muda wa utekelezaji wa heuristic ya OR-Tools iliyotumika.

6. Algoriti za ugawaji katika makundi zilizolinganishwa katika utafiti

MADO Husasishaje Eneo la Bohari?

MADO huunganisha vekta zinazoelekea kutoka bohari ya pamoja kwenda kwenye kituo cha kila kundi kwa uzani unaowakilisha ukubwa wa jukumu la kundi na mzigo wa kijiografia/njia ili kutoa mwelekeo wa kusogea kwa bohari; hata hivyo, kwa kuwa katika chanzo uzani huu wa pili umefafanuliwa kama convex hull katika sehemu ya awali ya mbinu na kama urefu wa sasa wa njia ya TSP katika mtiririko wa baadaye wa Route-Feedback MADO, haipaswi kudhaniwa kuwa maelezo haya mawili ni algoriti ileile ya kihisabati.

7. Bohari ya kwanza huchaguliwaje?

Katika chanzo, geometric centroid ya nodi zote za wateja huhesabiwa kwanza. Nukta hii huitwa bohari ya kinadharia.

Hata hivyo, kwa kuwa eneo halisi la bohari linatakiwa kuwa mojawapo ya nodi sampuli zinazofaa katika tatizo, nukta sampuli iliyo karibu zaidi na centroid ya kinadharia huchaguliwa na kutumiwa kama eneo la kwanza la bohari halisi.

8. Mlinganyo (1): Vekta ya awali ya mwelekeo wenye uzani ya MADO

Mlinganyo (1) katika sehemu ya mbinu ya chanzo:

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

Hapa:

• \(V\): vekta ya jumla ya mabadiliko ya hali/eneo la bohari,
• \(N\): jumla ya idadi ya nodi za wateja,
• \(N(C_i)\): idadi ya nodi za wateja katika kundi la \(i\),
• \(L_i\): katika fasili hii ya awali, convex hull ya kundi la \(i\),
• \(L\): jumla ya convex hull za makundi yote,
• \(V_i\): vekta inayoelekea kutoka bohari ya sasa hadi kituo cha kundi la \(i\).

\(N(C_i)/N\) na \(L_i/L\) ni uwiano usio na vipimo. Uwiano huu miwili unapozidishwa, huzalisha tena uzani usio na vipimo. Kwa kuwa uzani huu unazidishwa kwa vekta ya eneo \(V_i\), matokeo \(V\) yana kipimo sawa na koordinati za eneo.

Uwiano wa nodi unapokuwa mkubwa, athari ya kundi lenye majukumu mengi kwenye bohari huongezeka. Uwiano wa convex hull unapokuwa mkubwa, athari ya kundi lililosambaa zaidi kijiografia huongezeka.

Chanzo kinaeleza kuwa sababu ya kutotumia hasa urefu halisi wa njia ya TSP katika fomula hii ya awali ni kwamba urefu wa njia tayari hutegemea eneo la bohari, jambo ambalo linaweza kuongeza utegemezi wa mzunguko wakati wa usasishaji.

9. Mlinganyo (2): Bohari mpya

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

Mlinganyo huu unaonyesha kuongezwa kwa vekta ya mwelekeo wenye uzani kwenye koordinati ya bohari ya sasa. Kadiri \(V\) inavyokaribia sifuri, ndivyo mwendo wa bohari unaopendekezwa unavyopungua.

10. Mlinganyo (3): Fasili ya kusitisha mapema

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

Katika maelezo ya awali ya hatua nne ya chanzo, algoriti husitishwa ikiwa bohari mpya inaprojektiwa kwenye nodi sampuli ileile kama bohari iliyotangulia.

Hata hivyo, Algorithm 1 ya baadaye hutumia mantiki pana zaidi ya kusitisha: algoriti husimama ikiwa bohari haibadiliki, ukubwa wa hatua umekuwa mdogo sana, mzunguko au hali inayojirudia imegunduliwa, au idadi ya juu zaidi ya marudio imefikiwa.

11. Fasili ya baadaye ya Route-Feedback MADO katika chanzo

Mtiririko wa baadaye wa hatua nane wa makala na Algorithm 1 vinaeleza utaratibu wa usasishaji kwa namna tofauti. Hapa makundi huundwa mara moja na huwekwa thabiti katika kipindi chote cha uboreshaji wa bohari. Katika kila marudio, uzani huundwa kwa kutumia:

• idadi ya nodi za kundi \(n_i\),
• urefu wa njia ya TSP \(L_i^{(t)}\) uliokokotolewa kwenye bohari ya sasa

hutumiwa kuunda uzani.

Katika sehemu hiyo hiyo, chanzo kinatoa usasishaji wa bohari inayopendekezwa:

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

kwa namna hii.

Hapa:

• \(p^{(t)}\): koordinati ya bohari katika marudio ya \(t\),
• \(D^{(t)}\): mwelekeo uliosanifiwa wa usasishaji wa bohari,
• \(\|D^{(t)}\|_2\): norma ya Euclidean ya vekta ya mwelekeo,
• \(s_t\): ukubwa wa hatua unaobadilika na wenye ufanisi,
• \(\varepsilon\): kigezo cha uvumilivu kinachotumiwa kwa tatizo la kugawanya kwa sifuri au norma ndogo sana.

Kugawa vekta kwa norma yake kunanormalisha kwa kiasi kikubwa taarifa ya mwelekeo; ukubwa halisi wa mwendo huamuliwa na \(s_t\).

Hata hivyo, chanzo hakitoi thamani za namba za \(T_{max}\), \(\varepsilon\) na hatua ya awali \(\eta_0\). Inasemwa kuwa “lexicographic objective” iliyofafanuliwa kabla hutumiwa katika kukubali bohari inayopendekezwa, lakini mpangilio kamili wa kihisabati wa vipaumbele wa kanuni hii ya kukubali kwa lexicographic haujaripotiwa katika mlinganyo tofauti.

12. Kwa nini tofauti kati ya maelezo mawili ya mbinu ni muhimu?

Convex hull hutegemea tu msambao wa kijiometri wa kundi na haibadiliki moja kwa moja bohari inaposogea. Urefu wa njia ya TSP, kwa upande mwingine, hutegemea eneo la sasa la bohari na unaweza kukokotolewa upya baada ya kila mabadiliko ya bohari.

Kwa hiyo:

Idadi ya nodi + convex hull

na:

Idadi ya nodi + urefu wa sasa wa njia ya TSP

si kanuni moja ya uboreshaji.

Kwa kuwa chanzo kinatumia maneno “Node-only”, “Route-only” na “Full MADO” katika ablation ya Table 6 na kinaeleza katika mjadala kwamba kipengele cha route-length hutoa taarifa halisi ya routing burden, majaribio haya ya baadaye yanahusiana na maelezo ya route-feedback. Hata hivyo, Mlinganyo (1) wa awali uliochapishwa lazima uhifadhiwe na usipuuzwe.

13. Je, makundi huundwa upya?

Chanzo kina maelezo mawili tofauti hapa pia. Sehemu ya awali ya hatua nne hutumia kauli “cluster the dataset again” baada ya bohari mpya ya kinadharia kubainishwa. Kinyume chake, maelezo ya baadaye ya Figure 2 na Algorithm 1 yanasema wazi kwamba clustering hufanywa mara moja na uanachama wa makundi hubaki thabiti katika kipindi chote cha uboreshaji wa bohari.

Kwa hiyo, Verianla haifafanui upya algoriti kwa kufuta kimya kimya mojawapo ya maelezo haya mawili ya chanzo. Katika utekelezaji unaoweza kurudiwa, lazima ibainishwe pia ni toleo lipi litakalotumika kama msingi.

14. Kuzuia mzunguko na kusitisha

Bohari inayopendekezwa inapoprojektiwa mara kwa mara kwenye nodi zinazofaa za wateja, algoriti inaweza kwenda na kurudi kati ya nodi mbili au zaidi. Ili kuzuia hili, chanzo kinafafanua:

• kurekodi hali za bohari zilizotembelewa kwa hash,
• ugunduzi wa hali inayojirudia,
• ugunduzi wa mzunguko endelevu wa hali mbili,
• ugunduzi wa projection stall,
• kupunguza hatua/rejection damping ikiwa bohari inayopendekezwa haileti uboreshaji,
• minimum displacement,
• kikomo cha juu cha marudio

kama mbinu za usalama.

Waandishi wanasema mbinu hizi huwezesha algoriti kusimama kwa idadi yenye kikomo ya marudio katika matumizi ya vitendo. Hata hivyo, chanzo kwa uwazi hakitoi dhamana ya kukaribia optimum ya kimataifa.

15. Uchangamano wa divide-and-conquer

Usemi wa jumla wa uchangamano unaotolewa na chanzo kwa mfumo kamili wa MADO ni:

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

kwa namna hii.

Hapa:

• \(n\): jumla ya idadi ya nodi,
• \(k\): idadi ya makundi,
• \(I_c\): idadi ya marudio ya ndani ya mbinu ya ugawaji katika makundi,
• \(T\): idadi ya marudio ya usasishaji wa bohari wa MADO,
• \(m=n/k\): wastani wa idadi ya nodi kwa kila kundi,
• \(f(m)\): gharama ya kutatua tatizo moja dogo la TSP lenye nodi \(m\).

Chanzo kinadai kwamba uboreshaji wa bohari hauleti gharama ya ziada ya kiwango cha juu kwa kudhani kwamba \(T\) hubaki kuwa thamani ndogo thabiti katika vitendo. Hata hivyo, ni muhimu kukumbuka kuwa \(f(m)\) hutegemea mipangilio ya OR-Tools na mkakati wa suluhisho uliotumika.

Thamani ya Workload Balance Inapaswa Kufasiriwaje?

Toleo lililochapishwa la chanzo halina uthabiti wa ndani kuhusu suala hili: maandishi ya mbinu yanachukulia thamani ndogo katika Mlinganyo (7) kuwa yenye usawazishaji bora zaidi, huku sehemu ya matokeo na majedwali yakifasiri thamani ya juu ya Workload Balance kuwa usawazishaji bora zaidi; kwa hiyo, badala ya kuamua kwa uhakika mwelekeo wa thamani fulani kana kwamba chanzo kinarekebishwa, ni muhimu kuangalia pamoja fomula, matokeo ya majedwali na kutolingana huku kwa uripoti.

16. Mlinganyo (4): Urefu wa njia ya TSP iliyofungwa ya kundi moja

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

\(D_k\) ni urefu wa mzunguko uliofungwa wa muuzaji aliyepewa kundi la \(k\). \(d(v_i,v_{i+1})\) ni umbali kati ya nodi mbili zinazofuatana. Kipengele cha mwisho kinaongeza kurudi kutoka nodi ya mwisho hadi nodi ya kuanzia, hivyo kufunga njia.

17. Mlinganyo (5): Min-Max Distance

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

Kipimo hiki huchagua njia ndefu zaidi kati ya njia zote za wauzaji. Lengo ni kupunguza thamani hii ya juu kadiri iwezekanavyo.

Kwa mfano, ikiwa njia tatu ni vitengo 100, 105 na 250, Min-Max Distance ni 250. Hata kama safari ya jumla inakubalika, muuzaji mmoja anaweza kuwa amebebeshwa mzigo mkubwa kupita kiasi wa vitengo 250. Kwa hiyo, kipimo cha Min-Max ni muhimu kwa kudhibiti kitengo chenye mzigo mzito zaidi.

18. Mlinganyo (6): Total-Sum Distance

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

Total-Sum hujumlisha urefu wa njia zinazofuatwa na wauzaji wote. Thamani ndogo inaonyesha umbali mdogo wa jumla wa uendeshaji.

Min-Max na Total-Sum si lengo moja. Suluhisho linaweza kuongeza kidogo umbali wa jumla huku likipunguza kwa kiasi kikubwa njia ndefu zaidi. Tatizo la usawazishaji lenye malengo mengi la MADO linatokana na mvutano huu.

19. Mlinganyo (7) na (8): Workload Balance

Katika chanzo:

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

na:

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

zimetolewa.

\(\bar D\) ni wastani wa urefu wote wa njia. Sehemu ya juu ni wastani wa mikengeuko ya mraba ya urefu wa njia kutoka kwenye wastani. Sehemu ya chini ni mkengeuko mkubwa zaidi wa mraba.

Sehemu ya juu na ya chini zote zina kitengo cha umbali mraba; kwa hiyo uwiano hauna kipimo.

Hata hivyo, unormalishaji huu huleta matokeo muhimu ya kihisabati: ikiwa mikengeuko yote inapunguzwa au kuongezwa kwa kizio kilekile, sehemu ya juu na ya chini hubadilika kwa mraba wa kizio hicho na uwiano unaweza kubaki uleule. Kwa hiyo, Mlinganyo (7) si variance ya kawaida wala standard deviation inayopima peke yake ukubwa halisi wa tofauti za njia.

Katika njia zilizo sawa kabisa, kwa kuwa thamani zote za \(D_k-\bar D\) ni sifuri, fomula iliyochapishwa kinadharia hufikia hali ya \(0/0\). Chanzo hakitoi fasili tofauti kwa hali hii ya mpaka.

Wakati maelezo ya mbinu yanasema “thamani ndogo = usawazishaji bora zaidi”, maelezo ya Figure 3 yanasema “thamani kubwa = usawazishaji bora zaidi” na mabadiliko ya 0,98 → 0,99 katika Table 5 yanafasiriwa kama uboreshaji. Kwa hiyo, thamani za Workload Balance katika majedwali ya matokeo zimewasilishwa kwa mwelekeo wa tafsiri uliotumiwa na waandishi wa chanzo katika sehemu ya matokeo, lakini mgongano kati ya fomula na maandishi umewekwa wazi.

20. Mlinganyo (9) na (10): Silhouette / Cluster Separability

Chanzo kinatoa alama ya jumla ya silhouette kama:

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

na thamani ya silhouette kwa nukta moja kama:

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

kwa namna hii.

\(a(k)\) ni wastani wa umbali wa nukta kwenda kwa nukta nyingine katika kundi lake. Ikiwa nukta ndani ya kundi ziko karibu, \(a(k)\) hupungua.

\(b(k)\) ni thamani ndogo zaidi kati ya wastani wa umbali wa nukta kwenda kwenye kila kundi jingine. Ikiwa makundi mengine yametenganishwa vizuri, \(b(k)\) inaweza kuwa kubwa zaidi.

Thamani ya Silhouette iko kati ya −1 na +1:

• kukaribia +1: kundi lililobana zaidi na lililotenganishwa vizuri zaidi,
• karibu na 0: muundo ulio kwenye mpaka wa makundi au karibu na kuingiliana,
• thamani hasi: muundo unaodokeza kwamba nukta inaweza kuwa karibu zaidi na kundi jingine.

Chanzo kinasema kwamba seti ya data ya dsj1000 inaonyesha thamani za juu zaidi za separability kutokana na muundo wake wa kijiografia wenye makundi yaliyojitokeza wazi.

21. Mlinganyo (11) na (12): Robustness

Chanzo kinafafanua kipimo cha uthabiti kama:

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

na thamani ya wastani kama:

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

ifuatavyo.

Muundo ndani ya sehemu ya uwiano unafanana na uwiano wa standard deviation kwa wastani. Kwa kuwa chanzo kinaongeza \(1-\) mbele yake, alama hukaribia 1 kadiri utofauti unavyopungua. Kwa hiyo, ingawa jina “CV” limetumiwa hapa, kipimo kilichochapishwa si coefficient of variation ya kawaida yenyewe, bali ni alama ya uthabiti katika mfumo wa 1 pungufu ya utofauti ulionormalishwa.

Chanzo kinaripoti katika sehemu ya matokeo kwamba wastani wa Robustness katika seti zote za data ni takriban 0,81.

Hata hivyo, thamani kamili ya namba ya idadi ya majaribio yanayorudiwa \(T\) na random seed iliyotumika hazijaripotiwa wazi katika sehemu ya mbinu ya chanzo.

22. Mlinganyo (13): Muda wa utekelezaji

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

Kipimo hiki ni muda wa saa halisi unaopita kutoka mwanzo wa algoriti hadi kutolewa kwa suluhisho la mwisho. Kitengo chake ni sekunde.

Chanzo kinasema kwamba muda wa utekelezaji kwa ujumla huongezeka kadiri idadi ya nodi inavyoongezeka na kwamba mwelekeo takriban wa mstari ulionekana katika grafu ya majaribio. Uchunguzi huu si uthibitisho wa kihisabati wa uchangamano wa kinadharia; ni mwelekeo wa kiempiria wa muda wa utekelezaji katika mazingira ya benchmark yaliyoripotiwa.

Mbinu na Matokeo ya Utafiti

23. Seti za data

Katika ulinganisho mkuu wa kwanza, mifano mitano ya benchmark ya TSPLIB ilitumiwa:

pr299 ilichaguliwa hasa kwa uchunguzi kifani wa kuona. Waandishi wanasema ilichaguliwa kwa sababu ina ukubwa wa kati, muundo wake wa kijiografia unafaa kuonyesha athari ya eneo la bohari, na inaweza kuonyesha mabadilishano kati ya umbali wa jumla na usawazishaji wa mzigo wa kazi.

24. Miundombinu ya programu

Majaribio yalitekelezwa kwa Python 3.10.

Algoriti za ugawaji katika makundi:

scikit-learn v1.3.0

na matatizo madogo ya TSP:

OR-Tools v9.10

yalitatuliwa kwa.

Katika sehemu ya matokeo ya chanzo, algoriti ya uboreshaji wa ndani ya 2-opt pia imetajwa. Hata hivyo, mahali kamili ambapo 2-opt huitwa katika mlolongo wa mbinu, kikomo cha marudio au vigezo vya utafutaji havijaripotiwa kando.

Chanzo hakiripoti modeli ya CPU/GPU iliyotumika, mfumo wa uendeshaji, kiasi cha RAM wala taarifa ya random seed. Hali hii inapunguza uwezo wa kuzalisha tena matokeo ya muda wa utekelezaji kwa usahihi uleule kwenye mifumo mingine.

25. Mtiririko mkuu wa suluhisho wa hatua nane

1. Ingizo: Koordinati za nodi za TSPLIB, taarifa za umbali na idadi ya wauzaji/makundi \(k\) hupakiwa.
2. Ugawaji katika makundi: Nodi hugawanywa katika makundi \(k\) kwa algoriti iliyochaguliwa.
3. Bohari ya kwanza: geometric centroid ya nodi zote hupatikana na kuprojektiwa kwenye nodi inayofaa iliyo karibu zaidi.
4. Suluhisho la kwanza la TSP: Njia hutatuliwa kwa namna ambayo mwanzo na mwisho wa kila kundi ni bohari ya pamoja.
5. Usasishaji wa MADO: Mwelekeo wa usasishaji wa bohari huundwa kwa uzani unaobadilika na bohari inayopendekezwa huhesabiwa.
6. Tathmini upya: Kwa bohari inayopendekezwa, njia zote za makundi hutatuliwa upya; Total-Sum, Min-Max na usambazaji wa njia hutathminiwa.
7. Tathmini ya utendaji: Vipimo sita huhesabiwa.
8. Tokeo: Bohari ya best-so-far, njia na vipimo vya utendaji hurudishwa.

26. Matokeo ya Total-Sum katika seti tano za kwanza

Bisecting K-Means ilitoa matokeo ya chini zaidi ya Total-Sum hasa katika eil76, pr299 na dsj1000. Hata hivyo, ukweli kwamba algoriti tofauti zilifanya vizuri zaidi katika att48 na gr229 unaonyesha kuwa mbinu ya ugawaji katika makundi hutegemea usambazaji wa data.

27. Matokeo ya Min-Max katika seti tano za kwanza

Washindi wa jedwali hili si wale wale wa jedwali la Total-Sum. Hii inaonyesha moja kwa moja kwamba kupunguza umbali wa jumla wa uendeshaji na kupunguza njia ndefu zaidi inayomwangukia muuzaji mmoja ni malengo tofauti.

28. Ujumbe mkuu wa grafu za Workload Balance, separability na robustness

Chanzo kinasema katika Figure 3 kwamba thamani nyingi za Workload Balance ziko katika kiwango cha juu na wastani wa michanganyiko yote ya algoriti/seti za data ni takriban 0,95. Kwa sababu ya mgongano wa fomula na mwelekeo ulioelezwa hapo awali, grafu hii inawasilishwa kwa tafsiri ya “thamani kubwa ni bora zaidi” iliyotumiwa katika sehemu ya matokeo.

Katika Figure 4, Cluster Separability inategemea sana seti ya data. dsj1000 inaonyesha thamani za juu zaidi za silhouette kutokana na muundo wake wa kijiografia wenye makundi yaliyojitokeza wazi.

Kwa Figure 5, chanzo kinaripoti wastani wa Robustness wa takriban 0,81. Hata hivyo, alama za baadhi ya algoriti hupungua kwa kiasi kikubwa katika seti fulani za data; kwa hiyo, thamani ya wastani haimaanishi kwamba algoriti zote zinaonyesha kiwango kilekile cha uthabiti.

29. Grafu ya radar na heatmap zinapaswa kufasiriwaje?

Chanzo kimetumia grafu za radar na heatmap yenye viwango vya wastani ili kuonyesha vipimo sita kwa pamoja.

Katika maelezo ya grafu ya radar, mara tu baada ya kauli “K-Means ina eneo kubwa zaidi la poligoni”, Agglomerative pia inaelezwa kuwa “ina eneo kubwa zaidi la poligoni”. Sehemu hiyo hiyo ina kauli zisizolingana kuhusu Spectral, zikiwa na maelezo chanya na pia yanayoelekea kwenye “worst comprehensive performance”.

Kwa hiyo, Verianla haitoi hitimisho moja la jumla la “algoriti bora zaidi” kutoka kwenye grafu ya radar.

Hitimisho la tahadhari zaidi kutoka kwenye mjadala wa heatmap wa chanzo linaweza kuhifadhiwa: hakuna algoriti ya ugawaji katika makundi iliyo bora kabisa katika seti zote za data na vipimo vyote. Uchaguzi wa algoriti hutegemea usambazaji wa data na kipimo kinachopewa kipaumbele.

30. Uchunguzi kifani wa pr299

pr299 iligawanywa katika makundi matatu kwa K-Means. Mfululizo wa Figure 9–14 katika chanzo unaonyesha:

1. usambazaji wa awali wa nodi,
2. uchaguzi wa bohari ya mwanzo,
3. uundaji wa makundi matatu,
4. njia za kwanza za TSP,
5. uhamishaji wa eneo la bohari kwa MADO,
6. njia za mwisho zilizotatuliwa kutoka bohari mpya

unaonyesha.

Kwa kuwa chanzo hakitoi koordinati zote na mfuatano wa nodi za njia katika grafu hizi kwa namna ya maandishi/jedwali, ramani bandia ya njia ya pr299 haijachorwa upya ndani ya Verianla.

Uchunguzi huu kifani unaonyesha mabadilishano muhimu yenye malengo mengi: huku urefu wa njia na viashiria vya usawazishaji/uthabiti vinavyotumiwa katika chanzo vikiboreshwa, cluster separability imepungua kidogo na muda wa utekelezaji umeongezeka kidogo.

31. Kwa nini namba za Table 3 na uchunguzi kifani wa pr299 hazifanani kabisa?

Katika Table 3, Total-Sum Distance ya K-Means/pr299 imetolewa kuwa 53.848,32, huku matokeo ya bohari iliyoboreshwa katika uchunguzi kifani wa Table 5 yakiwa 54.533,97. Chanzo hakielezi wazi kwa nini thamani hizi mbili ni tofauti. Marudio tofauti ya hali za kuanzia za K-Means au taratibu za majaribio yanaweza kuwa maelezo yanayowezekana, lakini kwa kuwa chanzo hakithibitishi hilo, Verianla haihusishi sababu hiyo kana kwamba ni ukweli.

32. Lengo la ablation ya Full MADO

Utafiti wa ablation unalenga kutenganisha jukumu la vipengele viwili vya uzani:

• Node-only MADO: ukubwa wa kundi pekee,
• Route-only MADO: mzigo wa njia pekee,
• Full MADO: idadi ya nodi na mzigo wa njia kwa pamoja.

Kwa mujibu wa tafsiri ya waandishi, kipengele cha urefu wa njia hutoa taarifa halisi ya routing burden, huku kipengele cha idadi ya nodi kikitoa kiwango cha jukumu na athari ya udhibiti/usawazishaji.

33. Matokeo kamili ya ablation katika Table 6

Hitimisho muhimu la jedwali hili ni kwamba Full MADO si bora kabisa peke yake katika kila kipimo na kila seti ya data. Kwa mfano, katika rat575, Node-only MADO huzalisha Total-Sum Distance ya chini zaidi, huku Full MADO ikitoa utendaji sawa au bora wa Min-Max na mchanganyiko tofauti wa usawazishaji. Vivyo hivyo, baadhi ya mbinu za tuli ni za haraka zaidi kwa muda wa utekelezaji.

Kwa hiyo, mchango wa MADO si tu “namba ndogo zaidi katika kila safu”; ni kutafuta mabadilishano yanayofaa zaidi kati ya jumla ya njia, njia ndefu zaidi na kiashiria cha usawazishaji kilichotumiwa katika chanzo.

34. Kwa nini vipimo vya umbali vya Table 3/4 na Table 6 havipaswi kulinganishwa moja kwa moja?

Thamani za Table 3 na Table 4 za chanzo na thamani za Table 6 zina vipimo vya namba vilivyo tofauti sana katika baadhi ya hali hata kwa seti za data zenye majina yale yale. Kwa mfano, thamani za Total-Sum za gr229 katika Table 3 ziko takriban katika kiwango cha 1.800–2.300, huku katika Table 6 zikiwa takriban 164.000–192.000.

Chanzo hakitoi maelezo ya ubadilishaji wa umbali, utekelezaji tofauti wa TSPLIB edge-weight au preprocessing nyingine kwa tofauti hii. Kwa hiyo, Verianla haiunganishi majedwali haya kwenye kipimo kimoja cha namba.

35. Ujumbe wa kisayansi wa ablation

Waandishi wanapolinganisha Node-only na Full MADO, wanadai kwamba kipengele cha urefu wa njia hutoa taarifa halisi ya routing-cost ambayo haiwezi kuonekana kwa idadi ya nodi pekee.

Katika ulinganisho wa Route-only na Full MADO, inapendekezwa kwamba kipengele cha idadi ya nodi hutoa fidia ya kiwango na athari ya udhibiti.

Katika mfano wa gr229, Route-only Workload Balance ikiwa 0,861, Full MADO hufikia 0,912. Chanzo kinahusisha hili na kipengele cha idadi ya nodi kuzuia kundi moja lililosambaa sana kijiografia kuvuta bohari kupita kiasi.

36. Matokeo yanayoungwa mkono na utafiti

• MADO inaweza kuathiri matokeo ya njia kwa kubadilisha eneo la bohari ya pamoja katika mifano ya benchmark ya TSPLIB iliyojaribiwa.
• Katika uchunguzi kifani wa pr299, bohari iliyoboreshwa ilizalisha Total-Sum na Min-Max Distance za chini zaidi.
• Uchaguzi wa algoriti ya ugawaji katika makundi hubadilisha matokeo kwa kiasi kikubwa; hakuna mbinu moja ya ugawaji katika makundi iliyo bora katika seti zote za data.
• Bisecting K-Means ilitoa matokeo mazuri ya Total-Sum katika kadhaa ya seti tano za kwanza.
• Full MADO ilipata matokeo ya Total-Sum ya chini zaidi au yanayolingana na ya chini zaidi katika benchmark zote sita za Table 6.
• Full MADO ilitoa hasa katika dsj1000 na pcb1173 thamani za chini zaidi za Total-Sum na Min-Max ikilinganishwa na mbinu za mwanzo za tuli.
• Matokeo ya ablation ya vipengele vya Node-count na route-length yanaunga mkono tafsiri ya waandishi kwamba vipengele hivi vina majukumu yanayokamilishana.
• Mbinu ya divide-and-conquer inayotegemea ugawaji katika makundi huwezesha SD-MTSP kubwa kugawanywa katika matatizo madogo ya TSP.

37. Matokeo ambayo utafiti hauungi mkono moja kwa moja

• Haijaonyeshwa kwamba MADO hupata optimum ya kimataifa katika mifano yote ya SD-MTSP.
• Hakuna uthibitishaji wa uwandani uliofanywa chini ya trafiki ya wakati halisi.
• Nukta za wateja zinazoongezwa au kuondolewa kwa njia ya kubadilika hazijatathminiwa kwa majaribio.
• Kundi la magari yasiyofanana yenye uwezo tofauti halijajaribiwa moja kwa moja.
• Madirisha ya muda na uwezo wa gari si miongoni mwa vikwazo vya modeli kuu ya benchmark.
• Data za gharama, mafuta, muda wa kazi wa dereva au SLA ya uwasilishaji kutoka kampuni halisi ya usafirishaji hazijatathminiwa.
• Thamani ya juu ya Robustness katika grafu haimaanishi uthabiti uliothibitishwa dhidi ya kutokuwa na uhakika katika mazingira halisi ya uwandani.
• Kuonekana takriban kwa mstari kwa grafu ya kiempiria ya muda wa utekelezaji hakuthibitishi kwamba algoriti ina uchangamano wa muda wa mstari katika hali zote.
• Matokeo ya Table 6 hayawezi kuunganishwa moja kwa moja na kipimo cha namba cha Table 3/4 bila maelezo.

38. Mapendekezo ya chanzo yenyewe kwa kazi za baadaye

Waandishi wanasema mbinu inapaswa kuendelezwa katika mazingira yanayobadilika na changamano zaidi. Mielekeo iliyopendekezwa ni:

• kuongeza reinforcement learning au online optimization ili kujibu mabadiliko ya trafiki ya wakati halisi,
• kushughulikia kuongezwa au kuondolewa kwa njia ya kubadilika kwa nukta za wateja/majukumu,
• kuunga mkono aina zisizofanana za wauzaji/magari,
• kuongeza vikwazo halisi vya uendeshaji kama uwezo wa gari,
• kuboresha utaratibu wa uboreshaji wa pamoja kati ya ugawaji katika makundi na upangaji wa njia

kwa namna hii.

Mapendekezo haya ya kazi za baadaye pia yanaonyesha mpaka wa matumizi ya uwandani wa makala ya sasa. Mbinu haiko moja kwa moja katika kiwango cha “mfumo wa usafirishaji uliothibitishwa kikamilifu katika uhandisi”; waandishi pia wanasema maendeleo ya ziada yanahitajika ili kuhama kutoka uwezekano wa kinadharia wa matumizi hadi kiwango cha engineering reliability.

Maelezo ya Chanzo na Mbinu

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

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

Mwandishi wa mawasiliano: Chunlong Fu.

Mchango sawa: Chanzo hakina tamko la mchango sawa.

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

Jarida: Mathematics.

Mchapishaji: MDPI.

Rekodi ya bibliografia: Mathematics 2026, 14(15), 2811.

DOI: 10.3390/math14152811.

Tarehe ya kuwasilishwa: 5 Juni 2026.

Tarehe ya marekebisho: 18 Julai 2026.

Tarehe ya kukubaliwa: 28 Julai 2026.

Tarehe ya kuchapishwa: 5 Agosti 2026.

Kiungo rasmi: Rekodi ya uchapishaji ya MDPI kupitia DOI 10.3390/math14152811.

Aina ya chanzo: Makala asili ya utafiti iliyochapishwa katika jarida la kisayansi lililopitiwa na wataalamu; utafiti wa kimahesabu unaotegemea uboreshaji wa kikombinatoria, ugawaji katika makundi na upangaji wa njia.

Hali ya preprint: Chanzo kilichotolewa ni toleo lililochapishwa la jarida. Hakuna kitambulisho tofauti cha preprint kilichoripotiwa katika PDF.

Leseni: Creative Commons Attribution (CC BY).

Maneno muhimu: SD-MTSP; clustering algorithm; task balancing; depot location optimization.

MSC: 05B05; 90B50.

Programu: Python 3.10, scikit-learn v1.3.0 na OR-Tools v9.10.

Chanzo cha benchmark: TSPLIB.

Seti kuu za kwanza za data: att48, eil76, gr229, pr299 na dsj1000.

Seti za data za ablation: att48, eil76, gr229, rat575, dsj1000 na pcb1173.

Vipimo vya tathmini: Total-Sum Distance, Min-Max Distance, Workload Balance, Cluster Separability, Robustness na Running Time.

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

Upatikanaji wa data: Waandishi wamesema kwamba data za utafiti zinapatikana kwa ufikiaji wazi kwa msingi wa TSPLIB na kwamba wametoa kiungo cha ufikiaji cha GitCode katika sehemu ya Data Availability.

Mgongano wa maslahi: Waandishi hawakuripoti mgongano wa maslahi.

Tamko la matumizi ya akili bandia: Waandishi wameripoti kwamba walitumia ChatGPT-5.4 wakati wa kuandaa makala kwa ajili ya kuboresha sarufi na kuhariri lugha; walipitia na kuhariri wenyewe maudhui ya mwisho na wakachukua wajibu wa maudhui yaliyochapishwa.

Michango ya waandishi: Uundaji wa dhana Qi Jiang; mbinu Jiaxin Zou, Chunlong Fu, Pingli Zheng na Kaiwen Xiao; programu Guofang Liu na Hongxia He; uthibitishaji Jiaxin Zou, Chunlong Fu na Hongxia He; uchambuzi rasmi Guofang Liu na Yang Deng; uchunguzi Chunlong Fu; rasilimali Pingli Zheng na Qi Jiang; uratibu wa data Jiaxin Zou, Pingli Zheng na Kaiwen Xiao; rasimu ya kwanza Jiaxin Zou; mapitio na uhariri Chunlong Fu; uonyeshaji Yang Deng; usimamizi Chunlong Fu na Guofang Liu.

Kutolingana muhimu kwa mbinu 1 — fasili ya uzani: Mlinganyo wa awali (1) hutumia uwiano wa nodi na uwiano wa convex hull. Mtiririko wa baadaye wa Route-Feedback MADO, Algorithm 1 na mjadala wa Table 6 hutumia idadi ya nodi na urefu wa sasa wa njia ya TSP. Chanzo hakiunganishi maelezo haya mawili kwa uhusiano wa wazi wa marekebisho.

Kutolingana muhimu kwa mbinu 2 — ugawaji katika makundi: Maelezo ya awali ya hatua nne yanataja kugawa data tena katika makundi baada ya bohari kusasishwa, huku Figure 2 na Algorithm 1 zikisema kwamba uanachama wa makundi huundwa mara moja na hubaki thabiti katika kipindi chote cha uboreshaji wa bohari.

Kutolingana muhimu kwa kipimo — Workload Balance: Maelezo kabla ya Mlinganyo (7) yanasema kwamba thamani ndogo zinaonyesha usawazishaji bora zaidi. Sehemu ya matokeo, Figure 3 na Table 5–6, kwa upande mwingine, zinafasiri thamani ya juu kuwa bora zaidi. Verianla haijarekebisha mgongano huu kimya kimya.

Maelezo kuhusu wigo wa seti za data: Section 5.1 inafafanua mifano mitano ya benchmark; Table 6 hutumia ulinganisho tofauti wa mifano sita unaojumuisha rat575 na pcb1173 badala ya pr299.

Maelezo kuhusu kipimo cha umbali: Katika Table 3/4 na Table 6, ukubwa wa umbali wa baadhi ya seti za data zenye majina yale yale ya TSPLIB uko katika vipimo tofauti. Chanzo hakitoi ubadilishaji wa wazi wala maelezo ya preprocessing kwa tofauti hii; majedwali hayajaunganishwa moja kwa moja kana kwamba ni seti moja ya data yenye kipimo kimoja.

Maelezo kuhusu namba ya pr299: Katika Table 3, Total-Sum Distance ya K-Means/pr299 ni 53.848,32, huku matokeo ya bohari iliyoboreshwa katika uchunguzi kifani wa Table 5 yakiwa 54.533,97. Chanzo hakielezi wazi sababu ya tofauti hiyo.

Maelezo kuhusu 2-opt: Katika sehemu ya matokeo, inaelezwa kwamba uboreshaji wa ndani wa 2-opt ulijumuishwa katika suluhisho la OR-Tools; hata hivyo, usanidi wa kina wa 2-opt haujatolewa katika sehemu ya mbinu.

Maelezo kuhusu uwezo wa kuzalisha tena: Algorithm 1 inafafanua \(T_{max}\), \(\varepsilon\) na kigezo cha hatua ya awali \(\eta_0\) kama viingizo; chanzo hakiripoti thamani za namba zilizotumika kwa vigezo hivi. Idadi ya Repeated-experiment, random seed na vifaa vya kukokotoa pia havijaripotiwa wazi.

Kikomo cha convergence: Waandishi hawatoi dhamana ya optimum ya kimataifa. State hashing, cycle detection, udhibiti wa projection-stall na mbinu za kupunguza hatua zinalenga kufanya marudio yasitishwe katika matumizi ya vitendo.

Kikomo cha ulimwengu halisi: Utafiti ni uthibitishaji wa benchmark ya TSPLIB. Hakuna uthibitishaji wa kiutendaji wa uwandani uliofanywa kwenye kundi halisi la magari ya usafirishaji, trafiki hai, uwezo wa gari, madirisha ya muda, uingizaji wa wateja unaobadilika na magari yasiyofanana.