Optimization of LPG Gas Distribution Routes with a Combination of the Saving Matrix Method and Nearest Neighbor

Andi Amin Amirul Mukminin; Billy  Hendrik; Rini  Sovia

doi:10.35134/komtekinfo.v12i4.656

Authors

Andi Amin Amirul Mukminin Universitas Ibnu Sina
Billy Hendrik Universitas Putra Indonesia YPTK Padang
Rini Sovia Universitas Putra Indonesia YPTK Padang

DOI:

https://doi.org/10.35134/komtekinfo.v12i4.656

Keywords:

Distribution, LPG, Route Optimization, , Saving Matrix, Nearest Neighbour

Abstract

Distribution is an important process in economic activities, which involves the delivery of goods or products from producers to end consumers. Efficiency in the distribution system highly depends on the selection of optimal routes, which can affect costs, time, and the quality of service provided. PT Amartha Anugrah Mandiri, which operates in the distribution of 3 kg LPG, faces significant challenges in terms of inefficient distribution route selection, limited fleet capacity, and unstructured variations in LPG demand. The distribution routes currently used do not consider the aspects of distance, time, and cost efficiency, resulting in the wastage of resources such as fuel and time. This research aims to optimize LPG distribution routes. The methods used in this study are the Saving Matrix and Nearest Neighbor. The Saving Matrix method is used to reduce distribution distance and costs by combining existing delivery routes, while the Nearest Neighbor is applied to determine the order of visits to the nearest bases gradually. Both methods are designed to produce distribution routes that are efficient in terms of time, distance, and cost, as well as to maximize the use of the existing fleet. The data in this study were obtained thru direct observation at PT. Amartha Anugrah Mandiri. The data collected included base locations, LPG demand, vehicle capacity, and operational costs. There are 22 bases served with a total delivery reaching 1120 LPG 3 kg cylinders spread across various sub-districts of Batam City. Deliveries are carried out using trucks with a maximum capacity of 560 cylinders, so in one day, distribution requires more than one trip. Using this data, the distance matrix and savings matrix were calculated to design a more efficient distribution system. The research results show that the application of these two methods successfully reduced the total distance traveled, delivery time, and operational costs significantly, as well as improved the efficiency of LPG distribution. This research is expected to contribute to the company so that the 3 kg LPG delivery process can run optimally.

References

S. Syahira, A. Nailalmuna, N. Febriani Siti Awaliyyah, N. Putri, B. Oktavia, and K. Aziz Husyairi, “Analisis Saluran Distribusi Pepaya Calina di Kabupaten Bogor (Studi Kasus: Roemah Buah KN Jaya, Rancabungur, Jawa Barat),” EKOMA : Jurnal Ekonomi, vol. 4, no. 1, 2024.

A. Munandar, “Evaluasi Kebijakan Penyaluran LPG 3 Kg: Efektivitas Subsidi Rumah Tangga Miskin vs Penggunaan Industri,” vol. 5, no. 4, p. 2025, 2025, doi: 10.38035/jihhp.v5i4.

Geraldo, Heni Rohaeni, and Indah Rizki Maulia, “Penentuan Lokasi Gudang Baru Dan Optimasi Rute Distribusi Untuk Meminimalisir Biaya Distribusi Pada Pt Xyz,” 2025.

A. Ahmad, M. Dahlan, A. Pawennari, and K. Naja, “Penentuan Jalur Distribusi Telur Ayam Menggunakan Metode Savings Matrix,” Universitas Muslim Indonesia Jl. Urip Sumoharjo No.km, vol. 11, no. 1, p. 455696, 2025.

F. Puji Lestari and S. Muhimatul Khoiroh, “Penentuan Rute Distribusi Pada Perusahaan Distributor Multi Product dengan Pendekatan Nearest Neighbor (Studi Kasus : PT. XYZ Depo Blitar),” vol. X, no. 1, 2025.

D. , Y. A. , G. W. , & Asriani. Herdhiansyah, “Optimasi penentuan rute distribusi beras komersial Bulog menggunakan metode branch and bound dengan bantuan software lingo,” 2023, doi: https://doi.org/10.21107/agrointek.v17i2.14514.

K. A. Maulana and A. Emaputra, “Penentuan Jalur Distribusi Gas LPG dengan Metode Savings Matrix dan Nearest Neighbor pada PT. XYZ,” Jurnal Rekayasa Industri (JRI), vol. 2022, 2022.

F. , N. I. , & D. S. Pulansari, “Determining the Shortest Route of Distribution to Reduce Environmental Emissions Using Saving Matrix and Nearest Neighbor Methods,” Galaxy Science, Nov. 2021. doi: 10.11594/nstp.2021.1435.

F. Armanda, R. F. Sari, and M. Dare Garba, “Numerical: Jurnal Matematika dan Pendidikan Matematika Optimization of Liquid Petroleum Gas (LPG) Cylinder Distribution Route with the Saving Matrix Method,” vol. 7, no. 1, 2023, doi: 10.25217/numerical.v7i1.

T. Risa Damayanti, A. Lita Kusumaningrum, Y. Dwi Susanty, and S. Susilawati, “Route Optimization Using Saving Matrix Method-A Case Study at Public Logistics Company in Indonesia,” 2020.

P. H. Kasih and Y. Maulidina, “Penentuan Rute Pengiriman untuk Meminimasi Jarak Tempuh Transportasi menggunakan Metode Saving Matrix,” Jurnal INTECH Teknik Industri Universitas Serang Raya, vol. 9, no. 1, pp. 53–62, Jun. 2023, doi: 10.30656/intech.v9i1.5680.

Aditia Rahmana and Suseno, “Usulan Rute Distribusi Terpendek Menggunakan Metode Saving Matrix Untuk Minimasi Jarak Dan Biaya Distribusi,” Jurnal Ilmiah Research And Development Student, vol. 3, no. 1, pp. 72–84, Dec. 2024, doi: 10.59024/jis.v3i1.1048.

F. D. Nasution, A. Momon, and R. Fitriani, “Penentuan Rute Distribusi Pallet Mesh Menggunakan Metode Saving Matrix (Studi Kasus : Pt. Mmm),” Jurnal Manajemen Industri dan Logistik, vol. 5, no. 1, pp. 1–9, 2021, doi: 10.30988/jmil.v5i1.542.

S. Martono and H. L. H. S. Warnars, “Penentuan Rute Pengiriman Barang Dengan Metode Nearest Neighbor,” PETIR, vol. 13, no. 1, pp. 44–57, Mar. 2020, doi: 10.33322/petir.v13i1.869.

U. Novalia Harahap and Y. S. Daulay, “Penentuan Rute Distribusi Menggunakan Metode Saving Matrix untuk Meminimalkan Biaya Transportasi pada UMKM Gerai Kimia di Kec. Namorambe,” 2024.

A. Andriyanto and D. Achmad Falevi, “Penentuan Rute Distribusi Menggunakan Metode Saving Matrix Untuk Meningkatkan Load Factor Di Pt Pos Indonesia Mail Processing Centre Bandung 40400,” Jurnal Logistik Bisnis, vol. 14, no. 1, 2024, [Online]. Available: https://ejurnal.ulbi.ac.id/index.php/logistik/

M. C. Sugiono, “Model vehicle routing problem untuk penentuan rute distribusi unit sepeda motor dengan metode saving matrix,” Journal Industrial Servicess, vol. 7, no. 2, p. 230, Mar. 2022, doi: 10.36055/jiss.v7i2.14018.

S. Lestari Mahmud, N. Achmad, R. Malango, and J. Matematika, “Penentuan Rute Pendistribusian Gas Lpg 3 Kg Menggunakan Metode Saving Matriks (studi kasus: Kabupaten Bolaang Mongondow Selatan),” J. Ris. & Ap. Mat, vol. 06, no. 01, pp. 40–62, 2022.

N. A. F. P. , Adam, I. P. , T. A. , Sari, and W. Sutopo, “Determination of Routes for Daily Newspaper Product Distribution with Saving Matrix Methods,” IOP Conf Ser Mater Sci Eng, vol. 943, no. 1, Nov. 2021, doi: 10.1088/1757-899X/943/1/012040.

S. Fajar Mahmud, H. Rahman, P. Studi Teknik Industri, S. Tinggi Teknologi Dumai Jl Utama Karya, and B. Batrem, “Optimasi Rute Transportasi dengan Pendekatan Saving Matrix dan Nearest Neighbor,” vol. 17, no. 2, p. 2024, 2024.