Salah satu kegiatan dalam transportasi adalah pendistribusian suatu produk dari suatu tempat ke tempat lain atau dari suatu sumber ke suatu atau beberapa tujuan. Dalam mendistribusikan suatu produk, faktor biaya, jarak tempuh dan waktu tempuh menjadi hal yang cukup penting untuk diperhatikan karena melibatkan banyak hal dalam pengoperasiannya. Misalnya, jumlah armada yang dibutuhkan, kapasitas armada (jumlah produk yang mampu diangkut), biaya bahan bakar, dan lain-lain, sehingga dibutuhkan suatu perhitungan yang matang agar proses distribusi yang ada menjadi lebih optimal, baik dari segi jalur yang dilalui, biaya, serta jumlah armada yang digunakan. Hal itulah yang akhirnya mendorong penulis untuk melakukan penelitian mengenai optimasi jalur distribusi pengiriman produk di PT Nippon Indosari Corpindo yang bertujuan untuk mengetahui rute atau jalur distribusi yang mampu memberikan biaya yang minimal serta jumla armada yang optimal untuk digunakan dalam mendistribusikan produk.
Penelitian ini menggunakan metode Travelling Salesman Problem (TSP) yang bertujuan untuk mengetahui agen mana saja yang harus dikunjungi terlebih dahulu sehingga menghasilkan jarak tempuh yang minimum. Sebelum melakukan proses TSP, terlebih dahulu dilakukan proses kluster dengan metode transportasi untuk membagi wilayah pengiriman menjadi sub wilayah. Untuk melakukan proses kluster, penulis menggunakan data jarak dari satu agen ke agen lainnya serta data demand untuk tiap-tiap agen. Seluruh data tersebut penulis dapatkan dengan cara melakukan survey ke lapangan serta menggunakan data sekunder yang didapatkan dari perusahaan.
Hasil penelitian menunjukkan bahwa terdapat dua buah jalur usulan yang dapat digunakan oleh perusahaan, yaitu jalur usulan dengan tiga kluster dan empat kluster. Kedua jalur usulan tersebut memiliki kelebihan dan kekurangan, yaitu pada penghematan biaya yang dapat dilakukan. Dengan menggunakan jalur usulan dengan tiga kluster, total penghematan yang dapat dilakukan oleh perusahaan adalah sebesar Rp 2.935.200,- / bulan, dengan cukup menggunakan tiga buah armada saja.
Berdasarkan kondisi diatas, dapat disimpulkan bahwa sebaiknya perusahaan menggunakan jalur usulan dengan tiga kluster karena akan lebih banyak menghemat total biaya distribusi dan hanya cukup menggunakan tiga buah armada saja dengan jangka waktu selamanya karena pola trend data penjualan menunjukkan trend linier.