Indonesia sebagai negara kepulauan memiliki lebih dari 17 ribu pulau. Hal ini menyebabkan adanya tantangan tersendri untuk mewujudkan konektivitas antar pulaunya, terutama pada daerah terpencil dan tertinggal. Pelayaran perintis merupakan pelayaran yang disubsidi oleh pemerintah Indonesia dengan tujuan utama meningkatkan perekonomian di daerah terpencil dan tertinggal. Namun saat ini, kinerja pelayaran perintis masih belum optimal untuk mencapai tujuan tersebut. Hal tersebut ditandai dengan lamanya round voyage suatu trayek yang dapat mencapai 14 hari serta rendahnya capaian target voyage pelayaran perintis. Oleh karena itu, perlu adanya evaluasi serta efisiensi rute pelayaran perintis. Salah satu yang dapat dilakukan untuk meningkatkan efisiensi rute pelayaran perintis adalah dengan melakukan re-routing trayek pelayaran perintis. Penelitian ini melakukan re-routing pelayaran perintis di wilayah NTT-Maluku Barat Daya dengan pertama melakukan clustering menggunakan DBSCAN (Density-Based Spatial Clustering of Applications with Noise) serta optimasi dengan pendekatan TSP (Travelling Salesman Problem). Hasil yang didapatkan adalah terdapat pengurangan dari rata-rata jarak tempuh trayek pelayaran perintis sebesar 55% (dari 1276 NM menjadi 569,3 NM) serta pengurangan angka rata-rata lama round voyage trayek sebesar 74% (dari 13,3 hari menjadi 3,5 hari). Selain itu, terjadi penurunan ketimpangan antar trayeknya yang dilihat dari nilai jangkauan (range) dari jumlah pelabuhan, jarak tempuh, serta lama round voyage pada trayek pelayaran perintis di wilayah NTT-Maluku Barat Daya.

---

Indonesia, as an archipelagic country, has more than 17,000 islands. This causes challenges in realizing inter-island connectivity, especially in remote and underdeveloped areas. Pelayaran Perintis is a shipping program that the Indonesian government subsidizes to improve the economy in remote and underdeveloped areas. However, the performance of Pelayaran Perintis is still not optimal for achieving this goal. This is indicated by the length of the round voyage of a route that can reach 14 days and the low achievement of the Pelayaran Perintis voyage target. Therefore, there is a need for evaluation and efficiency of Pelayaran Perintis routes. One thing that can be done to increase the efficiency of Pelayaran Perintis routes is by re-routing Pelayaran Perintis routes. This study re-routes Pelayaran Perintis in the NTT-Maluku Southwest region by first clustering using DBSCAN (Density-Based Spatial Clustering of Applications with Noise) and optimization with the TSP (Travelling Salesman Problem) approach. The results obtained are a reduction in the average mileage for Pelayaran Perintis routes by 55% (from 1276 NM to 569.3 NM) and a reduction in the average length of round voyage routes by 74% (from 13.3 days to 3, 5 days). In addition, there has been a decrease in inequality between routes, which can be seen from the range value of the number of ports, distance traveled, and round voyage length on Pelayaran Perintis routes in the NTT-Southwest Maluku region.