Di era global ini, pembangunan infrastruktur berperan penting dalam pertumbuhan ekonomi. Dalam pembangunan infrastruktur, material berperan sebagai elemen penting yang menghabiskan biaya konstruksi paling besar. Pada proses distribusi material ke konsumen, produsen sering menghadapi tantangan untuk dapat mendistribusikan produk mereka menuju konsumen dengan tepat waktu dan efisien. Proses distribusi tersebut harus dilakukan secara efektif agar tidak menghambat jadwal pekerjaan di proyek. Strategi efisiensi dalam menyelesaikan permasalahan distribusi ini dikenal dengan istilah Vehicle Routing Problem (VRP). Penelitian ini bertujuan untuk mengoptimalkan rute distribusi dan mencari total biaya distribusi paling minimal yang dapat dilakukan dengan menggunakan studi kasus salah satu distributor material penutup lantai di Surabaya. Optimasi pada penelitian ini menggunakan metode metaheuristik dengan algoritma Symbiotic Organisms Search (SOS), dengan 3 jenis model VRP sebagai fungsi objektif optimasi yaitu Split Delivery Vehicle Routing Problem (SDVRP), SDVRP with Time Windows (SDVRPTW), dan SDVRP with Flexible Time Windows (SDVRPFlexTW). Hasil optimasi menunjukan adanya penghematan sebesar 33,59% untuk SDVRP, 18,33% untuk SDVRPTW, dan 25,31% untuk SDVRPFlexTW terhadap biaya rute eksisting. Model SDVRPFlexTW merupakan model yang paling realistis dan efisien karena memperhatikan jendela waktu dan memiliki fleksibilitas untuk mengurangi total biaya distribusi dengan melakukan pengiriman lebih awal atau lebih akhir dengan mengorbankan kepuasan konsumen.