Problém obchodního cestujícího (Travelling salesman problem) je úloha kombinatorické optimalizace, jejíž cílem je nalézt v zadaném ohodnoceném úplném grafu kružnici takovou, že prochází všemi vrcholy a zároveň je její cena minimální. Jinými slovy se jedná o nalezení nejkratší Hamiltonovské kružnice v ohodnoceném grafu.

V dané zemi existuje mnoho měst, mezi všemi městy je postavené silnice. Cílem obchodního cestujícího je objet všechna města takovým způsobem, aby cena za jízdenky byla minimální (odpovídá vzdálenosti měst) a vrátit se do výchozího města.

Problém je NP-úplný a silně NP-obtížný, což znamená, že pokud platí, pak pro problém obchodního cestujícího neexistuje žádný polynomiální k-aproximační algoritmus – neexistuje polynomiální algoritmus, který by našel libovolné řešení, které je nejhůře k-násobkem optimálního řešení.

Variantou tohoto problému je problém metrického obchodního cestujícího, ve kterém vzdálenosti na grafu splňují trojúhelníkovou nerovnost. Toto zjednodušení odpovídá velkému množství reálných problémů (např. hledání na mapě), a zároveň umožňuje konstrukci aproximačních algoritmů.