Indonesia merupakan salah satu negara maritim terbesar di dunia,untuk menjamin pergerakan barang dan penumpang terus berjalan pemerintah membuat kapal perintis sebagai kapal subsidi untuk pemerataan.wilayah yang menjadi perhatian adalah Regional Indonesia Timur,namun untuk diciptakan biaya operasional yang optimal agar cost dan tujuan bisa tepat sasaran perlu dilakukan optimasi,salah satu hal yang berperan dari terciptanya biaya operasional lebih rendah adalah pemilihan rute dikarenakan  cost lebih banyak dihabiskan pada bahan bakar.dalam pengoptimalan rute yang bersifat travelling salesman problem dapat digunakan penyelesaian berdasarkan metode heuristik,dua metode heuristik yang yang dapat menjadi pilihan adalah Algoritma genetika dan Tabu search dengan membangun pengoptimalan dalam kedua metode tersebut didapatkan kesimpulan keduanya bisa menjadi solusi dan perbedaan hasil kedua metode tidak berbeda jauh,keduanya  menciptakan berbagai rute dalam permasalahan harga bahan bakar optimal yang dapat dijadikan solusi pemilihan rute yang baru.

---

Indonesia is one of the largest maritime countries in the world, To ensure the movement of commodity and passengers continues, the government makes pioneer ships as subsidized ships for equity. The area of concern Eastern Indonesia Region, but in order to create optimal operational costs so that costs and goals can be right on target, optimization needs to be done. One of the things that plays a role in creating lower operational costs is route selection because more costs are spent on fuel.When optimizing routes that are traveling salesman problems, solutions based on heuristic methods can be used, Two heuristic methods that can be chosen are genetic algorithms and taboo search by building optimization in the two methods, it can be concluded that both of them can be a solution and the difference in the results of the two methods is not much different, both create various routes in the optimal fuel price problem which can be used as a new route selection solution.