Lukito, Louis Cristian Samuel (2026) Pemodelan Optimasi Rute Berbasis Cluster Menggunakan Mixed-Integer Linear Programming di PT Gagas Energi Indonesia. Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 5002221004-undergraduate-Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
5002221004-undergraduate-Thesis.pdf - Accepted Version Restricted to Repository staff only Download (7MB) | Request a copy |
Abstract
Penentuan rute distribusi gas bumi terkompresi (Compressed Natural Gas- CNG) dalam skala besar merupakan masalah logistik yang kompleks (NP-hard). Penelitian ini mengusulkan model optimasi hibrida berbasis Cluster-First, Route-Second (CFRS) untuk menyelesaikan masalah Capacitated Vehicle Routing Problem (CVRP) di PT Gagas Energi Indonesia wilayah Surabaya. Model ini menggabungkan algoritma klasterisasi pelanggan secara iteratif menggunakan fungsi skor multi-objective (untuk memaksimalkan utilisasi kapasitas dan meminimalkan estimasi waktu) dengan optimasi rute eksak berbasis MixedInteger Linear Programming (MILP) menggunakan kendala Miller-Tucker-Zemlin (MTZ) untuk eliminasi subtour. Kebaruan dari penelitian ini adalah integrasi model penurunan tekanan fisik truk Gas Transport Module (GTM) dari tekanan awal 250 Bar hingga target pengisian pelanggan 200 Bar, serta penerapan logika Klien E (Connecting Client) untuk memaksimalkan pemanfaatan sisa muatan gas hingga mencapai batas aman minimum 10 Bar sebelum truk kembali ke depot. Model ini juga mengintegrasikan faktor lalu lintas dinamis berbasis pengali waktu time-dependent (α = 1,0; 1,3; 1,7; 2,0). Seluruh alur diimplementasikan dalam prototipe aplikasi berbasis Python GUI yang secara otomatis merencanakan rute harian dan mengekspor dokumen surat jalan dalam format PDF A4. Validasi menggunakan data historis 3 rute riil membuktikan akurasi fisik model dengan sisa tekanan truk kembali ke depot tercatat tepat 10,0 Bar pada rute dengan Klien E. Hasil simulasi menunjukkan solver MILP mampu menyelesaikan rute optimal sub-masalah dalam waktu kurang dari 5 detik per cluster. Selain itu, mode optimasi dinamis yang diusulkan mampu mengurangi jumlah armada truk yang dikerahkan hingga 15% pada kondisi kepadatan tinggi, menghemat total waktu perjalanan hingga 32,3% (Skenario Lonjakan Permintaan) dan 11,3% (Skenario Lalu Lintas Dinamis), memotong jarak tempuh sebesar 20,1%, serta menghemat konsumsi BBG hingga 51,7% untuk truk 10feet. Model ini juga menunjukkan resiliensi operasional yang tinggi saat terjadi gangguan armada (truk 10-feet luring) dengan mempertahankan tingkat pelayanan sebesar 87,5% dibandingkan 37,5% pada kebijakan cluster tetap perusahaan.
=====================================================================================================================================
Determining large-scale distribution routes for compressed natural gas (CNG) is a complex logistical challenge classified as NP-hard. This study proposes a hybrid Cluster-First, Route-Second (CFRS) optimization model to solve the Capacitated Vehicle Routing Problem (CVRP) at PT Gagas Energi Indonesia in the Surabaya region. The model combines an iterative customer clustering algorithm utilizing a multi objective scoring function (to maximize capacity utilization and minimize estimated travel time) with exact route optimization using Mixed-Integer Linear Programming (MILP) and Miller-Tucker-Zemlin (MTZ) subtour elimination constraints. The key novelty lies in the integration of a physical pressure decay model for Gas Transport Module (GTM) trucks (from an initial pressure of 250 Bar to a target customer pressure of 200 Bar), alongside a Connecting Client (Client E) logic designed to maximize residual gas payload utilization down to a strict operational safety limit of 10 Bar. Additionally, the model incorporates dynamic traffic factors via time-dependent travel time multipliers (α = 1.0,1.3,1.7,2.0). The entire workflow is integrated into a Python-based GUI prototype that automates daily dispatch planning and exports structured A4 PDF dispatch documents. Validation against 3 historical real-world routes confirms the physical accuracy of the pressure decay model, with the truck’s returning pressure recorded at exactly 10.0 Bar. Simulation results demonstrate that the MILP solver yields local optimal routes in under 5 seconds per cluster. Compared to the company’s fixed cluster policy, the proposed dynamic clustering approach reduces truck fleet deployment by up to 15% under peak demands, saves total travel duration by up to 32.3% (Peak Demand scenario) and 11.3% (Dynamic Traffic scenario), reduces travel distance by 20.1%, and cuts CNG fuel consumption by 51.7.
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | Optimasi rute, Vehicle Routing Problem, Mixed-Integer Linear Programming, Cluster-based optimization, NP-hard, Near-optimal solution, Route optimization, Vehicle Routing Problem, Mixed-Integer Linear Programming, Cluster-based optimization, NP-hard, Near-optimal solution. |
| Subjects: | Q Science > QA Mathematics > QA278.55 Cluster analysis Q Science > QA Mathematics > QA401 Mathematical models. Q Science > QA Mathematics > QA402.6 Transportation problems (Programming) |
| Divisions: | Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44201-(S1) Undergraduate Thesis |
| Depositing User: | Louis Cristian Samuel Lukito |
| Date Deposited: | 03 Aug 2026 01:24 |
| Last Modified: | 03 Aug 2026 01:24 |
| URI: | http://repository.its.ac.id/id/eprint/136433 |
Actions (login required)
 |
View Item |