Optimizing Kuring Tofu's Distribution Route in Salatiga and Semarang Using Prim's Algorithm

Jurnal Pendidikan Matematika (Kudus)
Vol 8, No 2 (2025): Jurnal Pendidikan Matematika (Kudus)

In product marketing, one of the important things to consider is the product distribution process. To optimize the distribution process, determining the shortest route is essential, which can be achieved by applying Prim's Algorithm. Prim's Algorithm is a method in graph theory used to find the minimum spanning tree on a connected weighted graph. The purpose of this study is to determine the shortest route from the Kuring Tofu Factory to marketing areas in Salatiga and Semarang using Prim’s Algorithm. This study was conducted by identifying routes using Google Maps and interviewing a staff member of the Kuring Tofu Factory. The data obtained was then processed using the principles of Prim's Algorithm. The interview revealed that product distribution covered 12 markets located in the Salatiga and Semarang areas. The resulting minimum spanning tree indicated a total distance of 175.5 km, with distance and time, respectively, being 175.5 km in 4 hours and 57 minutes. This distance is shorter than the initial total distribution route shown by Google Maps, which is 378.9 km with a travel time of 6 hours and 57 minutes. Therefore, the percentage of distance traveled saved is 53.7%, and the percentage of travel time saved is approximately 29%. These results demonstrate that the graph theory approach can improve distribution efficiency and save time. Therefore, Prim's Algorithm can be used as one solution to determine the shortest and fastest route from one place to another. Dalam pemasaran produk, salah satu hal penting yang perlu diperhatikan yaitu proses pendistribusian produk tersebut. Untuk mengoptimalkan proses pendistribusian, maka diperlukan rute terpendek yang dapat dilakukan dengan mengaplikasikan Algoritma Prim. Algoritma Prim adalah metode dalam teori graf yang digunakan untuk menemukan pohon rentang minimum (minimum spanning tree) pada graf berbobot yang saling terhubung. Tujuan dari penelitian ini yaitu menentukan rute terpendek untuk pendistribusian produk Pabrik Tahu Kuring ke daerah pemasaran yang berada di daerah Salatiga dan Semarang dengan menggunakan Algoritma Prim. Penelitian ini dilakukan dengan mencari rute menggunakan Google Maps dan wawancara terhadap salah satu pegawai di pabrik tersebut. Kemudian data yang diperoleh diolah menggunakan prinsip Algoritma Prim. Dalam wawancara, pendistribusian produk dilakukan di 12 pasar yang berada di daerah Salatiga dan Semarang. Penelitian ini memperoleh hasil bobot dari pohon perentang minimum dengan jarak tempuh dan waktu secara berturut-turut, yaitu 175,5 km dalam waktu 4 jam lebih 57 menit. Jarak tersebut lebih dekat dibandingkan dengan total lintasan pendistribusian awal yang ditunjukkan oleh Google Maps yaitu jaraknya 378,9 km dengan waktu tempuh 6 jam lebih 57 menit. Sehingga diperoleh persentase penghematan jarak tempuh yaitu 53,7% dan persentase waktu tempuh sekitar 29%. Hasil ini membuktikan pendekatan teori graf dapat meningkatkan efisiensi distribusi dan menghemat waktu. Oleh karena itu, Algoritma Prim dapat dijadikan salah satu solusi untuk menentukan rute terpendek dan tercepat dari suatu tempat ke tempat lainnya.Optimizing Kuring Tofu's Distribution Route in Salatiga and Semarang Using Prim's Algorithm