PT XYZ merupakan dealer dari salah satu perusahaan besar yang bergerak dalam bidang otomotif. Perusahaan memiliki tiga core business yaitu sales, after sales, dan penyediaan spare parts. Salah satu core business PT XYZ yaitu penyediaan spare parts, dimana dalam sisi logistik didukung oleh regional part depo atau Distribution Center. Regional part depo Permasalahan yang terjadi pada PT XYZ adalah perusahaan ini tidak dapat mendistribusikan produknya pada beberapa konsumen dikarenakan keterlambatan pengiriman yang dikarenakan penentuan rute yang kurang optimal, hanya didasarkan pada intuisi driver.
Penelitian ini membahas VRP dasar dengan karakterisktik capacitated, time window, multiple products and compartments dengan tujuan meminimalkan total biaya transportasi. VRP masuk ke dalam permasalahan hard-combinatorial dengan karakteristik NP-hard sehingga umumnya VRP dipecahkan dengan metode metaheuristik seperti algoritma Harmony Search yang digunakan juga pada penelitian ini. Algoritma ini dimulai dengan pembangkitan populasi awal dengan menggunakan algoritma nearest neighbour yang kemudian dioptimalisasi menggunakan algoritma Harmony Search.
Hasil dari algoritma ini dapat mengoptimalkan jarak tempuh, jumlah kunjungan, dan meminimalkan biaya total transportasi. Dari hasil penelitian pengukuran satu hari yang terdiri dari lima rute keberangkatan terjadi penurunan biaya sebesar 15% atau sebesar Rp103,415.00.
Kata Kunci : Transportasi, Perancangan Rute Kendaraan, Algoritma Harmony Search, Algoritma nearest neighbour, Time window, Multiple Product and Compartment.