Az utazó ügynök problémája egy kombinatorikus optimalizálási probléma. Kiváló példa a bonyolultság-elmélet által NP-nehéznek nevezett problémaosztályra. Az utazó ügynök problémájához kapcsolódó matematikai feladatokkal először Sir William Rowan Hamilton és Thomas Penyngton Kirkman foglalkoztak az 1800-as években. Hamilton és Kirkman ezen korai munkájáról szóló értekezés megtalálható a Graph Theory 1736-1936. című munkában. Az utazóügynök-probléma általános változatát először az 1930-as években vizsgálták Bécsben, illetve a Harvardon, kiváltképp Karl Menger. A problémával később Hassler Whitney és Merrill M. Flood is komolyan foglalkozott a Princetoni Egyetemen. Az utazóügynök-probléma fejlődéséről, valamint Menger és Whitney kapcsolatáról részletes információk találhatók Alexander Schrijver publikációjában.

A probléma

Adva van n város, illetve az útiköltség bármely két város között, keressük a legolcsóbb utat egy adott városból indulva, amely minden várost pontosan egyszer érint, majd a kiindulási városba ér vissza.

 út közül kell választanunk, ez ugyanis a Hamilton-körök száma az n pontú teljes gráfban.
Megjegyzés: Ez a képlet csak  esetén működik.

Kapcsolódó problémák
 Ekvivalens gráfelméleti megfogalmazása a problémának: Adott teljes élsúlyozott gráf esetén keressük a legkisebb összsúllyal rendelkező Hamilton-kört. Megmutatható, hogy a kiindulási városba való visszatérés megkövetelése nem nehezít a probléma számítási nehézségén, tehát minimális súlyú Hamilton-út keresése egy adott pontból is NP-teljes.
 A probléma egy másik változata, amikor nem a legkisebb súlyú Hamilton-kört keressük, hanem azt, amelyikben a „legnehezebb” él súlya a lehető legkisebb. A logisztikai problémákon túl nagy gyakorlati jelentőséggel bír például a nyomtatott áramkörök gyártása során fúrórobotok ideális mozgásának megtervezésében.
 Az utazóügynök-probléma általánosított változatában „országok” szerepelnek egy vagy több „várossal”, az ügynök minden országból pontosan egy várost köteles meglátogatni, majd visszatérni kiindulási helyére. Behzad és Modarres megmutatta, hogy az általánosított utazóügynök-probléma visszavezethető egy standard utazóügynök-problémára azonos mennyiségű várossal, más súlyozással.

Számítási nehézség
A legkézenfekvőbb megoldás az összes permutáció végignézése, és a legkisebb súlyú kiválasztása lenne, de tekintve, hogy ez n! darab permutációt jelent (ahol n a városok száma), nagyobb n-ekre ez a megoldás kivitelezhetetlen. Dinamikus programozási technikák segítségével a probléma megoldásának lépésszáma felülről becsülhető -nel. Ez még exponenciális függvénye n-nek, de sokkal jobb, mint az  lépést használó brute force („nyers erő”) módszer.

A probléma bizonyítottan NP-nehéz, annak eldöntése pedig, hogy adott x-re létezik-e x-nél olcsóbb megoldása a konkrét esetnek NP-teljes. A probléma különböző megszorító feltételek mellett is NP-nehéz marad: kiköthetjük, hogy a városok egy euklideszi síkon helyezkedjenek el a szokásos távolságfogalommal. Akkor sem egyszerűsödik a helyzet, ha elhagyjuk azt a feltételt, hogy az ügynök minden várost csak egyszer látogathat meg, hiszen könnyen látható, hogy euklideszi síkon amúgy is ez az optimális megoldás (a háromszög-egyenlőtlenség miatt).

Algoritmusok
Mivel tehát hatékony megoldás nem ismert a probléma megoldására sok város mellett, a következő célú algoritmusok a gyakoriak:
 A legjobb megoldást megkereső algoritmus, mely csak kisebb mennyiségű pontszám mellett hatékony.
 „Szuboptimális” vagy heurisztikus algoritmusok, melyek nagy valószínűséggel az optimális megoldáshoz jól közelítő megoldást adnak.
 A probléma speciális eseteivel foglalkozó, azt valamilyen megszorítás mellett hatékonyan megoldó algoritmusok.

Teljes megoldású algoritmus
Az idő múlásával az egyre finomodó technikáknak, és a számítástechnika fejlődésének köszönhetően egyre nagyobb mennyiségű városra sikerült megoldani a problémát (forrás: Georgia Tech):
 1954: 49 amerikai város - G. B. Dantzig, D. R. Fulkerson és S. Johnson.
 1977: 120 város Németország környékéről - M. Grötschel.
 1987: 2392 pont - M. W. Padberg és G. Rinaldi.
 2004: Svédország  városa - D. Applegate, R. Bixby, V. Chvátal, W. Cook és K. Helsgaun.
 2006: egy  pontú probléma megoldása a CONCORDE algoritmus segítségével - D. Applegate, R. Bixby, V. Chvátal, W. Cook, D. Espinoza, M. Goycoolea és K. Helsgaun.

Jegyzetek

Hivatkozások
 A probléma a Mathworld honlapján.
 Encyclopedia of Mathematics
 TSPLIB: Algoritmusok tesztelésére szolgáló mintabemenetek.
 A Georgia Tech  gyűjteménye a témáról.
 Alice és Bob - 6. rész: Alice és Bob a kiszámíthatóság határán
 Alice és Bob - 7. rész: Alice és Bob egymillió dolláros kérdése
 Alice és Bob - 8. rész: Alice és Bob biztonsága

Kapcsolódó szócikkek 
 Kínaipostás-probléma

Gráfelmélet
Számítási problémák a gráfelméletben
Gráfalgoritmusok
Hamilton-utak és -körök
Idegen nyelvű térképet tartalmazó szócikkek