Matematika Sains Volume 2 Nomor 2 Tahun 2024
ALGORITMA PRIM DALAM PENENTUAN LINTASAN
TERPENDEK DAN LINTASAN TERCEPAT PADA
PENDISTRIBUSIAN BARANG PT.
SUMBER ALFARIA TRIJAYA
TBK PEKANBARU
e-issn: 2987-2979 DOI: https://doi.
org/10.
34005/ms.
Hana Rezki Yana .
Depriwana Rahmi2 .
Annisa Kurniati.
Suci Yuniati .
Fakultas Tarbiyah dan Keguruan.
UIN Sultan Syarif Kasim email: annisah.
kurniati@uin-suska.
ABSTRAK
Penelitian ini meneliti tentang penentuan lintasan terpendek dan lintasan tercepat dalam pendistribusian barang PT.
Sumber Alfaria Trijaya Tbk Pekanbaru dengan menggunakan Algoritma Prim.
Data dan informasi yang mencakup semua lintasan yang menghubungkan alfamart-alfamart diperoleh melalui aplikasi google maps.
Data mini digunakan untuk membangun model awal berupa graf berbobot terhubung.
Dengan menggunakan Algoritma Prim, dilakukan optimalisasi model lintasan, sehingga diperoleh minimum spanning tree.
Berdasarkan minimum spanning tree ini diperoleh lintasan terpendek dan lintasan tercepat dari PT.
Sumber Alfaria Trijaya berturut-turut 25,5 km dan 50 menit.
Kata Kunci: Algoritma Prim.
Lintasan Terpendek.
Lintasan Tercepat ABSTRACT This study examines the determination of the shortest path and the fastest path in the distribution of goods PT Sumber Alfaria Trijaya Tbk Pekanbaru by using Prim's Algorithm.
Data and information that includes all paths connecting alfamart-alfamart are obtained through the google maps application.
Mini data is used to build an initial model in the form of a connected weighted graph.
By using Prim's Algorithm, optimization of the path model is carried out, so that the minimum spanning tree is obtained.
Based on this minimum spanning tree, the shortest path and the fastest path from PT.
Sumber Alfaria Trijaya are 25.
5 km and 50 minutes, respectively.
Keyword: Prim's Algorithm.
Shortest Path.
Fastest Path
PENDAHULUAN
Pendistribusian barang adalah kegiatan yang sangat penting dalam bisnis, terutama dalam industri logistik.
Dalam beberapa tahun terakhir, perusahaan-perusahaan telah mengalami kesulitan dalam mengelola distribusi barang secara efisien dan efektif, terutama dalam menghadapi keterlambatan pendistribusian dan biaya yang tinggi.
Salah satu cara untuk mengatasi masalah ini adalah dengan menggunakan algoritma yang dapat membantu dalam menentukan lintasan terpendek dan lintasan tercepat dalam pendistribusian barang.
(Lusiani et , 2.
Matematika Sains Volume 2 Nomor 2 Tahun 2024 Teori Graf adalah metode yang digunakan untuk menyelesaikan permasalahan diskrit yang kompleks, seperti merepresentasikan objek-objek diskrit dan hubungan antara objek-objek Salah satu contoh penggunaan teori graf yang paling umum adalah mencari rute tujuan pada peta.
(Sari & Musthofa, 2.
Dengan menggunakan teori graf, hasil yang didapatkan dapat memiliki keuntungan tertentu, seperti rute dengan waktu tempuh yang tercepat, rute dengan jarak terpendek, rute dengan biaya yang paling murah, rute dengan tingkat efisiensi yang paling tinggi, dan lain-lain.
(Komputer et al.
, 2.
Salah satu teori graf yang dapat diimplementasikan dalam mencari rute tercepat dan terpendek adalah teori graf pada Algoritma Prim.
Algoritma prim adalah salah satu algoritma yang sangat efektif dalam menentukan lintasan terpendek dan lintasan tercepat dalam jaringan transportasi.
Algoritma ini bekerja dengan cara mencari lintasan terpendek antara dua titik dalam jaringan yang memiliki bobot minimum.
Dalam konteks pendistribusian barang, algoritma ini dapat membantu dalam menentukan rute yang paling efisien untuk mengirimkan barang dari satu tempat ke tempat lain, sehingga biaya dan waktu yang dibutuhkan dapat dikurangi.
(Syamsuddin MasAoud, 2.
Dalam penelitian ini, penulis akan membahas penerapan Algoritma Prim dalam penentuan lintasan terpendek dan lintasan tercepat pada pendistribusian barang.
Pada penelitian ini penulis menggunakan bantuan aplikasi google maps untuk menentukan jarak dan waktu Penelitian ini akan menggunakan contoh kasus dari perusahaan PT.
Sumber Alfaria Trijaya TBK Pekanbaru yang melakukan pendistribusian barang ke 6 titik alfamart di Pekanbaru.
Dengan menggunakan Algoritma Prim, kita dapat menentukan lintasan terpendek dan lintasan tercepat yang dapat membantu perusahaan tersebut dalam mengurangi biaya dan waktu yang dibutuhkan dalam pendistribusian barang.
Penelitian dalam permasalahan jaringan yang memuat lintasan dengan bobot minimum dengan menggunakan Algoritma Prim telah banyak dilakukan diantaranya adalah.
Algoritma Prim dalam Penentuan Lintasan Terpendek dan Lintasan Tercepat pada Pendistribusian Logistik Bulog Jawa Barat(Lusiani et al.
, 2.
Penelitian terbaru pada tahun 2024 dengan Menggunakan Algoritma Prim Adalah Penentuan Rute Pendistribusian Gas Lpg Menggunakan Algoritma Prim Dengan Optimalisasi Melalui Pergantian Sisi(Syamsuddin MasAoud, 2.
Secara teoritis.
Algoritma Prim juga telah dibandingkan dengan algoritma kruskal dalam penentuan lokasi pembangunan jalan baru(Minarwati, 2.
Pada artikel ini akan ditentukan lintasan terpendek dan lintasan tercepat pada pendistribusian barang PT.
Sumber Alfaria Trijaya Tbk Pekanbaru.
KAJIAN TEORI
1 Teori Graph Teori graf adalah cabang matematika dan ilmu komputer yang mempelajari sifat-sifat graf atau grafik.
Graf adalah sekumpulan objek terstruktur di mana beberapa pasangan objek mempunyai hubungan atau keterkaitan.
Teori graf ini pertama kali diperkenalkan oleh Leonhard Euler dalam sebuah artikel ilmiah yang berjudul AuSeven Bridges of KonigsbergAy yang membahas adanya struktur yang saat ini dikenal sebagai sirkuit Euler pada graf keterhubungan daratan kota Konigsberg dan pulau kecil di tengah sungai Pregel yang dihubungkan oleh tujuh buah jembatan.
Teori graf memiliki aplikasi yang luas di berbagai bidang, termasuk ilmu komputer, kimia teoritik, transportasi, dan lain-lain.
Salah satu contoh Matematika Sains Volume 2 Nomor 2 Tahun 2024 aplikasi utama teori graf adalah dalam optimisasi jaringan komunikasi.
Dalam jaringan komunikasi yang kompleks, terdapat banyak simpul atau node yang saling terhubung.
Dengan menggunakan teori graf, dapat dibangun model graf yang merepresentasikan jaringan tersebut, di mana simpul-simpul graf melambangkan node dan sisi-sisi graf melambangkan koneksi antar-node.
Dengan memanfaatkan teori graf, kita dapat mengoptimalkan pemilihan rute komunikasi antara simpul-simpul tersebut.
(Buhaera et al.
, 2.
2 Aplikasi Teori Graph Graf dapat digunakan dalam berbagai situasi untuk menggambarkan hubungan antar elemen atau variabel dalam data.
Graf dapat digunakan dalam analisis jaringan sosial untuk menggambarkan hubungan antar orang, baik dalam bentuk graf terarah yang menunjukkan pertemanan maupun graf tidak terarah yang menunjukkan kekerabatan.
Graf juga digunakan dalam analisis sistem transportasi untuk menggambarkan hubungan antar kota, baik dalam bentuk graf terarah yang menunjukkan arah perjalanan maupun graf tidak terarah yang menunjukkan kota-kota yang dapat dicapai dengan berbagai cara transportasi.
Selain itu, graf digunakan dalam analisis aliran air untuk menggambarkan hubungan antar daerah dalam suatu sistem irigasi, baik dalam bentuk graf terarah yang menunjukkan aliran air maupun graf tidak terarah yang menunjukkan daerah-daerah yang saling terhubung.
Graf juga digunakan dalam analisis jaringan elektronik untuk menggambarkan hubungan antar perangkat, baik dalam bentuk graf terarah yang menunjukkan aliran sinyal maupun graf tidak terarah yang menunjukkan perangkat-perangkat yang saling terhubung.
Graf dapat membantu kita memahami dan menganalisis data dengan lebih mudah dan efektif, serta digunakan dalam berbagai aplikasi lainnya seperti analisis jaringan telekomunikasi, jaringan pekerjaan, dan jaringan makanan.
(Sanjaya, 2.
3 Jalur Terpendek (Shortest Pat.
Jalur terpendek .
hortest pat.
adalah rute yang paling efisien yang dapat ditemukan menggunakan graf.
Rute ini biasanya ditentukan oleh biaya perjalanan total yang paling rendah.
Dalam konteks graf, setiap garis yang menghubungkan simpul titik memiliki bobot yang mewakili biaya perjalanan.
Jika total biaya perjalanan dari garis yang dilalui dihitung, maka rute yang memiliki biaya total minimal adalah jalur Berikut adalah beberapa algoritma yang dapat digunakan untuk menyelesaikan masalah jalur terpendek:(Ramadhan et al.
, 2.
Algoritma Dijkstra: Algoritma ini menggunakan prioritas untuk memilih simpul berikutnya yang akan diunjur.
Prioritas ditentukan oleh biaya perjalanan terpendek yang telah ditemukan hingga simpul tersebut.
Algoritma Bellman-Ford: Algoritma ini mirip dengan Dijkstra, tetapi dapat digunakan untuk graf yang memiliki siklus biaya negatif.
Algoritma Floyd-Warshall: Algoritma ini dapat digunakan untuk graf yang memiliki lebih dari dua simpul.
Algoritma ini mencari jalur terpendek antara setiap pasangan simpul.
Algoritma A* (A-Sta.
: Algoritma ini menggunakan prioritas yang lebih akurat Matematika Sains Volume 2 Nomor 2 Tahun 2024 daripada Dijkstra, dengan mempertimbangkan biaya perjalanan dan jarak antara 4 Algoritma Prim Algoritma Prim adalah sebuah algoritme dalam teori graf yang digunakan untuk mencari pohon rentang minimum pada sebuah graf berbobot yang saling terhubung.
Algoritme ini bekerja dengan cara membangun suatu pohon pembangun minimum yang mengandung node dan edge, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan.
Algoritma Prim memfokuskan pada pemilihan bobot minimum berdasarkan simpul yang Karena tidak memerlukan pengurutan terlebih dahulu, algoritma ini cocok untuk pohon dengan jumlah simpul yang besar.
Algoritma Prim akan selalu berhasil menemukan pohon merentang minimum, namun pohon merentang yang dihasilkan tidak selalu (Syahputra, 2.
METODE PENELITIAN Model yang akan dikaji merupakan model pada analisa kasus penentuan lintasan terpendek dan lintasan tercepat pada pendistribusian barang, yaitu pendistribusian barang yang dilakukan oleh PT.
Sumber Alfaria Trijaya Pekanbaru dari gudang menuju ke beberapa retailer alfamart.
Pendistribusian barang ini dimulai dari PT.
Sumber Alfaria Trijaya yang berlokasi di Jl.
Air Hitam menuju ke 9 alfamart yaitu Alfamart Melati.
Alfamart Garuda Sakti km 3,5.
Alfamart Soebrantas 4.
Alfamart Soebrantas 5.
Alfamart Tuanku Tambusai 3 dan titik terakhir Alfamart Cempaka.
Model awal yang dibangun pada algoritma ini adalah graf berbobot terhubung, dengan bobot berupa jarak tempuh dan waktu tempuh.
Untuk penentuan lintasan terpendek digunakan bobot berupa jarak tempuh, sedangkan untuk penentuan lintasan tercepat digunakan bobot berupa waktu tempuh.
Dengan demikian, dari model awal tersebut diperoleh pohon merentang minimum setelah dijalankan langkah-langkah Algoritma Prim.
Adapun langkah-langkah penelitian yang dilakukan sebagai berikut:
Melakukan pengambilan data menggunakan google maps untuk mencari jarak antara masing-masing lokasi alfamart yang akan dilakukan pengantaran barang dari PT.
Sumber Alfaria Trijaya TBK Pekanbaru Melakukan pembentukan Graf awal dari data peta di google maps tersebut.
Melakukan pencarian Minimum Spanning Tree dari Graf yang diperoleh dengan menggunakan Algoritma Prim.
Melakukan perbandingan hasil antara hasil pencarian rute terpendek yang telah didaoatkan dengan hasil awal pada data di google maps.
Didapatkan perbandingan antara jumlah bobot awal graf sebelum dan sesudah dilakukan pencarian rute terpendek, kemudian dilakukan penarikan Berikut adalah bagan prosedur tahapan dalam penelitian ini :
Matematika Sains Volume 2 Nomor 2 Tahun 2024 Mulai Identifikasi Masalah dan Perumusan Masalah Melakukan Studi Literature Koleksi Data dari Google Maps Algoritma Prim Hasil dan Kesimpulan Selesai HASIL DAN PEMBAHASAN Terdapat beberapa jalan alternatif yang dapat dilalui menuju titik terakhir pendistribusian barang yaitu Alfamart Cemapaka ditunjukkan pada tabel berikut:
Tabel 4.
1 Data Bobot Jarak dari gudang Alfamart menuju titik terakhir Nama Tempat Simbol Jarak .
PT.
Sumber Alfaria Trijaya Alfamart Melati Alfamart Garuda Sakti Km 3,5 Alfamart Soebrantas 4 Alfamart Soebrantas 5 Alfamart Tuanku Tambusai 3 Alfamart Cempaka Dari tabel 4.
1 diatas, rincian titik pendistribusian barang alfamart dapat dilihat pada gambar dalam Google Maps sebagai berikut :
Matematika Sains Volume 2 Nomor 2 Tahun 2024 Gambar 4.
Peta Wilayah Kota Pekanbaru Dari gambar 4.
1 diatas dapat diinterpretasikan ke dalam bentuk graf berbobot dengan asumsi bahwa A sebagai titik awal dan G sebagai titik akhir.
Tiap bobot telah diberikan simbol dan warna yang berbeda untuk memudahkan penamaan dari graf tersebut.
Sesuai dengan gambar 1 diatas dapat diintrepetasikan kedalam graf sebagai berikut:
Gambar 4.
Graf Berbobot Dalam Jarak Tempuh Dari Gambar 4.
2 diatas sudah ditentukan titik awalnya yaitu titik A dan penulis memberikan warna ungu muda untuk titik A sebagai titik awal.
Kemudian dari gambar 2 diatas dapat dirincikan kedalam tabel dibawah ini agar mudah dipahami jarak antar tiap titik, dapat dilihat pada tabel berikut ini :
Matematika Sains Volume 2 Nomor 2 Tahun 2024 Tabel 4.
2 Bobot dalam Jarak dan Waktu Tempuh
Sisi
(A,B)
(A,C)
(A,D)
(A,F)
(A,G)
(B,C)
(B,D)
(B.
(B,F)
(B,G)
(C,D)
(D,E)
(D,F)
(D,G)
(E,F)
(F,G)
Bobot Tabel 4.
2 menunjukkan bobot dari tiap sisi, yaitu jarak tempuh dalam satuan kilometer dan waktu tempuh dalam satuan menit dari satu daerah ke daerah lainnya Misalnya, sisi (A.
B)adalah sisi yang menghubungkan daerah A dan daerah B.
Jarak dan waktu tempuh dari daerah A ke daerah B .
tau sebalikny.
, berturut-turut 4,9 km dan 9 menit.
Selanjutnya setelah mengetahui jarak tempuh waktu tempuh dari tiap sisi maka penulis dapat menentukan jalur lintasan terpendek menuju titik G sebagai titik akhir.
Kemudian penulis menginterpretasikannya kedalam bentuk graf sebagai berikut :
Gambar 4.
Jalur terpendek dalam jarak tempuh Matematika Sains Volume 2 Nomor 2 Tahun 2024 Pada graf diatas titik awal adalah titik A yang diberi warna ungu, kemudian tentukan titik dengan jarak terpendek dari titik A yaitu titik C dengan jarak 2 km, kemudian titik A ke C diberikan warna ungu muda sebagai tanda titik yang sudah dilewati.
Kemudian titik B diposisikan sebagai titik selanjutnya dan tentukan jarak terpendek dari titik C ke titik lainnya.
Titik B merupakan titik dengan jarak terpendek yaitu 4 km.
Selanjutnya titik C ke B diberikan warna ungu muda sebagai tanda titik yang sudah dilewati.
Selanjutnya posisikan titik B sebagai titik selanjutnya, dan tentukan jarak terpendek dari titik B ke titik lainnya.
Titik D merupakan titik dengan jarak terpendek dengan jarak 4,8 km.
Kemudian titik B ke D diberikan warna ungu muda sebagai tanda titik yang sudah dilewati.
Langkah ini akan diteruskan hingga melalui semua titik satu kali hingga sampai di titik terakhir yaitu titik G.
Maka didapat alur perjalanan yakni dari A,C,B,D,E,F dan G.
Selanjutnya dapat kita visualisasikan dalam graf sebagai berikut:
Gambar 4.
4 Lintasan Teroendek dalam jarak tempuh Setelah didapatkan jarak terpendek dari tiap titik, maka penulis dapat menjumlahkan jarak terpendek dari titik tersebut berdasarkan informasi yang telah didapat kemudian disusun kedalam bentuk tabel dibawah ini:
Matematika Sains Volume 2 Nomor 2 Tahun 2024
Tabel 3 Bobot dalam jarak
Titik
(A,C)
(C,B)
Jarak .
(B,D) (D,E) (E,F) (F,G) Total Jarak Dari graf dan tabel diatas dapat dilihat bahwa lintasan terpendek yang didapatkan untuk menuju titik terakhir yaitu titik G adalah 25,5 km.
Selanjutnya penulis juga dapat mementukan lintasan tercepat dengan menggunakan langkah yang sama untuk menentukan lintasan terpendek yaitu sebagai berikut:
Gambar 4.
Jalur tercepat dalam waktu tempuh Pada graf diatas posisikan titik awal pada titik A, kemudian tentukan waktu yang minimum dari titik A ke titik lainnya.
Titik C merupakan titik dengan waktu yang minimum yaitu 2 Kemudian titik A ke C diberikan warna ungu muda untuk menandakan bahwa titik yang telah dilewati.
Selanjutnya posisikan titik C sebagai titik selanjutnya, dan tentukan jarak terpendek dari titik C ke titik lainnya.
Titik B merupakan titik dengan waktu minimum yaitu 6 menit.
Kemudian titik C ke B diberikan warna ungu muda sebagai tanda titik yang sudah dilewati.
Langkah ini akan diteruskan hingga melalui semua titik satu kali hingga sampai di titik terakhir yaitu titik G.
Maka didapat alur perjalanan yakni dari A,C,B,F,E,D dan G.
Selanjutnya dapat kita visualisasikan dalam graf sebagai berikut:
Matematika Sains Volume 2 Nomor 2 Tahun 2024 Gambar 4.
6 Jalur Tecepat dalam Waktu Tempuh Setelah didapatkan waktu minimum dari tiap titik, maka penulis dapat menjumlahkan waktu minimum dari titik tersebut berdasarkan informasi yang telah didapat kemudian disusun kedalam bentuk tabel dibawah ini:
Tabel 4.
4 Bobot dalam waktu tempuh
Titik
(A,C)
(C,B)
(B,F)
(D,E)
(E,F)
(F,G)
Total Tabel 4.
4 menunjukkan bobot dari pohon merentang minimum waktu tempuh yaitu 50 menit.
KESIMPULAN
Berdasarkan graf pada gambar 4.
4 dan 4.
6 diperoleh lintasan terpendek dengan bobot jarak tempuh melalui sisi sisi (A,C) , (C,B) , (B,D) , (D,E) , (E.
F) , (F,G), sedangkan lintasan tercepat yaitu lintasan tercepat dengan bobot waktu tempuh melalui sisi-sisi (A,C), (C,B) , (B,F) , (D,E) , (E,F) .
(F,G).
Dengan demikian, lintasan terpendek dan lintasan tercepat dari titik A yaitu PT.
Sumber Alfaria Trijaya berturut turut 25,5 km dan 50 menit.
Lintasan terpendek yang diperoleh berjarak lebih pendek diabmndingkan lintasan terpendek yang ditunjukkan di aplikasi google maps yaitu 44,1 km.
Sementara, lintasan tercepat sesuai lintasan tercepat yang ditunjukkan di aplikasi google maps yaitu 1 jam 15 menit Matematika Sains Volume 2 Nomor 2 Tahun 2024
REFERENSI