OPTIMASI RUTE DISTRIBUSI GAS LPG DENGAN METODE SAVING MATRIX & ALGORITMA NEAREST NEIGHBOUR (Studi Kasus pada PT. REZKI BAHARI PAJUKUKANG) = OPTIMIZATION OF LPG GAS DISTRIBUTION ROUTES USING THE SAVING MATRIX METHOD & NEAREST NEIGHBOR ALGORITHM (CASE STUDY AT PT. REZKI BAHARI PAJUKUKANG)

Latar belakang. PT. Rezki Bahari Pajukukang merupakan salah satu perusahaan yang aktif dalam mendistribusikan gas LPG 3 kg di Kabupaten Tanah Bumbu Provinsi Kalimantan Selatan. Dalam melakukan pendistribusian gas LPG, proses pengiriman yang dilakukan masih belum efisien. Salah satu penyebab utamanya adalah ketergantungan pada intuisi dan pengalaman sopir dalam menentukan jalur distribusi, tanpa adanya rancangan rute yang sistematis. Akibatnya, sering terjadi jarak tempuh yang lebih panjang dari seharusnya serta peningkatan biaya operasional. Tujuan. Penelitian ini bertujuan menentukan rute distribusi yang lebih optimal dengan metode saving matrix dan algoritma nearest neighbour dengan harapan dapat menurunkan jarak, waktu tempuh dan biaya distribusi yang dikeluarkan. Metode. Adapun metode yang digunakan yaitu saving matrix dan algoritma nearest neighbour. Hasil. Hasil analisis menunjukkan bahwa rute awal perusahaan selama bulan Juli 2025 memiliki total jarak tempuh 1330,2 km dengan waktu 2076 menit dan biaya distribusi sebesar Rp6.718.635. Setelah dilakukan optimasi, metode Saving Matrix selama bulan Juli 2025 menghasilkan jarak tempuh 1005 km dengan waktu 1647 menit dan biaya sebesar Rp6.103.924, sedangkan algoritma Nearest Neighbour selama bulan Juli 2025 menghasilkan jarak tempuh 1067,1 km dengan waktu 1719 menit dan biaya sebesar Rp6.221.569. Dengan demikian, metode Saving Matrix terbukti lebih efisien karena mampu menghemat jarak 24,44%, waktu 20,66%, dan biaya distribusi sebesar 9,14% dibandingkan rute awal. Penelitian ini menyimpulkan bahwa penerapan metode heuristik, khususnya Saving Matrix dapat meningkatkan efisiensi distribusi LPG sekaligus menjadi acuan praktis bagi perusahaan dalam merancang strategi distribusi yang efektif dan hemat biaya.