PENGEMBANGAN MODEL MATEMATIS FLEET SIZE AND MIX GREEN VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (FSMGVRPTW)

Salman Azzam Habibi Mardiansjah, Ir. Nur Mayke Eka Normasari, ST., M.Eng., Ph.D., IPM., ASEAN Eng.

2026 | Skripsi | TEKNIK INDUSTRI

Transisi menuju sistem logistik yang lebih berkelanjutan mendorong perusahaan untuk mulai mengadopsi kendaraan berbahan bakar alternatif. Namun, keterbatasan infrastruktur pengisian ulang menyebabkan perencanaan rute angkutan barang menjadi lebih kompleks karena kendaraan memiliki jangkauan terbatas dan rute harus mempertimbangkan titik pengisian yang tersedia. Penelitian ini menyusun model matematis Fleet Size and Mix Green Vehicle Routing Problem with Time Windows (FSMGVRPTW) sebagai integrasi Green Vehicle Routing Problem with Time Windows (GVRPTW) dan Fleet Size and Mix Vehicle Routing Problem (FSMVRP). Model bertujuan meminimasi total biaya perusahaan dengan menentukan rute pelayanan pelanggan menggunakan armada heterogen berbahan bakar alternatif, sekaligus menentukan keputusan fleet size dan mix, dengan mempertimbangkan time windows serta kemungkinan pengisian ulang di Alternative Fuel Station (AFS).

Untuk penyelesaian, metode eksak diterapkan pada instance skala kecil sampai menengah, sedangkan instance skala besar diselesaikan menggunakan metaheuristik Simulated Annealing (SA) yang dilengkapi operator route split dan route merge agar sesuai dengan karakteristik armada heterogen. SA membangun solusi awal menggunakan semi-parallel heuristic dengan kriteria pemilihan rute berbasis Average Cost per Unit Transferred  (ACUT), kemudian menghasilkan neighborhood melalui operator swap, insert, split, merge, dan re-type. Evaluasi rute dilakukan menggunakan decoder yang mensimulasikan propagasi waktu, muatan, dan bahan bakar, serta melakukan penambahan/penghapusan AFS untuk menjaga fisibilitas rute.

Eksperimen komputasi dilakukan pada 21 instance dengan variasi jumlah pelanggan dan pola persebaran (clustered, random, random-clustered). Secara keseluruhan, SA menghasilkan solusi near optimum ketika divalidasi terhadap metode eksak, dengan optimality gap rata-rata 1,18%. Dari sisi waktu komputasi, SA cenderung lebih lambat dibanding metode eksak pada instance skala kecil tetapi tetap fisibel untuk instance skala besar dengan waktu penyelesaian kurang dari 30 menit ketika metode eksak tidak lagi praktis. Hasil analisis sensitivitas menunjukkan bahwa perubahan demand dan routing cost pada rentang uji memengaruhi total biaya serta keputusan fleet size and mix, sehingga memberikan insight mengenai kecenderungan pergeseran komposisi armada dan kebutuhan konsolidasi rute pada skenario perubahan kondisi operasional. 

The transition toward more sustainable logistics has encouraged firms to adopt alternative-fuel vehicles. Nevertheless, limited refueling and recharging infrastructure increases the complexity of freight route planning, as vehicle driving range is constrained and routes must explicitly account for the availability of refueling points. This study develops a mathematical formulation of the Fleet Size and Mix Green Vehicle Routing Problem with Time Windows (FSMGVRPTW) by integrating the Green Vehicle Routing Problem with Time Windows (GVRPTW) and the Fleet Size and Mix Vehicle Routing Problem (FSMVRP). The model aims to minimize total distribution cost by determining customer service routes for a heterogeneous alternative-fuel fleet while simultaneously deciding the fleet size and mix, subject to customer time windows and the possibility of refueling at Alternative Fuel Stations (AFS).

To solve the problem, an exact method is applied to small-to-medium instances, whereas large-scale instances are addressed using a Simulated Annealing (SA) metaheuristic augmented with route split and route merge operators to better accommodate heterogeneous fleet characteristics. SA constructs an initial solution using a semi-parallel heuristic with a route selection criterion based on Average Cost per Unit Transferred (ACUT), and subsequently explores neighborhoods through swap, insert, split, merge, and re-type operators. Route feasibility is evaluated using a decoder that simulates the propagation of time, load, and fuel states, and performs AFS insertion and deletion to maintain feasibility.

Computational experiments are conducted on 21 instances with varying numbers of customers and three spatial distribution patterns (clustered, random, and random-clustered). Overall, SA produces near-optimal solutions when validated against the exact method, achieving an average optimality gap of 1.18%. In terms of computational effort, SA is generally slower than the exact approach on small instances, yet remains feasible for large instances, with solution times of less than 30 minutes when the exact method becomes impractical. Sensitivity analyses further indicate that variations in customer demand and routing cost within the tested ranges affect both total cost and the resulting fleet size-and-mix decisions, providing managerial insights into fleet composition shifts and the need for route consolidation under changing operating conditions.

Kata Kunci : FSMGVRPTW, armada heterogen, simulated annealing