Considerăm o mulţime de noduri V={1, 2, …, n} şi o mulţime de arce A. Nodurile reprezintă oraşe iar arcele perechi de oraşe între care există o legătură directă. Pentru fiecare arc (i, j), c_ij este timpul călătoriei directe între cele două oraşe. Se pune problema găsirii unui tur care: să înceapă în oraşul 1, să se termine tot în oraşul 1, să treacă prin fiecare din celelalte oraşe o singură dată şi să fie realizat într-un timp total minim.

Pentru formularea problemei introducem variabilele x_ij care iau valoarea 1 dacă j urmează imediat după i în tur şi 0 altfel. Astfel, .

Aceste condiţii asigură nu numai realizarea unui tur ci şi formarea subtururilor care nu pot fi întregite la un tur. Pentru a evita formarea subtururilor este necesară introducerea unei condiţii suplimentare, dată pentru orice cu prin:

Folosind restricţiile specificate, problema comis voiajorului se poate exprima formal prin:

urmator