Traveling Salesman Problem (TSP) adalah masalah optimasi kombinatorial klasik dan memiliki peran dalam perencanaan, penjadwalan, dan pencarian pada bidang rekayasa dan pengetahuan (Dong, 2012). TSP juga merupakan objek yang baik untuk menguji kinerja metode optimasi, beberapa metode seperti Cooperative Genetic Ant System (CGAS) (Dong, 2012), Parallelized Genetic Ant Colony System (PGAS) Particle Swarm Optimization and Ant Colony Optimization Algorithms (PSO–ACO) (Elloumi, 2014), dan Ant Colony Hyper-Heuristics (ACO HH) (Aziz, 2015) telah dikembangkan untuk memecahkan TSP. Sehingga, pada penelitian ini diimplementasikan kombinasi metode baru untuk meningkatkan akurasi penyelesaian TSP. Firefly Algorithm (FA) merupakan salah satu algoritma yang dapat digunakan untuk memecahkan masalah optimasi kombinatorial (Layeb, 2014). FA merupakan algoritma yang berpotensi kuat dalam memecahkan kasus optimasi dibanding algoritma yang ada termasuk Particle Swarm Optimization (Yang, 2010). Namun, FA memiliki kekurangan dalam memecahkan masalah optimasi dengan skala besar (Baykasoğlu dan Ozsoy, 2014). Tabu Search (TS) merupakan metode optimasi yang terbukti efektif untuk memecahkan masalah optimasi dengan skala besar (Pedro, 2013). Pada penelitian ini, TS akan diterapkan pada FA (FATS) untuk memecahkan kasus TSP. Hasil FATS akan dibandingkan terhadap penelitian sebelumnya yaitu ACOHH. Perbandingan hasil menunjukan peningkatan akurasi sebesar 0.89% pada dataset Oliver30, 0.14% dataset Eil51, 3.81% dataset Eil76 dan 1.27% dataset KroA100.