Problém obchodného cestujúceho

Problém obchodného cestujúceho (z angl. travelling salesman problem - skratka TSP) je jedna z najznámejších optimalizačných úloh. Je to aj vďaka veľkému množstvu jej praktických aplikácií (rozvoz tovaru, osadzovanie súčiastok plošného spoja a podobne).

Podstata problému

Nech je daných N miest a nech je možné dostať sa z každého mesta do všetkých ostatných (buď priamo alebo cez niektoré iné mesto). Nech je každá cesta medzi dvomi navzájom prepojenými mestami ohodnotená číslom, ktoré môže vyjadrovať vzdialenosť, cenu, čas atď. Cieľom obchodného cestujúceho je vybrať sa z mesta, v ktorom sa práve nachádza, navštíviť každé mesto práve raz a vrátiť sa do počiatočného mesta. Pritom sa snaží túto cestu absolvovať tak, aby precestoval čo najmenšiu vzdialenosť, zaplatil čo najmenej peňazí a podobne.

Dejiny

Problém obchodného cestujúceho sa datuje od 19. storočia. V tom období sa ním zaoberal írsky matematik Sir William Rowan Hamilton a britský matematik Thomas Kirkman. V tridsiatych rokoch 20. storočia bola na univerzite vo Viedni a Harvarde popísaná presnejšia matematická formulácia. Výskumné tímy Grotschela a Padberga v priebehu jedného roka (1987) vyriešili úlohy s 532 mestami v USA, so 666 rôznymi miestami na svete a úlohy vŕtania otvorov pri výrobe dosiek s tlačenými spojmi s 1002 a 2392 bodmi.
Applegate, Bixby, Chvátal a Cook našli v roku 1992 optimálnu cestu pre 3038 miest, na ktorú použili veľkú sieť z paralelne pracujúcich počítačov. V ďalších rokoch postupne zdokonaľovali objavené techniky až v roku 1998 našli optimálnu cestu medzi 13509 mestami v USA, v roku 2004 optimálnu cestu medzi 24978 mestami vo Švédsku a nakoniec v roku 2006 cestu medzi 85900 bodov. Pri riešení týchto úloh používali softvér Concorde, ktorý je k dispozícii na internete.

Problém obchodného cestujúceho v teórii grafov

V terminológii teórie grafov jednotlivé mestá predstavujú vrcholy, prepojenia medzi mestami sú hrany. Ide o hranovo ohodnotený súvislý graf G=(V, H), v ktorom hľadáme hamiltonovskú kružnicu, ktorá má minimálny súčet ohodnotení hrán.

Základné definície a pojmy:
Hamiltonovská kružnica je taký podgraf, ktorý je kružnica a obsahuje všetky vrcholy pôvodného grafu.

Graf G, ktorý má aspoň jednu hamiltonovskú kružnicu, nazývame hamiltonovským grafom.

Nech pre ľubovoľné dva nesusedné vrcholy u, v grafu G=(V, H), |V| = n, n ≥ 3, platí: \delta(u)+\delta(v)\ge n, potom G je hamiltonovský graf.

Nech G=(V, H), |V| = n, n ≥ 3. Nech pre každé celé číslo j, 1 \le j \le \frac {n}{2}, počet vrcholov stupňa najviac j je menší než j, potom graf G obsahuje hamiltonovskú kružnicu.

Pre kompletný graf Kₙ, kde n ≥ 3, počet všetkých rôznych hamiltonovských kružníc vieme určiť podľa nasledujúceho vzťahu: \frac {1}{2} (n-1)!

Využitie

Problém obchodného cestujúceho má množstvo praktických aplikácií. Využíva sa pri plánovaní dopravy, v prevádzkach, pri umiestňovaní zariadení, plánovaní výroby a riadení dodávateľského reťazca. Napríklad, môže pomôcť znížiť výrobné náklady, ak sa stanoví najefektívnejší model pre dierovanie otvorov do dosky plošných spojov alebo iných predmetov. Otvory, ktoré je potrebné vyvŕtať predstavujú počet miest a čas potrebný k posunu vŕtacej hlavy od jednej diery k nasledujúcej predstavuje cestovné náklady.

Záver

Hoci je problém obchodného cestujúceho známy už pomerne dlho, ešte stále nebol nájdený efektívny algoritmus. Dokonca väčšina odborníkov sa domnieva, že ho nebude možné nikdy riešiť polynomiálnymi algoritmami kvôli jeho zložitosti.