PEMECAHAN TRAVELING SALESMEN PROBLEM MENGGUNAKAN TEKNIK BRANCH AND BOUND DAN CHEAPEST INSERTION HEURISTIC - Lattan, Briand Wehelmus; Tupan, Johan M.; Paillin, Daniel B. (Fakultas Teknik Universitas Pattimura, 2021)
Fa.Bandil merupakan perusahan distributor produk tepung terigu. Berdasarkan hasil pengamatan peneliti, waktu yang dibutuhkan perusahaan untuk satu kali proses distribusi yaitu 2 jam kerja ke 26 outlet, dengan jarak yang ditempuh yaitu 74,23 km. Biaya transportasi yang dibutuhkan seperti biaya bahan bakar ditambah dengan biaya maintenance yaitu Rp 669.361 dalam satu minggu proses distribusi. Ketidakpastian rute pengiriman produk ini menyebabkan rute distribusi tidak terstruktur dengan baik sehingga berdampak pada pertambahan jarak, waktu dan biaya transportasi. Tujuan penelitian ini adalah menentukan rute distribusi produk yang optimal dengan menggunakan software WINQSB. Metode yang digunakan untuk menyelesaikan permasalahan rute distribusi yaitu Branch and Bound dan Cheapest Insertion Heuristic dengan bantuan software WINQSB. Hasil penelitian menunjukan pengolahan data jarak tempuh dan waktu tempuh untuk 3 rute distribusi dengan metode Branch and Bound sesuai dengan pembagian yang sudah dilakukan jarak tempuh untuk rute 1 yaitu (39,6), rute 2, (31,70), dan rute 3 (19,90). Untuk waktu tempuh Branch and Bound sesuai dengan pembagian yang sudah dilakukan maka waktu tempuh untuk rute 1 yaitu (59,4), rute 2 (47,55), dan rute 3 (29,85). Dengan metode Cheapest Insertion Heuristic jarak untuk rute 1 yaitu (39,60), rute 2 (32,40), dan rute 3 (20,50). Untuk data waktu tempuh rute 1 yaitu (59,4), rute 2 (48,6), dan rute 3 (30,75). Kesimpulan dari penelitian ini yaitu rute dengan metode Branch and Bound memberikan hasil biaya transportasi sebesar Rp 547.613, yang mana hasilnya lebih kecil dari metode cheapest insterion heuristi yaitu biaya transportasi sebesar Rp 548.458, dan secara keseluruhan hasil metode Branch and Bound lebih kecil dari metode cheapest insterion heuristi dan hasil regular perusahaan.