PT. AAA merupakan salah satu perusahaan yang memproduksi cat kayu, cat tembok, cat batu, pelitur, dan thinner yang mempunyai layanan yaitu melakukan pengiriman produk ke pelanggan secara langsung. Hal tersebut dilakukan menggunakan armada sendiri untuk pelanggan di Pulau Jawa khususnya untuk daerah Karesidenan Surakarta. Dalam melakukan pengiriman, armada seringkali mengalami keterlambatan dikarenakan perencanaan penentuan rute yang kurang baik. Urutan rute pengiriman berdasarkan frekuensi rute yang dilalui oleh operator, tidak dengan perencanaan yang baik sehingga menyebabkan armada tiba di luar jam buka-tutup pelanggan.
Penelitian ini dilakukan untuk memberikan usulan rute pengiriman produk ke pelanggan khususnya untuk daerah Karesidenan Surakarta dengan menggunakan metode Vehicle Routing Problem with Heterogeneous Fleet and Time Windows dan Algoritma Two-Phase Tabu Search dengan pembangkit solusi awal yaitu Algoritma Nearest Neighbour untuk mengurangi jumlah keterlambatan pengiriman produk. Metode VRP digunakan karena mampu menyelesaikan masalah penentuan rute yang dialami oleh perusahaan. Adapun hasil dari penelitian ini adalah urutan rute dan kendaraan yang digunakan untuk melakukan pengiriman produk.
Hasil perhitungan dari penelitian ini adalah memberikan usulan urutan rute pengiriman untuk armada pengiriman dengan jarak tempuh sebesar 22,51% lebih kecil dibandingkan urutan rute pada kondisi awal. Jarak tempuh tersebut berkurang dari 938,93 km menjadi 727,516 km. Akibat dari pengurangan jarak tempuh tersebut, maka keterlambatan pengiriman produk kepada pelanggan berkurang menjadi rata-rata empat lokasi pelanggan untuk setiap hari.
Kata Kunci: Heterogeneous Fleet, Minimize Travel Distances, Rute Distribusi, Vehicle Routing Problem, Time Window