Indonesia merupakan negara kepulauan yang memiliki pulau – pulau kecil yang tersebar dari Sabang hingga Merauke. Hal ini menjadi tantangan untuk meningkatkan konektivitas antar pulau nya, terutama di beberapa wilayah terpencil dan masih tertinggal. Beberapa wilayah ini sangat membutuhkan akses transportasi yang layak khususnya transportasi laut untuk menopang perekonomiannya. Maka dari itu, pelayaran perintis yang merupakan jasa pelayaran yang didanai oleh APBN dalam rangka membantu daerah – daerah yang membutuhkan askes transportasi laut, pelayaran ini juga bertujuan untuk mendukung perkembangan perekonomian di beberapa daerah terpencil Indonesia. Rute pelayaran saat ini masih belum efektif, terutama rute pelayaran perintis di Pelabuhan Bitung, Kepulauan Sulawesi Utara ditunjukkan dengan waktu pelayaran keliling selama 22 hari. Dengan waktu selama itu, intensitas kapal untuk mengunjungi setiap daerah menjadi lebih sedikit. Pada penelitian ini, beberapa faktor yang mempengaruhi konektivitas antar pulau akan dioptimasi, dengan cara mengurangi jarak tempuh pelayaran untuk mengurangi pengeluaran anggaran APBN, dan mengurangi waktu pelayaran keliling yang bertujuan untuk meningkatkan intensitas kunjungan ke setiap daerah terpencil. Proses optimasi untuk mendukung kedua hal itu dilakukan dengan metode DBSCAN (Density Based Spatial Clustering of Application with Noise) dan TSP (Traveling Salesman Problem). Hasil akhir dari penelitian ini adalah berupa rekomendasi rute baru untuk Pelabuhan Bitung (R-35 dan R-36).