Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
2 Oktober 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 238-247 DOI: https://doi.
org/10.
55606/jurrimipa.
Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling Salesman Problem Rizki Putra Sinaga Universitas Negeri Medan Faridawaty Marpaung Universitas Negeri Medan Korespondensi penulis: rizkiputrasinaga6@gmail.
Abstract: The main problem of the Traveling Salesman Problem is that a salesman travels to several places to go with a known distance and then returns to his original place by using the shortest route from his journey, and all the places the salesman goes to are only allowed once.
This research focuses on the problem of distributing goods at PT.
The Medan Nugraha Ekakurir (JNE) route with the destination delivery address in the Medan area.
The Cheapest Insertion Heuristic Algorithm is an algorithm used to form tours .
by gradually building the shortest path route with minimal weight, by adding new points one at a time.
One.
The Nearest Neighbor Algorithm is a simple and fast algorithm to build a feasible initial tour length from TSP where the technique takes the shortest distance from the initial position regardless of other distances.
This study resulted in the conclusion that the application of the cheapest insertion heuristic and nearest neighbor algorithms in terms of finding the distance to the problem of shipping goods at PT.
The Medan Nugraha Ekakurir (JNE) route starts with finding the distance between addresses with the help of google maps, then continues with the help of the WinQSB software.
Based on the research results obtained using the cheapest insertion heuristic and nearest neighbor algorithms, it is obtained that the search for the shortest route distance for shipping goods at PT.
The smaller Medan Nugraha Ekakurir (JNE) route is generated by the nearest neighbor algorithm.
This shows that the nearest neighbor algorithm is more effective in terms of finding the traveling distance on the Traveling Salesman Problem problem of shipping goods at PT.
Medan's Nugraha Ekakurir (JNE) Line.
Keywords: Traveling Salesman Problem.
Cheapest Insertion Heuristic Algorithm.
Nearest Neighbor Abstrak: Pokok permasalahan Traveling Salesman Problem adalah perjalanan seorang salesman menuju ke beberapa tempat yang akan dituju dengan jarak yang diketahui lalu kembali ke tempat semula dengan menggunakan rute terpendek dari perjalananya, dan semua tempat yang dituju oleh salesman hanya boleh satu Penelitian ini focus pada masalah pendistribusian barang di PT.
Jalur Nugraha Ekakurir (JNE) Medan dengan tujuan alamat pengiriman di wilayah medan.
Algoritma Cheapest Insertion Heuristic merupakan suatu algoritma yang digunakan untuk membentuk tur .
dengan cara secara bertahap membangun rute jalur terpendek dengan bobot minimal, dengan menambahkan titik-titik baru satu per satu.
Algoritma Nearest Neighbor merupakan Algoritma yang sederhana dan cepat untuk membangun panjang tur awal yang layak dari TSP dimana teknik mengambil jarak yang paling dekat dari posisi awal tanpa memperhatikan jarak yang lain.
Penelitian ini menghasilkan kesimpulan yaitu penerapan algoritma cheapest insertion heuristic dan nearest neighbor dalam hal pencarian jarak pada masalah pengiriman barang di PT.
Jalur Nugraha Ekakurir (JNE) Medan dimulai dengan mencari jarak antar alamat dengan bantuan goggle maps, kemudian dilanjutkan dengan bantuan software WinQSB.
Berdasarkan hasi penelitian yang diperoleh menggunakan algoritma cheapest insertion heuristic dan nearest neighbor diperoleh pencarian jarak rute terpendek pengiriman barang di PT.
Jalur Nugraha Ekakurir (JNE) Medan yang lebih kecil dihasilkan algoritma nearest neighbor.
Hal ini menunjukan algoritma nearest neighbor lebih efektif dalam hal pencarian jarak traveling pada persoalan Traveling Salesman Problem pengiriman barang di PT.
Jalur Nugraha Ekakurir (JNE) Medan.
Kata kunci: Traveling Salesman Problem.
Algoritma Cheapest Insertion Heuristic.
Nearest Neighbor
LATAR BELAKANG
Dalam kehidupan sehari-hari, ketika kita berpindah dari satu tempat ke tempat lain, penting untuk mempertimbangkan waktu dan biaya agar dapat menemukan rute terpendek yang paling efisien.
Salah satu tantangan yang sering dihadapi adalah mencari rute terpendek dalam Received Mei 30, 2023.
Revised Juni 28, 2023.
Accepted Juli 31, 2023 * Rizki Putra Sinaga, rizkiputrasinaga6@gmail.
Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling Salesman Problem perjalanan yang melibatkan kunjungan ke setiap tempat hanya sekali dan kembali ke tempat Permasalahan ini dikenal dengan sebutan "Traveling Salesman Problem" (TSP).
Traveling Salesman Problem (TSP) dikenal sebagai salah satu masalah optimasi yang banyak menarik perhatian para peneliti sejak beberapa puluh tahun.
Pokok permasalahan TSP adalah perjalanan seorang salesman menuju ke beberapa tempat yang akan dituju dengan jarak yang diketahui lalu kembali ke tempat semula dengan menggunakan rute terpendek dari perjalananya, dan semua tempat yang dituju oleh salesman hanya boleh satu kali (Aristi 2.
Dalam menyelesaikan TSP, digunakan konsep teori graf yang merupakan salah satu cabang ilmu matematika.
Graf TSP mempresentasikan jaringan berbobot, di mana setiap titik dalam graf mewakili sebuah kota, setiap sisi mewakili jalan yang menghubungkan kota-kota tersebut, dan bobot pada setiap sisi mewakili jarak antara kota-kota tersebut yang perlu ditempuh (Efendi, 2.
Meskipun TSP terdengar sederhana dalam pernyataannya, namun pada kenyataannya sangat sulit untuk menemukan solusi yang optimal, terutama ketika jumlah kota yang terlibat sangat besar.
TSP memiliki banyak aplikasi dalam masalah dunia nyata, seperti perencanaan rute pengambilan surat dari kotak pos, pengaturan rute pengisian uang di mesin ATM, pengiriman koran, dan pendistribusian barang.
Terdapat beberapa penelitian yang pernah dilakukan mengenai TSP , diantaranya penelitian yang dilakukan oleh (Rio Utomo 2.
tentang Implementasi Algoritma Cheapest Insertion Heuristic dalam Penyelesaian Traveling Salesman Problem (TSP).
Dari hasil penelitian diperoleh bahwa algoritma Cheapest Insertion Heuristic dapat digunakan umtuk mencari rute terpendek pendistribusian air mineral Al-MaAosoem Muawanah dengan menggunakan algortima Cheapest Insertion Heuristic dan data jarak diambil dari koordinat titik awal menggunakan latitude dan longitude.
Penelitian lain dilakukan oleh (Katarina 2.
mengenai Distribusi barang menggunakan Algoritma Nearest Neighbor.
Dari hasil peneltian diperoleh bahwa Algoritma Nearest Neighbor dapat digunakan mencari rute terpendek pada distribusi minuman aqua merek OXYO ke konsumen.
Algoritma yang biasa digunakan dalam mencari TSP yaitu algoritma Best First Search .
Genetika.
Ant Colony.
Nearest Neighbor.
Cheapest Insertion Heuristic .
Djikstra dan masih banyak lagi.
Dalam penelitian ini, peneliti akan menggunakan algoritma Nearest Neighbor dan Cheapest Insertion Heuristic menyelesaikan TSP.
Kedua algoritna memiliki cara dalam menyelesaikan TSP sehingga peneliti ingin mengkaji algoritma yang lebih baik menyelesaikan permasalahan TSP dalam hal pencarian jarak traveling.
JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 238-247 Algoritma Cheapest Insertion Heuristic merupakan suatu algoritma yang digunakan untuk membentuk tur .
dengan cara secara bertahap membangun rute jalur terpendek dengan bobot minimal, dengan menambahkan titik-titik baru satu per satu.
Pada setiap langkah, algoritma ini memilih titik baru dan sisi yang memberikan nilai penyisipan paling kecil.
Kelebihan dari algoritma Cheapest Insertion Heuristic adalah kemampuannya dalam memilih simpul yang akan disisipkan, baik itu simpul yang berada di luar tur yang sedang dibangun maupun sisi yang sudah ada dalam tur (Kusrini, 2.
Algoritma Nearest Neighbor adalah Algoritma yang sederhana dan cepat untuk membangun panjang tur awal yang layak dari TSP.
Algoritma Nearest Neighbor adalah teknik serakah yang menemukan kemungkinan terbaik .
arak terpendek dari sebuah nod.
di setiap langkah (Dian 2.
Kedua algoritma memiliki keunikan dan cara masing-masing untuk menyelesaikan TSP untuk itu peneliti ingin membandingan keduanya.
Seperti yang diketahui permasalahan TSP banyak diapikasikan dalam kehidupan sehari-hari contohnya pendistribusian atau pengiriman Proses pendistribusian atau pengiriman barang adalah proses dimana perusahaan atau toko penyedia barang sangat memerlukan pertimbangan dan perhitungan yang tepat mencari rute terpendek dalam pendistribusian atau pengiriman karena berkaitan dengan transportasi yang dikeluarkan dalam pendistribusian atau pengiriman barang.
PT.
Jalur Nugraha Ekakurir (JNE) merupakan salah satu perusahaan yang bergerak dalam bidang jasa pengiriman barang di Indonesia.
PT.
Jalur Nugraha Ekakurir (JNE) sendiri memiliki cabang di setiap alamat di seluruh Indonesia.
Dalam mengirim barang dari pusat ke pelanggan di berbagai tempat dan di banyak alamat, perlu adanya suatu sistem yang mampu meminimalisasi biaya pengiriman agar didapatkan keuntungan yang maksimal.
Oleh karena itu penelitian ini menggunakan data yang diperoleh dari rute pengiriman barang PT.
Jalur Nugraha Ekakurir (JNE) untuk membandingkan algoritma mana yang lebih baik menyelesaikan permasalahan TSP dalam hal pencarian rute terpendek pada kasus proses perdistribusian atau pengiriman barang.
Pada saat ini belum adanya perbandingan berapa baiknya cara kedua algoritma dalam hal pencarian rute terpendek pada kasus pengiriman Selain menggunakan penyelesaian manual, untuk menghindari perhitungan salah maka dibutuhkan sebuah software aplikasi untuk membantu memeriksa hasil perhitungan kedua Software WINQSB merupakan software yang cukup baik dalam memeriksa hasil perhitungan kedua algoritma.
Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest
Neighbor Dalam Menyelesaikan Traveling Salesman Problem
KAJIAN TEORITIS
PT.
Jalur Nugraha Ekakurir (JNE) merupakan salah satu perusahaan yang bergerak dalam bidang jasa pengiriman barang di Indonesia.
PT.
Jalur Nugraha Ekakurir (JNE) sendiri memiliki cabang di setiap alamat di seluruh Indonesia.
Dalam mengirim barang dari pusat ke pelanggan di berbagai tempat dan di banyak alamat, perlu adanya suatu sistem yang mampu meminimalisasi biaya pengiriman agar didapatkan keuntungan yang maksimal.
Penelitian mengenai Travelling Salesman Problem (TSP) memiliki keterkaitan yang signifikan dengan teori graf.
Setiap kota yang harus dikunjungi oleh seorang salesman dapat direpresentasikan sebagai simpul .
, sedangkan jalur yang menghubungkan dua kota dapat diwakili oleh tepi .
pada suatu graf.
Secara umum, graf adalah suatu struktur yang digunakan untuk menggambarkan hubungan antara objek-objek, seperti peta, jaringan distribusi air, dan sejenisnya.
Dalam graf, setiap objek dapat direpresentasikan sebagai titik atau simpul, dan garis yang menghubungkan titik-titik tersebut merepresentasikan jalur atau hubungan antara objek-objek tersebut.
Graf dapat dituliskan dalam notasi G(V.
E), di mana V adalah himpunan simpul .
odes/vertice.
dalam graf, dan E adalah himpunan tepi .
yang menghubungkan simpul-simpul tersebut.
Travelling Salesman problem (TSP) merupakan salah satu permasalahan yang banyak dipelajari dalam optimasi kombinatorial.
Meskipun sederhana dalam penyajiannya.
TSP sangat sulit untuk diselesaikan secara optimal.
Sebagai masalah NP-Hard.
TSP tidak dapat diselesaikan dengan algoritma eksak dalam waktu polynomial computation.
Seiring dengan meningkatnya ukuran masalah, waktu komputasi yang dibutuhkan untuk menyelesaikan TSP secara eksak akan meningkat secara eksponensial.
TSP melibatkan mencari tur dengan jarak minimal yang melintasi setiap kota tepat satu kali dan kembali ke kota awal.
Secara teoritis.
TSP dapat direpresentasikan sebagai Graph lengkap dan berbobot G = (V.
E), di mana V adalah himpunan titik dan E adalah himpunan sisi.
Algoritma Cheapest Insertion Heuristic merupakan suatu pendekatan yang digunakan untuk membentuk tur dengan menambahkan titik secara bertahap dengan biaya minimal.
Algoritma ini memilih titik baru dan sisi yang akan menyisipkannya sehingga mendapatkan nilai penyisipan terkecil.
Kemudian, titik baru tersebut disisipkan di antara dua titik yang telah terpilih sebelumnya.
Algoritma ini seringkali menghasilkan solusi yang baik karena proses pemilihan tempat yang akan disisipkan dilakukan pada setiap titik di luar tur dan setiap sisi di dalam tur yang telah terbentuk.
Dengan menggunakan algoritma Cheapest Insertion Heuristic,rute perjalanan dapat terbentuk secara efisien dengan mempertimbangkan bobot Proses pemilihan titik baru dan penyisipannya secara berturut-turut membantu JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 238-247 mengoptimalkan perjalanan dalam mencapai solusi yang cukup baik.
Algoritma ini menjadi salah satu pendekatan yang populer dalam menyelesaikan permasalahan TSP.
(Saleh 2.
Software QSB (Quantity System for busines.
atau umumnya juga dikenal dengan nama WINQSB (QSB yang berjalan pada sistem operasi Window.
merupakan software yang mengandung algoritma problem solving untuk riset operasi .
perational researc.
dan untuk ilmu manajemen.
WINQSB sendiri terdapat beberapa modul yang dapat digunakan untuk menyelesaikan masalah-masalah operation riset dan ilmu manajemen seperti analisis Sampling.
Agregat dalam sistem Produksi.
Model Jaringan Analisis Keputusan.
Pemrograman dinamis, goal programming.
Tata letak fasilitas, peramalan permintaan.
Sistem inventory.
Penjadwalan kerja.
Pemrograman Linier dan Integer.
Pernencanaan kebutuhan material (MRP).
Proses Markov, dan teori antrian.
Pada penelitian ini software WINQSB digunakan untuk menyelesaikan model jaringan pada persoalan Traveling Salesman Problem.
METODE PENELITIAN
Jenis penelitian yang dilakukan dalam penelitian ini adalah studi kasus pada PT.
Jalur Nugraha Ekakurir (JNE) Medan.
Jenis data yang digunakan ialah data sekunder yang diperoleh dari PT.
Jalur Nugraha Ekakurir (JNE) Medan.
Data yang digunakan dalam penelitian ini adalah data memuat rute perjalanan pengiriman barang PT.
Jalur Nugraha Ekakurir (JNE) Medan.
Prosedur penelitian yang dilakukan untuk memecahkan permasalahan penelitian adalah sebagai berikut:
Melakukan studi literatur dengan mengumpulkan mengumpulkan teori Algoritma Nearest Neighbor dan Cheapest Insertion Heuristic yang mendukung pembahasan pada penelitian.
Melakukan pengumpulan data .
Pengumpulan data lokasi tujuan dan jarak rute perjalanan pengiriman barang PT.
Jalur Nugraha Ekakurir (JNE) Medan dengan menggunakan bantuan pencarian arah Google Map.
Memodelkan dan mengubah data dalam graf lengkap.
Pengelolahan data .
Mengambil data perjalanan dari salah satu seorang salesman dan menginput data lokasi antar alamat tujuan yang diperoleh kedalam tabel matriks jarak.
Menyelesaikan pencarian rute terpendek pengiriman barang PT.
Jalur Nugraha Ekakurir (JNE) Medan dari data jarak antar lokasi tujuan tersebut menggunakan Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling Salesman Problem Algoritma Nearest Neighbor dan Cheapest Insertion Heuristic serta melakukan pemeriksaan menggunakan aplikasi WINQSB.
Menentukan keefektifan perbandingan algoritma Nearest Neighbor dan Cheapest Insertion Heuristic menyelesaikan pencarian rute terpendek pengiriman barang PT.
Jalur Nugraha Ekakurir (JNE) Medan .
Menarik Kesimpulan.
HASIL DAN PEMBAHASAN
Perbandingan Algoritma Nearest Neighbor dengan algoritma Cheapest Insertion Berdasarkan langkah-langkah yang telah ditentukan untuk menentuk rute terpendek dengan menggunakan algoritma Nearest Neighbor dan Cheapest Insertion Heuristic terdapat perbedaan diantara keduanya yaitu :
Pada algoritma Nearest Neighbor langkah awal yang dilakukan yaitu mengambil vertex atau jarak terkecil ketujuan tanpa memperhatikan yang lain.
Pada algoritma Nearest Neighbor dalam mencari rute terpendek juga sangat cepat dan lebih Pada algoritma Cheapest Insertion Heuristic langkah awal yang dilakukan yaitu membuat hubungan subtour antara 2 titik, yang dimaksud subtour adalah perjalanan dari titik pertama dan berakhir di titik akhir.
Kemudian membuat subtour baru yang belum masuk dan menyisipkan titik-titik sehingga semua titik masuk kedalam Dari perhitungan pencarian rute terpendek algoritma Nearest Neighbor memiliki totak jarak yang terkecil dengan total jarak 34,3 km sedangkan algoritma Cheapest Insertion Heuristic 35,85 km.
Pemeriksaan Traveling Salesman Problem Menggunakan Software WINQSB Masalah perhitungan Traveling Salesman Problem dalam mencari rute terpendek Melibatkan dengan titik.
yang banyak.
Untuk menghindari kesalahan-kesalahan yang terjadi akibat human eror, diperlukan keterlibatan komputer dalam upaya pemeriksaan persoalan rute terpendek.
Software QSB (Quantity System for busines.
atau umumnya juga dikenal dengan nama WINQSB (QSB yang berjalan pada sistem operasi Window.
merupakan software yang mengandung algoritma problem solving untuk riset operasi .
perational researc.
dan untuk ilmu manajemen.
WINQSB sendiri terdapat beberapa modul yang dapat digunakan untuk menyelesaikan masalah-masalah operation riset dan ilmu manajemen seperti analisis JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 238-247 Sampling.
Agregat dalam sistem Produksi.
Model Jaringan Analisis Keputusan.
Pemrograman dinamis, goal programming.
Tata letak fasilitas, peramalan permintaan.
Sistem inventory.
Penjadwalan kerja.
Pemrograman Linier dan Integer.
Pernencanaan kebutuhan material (MRP),Proses Markov, dan teori antrian.
Pada penelitian ini software WINQSB digunakan untuk menyelesaikan model jaringan pada persoalan Traveling Salesman Problem.
Langlah-langkah Pencarian Traveling Salesman Problem pada Software WINQSB Membuka software WINQSB dan memilih Network Modeling Gambar 1.
Membuka tampilan WINQSB Memilih problem yang akan diselesaikan yaitu Traveling Salesman Problem.
Kemudian memilih jenis data TSP simetris atau tidak dan membuat jumlah vertex yang akan dicari pada tabel matriks jarak.
Gambar 2.
Tampilan Network Modeling WINQSB Kemudian mengisi jarak pada tabel matriks jarak , lalu memilih menu Solve and Analyze dan memilih algoritma yang digunakan untuk menyelesaikan persoalan Traveling Salesman Problem.
Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling Salesman Problem Gambar 3.
Tampilan algoritma penyelesaian Hasil pemeriksaan algoritma Nearest Neighbor Gambar 4.
Hasil pemeriksaan algoritma Nearest Neighbor Hasil pencarian algoritma Nearest Neighbor dengan jarak terpendek dengan 30Km.
Hasil pemeriksaan algoritma Cheapest Insertion Heuristic Gambar 5.
Hasil pemeriksaan algoritma Cheapest Insertion Heuristic Hasil pencarian algoritma Cheapest Insertion Heuristic dengan jarak terpendek 85Km.
JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 238-247
KESIMPULAN
Berdasarkan pembahasan mengenai perbandingan Algoritma Nearest Neighbor dan algoritma Cheapest Insertion untuk mengatasi Travelling Salesman Problem (TSP) dalam hal pencarian jarak pada rute pengiriman barang dan juga menggunakan bantuan software WINQSB, dapat diambil kesimpulan sebagai berikut.
Berdasarkan solusi optimum yang diperoleh dengan menggunakan algoritma Cheapest Insertion sebesar 35,85 km dan algoritma Nearest Neighbor sebesar 34,3 km diperoleh panjang rute yang lebih pendek dari panjang sirkuit yang dihasilkan algoritma Cheapest Insertion sebesar 35,85 km.
Hal ini menunjukkan bahwa algoritma Nearest Neighbor lebih efektif dalam mencari jarak traveling untuk rute pengiriman barang di PT.
Jalur Nugraha Ekakurir (JNE) Medan.
rute terpendek yang dihasilkan pada proses pengiriman barang menggunakan algoritma Nearest Neighbor melalui JNE.
Kantor gudang JNE Ae Jalan Ir.
Juanda - Jalan Walikota - Jalan Uskup Agung - Jalan Masdulhak - Jalan Slamet Riyadi - Jalan KH Agus Salim - Jalan Cut Nyak Dien - Jalan Jenderal Sudirman - Jalan Letjen Suprapto - Jalan Brigjend Katamso - Jalan Pemuda - Jalan KH.
Zainul Arifin - Jalan Kediri - Jalan Muara Takus - Jalan Teuku Cik Ditiro - Jalan Pangeran Diponegoro - Jalan Teuku Daud - Jalan R.
Kartini - Jalan Cut Mutia - lalu kembali kekantor gudang JNE dengan jarak minimum 34,3 Km dalam sekali tempuh.
Hasil perhitungan manual algoritma Cheapest Insertion Heuristic dan algoritma Nearest Neighbor sama dengan hasil pemeriksaan yang dilakukan oleh software WINQSB.
SARAN