Banyaknya pulau di Indonesia menyebabkan adanya tantangan untuk menjaga konektivitas antar pulaunya, mendorong untuk dibutuhkannya moda transportasi agar meningkatkan konektivitas antar pulau khususnya di wilayah 3T. Di masa ini pelayaran perintis menjadi moda transportasi yang ditugaskan oleh pemerintah guna melayani daerah 3T. Namun, pada penerapannya pelayaran perintis masih dinilai kurang optimal sehingga perlu dilakukannya optimasi. Optimasi merupakan aktifitas yang bertujuan untuk mendapatkan nilai maksimal atau minimal berdasarkan fungsi dan tujuan yang ingin dicapai, dengan tetap memenuhi fungsi kendala yang berlaku. Optimasi dinilai penting untuk keberlanjutan akses transportasi laut khususnya pelayaran perintis di Sulawesi Selatan-Nusa Tenggara. Seluruh Pelabuhan yang dilayani trayek pelayaran perintis diklasterkan menggunakan metode Density Based Spatial Clustering of Applications with Noise (DBSCAN). Penelitian ini ditujukan untuk memberikan rekomendasi untuk optimasi rute pelayaran perintis. Terdapat 3 klaster yang terbentuk untuk menyesuaikan ketersediaan kapal perintis yang berjumlah 3 kapal. Masing-masing klaster dilakukan optimasi menggunakan Travelling Salesman Problem (TSP). Hasil optimasi didapatkan lebih optimal dengan total jarak tempuh rata-rata di ketiga klaster yang terbentuk sebesar 630 NM dibandingkan dengan rute eksisting sebesar 1211 NM dengan penurunan sebesar 48%

---

The large number of islands in Indonesia poses a challenge to maintain connectivity between islands, encouraging the need for modes of transportation to increase inter-island connectivity, especially in the 3T region. At this time perintis shipping became a mode of transportation assigned by the government to serve the 3T areas. However, in its implementation, perintis shipping is still considered less than optimal, so optimization is needed. Optimization is an activity that aims to get the maximum or minimum value based on the function and goals to be achieved, while still meeting the applicable constraints. Optimization is considered important for the sustainability of access to sea transportation, especially perintis shipping in South Sulawesi-Nusa Tenggara. All ports served by perintis shipping routes are clustered using the Density Based Spatial Clustering of Applications with Noise (DBSCAN) method. This research is intended to provide recommendations for optimizing perintis shipping routes. There are 3 clusters formed to adjust the availability of perintis ships, which total 3 ships. Each cluster is optimized using the Traveling Salesman Problem (TSP). Optimization results obtained are more optimal with the total average mileage in the three clusters formed of 630 NM compared to the existing route of 1211 NM with a decrease of 48%.