PT Atlantic Ocean Paint merupakan perusahaan yang bergerak di bidang cat. Perusahaan ini membutuhkan banyak salesman untuk memperlancar proses distribusi produknya. Tugas dari salesman tersebut yaitu untuk mengontrol stok produk dan pembayaran dari masing-masing toko. Salesman tersebut harus mengunjungi masing-masing toko satu kali dalam satu minggu. Penelitian ini membahas bagaimana cara salesman tersebut dalam menentukan rute perjalananya sehingga didapatkan rute terbaik. Tujuan yang ingin diperoleh dari penelitian ini adalah : (1) Mampu menemukan rute terbaik seorang salesman dalam mengunjungi toko di wilayah Sampang dengan menggunakan algoritma Tabu Search; dan (2) Menentukan jarak yang optimal seorang salesman di wilayah Sampang. Tabu Search merupakan algoritma yang dikembangkan dari local search. Tabu Search melakukan pencarian pada lingkungan dari solusi berikutnya, meskipun solusi tersebut tidak lebih baik dari solusi sebelumnya. Tabu Search dimulai dengan cara yang sama seperti neighbourhood search (lokal) biasa dengan cara kerja secara iterasi dari suatu titik (solusi) ke solusi lain hingga kriteria terminasi yang telah dipilih dipenuhi.

• TRAVELLING SALESMAN PROBLEM MENGGUNAKAN ALGORITMA DIJKSTRA (Studi Kasus J&T Rungkut, Surabaya)