Penentuan Rute Optimal Distribusi Produk Nestle dengan Metode Traveling Salesman Problem (Tsp) (Studi Kasus : PT. Paris Jaya Mandiri)

Paris Jaya Mandiri adalah salah satu Perusahaan yang bergerak pada bidang distributor produk Nestle di Indonesia. Sebagai Perusahaan distributor, aktivitas distribusi harus diberi perhatian khusus sehingga dapat mengatasi adanya keterlambatan atau ketidaktepatan waktu pengiriman produk yang disebabkan karena ketidakpastian rute pengiriman produk. Masalah ini dapat diatasi dengan memberikan solusi rute optimal agar dapat diperoleh effisiensi jarak dan waktu tempuh yang dapat berdampak positif bagi Perusahaan.Traveling Salesman Problem merupakan suatu permasalahan untuk mencari jarak tempuh minimum dari titik awal menuju semua titik tujuan dan kembali lagi pada titik awal dengan asumsi bahwa semua titik tujuan yang akan dilalui hanya dikunjungi sebanyak satu kali untuk memperoleh rute optimal. Salah satu algoritma yang dapat digunakan dalam menyelesaikan permasalahan ini adalah algoritma Branch and Bound. Tolak ukur yang digunakan pada metode ini adalah jarak antaroutlet dimulai dari mengukur masing – masing jarak dari gudang menuju oulet dan kembali ke gudang. Pada penelitian ini dilakukan perhitungan untuk mengukur jarak terpendek dari 67 lokasi outlet yang tersebar pada wilayah distribusi Sirimau 1 dan 2 serta wilayah distribusi Nusaniwe. Hasil olahan data metode Branch and Bound menunjukkan bahwa dari 3 wilayah dapat diperoleh 5 rute optimal yaitu rute 1 didapat jarak sebesar 8.09 Km dengan total waktu 46.03 menit, rute 2 sebesar 9.47 Km dengan total waktu 59.2 menit, rute 3 sebesar 10.88 Km dengan total waktu 35.35 menit, rute 4 sebesar 9.74 Km dengan total waktu 43.08 menit dan rute 5 sebesar 19.87 Km dengan total waktu 83.05 menit. Dari hasil data tersebut diperoleh penghematan jarak sebesar 17.96% dan total waktu sebesar 6.26% dari rute awal Perusahaan