Indonesia sebagai negara kepulauan, memerlukan sistem transportasi yang efisien sebagai penghubung antar wilayah. Kapal sebagai alat transportasi laut menjadi sarana utama dalam mengatasi tantangan mobilitas di Indonesia, khususnya proses pendistribusian barang dalam jumlah besar. Akan tetapi, belum meratanya pengembangan ekonomi dan infrastruktur di wilayah Indonesia bagian timur mengakibatkan terjadinya kesenjangan antar wilayah dan disparitas harga karena tingginya biaya operasional dalam proses pendistribusian barang. Berdasarkan kondisi tersebut, pemerintah mengambil langkah dalam mengoptimalkan peluang ekonomi melalui program tol laut. Tol laut direalisasikan sebagai trayek yang efektif dan efisien sehingga jalur paling ideal dibutuhkan dalam proses pendistribusian barang ke setiap wilayah di Indonesia. Optimasi rute pelayaran pada trayek tol laut perlu dilakukan sebagai langkah krusial untuk menghasilkan jalur paling ideal yang lebih efektif dalam mengurangi biaya operasional dan keterlambatan pendistribusian barang. Penelitian ini mengimplementasikan travelling salesman problem dengan algoritma simulated annealing sebagai metode optimasi pemilihan rute pelayaran. Metode tersebut menghasilkan pemilihan rute yang optimal dengan fungsi objektif jarak tempuh minimum. Penelitian ini bertujuan untuk menguji apakah trayek tol laut 2023 yang telah dijalankan oleh pemerintah merupakan jalur terbaik berdasarkan jarak terpendek. Hasil penelitian menunjukan bahwa terdapat 12 rute baru yang memiliki jarak lebih dekat dibandingkan dengan rute pada trayek tol laut yang telah dijalankan oleh pemerintah. Penelitian juga menghasilkan estimasi biaya bahan bakar yang menurun pada 12 rute tersebut. Berkurangnya biaya bahan bakar ini dapat mengurangi tingginya biaya operasional dalam proses pendistribusian barang. Hasil ini dapat menjadi masukan bagi pemerintah Indonesia, khususnya Kementerian Perhubungan sebagai bahan evaluasi dalam Keputusan Direktur Jenderal Perhubungan Laut Nomor: KP-DJPL 678 Tahun 2023.

---

Indonesia, as an archipelagic country, requires an efficient transportation system to connect its regions. Ships, as the primary means of sea transportation, are essential for overcoming mobility challenges in Indonesia, particularly in the distribution of goods in large quantities. However, the uneven economic and infrastructure development in eastern Indonesia has resulted in regional disparities and price differences due to high operational costs in the distribution process. In response to these conditions, the government has taken steps to optimize economic opportunities through the tol laut program. The tol laut program is designed to be a cost-effective and efficient shipping route network, thus necessitating the most ideal routes for the distribution of goods to every region in Indonesia. Optimizing the shipping routes of the Tol Laut is crucial for creating the most ideal routes that are more effective in reducing operational costs and delays in goods distribution. This research implements the travelling salesman problem using the simulated annealing algorithm as a method for optimizing the selection of shipping routes. This approach identifies the most efficient routes to minimize travel distances. This study aims to test whether the tol laut 2023 routes implemented by the government are the best routes based on the shortest distance. The results of the study indicate that there are 12 new routes with shorter distances compared to the routes of the sea toll previously implemented by the government. The research also estimates a decrease in fuel costs for these 12 routes. This reduction in fuel costs can lower the high operational costs in the goods distribution process. These findings can provide input for the Indonesian government, particularly the Ministry of Transportation, as evaluation material in the Decision of the Director General of Sea Transportation Number: KP-DJPL 678 of 2023.