Problém obchodního cestujícího - Travelling salesman problem

Řešení problému obchodního cestujícího: černá čára ukazuje nejkratší možnou smyčku, která spojuje každou červenou tečku.

The problém obchodního cestujícího (nazývané také problém obchodního cestujícího^[1] nebo TSP) se ptá na následující otázku: „Vzhledem k seznamu měst a vzdálenostem mezi každou dvojicí měst, jaká je nejkratší možná trasa, která každé město navštíví přesně jednou a vrátí se do původního města?“ Je to NP-tvrdé problém v kombinatorická optimalizace, důležité v teoretická informatika a operační výzkum.

The problém s cestujícím kupujícím a problém s směrováním vozidla jsou obě zobecnění TSP.

V teorie výpočetní složitosti, rozhodovací verze TSP (pokud je uvedena délka L, úkolem je rozhodnout, zda má graf maximálně prohlídku L) patří do třídy NP-kompletní problémy. Je tedy možné, že nejhorší případ provozní doba pro jakýkoli algoritmus pro zvýšení TSP superpolynomiálně (ale ne více než exponenciálně ) s počtem měst.

Problém byl poprvé formulován v roce 1930 a je jedním z nejintenzivněji studovaných problémů v oblasti optimalizace. Používá se jako měřítko pro mnoho optimalizačních metod. I když je problém výpočetně obtížný, mnoho heuristika a přesné algoritmy jsou známy, takže některé případy s desítkami tisíc měst lze zcela vyřešit a dokonce i problémy s miliony měst lze přiblížit s malým zlomkem 1%.^[2]

TSP má několik aplikací i ve své nejčistší formulaci, jako např plánování, logistika a výroba mikročipy. Mírně upravený se jeví jako dílčí problém v mnoha oblastech, jako např Sekvenování DNA. V těchto aplikacích koncept město představuje například zákazníky, pájecí body nebo fragmenty DNA a koncept vzdálenost představuje cestovní časy nebo náklady, nebo a opatření podobnosti mezi fragmenty DNA. TSP se také objevuje v astronomii, protože astronomové pozorující mnoho zdrojů budou chtít minimalizovat čas strávený pohybem dalekohledu mezi zdroji. V mnoha aplikacích mohou být zavedena další omezení, jako jsou omezené zdroje nebo časová okna.

Dějiny

Původ problému obchodního cestujícího je nejasný. Příručka pro obchodní cestující z roku 1832 zmiňuje problém a zahrnuje ukázky prohlídek Německo a Švýcarsko, ale neobsahuje žádné matematické zacházení.^[3]

William Rowan Hamilton

Problém obchodního cestujícího byl matematicky formulován v 18. letech irským matematikem W.R. Hamilton a britským matematikem Thomas Kirkman. Hamiltonova icosian hra byla rekreační hádanka založená na hledání a Hamiltonovský cyklus.^[4] Obecná forma TSP se zdá být poprvé studována matematiky ve 30. letech ve Vídni a na Harvardu, zejména Karl Menger, který definuje problém, uvažuje o zřejmém algoritmu hrubou silou a sleduje neoptimálnost heuristiky nejbližšího souseda:

Označujeme posel problém (protože v praxi by tuto otázku měl vyřešit každý pošťák, každopádně také mnoho cestujících) úkol najít pro konečně mnoho bodů, jejichž párové vzdálenosti jsou známy, nejkratší cestu spojující tyto body. Tento problém je samozřejmě řešitelný konečně mnoha pokusy. Pravidla, která by posunula počet pokusů pod počet permutací daných bodů, nejsou známa. Pravidlo, že jeden by měl nejdříve přejít z počátečního bodu do nejbližšího bodu, poté do nejbližšího bodu atd., Obecně nepřináší nejkratší trasu.^[5]

To bylo poprvé zváženo matematicky ve 30. letech 20. století Merrill M. Flood který hledal řešení problému se směrováním školního autobusu.^[6]Hassler Whitney na Univerzita Princeton vyvolal zájem o problém, který nazval „problém 48 států“. Nejstarší publikací používající frázi „problém obchodního cestujícího“ byl rok 1949 RAND Corporation zpráva od Julia Robinson „O hře Hamiltonian (problém obchodního cestujícího).“^[7][8]

V padesátých a šedesátých letech se tento problém stal stále populárnějším ve vědeckých kruzích v Evropě a USA RAND Corporation v Santa Monica nabídl ceny za kroky při řešení problému.^[6] Pozoruhodné příspěvky poskytl George Dantzig, Delbert Ray Fulkerson a Selmer M. Johnson od společnosti RAND Corporation, která problém vyjádřila jako celočíselný lineární program a vyvinuli rovina řezání metoda jeho řešení. Napsali to, co je považováno za seminární práci na toto téma, v níž pomocí těchto nových metod vyřešili instanci se 49 městy na optimálnost vytvořením prohlídky a prokázáním, že žádná jiná prohlídka nemůže být kratší. Dantzig, Fulkerson a Johnson však spekulovali, že vzhledem k téměř optimálnímu řešení budeme schopni najít optimálnost nebo dokázat optimálnost přidáním malého počtu zvláštních nerovností (řezů). Tuto myšlenku využili k vyřešení svého počátečního 49 městského problému pomocí řetězcového modelu. Zjistili, že k vyřešení problému s 49 městy potřebují pouze 26 škrtů. I když tento článek neposkytl algoritmický přístup k problémům TSP, myšlenky, které v něm byly, byly nepostradatelné pro pozdější vytvoření přesných metod řešení pro TSP, ačkoli nalezení algoritmického přístupu při vytváření těchto řezů by trvalo 15 let.^[6] Kromě metod roviny řezu použili Dantzig, Fulkerson a Johnson větev a svázaný algoritmy snad poprvé.^[6]

V roce 1959 Jillian Beardwood J.H. Halton a John Hammersley publikoval v časopise Cambridge Philosophical Society článek s názvem „Nejkratší cesta mnoha body“.^[9] Věta Beardwood – Halton – Hammersley poskytuje praktické řešení problému obchodního cestujícího. Autoři odvodili asymptotický vzorec k určení délky nejkratší trasy pro obchodníka, který začíná doma nebo v kanceláři a navštíví pevný počet míst před návratem na začátek.

V následujících desetiletích byl problém studován mnoha výzkumníky z matematika, počítačová věda, chemie, fyzika a další vědy. V šedesátých letech však byl vytvořen nový přístup, že místo hledání optimálních řešení by bylo možné vytvořit řešení, jehož délka je prokazatelně omezena násobkem optimální délky, a tím by vznikly spodní hranice problému; ty pak mohou být použity s větvenými a vázanými přístupy. Jedním ze způsobů, jak toho dosáhnout, bylo vytvořit a minimální kostra grafu a poté zdvojnásobte všechny jeho okraje, což vytváří vazbu, že délka optimální cesty je nejvýše dvojnásobkem váhy minimálního kostry.^[6]

V roce 1976 udělali Christofides a Serdyukov nezávisle na sobě velký pokrok v tomto směru:^[10] the Algoritmus Christofides-Serdyukov poskytuje řešení, které je v nejhorším případě maximálně 1,5krát delší než optimální řešení. Protože algoritmus byl tak jednoduchý a rychlý, mnozí doufali, že ustoupí téměř optimální metodě řešení. Toto zůstává metodou s nejlepším nejhorším scénářem. Pro poměrně obecný zvláštní případ problému byl však v roce 2011 poražen nepatrnou rezervou.^[11]

Richard M. Karp v roce 1972 ukázal, že Hamiltonovský cyklus problém byl NP-kompletní, což znamená NP-tvrdost TSP. To poskytlo matematické vysvětlení zjevné výpočetní obtížnosti nalezení optimálních cest.

Velký pokrok byl učiněn na konci 70. a 80. let, kdy Grötschel, Padberg, Rinaldi a další dokázali přesně řešit případy až s 2392 městy pomocí řezacích letadel a větev a svázaný.

V 90. letech Applegate, Bixby, Chvátal, a kuchař vytvořil program Concorde který byl použit v mnoha nedávných řešeních záznamu. Gerhard Reinelt publikoval TSPLIB v roce 1991, soubor srovnávacích příkladů různé obtížnosti, který byl použit mnoha výzkumnými skupinami pro srovnání výsledků. V roce 2006 Cook a další vypočítali optimální prohlídku instancí 85 900 měst danou problémem s uspořádáním mikročipů, v současnosti největší řešenou instancí TSPLIB. Pro mnoho dalších případů s miliony měst lze najít řešení, u nichž je zaručeno, že budou v rozmezí 2–3% od optimální cesty.^[12]

V roce 2020 byl vyvinut mírně vylepšený aproximační algoritmus.^[13][14]

Popis

Jako problém s grafem

Symetrický TSP se čtyřmi městy

TSP lze modelovat jako neorientovaný vážený graf, takže města jsou grafy vrcholy, cesty jsou grafy hrany a vzdálenost cesty je váha hrany. Jedná se o problém s minimalizací, který začíná a končí ve stanoveném čase vrchol po vzájemné návštěvě vrchol přesně jednou. Model je často a kompletní graf (tj. každá dvojice vrcholů je spojena hranou). Pokud mezi dvěma městy neexistuje žádná cesta, přidání libovolně dlouhé hrany dokončí graf bez ovlivnění optimální trasy.

Asymetrické a symetrické

V symetrický TSP, vzdálenost mezi dvěma městy je stejná v každém opačném směru, tvořící neorientovaný graf. Tato symetrie snižuje počet možných řešení na polovinu. V asymetrický TSP, cesty nemusí existovat v obou směrech nebo mohou být různé vzdálenosti, které tvoří a řízený graf. Dopravní kolize, jednosměrné ulice, a letenky pro města s různými odletovými a příletovými poplatky jsou příklady toho, jak by se tato symetrie mohla rozpadnout.

Související problémy

• Ekvivalentní formulace ve smyslu teorie grafů je: Vzhledem k tomu, a kompletní vážený graf (kde vrcholy by představovaly města, hrany by představovaly silnice a váhy by byly cena nebo vzdálenost dané silnice), najděte Hamiltonovský cyklus s nejmenší hmotností.
• Požadavek návratu do výchozího města nemění výpočetní složitost problému, viz Problém hamiltonovské cesty.
• Dalším souvisejícím problémem je Problém úzkého hrdla obchodního cestujícího (úzké místo TSP): Najděte Hamiltonovský cyklus v a vážený graf s minimální hmotností nejtěžší okraj. Například vyhýbání se úzkým uličkám s velkými autobusy.^[15] Problém má značný praktický význam, kromě zjevných přepravních a logistických oblastí. Klasický příklad je v tištěný obvod výroba: plánování trasy trasy vrtat stroj na vrtání otvorů do PCB. V aplikacích pro robotické obrábění nebo vrtání jsou „městy“ součásti ke stroji nebo díry (různých velikostí) k vrtání a „náklady na cestování“ zahrnují čas na přestavení robota (problém se sekvenováním úlohy jednoho stroje).^[16]
• The zobecněný problém obchodního cestujícího, známý také jako „problém cestovního politika“, se zabývá „státy“, které mají (jedno nebo více) „měst“, a prodejce musí navštívit přesně jedno „město“ z každého „státu“. Jedna aplikace se vyskytla při objednávání řešení problém řezného materiálu aby se minimalizovaly změny nože. Další se týká vrtání polovodič výroba, viz např. US patent 7 054 798 . Poledne a Bean prokázali, že obecný problém obchodního cestujícího lze transformovat na standardní problém obchodního cestujícího se stejným počtem měst, ale upravený matice vzdálenosti.
• Problém sekvenčního řazení se zabývá problémem návštěvy souboru měst, kde existují prioritní vztahy mezi městy.
• Běžnou dotazovací otázkou na Googlu je, jak směrovat data mezi uzly zpracování dat; trasy se liší časem pro přenos dat, ale uzly se také liší jejich výpočetním výkonem a úložištěm, což zvyšuje problém, kam posílat data.
• The problém s cestujícím kupujícím jedná s kupujícím, který je pověřen nákupem sady produktů. Může si tyto produkty koupit v několika městech, ale za různé ceny a ne všechna města nabízejí stejné produkty. Cílem je najít cestu mezi podmnožinou měst, která minimalizuje celkové náklady (cestovní náklady + pořizovací náklady) a která umožňuje nákup všech požadovaných produktů.

Celočíselné formulace lineárního programování

TSP lze formulovat jako celočíselný lineární program.^[17][18][19] Je známo několik formulací. Dvě pozoruhodné formulace jsou formulace Miller – Tucker – Zemlin (MTZ) a Dantzig – Fulkerson – Johnson (DFJ). Formulace DFJ je silnější, ačkoli formulace MTZ je v některých nastaveních stále užitečná.^[20][21]

Formulace Miller – Tucker – Zemlin

Označte města čísly 1,…, n a definovat:

${displaystyle x_ {ij} = {egin {cases} 1 & {ext {the cesta goes from city}} i {ext {to city}} j 0 & {ext {else}} end {cases}}}$

Pro i = 1, …, n, nechť ${displaystyle u_ {i}}$ být fiktivní proměnnou a nakonec vzít ${displaystyle c_ {ij}> 0}$ být vzdálenost od města i do města j. Potom lze TSP zapsat jako následující celočíselný problém lineárního programování:

${displaystyle {egin {aligned} min & sum _ {i = 1} ^ {n} sum _ {jeq i, j = 1} ^ {n} c_ {ij} x_ {ij} dvojtečka && & x_ {ij} v { 0,1} && i, j = 1, ldots, n; & u_ {i} v mathbf {Z} && i = 2, ldots, n; & sum _ {i = 1, ieq j} ^ {n} x_ {ij } = 1 && j = 1, ldots, n; & sum _ {j = 1, jeq i} ^ {n} x_ {ij} = 1 && i = 1, ldots, n; & u_ {i} -u_ {j} + nx_ {ij} leq n-1 && 2leq ieq jleq n; & 1leq u_ {i} leq n-1 && 2leq ileq n.end {zarovnáno}}}$

První sada rovností vyžaduje, aby se ke každému městu dostalo přesně z jednoho jiného města, a druhá sada rovností vyžaduje, aby z každého města došlo k odletu přesně do jednoho dalšího města. Poslední omezení vynucují, že existuje pouze jedna prohlídka pokrývající všechna města, a nikoli dvě nebo více nesouvislých prohlídek, které pokrývají pouze všechna města. Abychom to dokázali, níže je ukázáno (1), že každé proveditelné řešení obsahuje pouze jednu uzavřenou posloupnost měst, a (2), že pro každou jednotlivou prohlídku zahrnující všechna města existují hodnoty pro figuríny ${displaystyle u_ {i}}$ které uspokojují omezení. (Fiktivní proměnné označují pořadí prohlídek, takové, že ${displaystyle u_ {i}$ znamená město ${displaystyle i}$ je navštíven před městem ${displaystyle j}$. Toho lze dosáhnout zvýšením ${displaystyle u_ {i}}$ při každé návštěvě.)

Abychom prokázali, že každé proveditelné řešení obsahuje pouze jednu uzavřenou posloupnost měst, stačí ukázat, že každý podúrovník v proveditelném řešení prochází městem 1 (s tím, že rovnosti zajistí, že může existovat pouze jedna taková prohlídka). Neboť pokud sečteme všechny nerovnosti odpovídající ${displaystyle x_ {ij} = 1}$ pro jakýkoli obrys k kroky, které neprocházejí městem 1, získáváme:

${displaystyle nkleq (n-1) k,}$

což je rozpor.

Nyní je třeba ukázat, že pro každou jednotlivou prohlídku zahrnující všechna města existují hodnoty pro fiktivní proměnné ${displaystyle u_ {i}}$ které uspokojují omezení.

Bez ztráty obecnosti definujte prohlídku jako původní (a končící) ve městě 1. Vyberte ${displaystyle u_ {i} = t}$ pokud město i je navštíven v kroku t (i, t = 1, 2, ..., n). Pak

${displaystyle u_ {i} -u_ {j} leq n-1,}$

od té doby ${displaystyle u_ {i}}$ nemůže být větší než n a ${displaystyle u_ {j}}$ nesmí být menší než 1; omezení jsou tedy splněna kdykoli ${displaystyle x_ {ij} = 0.}$ Pro ${displaystyle x_ {ij} = 1}$, my máme:

${displaystyle u_ {i} -u_ {j} + nx_ {ij} = (t) - (t + 1) + n = n-1,}$

uspokojení omezení.

Formulace Dantzig – Fulkerson – Johnson

Označte města čísly 1,…, n a definovat:

${displaystyle x_ {ij} = {egin {cases} 1 & {ext {the cesta goes from city}} i {ext {to city}} j 0 & {ext {else}} end {cases}}}$

Vzít ${displaystyle c_ {ij}> 0}$ být vzdálenost od města i do města j. Potom lze TSP zapsat jako následující celočíselný problém lineárního programování:

${displaystyle {egin {aligned} min & sum _ {i = 1} ^ {n} sum _ {jeq i, j = 1} ^ {n} c_ {ij} x_ {ij} dvojtečka && & x_ {ij} v { 0,1} && i, j = 1, ldots, n; & sum _ {i = 1, ieq j} ^ {n} x_ {ij} = 1 && j = 1, ldots, n; & sum _ {j = 1, jeq i} ^ {n} x_ {ij} = 1 && i = 1, ldots, n; & sum _ {iin Q} {sum _ {jeq i, jin Q} {x_ {ij}}} leq | Q | -1 && forall Qsubsetneq {1, ldots, n}, | Q | geq 2 end {zarovnáno}}}$

Poslední omezení formulace DFJ zajišťuje, že mezi nezačínajícími vrcholy nejsou žádné dílčí prohlídky, takže vrácené řešení je jediná prohlídka a ne spojení menších prohlídek. Protože to vede k exponenciálnímu počtu možných omezení, v praxi se to řeší pomocí generování zpožděného sloupce.

Výpočet řešení

Tradiční linie útoku na NP-tvrdé problémy jsou následující:

• Vymýšlet přesné algoritmy, které fungují přiměřeně rychle pouze u malých velikostí problémů.
• Vytvoření „neoptimálního“ nebo heuristické algoritmy tj. algoritmy, které poskytují přibližná řešení v rozumném čase.
• Hledání zvláštních případů problému („dílčích problémů“), u nichž je možná lepší nebo přesnější heuristika.

Přesné algoritmy

Nejpřímějším řešením by bylo vyzkoušet vše obměny (seřazené kombinace) a uvidíte, která je nejlevnější (pomocí vyhledávání hrubou silou ). Délka tohoto přístupu je v polynomiálním faktoru ${displaystyle O (n!)}$, faktoriál počtu měst, takže toto řešení se stává nepraktickým i pro pouhých 20 měst.

Jedna z prvních aplikací aplikace dynamické programování je Aldrid-Karpův algoritmus který problém včas vyřeší ${displaystyle O (n ^ {2} 2 ^ {n})}$.^[22] Této hranice bylo také dosaženo vyloučením - zahrnutím v pokusu předcházejícím přístupu dynamického programování.

Řešení symetrického TSP se 7 městy pomocí vyhledávání hrubou silou. Poznámka: Počet permutací: (7−1)! / 2 = 360

Zlepšení těchto časových limitů se zdá být obtížné. Například nebylo stanoveno, zda přesný algoritmus pro TSP, který běží v čase ${displaystyle O (1,9999 ^ {n})}$ existuje.^[23]

Mezi další přístupy patří:

• Rozličný rozvětvené a vázané algoritmy, které lze použít ke zpracování TSP obsahujících 40–60 měst.

Řešení TSP se 7 městy pomocí jednoduchého algoritmu Branch and bound. Poznámka: Počet permutací je mnohem menší než vyhledávání hrubou silou

• Algoritmy progresivního zlepšování, které používají techniky připomínající lineární programování. Funguje dobře až pro 200 měst.
• Provádění rozvětvené a vázané a problémové generování řezů (větev a řez^[24]); toto je způsob volby pro řešení velkých instancí. Tento přístup drží současný rekord a řeší instanci s 85 900 městy, viz Applegate a kol. (2006).

Přesné řešení pro 15 112 německých měst z TSPLIB bylo nalezeno v roce 2001 pomocí metoda řezací roviny navrhl George Dantzig, Ray Fulkerson, a Selmer M. Johnson v roce 1954, na základě lineární programování. Výpočty byly prováděny na síti 110 procesorů umístěných na Rice University a Univerzita Princeton. Celková doba výpočtu byla ekvivalentní 22,6 roku na jednom 500 MHz Alfa procesor. V květnu 2004 byl vyřešen problém obchodního cestujícího s návštěvou všech 24 978 měst ve Švédsku: byla nalezena prohlídka v délce přibližně 72 500 kilometrů a bylo prokázáno, že kratší prohlídka neexistuje.^[25] V březnu 2005 byl problém obchodního cestujícího s návštěvou všech 33 810 bodů v desce s plošnými spoji vyřešen pomocí Řešič Concorde TSP: byla nalezena prohlídka o délce 66 048 945 jednotek a bylo prokázáno, že kratší prohlídka neexistuje. Výpočet trval přibližně 15,7 CPU let (Cook et al. 2006). V dubnu 2006 byla instance s 85 900 body vyřešena pomocí Řešič Concorde TSP, který přebírá 136 CPU let, viz Applegate a kol. (2006).

Heuristické a aproximační algoritmy

Rozličný heuristika a aproximační algoritmy, které rychle přinášejí dobrá řešení, byly navrženy. Mezi ně patří Vícefragmentový algoritmus. Moderní metody mohou v rozumné době najít řešení pro extrémně velké problémy (miliony měst), která jsou s vysokou pravděpodobností vzdálena jen 2–3% od optimálního řešení.^[12]

Je rozpoznáno několik kategorií heuristiky.

Konstruktivní heuristika

Algoritmus nejbližšího souseda pro TSP se 7 městy. Řešení se mění s tím, jak se mění výchozí bod

The algoritmus nejbližšího souseda (NN) (A chamtivý algoritmus ) umožňuje prodejci zvolit nejbližší nenavštívené město jako svůj další krok. Tento algoritmus rychle poskytuje efektivně krátkou trasu. U N měst náhodně rozmístěných v letadle poskytuje algoritmus v průměru cestu o 25% delší než nejkratší možná cesta.^[26] Existuje však mnoho speciálně uspořádaných distribucí měst, díky nimž je algoritmus NN nejhorší cestou.^[27] To platí pro asymetrické i symetrické TSP.^[28] Rosenkrantz a kol.^[29] ukázaly, že algoritmus NN má aproximační faktor ${displaystyle Theta (log | V |)}$ pro případy splňující nerovnost trojúhelníku. Varianta algoritmu NN, nazývaná operátor Nearest Fragment (NF), který spojuje skupinu (fragment) nejbližších nenavštívených měst, může najít kratší trasy s postupnými iteracemi.^[30] Operátor NF lze také použít na počáteční řešení získané algoritmem NN pro další zlepšení v elitářském modelu, kde jsou přijímána pouze lepší řešení.

The bitonické turné ze sady bodů je minimální obvod monotónní mnohoúhelník který má body jako své vrcholy; lze jej efektivně vypočítat pomocí dynamické programování.

Další konstruktivní heuristika „Match Twice and Stitch (MTS), provádí dva po sobě jdoucí párování, kde je druhé párování provedeno po odstranění všech okrajů prvního párování, čímž se získá sada cyklů. Cykly se poté sešívají, aby se vytvořila závěrečná prohlídka.^[31]

Algoritmus Christofides a Serdyukov

Vytvoření shody

Pomocí heuristické zkratky v grafu vytvořeném výše uvedenou shodou

The algoritmus Christofides a Serdyukov sleduje podobný obrys, ale kombinuje minimální kostru s řešením jiného problému, minimální váhy perfektní shoda. To poskytuje prohlídku TSP, která je maximálně 1,5krát optimální. Byl to jeden z prvních aproximační algoritmy, a byl částečně zodpovědný za upozorňování na aproximační algoritmy jako praktický přístup k neřešitelným problémům. Ve skutečnosti se termín „algoritmus“ rozšířil na aproximační algoritmy až později; Christofidův algoritmus byl původně označován jako Christofidova heuristika.^[10]

Tento algoritmus se dívá na věci jinak pomocí výsledku z teorie grafů, který pomáhá zlepšit LB TSP, který vznikl zdvojnásobením nákladů na minimální kostru. Vzhledem k Euleriánský graf můžeme najít Eulerian tour v ${displaystyle O (n)}$ čas.^[6] Pokud bychom tedy měli euleriánský graf s městy z TSP jako vrcholy, snadno vidíme, že bychom mohli použít takovou metodu pro nalezení Eulerianovy cesty k nalezení řešení TSP. Podle trojúhelníková nerovnost víme, že turné TSP nemůže být delší než turné Eulerian a jako takové máme LB pro TSP. Taková metoda je popsána níže.

1. Najděte minimální kostru pro problém
2. Vytvořte duplikáty pro každou hranu a vytvořte euleriánský graf
3. Najděte pro tento graf prohlídku Eulerian
4. Převést na TSP: je-li město navštěvováno dvakrát, vytvořte zástupce města před tímto v prohlídce k tomuto po něm.

Ke zlepšení dolní meze je zapotřebí lepší způsob vytváření euleriánského grafu. Podle trojúhelníkové nerovnosti musí mít nejlepší euleriánský graf stejné náklady jako nejlepší cesta obchodního cestujícího, a proto je hledání optimálních euleriánských grafů přinejmenším stejně těžké jako TSP. Jedním ze způsobů, jak toho dosáhnout, je minimální hmotnost vhodný pomocí algoritmů ${displaystyle O (n ^ {3})}$.^[6]

Vytvoření grafu do euleriánského grafu začíná stromem minimálního rozsahu. Pak musí být všechny vrcholy lichého pořadí rovné. Musí tedy být přidána shoda pro vrcholy lichých stupňů, což zvyšuje pořadí každého vrcholu lichého stupně o jeden.^[6] Toto nám ponechává graf, kde každý vrchol je sudého řádu, který je tedy Eulerian. Přizpůsobení výše uvedené metody dává algoritmus Christofides a Serdyukov.

1. Najděte minimální kostru pro problém
2. Vytvořte shodu problému se sadou měst lichého pořadí.
3. Najděte pro tento graf prohlídku Eulerian
4. Převod na TSP pomocí zkratek.

Párová výměna

Příklad iterace 2 opt

Párová výměna nebo 2-opt technika zahrnuje iterativní odstranění dvou hran a jejich nahrazení dvěma různými hranami, které znovu spojují fragmenty vytvořené odstraněním hran, do nové a kratší prohlídky. Podobně 3-opt technika odstraní 3 hrany a znovu je spojí, aby vytvořily kratší prohlídku. Jedná se o speciální případy k-opt metoda. Etiketa Lin – Kernighan je často slyšené nesprávné pojmenování pro 2-opt. Lin – Kernighan je ve skutečnosti obecnější metodou k-opt.

U euklidovských instancí dává heuristika 2 optů průměrná řešení, která jsou přibližně o 5% lepší než Christofidův algoritmus. Pokud začneme s počátečním řešením vytvořeným pomocí a chamtivý algoritmus, průměrný počet tahů opět výrazně klesá a je ${displaystyle O (n)}$. U náhodných startů je však průměrný počet tahů ${displaystyle O (nlog (n))}$. Přestože se jedná o malé zvětšení velikosti, počáteční počet tahů pro malé problémy je 10krát větší pro náhodný start ve srovnání s jedním provedeným chamtivou heuristikou. Důvodem je, že taková heuristika se dvěma opty využívá „špatné“ části řešení, jako jsou přechody. Tyto typy heuristiky se často používají uvnitř Problém s směrováním vozidla heuristiky k opětovné optimalizaci řešení tras.^[26]

k-opt heuristická neboli Lin – Kernighanova heuristika

Lin – Kernighanova heuristika je zvláštním případem PROTI-opt nebo variable-opt technika. Zahrnuje následující kroky:

1. Při prohlídce smazat k vzájemně nesouvislé hrany.
2. Znovu sestavte zbývající fragmenty do prohlídky a nezanechávejte žádné disjunktní podokna (tj. Nespojujte koncové body fragmentu dohromady). To ve skutečnosti zjednodušuje uvažovaný TSP na mnohem jednodušší problém.
3. Ke každému koncovému bodu fragmentu lze připojit 2k − 2 další možnosti: ze 2k celkové dostupné koncové body fragmentu jsou dva koncové body uvažovaného fragmentu zakázány. Tak omezený 2k-city TSP lze poté vyřešit metodami hrubou silou k nalezení nejlevnější rekombinace původních fragmentů.

Nejoblíbenější z k-opt metody jsou 3-opt, jak je zavedeno Shen Lin z Bell Labs v roce 1965. Zvláštní případ 3-opt je ten, kde hrany nejsou disjunktní (dva z okrajů sousedí jeden s druhým). V praxi je často možné dosáhnout podstatného zlepšení oproti 2-opt bez kombinatorických nákladů na obecný 3-opt omezením 3-změn této speciální podmnožiny, kde dva z odstraněných okrajů sousedí. Tento takzvaný dva a půl opt obvykle spadá zhruba do poloviny mezi 2 opt a 3 opt, a to jak z hlediska kvality dosažených prohlídek, tak času potřebného k dosažení těchto prohlídek.

PROTI-opt heuristické

Metoda variabilní opt souvisí s a zobecněním k-opt metoda. Vzhledem k tomu, že k-opt metody odstraní pevné číslo (k) hran z původní prohlídky, metody variabilní optiky neopravují velikost sady hran, kterou chcete odstranit. Místo toho rostou, jak proces hledání pokračuje. Nejznámější metodou v této rodině je metoda Lin – Kernighan (zmíněná výše jako nesprávné pojmenování pro 2-opt). Shen Lin a Brian Kernighan poprvé publikovali svou metodu v roce 1972 a byla to nejspolehlivější heuristika pro řešení problémů obchodního cestujícího téměř dvě desetiletí. Pokročilejší metody s proměnnou optikou byly vyvinuty v Bell Labs na konci 80. let Davidem Johnsonem a jeho výzkumným týmem. Tyto metody (někdy nazývané Lin – Kernighan – Johnson ) stavět na metodě Lin – Kernighan a přidávat nápady z tabu vyhledávání a evoluční výpočty. Základní technika Lin – Kernighan dává výsledky, u nichž je zaručeno, že budou minimálně 3-opt. Metody Lin – Kernighan – Johnson vypočítají prohlídku Lin – Kernighan a poté ji naruší tím, co bylo popsáno jako mutace, která odstraní alespoň čtyři okraje a znovu spojí cestu jiným způsobem, poté PROTI- otevření nové prohlídky. Mutace často stačí k přesunutí prohlídky z místní minimum identifikoval Lin – Kernighan. PROTI-opt metody jsou široce považovány za nejsilnější heuristiku problému a jsou schopny řešit speciální případy, jako je Hamiltonův cyklický problém a jiné nemetrické TSP, na kterých ostatní heuristiky selhávají. Po mnoho let Lin – Kernighan – Johnson identifikoval optimální řešení pro všechny TSP, kde bylo známé optimální řešení, a určil nejznámější řešení pro všechny ostatní TSP, na kterých byla metoda vyzkoušena.

Náhodné zlepšení

Optimalizováno Markovův řetězec Algoritmy, které používají heuristické sub-algoritmy místního vyhledávání, mohou najít trasu extrémně blízkou optimální trase pro 700 až 800 měst.

TSP je prubířským kamenem pro mnoho obecných heuristik navržených pro kombinatorickou optimalizaci, jako je genetické algoritmy, simulované žíhání, tabu vyhledávání, optimalizace kolonií mravenců, dynamika formování řeky (vidět rojová inteligence ) a metoda křížové entropie.

Optimalizace kolonií mravenců

Umělá inteligence výzkumník Marco Dorigo popsal v roce 1993 metodu heuristického generování „dobrých řešení“ TSP pomocí a simulace kolonie mravenců volala ACS (systém kolonií mravenců).^[32] Modeluje chování pozorované u skutečných mravenců, aby našel krátké cesty mezi zdroji potravy a jejich hnízdem, an vznikající chování vyplývající z preferencí každého mravence následovat stopové feromony uloženy jinými mravenci.

ACS vysílá velké množství agentů virtuálních mravenců, aby prozkoumali mnoho možných cest na mapě. Každý mravenec si pravděpodobně vybere další město, které má navštívit, na základě heuristiky kombinující vzdálenost do města a množství virtuálního feromonu uloženého na okraji města. Mravenci zkoumají a ukládají feromon na každou hranu, kterou protínají, dokud nedokončí prohlídku. V tomto okamžiku mravenec, který dokončil nejkratší prohlídku, vloží virtuální feromon po celé své prohlídkové trase (globální aktualizace stezky). Množství uloženého feromonu je nepřímo úměrné délce prohlídky: čím kratší je prohlídka, tím více se ukládá.

Algoritmus optimalizace kolonií mravenců pro TSP se 7 městy: Červené a silné čáry na mapě feromonů naznačují přítomnost více feromonů

Speciální případy

Metrický

V metrický TSP, také známý jako delta-TSP nebo Δ-TSP, meziměstské vzdálenosti splňují nerovnost trojúhelníku.

Velmi přirozeným omezením TSP je vyžadovat, aby vzdálenosti mezi městy tvořily a metrický uspokojit nerovnost trojúhelníku; to je přímé spojení z A na B nikdy není dál než trasa přes střední C:

${displaystyle d_ {AB} leq d_ {AC} + d_ {CB}}$.

Okraj se rozprostírá a poté se staví a metrický na množině vrcholů. Když jsou města vnímána jako body v rovině, mnoho přirozených funkce vzdálenosti jsou metriky a tolik přirozených instancí TSP uspokojuje toto omezení.

Následuje několik příkladů metrických TSP pro různé metriky.

• V euklidovském TSP (viz níže) je vzdálenost mezi dvěma městy Euklidovská vzdálenost mezi odpovídajícími body.
• V přímočarém TSP je vzdálenost mezi dvěma městy součtem absolutních hodnot jejich rozdílů X- a y-souřadnice. Tato metrika se často nazývá Vzdálenost na Manhattanu nebo metrika městského bloku.
• V maximální metrika, vzdálenost mezi dvěma body je maximem absolutních hodnot rozdílů jejich X- a y-souřadnice.

Poslední dvě metriky se objevují například při směrování stroje, který vyvrtá danou sadu děr v a tištěný spoj. Metrika na Manhattanu odpovídá stroji, který nastavuje nejprve jednu souřadnici a poté druhou, takže čas pro přesun do nového bodu je součtem obou pohybů. Maximální metrika odpovídá stroji, který nastavuje obě souřadnice současně, takže doba pro přesun do nového bodu je pomalejší ze dvou pohybů.

Ve své definici TSP neumožňuje dvakrát navštívit města, ale mnoho aplikací toto omezení nevyžaduje. V takových případech lze symetrickou nemetrickou instanci snížit na metrickou. Tím se nahradí původní graf úplným grafem, ve kterém je vzdálenost mezi městy ${displaystyle d_ {AB}}$ se nahrazuje nejkratší cesta mezi A a B v původním grafu.

Euklidovský

Když vstupními čísly mohou být libovolná reálná čísla, je euklidovský TSP konkrétním případem metrického TSP, protože vzdálenosti v rovině se řídí nerovností trojúhelníku. Když vstupní čísla musí být celá čísla, porovnání délek prohlídek zahrnuje porovnání součtů s odmocninami.

Stejně jako obecný TSP je i euklidovský TSP v obou případech NP-tvrdý. S racionálními souřadnicemi a diskretizovanou metrikou (vzdálenosti zaokrouhleno na celé číslo) je problém NP-úplný.^[33] Díky racionálním souřadnicím a skutečné euklidovské metrice je známo, že euklidovská TSP je v hierarchii počítání,^[34] podtřída PSPACE. S libovolnými reálnými souřadnicemi nemůže být euklidovský TSP v takových třídách, protože existuje nespočetně mnoho možných vstupů. Euklidovský TSP je však pravděpodobně nejjednodušší verzí pro přiblížení.^[35] Například minimální kostra grafu přidružená k instanci euklidovského TSP je a Euklidovský minimální kostra, a lze jej tedy vypočítat v očekávaném O (n log n) čas na n bodů (podstatně méně než počet hran). To umožňuje, aby jednoduchý 2-aproximační algoritmus pro TSP s trojúhelníkovou nerovností výše fungoval rychleji.

Obecně platí, že pro všechny C > 0, kde d je počet dimenzí v euklidovském prostoru, existuje algoritmus polynomiálního času, který najde prohlídku délky maximálně (1 + 1 /C) krát optimální pro geometrické instance TSP v

${displaystyle Oleft (n (log n) ^ {(O (c {sqrt {d}})) ^ {d-1}} ight),}$

čas; tomu se říká a schéma aproximace v polynomiálním čase (PTAS).^[36] Sanjeev Arora a Joseph S. B. Mitchell byly oceněny Gödelova cena v roce 2010 za jejich současný objev PTAS pro euklidovský TSP.

V praxi se nadále používají jednodušší heuristiky se slabšími zárukami.

Asymetrický

Ve většině případů je vzdálenost mezi dvěma uzly v síti TSP stejná v obou směrech. Případ, kdy je vzdálenost od A na B is not equal to the distance from B na A is called asymmetric TSP. A practical application of an asymmetric TSP is route optimization using street-level routing (which is made asymmetric by one-way streets, slip-roads, motorways, etc.).

Conversion to symmetric

Solving an asymmetric TSP graph can be somewhat complex. The following is a 3×3 matrix containing all possible path weights between the nodes A, B a C. One option is to turn an asymmetric matrix of size N into a symmetric matrix of size 2N.^[37]

Asymmetric path weights

	A	B	C
A		1	2
B	6		3
C	5	4

To double the size, each of the nodes in the graph is duplicated, creating a second ghost node, linked to the original node with a "ghost" edge of very low (possibly negative) weight, here denoted −w. (Alternatively, the ghost edges have weight 0, and weight w is added to all other edges.) The original 3×3 matrix shown above is visible in the bottom left and the transpose of the original in the top-right. Both copies of the matrix have had their diagonals replaced by the low-cost hop paths, represented by −w. In the new graph, no edge directly links original nodes and no edge directly links ghost nodes.

Symmetric path weights

	A	B	C	A'	B '	C′
A				−w	6	5
B				1	−w	4
C				2	3	−w
A'	−w	1	2
B '	6	−w	3
C′	5	4	−w

The weight −w of the "ghost" edges linking the ghost nodes to the corresponding original nodes must be low enough to ensure that all ghost edges must belong to any optimal symmetric TSP solution on the new graph (w=0 is not always low enough). As a consequence, in the optimal symmetric tour, each original node appears next to its ghost node (e.g. a possible path is ${displaystyle mathrm {A o A' o C o C' o B o B' o A} }$) and by merging the original and ghost nodes again we get an (optimal) solution of the original asymmetric problem (in our example, ${displaystyle mathrm {A o C o B o A} }$).

Analyst's problem

There is an analogous problem in teorie geometrických měr which asks the following: under what conditions may a subset E z Euklidovský prostor be contained in a rectifiable curve (that is, when is there a curve with finite length that visits every point in E)? Tento problém je známý jako analyst's travelling salesman problem.

Path length for random sets of points in a square

Předpokládat ${displaystyle X_ {1}, ldots, X_ {n}}$ jsou ${displaystyle n}$ independent random variables with uniform distribution in the square ${displaystyle [0,1]^{2}}$a nechte ${displaystyle L_{n}^{ast }}$ be the shortest path length (i.e. TSP solution) for this set of points, according to the usual Euklidovská vzdálenost. Je známo^[38] that, almost surely,

${displaystyle {frac {L_{n}^{*}}{sqrt {n}}}ightarrow eta qquad { ext{when }}n o infty ,}$

kde ${displaystyle eta}$ is a positive constant that is not known explicitly. Od té doby ${displaystyle L_{n}^{*}leq 2{sqrt {n}}+2}$ (see below), it follows from bounded convergence theorem že ${displaystyle eta =lim _{n o infty }mathbb {E} [L_{n}^{*}]/{sqrt {n}}}$, hence lower and upper bounds on ${displaystyle eta}$ follow from bounds on ${displaystyle mathbb {E} [L_{n}^{*}]}$.

The almost sure limit ${displaystyle {frac {L_{n}^{*}}{sqrt {n}}}ightarrow eta }$ tak jako ${displaystyle n o infty}$ may not exist if the independent locations ${displaystyle X_ {1}, ldots, X_ {n}}$ are replaced with observations from a stationary ergodic process with uniform marginals.^[39]

Horní hranice

• Jeden má ${displaystyle L^{*}leq 2{sqrt {n}}+2}$, a proto ${displaystyle eta leq 2}$, by using a naive path which visits monotonically the points inside each of ${displaystyle {sqrt {n}}}$ slices of width ${displaystyle 1/{sqrt {n}}}$ in the square.
• Málo^[40] dokázal ${displaystyle L_{n}^{*}leq {sqrt {2n}}+1.75}$, proto ${displaystyle eta leq {sqrt {2}}}$, later improved by Karloff (1987): ${displaystyle eta leq 0.984{sqrt {2}}}$.
• Some study reported^[41] an upper bound that ${displaystyle eta leq 0.92dots }$.
• Some study reported^[42] an upper bound that ${displaystyle eta leq 0.73dots }$.

Dolní mez

• By observing that ${displaystyle mathbb {E} [L_{n}^{*}]}$ je větší než ${displaystyle n}$ times the distance between ${displaystyle X_ {0}}$ and the closest point ${displaystyle X_{i}eq X_{0}}$, one gets (after a short computation)

${displaystyle mathbb {E} [L_{n}^{*}]geq { frac {1}{2}}{sqrt {n}}.}$

• A better lower bound is obtained^[38] by observing that ${displaystyle mathbb {E} [L_{n}^{*}]}$ je větší než ${displaystyle { frac {1}{2}}n}$ times the sum of the distances between ${displaystyle X_ {0}}$ and the closest and second closest points ${displaystyle X_{i},X_{j}eq X_{0}}$, což dává

${displaystyle mathbb {E} [L_{n}^{*}]geq left({ frac {1}{4}}+{ frac {3}{8}}ight){sqrt {n}}={ frac {5}{8}}{sqrt {n}},}$

• The currently^[41] best lower bound is

${displaystyle mathbb {E} [L_{n}^{*}]geq ({ frac {5}{8}}+{ frac {19}{5184}}){sqrt {n}},}$

• Held and Karp^[43] gave a polynomial-time algorithm that provides numerical lower bounds for ${displaystyle L_{n}^{*}}$, and thus for ${displaystyle eta (simeq L_{n}^{*}/{sqrt {n}})}$ which seem to be good up to more or less 1%.^[44] In particular, David S. Johnson^[45] obtained a lower bound by computer experiment:

${displaystyle L_{n}^{*}gtrsim 0.7080{sqrt {n}}+0.522,}$

where 0.522 comes from the points near square boundary which have fewer neighbours,and Christine L. Valenzuela and Antonia J. Jones^[46] obtained the following other numerical lower bound:

${displaystyle L_{n}^{*}gtrsim 0.7078{sqrt {n}}+0.551}$.

Výpočetní složitost

The problem has been shown to be NP-tvrdé (more precisely, it is complete for the třída složitosti FP^NP; vidět funkční problém ) a rozhodovací problém version ("given the costs and a number X, decide whether there is a round-trip route cheaper than X") is NP-kompletní. The bottleneck traveling salesman problem is also NP-hard. The problem remains NP-hard even for the case when the cities are in the plane with Euclidean distances, as well as in a number of other restrictive cases. Removing the condition of visiting each city "only once" does not remove the NP-hardness, since in the planar case there is an optimal tour that visits each city only once (otherwise, by the nerovnost trojúhelníku, a shortcut that skips a repeated visit would not increase the tour length).

Complexity of approximation

In the general case, finding a shortest travelling salesman tour is NPO -kompletní.^[47] If the distance measure is a metrický (and thus symmetric), the problem becomes APX -kompletní^[48] a the algorithm of Christofides and Serdyukov approximates it within 1.5.^[49][50][10] 2020 předtisk improves this bound to ${displaystyle 1.5-10^{-36}}$.^[51]The best known inapproximability bound is 123/122.^[52]

If the distances are restricted to 1 and 2 (but still are a metric) the approximation ratio becomes 8/7.^[53] In the asymmetric case with nerovnost trojúhelníku, only logarithmic performance guarantees are known, the best current algorithm achieves performance ratio 0.814 log(n);^[54] it is an open question if a constant factor approximation exists.The best known inapproximability bound is 75/74.^[52]

The corresponding maximization problem of finding the nejdelší travelling salesman tour is approximable within 63/38.^[55] If the distance function is symmetric, the longest tour can be approximated within 4/3 by a deterministic algorithm^[56] a uvnitř ${displaystyle { frac {1}{25}}(33+varepsilon )}$ by a randomized algorithm.^[57]

Human and animal performance

The TSP, in particular the Euklidovský variant of the problem, has attracted the attention of researchers in kognitivní psychologie. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient for graphs with 10-20 nodes, and 11% less efficient for graphs with 120 nodes.^[58][59] The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic.^[60][61][62] However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to affect performance in the task.^[63][64][65] Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems,^[66] and have also led to new insights into the mechanisms of human thought.^[67] První vydání Journal of Problem Solving was devoted to the topic of human performance on TSP,^[68] and a 2011 review listed dozens of papers on the subject.^[67]

Studie z roku 2011 v poznávání zvířat titled "Let the Pigeon Drive the Bus," named after the children's book Don't Let the Pigeon Drive the Bus!, examined spatial cognition in pigeons by studying their flight patterns between multiple feeders in a laboratory in relation to the travelling salesman problem. In the first experiment, pigeons were placed in the corner of a lab room and allowed to fly to nearby feeders containing peas. The researchers found that pigeons largely used proximity to determine which feeder they would select next. In the second experiment, the feeders were arranged in such a way that flying to the nearest feeder at every opportunity would be largely inefficient if the pigeons needed to visit every feeder. The results of the second experiment indicate that pigeons, while still favoring proximity-based solutions, "can plan several steps ahead along the route when the differences in travel costs between efficient and less efficient routes based on proximity become larger."^[69] These results are consistent with other experiments done with non-primates, which have proven that some non-primates were able to plan complex travel routes. This suggests non-primates may possess a relatively sophisticated spatial cognitive ability.

Natural computation

When presented with a spatial configuration of food sources, the améboid Physarum polycephalum adapts its morphology to create an efficient path between the food sources which can also be viewed as an approximate solution to TSP.^[70] It's considered to present interesting possibilities and it has been studied in the area of natural computing.

Srovnávací hodnoty

For benchmarking of TSP algorithms, TSPLIB^[71] is a library of sample instances of the TSP and related problems is maintained, see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual tištěné obvody.

Populární kultura

• Travelling Salesman, by director Timothy Lanzone, is the story of four mathematicians hired by the U.S. government to solve the most elusive problem in computer-science history: P vs. NP.^[72]

Viz také

• Canadian traveller problem
• Exact algorithm
• Problém kontroly trasy (also known as "Chinese postman problem")
• Set TSP problem
• Sedm mostů v Königsbergu
• Steiner travelling salesman problem
• Výzva metra
• Tube Challenge
• Problém s směrováním vozidla
• Graph exploration

Poznámky

Reference

Další čtení

• Adleman, Leonard (1994), "Molecular Computation of Solutions To Combinatorial Problems" (PDF), Věda, 266 (5187): 1021–4, Bibcode:1994Sci...266.1021A, CiteSeerX  10.1.1.54.2565, doi:10.1126/science.7973651, PMID  7973651, archivovány z originál (PDF) dne 6. února 2005
• Babin, Gilbert; Deneault, Stéphanie; Laportey, Gilbert (2005), "Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem", The Journal of the Operational Research Society, Cahiers du GERAD, Montreal: Group for Research in Decision Analysis, G-2005-02 (3): 402–407, CiteSeerX  10.1.1.89.9953, JSTOR  4622707
• Cook, William (2012). In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press. ISBN  9780691152707.
• Cook, William; Espinoza, Daniel; Goycoolea, Marcos (2007), "Computing with domino-parity inequalities for the TSP", INFORMS Journal o práci na počítači, 19 (3): 356–365, doi:10.1287/ijoc.1060.0204
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (31 July 2009). "35.2: The traveling-salesman problem". Úvod do algoritmů (2. vyd.). MIT Stiskněte. pp. 1027–1033. ISBN  9780262033848.
• Dantzig, G. B.; Fulkerson, R.; Johnson, S. M. (1954), "Solution of a large-scale traveling salesman problem", Operační výzkum, 2 (4): 393–410, doi:10.1287/opre.2.4.393, JSTOR  166695, S2CID  44960960
• Garey, Michael R .; Johnson, David S. (1979). "A2.3: ND22–24". Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman. 211–212. ISBN  9780716710448.
• Goldberg, D. E. (1989), "Genetic Algorithms in Search, Optimization & Machine Learning", Reading: Addison-Wesley, New York: Addison-Wesley, Bibcode:1989gaso.book.....G, ISBN  978-0-201-15767-3
• Gutin, G.; Yeo, A.; Zverovich, A. (15 March 2002). "Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP". Diskrétní aplikovaná matematika. 117 (1–3): 81–86. doi:10.1016/S0166-218X(01)00195-0. ISSN  0166-218X.
• Gutin, G.; Punnen, A. P. (18 May 2007). The Traveling Salesman Problem and Its Variations. Springer USA. ISBN  9780387444598.
• Johnson, D. S.; McGeoch, L. A. (1997), "The Traveling Salesman Problem: A Case Study in Local Optimization", in Aarts, E. H. L.; Lenstra, J. K. (eds.), Local Search in Combinatorial Optimisation (PDF), John Wiley and Sons Ltd., pp. 215–310
• Lawler, E. L .; Shmoys, D. B.; Kan, A. H. G. Rinnooy; Lenstra, J. K. (1985). The Traveling Salesman Problem. John Wiley & Sons, Incorporated. ISBN  9780471904137.
• MacGregor, J. N.; Ormerod, T. (1996), "Human performance on the traveling salesman problem" (PDF), Postřeh a psychofyzika, 58 (4): 527–539, doi:10.3758/BF03213088, PMID  8934685, S2CID  38355042, archivovány z originál (PDF) dne 29. prosince 2009
• Mitchell, J. S. B. (1999), "Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems", SIAM Journal on Computing, 28 (4): 1298–1309, doi:10.1137/S0097539796309764
• Rao, S .; Smith, W. (1998), "Approximating geometrical graphs via 'spanners' and 'banyans'", Řízení, pp. 540–550, CiteSeerX  10.1.1.51.8676
• Rosenkrantz, Daniel J .; Stearns, Richard E .; Lewis, Philip M., II (1977). „Analýza několika heuristik pro problém obchodního cestujícího“. SIAM Journal on Computing. SIAM (Společnost pro průmyslovou a aplikovanou matematiku). 6 (5): 563–581. doi:10.1137/0206041. S2CID  14764079.
• Medveděv, Andrej; Lee, Michael; Butavicius, Marcus; Vickers, Douglas (1. února 2001). "Lidský výkon na vizuálně prezentovaných problémech Traveling Salesman". Psychologický výzkum. 65 (1): 34–45. doi:10,1007 / s004260000031. ISSN  1430-2772. PMID  11505612. S2CID  8986203.
• Walshaw, Chris (2000), Víceúrovňový přístup k problému obchodního cestujícího, CMS Press
• Walshaw, Chris (2001), Víceúrovňový algoritmus Lin-Kernighan-Helsgaun pro problém obchodního cestujícího, CMS Press

externí odkazy

• Problém obchodního cestujícího na Wayback Machine (archivováno 17. prosince 2013) v University of Waterloo
• TSPLIB na University of Heidelberg
• Problém obchodního cestujícího napsal Jon McLoone v rámci demonstračního projektu Wolfram
• Vizualizační nástroj TSP