Penelitian ini bertujuan mengembangkan varian modelVRP untuk menyusun rute angkutan umum penumpang. Sebagai bahan pertimbangan adalah karakteristik rutenya tertutup yang berawal dan berakhir pada terminal atau pangkalan yang sama, karakteristik pelanggannya deterministik dengan volume permintaan layanan tetap dan dalam kurun waktu saturound trip tertentu, serta karakteristik kendaraan yang dioperasikan memiliki variasi kapasitas dan biaya operasi. Rute disusun untuk memperoleh efisiensi biaya operasional yang optimal, setiap jalur yang ada dalam jaringan pelayanan dilewati tepat satu kali dengan alasan pemberian frekuensi layanan yang sama untuk setiaplink pergerakan penumpang. Penyusunan rute dilakukan melalui dua tahap, yaitu tahap inisialisasi dengan pendekatan metoda Nearest Addition atau Nearest Neighborhood Heuristic dan tahap perbaikan dengan pendekatan metoda Genetic Algorithm. Model ini belum mempertimbangkan adanya pola rute dengan naik-turun penumpang yang dinamis, serta kecepatan dan waktu tempuh kendaraan yang bersifat stokastik, permintaan pergerakan penumpang setiap jalur yang bersifat stokastik, ataupun jumlah pelabuhan dalam jaringan pelayanan yang bersifat stokastik. Sehingga membuka peluang penelitian lebih lanjut. Hasil penelitian menunjukkan bahwa dengan penyusunan ulang rute pelayanan kapal-kapal milik PELNI, total biaya operasional seluruh kapal dapat ditekan jauh lebih efisien hingga mencapai 64,38% dari total biaya aktual. Sedangkan dari sisi total jarak tempuh, dapat ditekan lebih efektif hingga mencapai 59,64% dari total jarak tempuh aktual. Kata kunci: VRP, angkutan laut penumpang, efisiensi biaya, efektivitas jaringan