Traveling Salesman Problem (sering disebut TSP) adalah masalah algoritmik klasik dalam bidang ilmu komputer dan riset operasi. Ini difokuskan pada optimasi. Dalam konteks ini, solusi yang lebih baik sering kali berarti solusi yang lebih murah, lebih singkat, atau lebih cepat. TSP adalah masalah matematika. Hal ini paling mudah diekspresikan sebagai grafik yang menggambarkan lokasi dari sekumpulan node.

Travelling salesman problem didefinisikan pada tahun 1800-an oleh matematikawan Irlandia W. R. Hamilton dan oleh matematikawan Inggris Thomas Kirkman. Hamilton's Icosian Game adalah teka-teki rekreasi yang didasarkan pada menemukan siklus Hamiltonian. Bentuk umum TSP tampaknya pertama kali dipelajari oleh para matematikawan selama tahun 1930-an di Wina dan di Harvard, terutama oleh Karl Menger. Menger mendefinisikan masalahnya, mempertimbangkan algoritma brute-force yang jelas, dan mengamati ketidakoptimalan heuristik tetangga terdekat:

Kita nyatakan dengan masalah pengirim pesan (karena dalam prakteknya masalah ini harus dipecahkan oleh setiap tukang pos, bagaimanapun juga oleh banyak pelancong) tugas untuk menemukan, untuk finitely banyak titik yang jarak berpasangannya diketahui, rute terpendek yang menghubungkan titik-titik tersebut. Tentu saja, masalah ini dapat diselesaikan dengan banyak percobaan yang berhingga banyaknya. Aturan-aturan yang akan mendorong jumlah percobaan di bawah jumlah permutasi dari titik-titik yang diberikan, tidak diketahui. Aturan yang pertama-tama harus dilakukan dari titik awal ke titik terdekat, kemudian ke titik yang paling dekat dengan titik ini, dst., secara umum tidak menghasilkan rute terpendek.

Hassler Whitney di Princeton University memperkenalkan nama traveling salesman problem segera setelahnya.