Usulan Perbaikan Rute Pengangkutan Sampah Menggunakan Metode Branch And Bound Dan Nearest Neighbour Untuk Meminimalkan Biaya Transportasi

Nidya Wisudawati; Ananda Valentine; Rurry Patradhiani

doi:10.24014/jti.v8i2.20100

Usulan Perbaikan Rute Pengangkutan Sampah Menggunakan Metode Branch And Bound Dan Nearest Neighbour Untuk Meminimalkan Biaya Transportasi

Nidya Wisudawati, Ananda Valentine, Rurry Patradhiani

Abstract

Penelitian ini bertujuan untuk memilih rute optimal pengangkutan sampah pada UKM Kelompok Usaha Bersama Peduli Sampah Kecamatan Tanah Abang sehingga dapat meminimalkan biaya transportasi. Metode Branch and Bound dan Nearest Neighbour dipilih dalam menyelesaikan masalah pada penelitian ini. Metode Branch and Bound adalah metode pencarian di dalam ruang solusi secara sistematis. Sedangkan metode Nearest Neighbour adalah sebuah teknik menyelesaikan permasalahan rute dengan menentukan titik terdekat dengan jarak terpendek. Hasil perhitungan untuk rute awal pengangkutan sampah didapatkan jarak tempuh per tahun sebesar 5.356,8Km, waktu tempuh per tahun sebesar 12.480 Menit dan biaya transportasi per tahun sebesar Rp.11.584.793,6. Dari hasil penelitian menggunakan metode Branch and Bound didapat jarak tempuh per tahun sebesar 4.454,4 Km, waktu tempuh per tahun sebesar 10.560 Menit dan biaya transportasi per tahun sebesar Rp.9.641.548,8. Dengan metode Nearest Neighbor didapat jarak tempuh per tahun sebesar 4.454,4 Km, waktu tempuh per tahun sebesar 10.368 Menit dan biaya transportasi per tahun sebesar Rp.9.641.548,8. Perbandiangan antara kedua metode tersebut menghasilkan jarak tempuh dan biaya transportasi yang sama, tetapi terdapat perbedaan pada waktu tempuh. Metode Nearest Neighbour memiliki waktu tempuh yang lebih cepat sehingga metode ini terpilih untuk mencapai tujuan penelitian.

Full Text:

PDF

References

Kementrian Lingkungan Hidup, “Kementrian Lingkungan Hidup,” 2020. ppkl.menlhk.go.id (accessed May 20, 2021).

Toth and Vigo, Vehicle Routing Problem. Philadelphia: SIAM Monographs on Discrete Mathematics and Application., 2002.

I. Indrawati, N. Eliyati, and A. Lukowi, “Penentuan Rute Optimal pada Pengangkutan Sampah di Kota Palembang dengan Menggunakan Metode Saving Matrix,” J. Penelit. Sains, vol. 18, no. 3, p. 168493, 2016.

W. L. Winston, Operations research: Applications and algorithms, Fourth Edi. California: Wads-worth Publishing, 2004.

E. Armandi, A. Purwani, and U. Linarti, “Optimasi Rute Pengangkutan Sampah Kota Yogyakarta Menggunakan Hybrid Genetic Algorithm,” 2013, doi: 10.23917/jiti.v18i2.8744.

A. Riyanto and F. Herni Mustofa, “Usulan Perbaikan Rute Pengiriman Dengan Menggunakan Metode Nearest Neighbour Dan Branch And Bound Di Home Industry Donat Enak Bandung,” vol. 02, no. 02, 2014.

D. Moriza, H. Adiyanto, and Y. Nurdiansyah, “Rute Pendistribusian Air Mineral Dalam Kemasan Menggunakan Metode Nearest Neighbour dan Branch and Bound Di PT Agronesia BMC,” Reka Integr. Itenas, vol. 4, no. 2, pp. 195–205, 2016, [Online]. Available: https://ejurnal.itenas.ac.id/index.php/rekaintegra/article/view/1101

D. P. T. X and C. B. K. Wulandari, “Penentuan Rute Distribusi Menggunakan Metode Nearest Neighbors dan Metode Branch,” vol. 02, no. 01, pp. 7–12, 2020.

F. Triyanto, H. Adianto, and S. Susanty, “Usulan Rancangan Rute Distribusi Gas LPG 3 Kg Menggunakan Metode Heuristik dan Metode Branch and Bound,” J. Online Insitut Teknol. Nas., vol. 03, no. 03, pp. 194–205, 2015.

M. Amri, A. Rahman, and R. Yuniarti, “Penyelesaian Vehicle Routing Problem dengan Menggunakan Metode Nearest Neighbour ( Studi Kasus : MTP Nganjuk Distributor PT . Coca Cola ),” J. Rekayasa dan Manaj. Sist. Ind., vol. 2, no. 1, pp. 36–45, 2014.

G. Dantzig and J. Ramser, The Truck Dispatching Problem. Management Science, 1959.

P. G. Pakusadewa, C. Dewi, and R. C. Wihandika, “Penerapan Hibridisasi Algoritme Genetika dan Simulated Annealing untuk Optimasi Vehicle Routing Problem pada Kasus Pengangkutan Sampah Kota Denpasar Putu,” J. Pengemb. Teknol. Inf. dan Ilmu Komput., vol. 2, no. 9, pp. 3215–3223, 2018.

T. Chandra, “Penerapan Algoritma North West Corner Dalam Penyelesaian Masalah Transportasi,” J. TIMES, vol. 5, no. 1, pp. 12–16, 2016, [Online]. Available: http://stmik-time.ac.id/ejournal/index.php/jurnalTIMES/article/view/393/106

M. Tamannaei and M. R. Barzoki, “Mathematical Programming and Solution approaches for Minimizing Tardiness and Transportation Costs in The Supply Chain Schedulling Problem,” Comput. Ind. Eng., vol. 127, pp. 643–656, 2019, doi: https://doi.org/10.1016/j.cie.2018.11.003.

R. Yuniarti and M. Astuti, “Penerapan Metode Saving Matrix dalam Penjadwalan dan Penentuan Rute Distribusi Premium di SPBU Kota Malang,” J. Rekayasa Mesin, vol. 4, no. 1, pp. 17–26, 2013.

B. Santosa and P. Willy, Metoda Metaheuristik Konsep dan Implementasi. Surabaya: Guna Widya, 2011.

Suyanto, Algoritma Optimasi Deterministik atau Probabilistik. Yogyakarta: Graha Ilmu, 2010.

I. Fajar, G. Siregar, and D. Tarwidi, “Algoritma Mencari Lintasan Terpendek,” Bandung, 2005.

M. Mataija and M. R. Segic, “Solving The Travelling Salesman Problem Using The Branch And Bound Method,” J. Polytech. Rijeka, vol. 4, no. 1, pp. 259–270, 2016.

S. Martono and H. L. H. S. Warnars, “Penentuan Rute Pengiriman Barang Dengan Metode Nearest Neighbor,” Petir, vol. 13, no. 1, pp. 44–57, 2020, doi: 10.33322/petir.v13i1.869.

A. Suyudi, A. Imran, and S. Susanty, “Usulan Rancangan Rute Pendistribusian Air Galon Hanaang Menggunakan Algoritma Nearest Neighbour Dan Local Search *,” J. Online Inst. Teknol. Nas., vol. 03, no. 04, pp. 264–272, 2015, [Online]. Available: https://ejurnal.itenas.ac.id/index.php/rekaintegra/article/view/924

O. Braysy and M. Grendreau, “Vehicle Routing Problem With Time Windows,” Transp. Sci., vol. 39, no. 1, pp. 104–118, 2005.

E. Balas and P. Toth, Branch and Bound Methods for the Travelling Salesman Problem. University of Pittsburgh PA Manajement Sciences Research, 1983.

S. Laaksonen, “Regression-based nearest neighbour hot decking,” Comput. Stat., vol. 15, pp. 65–71, 2000.

J. L. Vermeulen, A. Hillebrand, and R. Geraerts, “A comparative study of k-nearest neighbour techniques in crowd simulation,” Comput. Animat. Virtual Worlds, vol. 28, no. 3–4, 2017.

DOI: http://dx.doi.org/10.24014/jti.v8i2.20100