PEMECAHAN TRAVELING SALESMEN PROBLEM MENGGUNAKAN TEKNIK BRANCH AND BOUND DAN CHEAPEST INSERTION HEURISTIC

  • Briand Wehelmus Lattan TEKNIK INDUSTRI UNIVERSITAS PATTIMURA
  • Johan M. Tupan Fakultas Teknik, Universitas Pattimura
  • Daniel B. Paillin Fakultas Teknik, Universitas Pattimura
Keywords: Branch and Bound, Cheapest Insertion Heuristic, Distribusi, Traveling Salesmen Problem

Abstract

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.

Downloads

Download data is not yet available.
Published
2021-10-31
How to Cite
Lattan, B., Tupan, J., & Paillin, D. (2021). PEMECAHAN TRAVELING SALESMEN PROBLEM MENGGUNAKAN TEKNIK BRANCH AND BOUND DAN CHEAPEST INSERTION HEURISTIC. I Tabaos, 1(1), 13-22. https://doi.org/10.30598/i-tabaos.2021.1.1.13-22
Section
Articles