Studi inventory routing kapal pengangkut BBM PT.Pertamina berbasis Algoritma genetika 1)
Betty Ariani ,A.A.Dinariyana
2)
1)
2)
mahasiswa PPSTK- ITS Staf pengajar Jurusan Teknik Sistem Perkapalan FTK - ITS
Abstract This paper addresses on the problem of finding a set of routes that minimizing the total cost routing in a network for a homogeneous fleet of ships engaged on delivery several liquid product of PT.Pertamina based on Genetic Algorithm.The problem is to decide how much of each product should be carried by each ship from supply ports to demand ports, subject to the inventory level of each product in each port being maintained between certain levels that are set by the consumption rates and the storage capacities of the various product in each port.The product are assumed to require dedicated compartement in the ship. Fitness value is calculated by the total distance between demand ports, and total transportation cost. Keywords: ship inventory routing; multy products;homogeneous fleet; genetic algorithm
1. Pendahuluan PT.Pertamina melayani kebutuhan bahan bakar minyak untuk seluruh nusantara.Dalam pendistribusiannya banyak kendala yang muncul dimana kadang suplai salah satu jenis atau beberapa bahan bakar minyak terlambat atau kurang.Tidak dipungkiri kendala jarak, dan penjadwalan distribusi masih kurang optimal. Permasalahan Vehicle routing problem memiliki pembagian beberapa karakteristik, yaitu: Split delivery, multiple trips, multiple products dan multiple compartemen [1]. -Pada split delivery → 1 konsumen dapat di suplai beberapa/ lebih dari1 vehicle. -VRP multiple trips → jika 1 vehicle menempuh lebih dari 1 rute. - VRP multiple product dan multiple compartement → jika ada beberapa product yang harus dikirim. Untuk permasalahan vehicle ada 2 pembagaian secara jenis untuk satu homogeneous fleet dan heterogenous fleet pada permasalahan inventory routing dengan heteregenous fleet atau [6] yang dipermasalahkan adalah : 1. Kapan waktu untuk melayani konsumen? 2. Berapa banyak yang harus dikirim? 3. Rute yang harus ditempuh? Algoritma genetika adalah suatu algoritma pencarian heuristic yang didasarkan atas mekanisme evolusi biologis. Terdiri atas 6 komponen utama yaitu teknik peneysuaian, prosedur inisialisasi, fungsi evaluasi, seleksi operator genetika dan penentuan parameter. Genetika algoritma sangat tepat dikembangkan untuk pencarian optimasi pada permasalahan kombinational. [2] Pada paper ini akan dilakukan perencanaan terhadap rute dan waktu pelayaran ( Ship routing & scheduling planning) dari Bulk Carrier yang mengangkut bahan bakar minyak milik Pertamina dari depo pusat ke depo – depo daerah.Data yang perlu didapatkan adalah kapasitas depo, rata-rata permintaan dari masing-masing jenis bahan bakar minyak, tingkat konsumsi rata-rata dari masing-masing jenis, dan jarak masing-masing depo.Secara garis besar yang kita lakukan pada perencanaan ini meliputi : 1. Melakukan pemodelan permasalahan homogeneous fleet Vehicle routing problem (VRP) pada algoritma genetika 2. Aplikasi algoritma genetika untuk mencari nilai optimum dari permasalahan homogenous fleet VRP
3. Bagaimana merancang dan membuat perangkat lunak untuk menjelaskan homogeneous fleet dengan algoritma genetika Sebagai batasan dalam perencanaan diambil asumsi-asumsi sebagai berikut: 1. Jumlah vehicle diinputkan dimana tiap vehicle memiliki kapasitas berbeda 2. Jumlah pelanggan diinputkan user dimana tiap pelanggan memiliki jarak lokasi dan demand 3. Jumlah depot penyuplai adalah 1 2. Metode pengerjaan: 2.1 Pemodelan kromosom: Dalam merancang kromosom mempertimbangkan: 1. Kromosom harus dapat mengandung informasi banyaknya vehicle pada solusi tersebut, dan status penugasan vehicle pada tiap customer. 2. Kromosom terdiri dari beberapa sub rute yang membentuk rute 3. VRP berkaitan dengan rute sehingga tidak bisa dinyatakan biner. Data yang dipakai sebagai data base pada perancangan perangkat lunak adalah sebagai berikut: Tabel 1 data jarak antar depo
kalabahi 0 118
larantuka
Kalabahi Larantuka Maumere Ende Reo Waingapu Atapupu kupang
194 185 274 198 185 198
120 93 252 254 129 130
maumere
ende
reo
waingapu
atapupu
kupang
0 93 124 254 295 218
0 252 99 192 201
0 135 192 348
0 265 201
0 118
0
0
Keterangan : jarak adalah dalam km Tabel 2 data kapasitas storage tank depo,tingkat konsumsi dan waktunya
depo kupang Atapupu Kalabahi Larantuka Maumere Reo Ende waingapu
CPTY 4912 293 96 182 1170 278 1114 1103
bensin CR 336 41 7 15 31.3 17 22.9 17
TM 14.6 7.1 13.7 12.1 37.4 16.4 48.6 64.9
CPTY 8484 481 288 360 1109 571 1114 1100
kerosin CR 389 53 16 30 34.5 57.3 39 28
TM 21.8 9.1 18 12 32.1 10 28.6 39.3
CPTY 12122 577 506 474 2237 963 2227 2229
solar CR 715 54 15 30 49.2 48.2 44.6 40
TM 17 10.7 33.7 15.8 45.5 20 49.9 55.7
Keterangan : CPTY = kapasitas storage tank masing-masing depo dalam kilo liter CR =banyaknya pemakaian dalam kilo liter TM = waktu lamanya pemakaian dalam hari Tabel 3 data kapal pengangkut bahan bakar
kapal bensin 300
kapasitas kerosin 600
solar 600
Sewa
Bea / km
kecepatan
$ 90
$ 10
10 knot
Tabel 4 contoh inputan data permintaan untuk 1 periode ( 7 hari )
Depo Bensin Atapupu 287 Kalabahi 49 Larantuka 105 Maumere 219.1 Reo 11.9 Ende 160.3 waingapu 119 Dengan menggunakan perumusan: jika demand – stok ≤ 0 tidak dikirim Jika demand – stok > 0 maka dilakukan pengiriman
Kerosin 371 112 210 241.5 401.1 273 196
Solar 378 105 210 344.4 337.4 312.2 280
2.2 Perancangan operator algoritma genetika : Population generator (pembangkitan populasi): Kita melakukan pembangkitan secara random terhadap rute.Setelah itu dilakukan pengecekan apakah rute hasil pembangkitan tersebut mungkin atau tidak.jika rute mungkin maka dimasukkan kedalam populasi,jika tidak mungkin buat kemungkinan sebesar 10 % supaya rute tetap bisa masuk dengan tujuan memperlebar area pencarian solusi (search space) dan lebih menyingkat waktu.Adapun proses pembangkitan random rute adalah sebagai berikut : Misalkan dengan data demand dan stok yang ada maka diambil keputusan sebagai berikut: Tabel 5 contoh pengambilan keputusan pengiriman
1
2
3
4
B
K
S
B
K
S
B
K
S
B
K
S
1
1
1
1
1
1
1
1
1
1
1
1
1
2
0
0
0
1
1
0
0
0
1
1
1
0
3
0
0
0
1
1
1
0
0
0
1
1
1
4
0
0
0
0
0
0
0
0
0
1
1
0
5
0
1
0
1
1
1
0
1
0
1
1
1
6
0
0
0
0
0
0
0
0
0
0
1
0
7
0
0
0
0
0
0
0
0
0
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
Keterangan : 1 berarti dilakukan pengiriman 0 berarti tidak dilakukan pengiriman
Buat daftar kota-kota yang memiliki permasalahan VRP yang diinput user, kemudian buat sub rute dengan pemisah 0 sebanyak jumlah kendaraan. 123045067,memiliki arti memakai 3 kapal dimana kapal 1 menuju depo 123, kapal 2 menuju depo 45 dan kapal ke tiga menuju ke depo 67 Proses seleksi Melakukan pemilihan terhadap dua kromosom dari populasi yang dibangkitkan tadi dengan menggunakan metode Roullete Wheel,dengan cara : Cari nilai evaluasi (jarak tempuh) terbesar dari keseluruhan solusi pada populasi Hitung selisih dari nilai evaluasi terbesar dengan nilai evaluasi tiap kromosom. Nilai-nilai itu kemudian dijumlah
Hasilnya dikali dengan bilangan random dan dapatkan nilainya,nilai tersebut dicari posisinya pada daftar selisih nilai evaluasi terbesar dengan nilai evaluasi tiap kromosom. Maka itulah hasil proses seleksi. Cross over (pindah silang) Digunakan simple random cross over dimana input dari proses cross over adalah dua buah kromosom yang sebelumnya diambil lewat proses seleksi.Algoritma simple random cross over ini memerlukan kromosom yang repetitive,dimana tidak boleh ada lebih dari satu gen yang bernilai sama.sedangkan kromosom yang digunakan pada aplikasi ini bertipe repetitive (menggunakan lebih dari satu gen bernilai 0 sebagai penanda depot / pemisah rute).karena itu pada awal operasi cross over dilakukan normalisasi pada kedua kromosom yang akan disilangkan .proses tersebut dilakukan dengan mengganti gen-gen yang bernilai 0 dengan integer negative dekremental (-1,-2,…) sehingga kromosom yang dihasilkan akan bertipe non repetitive Mutasi Proses mutasi pada umumnya adalah proses pergantian bit dari 1 menjadi 0 pada suatu titik tertentu yang didapatkan secara acak.Namun karena kromosom yang digunakan pada aplikasi ini adalah bertipe non repetitive maka operator mutasi yang digunakan adalah random swap mutation yaitu proses pertukaran 2 buah gen dalam 1 kromosom dimana gen-gen yang akan ditukarkan tersebut didapatkan secara acak. Fungsi repair Karena solusi yang dibangkitkan terkadang tidak feasible maka ditambahkan satu fungsi yaitu repair yang fungsinya mereduksi ke unfeasiblean solusi.Pengerjaannya sebagai berikut : Cari sub rute dengan demand paling banyak Cari sub rute dengan demand paling sedikit Ambil satu customer secara acak pada sub rute dengan demand paling banyak Masukkan customer tersebut pada akhir sub rute dengan demand paling sedikit Proses selesai 3.Hasil solusi dari metode algoritma genetika Nilai parameter algoritma genetika yang dipakai adalah sebagai berikut: Ukuran populasi = 50 Peluang cross over = 0.6 atau 60% Peluang mutasi = 0.001 atau 0.1 % Maksimum generasi = 100 Didapatkan hasil sebagai berikut :
C
Atapupu
U
Kalabahi
S
Larantuka
Periode 1 1 (251,371,378) 1 ( 49,112,105) 0
T
Maumere
0
O
Reo
M
Ende
1 ( 101,188,263) 0
E
Waingapu
1 ( 119,196,280)
Periode 2 1 (36,0,0) 0 1 (105,210,210) 1 (0,50,0) 1 (17,0,74) 0 0
Periode 3 1 (287,371,378) 1 (0,0,105) 0 0 0 0 0
Periode 4 1 (287,371,378) 1 (49,112,0) 1 (105,210,210) 1 (219,241,344) 1 (11,401,337) 1 (0,273,0) 0
R Total kapasitas
-
Jarak tempuh Jumlah kapal Total biaya
2413
Periode 1 791 2 $ 8000
Periode 2 672 1 $ 6810
702
1141
Periode 3 321 1 $ 3300
3548
Periode 4 894 3 $ 9030
4.Kesimpulan Paper ini belum bisa menyajikan hasil yang benar – benar factual karena keterbatasan inputan data dan populasi yang dibangkitkan kurang besar sehingga tidak memberikan ruang pencarian yang maksimal.Diharapkan kelanjutan pencarian dengan ruang yang lebih besar akan memberikan hasil yang lebih optimal lagi.
5.Daftar Pustaka [1] [2] [3] [4]
[5] [6]
Suprayogi & Setiawan Komara ,A sequential insertion algorithm for solving a distribution problem of fuel products,journal of the society of Naval Architects of Japan,336-340, 2006 Sri Kusuma dewi & Hari purnomo, penyelesaian masalah optimasi dengan teknik heuristic , pp 223-250, 2007 Suprayogi & Tombak Gapura Bhagya, Solving ship routing and deployment problem using genetic algorithm, Journal of the society of Naval Architect of Japan, 2006 Ricardo Giesen & Juan carlos munos, Multi item inventory routing problem for ship distribution of liquid oil bulk products,Transport and logistic Engineering Departement Pontificia Universidad Catolica de Chile. Tamer F.Abdelmaguid & Maged M Dessouky, A genetic algorithm approach to the integrated inventory distribution problem, Transportasion research,2007 Faiz Al khayyal & Seung June Hwang, Inventory constrained maritime routing and scheduling for multy commodity liquid bulk,European Journal of Operation Research,2005.
