Саякатчы Сатуучу Маселеси оптималдаштыруу адабиятындагы эң белгилүү жана эң татаал маселелердин бири. Классикалык түрүндө маселе жөнөкөй көрүнөт: сатуучу белгилүү шаарлардын ар бирине так бир жолу барып, андан кийин баштапкы чекитке кайтып, жалпы аралыкты минималдаштырышы керек. Бирок шаарлардын саны көбөйгөн сайын мүмкүн болгон маршруттардын саны абдан тез өсөт. Ошондуктан TSP NP-hard маселе деп эсептелет.

Изилдөөнүн негизги объектиси болсо TSPнин андан да татаал варианты болгон Asymmetric Traveling Salesman Problem, башкача айтканда ATSP. Классикалык симметриялуу TSPде эки шаардын ортосундагы аралык эки багытта тең бирдей. ATSPде болсо багыт маанилүү. Aдан Bге баруунун баасы Bден Aга баруунун баасынан айырмаланышы мүмкүн. Мындай айырма реалдуу дүйнөдө кеңири кездешет. Бир тараптуу жолдор, жол тыгыны, шамалдын багыты, убакыт терезелери, телескоптордун асмандагы буталарга жетүү кезеги, ДНК бөлүктөрүнүн багытка көз каранды дал келүүлөрү же өндүрүш линияларындагы операциялардын кезеги асимметриялуу чыгымдарды жаратышы мүмкүн.

Ошондуктан ATSP жөн гана математикалык оюн эмес. Ал логистикада жеткирүү кезектерин, астрономияда байкоо пландарын, геномикада секвенирлөө жана assembly процесстерин, өнөр жайда өндүрүш агымдарын жана чоң масштабдуу тармак пландоосун таасирленткен негизги оптималдаштыруу маселеси. Бирок ATSPнин багытка көз карандылыгы чечим мейкиндигин дагы татаал кылат. Симметриялуу TSP үчүн иштелип чыккан айрым ыкмалар ATSPге түз колдонулбайт же олуттуу ылайыкташтырууну талап кылат.

Изилдөөнүн негизги суроосу мындай: чоң масштабдуу ATSP мисалдарын стандарттык компьютерлерде бир эле учурда тез жана так чечүүгө болобу? Бул жердеги “так” деген сөз маанилүү. Көптөгөн эвристикалык ыкмалар тез чечим чыгарат, бирок ал чечим глобалдык оптимум экенине кепилдик жок. Ал эми exact MIP solver'лер теориялык жактан оптимумду таба алат, бирок чоң ATSP мисалдарында эсептөө убактысы жана эс тутум керектөөсү тез өсөт. Изилдөө ушул эки чектин ортосунда көпүрө курууну көздөйт: эвристикалык ылдамдык менен exact solver тактыгын бир архитектурада бириктирүү.

Авторлор сунуштаган ыкма GTA деп аталат. GTA — Gurobi Tabu Algorithm деген аталыштын кыскартылышы. Атынан көрүнүп тургандай, ыкма кеңири колдонулган коммерциялык MIP solver болгон Gurobi менен Tabu Search эвристикасын бириктирет. Бирок изилдөө бул компоненттерди жөн гана катар коюп койбостон, чоң масштабдуу ATSP үчүн стратегиялык түрдө кайра уюштурганын ырастайт.

GTAнын өзөгүндө үч бөлүктөн турган түзүлүш бар:

• Tabu Search warm start: Өтө кыска убакытта жакшы баштапкы тур түзөт. Изилдөөдө мындай баштапкы чечимдер адатта 1%–5% optimality gap аралыгында, консервативдүү баалоодо 10%дан төмөн экени айтылат.
• Gurobi MIP чечими: Баштапкы турду колдонуп exact издөө жүргүзөт жана 0% optimality gap максатына жетүүгө аракет кылат.
• MTZсиз subtour elimination: Miller–Tucker–Zemlin чектөөлөрүнүн ордуна lazy constraint callback колдонулуп, кошумча циклдер динамикалык түрдө жок кылынат.

Бул үч компоненттин чогуу иштеши маанилүү. Tabu Search жалгыз өзү тез, бирок жакындатылган жыйынтык берет. Gurobi жалгыз өзү чоң ATSPде cold start менен өтө узак иштеши мүмкүн. MTZ чектөөлөрү классикалык TSP формулировкаларында subtour'ларды токтотуу үчүн колдонулганы менен, чоң маселелерде моделдин көлөмүн жана чечүү жүгүн көбөйтүшү мүмкүн. GTA жакшы баштапкы тур берип Gurobiнин издөө дарагын тарытат; MTZ чектөөлөрүн алып салып моделдин түзүлүшүн жеңилдетет; lazy constraints аркылуу subtour кесүүлөрүн зарыл болгондо гана кошот.

ATSPнин стандарттык MIP логикасын түшүндүрүү үчүн негизги формулировканы төмөнкүдөй кароого болот. Бул формула изилдөө колдонгон MTZсиз MIP ыкмасын түшүнүүгө жардам берген фондук түшүндүрмө:

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

Бул жерде N — түйүндөрдүн саны. c_ij — i түйүнүнөн j түйүнүнө баруунун баасы. ATSPде адатта c_ij ≠ c_ji болушу мүмкүн. x_ij — iден jге өтүлөбү же жокпу көрсөтүүчү бинардык өзгөрмө. Эгер маршрут iден jге өтсө [ x_{ij}=1 ], өтпөсө [ x_{ij}=0 ] болот.

Ар бир түйүндөн так бир чыгуу болушун камсыз кылган негизги даража чектөөсү:

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

Ар бир түйүнгө так бир кирүү болушун камсыз кылган чектөө:

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

Бул эки чектөө ар бир түйүндө бир чыгуу жана бир кирүү болушун камсыз кылат. Бирок булар өз алдынча жетиштүү эмес. Анткени чечим бардык түйүндөрдү камтыган бир турдун ордуна бир нече кичине циклге, башкача айтканда subtour'ларга бөлүнүшү мүмкүн. Мисалы 1-2-3-1 жана 4-5-6-4 сыяктуу эки өзүнчө жабык маршрут түзүлүшү мүмкүн. TSP/ATSPнин негизги татаалдыгы — бардык түйүндөрдү бир Hamilton туруна бириктирүү.

Классикалык MTZ ыкмасы кошумча иреттөө өзгөрмөлөрү аркылуу мындай subtour'ларды токтотууга аракет кылат. Бирок чоң масштабда бул кошумча өзгөрмөлөр жана чектөөлөр чечүүнү оорлотушу мүмкүн. Изилдөө сунуштаган ыкмада MTZ чектөөлөрүнүн ордуна lazy constraint callback колдонулат. Бул логикада solver алгач даража чектөөлөрү менен чечим чыгарат; эгер чечим subtour'лардан турса, ошол subtour'ларды гана кескен жаңы чектөөлөр кийин кошулат. Жалпы subtour elimination логикасын төмөнкү фондук формула менен көрсөтүүгө болот:

\[ \sum_{i\in S}\sum_{j\in S, j\neq i} x_{ij} \leq |S|-1 \quad \forall S \subset \{1,\ldots,N\},\; 2\leq |S| < N \]

Бул жерде S — бардык түйүндөрдүн бир гана ички жыйындысы. Бул чектөө S жыйындысынын ичиндеги түйүндөр өз алдынча жабык кичине тур түзүшүнө жол бербейт. Бирок мүмкүн болгон бардык S жыйындылары үчүн мындай чектөөлөрдү алдын ала кошуу практикалык эмес. Lazy constraint дал ушундан улам колдонулат: solver тапкан чечимде чындап пайда болгон subtour'лар гана кесилет.

Изилдөө GTAнын күчү ушул жерде деп эсептейт. MIP solver өтө чоң чечим мейкиндигинде нөлдөн баштап жүрбөйт. Tabu Search алгач жакшы маршрут берет. Бул маршрут Gurobi үчүн incumbent, башкача айтканда баштапкы чечим болот. Эгер incumbent оптимумга жакын болсо, branch-and-cut издөө тар чөйрөдө иштей алат; начар бутактар эртерээк кесилет; cut generation натыйжалуураак болот. Ошондуктан изилдөө warm start сапаты критикалык мааниге ээ экенин баса белгилейт.

Авторлор начар warm start чечимдери пайдадан көбүрөөк зыян алып келиши мүмкүн экенин өзгөчө белгилейт. Изилдөөдө 10%–15%дан жогору gap'и бар баштапкы чечимдер MIP solver'ди туура эмес багыттап, атүгүл cold start'тан да начар натыйжа бериши мүмкүн экени айтылат. Мунун себеби — жаман incumbent издөө дарагын туура эмес багыттап, жакшыраак чечимдердин эрте табылышына тоскоол болуп жана solver'дин ички эвристикаларын басаңдатышы мүмкүн. Ошондуктан GTA үчүн жөн гана “бир баштапкы чечим” эмес, түзүлүшү боюнча ырааттуу жана жетиштүү жакын баштапкы тур талап кылынат.

Изилдөө Tabu Search warm start адатта секунддардын ичинде 1%–9% аралыгында gap берерин, көп учурда 5%дан төмөн каларын ырастайт. Ошол эле текстте генетикалык алгоритм жана simulated annealing сыяктуу башка эвристикалар чоң ATSP мисалдарында 30 мүнөттөн ашык убакыттан кийин да 50%дан жогору gap бере алары айтылат. Ошондуктан авторлор GTA архитектурасында Tabu Search тандоосу кокустук эмес, warm start сапаты менен ылдамдыктын тең салмагынан чыккан деп эсептейт.

Изилдөөнүн өндүрүмдүүлүк боюнча дооматтары абдан күчтүү. 1-таблицада GTA 5.000 түйүндүү ATSP үчүн N^2.01–N^2.03 аралыгында эмпирикалык татаалдык көрсөтүп, 350–850 секунд ичинде 0% optimality gap алган деп берилет. Ал эми warm start'сыз Gurobi lazy-constraint ыкмасы үчүн N^2.1–N^2.2 жана 3.750–6.750 секунд аралыгы көрсөтүлөт. Бул салыштыруу GTA жөн гана Gurobi колдонуу эмес экенин; warm start жана моделдин дизайны иштөө убактысына олуттуу таасир берерин көрсөтүү үчүн колдонулат.

Бирок бул жерде кылдат илимий айырма жасалышы керек. Изилдөөдө берилген N^2.01–N^2.03 жүрүм-турум формалдуу алгоритмдик татаалдык далили эмес. Авторлор да муну ачык айтат: квадраттыкка жакын жүрүм-турум ар башка түйүн сандарында алынган иштөө убактысын log-log регрессия менен моделдөө аркылуу алынган. NP-hard ATSP үчүн мындай эмпирикалык масштабдоо билдирүүлөрү адабиятта кеңири болсо да, алар математикалык worst-case татаалдык кепилдиги эмес, эксперименттик benchmark катары кабыл алынышы керек.

Изилдөөдөгү биринчи маанилүү визуалдык салыштыруу GTAны exact жана heuristic solver'лер менен салыштырган runtime графиги. Бул графикте exact solver категориясы жашыл, heuristic ыкмалар көк, GTA болсо ATSP үчүн кыйла төмөн убакыт менен көрсөтүлөт. Текстке ылайык GTA 5.000 түйүндүү ATSPде орточо болжол менен 600 секунддук иштөө убактысында жайгашат, exact solver'лер жана эвристикалар ар башка trade-off'тарга ээ экени айтылат. Бул визуал изилдөөнүн негизги дооматын жөнөкөй көрсөтөт: GTA heuristic ылдамдыгына жакындап, exact optimality, башкача айтканда 0% gap максатын сактоого аракет кылат.

Изилдөөдөгү log-log жана lin-log өндүрүмдүүлүк графиктери түйүн саны өскөн сайын GTA runtime маалыматтары салттуу exact ыкмаларга караганда эңкейиши төмөн масштабдоону көрсөтөрүн түшүндүрөт. Log-log графикте GTA маалыматтары кызыл чекиттер менен, heuristic 50% gap ийри сызыгы жана best-case exact 0% gap ийри сызыгы менен салыштырылат. Бул визуал GTA эмпирикалык жактан болжол менен [ y = 10^{-5}x^{2.0368} ] сызыгына жакын жүрүм-турум көрсөткөн деген дооматты колдоо үчүн колдонулат. Дагы бир жолу, бул эксперименттик маалыматка ылайыкташтыруу; бардык ATSP мисалдары үчүн теориялык кепилдик эмес.

Изилдөөнүн өзүнүн Gurobi салыштыруусу да маанилүү. Бир графикте GTA lazy constraint колдонгон Gurobi жана MTZ негизиндеги чечим менен салыштырылат. GTA ийри сызыгы lazy-only жана MTZ ыкмаларынан төмөн турат. Текст warm start'сыз Gurobi lazy constraint менен да айрым учурларда 24 сааттан ашып кетиши мүмкүн экенин, MTZ формулировкасы чоң масштабда андан да оор болорун билдирет. Бул GTAдагы өндүрүмдүүлүктүн негизги булагы компоненттердин синергиясы деген дооматты бекемдөө үчүн колдонулат.

Изилдөөдө тармактык визуалдаштыруу бөлүмү да бар. Түйүн саны 10, 100, 1.000 жана 2.000 болгондо оптималдык маршрут карталары көрсөтүлөт. 10 түйүндүү мисалды оңой байкоого болот, 100 түйүндө байланыштар тыгыздайт; 1.000 жана 2.000 түйүндө маршрут тыгыз тармакка айланат. Ири жашыл жана көк чекиттер баштапкы жана орто жолдогу түйүндөрдү билдирет. Бул визуалдар TSP/ATSP түйүн саны көбөйгөн сайын визуалдык жана түзүлүштүк жактан кантип татаалданарын көрсөтөт.

Бул визуалдаштыруу жөн гана эстетикалык кошумча эмес. Изилдөө маршрут карталары колдонуучуга чечимдин мейкиндик түзүлүшүн, кластерлешүү жүрүм-турумун, баштапкы-орто жол байланышын жана түйүндөрдүн оптималдык иреттеги ордун интуитивдүү түшүнүүгө жардам берет деп эсептейт. Логистикалык пландоо, байкоо графигин түзүү жана биологиялык маалыматтарды иреттөө сыяктуу тармактарда колдонуучу жалпы чыгымды гана эмес, маршрут кандай түзүлгөнүн да көргүсү келиши мүмкүн. Ошондуктан GTA интерфейси реалдуу убакытта итерацияны көзөмөлдөө жана маршруттун тыгыздыгын визуалдаштыруу берет деп айтылат.

Изилдөөнүн дагы бир маанилүү тест тобу seed өзгөрүүсүнө байланыштуу. ATSP чыгым матрицасы кокус түзүлөт жана seed өзгөргөндө чыгым коэффициенттери, демек глобалдык оптимум жана издөө мейкиндиги да өзгөрөт. Эгер алгоритм бир seedде гана тез иштеп, башка seedдерде начарласа, аны ишенимдүү деп эсептөөгө болбойт. Изилдөөдө алгач S = 42 жана S = 65 seed маанилери, андан кийин 133, 29 жана 7 seed маанилери менен ар башка түйүн сандарындагы иштөө убакыттары салыштырылган.

Seed өзгөрүүсүнүн жыйынтыктары GTAнын иштөө убактысы ар башка кокус чыгым матрицаларында окшош масштабдоону көрсөтөрүн ырастайт. Графиктерде кичине түйүн сандарында майда өзгөрүүлөр көрүнөт, чоң түйүн сандарында runtime ийри сызыктары бири-бирине жакындайт. Бул жыйынтык изилдөөдө runtime seed-invariance катары чечмеленет. Башкача айтканда, алгоритмдин өндүрүмдүүлүгү кокус чыгым матрицасынын белгилүү бир өзгөчө формасына көз каранды эмес көрүнөт.

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

Изилдөөдө чыгым коэффициенттеринин масштабы да текшерилет. Алгач чыгымдар [1,10] аралыгында, андан кийин [10,100] аралыгында түзүлөт. Авторлор бул масштаб өзгөрүүсү теориялык жактан нормалдаштырылышы мүмкүн экенин кабыл алат, бирок практикада чоң коэффициент диапазондору solver жүрүм-турумуна таасир бере аларын айтат. Figure 6да эки диапазондогу runtime ийри сызыктары log-log, log-lin жана lin-lin көрүнүштөрдө салыштырылат. Изилдөөнүн түшүндүрмөсү GTA чыгым коэффициентинин масштабына карата негизинен туруктуу экенин көрсөтөт.

Бул жыйынтык колдонмо жагынан маанилүү. Реалдуу дүйнөдө чыгымдар ар кандай бирдиктерде болушу мүмкүн: километр, мүнөт, күйүүчү май, тобокелдик баллы, астрономиялык көрүнүү коэффициенти, генетикалык дал келүү баллы же артыкчылык салмагы. Эгер алгоритм белгилүү сандык диапазонго сезимтал болсо, ар бир колдонмодо өзүнчө нормалдаштыруу жана параметр жөндөө талап кылынат. Изилдөө GTA [1,10] жана [10,100] диапазондорунда окшош жүрүм-турум көрсөткөнүн айтып, мындай кошумча алдын ала иштетүүгө азыраак муктаж болушу мүмкүн деп эсептейт.

Изилдөөнүн эң көңүл бурдурган дооматтарынын бири — негизги тоскоолдук алгоритмдик татаалдыктан RAMга өтөт деген пикир. Талкуу бөлүмүндө эксперименттер 16 GB RAM бар стандарттык компьютерлерде, GPU жана параллелдештирүүсүз жүргүзүлгөнү айтылат. Колдонулган системалардын бири 4 ядро жана 8 logical processor бар Intel машинасы; текшерүү үчүн 12-муундагы i5, 8 ядро жана 16 processor түзүлүшү колдонулган. Авторлор чоң мисалдарда runtime дээрлик горизонталдуу боло баштайт жана негизги чектөөчү фактор RAM/системалык эс тутум болуп калат деп ырастайт.

Бул доомат илимий жактан маанилүү, бирок аны этият формулировкалоо керек. ATSP сыяктуу NP-hard маселеде “алгоритмдик татаалдык жоголду” деп айтуу туура эмес. Изилдөөнүн дооматын тар мааниде окуу керек: GTAнын инженердик дизайны изилденген кокус ATSP мисалдарында Gurobiнин издөө мейкиндигин ушунчалык тарытат, практикалык тоскоолдук айрым чоң N маанилеринде эсептөө убактысынан көбүрөөк эс тутумду башкарууга өтөт. Бул worst-case теориялык татаалдык дооматы эмес, эксперименттик өндүрүмдүүлүк байкоосу.

Үзгүлтүксүз жакшыртуу бөлүмүндө GTA кодунан графикалык интерфейс катмарын жана diagonal өзгөрмөлөрдү алып салуу менен иштөө убактысы олуттуу кыскарганы айтылат. GUI коддун болжол менен 30%–35%ын түзөрү, колдонуучуга ыңгайлуу болушу үчүн маанилүү, бирок RAM керектөөсүн көбөйтөрү айтылат. Ошондой эле diagonal жазууларга чоң M маанисин берүү ордуна мындай өзгөрмөлөрдү таптакыр түзбөө сунушталат.

Бул инженердик жактан абдан конкреттүү пункт. N = 2.000 болгондо толук матрица ыкмасы 2.000 × 2.000 = 4.000.000 өзгөрмө түзүшү мүмкүн. Diagonal өзгөрмөлөр алынганда бул сан 3.998.000 болот. Сандык айырма болгону 2.000дей көрүнгөнү менен, solver'дин өзгөрмө түзүүсү, матрицаны сактоосу, presolve жана эс тутум башкаруусу боюнча таасири чоңураак болушу мүмкүн. Изилдөөдө GUI жана diagonal өзгөрмөлөр алынганда орточо болжол менен 50% runtime жакшырганы айтылат.

Figure 7 бул жакшыртууну көрсөтөт. Жогорку панелде ар башка түйүн сандары үчүн баштапкы GTA убакыттары менен GUI/diagonal алынган версиянын убакыттары салыштырылат. Төмөнкү панелде баштапкы GTA маалыматы менен оптималдаштырылган версиянын runtime ийри сызыктары көрсөтүлөт. Текст алгоритмдин негизги итерациялары өзгөрбөгөнүн, негизги айырма кодду жөнөкөйлөтүү жана маселенин формулировкасын оптималдаштыруудан чыкканын белгилейт. Бул “негизги тоскоолдук RAM жана маселенин көрсөтүлүшү” деген дооматты колдоо үчүн колдонулат.

Изилдөөнүн колдонмо тармактары кеңири талкууланат. Логистикада ATSP багытка көз каранды жеткирүү жана маршрут пландоо үчүн маанилүү. Астрономияда телескоптун байкоо кезеги, асмандагы буталардын көрүнүү терезелери, позициялык чектөөлөр жана илимий артыкчылык салмактары менен TSP/ATSP туундуларына айланышы мүмкүн. Геномикада ДНК секвенирлөө же assembly маселелери багытка көз каранды дал келүү жана иреттөө түзүлүштөрүнөн улам ATSP сымал оптималдаштырууларга байланышы мүмкүн. Изилдөө GTAны убакыт терезелери, көрүнүү жана позиция чектөөлөрү сыяктуу варианттарга кеңейтсе болорун айтат.

Бирок бул колдонмо дооматтарын да кылдат ажыратуу керек. Изилдөө бул тармактардагы бардык реалдуу маалымат маселелерин чечкен эмес. Айрым варианттар даярдалганы же бар экени айтылат; айрымдары болсо келечектеги ылайыкташтыруу катары берилет. Өзгөчө multi-agent TSP жана gene overlap sequencing сыяктуу тармактарда GTA түздөн-түз текшерилбегени текстте көрсөтүлөт. Демек бул тармактар далилденген жыйынтыктар эмес, потенциалдуу колдонмо багыттары катары каралышы керек.

Изилдөөнүн күчтүү жактарынын бири практикалык инженердик деталдарга көңүл бурушу. Ал жөн гана “жаңы теориялык алгоритмди” сунуштабайт, solver параметрлери, warm start сапаты, GUI, diagonal өзгөрмөлөр, seed өзгөрүүсү, чыгым масштабдоосу, runtime логдору жана визуалдаштыруу сыяктуу реалдуу колдонууда өндүрүмдүүлүккө таасир берген факторлорду талкуулайт. Мындай мамиле оптималдаштыруу программаларында көп учурда көңүл сыртында калган, бирок практикада чечүүчү болгон деталдарга басым жасайт.

Дагы бир күчтүү жагы — ATSP симметриялуу TSPден айырмаланып жана татаалыраак экенин дайыма баса белгилеши. Адабиятта Concorde жана TSPLIB сыяктуу benchmarkтардын көбү симметриялуу TSP үчүн күчтүү; бирок ATSP жагында 5.000 түйүндүү стандарттык benchmarkтар жетишсиз экени айтылат. Изилдөө GTAны ушул боштукту толтуруучу талапкер алкак катары сунуштайт. Өзгөчө TSPLIBдеги чоң симметриялуу мисалдар менен ATSP жыйынтыктары түздөн-түз бир эле нерсе эмес экенин баса белгилеши методологиялык жактан туура.

Чектөөлөрү да ачык. Биринчиден, изилдөө текст боюнча рецензиядан өткөнү тастыкталбаган долбоор. Экинчиден, квадраттыкка жакын иштөө убактысы үчүн формалдуу теориялык далил жок; жыйынтык эмпирикалык регрессияга негизделген. Үчүнчүдөн, 5.000 түйүндүү ATSP үчүн түз стандартташтырылган тышкы benchmark жетишсиз болгондуктан салыштыруулардын айрымдары симметриялуу TSP benchmarkтары же авторлордун өз Gurobi варианттары менен жүргүзүлгөн. Төртүнчүдөн, кокус түзүлгөн чыгым матрицалары чыныгы өндүрүш, биологиялык же астрономиялык маалымат түзүлүштөрүнүн баарын толук чагылдырбашы мүмкүн.

Бешинчи чектөө — Gurobi сыяктуу коммерциялык solver'ге көз карандылык. Изилдөө Gurobiни ачык жеткиликтүүлүк философиясы жана ATSPге ылайыктуулугу үчүн тандаганын билдирет; бирок Gurobi лицензиясы, колдонуучу жеткиликтүүлүгү жана solver версияларынын айырмасы репродукцияга таасир бериши мүмкүн. Алтынчыдан, текстте “source code and variants are or will be made open-access” деген билдирүү бар; бул коддун жеткиликтүүлүгү жана көз карандысыз кайталануу үчүн критикалык жагдай. Код, параметрлер жана логдор чындап ачык берилгенде дооматтарды текшерүү күчтүү болот.

Изилдөө эмнени айтат жана эмнени айтпайт — так ажыратылышы керек. Изилдөө GTA чоң кокус ATSP мисалдарында стандарттык жабдыкта 0% gapке тез жеткенин билдирет. Tabu Search warm start, Gurobi MIP жана lazy subtour elimination биригиши күчтүү инженердик синергия түзөт деп ырастайт. Бирок изилдөө ATSPнин worst-case NP-hard татаалдыгын теориялык жактан жок кылганын далилдебейт. Бардык реалдуу дүйнөдөгү ATSP мисалдарында бирдей убакытты кепилдебейт. Gurobiден көз карандысыз solver-agnostic алгоритм сунуштайт деп да айтпайт. Эң туура түшүнүк мындай: GTA чоң масштабдуу ATSP үчүн практикалык, детерминисттик, инженердик багыттагы жана күчтүү өндүрүмдүүлүк дооматтары бар гибриддик чечим алкагы; бул дооматтардын баалуулугу көз карандысыз кайталануу жана чыныгы маалымат benchmarkтары менен дагы такталат.

Изилдөөнүн Методу жана Жыйынтыктары

Изилдөөнүн методу кокус асимметриялуу чыгым матрицаларын түзүү, Tabu Search менен жогорку сапаттагы warm start алуу, MTZсиз Gurobi MIP моделин куруу, lazy constraint callback менен subtour elimination колдонуу, runtime/optimality gap/iteration/node metadata жазуу жана ар башка seed, чыгым масштабы, маселенин өлчөмү жана кодду жөнөкөйлөтүү шарттарында өндүрүмдүүлүктү салыштыруу кадамдарынан турат.

1. Маселенин түрү жана маалымат түзүү

2. ATSPнин негизги MIP логикасы

Изилдөө колдонгон MTZсиз Gurobi ыкмасын түшүндүрүү үчүн стандарттык ATSP максатын төмөнкү негизги байланыш аркылуу түшүнүүгө болот:

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

Чыгуу чектөөсү:

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

Кирүү чектөөсү:

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

Subtour elimination логикасы:

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

3. GTAнын алгоритмдик компоненттери

4. Warm start сапаты

5. 1-таблицадагы өндүрүмдүүлүк салыштыруусу

6. Сүрөттөрдүн техникалык мааниси

• 1-таблица жана биринчи өндүрүмдүүлүк графиги: GTA exact solver жана heuristic ыкмалардын ортосунда жайгашканын көрсөтөт. Изилдөө GTA ATSPде 0% gap менен heuristic ылдамдыгына жакын runtime берет деп ырастайт.
• Log-log жана lin-log өндүрүмдүүлүк графиктери: GTA runtime маалыматтары түйүн санына карата эмпирикалык түрдө квадраттыкка жакын масштабдоо көрсөтөт деген дооматты колдойт. Бул формалдуу далил эмес, регрессияга негизделген эксперименттик байкоо.
• GTA-LAZY-MTZ салыштыруусу: Warm start жана MTZсиз lazy subtour elimination айкалышы warm start'сыз lazy жана MTZ ыкмаларынан төмөн runtime берет деп көрсөтөт.
• Optimal route карталары: 10, 100, 1.000 жана 2.000 түйүн үчүн маршруттун татаалдыгы визуалдык түрдө кантип өсөрүн көрсөтөт. Ири жашыл жана көк чекиттер баштапкы жана орто жолдогу түйүндөрдү билдирет.
• Seed invariance графиги: S = 42, 65, 7, 29 жана 133 сыяктуу ар башка seed маанилеринде runtime ийри сызыктары окшош жүрүм-турум көрсөтөрүн билдирет.
• Cost range графиги: [1,10] жана [10,100] чыгым диапазондорунда иштөө убактысы окшош масштабдоо көрсөтөт деген пикирди колдойт.
• GUI жана diagonal өзгөрмөлөрдү алып салуу графиги: Кодду жөнөкөйлөтүү жана моделден diagonal өзгөрмөлөрдү алып салуу орточо болжол менен 50% runtime жакшыртуусун берген деп билдирилет.

7. Seed жана чыгым масштабы тесттери

8. RAM жана кодду жөнөкөйлөтүүнүн таасири

9. Колдонмо тармактары

10. Изилдөөнүн негизги жыйынтыктары

• GTA Tabu Search warm start менен Gurobi MIP exact чечимин бириктирет.
• MTZ чектөөлөрүнүн ордуна lazy constraint callback менен subtour elimination колдонулат.
• Изилдөөдө 5.000 түйүнгө чейинки ATSP мисалдарында 0% optimality gap билдирилет.
• 1-таблицада GTA үчүн 5.000 түйүндүү ATSPде 350–850 секунд аралыгы берилет.
• Warm start'сыз Gurobi lazy constraints ыкмасы үчүн 3.750–6.750 секунд аралыгы көрсөтүлөт.
• Квадраттыкка жакын N^2.01–N^2.03 жүрүм-турум эмпирикалык log-log регрессия менен ырасталат.
• Ар башка seed маанилеринде runtime масштабдоосу окшош бойдон калары билдирилет.
• [1,10] жана [10,100] чыгым диапазондорунда runtime туруктуулугу көрсөтүлөт.
• GUI жана diagonal өзгөрмөлөрдү алып салуу менен болжол менен 50% runtime жакшырганы билдирилет.
• Авторлор чоң масштабда негизги тоскоолдук эсептөө убактысынан RAM/системалык эс тутумга өтөт деп ырастайт.

11. Күчтүү жактары

• ATSP симметриялуу TSPден айырмалуу жана татаалыраак маселе экенин так баса белгилейт.
• Эвристикалык ылдамдык менен exact MIP optimality максатын бир архитектурада бириктирет.
• Warm start сапатынын MIP өндүрүмдүүлүгүнө таасирин практикалык жактан карайт.
• MTZсиз lazy subtour elimination аркылуу моделдин көлөмүн жана чечүү жүгүн азайтууну көздөйт.
• Seed, чыгым диапазону жана кодду жөнөкөйлөтүү тесттери менен инженердик туруктуулукту көрсөтүүгө аракет кылат.
• Маршрут визуалдаштыруу жана колдонуучу интерфейси аркылуу ыкманы теориялык гана эмес, колдонууга мүмкүн болгон курал катары берет.

12. Чектөөлөр

• Изилдөө текст боюнча рецензиядан өткөнү тастыкталбаган изилдөө долбоору / preprint мүнөзүндө.
• Квадраттыкка жакын татаалдык формалдуу теориялык далил менен эмес, эмпирикалык runtime регрессиясы менен колдоого алынат.
• 5.000 түйүндүү ATSP үчүн түз стандартташтырылган тышкы benchmark жетишсиз.
• Салыштыруулардын айрымдары симметриялуу TSP benchmarkтары менен жасалат; бул маалыматтар ATSP менен бирдей маселе классы эмес.
• Кокус түзүлгөн чыгым матрицалары чыныгы логистика, геномика же астрономия маалыматтарындагы көз карандылык түзүлүшүн толук чагылдырбашы мүмкүн.
• GTAнын ийгилиги Gurobi solver'ге, solver параметрлерине, RAM көлөмүнө жана warm start колдонулушуна көз каранды.
• Коддун жана solver логдорунун ачык жеткиликтүүлүгү көз карандысыз кайталануу үчүн критикалык; текстте ачык жеткиликтүүлүк ниети айтылат.
• Multi-agent TSP, gene overlap sequencing жана айрым өнүккөн варианттар бул изилдөөдө толук текшерилген жыйынтыктар катары берилбейт.

Булак жана Метод Эскертмеси

Бул макала Wissam Nakhle, Gaby Abou Haidar, Elie Al Ahmar жана Roger Achkar даярдаган “GTA - An ATSP Method: Shifting the Bottleneck from Algorithm to RAM” аттуу изилдөөнүн негизинде даярдалган. Изилдөөдө авторлордун байланыштары Concordia University, American University of Science and Technology, Université La Sagesse жана Antonine University деп көрсөтүлгөн.

Булак түрү тексттин түзүлүшү жана берүү формасы эске алынып, академиялык изилдөө макаласынын долбоору / preprint мүнөзүндөгү техникалык изилдөө катары бааланышы керек. Текстте рецензияланган журналга кабыл алуу, DOI, конференцияга кабыл алуу же ачык рецензия маалыматы ырасталбагандыктан, бул изилдөө үчүн рецензиядан өткөнү текст аркылуу ырасталбаган изилдөө деген аныктама колдонулушу керек.

Бул мазмун даярдалганда изилдөөдө берилген GTA архитектурасы, Tabu Search warm start ыкмасы, Gurobi MIP колдонулушу, MTZсиз lazy subtour elimination стратегиясы, ATSPнин симметриялуу TSPден айырмасы, 1-таблицадагы өндүрүмдүүлүк салыштыруусу, log-log жана lin-log runtime графиктеринин түшүндүрмөсү, seed өзгөрүүсү, чыгым диапазонун масштабдоо, тармак визуалдаштыруу, GUI/diagonal өзгөрмөлөрдү жөнөкөйлөтүү эксперименттери жана жыйынтык бөлүмүндөгү дооматтар менен чектөөлөр негиз катары алынган.

Текстте жок көз карандысыз тастыктоо, рецензияланган басылмага кабыл алуу, бардык реалдуу дүйнөдөгү ATSP мисалдары үчүн кепилдик, worst-case теориялык татаалдык далили, Gurobiден көз карандысыз ийгилик, бардык TSP варианттарында автоматтык иштөө же так коммерциялык/операциялык ийгилик сыяктуу дооматтар кошулган эмес. Изилдөөнүн жыйынтыктары чоң масштабдуу кокус ATSP мисалдарында GTA күчтүү жана кайталанма өндүрүмдүүлүк көрсөтүшү мүмкүн экенин ырастайт; бирок бул дооматтардын илимий ишенимдүүлүгү ачык код, толук solver логдору, көз карандысыз кайталануу жана чыныгы маалымат benchmarkтары менен дагы күчтөндүрүлүшү керек.