Gambar Ilustrasi persoalan Travelling Salesman Problem

Travelling Salesman Problem (TSP) adalah salah satu permasalahan yang terkenal dalam teori graf dan optimasi kombinatorial. TSP melibatkan sebuah salesman yang harus mengunjungi sejumlah kota yang berbeda dengan jarak yang telah ditentukan, kemudian kembali ke kota asalnya dengan jarak perjalanan minimum.

Misalkan terdapat N kota yang ingin dikunjungi oleh salesman. Jika kita menganggap setiap kota sebagai simpul dalam sebuah graf lengkap, maka setiap pasangan simpul memiliki jarak yang terkait dengannya. Dalam TSP, tujuan adalah menemukan jalur perjalanan terpendek yang melewati semua kota sekali dan kembali ke kota asal.

Secara formal, dapat dinyatakan sebagai berikut: Diberikan sebuah graf berbobot lengkap G dengan simpul-simpul V dan bobot antar simpul w(u,v), dimana u dan v adalah simpul-simpul yang berbeda. Temukan tur sirkuit hamilton minimal pada G, yaitu tur yang melalui setiap simpul tepat satu kali dan kembali ke simpul awal dengan total bobot yang minimum.

TSP termasuk dalam kelas masalah NP-hard, yang berarti bahwa tidak diketahui adanya algoritma efisien yang dapat mencari solusi optimal untuk semua masukan dalam waktu yang terbatas. Oleh karena itu, dalam praktiknya, digunakan berbagai teknik untuk mendekati solusi yang optimal secara efisien.

Berikut ini adalah beberapa pendekatan umum dalam menyelesaikan TSP:

1. Brute Force: Metode ini melibatkan pengujian semua kemungkinan permutasi jalur yang mungkin dan menghitung total jarak untuk setiap jalur. Namun, pendekatan ini tidak efisien karena kompleksitasnya adalah O(N!), yang sangat besar saat N menjadi besar.
2. Dynamic Programming: Metode ini mengandalkan pemrograman dinamis untuk memecahkan TSP. Ide dasarnya adalah untuk memodelkan masalah menjadi submasalah yang lebih kecil dan menyimpan solusi optimal dari submasalah tersebut dalam tabel. Solusi akhir ditemukan dengan membangun solusi optimal secara bertahap dari submasalah yang lebih kecil.
3. Algoritma Genetika: Pendekatan ini terinspirasi oleh evolusi alami. Solusi disimbolkan sebagai individu dalam populasi, dan operasi seperti seleksi, reproduksi, mutasi, dan crossover digunakan untuk menghasilkan generasi berikutnya. Proses ini dilakukan untuk beberapa generasi dengan harapan menemukan solusi yang semakin baik.
4. Algoritma Heuristik: Pendekatan ini menggunakan heuristik atau aturan praktis untuk mencari solusi yang memadai secara cepat. Contoh dari algoritma ini adalah Nearest Neighbor, yang memilih simpul terdekat yang belum dikunjungi sebagai langkah selanjutnya.

Penting untuk dicatat bahwa meskipun masih ada ruang untuk perbaikan, TSP tetap menjadi salah satu permasalahan klasik yang menarik dan relevan dalam bidang pengoptimalan dan komputasi. Berbagai inovasi dan teknik baru terus dikembangkan untuk mendekati solusi yang lebih baik dan efisien.