Саудагер саяхашысы мәселесі: комбинаторлық оптимизациядағы NP қиындықтары

Саяхатшы сатушы мәселесі: Комбинаторлық оптимизациядағы NP қиын мәселе. Ең қысқа маршрутты табу, қалаларды бір рет барып қайту. Теориялық информатика.

15 мин оқу

100%

Дереккөз: Travelling salesman problem — Wikipedia

Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.

Мазмұны

Кіріспе

Комбинаторлық оңтайландырудағы NP қиындық. Саяхаттаушы сатушы проблемасы (TSP) деп те аталады, келесі сұраққа жауап береді: "Қалалар тізімі және әрбір қала жұбы арасындағы қашықтықтар берілген жағдайда, әр қалаға дәл бір рет барып, бастапқы қалаға оралатын ең қысқа маршрут қандай?" Бұл комбинаторлық оңтайландырудағы NP қиын мәселе, теориялық информатика және операциялық зерттеулерде маңызды. Саяхаттаушы сатып алушы проблемасы және көлік маршрутын жоспарлау проблемасы – екеуі де TSP-нің жалпылама түрі болып табылады. Есептеу күрделілігі теориясында TSP-нің шешімдік нұсқасы (ұзындығы L берілген кезде, графтың ұзындығы L-ден аспайтын айналымның бар-жоғын анықтау міндеті) NP-толық проблемалар класына жатады. Осылайша, TSP үшін кез келген алгоритмнің нашар жағдайдағы орындалу уақыты қалалар санының өсуімен суперполиномиялық (бірақ экспоненциалды емес) деңгейде ұлғаюы мүмкін. Бұл мәселе алғаш рет 1930 жылы қойылды және оңтайландыру саласындағы ең көп зерттелген мәселелердің бірі болып табылады. Ол көптеген оңтайландыру әдістері үшін өлшем таяқшасы ретінде қолданылады. Мәселе есептеу жағынан қиын болғанымен, көптеген эвристикалық және нақты алгоритмдер белгілі, сондықтан ондаған мың қаласы бар кейбір мысалдарды толығымен шешуге болады, ал миллиондаған қаласы бар проблемаларды 1% шегінде жуықтауға болады. TSP тіпті ең қарапайым түрінде де жоспарлау, логистика және микрочиптерді өндіру сияқты қолдануларға ие. Сәл өзгертілген түрінде, ол ДНК тізбектеу сияқты көптеген салаларда қосалқы мәселе ретінде кездеседі. Мұндай қолдануларда "қала" түсінігі клиенттерді, дәнекерлеу нүктелерін немесе ДНК фрагменттерін білдіретін алды, ал "қашықтық" түсінігі – жол жүру уақытын, құнын немесе ДНК фрагменттерінің ұқсастық деңгейін көрсетеді. TSP астрономияда да қолданылады, себебі көптеген көздерді бақылайтын астрономдар телескопты көздер арасында жылжытуға жұмсалатын уақытты азайтуға тырысады; мұндай жағдайларда TSP оптималды басқару мәселесінің ішіне енгізілуі мүмкін. Көптеген қолдануларда шектеулі ресурстар немесе уақыт терезелері сияқты қосымша шектеулер қойылуы мүмкін.

NP hard problem in combinatorial optimization

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP. In the theory of computational complexity, the decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour whose length is at most L) belongs to the class of NP complete problems. Thus, it is possible that the worst case running time for any algorithm for the TSP increases superpolynomially (but no more than exponentially) with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, many heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely, and even problems with millions of cities can be approximated within a small fraction of 1%. The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources want to minimize the time spent moving the telescope between the sources; in such problems, the TSP can be embedded inside an optimal control problem. In many applications, additional constraints such as limited resources or time windows may be imposed.

Тарих

Саяхатшы сатушы мәселесінің шығу тегі белгісіз. 1832 жылы саяхатшы сатушыларға арналған нұсқаулықта бұл мәселе айтылған және Германия мен Швейцария арқылы экскурсиялардың мысалдары келтірілген, бірақ математикалық тұрғыдан қарастырылмаған. ТСП математикалық тұрғыдан 19-ғасырда ирланд математигі Уильям Роуэн Гамильтон және британ математигі Томас Киркман жасаған. Гамильтонның икозиандық ойыны – Гамильтон циклін табуға негізделген ойын-сауық жұмбағы. ТСП-ның жалпы түрін математиктер 1930 жылдары Венада және Гарвардта алғаш рет зерттеген, әсіресе Карл Менгер, мәселені анықтап, түйінсіз іздеу алгоритмін қарастырып, жақын көрші эвристикасының оңтайлы еместігін байқады: Біз хабаршы мәселесі деп атаймыз (практикада бұл мәселені әрбір пошташы, сондай-ақ көптеген саяхатшылар да шешуі керек), шекті сандағы нүктелердің жұптық арақашықтықтары белгілі болғанда, осы нүктелерді байланыстыратын ең қысқа маршрутты табу міндеті. Әрине, бұл мәселені шекті сандағы тәжірибелер арқылы шешуге болады. Берілген нүктелердің орналасуының санынан кем тәжірибелер санын қамтамасыз ететін ережелер белгісіз. Бастапқы нүктеден ең жақын нүктеге, содан кейін оған ең жақын нүктеге, және т.б. жүру ережесі, әдетте, ең қысқа маршрутты бермейді. Оны алғаш рет 1930 жылдары мектеп автобустарының маршрутын шешуге тырысқан Мерилл М. Флуд математикалық тұрғыдан қарастырды. Принстон университетінің профессоры Хаслер Уитни бұл мәселеге қызығушылық танытып, оны "48 штат мәселесі" деп атады. "Саяхатшы сатушы мәселесі" деген сөз тіркесін пайдаланған ең алғашқы жарияланым 1949 жылы Джулия Робинсонның "Гамильтон ойыны (саяхатшы сатушы мәселесі)" атты РАНД корпорациясының есебі болды. 1950-1960 жылдары бұл мәселе Еуропа мен АҚШ-тағы ғылыми ортада кеңінен танымал болды, өйткені Санта-Моникадағы РАНД корпорациясы мәселені шешудегі қадамдар үшін сыйлықтар ұсынды. Кристофидес-Сердюков алгоритмі ең нашар жағдайда оңтайлы шешімнен 1,5 есе ұзын шешім береді. Алгоритм қарапайым және жылдам болғандықтан, көптеген адамдар оның оңтайлы шешімге жақын әдіс беруіне үміттенді. Алайда, бұл үміт бірден іске аспады, және Кристофидес-Сердюков 2011 жылға дейін ең нашар жағдай бойынша жақсы әдіс болып қалды, ол кезде "графикалық" ТСП-лардың кіші жиынтығы үшін (өте) сәл жақсартылған жуықтама алгоритмі жасалды. 2020 жылы бұл шағын жақсарту толық (метриялық) ТСП-ға дейін кеңейтілді. Ричард М. Карп 1972 жылы Гамильтон циклы мәселесінің NP-толық екенін көрсетті, бұл ТСП-ның NP-қиындығын білдіреді. Бұл оңтайлы маршруттарды табудың есептеу қиындығына математикалық түсіндірме берді. 1970 және 1980 жылдардың соңында Гротшель, Падберг, Риналди және басқалар кесу жазылымдарын және тармақталу және шектеу әдістерін қолданып, 2392 қалаға дейін шешімдерді дәл шеше алды. 1990 жылдары Апплегейт, Биксби, Чватал және Кук Конкорд бағдарламасын жасады, ол көптеген жаңа рекордтық шешімдерде қолданылды. Герхард Райнельт 1991 жылы TSPLIB-ті жариялады, бұл әртүрлі қиындық деңгейлеріндегі эталондық жағдайлардың жинағы, оны көптеген зерттеу топтары нәтижелерді салыстыру үшін пайдаланды. 2006 жылы Кук және басқалар микрочип орналасу мәселесі арқылы берілген 85 900 қалалық инстанция арқылы оңтайлы маршрутты есептеді, қазіргі уақытта бұл ең үлкен шешілген TSPLIB инстанциясы. Миллиондаған қалалары бар көптеген басқа инстанциялар үшін оңтайлы маршруттан 2–3% ішінде болатын шешімдерді табуға болады.

The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, but contains no mathematical treatment. The TSP was mathematically formulated in the 19th century by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman. Hamilton's icosian game was a recreational puzzle based on finding a Hamiltonian cycle. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger, who defines the problem, considers the obvious brute force algorithm, and observes the non optimality of the nearest neighbour heuristic:
We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route. It was first considered mathematically in the 1930s by Merrill M. Flood who was looking to solve a school bus routing problem. Hassler Whitney at Princeton University generated interest in the problem, which he called the "48 states problem". The earliest publication using the phrase "travelling [or traveling] salesman problem" was the 1949 RAND Corporation report by Julia Robinson, "On the Hamiltonian game (a traveling salesman problem)." In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the United States after the RAND Corporation in Santa Monica offered prizes for steps in solving the problem. the Christofides Serdyukov algorithm yields a solution that, in the worst case, is at most 1.5 times longer than the optimal solution. As the algorithm was simple and quick, many hoped it would give way to a near optimal solution method. However, this hope for improvement did not immediately materialize, and Christofides Serdyukov remained the method with the best worst case scenario until 2011, when a (very) slightly improved approximation algorithm was developed for the subset of "graphical" TSPs. In 2020 this tiny improvement was extended to the full (metric) TSP. Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP complete, which implies the NP hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours. Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2,392 cities, using cutting planes and branch and bound. In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2006, Cook and others computed an optimal tour through an 85,900 city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 2–3% of an optimal tour.

Графикалық мәселе ретінде

TSP бағытталмаған салмақты график ретінде модельдеуге болады, онда қалалар – график түйіндері, жолдар – график қабырғалары, ал жолдың ұзындығы – қабырға салмағы болып табылады. Бұл – әрбір басқа түйінді дәл бір рет басып өтіп, белгіленген түйіндіде басталып, сонда аяқталуға қатысты азайту мәселесі. Көбінесе модель толық график түрінде болады (яғни, түйіндердің кез келген жұбы қабырғамен байланысқан). Егер екі қала арасында жол болмаса, онда жеткілікті ұзын қабырға қосу арқылы графикті толықтыруға болады, бұл оңтайлы маршрутқа әсер етпейді.

Асимметриялық және симметриялық

Симметриялық TSP-де екі қала арасындағы қашықтық екі бағытта да бірдей болады, нәтижесінде бағытталмаған граф пайда болады. Бұл симметрия мүмкін болатын шешімдер санын екі есеге азайтады. Асимметриялық TSP-де екі бағытта да жол болмауы мүмкін немесе қашықтықтар әртүрлі болуы мүмкін, бұл бағытталған графты құрайды. Қозғалыс тығындары, бір бағытты көшелер және әртүрлі тариптермен ұшу билеттері – бұл асимметриялық TSP мәселесін тудыруы мүмкін нақты өмірдегі факторлар.

Қатысушы мәселелер

Графтар теориясы тұрғысынан эквивалентті формулировка мынадай: толық салмақты граф берілген (мұндағы төбелер қалаларды, қабырғалар жолдарды, ал салмақтар жолдың құнын немесе қашықтығын көрсетеді), ең аз салмақты Гамильтон циклін табыңыз. Бұл Гамильтондық жол мәселесінен гөрі жалпылама, ол тек толық емес, салмақталмаған графта Гамильтондық жолдың (немесе циклдің) бар-жоғын сұрайды. Бастапқы қалаға оралу талабы мәселенің есептеу күрделілігін өзгертпейді; Гамильтондық жол мәселесін қараңыз. Тағы бір байланысты мәселе – сатушы саяхаткердің шектеулі мәселесі: салмақты графтағы ең ауыр қабырғаның ең аз салмағы бар Гамильтон циклін табыңыз. Нақты мысал – үлкен автобустармен тар көшелерден қашу. Көлік және логистика салаларынан басқа, бұл мәселе маңызды практикалық қолданысқа ие. Классикалық мысал – басылған схемаларды өндіру: баспа тізбегінде тесіктерді бұрғылау үшін бұрғылау машинасының маршрутын жоспарлау. Роботтық өңдеу немесе бұрғылау қолданбаларында «қалалар» – өңдеуге арналған бөлшектер немесе бұрғылауға арналған тесіктер (әр түрлі өлшемдерде), ал «саяхат құны» роботты қайта жабдықтауға кеткен уақытты қамтиды (бір машинамен жұмыс істеудің реттілігі мәселесі). Сатушы саяхаткердің жалпыланған мәселесі, сондай-ақ «саяхаткер саясаткердің мәселесі» деп те аталады, «мемлекеттермен» айналысады, олардың әрқайсысында (бір немесе бірнеше) «қалалар» бар, және сатушы әр мемлекеттен дәл бір қалаға баруы керек. Бір қолданысы – пышақ алмасуды азайту үшін кесу қорының мәселесіне шешім табу. Тағы бір қолданысы – жартылай өткізгіш өндірісінде бұрғылау; мысалы, Noon және Bean жалпыланған сатушы саяхаткер мәселесін бірдей қалалар санымен, бірақ өзгертілген қашықтық матрицасымен стандартты TSP-ге түрлендіруге болатынын көрсетті. Реттік орналастыру мәселесі қалалар жиынтығына сапар жасау мәселесімен айналысады, онда қалалар арасында басымдық қатынастары бар. Google-дегі әдеттегі сұхбат сұрағы – деректерді өңдеу түйіндері арасында маршрутты қалай жоспарлау; деректерді беру маршруттары уақытқа байланысты өзгереді, бірақ түйіндердің есептеу қуаты мен жад сыйымдылығы да әртүрлі, бұл деректерді қайда жіберу мәселесін күрделендіреді. Сатушы сатып алушы мәселесі өнімдер жиынтығын сатып алуға міндеттелген сатып алушымен айналысады. Ол осы өнімдерді бірнеше қаладан сатып ала алады, бірақ әртүрлі бағамен, және барлық қалалар бірдей өнімдерді ұсынбайды. Мақсаты – қалалардың ішкі жиыны арасындағы маршрутты табу, ол жалпы құнды (саяхат құны + сатып алу құны) азайтады және барлық қажетті өнімдерді сатып алуға мүмкіндік береді.

An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight. This is more general than the Hamiltonian path problem, which only asks if a Hamiltonian path (or cycle) exists in a non complete unweighted graph. The requirement of returning to the starting city does not change the computational complexity of the problem; see Hamiltonian path problem. Another related problem is the bottleneck travelling salesman problem: Find a Hamiltonian cycle in a weighted graph with the minimal weight of the weightiest edge. A real world example is avoiding narrow streets with big buses. The problem is of considerable practical importance, apart from evident transportation and logistics areas. A classic example is in printed circuit manufacturing: scheduling of a route of the drill machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single machine job sequencing problem). The generalized travelling salesman problem, also known as the "travelling politician problem", deals with "states" that have (one or more) "cities", and the salesman must visit exactly one city from each state. One application is encountered in ordering a solution to the cutting stock problem in order to minimize knife changes. Another is concerned with drilling in semiconductor manufacturing; see e. g., Noon and Bean demonstrated that the generalized travelling salesman problem can be transformed into a standard TSP with the same number of cities, but a modified distance matrix. The sequential ordering problem deals with the problem of visiting a set of cities, where precedence relations between the cities exist. A common interview question at Google is how to route data among data processing nodes; routes vary by time to transfer the data, but nodes also differ by their computing power and storage, compounding the problem of where to send data. The travelling purchaser problem deals with a purchaser who is charged with purchasing a set of products. He can purchase these products in several cities, but at different prices, and not all cities offer the same products. The objective is to find a route between a subset of the cities that minimizes total cost (travel cost + purchasing cost) and enables the purchase of all required products.

DantzigFulkersonJohnson формуласы

Қалаларды 1, ..., n сандарымен белгілеп, мынаны анықтаңыз: i қаласынан j қаласына дейінгі арақашықтық деп алыңыз. Содан кейін TSP келесі бүтін сандық сызықтық бағдарламалау мәселесі ретінде жазылуы мүмкін: DFJ формуласының соңғы шектеуі – субтурды жою шектеуі деп аталады – Q-ның ешқандай дұрыс ішкі жиыны субтур құрамайтынын қамтамасыз етеді, сондықтан шешім кіші турлардың бірігісі емес, жалғыз тур болып табылады. Бұл мүмкін шектеулердің экспоненциалдық санына алып келетіндіктен, практикада ол қатарларды жарату арқылы шешіледі.

Эвристикалық және шамалау алгоритмдері

Жақсы шешімдерді жылдам табуға мүмкіндік беретін әртүрлі эвристикалар мен жуықтау алгоритмдері жасалған. Олардың қатарында көп фрагментті алгоритм де бар. Қазіргі заманғы әдістер өте үлкен мәселелерді (миллиондаған қалаларды) ақылға қонымды уақыт ішінде шеше алады, және олардың шешімдері жоғары ықтималдықпен оптималды шешімнен 2–3% ғана ауысады. Бұл асимметриялық және симметриялық TSP-лер үшін де сәйкес келеді. Розенкранц және авторлар NN алгоритмінің үшбұрыш теңсіздігін қанағаттандыратын жағдайларда жуықтау коэффициентіне ие екенін көрсетті. NN алгоритмінің бір түрі – ең жақын фрагмент (NF) операторы, ол ең жақын болып табылатын (фрагмент) саналатын, әлі сапарламаған қалалар тобын байланыстырады, және бір-бірінен кейін келетін итерациялар арқылы қысқарақ маршруттарды таба алады. NF операторын NN алгоритмі арқылы алынған бастапқы шешімді одан әрі жақсарту үшін элиталық модельде де қолдануға болады, онда тек жақсырақ шешімдер ғана қабылданады. Нүктелер жиынының битондық айналымы – бұл нүктелерді төбелері ретінде қамтитын ең аз периметрлі монотонды көпбұрыш; оны динамикалық бағдарламалау арқылы тиімді есептеуге болады. Тағы бір құрылымдық эвристика – Match Twice and Stitch (MTS), екі рет сәйкестендіруді жүзеге асырады, екінші сәйкестендіру бірінші сәйкестендірудің барлық қабырғаларын жойғаннан кейін орындалады, нәтижесінде циклдар жиынтығы пайда болады. Содан кейін циклдар тігіліп, соңғы айналым жасалады.

Кристофид пен Сердюков алгоритмі

Кристофид пен Сердюковтың алгоритмі ұқсас жоспарды ұстанады, бірақ ең аз қамтитын ағашты тағы бір мәселенің – ең аз салмақты толық сәйкестендірудің – шешімімен үйлестіреді. Бұл TSP маршрутын оптималды маршруттан ең көп дегенде 1,5 есе ұзын қылады. Бұл алғашқы жуықтау алгоритмдерінің бірі болды және қиын мәселелерге жуықтау алгоритмдерін практикалық тәсіл ретінде қарастыруға ықпал етті. Шындығында, "алгоритм" термині кейінге дейін жуықтау алгоритмдеріне кеңінен қолданылмады; Кристофид алгоритмі бастапқыда Кристофид эвристикасы деп аталған.

k-opt эвристикасы немесе LinKernighan эвристикасы

Лин–Керниган эвристикасы V опт немесе өзгермелі опт техникасының ерекше жағдайы болып табылады. Ол келесі қадамдарды қамтиды:

Берілген турда, бір-бірімен байланысы жоқ k жиекті жойыңыз. Қалған фрагменттерді турға қайта жинаңыз, ешқандай байланыспаған кіші турларды қалдырмай (яғни, фрагменттің соңғы нүктелерін бір-бірімен қоспаңыз). Бұл қарастырылып отырған саяхатшының мәселесін (TSP) әлдеқайда қарапайым мәселеге дейін жеңілдетеді. Әр фрагменттің соңғы нүктесі 2k – 2 басқа мүмкіндікке қосылуы мүмкін: барлық 2k фрагмент соңғы нүктелерінің ішінде, қарастырылып отырған фрагменттің екі соңғы нүктесі қосылуға рұқсат етілмейді. Мұндай шектеулі 2k қалалық TSP-ні бастапқы фрагменттердің ең төмен құнмен қайта құрастыруын табу үшін күшпен іздеу әдістерін қолдануға болады. k-опт әдістерінің ең танымал түрі – 1965 жылы Bell Labs-тің Шен Лин ұсынған 3-опт әдісі. 3-опт әдісінің ерекше жағдайы – жиектердің ажыратылмауы (екі жиек бір-біріне іргелес). Іс жүзінде, 3 өзгерісті осы ерекше жиынтыққа шектеу арқылы, 2-опттан айтарлықтай жақсартуға қол жеткізу мүмкін, бұл 3-опттың комбинаторлық қиындығын тудырмайды, егер алынып тасталған екі жиек іргелес болса. Осылай аталатын «екі жарым опт» әдісі, турлардың сапасы және оларды құруға қажетті уақыт тұрғысынан 2-опт пен 3-опт арасындағы орташа деңгейде болады.

V-opt эвристикалық

Өзгермелі opt әдісі k opt әдісімен байланысты және оның жалпылама түрі болып табылады. k opt әдістері бастапқы турдан (k) санындағы қабырғаларды алып тастаса, өзгермелі opt әдістері алып тасталатын қабырғалар жиынының мөлшерін белгілемейді. Оның орнына, олар іздеу процесі жалғасқан сайын жиынтықты кеңейтеді. Бұл отбасыдағы ең белгілі әдіс – Линн-Керниган әдісі (жоғарыда 2 opt үшін бұрыс атау ретінде айтылған). Шен Лин мен Брайан Керниган алғаш рет 1972 жылы осы әдісті жариялады, және ол шамамен екі онжылдық бойы саяхатшы сатушы мәселесін шешу үшін ең сенімді эвристика болып табылды. Белгілі бір жетілдірілген өзгермелі opt әдістері 1980-ші жылдардың соңында Дэвид Джонсон және оның зерттеу тобы Bell Labs-та жасалды. Бұл әдістер (кейде Линн-Керниган-Джонсон деп аталады) Линн-Керниган әдісіне негізделген, сондай-ақ табу іздеу және эволюциялық есептеулерден алынған идеяларды қамтиды. Негізгі Линн-Керниган техникасы кем дегенде 3 opt деңгейінде нәтижелер береді. Линн-Керниган-Джонсон әдістері Линн-Керниган турын есептейді, содан кейін турды кем дегенде төрт қабырғаны алып тастайтын және турды басқаша қайта құрайтын, «мутация» деп сипатталатын өзгеріс арқылы бұзады, содан кейін жаңа турды V opt арқылы жақсартады. Мутация көбінесе турды Линн-Керниган анықтаған жергілікті минимумнан жылжытуға жеткілікті. V opt әдістері мәселенің ең қуатты эвристикасы болып саналады және Гамильтон циклы мәселесі және басқа эвристикалардың күшін жоятын басқа метрикалық емес TSP сияқты ерекше жағдайларды шеше алады. Көптеген жылдар бойы Линн-Керниган-Джонсон оңтайлы шешімдері белгілі барлық TSP үшін оңтайлы шешімдерді анықтады және әдіс қолданылған басқа барлық TSP үшін ең жақсы шешімдерді тапты.

Кездейсоқ жақсарту

Жергілікті іздеу эвристикалық кіші алгоритмдерін қолданатын оңтайландырылған Марков тізбегі алгоритмдері 700-800 қала үшін ең оңтайлы маршрутқа өте жақын маршрутты анықтай алады. TSP – генетикалық алгоритмдер, симуляцияланған қайнату, табу іздеу, құмырсқалар тобын оңтайландыру, өзен қалыптасу динамикасы (үйіршік интеллектін қараңыз) және кросс-энтропия әдісі сияқты комбинаторлық оңтайландыруға арналған көптеген жалпы эвристикалардың сынақ тасы болып табылады.

Инсертті шектеу эвристикасы

Бұл конвекс қабықшасы сияқты кіші турдан басталып, содан кейін басқа төбелер қосылады.

Құмырсқалар колониясын оңтайландыру

Жасанды интеллект зерттеушісі Марко Дориго 1993 жылы TSP үшін «жақсы шешімдерді» эвристикалық түрде жасау әдісін сипаттады, ол ACS (құмырсқалар колониясы жүйесі) деп аталатын құмырсқалар колониясының симуляциясын пайдаланады. Ол тамақ көздері мен ұясы арасындағы ең қысқа жолдарды табу үшін нақты құмырсқалардың мінез-құлқына негізделген, бұл әрбір құмырсқаның басқа құмырсқалар қалдырған феромон иісін ұнататынынан туындайтын пайда болатын қасиет. ACS картадағы көптеген мүмкін маршруттарды зерттеу үшін көптеген виртуалды құмырсқа агенттерін жібереді. Әр құмырсқа келесі қалаға бару ықтималдығын қалаға дейінгі қашықтық пен сол қалаға апаратын қабырғаға салынған виртуалды феромон мөлшерін ескеретін эвристикалық ереже бойынша таңдайды. Құмырсқалар маршруттарды зерттейді, өтіп кеткен әрбір қабырғаға феромон қалдырады, барлығы бір айналымды аяқтағанша. Содан кейін ең қысқа маршрутты аяқтаған құмырсқа өзінің толық маршруты бойынша виртуалды феромонды жаңартады (жалпы маршрут жаңарту). Қалдырылған феромон мөлшері маршруттың ұзындығына кері пропорционал: маршрут неғұрлым қысқа болса, соғұрлым көп феромон қалдырылады.

Асимметриялық

Көп жағдайда TSP желісіндегі екі түйін арасындағы қашықтық екі бағытта да бірдей болады. Егер А-дан В-ға дейінгі қашықтық В-дан А-ға дейінгі қашықтықтан өзгеше болса, онда бұл асимметриялық TSP деп аталады. Асимметриялық TSP-ның нақты қолданылуы – көше деңгейінде маршрутталған маршруттарды оңтайландыру (бір бағытты көшелер, қосымша жолдар, тас жолдар және т.б. салдарынан асимметрия туындайды).

Талдаушының мәселесі

Геометриялық өлшемдер теориясында мынадай ұқсас мәселе бар: Евклид кеңістігінің Е жиынтығын түзетілетін қисыққа қашан қоюға болады (яғни, Е жиынтығындағы әрбір нүктеге тоқтаусыз, шекті ұзындығы бар қисық сызық бола ма)? Бұл мәселе аналитиктердің саяхатшы сатушысының мәселесі деп белгілі.

Квадраттағы кездейсоқ нүктелер жиынтығының жол ұзындығы

Квадраттағы біркелкі таралыммен тәуелсіз кездейсоқ айнымалылар болсын, және осы нүктелер жиынтығы үшін ең қысқа жол ұзындығы (яғни, саяхатшы мәселесінің шешімі) әдеттегі Евклидтік қашықтық бойынша анықталсын. Белгілі болғандай, дерлік сөзсіз түрде,

мұндағы – нақты мәні белгісіз оң тұрақты. Егер (төменде қараңыз) болса, шектелген жинақталу теоремасынан келесісін білуге болады: , демек, -ның төменгі және жоғарғы шектері -ның шектерінен туындайды. Біркелкі таралыммен шеттік таралымдары бар стационарлық эргодикалық процесс бойынша алынған тәуелсіз орналасқан нүктелерді алмастырған жағдайда дерлік сөзсіз шек -ның лимиті болмауы мүмкін.

Жоғарғы шек

Бірде, және сондықтан, квадраттың ені бірдей кесінділерінің ішіндегі нүктелерді монотонды түрде аралайтын қарапайым жол арқылы. Аз ғана адам дәлелдеді, содан кейін Карлофф (1987) оны жақсартты: Фитчер жоғарғы шегін көрсетті.

Есептеу күрделілігі

Мәселе NP қиын екені көрсетілді (нақтырақ айтқанда, ол күрделілік класы FPNP үшін толық; функциялық мәселеге қараңыз), ал шешімді қабылдау мәселесінің түрі ("бағалар мен x саны берілгенде, x-тен арзан айналма жол бар ма, жоқ па, анықтаңыз") NP толық. Түймешік саудагерінің мәселесі де NP қиын. Мәселе қалалардың эвклидтік қашықтықтарымен жазықтықта орналасқан жағдайында да, сондай-ақ басқа да шектеулі жағдайларда да NP қиын болып қалады. Әр қалаға "бір рет қана" бару шартын алып тастау NP қиындығын жоймайды, себебі жазықтықта әр қалаға бір рет қана баратын ең оңтайлы маршрут бар (әйтпесе, үшбұрыш теңсіздігіне сәйкес, қайталап баратын қадамды өткіріп тастау маршруттың ұзындығын ұлғайтпайды).

Ұқсастырудың күрделілігі

Жалпы жағдайда, саяхатшы сатушының ең қысқа маршрутын табу NPO-толық мәселе. Егер қашықтық өлшемі метрикалық (яғни симметриялық) болса, мәселе APX-толық болады, ал Кристофид пен Сердюковтың алгоритмі оны 1,5 есеге жуықтайды. Вера Трауб және де-нің ең жақсы қазіргі алгоритмі 75/74 ең жақсы белгілі жуықтау шегіне жетеді. Саяхатшы сатушының ең ұзақ маршрутын табуға қатысты максимизациялық мәселе 63/38 шегінде жуықталады. Егер қашықтық функциясы симметриялық болса, онда ең ұзақ маршрутты детерминистік алгоритммен 4/3 есеге, ал кездейсоқ алгоритммен жуықтауға болады.

Адам мен жануарлардың жұмыс істеу қабілеті

ТСП, әсіресе мәселенің Евклидтік түрі, когнитивтік психология зерттеушілерінің назарын аударды. Адамдардың оңтайлы шешімдерге жақын, жылдам және дерлік сызықтық тәсілмен шығара алатыны байқалды, бұл өнімділік 10-20 түйінді графиктер үшін 1%-ға дейін, ал 120 түйінді графиктер үшін 11%-ға дейін тиімсіздікке ие. Адамдардың мәселенің жақын оңтайлы шешімдерін дәл және оңай шығара алатыны зерттеушілерді адамдар бір немесе бірнеше эвристика қолданады деген гипотезаға әкелді, олардың ең танымал екеуі – дөңгелек қабықша гипотезасы және қиылыстардан қашу эвристикасы. Алайда, қосымша мәліметтер адам өнімділігінің өте әртүрлі екенін, сондай-ақ жеке ерекшеліктер мен график геометриясының міндетті орындауға әсер ететінін көрсетеді. Дегенмен, нәтижелер компьютердің ТСП бойынша өнімділігін адамдардың осы мәселелерді шешу үшін қолданатын әдістерін түсіну және имитациялау арқылы жақсартуға болатынын көрсетеді, сонымен қатар адам ойлау механизмдері туралы жаңа түсініктерге де әкелді. «Проблемаларды шешу» журналының бірінші саны ТСП-де адам өнімділігі тақырыбына арналды, ал 2011 жылғы шолуда осы тақырыпта ондаған мақала тізілген. Бұл нәтижелер басқа эксперименттермен сәйкес келеді, олар кейбір примат емес жануарлардың күрделі саяхат жолдарын жоспарлай алатынын көрсетті. Бұл примат емес жануарлардың салыстырмалы түрде дамыған кеңістіктік танымдық қабілетке ие болуы мүмкін екенін ұсынады.

Табиғи есептеу

Тамақ көздерінің кеңістіктік орналасуымен қабат келгенде, амебоид Physarum polycephalum тамақ көздері арасындағы тиімді жолды жасау үшін морфологиясын өзгертеді, бұл оны ТСП мәселесіне жуықтап шешім ретінде қарастыруға мүмкіндік береді.

Салыстырмалы көрсеткіштер

TSP алгоритмдерін салыстыру үшін TSPLIB кітапханасы TSP және оған байланысты мәселелердің үлгілік мысалдарымен қамтамасыз етілген; TSPLIB сыртқы сілтемесін қараңыз. Олардың көпшілігі нақты қалалардың тізімдері және нақты басылған схемалардың орналасуы болып табылады.

Танымал мәдениет

"Саяхатшы сатушы" ("Travelling Salesman") режиссері Тимоти Ланзонның фильмі, АҚШ үкіметі компьютер ғылымы тарихындағы ең құпия мәселені – P vs NP мәселесін шешу үшін жалдаған төрт математик туралы айтады. Математик Боб Бош бұл мәселенің шешімдерін TSP өнері деп аталатын бір сала қолданады.