PT KLM merupakan salah satu mitra dari PT PERTAMINA yang melakukan kegiatan berupa pendistribusian bahan bakar minyak jenis Solar HSD (Head Speed Diesel) dari DEPOT milik PT PERTAMINA untuk didistribusikan ke PLTD. Berdasarkan data pada bulan Juli-Desember 2016 milik PT KLM bahwa terjadi permasalahan, dimana terjadinya keterlambatan dalam pengiriman bahan bakar minyak sehingga menyebabkan pengeluaran biaya pinalty. Penyebab terjadinya keterlambatan ialah waktu dan jarak tempuh yang tidak efisien karena belum adanya jadwal dan rute pendistribusian yang tepat.
Dalam mendistribusikan bahan bakar minyak tersebut, PT KLM memiliki armada transportasi berupa mobil tanki sejumlah 9 buah dengan 2 varian kapasitas. Maka permasalahan ini dapat diselesaikan dengan menggunakan pendekatan Vehicle Routing Problem (VRP) dengan karakteristik time window, multiple trip, split delivery, dan heterogenous fleet. Pada karakteristik tersebut menunjukkan bahwa permasalahan VRP yang dihadapi oleh PT. KLM cukup kompleks, sehingga harus diselesaikan dengan pendekatan metaheuristik berupa algoritama Tabu Search. Dengan solusi awal berupa algoritma Nearest Neighbor.
Hasil dari perhitungan algoritma tersebut dapat mengurangi jarak tempuh dan waktu tempuh sebesar 9,4%, meminimasi keterlambatan, penurunan biaya total operasional pengiriman hingga 16,27%, serta penurunan jumlah kendaraan yang digunakan sebesar 12,5%.
Kata Kunci : Vehicle Routing Problem (VRP), Time Window, Heterogeneous Fleet, Multiple Trip, Split Delivery, Algoritma Nearest Neighbor, Algoritma Tabu Search.