Permasalahan Penjual Keliling
Sejarah

Asal-usul dari permasalahan penjual keliling tidak jelas. Sebuah buku panduan untuk penjual keliling dari tahun 1832 menyebutkan permasalahan dan termasuk contoh tur melalui Jerman dan Swiss, tetapi tidak mengandung penyelesaian matematis.
TSP secara matematis diformulasikan pada abad ke-19 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Kirkman. Permainan icosian Hamilton adalah teka-teki buatan yang didasarkan pada pencarian siklus Hamilton.  Bentuk umum TSP tampaknya pertama kali dipelajari oleh matematikawan pada tahun 1930-an di Wina dan di Harvard, khususnya oleh Karl Menger, yang mendefinisikan masalah tersebut, mempertimbangkan algoritma gaya kasar yang jelas, dan mengamati ketidakoptimalan heuristik dari tetangga terdekat.
Kita menyatakan dengan "masalah kurir" (karena dalam praktiknya, pertanyaan ini harus diselesaikan oleh setiap tukan pos, juga oleh banyaknya pelancong) tugas untuk menemukan, untuk banyak titik terhingga yang jarak berpasangannya diketahui, rute terpendek yang menghubungkan titik-titik tersebut. Tentu saja, masalah ini dapat dieselesaikan dengan banyak percobaan. Aturan yang akan mendorong jumlah percobaan di bawah jumlah permutasi dari poin yang diberikan tidak diketahui. Aturan bahwa seseorang harus berangkat dari titik awal ke titik terdekat, lalu ke titik terdekat dengan titik tersebut, dan seterusnya, secara umum tidak menghasilkan rute terpendek.
Masalah ini pertama kali dipertimbangkan secara matematis pada tahun 1930-an oleh Merrill M. Flood yang berupaya memecahkan masalah rute bus sekolah  Hassler Whitney di Universitas Princeton membangkitkan minat terhadap masalah tersebut, yang disebutnya sebagai "permasalahan 48 bagian". Publikasi paling awal yang menggunakan kata "travelling salesman problem" atau "permasalahan penjual keliling" pada tahun 1949 oleh Julia Robinson dalam RAND Corporation, "Pada permainan Hamiltonian (permasalahan penjual keliling)".
Pada tahun 1950-an dan 1960-an, masalah ini menjadi semakin populer di kalangan ilmiah di Eropa dan Amerika Serikat setelah RAND Corporation di Santa Monica menawarkan hadiah untuk langkah-langkah dalam memecahkan masalah tersebut  Kontribusi penting diberikan oleh George Dantzig, Delbert Ray Fulkerson, dan Selmer M. Johnson dari RAND Corporation, yang menyatakan masalah tersebut sebagai program linear integer dan mengembangkan metode bidang potong untuk solusinya. Mereka menulis apa yang dianggap sebagai makalah penting tentang subjek tersebut di mana, dengan metode-metode baru ini, mereka memecahkan contoh dengan 49 kota hingga optimal dengan membuat sebuah tur dan membuktikan bahwa tidak ada tur lain yang lebih pendek. Namun, Dantzig, Fulkerson, dan Johnson berspekulasi bahwa, dengan solusi yang mendekati optimal, seseorang mungkin dapat menemukan keoptimalan atau membuktikan keoptimalan dengan menambahkan sejumlah kecil pertidaksamaan tambahan (pemotongan). Mereka menggunakan ide ini untuk memecahkan masalah 49 kota awal mereka menggunakan model string. Mereka menemukan bahwa mereka hanya memerlukan 26 pemotongan untuk mencapai solusi bagi masalah 49 kota mereka. Meskipun makalah ini tidak memberikan pendekatan algoritmik untuk masalah TSP, ide-ide yang terkandung di dalamnya sangat diperlukan untuk kemudian menciptakan metode solusi eksak untuk TSP, meskipun akan memakan waktu 15 tahun untuk menemukan pendekatan algoritmik dalam menciptakan pemotongan ini. Selain metode bidang pemotongan, Dantzig, Fulkerson, dan Johnson menggunakan algoritma cabang dan batas mungkin untuk pertama kalinya.
William Rowan Hamilton, tahun 1850