Masalah klasik yang dikenal sebagai Traveling Salesman Problem (TSP) menjadi pokok bahasan menantang yang dikaji secara intensif selama beberapa dasawarsa terakhir di bidang operational research, logistik dan sistem rantai pasok (supply chain systems), transportasi maupun theoretical computer science.
Sejarah TSP bisa ditelusur dari Euler yang mempelajari Knight Tour’s Problem (1759), Kirkman yang mempelajari grafik polihedron (1856) maupun Hamilton yang membuat game Icosian (1856) yang bertujuan mencari jalur sirkuit berbasis grafik polihedron yang memenuhi kondisi tertentu [2]. Istilah TSP sendiri diperkirakan berasal dari buku yang diterbitkan oleh seorang veteran salesman sekitar tahun 1930an di Jerman, meski dalam buku ini masalah TSP lebih dibahas dari aspek bisnis dan belum diformulasikan secara matematis.
