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
DOI: https://doi.org/10.30598/i-tabaos.2021.1.1.13-22
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
Issue
Vol 1 No 1 (2021)
Section
Articles

Copyright (c) 2021 Briand Wehelmus Lattan

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Penulis yang menerbitkan artikel di Jurnal i-TABAOS menyetujui persyaratan berikut: 

  • Penulis memegang hak cipta dan memberikan hak publikasi pertama dari karya yang dilisensikan secara bersamaan kepada Jurnal i-TABAOS, di bawah Lisensi Creative Commons Attribution-ShareAlike 4.0 yang memungkinkan orang lain untuk berbagi karya dengan pengakuan kepemilikan karya dan publikasi awal di jurnal ini.
  • Penulis dapat membuat pengaturan kontrak tambahan yang terpisah untuk distribusi non-eksklusif dari versi jurnal yang diterbitkan (misalnya, mempostingnya ke repositori institusional atau menerbitkannya dalam sebuah buku) dengan pengakuan publikasi awal  pada jurnal ini.
  • Penulis diizinkan dan didorong untuk memposting karyanya secara online (misalnya, di repositori institusional atau di situs web mereka) sebelum dan selama proses pengiriman, karena dapat menghasilkan pertukaran yang produktif, serta kutipan yang lebih awal dan lebih besar dari karya yang diterbitkan (Lihat Pengaruh Akses Terbuka).

Baca lebih lanjut tentang Creative Commons Attribution-ShareAlike 4.0 Licence: https://creativecommons.org/licenses/by-sa/4.0/.