Көп салмактуу адаптивдүү депону оптималдаштыруу (Multi-Weight Adaptive Depot Optimization, MADO), бир деполуу көп кыдыруучу сатуучу маселесинде кардар түйүндөрүн кластерлерге бөлүп, ар бир кластерди бир кыдыруучу сатуучуга бекитип жана жалпы депонун жайгашуусун маршруттун натыйжалуулугу менен жумуш жүгүнүн тең салмактуулугун бирге эске алуу менен итеративдүү өзгөрткөн оптималдаштыруу ыкмасы. Изилдөө TSPLIB benchmark маалымат топтомдорунда сегиз түрдүү кластерлөө алгоритмин, OR-Tools негизиндеги TSP чечимин, депонун жайгашуусун оптималдаштырууну жана Total-Sum Distance, Min-Max Distance, Workload Balance, Cluster Separability, Robustness жана Running Time деген алты натыйжалуулук көрсөткүчүн бириктирет.

Ыкманын негизги идеясы чоң SD-MTSP ни түздөн-түз бир бүтүн катары чечүүнүн ордуна кардар түйүндөрүн кластерлерге бөлүп, аны кичирээк TSP көмөкчү маселелерине ажыратуу болуп саналат. Андан кийин жалпы депонун жайгашуусу кластерлердин көлөмүн жана мейкиндик/маршрут жүгүн билдирген салмактардын жардамы менен жаңыртылат. Ар бир талапкер депо үчүн кластер ичиндеги TSP маршруттары кайра чечилип, жаңы жайгашуу маршруттун узундугу жана тең салмактуулук критерийлери боюнча бааланат.

Алгачкы беш маалымат топтомун салыштырууда att48, eil76, gr229, pr299 жана dsj1000 колдонулган. Total-Sum Distance боюнча att48 үчүн BIRCH, gr229 үчүн Fuzzy C-Means; eil76, pr299 жана dsj1000 үчүн Bisecting K-Means эң төмөн маанилерди берген. Бул жыйынтык бир да кластерлөө алгоритми бардык маалымат бөлүштүрүүлөрүндө үстөм эмес экенин көрсөтөт.

pr299 учурдук изилдөөсүндө баштапкы депо менен Total-Sum Distance 55.145,51 болсо, оптималдаштырылган деподо 54.533,97 ге; Min-Max Distance 21.130,08 ден 20.624,04 кө төмөндөгөн. Булак ошол эле салыштырууда Workload Balance мааниси 0,98 ден 0,99 га жана Robustness мааниси 0,88 ден 0,90 га жогорулаганын; Cluster Separability 0,24 төн 0,21 ге төмөндөгөнүн жана иштөө убактысы 7,71 секунддан 7,87 секундга өскөнүн билдирет.

Кийинки алты маалымат топтомдуу абляциялык изилдөөдө Full MADO att48, eil76, gr229, rat575, dsj1000 жана pcb1173 боюнча Geometric, Midpoint, S-shaped, Node-only MADO жана Route-only MADO ыкмалары менен салыштырылган. Булак Full MADO алты мисалдын баарында эң төмөн же тең эң төмөн Total-Sum Distance; бешөөндө эң төмөн же тең эң төмөн Min-Max Distance алганын билдирет. dsj1000 жана pcb1173 үчүн эң жакшы статикалык баштапкы стратегияга салыштырмалуу Total-Sum Distance төмөндөшү тиешелүүлүгүнө жараша болжол менен %2,3 жана %1,6 деп маалымдалган.

Ошентсе да, изилдөө реалдуу бөлүштүрүү автопаркы, реалдуу жол кыймылы, унаа сыйымдуулугу, убакыт терезеси же динамикалык буйрутма агымы боюнча талаалык текшерүү эмес. Жыйынтыктар TSPLIB негизиндеги эсептөө benchmark шарттарында алынган. Булак ошондой эле ыкманын сүрөттөлүшүнүн ар башка бөлүктөрүндө салмакты эсептөө, кластер мүчөлүктөрү итерация учурунда туруктуу калабы же жокпу жана Workload Balance метрикасынын жогорку/төмөн маанисин чечмелөө боюнча толук дал келбеген билдирүүлөрдү камтыйт. Ошондуктан бул жагдайлар такталгандай көрсөтүлбөшү керек.

1. Кыдыруучу сатуучу маселеси деген эмне?

Traveling Salesman Problem (TSP), сатуучу же унаа белгилүү шаарлардын ар бирине бир жолу барып, баштапкы чекитке кайтып келишин жана жалпы жол чыгымын мүмкүн болушунча азайтууну көздөгөн классикалык комбинатордук оптималдаштыруу маселеси.

Бир маршрут:

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

түрүндө жабык турду түзөт.

TSP нин маанилүү өзгөчөлүгү — чечим мейкиндиги шаарлардын саны көбөйгөн сайын абдан тез өсөт. \(n\) шаар үчүн мүмкүн болгон иреттөөлөрдүн саны факториалдык өсүшкө ээ. Ошондуктан түйүндөрдүн саны жүздөгөн же миңдеген деңгээлге жеткенде бардык маршруттарды бирден сынап чыгуу практикалык эмес.

2. MTSP деген эмне?

Multiple Traveling Salesman Problem (MTSP), TSP нин бир нече кыдыруучу сатуучу же операциялык бирдиги бар кеңейтилген түрү. Бир адам бардык чекиттерге баргандын ордуна тапшырмалар бир нече сатуучунун арасында бөлүштүрүлөт.

Бул жерде жалпы аралык кыска болушу гана жетишсиз болушу мүмкүн. Мисалы, төрт унаанын үчөө кыска маршруттарда иштеп, төртүнчү унаа бардык алыскы чекиттерди тейлөөгө туура келсе, жалпы жол кабыл алынарлык болгон күндө да тапшырмалардын бөлүштүрүлүшү операциялык жактан тең салмаксыз болушу мүмкүн.

3. SD-MTSP деген эмне?

Single-Depot Multiple Traveling Salesman Problem (SD-MTSP), бардык кыдыруучу сатуучулар бир жалпы деподон чыгып, өздөрүнө бекитилген кардар түйүндөрүнө барып жана кайра ошол эле депого кайта турган MTSP түрү.

Демек, эки чечим бири-бири менен байланыштуу:

• Кайсы кардар кайсы сатуучуга бекитилери,
• жалпы депо кайда жайгашары.

Депонун жайгашуусу өзгөргөндө ар бир сатуучунун маршрутунун башталыш жана аяктоо байланыштары да өзгөрөт. Ошентип, жалпы аралык жана эң узун маршрут бирге өзгөрүшү мүмкүн.

4. Депо эмне үчүн геометриялык борборго гана жайгаштырылбайт?

Кардар чекиттеринин геометриялык борборун алуу жөнөкөй жана тез; бирок геометриялык борбор кардар кластерлеринде канча түйүн бар экенин, кластерлер канчалык жайылганын же реалдуу TSP маршруттары канчалык узун экенин түздөн-түз эске албайт.

Мисалы, эки кластердин борборлору деподон бирдей аралыкта болсо да, бир кластерде 20, экинчисинде 100 кардар болушу мүмкүн. Ошол сыяктуу эле кардарлардын саны бирдей болгон эки кластердин бири тар аймакта, экинчиси кең географиялык мейкиндикте таралышы мүмкүн.

MADO нун негизги мотивациясы ушул айырмачылыктарды депону жаңыртууга салмак катары кошуу болуп саналат.

5. Кластерлөө эмне үчүн колдонулат?

Кластерлөө чоң SD-MTSP маселесин кичирээк көмөкчү маселелерге бөлүү үчүн колдонулат. Ар бир кластер бир кыдыруучу сатуучуга бекитилет жана кластер ичиндеги маршрут өзүнчө TSP катары чечилет.

Булак статикалык жана бирдей көлөмдөгү бөлүү үчүн \(n=k\,m\) божомолунун алдында толук масштабдагы маселенин теориялык факториалдык түзүлүшүн:

\[ O(n!) \]

ордуна болжол менен:

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

түрүндө карайт.

Бул жерде:

• \(n\): түйүндөрдүн жалпы саны,
• \(k\): кластерлердин же сатуучулардын саны,
• \(m=n/k\): бир кластерге туура келген түйүндөрдүн орточо саны.

Бул туюнтма чоң маселени кичинекей TSP ларга бөлүүнүн теориялык негиздемесин түшүндүрөт. Бирок изилдөөдөгү реалдуу TSP көмөкчү маселелери OR-Tools менен чечилет; ошондуктан \(O(m!)\) туюнтмасы колдонулган OR-Tools эвристикасынын реалдуу иштөө убактысынын татаалдыгы катары чечмеленбеши керек.

6. Изилдөөдө салыштырылган кластерлөө алгоритмдери

MADO депонун жайгашуусун кантип жаңыртат?

MADO жалпы деподон ар бир кластердин борборуна багытталган векторлорду кластердин тапшырма көлөмүн жана мейкиндик/маршрут жүгүн көрсөткөн салмактар менен бириктирип, депонун кыймыл багытын түзөт; бирок булакта бул экинчи салмак эрте ыкма бөлүмүндө томпок кабык, кийинки Route-Feedback MADO агымында болсо учурдагы TSP маршрутунун узундугу катары аныкталгандыктан, эки сүрөттөмө бир эле математикалык алгоритм деп болжолдонбошу керек.

7. Алгачкы депо кантип тандалат?

Булакта адегенде бардык кардар түйүндөрүнүн геометриялык centroid-и эсептелет. Бул чекит теориялык депо деп аталат.

Бирок реалдуу депонун жайгашуусу маселедеги ылайыктуу үлгү түйүндөрүнүн бири болушу талап кылынгандыктан, теориялык centroid-ке эң жакын үлгү чекити тандалып, алгачкы реалдуу депо жайгашуусу катары колдонулат.

8. Теңдеме (1): Эрте MADO салмакталган багыт вектору

Булактын ыкма бөлүмүндөгү Теңдеме (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} \]

Бул жерде:

• \(V\): депонун жалпы абал/жайгашуу өзгөрүү вектору,
• \(N\): кардар түйүндөрүнүн жалпы саны,
• \(N(C_i)\): \(i\)-кластердеги кардар түйүндөрүнүн саны,
• \(L_i\): бул эрте аныктамада \(i\)-кластердин томпок кабыгы,
• \(L\): бардык кластерлердин томпок кабыктарынын суммасы,
• \(V_i\): учурдагы деподон \(i\)-кластердин борборуна багытталган вектор.

\(N(C_i)/N\) жана \(L_i/L\) өлчөмсүз катыштар. Бул эки катыш көбөйтүлгөндө кайра эле өлчөмсүз салмак алынат. Бул салмак \(V_i\) жайгашуу векторуна көбөйтүлгөндүктөн, натыйжа \(V\) жайгашуу координаттары менен бирдей өлчөмгө ээ болот.

Түйүндөрдүн катышы чоң болгондо тапшырмалары көп кластердин депого тийгизген таасири өсөт. Томпок кабыктын катышы чоң болгондо мейкиндик жактан кеңири тараган кластердин таасири өсөт.

Булак реалдуу TSP маршрутунун узундугун бул эрте формулада колдонбоосун маршрут узундугу депонун жайгашуусуна ансыз да көз каранды болгондугу жана бул жаңыртуу учурунда циклдик көз карандылыкты күчөтүшү мүмкүн экендиги менен түшүндүрөт.

9. Теңдеме (2): Жаңы депо

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

Бул теңдеме салмакталган багыт векторунун учурдагы депо координатасына кошулушун билдирет. \(V\) нөлгө жакындаган сайын сунушталган депо жылышы кичирейет.

10. Теңдеме (3): Эрте токтотуунун аныктамасы

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

Булактын эрте төрт кадамдуу сүрөттөмөсүндө жаңы депо мурунку депо менен бир эле үлгү түйүнүнө проекцияланса, алгоритм токтотулат.

Бирок кийинки Algorithm 1 мындан кеңири токтотуу логикасын колдонот: депо өзгөрбөсө, кадам өлчөмү өтө кичирейсе, цикл же кайталанган абал аныкталса же максималдуу итерациялар санына жетсе, алгоритм токтойт.

11. Булактын кийинки Route-Feedback MADO аныктамасы

Макаланын кийинки сегиз баскычтуу агымы жана Algorithm 1 жаңыртуу механизмин башкача сүрөттөйт. Бул жерде кластерлер бир жолу түзүлөт жана депону оптималдаштыруу бою туруктуу кармалат. Ар бир итерацияда салмактар:

• кластер түйүндөрүнүн саны \(n_i\),
• учурдагы деподо эсептелген TSP маршрутунун узундугу \(L_i^{(t)}\)

колдонуу менен түзүлөт.

Булак ошол эле бөлүмдө талапкер депону жаңыртууну:

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

түрүндө берет.

Бул жерде:

• \(p^{(t)}\): \(t\)-итерациядагы депо координатасы,
• \(D^{(t)}\): синтезделген депону жаңыртуу багыты,
• \(\|D^{(t)}\|_2\): багыт векторунун Евклид нормасы,
• \(s_t\): адаптивдүү натыйжалуу кадам өлчөмү,
• \(\varepsilon\): нөлгө бөлүү же өтө кичине норма маселеси үчүн колдонулган толеранттуулук мүчөсү.

Векторду анын нормасына бөлүү багыт жөнүндө маалыматты чоң даражада нормалдаштырат; реалдуу жылыштын чоңдугун \(s_t\) аныктайт.

Бирок булак \(T_{max}\), \(\varepsilon\) жана баштапкы кадам \(\eta_0\) үчүн сандык маанилерди бербейт. Талапкерди кабыл алууда “алдын ала аныкталган lexicographic objective” колдонулары айтылат, бирок бул лексикографиялык кабыл алуу эрежесинин так математикалык артыкчылык ирети өзүнчө теңдеме түрүндө маалымдалбайт.

12. Эки ыкманын сүрөттөмөсүнүн айырмасы эмне үчүн маанилүү?

Томпок кабык кластердин геометриялык жайылышына гана көз каранды жана депо жылганда түздөн-түз өзгөрбөйт. TSP маршрутунун узундугу болсо учурдагы депонун жайгашуусуна көз каранды жана депо ар бир өзгөргөндөн кийин кайра эсептелиши мүмкүн.

Демек:

Түйүндөрдүн саны + томпок кабык

менен:

Түйүндөрдүн саны + учурдагы TSP маршрутунун узундугу

бир эле оптималдаштыруу эрежеси эмес.

Булак Table 6 абляциясында “Node-only”, “Route-only” жана “Full MADO” деген терминдерди колдонуп, талкууда route-length мүчөсү реалдуу routing burden маалыматын берерин түшүндүргөндүктөн, бул кийинки эксперименттер route-feedback сүрөттөмөсүнө тиешелүү. Ошентсе да жарыяланган эрте Теңдеме (1) сакталууга жана көз жаздымда калбоого тийиш.

13. Кластерлер кайра түзүлөбү?

Булак бул жерде да эки башка баяндоону камтыйт. Эрте төрт кадамдуу бөлүм жаңы теориялык депо аныкталгандан кийин “cluster the dataset again” деген сөз айкашын колдонот. Ал эми кийинки 2-сүрөттүн түшүндүрмөсү жана Algorithm 1 кластерлөө бир жолу гана жүргүзүлөрүн жана кластер мүчөлүктөрү депону оптималдаштыруу бою туруктуу каларын ачык айтат.

Ошондуктан Verianla булактын ушул эки баяндоосунун бирин унчукпай алып салып, алгоритмди кайра аныктабайт. Кайра өндүрүлө турган ишке ашырууда кайсы вариант негиз катары алынары өзүнчө такталышы керек.

14. Циклдин алдын алуу жана токтотуу

Депо талапкери дайыма ылайыктуу кардар түйүндөрүнө проекцияланганда алгоритм эки же андан көп түйүндүн ортосунда ары-бери өтүп калышы мүмкүн. Булак мунун алдын алуу үчүн:

• барып өткөн депо абалдарын hash аркылуу жазып туруу,
• кайталанган абалды аныктоо,
• эки-абалдуу туруктуу циклди аныктоо,
• projection stall аныктоо,
• талапкер жакшырууну бербесе кадамды кичирейтүү/rejection damping,
• minimum displacement,
• максималдуу итерация чеги

сыяктуу коопсуздук механизмдерин аныктайт.

Авторлор бул механизмдер алгоритмдин практикада чектелген сандагы итерациялардан кийин токтошун камсыздай турганын билдиришет. Бирок булак ачык түрдө глобалдык оптимумга жакындашууга кепилдик бербейт.

15. Бөл-жана-башкар татаалдыгы

Булактын толук MADO алкагы үчүн берген жалпы татаалдык туюнтмасы:

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

түрүндө.

Бул жерде:

• \(n\): түйүндөрдүн жалпы саны,
• \(k\): кластерлердин саны,
• \(I_c\): кластерлөө ыкмасынын ички итерацияларынын саны,
• \(T\): MADO депону жаңыртуу итерацияларынын саны,
• \(m=n/k\): бир кластерге туура келген түйүндөрдүн орточо саны,
• \(f(m)\): \(m\) түйүндүү бир TSP көмөкчү маселесин чечүүнүн наркы.

Булак \(T\) практикада кичине туруктуу сан болуп калат деп болжолдоп, депону оптималдаштыруу жогорку даражадагы кошумча жүк жаратпайт деп негиздейт. Ошол эле учурда \(f(m)\) колдонулган OR-Tools жөндөөлөрүнө жана чечүү стратегиясына көз каранды экенин унутпоо керек.

Workload Balance мааниси кантип чечмелениши керек?

Булактын жарыяланган версиясы бул жагынан ички жактан ырааттуу эмес: ыкманын тексти Теңдеме (7) үчүн кичине маанини жакшыраак тең салмак деп кабыл алса, жыйынтыктар бөлүмү жана таблицалар жогорураак Workload Balance маанисин жакшыраак тең салмак катары чечмелейт; ошондуктан белгилүү бир маанинин багытын булакты оңдогондой тактап коюунун ордуна формуланы, таблица жыйынтыктарын жана ушул отчеттук дал келбестикти чогуу кароо керек.

16. Теңдеме (4): Бир кластердин жабык TSP маршрут узундугу

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

\(D_k\), \(k\)-кластерге бекитилген сатуучунун жабык тур узундугу. \(d(v_i,v_{i+1})\) удаалаш эки түйүндүн ортосундагы аралык. Акыркы мүчө акыркы түйүндөн баштапкы түйүнгө кайтууну кошуп, маршрутту жабат.

17. Теңдеме (5): Min-Max Distance

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

Бул метрика бардык сатуучу маршруттарынын ичинен эң узун маршрутту тандайт. Максат бул максималдуу маанини мүмкүн болушунча азайтуу.

Мисалы, үч маршрут 100, 105 жана 250 бирдик болсо, Min-Max Distance 250 ге барабар. Жалпы жол кабыл алынарлык болсо да, бир сатуучуга 250 бирдик ашыкча жүк түшүшү мүмкүн. Ошондуктан Min-Max метрикасы эң көп жүктөлгөн бирдикти көзөмөлдөө жагынан маанилүү.

18. Теңдеме (6): Total-Sum Distance

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

Total-Sum бардык сатуучулар басып өткөн маршруттардын узундуктарын кошот. Кичине маани жалпы операциялык аралык төмөн экенин көрсөтөт.

Min-Max жана Total-Sum бир эле максат эмес. Бир чечим жалпы аралыкты бир аз көбөйтүп, ошол эле учурда эң узун маршрутту олуттуу кыскартышы мүмкүн. MADO нун көп максаттуу тең салмак маселеси ушул карама-каршылыктан келип чыгат.

19. Теңдеме (7) жана (8): Workload Balance

Булакта:

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

жана:

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

берилген.

\(\bar D\), бардык маршрут узундуктарынын орточо мааниси. Алым — маршрут узундуктарынын орточодон квадраттык четтөөлөрүнүн орточосу. Бөлүм болсо квадраттык четтөөлөрдүн эң чоңу.

Алым да, бөлүм да аралыктын квадраты бирдигинде; ошондуктан катыш өлчөмсүз.

Бирок бул нормалдаштыруу маанилүү математикалык натыйжа берет: бардык четтөөлөр бир эле коэффициент менен кичирейсе же чоңойсо, алым менен бөлүм ошол коэффициенттин квадратына өзгөрүп, катыш өзгөрбөй калышы мүмкүн. Ошондуктан Теңдеме (7) маршрут айырмачылыктарынын абсолюттук чоңдугун өзүнчө өлчөгөн классикалык дисперсия же стандарттык четтөө эмес.

Маршруттар толугу менен тең болгондо бардык \(D_k-\bar D\) маанилери нөл болгондуктан, жарыяланган формула теориялык жактан \(0/0\) абалына келет. Булак бул чектик абал үчүн өзүнчө аныктама бербейт.

Ыкманын түшүндүрмөсү “кичине маани = жакшыраак тең салмак” десе, Figure 3 түшүндүрмөсү “жогорку маани = жакшыраак тең салмак” дейт жана Table 5 те 0,98 → 0,99 өзгөрүүсү жакшыруу катары чечмеленет. Ошондуктан жыйынтык таблицаларындагы Workload Balance маанилери булак авторлорунун жыйынтыктар бөлүмүндөгү чечмелөө багыты менен берилген, бирок формула менен тексттин ортосундагы карама-каршылык ачык калтырылган.

20. Теңдеме (9) жана (10): Silhouette / Cluster Separability

Булак жалпы silhouette упайын:

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

жана бир чекит үчүн silhouette маанисин:

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

түрүндө берет.

\(a(k)\), чекиттин өз кластериндеги башка чекиттерге чейинки орточо аралыгы. Кластер ичиндеги чекиттер бири-бирине жакын болсо, \(a(k)\) азаят.

\(b(k)\), чекиттин башка кластерлердин ар бирине чейинки орточо аралыктарынын эң кичине мааниси. Башка кластерлер жакшы бөлүнгөн болсо, \(b(k)\) чоңураак болушу мүмкүн.

Silhouette мааниси −1 менен +1 дин ортосунда:

• +1 ге жакындашы: компакттуураак жана жакшыраак бөлүнгөн кластер,
• 0 чамасында: кластерлердин чек арасында же бири-бирин басып калууга жакын түзүм,
• терс маани: чекит башка кластерге жакыныраак болушу мүмкүн экенин билдирген түзүм.

Булакта dsj1000 маалымат топтому айкын кластерленген мейкиндик түзүмүнө байланыштуу эң жогорку separability маанилерин көрсөтөрү айтылат.

21. Теңдеме (11) жана (12): Robustness

Булак туруктуулук өлчөмүн:

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

жана орточо маанини:

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

деп аныктайт.

Бөлчөктүн ичиндеги түзүм стандарттык четтөөнүн орточо мааниге катышына окшош. Булак анын алдына \(1-\) кошкону үчүн өзгөрмөлүүлүк азайган сайын упай 1 ге жакындайт. Демек, бул жерде “CV” аталышы колдонулган менен, жарыяланган өлчөм классикалык coefficient of variation өзү эмес, 1 минус нормалдаштырылган өзгөрмөлүүлүк түрүндөгү туруктуулук упайы.

Булак жыйынтыктар бөлүмүндө бардык маалымат топтомдорундагы орточо Robustness мааниси болжол менен 0,81 экенин билдирет.

Бирок кайталанган эксперименттердин саны \(T\) нин так сандык мааниси жана колдонулган random seed булактын ыкма бөлүмүндө ачык билдирилген эмес.

22. Теңдеме (13): Иштөө убактысы

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

Бул метрика алгоритм башталгандан акыркы чечим чыккыча өткөн дубал сааты боюнча убакыт. Анын бирдиги секунд.

Булак түйүндөрдүн саны көбөйгөн сайын иштетүү убактысы жалпысынан өсөрүн жана эксперимент графигинде болжол менен сызыктуу тенденция байкалганын билдирет. Бул байкоо теориялык татаалдыктын математикалык далили эмес; билдирилген benchmark шарттарындагы эмпирикалык иштөө убактысынын тенденциясы.

Изилдөөнүн ыкмасы жана жыйынтыктары

23. Маалымат топтомдору

Алгачкы негизги салыштырууда беш TSPLIB benchmark мисалы колдонулган:

pr299 өзгөчө визуалдык учурдук изилдөө үчүн тандалган. Авторлор муну орто масштабда болгону, мейкиндик түзүмү депонун жайгашуусунун таасирин визуалдаштырууга ылайыктуу болгону жана жалпы аралык менен жумуш жүгүнүн тең салмактуулугунун ортосундагы компромиссти көрсөтө алганы үчүн тандашканын билдиришет.

24. Программалык камсыздоо инфраструктурасы

Эксперименттер Python 3.10 менен ишке ашырылган.

Кластерлөө алгоритмдери:

scikit-learn v1.3.0

менен; TSP көмөкчү маселелери:

OR-Tools v9.10

менен чечилген.

Булактын жыйынтыктар бөлүмүндө 2-opt локалдык оптималдаштыруу алгоритми да айтылат. Бирок 2-opt ыкма чынжырында так кайсы жерде чакырылары, итерация чеги же издөө параметрлери өзүнчө билдирилген эмес.

Булак колдонулган CPU/GPU моделин, операциялык системаны, RAM көлөмүн жана random seed маалыматын билдирбейт. Бул иштөө убактысынын жыйынтыктарын башка системаларда так кайра өндүрүүнү чектейт.

25. Сегиз баскычтуу негизги чечим агымы

1. Киргизүү: TSPLIB түйүн координаттары, аралык маалыматы жана сатуучу/кластер саны \(k\) жүктөлөт.
2. Кластерлөө: Түйүндөр тандалган алгоритм менен \(k\) кластерге бөлүнөт.
3. Алгачкы депо: Бардык түйүндөрдүн геометриялык centroid-и табылып, эң жакын ылайыктуу түйүнгө проекцияланат.
4. Алгачкы TSP чечими: Ар бир кластердин башталыш жана аяктоо чекити жалпы депо боло тургандай маршрут чечилет.
5. MADO жаңыртуусу: Динамикалык салмактар менен депону жаңыртуу багыты түзүлүп, талапкер депо эсептелет.
6. Кайра баалоо: Талапкер депо үчүн бардык кластер маршруттары кайра чечилет; Total-Sum, Min-Max жана маршрут бөлүштүрүлүшү бааланат.
7. Натыйжалуулукту баалоо: Алты метрика эсептелет.
8. Чыгыш: Best-so-far депо, маршруттар жана натыйжалуулук өлчөмдөрү кайтарылат.

26. Алгачкы беш маалымат топтомундагы Total-Sum жыйынтыктары

Bisecting K-Means айрыкча eil76, pr299 жана dsj1000 үчүн Total-Sum боюнча эң төмөн жыйынтык берген. Ошентсе да att48 жана gr229 үчүн башка алгоритмдер жакшыраак болушу кластерлөө ыкмасы маалыматтын бөлүштүрүлүшүнө көз каранды экенин көрсөтөт.

27. Алгачкы беш маалымат топтомундагы Min-Max жыйынтыктары

Бул таблица менен Total-Sum таблицасынын жеңүүчүлөрү бирдей эмес. Бул жалпы операциялык аралыкты азайтуу менен бир сатуучуга туура келген эң узун маршрутту азайтуу ар башка максат экенин түздөн-түз көрсөтөт.

28. Workload Balance, separability жана robustness графиктеринин негизги билдирүүсү

Булак Figure 3 те Workload Balance маанилеринин көбү жогорку деңгээлде экенин жана бардык алгоритм/маалымат топтому комбинацияларында орточо маани болжол менен 0,95 экенин билдирет. Мурда түшүндүрүлгөн формула-багыт карама-каршылыгына байланыштуу бул график жыйынтыктар бөлүмүндө колдонулган “жогорку маани жакшыраак” багытында чечмеленет.

Figure 4 те Cluster Separability маалымат топтомуна күчтүү көз каранды. dsj1000 айкын кластерленген мейкиндик түзүмүнө байланыштуу эң жогорку silhouette маанилерин көрсөтөт.

Figure 5 үчүн булак орточо Robustness мааниси болжол менен 0,81 экенин билдирет. Бирок айрым алгоритмдердин белгилүү маалымат топтомдорундагы упайлары кыйла төмөндөйт; демек, орточо маани ар бир алгоритм бирдей туруктуулукту көрсөтөт дегенди билдирбейт.

29. Радар графиги жана heatmap кантип чечмелениши керек?

Булак алты метриканы чогуу көрсөтүү үчүн радар графиктерин жана орточо рейтингдерден турган heatmap колдонгон.

Радар графигинин түшүндүрмөсүндө “K-Means эң чоң полигон аянтына ээ” деген билдирүүдөн дароо кийин Agglomerative үчүн да “эң чоң полигон аянтына ээ” деп айтылат. Ошол эле бөлүм Spectral жөнүндө оң жана “worst comprehensive performance” багытындагы бири-бирине дал келбеген билдирүүлөрдү камтыйт.

Ошондуктан Verianla радар графигинен бирдиктүү универсалдуу “эң жакшы алгоритм” деген жыйынтык чыгарбайт.

Булактын heatmap талкуусунун этият жыйынтыгын сактоого болот: бир да кластерлөө алгоритми бардык маалымат топтомдору жана бардык өлчөмдөр боюнча абсолюттук үстөм эмес. Алгоритмди тандоо маалыматтын бөлүштүрүлүшүнө жана кайсы метрика артыкчылыктуу экенине көз каранды.

30. pr299 учурдук изилдөөсү

pr299 K-Means менен үч кластерге бөлүнгөн. Булактын 9–14-сүрөттөрүнүн ырааты:

1. баштапкы түйүн бөлүштүрүлүшүн,
2. баштапкы депонун тандалышын,
3. үч кластердин түзүлүшүн,
4. алгачкы TSP маршруттарын,
5. MADO менен депонун жайгашуусунун жылдырылышын,
6. жаңы деподон чечилген акыркы маршруттарды

көрсөтөт.

Булак бул графиктердин бардык координаттарын жана маршрут түйүндөрүнүн иретин текст/таблица түрүндө бербегендиктен, Verianla ичинде жасалма pr299 маршрут картасы кайра тартылган эмес.

Бул учурдук изилдөө маанилүү көп максаттуу компромиссти көрсөтөт: маршрут узундугу жана булакта колдонулган тең салмак/туруктуулук көрсөткүчтөрү жакшырганда cluster separability бир аз төмөндөп, иштөө убактысы бир аз өскөн.

31. Эмне үчүн Table 3 менен pr299 учурдук сандары толук бирдей эмес?

Table 3 те K-Means/pr299 үчүн Total-Sum Distance 53.848,32 деп берилсе, Table 5 учурдук изилдөөсүнүн оптималдаштырылган депо жыйынтыгы 54.533,97. Булак бул эки маанинин эмне үчүн айырмаланарын ачык түшүндүрбөйт. K-Means баштапкы шарттарынын же эксперименттик процедуранын башка кайталануулары мүмкүн болгон түшүндүрмө болушу мүмкүн, бирок булак муну ырастабагандыктан Verianla мындай себепти факт катары көрсөтпөйт.

32. Full MADO абляциясынын максаты

Абляциялык изилдөө эки салмак компонентинин милдетин ажыратууну көздөйт:

• Node-only MADO: кластердин көлөмү гана,
• Route-only MADO: маршрут жүгү гана,
• Full MADO: түйүндөрдүн саны жана маршрут жүгү чогуу.

Авторлордун чечмелөөсү боюнча маршрут узундугу мүчөсү реалдуу routing burden маалыматын, ал эми түйүндөрдүн саны мүчөсү тапшырманын масштабын жана жөнгө салуучу/тең салмактоочу таасирди камсыз кылат.

33. Table 6 дагы толук абляция жыйынтыктары

Бул таблицанын маанилүү жыйынтыгы — Full MADO ар бир өлчөмдө жана ар бир маалымат топтомунда жалгыз абсолюттук үстөм эмес. Мисалы, rat575 үчүн Node-only MADO төмөнүрөөк Total-Sum Distance берсе, Full MADO ошол эле же жакшыраак Min-Max натыйжалуулугун жана башка тең салмак комбинациясын камсыз кылат. Ошол сыяктуу айрым статикалык ыкмалар иштөө убактысы боюнча ылдамыраак.

Демек, MADO нун салымы жөн гана “ар бир мамычадагы эң кичине сан” эмес; ал маршруттардын суммасы, эң узун маршрут жана булакта колдонулган тең салмак көрсөткүчүнүн ортосунда ылайыктуураак компромиссти издейт.

34. Table 3/4 менен Table 6 аралык масштабдары эмне үчүн түз салыштырылбашы керек?

Булактын Table 3 жана Table 4 маанилери менен Table 6 маанилери бирдей аталыштагы маалымат топтомдорунда да кээ бир учурларда абдан башка сандык масштабдарга ээ. Мисалы, gr229 Total-Sum маанилери Table 3 те болжол менен 1.800–2.300 аралыгында болсо, Table 6 да болжол менен 164.000–192.000 деңгээлинде.

Булак бул айырма үчүн аралыкты өзгөртүү, башка TSPLIB edge-weight колдонулушу же башка preprocessing түшүндүрмөсүн бербейт. Ошондуктан Verianla бул таблицаларды бир жалпы сандык масштабда бириктирбейт.

35. Абляциянын илимий билдирүүсү

Авторлор Node-only менен Full MADO ну салыштырганда маршрут узундугу мүчөсү түйүндөрдүн санынан гана көрүнбөгөн реалдуу routing-cost маалыматын берерин негиздешет.

Route-only менен Full MADO салыштыруусунда болсо түйүндөрдүн саны мүчөсү масштабды компенсациялоо жана жөнгө салуучу таасир берет деп сунушталат.

gr229 мисалында Route-only Workload Balance 0,861 болсо, Full MADO 0,912 ге жеткен. Булак муну мейкиндик жактан кең бир кластердин депону ашыкча өзүнө тартуусун түйүндөрдүн саны мүчөсү чектегени менен байланыштырат.

36. Изилдөө колдогон жыйынтыктар

• MADO текшерилген TSPLIB benchmark мисалдарында жалпы депонун жайгашуусун өзгөртүү аркылуу маршрут жыйынтыктарына таасир бере алат.
• pr299 учурдук изилдөөсүндө оптималдаштырылган депо төмөнүрөөк Total-Sum жана Min-Max Distance берген.
• Кластерлөө алгоритмин тандоо жыйынтыктарды олуттуу өзгөртөт; бир да кластерлөө ыкмасы бардык маалымат топтомдорунда үстөм эмес.
• Bisecting K-Means алгачкы беш маалымат топтомунун бир нечесинде Total-Sum боюнча күчтүү жыйынтык берген.
• Full MADO Table 6 дагы алты benchmark дын баарында минималдуу же тең минималдуу Total-Sum жыйынтыгын алган.
• Full MADO айрыкча dsj1000 жана pcb1173 үчүн статикалык баштапкы ыкмаларга салыштырмалуу төмөнүрөөк Total-Sum жана Min-Max маанилерин камсыз кылган.
• Node-count жана route-length компоненттеринин абляция жыйынтыктары алардын бири-бирин толуктаган ролдору бар деген авторлордун чечмелөөсүн колдойт.
• Кластерлөөгө негизделген бөл-жана-башкар ыкмасы чоң SD-MTSP ни кичирээк TSP көмөкчү маселелерине бөлүүгө мүмкүндүк берет.

37. Изилдөө түздөн-түз колдобогон жыйынтыктар

• MADO бардык SD-MTSP мисалдарында глобалдык оптимумду табары көрсөтүлгөн эмес.
• Реалдуу убакыттагы жол кыймылы шартында талаалык текшерүү жүргүзүлгөн эмес.
• Динамикалык түрдө кошулган же өчүрүлгөн кардар чекиттери эксперименттик түрдө бааланган эмес.
• Ар кандай сыйымдуулуктагы унаалардан турган гетерогендүү парк түздөн-түз сыналган эмес.
• Убакыт терезелери жана унаа сыйымдуулугу негизги benchmark моделинин чектөөлөрүнүн арасында эмес.
• Реалдуу логистикалык компанияга тиешелүү чыгым, күйүүчү май, айдоочунун иш убактысы же жеткирүү SLA маалыматтары бааланган эмес.
• Графиктердеги жогорку Robustness мааниси реалдуу талаа белгисиздиктерине каршы далилденген туруктуулукту билдирбейт.
• Эмпирикалык иштөө убактысынын графиги болжол менен сызыктуу көрүнүшү алгоритм бардык шарттарда сызыктуу убакыт татаалдыгына ээ экенин далилдебейт.
• Table 6 жыйынтыктарын Table 3/4 түн сандык масштабы менен түшүндүрмөсүз түз бириктирүүгө болбойт.

38. Булактын өзүнүн келечектеги изилдөө сунуштары

Авторлор ыкманы кыйла татаал динамикалык чөйрөлөрдө өнүктүрүү керек экенин билдиришет. Сунушталган багыттар:

• реалдуу убакыттагы жол кыймылынын өзгөрүүлөрүнө жооп берүү үчүн reinforcement learning же online optimization кошуу,
• кардар/тапшырма чекиттеринин динамикалык түрдө кошулушун же алынып салынышын кароо,
• гетерогендүү сатуучу/унаа түрлөрүн колдоо,
• унаа сыйымдуулугу сыяктуу реалдуу операциялык чектөөлөрдү кошуу,
• кластерлөө менен маршрут пландаштыруунун ортосундагы биргелешкен оптималдаштыруу механизмин өркүндөтүү

түрүндө.

Бул келечектеги изилдөө сунуштары ошол эле учурда учурдагы макаланын талаада колдонулушуна коюлган чекти көрсөтөт. Ыкма түздөн-түз «инженерияда толук текшерилген логистикалык система» деңгээлинде эмес; авторлор да теориялык колдонмолуулуктан engineering reliability деңгээлине өтүү үчүн кошумча иштеп чыгуу керек экенин белгилешет.

Булак жана Ыкма Жөнүндө Эскертүү

Түпнуска аталышы: A Clustering-Based Multi-Task Balancing Method for Depot Optimization in Single-Depot Multiple Traveling Salesman Problems

Авторлор: Chunlong Fu, Jiaxin Zou, Guofang Liu, Pingli Zheng, Kaiwen Xiao, Yang Deng, Hongxia He жана Qi Jiang.

Жооптуу автор: Chunlong Fu.

Тең салым: Булакта тең салым жөнүндө билдирүү жок.

Мекеме: Department of Computer Science, Sichuan University Jinjiang College, Meishan 620860, China.

Журнал: Mathematics.

Басма: MDPI.

Библиографиялык жазуу: Mathematics 2026, 14(15), 2811.

DOI: 10.3390/math14152811.

Жөнөтүлгөн күнү: 5-июнь 2026.

Кайра каралган күнү: 18-июль 2026.

Кабыл алынган күнү: 28-июль 2026.

Жарыяланган күнү: 5-август 2026.

Расмий шилтеме: DOI 10.3390/math14152811 аркылуу MDPI жарыя жазуусу.

Булактын түрү: Рецензияланган илимий журналда жарыяланган түпнуска изилдөө макаласы; комбинатордук оптималдаштырууга, кластерлөөгө жана маршрут пландаштырууга негизделген эсептөөчү изилдөө.

Preprint статусу: Берилген булак — журналда жарыяланган версия. PDF ичинде өзүнчө preprint идентификатору көрсөтүлгөн эмес.

Лицензия: Creative Commons Attribution (CC BY).

Ачкыч сөздөр: SD-MTSP; clustering algorithm; task balancing; depot location optimization.

MSC: 05B05; 90B50.

Программалык камсыздоо: Python 3.10, scikit-learn v1.3.0 жана OR-Tools v9.10.

Benchmark булагы: TSPLIB.

Биринчи негизги маалымат топтомдору: att48, eil76, gr229, pr299 жана dsj1000.

Абляциялык маалымат топтомдору: att48, eil76, gr229, rat575, dsj1000 жана pcb1173.

Баалоо метрикалары: Total-Sum Distance, Min-Max Distance, Workload Balance, Cluster Separability, Robustness жана Running Time.

Каржылоо: Opening Foundation of the State Key Laboratory of Cognitive Intelligence, Anhui iFLYTEK Co., Ltd., Grant No. COGOS-2024HE03; ошондой эле Sichuan University Jinjiang College 2024 Young Teacher Research Fund Project, Grant No. QNJJ-2024-B08.

Маалыматтардын жеткиликтүүлүгү: Авторлор изилдөө маалыматтары TSPLIB негизинде ачык жеткиликтүү экенин жана Data Availability бөлүмүндө GitCode'го жетүү шилтемесин бергенин билдиришкен.

Кызыкчылыктардын кагылышы: Авторлор кызыкчылыктардын кагылышын билдиришкен эмес.

Жасалма интеллектти колдонуу жөнүндө билдирүү: Авторлор макаланы даярдоо учурунда ChatGPT-5.4'тү грамматиканы жакшыртуу жана тилдик редакциялоо үчүн колдонушканын; акыркы мазмунду өздөрү карап чыгып, редакциялашканын жана жарыяланган мазмун үчүн жоопкерчиликти өздөрүнө алышканын билдиришкен.

Авторлордун салымдары: Концептуалдаштыруу Qi Jiang; ыкма Jiaxin Zou, Chunlong Fu, Pingli Zheng жана Kaiwen Xiao; программалык камсыздоо Guofang Liu жана Hongxia He; валидация Jiaxin Zou, Chunlong Fu жана Hongxia He; формалдуу талдоо Guofang Liu жана Yang Deng; изилдөө Chunlong Fu; ресурстар Pingli Zheng жана Qi Jiang; маалыматтарды курациялоо Jiaxin Zou, Pingli Zheng жана Kaiwen Xiao; алгачкы долбоор Jiaxin Zou; карап чыгуу жана редакциялоо Chunlong Fu; визуалдаштыруу Yang Deng; жетекчилик Chunlong Fu жана Guofang Liu тарабынан аткарылган.

Маанилүү методологиялык шайкешсиздик 1 — салмактын аныктамасы: Алгачкы Теңдеме (1) түйүндөрдүн катышы менен томпок кабыкчанын катышын колдонот. Кийинки Route-Feedback MADO агымы, Algorithm 1 жана Table 6 талкуусу түйүндөрдүн санын жана учурдагы TSP маршрут узундугун колдонот. Булак бул эки сүрөттөмөнү ачык ревизиялык байланыш менен бири-бирине байланыштырбайт.

Маанилүү методологиялык шайкешсиздик 2 — кластерлөө: Алгачкы төрт кадамдуу түшүндүрмө жаңыртылган деподон кийин кайра кластерлөө жөнүндө айтса, Figure 2 жана Algorithm 1 кластер мүчөлүктөрү бир жолу түзүлүп, депону оптималдаштыруу бою туруктуу сакталарын айтат.

Маанилүү метрикалык шайкешсиздик — Workload Balance: Теңдеме (7) алдындагы түшүндүрмө кичине маанилер жакшыраак тең салмакты көрсөтөт дейт. Натыйжалар бөлүмү, Figure 3 жана Table 5–6 болсо жогорураак маанини жакшыраак деп чечмелейт. Verianla бул карама-каршылыкты унчукпай оңдогон эмес.

Маалымат топтомунун камтылышы жөнүндө эскертүү: Section 5.1 беш benchmark мисалын аныктайт; Table 6 болсо pr299 ордуна rat575 жана pcb1173 камтыган алты мисалдуу өзүнчө салыштырууну колдонот.

Аралык масштабы жөнүндө эскертүү: Table 3/4 жана Table 6'да бирдей TSPLIB аталыштарын алып жүргөн айрым маалымат топтомдорунун аралык чоңдуктары ар башка масштабда. Булак мунун үчүн ачык трансформация же preprocessing түшүндүрмөсүн бербейт; таблицалар түздөн-түз бир масштабдуу маалымат топтому катары бириктирилген эмес.

pr299 сандары жөнүндө эскертүү: Table 3'тө K-Means/pr299 үчүн Total-Sum Distance 53.848,32 болсо, кейс-изилдөөнүн Table 5 оптималдаштырылган депо жыйынтыгы 54.533,97. Булак айырманын себебин ачык түшүндүрбөйт.

2-opt жөнүндө эскертүү: Натыйжалар бөлүмүндө 2-opt локалдык оптималдаштыруу OR-Tools чечимине киргизилгени айтылат; бирок ыкма бөлүмүндө 2-opt'тун деталдуу конфигурациясы берилген эмес.

Кайра өндүрүлүүчүлүк жөнүндө эскертүү: Algorithm 1, \(T_{max}\), \(\varepsilon\) жана баштапкы кадам \(\eta_0\) параметрлерин киргизүү катары аныктайт; булак бул параметрлердин колдонулган сандык маанилерин билдирбейт. Repeated-experiment саны, random seed жана эсептөө жабдуусу да ачык түрдө маалымдалган эмес.

Жакындашуу чеги: Авторлор глобалдык оптимум кепилдигин беришпейт. State hashing, cycle detection, projection-stall көзөмөлү жана кадамды кичирейтүү механизмдери итерацияны практикада аяктоону көздөйт.

Чыныгы дүйнө чеги: Изилдөө TSPLIB benchmark текшерүүсү болуп саналат. Чыныгы логистикалык флот, жандуу жол кыймылы, унаа сыйымдуулугу, убакыт терезелери, динамикалык кардар киргизүүсү жана гетерогендүү унаалар боюнча операциялык талаа текшерүүсү жүргүзүлгөн эмес.