PT. XYZ adalah sebuah perusahaan yang mengkhususkan diri dalam pembuatan suku cadang dan ko mponen motor. Perusahaan terletak di daerah Cimahi, Jawa Barat dan mulai beroperasi pada tahun 1969. Perusahaan ini memiliki gudang sebagai tempat penyimpanan bahan baku dan finish good. Finish good tersebut akan didistribusikan ke luar kota Bandung. PT. XYZ sering mengalami keterlambatan pengiriman sehingga menyebabkan biaya yang harus dikeluarkan oleh perusahaan lebih besar. Penelitian ini bertujuan untuk menghasilkan rute yang dapat meminimasi total biaya transportasi yang harus dikeluarkan oleh perusahaan. Permasalahan yang terjadi pada PT. XYZ merupakan permasalahan umum pada bidang transportasi yang pada umumnya diselesaikan dengan pendekatan Vehicle Routing Problem. VRP yang terjadi pada PT. XYZ termasuk kedalam karakteristik VRP with Heterogeneous Fleet, VRP with Time Windows dan VRP with Split Delivery. Permasalahan ini diselesaikan menggunakan Algoritma Tabu Search dan Algoritma Nearest Neighbour sebagai solusi awal yang digunakan untuk masukkan dalam algoritma Tabu Search. Pendekatan VRP menggunakan algoritma Tabu Search mampu menghasilkan rute yang dapat meminimasi total biaya transportasi secara keseluruhan sebesar 33% dari kondisi eksisting.