Gas elpiji merupakan salah satu jenis bahan bakar yang memiliki penggunaan yang paling banyak di Indonesia dalam kegiatan memasak. Permintaan akan gas elpiji terus meningkat seiring dengan pertumbuhan populasi di Indonesia. Di antara wilayah-wilayah di Indonesia, Pulau Sumatera menjadi salah satu yang memiliki konsumsi gas elpiji yang signifikan, mencakup sekitar 20% dari total konsumsi nasional. Namun, terdapat permasalahan yang terkait dengan perencanaan aliran pola suplai gas elpiji di Pulau Sumatera, yang mengakibatkan terjadinya kelangkaan gas elpiji di wilayah tersebut. Oleh karena itu, diperlukan sebuah metode yang efektif untuk merencanakan aliran suplai gas elpiji dengan baik, guna memastikan ketersediaan yang memadai sesuai dengan permintaan yang ada dan menghindari terjadinya kelangkaan di masa yang akan datang. Penelitian ini akan mengadopsi metode minimum cost flow problem sebagai pendekatan dalam menyelesaikan permasalahan aliran pola suplai gas elpiji di Pulau Sumatera. Metode ini akan digunakan untuk mengoptimalkan jumlah aliran gas elpiji yang harus dialokasikan ke terminal depot dan SPBE yang terdapat di wilayah tersebut. Selain itu, metode ini juga memungkinkan peneliti untuk mengestimasi total biaya yang diperlukan untuk memenuhi permintaan gas elpiji. Pengolahan data dilakukan pada 1 terminal utama, 7 terminal depot, dan 50 SPBE. Implementasi pengembangan model menghasilkan jumlah aliran gas elpiji yang optimal dan mendapatkan penghematan sebesar Rp1.804.595.434 jika dibandingkan dengan kondisi saat ini.

---

Liquefied petroleum gas (LPG) represents one of the foremost types of fuel extensively utilized for cooking purposes in Indonesia. The demand for LPG continues to surge in tandem with the nation's burgeoning population. Among the various regions across Indonesia, Sumatra Island emerges as a notable consumer of LPG, accounting for approximately 20% of the overall national consumption. Regrettably, challenges associated with the planning of LPG supply distribution patterns on Sumatra Island have led to a scarcity of this essential resource in the region. Consequently, it becomes imperative to devise an efficacious methodology to meticulously plan the flow of LPG supply, ensuring its sufficient availability in line with prevailing demand while simultaneously averting any future scarcity. This research will adopt the minimum cost flow problem method as an approach to address the issues pertaining to the supply distribution patterns of LPG in Sumatra Island. This method will be employed to optimize the allocation of LPG flow quantities to the terminal depots and LPG filling stations (SPBE) within the region. Moreover, this method will enable researchers to estimate the total cost required to meet the demand for LPG. Data processing was conducted for 1 main terminal, 7 terminal depots, and 50 LPG filling stations (SPBE). The implementation of the developed model yielded an optimal quantity of LPG flow and resulted in cost savings amounting to Rp1,804,595,434 when compared to the current conditions.