Pasar di era industri 5.0 tidak lagi terhalang oleh jarak. Transportasi dalam dunia industri memiliki peran yang krusial karena dalam pengantaran barang dari lokasi ke lokasi lain terdapat biaya yang harus dikeluarkan. CV XYZ merupakan sebuah perusahaan yang bergerak di bidang distribusi peralatan air yang berlokasi di Kota Bandung. CV XYZ memiliki satu gudang dan dua toko yang melayani pengiriman pada 71 titik pelanggan yang tersebar di Provinsi Jawa Barat. Namun dalam prosesnya terdapat permasalahan pada kapasitas kendaraan yang tidak diutilisasi secara maksimal serta belum adanya rute pengiriman baku sehingga menyebabkan kebutuhan biaya pengiriman yang melebihi batas anggaran perusahaan. Tujuan penelitian ini adalah perancangan rute pengiriman untuk mendistribusikan produk dengan karakteristik permasalahan multi-depot heterogeneous-fleet vehicle-routing problem (MDHFVRP) dengan algoritma variable neighboorhood search menggunakan model mixed-integer linear programming untuk meminimasi biaya transportasi dengan memaksimalkan utilisasi kapasitas kendaraan. Pada biaya transportasi hasil perhitungan terdapat penghematan biaya hingga 40,05%. Muatan kendaraan dari hasil perhitungan terdapat kenaikan rata-rata muatan dari yang semula berada pada rentang 32,6-55,9% menjadi 87,4-99,9% kapasitas. Dari hasil perhitungan penelitian ini menunjukkan usulan rute yang dihasilkan dapat meminimasi biaya transportasi dengan mempertimbangkan utilisasi kapasitas kendaraan yang dimaksimalkan.
Kata Kunci: Vehicle Routing Problem, Multi Depot, Heterogeneous Fleet, Mixed-integer Linear Programming.