Penerapan Algoritma Nearest Neighbor dalam Permasalahan TSP untuk Menentukan Rute Terpendek Pendistribusian Krupuk Rengginang

Authors

  • Achmad Gilang Pamungkas Hani Putra Universitas Nahdlatul Ulama Blitar
  • Eva Amilatus Solikah Universitas Nahdlatul Ulama Blitar
  • Siti Ainun Nisak Universitas Nahdlatul Ulama Blitar

DOI:

https://doi.org/10.18592/jpm.v10i2.9756

Keywords:

Algoritma Nearest Neighbour, Heuristik, Optimasi, Travelling Salesman Problem

Abstract

Travelling Salesman Problem (TSP) adalah masalah optimasi yang digunakan untuk menentukan rute terpendek yang dimulai dan diakhiri pada titik yang sama, dengan mengunjungi semua titik yang diberikan tepat satu kali. Pada studi ini, permasalahan TSP diterapkan pada distribusi krupuk rengginang, di mana seorang pedagang harus merencanakan rute yang efisien dari tempat produksi menuju toko-toko untuk mengurangi biaya dan waktu perjalanan. Penelitian ini mengusulkan solusi optimasi menggunakan algoritma Nearest Neighbour, yang menghasilkan rute optimal sebagai berikut: A → B → H → I → F → G → C → D → E → J → A, dengan total jarak yang ditempuh sebesar 23,95 unit. Hasil ini menunjukkan bahwa algoritma Nearest Neighbour dapat memberikan solusi yang memadai dalam meminimalkan jarak tempuh pada kasus TSP ini.

References

Afrizal Herdyanto Sunaryono, Y. P. (2016). Pemilihan Rute Perjalanan Terpendek Menggunakan Algoritma. prosiding matematika.

Albuquerque, G., Ferreira, L., & Silva, E. (2017). A comparison of heuristic methods for the traveling salesman problem. European Journal of Operational Research, 258(3), 951-961. https://doi.org/10.1016/j.ejor.2016.11.045

Andik L. 2022. Penerapan K-NN dalam Permasalahan TSP untuk Menentukan Rite Terpendek Pengambilan Ulat Hongkong. Skripsi. Tidak Diterbitkan. Fakultas Ilmu Eksakta. Universitas Nahdlatul Ulama: Blitar.

Febrian, D. (2019). Aplikasi Metode Tetangga ( Nearest Neighbour Algorithm ) Terdekat untuk Mencari Rute Terpendek Perjalanan Wisata Museum dan Wisata Religi di Kota Medan. 5(1), 1–13.

Leong, C. K., Tan, W. K., & Lee, W. B. (2018). Solving the traveling salesman problem using dynamic programming approach. International Journal of Mathematical, Engineering, and Management Sciences, 3(3), 258-271. https://doi.org/10.22161/ijmems.3.3.8

Suci,W. (2020). Perbandingan Media Pembelajaran terhadap Hasil Belajar Al-Islam di SMA Muhammadiyah 1 gisting Kabupaten Tanggamus Tahun Pelajaran 2019/2020. Skripsi. Lampung: Institut Agama Islam Negeri (IAIN) Metro.

Yücesan, E., Ergen, B., & Yavuz, N. (2019). Solving the traveling salesman problem using simulated annealing and genetic algorithm techniques: A comparison. Computers and Industrial Engineering, 135, 301-308. https://doi.org/10.1016/j.cie.2019.06.015

Georgiadis, P., Bie, Z., & Lee, Y. (2020). Optimizing logistics in urban areas: The role of the travelling salesman problem. International Journal of Production Economics, 221, 107473. https://doi.org/10.1016/j.ijpe.2019.107473

Hernández, S., Orozco, J., & Sarmiento, J. (2018). A comparison of metaheuristics for solving the Traveling Salesman Problem. Computers & Operations Research, 91, 88-97. https://doi.org/10.1016/j.cor.2017.08.004

Kotsialos, A., Gendreau, M., & Mladenović, N. (2017). Hybrid algorithms for the Travelling Salesman Problem. Computers & Operations Research, 86, 133-141. https://doi.org/10.1016/j.cor.2017.06.003

Zhang, X., Zhang, Y., & Wei, X. (2019). A Hybrid Algorithm for Solving the Traveling Salesman Problem with Time Windows. Soft Computing, 23(12), 4185-4198. https://doi.org/10.1007/s00542-019-04602-z

Downloads

Published

2023-12-31

Issue

Section

Articles