PT XYZ merupakan sebuah perusahaan yang bergerak di bidang industri bahan kimia. Produk yang dihasilkan adalah cat dengan varian jenis, ukuran, dan warna. PT XYZ memiliki 2 Distribution Center yang terletak di dua daerah yang berbeda yaitu Bandung dan Surabaya. Distribution Center Bandung mendistribusikan produk secara langsung ke toko bangunan yang terdaftar sebagai pelanggan tetap perusahaan yang tersebar di beberapa daerah distribusi, salah satunya Cijerah. Transportasi merupakan salah satu elemen yang memberikan kontribusi yang cukup besar terhadap total biaya distribusi. PT XYZ seringkali mengalami keterlambatan pengiriman. Hal ini menimbulkan biaya yang harus dikeluarkan oleh perusahaan lebih besar. Penelitian ini bertujuan untuk meminimasi total biaya transportasi yang harus dikeluarkan oleh PT XYZ agar perusahaan tersebut dapat mengoptimalkan sistem distribusinya.
Permasalahan yang terjadi pada PT XYZ merupakan permasalahan umum dalam bidang transportasi dan pada umumnya diselesaikan dengan pendekatan Vehicle Routing Problem. VRP yang terjadi pada PT XYZ merupakan VRP dengan karakteristik VRP with Heterogeneous Fixed Fleet, VRP with Multiple Product, dan VRP with Time Windows. Karakteristik tersebut menunjukkan bahwa VRP yang terjadi pada PT XYZ cukup kompleks sehingga permasalahan ini diselesaikan dengan pendekatan metaheuristik yaitu Algoritma Genetika. Penulis menggunakan Algoritma Nearest Neighbour sebagai pembangkit solusi awal yang digunakan sebagai masukkan dalam Algoritma Genetika.
Pendekatan VRP dengan menggunakan Algoritma Genetika mampu mengurangi total jarak tempuh yang dibutuhkan sebesar 10,38% dari total jarak dan mengurangi total biaya transportasi secara keseluruhan sebesar 5,017% pada kondisi existing.
Kata Kunci: Transportasi, VRP, Heterogeneous Fleet, Multipe Product, Time Window, Algoritma Nearest Neighbour, Algoritma Genetika.