PT. XYZ merupakan distributor dari suatu perusahaan besar yang bergerak di sub sektor industri makanan dan minuman. Berdasarkan data PT. XYZ selama bulan Juli-Desember 2016, terjadi permasalahan dimana tidak semua demand dapat terpenuhi tepat pada waktunya. Target pemnuhan dari pihak perushaan sebesar 7%, tetapi hanya pada bulan Juli saja yang melebihi target. Permasalahan ini disebabkan oleh beberapa penyebab dimana yang paling berpengaruh merupakan keterlambatan armada tiba pada customer. Penyebab ini terjadi karena waktu tempuh yang lama karena penentuan rute yang tidak tepat. Permasalahan ini merupakan permasalahan umum yang sering terjadi pada bidang transportasi dimana armada yang digunakan lebih dari 1, maka permasalahan ini perlu diselesaikan dengan pendekatan Vechicle Routing Problem (VRP). Karakteristik VRP pada peneilitian ini adalah time windows. Untuk penyelesaian yang digunakan dengan pendekatan metaheuristik yaitu Alogaritma Tabu Search. Penulis menggunakan Alogaritma Nearest Neighbour sebagai pembangkit solusi awal yang selanjutnya digunakan pada Alogaritma Tabu Search. Pendekatan VRP dengan pendekatan Alogaritma Tabu Search dapat mengurangi total waktu tempuh sebesar 12.3% dari kondisi awal serta seluruh demand terpenuhi tanpa mengalami keterlambatan.
Kata kunci : Transportasi, Distribution Center, VRP, Time Windows, Alogaritma Nearest Neighbour, Alogaritma Tabu Search