Penentuan Rute Pendistribusian Gas LPG Menggunakan Algoritma Prim dengan Optimalisasi melalui Pergantian Sisi

Authors

  • Syamsuddin Mas'ud UNM

DOI:

https://doi.org/10.30605/proximal.v7i1.3063

Keywords:

Route, Prim Algorithm, Edge Exchange

Abstract

This research examines the determination of LPG gas distribution routes. The study is conducted on data collected by Elia Resita Ningrum in her research titled "Optimizing LPG Gas Distribution Routes Using the Floyd Warshall Algorithm and the Greedy Algorithm." This data is processed using different methods with the aim of obtaining better LPG gas distribution routes. The method to be used is the Prim algorithm, followed by route improvement through edge exchange in the graph. The Prim algorithm is used to obtain a minimum spanning tree. From this minimum spanning tree, one of the distribution routes is selected, namely v_1-v_2-v_3-v_4-v_8-v_4-v_10-v_11-v_10-v_4-v_5-v_6-v_7-v_9-v_12-v_13-v_14 with a total weight of 11.26. Route improvement is then carried out by exchanging edges in the graph, resulting in a new route, namely v_1-v_2-v_8-v_4-v_10-v_11-v_10-v_4-v_5-v_6-v_7-v_9-v_12-v_13-v_14 with a total weight of 10.91. This result is better than the result obtained by Elia Resita Ningrum with a total weight of 11.13. Based on the results obtained, for the case of LPG gas distribution by PT Petro Jaya Gas, the use of the Prim algorithm with route improvement through edge exchange produces better routes compared to the use of the Floyd Warshall Algorithm and the Greedy Algorithm conducted by Elia Resita Ningrum.

Keywords:      Route, Prim Algorithm, Edge Exchange.

Downloads

Download data is not yet available.

References

Alifiani, I., dkk. (2021). Solusi Optimal Pencarian Jalur Tercepat Menggunakan Algoritma Dijkstra untuk Mencari Lokasi Cafe di Bumiayu. Jurnal Derivat, v.8, n.2, p.140-148.

Applegate, D. L., dkk. (2006). The Traveling Salesman Problem, United Kingdom, Princeton University Press.

Arif, M. & Marbun, J. P. (2023). Pencarian Rute Terbaik Pendistribusian BBM dari Terminal BBM ke SPBU Wilayah Kota Medan Menggunakan Algoritma Dijkstra dengan Logika Fuzzy sebagai Penentu Bobot pada Graf. FARABI: Jurnal Matematika dan Pendidikan Matematika, v.6, n.1, p.10-19.

Balakrishnan, R. & Ranganathan, K. (2012). A Textbook of Graph Theory Second Edition, New York, Springer.

Bunaen, M. C., dkk. (2022). Penerapan Algoritma Dijkstra untuk Menentukan Rute Terpendek dari Pusat Kota Surabaya ke Tempat Bersejarah. Jurnal Teknologi Dan Sistem Informasi Bisnis, v.4, n.1, p.213-223.

Clark, J. & Holton, D. A. (1995). A First Look at Graph Theory. Singapur, World Scientific PubUshing Co. Pte. Ltd.

Fitriani, S., dkk. (2022). Penerapan Algoritma Bellman-Ford dalam Menentukan Rute Terpendek Objek Wisata Kabupaten Lampung Timur. Jurnal Siger Matematika, v.3, n.2, p.53-60.

Greco, F. (2008). Travelling Salesman Problem, Croatia, in-teh.

Lusiani, A., dkk. (2021). Algoritma Prim dalam Penentuan Lintasan Terpendek dan Lintasan Tercepat pada Pendistribusian Logistik Bulog Jawa Barat. The 12th Industrial Research Workshop and National Seminar Bandung-IRWNS 2021. Prosiding 673-677.

Nggufron, N., dkk. (2019). Pencarian Rute Terbaik Pemadam Kebakaran Kota Semarang Menggunakan Algoritma Dijkstra dengan Logika Fuzzy sebagai Penentu Bobot pada Graf. UNNES Journal of Mathematics, v.8, n.1, p.40-49.

Ningrum, E. R., dkk. (2023). Optimasi Rute Pendistribusian Gas Elpiji Menggunakan Algoritma Floyd Warshall dan Algoritma Greedy. Jurnal Ilmiah Matematika dan Terapan, v.20, n.1, p.1-14.

Rahmadi, D. & Sandariria, H. (2023). Penerapan Minimum Spanning Tree dalam Menentukan Rute Terpendek Distribusi Naskah Soal USBN di SMA Negeri se-Sleman. Basis : Jurnal Ilmiah Matematika, v.2, n.1, p.66-71.

Widianto, T., dkk. (2021). Optimalisasi Metode Weighted-Sum Dijkstra Algorithm untuk Menentukan Rute Terbaik yang Sesuai dengan Kebutuhan. Jurnal CoreIT, v.7, n.1, p.13-19.

Downloads

Published

2023-11-16

How to Cite

Syamsuddin Mas'ud. (2023). Penentuan Rute Pendistribusian Gas LPG Menggunakan Algoritma Prim dengan Optimalisasi melalui Pergantian Sisi. Proximal: Jurnal Penelitian Matematika Dan Pendidikan Matematika, 7(1), 9–17. https://doi.org/10.30605/proximal.v7i1.3063