Perancangan Model Rute dan Jadwal Pengisian Bahan Bakar Unit Loader yang Optimal Menggunakan Algoritma Tabu Search (Studi Kasus Pada PT Pamapersada Nusantara) Amar Rachman1, Febri Vabiono P2
Departemen Teknik Industri, Universitas Indonesia, Depok 16424 Tel: (021) 78888805. Fax: (021) 78885656 Email:
[email protected],
[email protected]
Abstrak Penentuan rute dan jadwal merupakan masalah yang terdapat dalam masalah distribusi yang dikenal dengan istilah vehicle routing problem (VRP). Rute dan jadwal yang optimal akan memberikan kontribusi terhadap penurunan biaya distribusi. Masalah distribusi dalam penelitian ini adalah pengisian bahan bakar unit loader yang tersebar di area tambang. Posisi unit loader ini berpindah-pindah dalam waktu yang tertentu sesuai dengan area mana yang akan ditambang. Oleh karena itu, dibutuhkan suatu model rute dan jadwal pengisian bahan bakar unit loader yang optimal yang bisa mengakomodasi terjadinya perpindahan posisi unit loader ini. Penelitian ini bertujuan untuk memperoleh model rute dan jadwal pengisian bahan bakar unit loader yang optimal dan mencegah unit loader berhenti beroperasi karena kehabisan bahan bakar. Algoritma Tabu Search akan digunakan untuk menyelesaikan masalah penentuan rute dan jadwal dalam penelitian ini. Algoritma Tabu Search merupakan salah satu algoritma metaheuristik yang ampuh untuk digunakan menyelesaikan masalah optimasi kombinatorial seperti VRP. Dengan algoritma ini, akan dirancang sebuah model optimasi menggunakan program MATLAB. Model yang dirancang kemudian akan digunakan untuk menentukan rute dan jadwal pengisian bahan bakar unit loader yang optimal setiap harinya. Kata Kunci: Rute, Jadwal, Optimasi, Vehicle Roting Problem, Algoritma Tabu Search, Model Abstract Routes and Schedules determination are problem that occur in distribution problem which is known as vehicle routing problem. Optimal routes and schedules will contribute to lowering the cost of distribution. Distribution problems in this study are loader units refueling that scattered in the mine area. The position of the loader unit to move in a certain time according to which area to be mined. Therefore, we need an optimal model of the routes and schedules of loader units refueling that can accommodate the movement of the loader units position. This study aims to obtain an optimal model of routes and schedules of loader units refueling and to prevent loader units from stop operating due to running out of fuel. Tabu Search algorithm is used to solve the problem of determining the routes and schedules in this study. Tabu Search algorithm is one of the powerful metaheuristic algorithms to be used to solve combinatorial optimization problems like VRP. With this algorithm, an optimization model will be designed using the MATLAB program. The model that is designed, later to be used to determine the optimal routes and schedules of loader units refueling every day. Key words: Route, Schedule, Optimization, Vehicle Roting Problem, Tabu Search Algorithm, Model
1
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
1. PENDAHULUAN PT Pamapersada Nusantara (PAMA) merupakan kontraktor pertambangan batubara terbesar di Indonesia yang senantiasa berusaha meningkatkan kapasitas produksinya. Salah satu langkah yang diambil oleh PAMA untuk meningkatkan produksinya adalah dengan menerapkan sistem 24/7. Sistem 24/7 ini artinya operasional tambang akan berlangsung selama 24 jam dalam sehari dan 7 hari dalam seminggu. Adanya sistem 24/7 ini mempengaruhi jadwal pengisian bahan bakar unit loader. Penerapan sistem baru ini membuat sistem penjadwalan yang lama tidak bisa dilakukan. Selama ini, jadwal pengisian bahan bakar unit loader dilakukan pada saat jam istirahat makan siang dan pada tengah malam. Dengan adanya sistem 24/7, sistem penjadwalan yang lama tidak bisa lagi diterapkan. Objek perhatian pada penelitian ini adalah unit produksi loader. Loader merupakan unit alat berat yang digunakan untuk memuat bahan tambang ke Hauler (truk pengangkut). Loader merupakan unit produksi yang bersifat non-mobile unit, yaitu unit yang memiliki mobilitas rendah sehingga pengisian ulang bahan bakarnya dilakukan dengan didatangi oleh unit fuel truck. Posisi unit loader ini tersebar secara geografis di area tambang dan posisinya bisa berpindah-pindah pada jangka waktu tertentu sesuai dengan area mana yang akan ditambang. Kapasitas dan tingkat konsumsi unit loader yang digunakan juga berbeda-beda sehingga jumlah bahan bakar yang harus diisi oleh fuel truck di tiap loader berbeda-beda. Untuk mengatasi permasalahan ini, maka dibutuhkan suatu model optimasi rute dan jadwal pengisian bahan bakar unit loader yang bisa mengakomodasi perpindahan posisi unit loader ini serta bisa mengoptimalkan biaya pengisian bahan bakar. Salah satu komponen utama yang harus diperbaiki dalam proses penjadwalan pengisian bahan bakar ini adalah penentuan rute yang dilalui fuel truck untuk mengisi bahan bakar unit loader. Salah satu metode yang bisa digunakan untuk menyelesaikan masalah optimasi rute dan penjadwalan sistem pengisian bahan bakar unit loader ini adalah dengan pendekatan model Mix Integer Programming yang diselesaikan dengan algoritma Tabu Search. Algoritma Tabu Search merupakan algoritma yang menuntun setiap tahapannya agar dapat menghasilkan kriteria aspirasi yang paling optimum tanpa terjebak ke dalam solusi awal yang ditemukan selama tahapan berlangsung. Tujuan dari penelitian ini adalah memperoleh suatu model rute dan jadwal pengisian bahan bakar unit loader yang bisa mengoptimalkan biaya pengisian bahan bakar, mengakomodasi perpindahan posisi unit loader, dan menghindari unit loader berhenti beroperasi karena kehabisan bahan bakar. Dengan model optimasi yang dirancang berdasarkan algoritma tabu search, diharapkan tujuan penelitian dapat tercapai.
2. DASAR TEORI 2.1 Vehicle Routing Problem Vehicle Routing Problem (VRP) adalah suatu istilah yang digunakan untuk masalah penentuan sejumlah set rute pada sejumlah kendaraan, baik dari single depot ataupun multiple depot, yang akan ditugaskan untuk melayani pelanggan ataupun kota yang tersebar secara geografis[1]. Tujuan yang ingin dicapai dalam VRP adalah melayani sejumlah pelanggan dengan jumlah permintaan masing-masing dengan biaya dan jarak tempuh kendaraan minimal, dimana rute kendaraan dimulai dan berakhir di depot.
2
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
VRP merupakan sebuah masalah optimasi yang termasuk ke dalam kategori masalah optimasi Mix Integer Programming yang diperkenalkan pertama kali oleh Dantzig dan Ramser pada tahun 1959 untuk masalah penentuan rute dan penjadwalan truk[2]. Kemudian Clarke dan Wright (1964) memperbaiki pendekatan yang dilakukan oleh Dantzig dan Ramser dengan mengajukan metode heuristik. Setelah itu penelitian pada VRP terus berkembang karena perannya dalam distribusi pada industry. VRP memegang peranan penting pada manajemen distribusi dan telah menjadi salah satu permasalahan dalam optimalisasi kombinasi yang dipelajari secara luas. VRP merupakan manajemen distribusi barang yang memperhatikan pelayanan, periode waktu tertentu, sekelompok pelanggan dengan sejumlah kendaraan yang berlokasi pada satu atau lebih depot, yang dijalankan oleh sekelompok pengendara dengan menggunakan road network yang sesuai. Solusi dari sebuah VRP yaitu menentukan sejumlah rute yang masingmasing dilayani oleh suatu kendaraan yang berasal dan berakhir pada depotnya, sehingga kebutuhan pelanggan terpenuhi, semua permasalahan operasional terselesaikan, dan biaya transportasi secara umum diminimalkan. Terdapat empat tujuan utama VRP, yaitu[3]: • • • •
Meminimalkan biaya transportasi total, terkait dengan jarak dan biaya tetap yang berhubungan dengan kendaraan Meminimalkan jumlah kendaraan yang dibutuhkan untuk melayani semua pelanggan Menyeimbangkan rute untuk waktu perjalanan dan muatan kendaraan Meminimalkan penalti akibat pelayanan yang kurang memuaskan dari konsumen
VRP merupakan sebuah masalah optimasi Mix Integer Programming yang masuk kategori NP-Hard Problem, yang berarti usaha komputasi yang digunakan akan semakin sulit dan banyak seiring dengan meningkatnya ruang lingkup masalah. Untuk masalah-masalah seperti ini, biasanya yang dicari adalah aproksimasi solusi yang terdekat, karena solusi tersebut dapat dicari dengan cepat dan cukup akurat. Biasanya masalah ini terselesaikan dengan menggunakan berbagai variasi dari metode heuristik yang memerlukan sedikit pengamatan pada ruang lingkup masalah. 2.2 Algoritma Tabu Search Tabu Search adalah salah satu algoritma metaheuristik yang pertama kali diperkenalkan oleh Fred Glover pada tahun 1986 dan telah menjadi salah satu metode terbaik dan berkembang paling cepat untuk menyelesaikan masalah optimasi kombinatorial[4]. Tabu search merupakan algoritma yang menuntun setiap tahapannya agar dapat menghasilkan kriteria aspirasi yang paling optimum tanpa terjebak ke dalam solusi awal yang ditemukan selama tahapannya berlangsung. Algoritma ini mencegah terjadinya perulangan dan ditemukannya solusi yang sama pada suatu iterasi yang akan digunakan lagi pada iterasi selanjutnya (statusnya dikatakan tabu). Tabu search adalah sebuah metode optimasi yang berbasis pada local search. Proses pencarian bergerak dari satu solusi ke solusi berikutnya dengan cara memilih solusi tetangga terbaik dari solusi sekarang (current) yang tidak tergolong solusi terlarang. Ide dasar dari algoritma tabu search adalah mencegah proses pencarian dari local search agar tidak melakukan pencarian ulang pada ruang solusi yang sudah pernah ditelusuri, dengan memanfaatkan suatu struktur memori yang mencatat sebagian jejak proses pencarian yang telah dilakukan[5]. Struktur memori fundamental dalam tabu search dinamakan tabu list. Tabu list menyimpan atribut dari sebagian move (transisi solusi) yang telah diterapkan pada 3
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
iterasi-iterasi sebelumnya. Tabu search menggunakan tabu list untuk menolak solusi-solusi yang memenuhi atribut tertentu guna mencegah proses pencarian mengalami cycling pada daerah solusi yang sama dan menuntun proses pencarian menelusuri daerah solusi yang belum dikunjungi. Sebagai tambahan dari tabu list, dikenal adanya aspiration criteria, yaitu suatu penanganan khusus terhadap move yang dinilai dapat menghasilkan solusi yang baik, namun move tersebut berstatus tabu[5]. Dalam hal ini, jika move tersebut memenuhi kriteria aspirasi yang telah ditetapkan sebelumnya, maka move tersebut dapat digunakan untuk membentuk solusi berikutnya, artinya status tabunya dibatalkan.
3. METODOLOGI PENELITIAN Untuk merancang model rute dan jadwal pengisian bahan bakar unit loader yang optimal, ada beberapa tahap penelitian yang harus dilaksanakan. Pertama sekali adalah identifikasi masalah dan penetapan tujuan penelitian seperti yang sudah dijelaskan pada pendahuluan. Setelah menetapkan tujuan penelitian, kemudian dilakukan studi literatur untuk menentukan metode yang digunakan untuk menyelesaikan masalah. Setelah itu dilakukan pengumpulan data yang dibutuhkan untuk melakukan penelitian. Data yang digunakan dalam penelitian ini diperoleh dari data historis perusahaan dan data yang diobservasi dari lapangan. Data yang digunakan adalah data fuel truck dan spesifikasinya, data loader dan spesifikasinya, data peta lokasi beserta posisi unit loader, dan data lainnya yang berhubungan dengan operasional penelitian. Data yang diperoleh kemudian disimpan dalam data Ms. Excel untuk kemudian diolah menggunakan model optimasi yang dirancang menggunakan program MATLAB. Untuk mencapai tujuan penelitian yaitu memperoleh model rute dan jadwal pengisian bahanbakar yang optimal, maka fungsi tujuan dari penelitian ini adalah untuk meminimalkan biaya total pengisian bahan bakar unit loader, yaitu: !!" !!"# + !!" !! (1)
!"# ! = !∈! !∈! !∈!
Dengan: Tij
= Waktu tempuh titik i ke titik j
Xijkp
= {0,1}
Sik
= Waktu pelayanan di titik i
Ck
= Biaya pemakaian fuel truck k
Fungsi integer di atas menunjukkan terhubung atau tidaknya titik i ke titik j dengan fuel truck k. Nilai 0 menunjukkan bahwa titik i dan titik j tidak terhubung, sedangkan nilai 1 menunjukkan bahwa titik i dan titik j dihubungkan oleh fuel truck k, dengan: i= 0,1,…..N j= 1,2,…..N,0 k= 1,2,…K 4
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
Berikut merupakan beberapa kendala operasional yang harus dipenuhi dalam model ini: •
Setiap loader harus dilayani sebanyak 1 kali selama periode perencanaan !!"# = 1, ∀! ∈ !; ! ≠ 0 (2) !∈! !∈!
!!"# = 1, ∀! ∈ !; ! ≠ 0 (3) !∈! !∈!
•
Semua fuel truck berangkat dari depot !!!" = 1, ∀! ∈ ! 4) !∈!
•
Jika fuel truck k memasuki sebuah titik i, maka fuel truck tersebut harus meninggalkan titik tersebut !!"# = !∈!
•
!∈!
Jumlah bahan bakar yang diisi oleh fuel truck k di titik (loader) i tidak bisa melebihi kapasitas fuel truck !! !∈!
•
!!"# , ∀! ∈ !, ∀! ∈ !; ! ≠ ! (5)
!!"# ≤ !! , ∀! ∈ ! (6) !∈!
Waktu kedatangan fuel truck k di titik j, merupakan waktu kedatangan di titik sebelumnya (i) ditambah waktu tempuh titik i ke titik j ditambah lamanya pengisian di titik i. !"!" = !"!" + !!"# !!" + !!" , ∀!; ! ≠ ! (7)
Atau, waktu kedatangan fuel truck k di titik j, merupakan waktu titik sebelumnya (i) ditambah waktu tempuh titik i ke titik j.
keberangkatan dari
!"!" = !"!" + !!"# !!" , ∀! ∈ !; ! ≠ ! (8) •
Waktu keberangkatan fuel truck dari titik i merupakan waktu kedatangan fuel truck k di loader i ditambah lamanya waktu pengisian di loader i !"!" = !"!" + !"#, ∀! ∈ !, ∀! ∈ ! (9)
•
Waktu kembalinya fuel truck ke depot tidak lebih dari selang waktu pengisian !"!! ≤ 12, ∀! ∈ ! (10)
Keterangan: Himpunan: N
: Himpunan semua titik (0 menunjukkan depot, 1-N menunjukkan loader)
K
: Himpunan semua kendaraan 5
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
Parameter: Tij
: Waktu tempuh titik i ke titik j (m)
Qk
: Kapasitas tangki fuel truck k (L)
di
: Jumlah bahan bakar yang diisi di loader i (L)
Sik
: Lama pengisian di loader i menggunakan fuel truck k (menit)
Ck
: Biaya pemakaian fuel truck (US$)
Variabel: Xijk
: Variabel integer, 1 jika i ke j terhubung, 0 jika tidak
TAik
: Waktu kedatangan fuel truck k di titik i
TDik
: Waktu keberangkatan fuel truck k dari titik i
Algoritma Tabu Search dalam penelitian ini diselesaikan dengan menggunakan software Matlab R2012b. Source code dari program yang digunakan bisa dilihat pada bagian lampiran. Berikut merupakan langkah-langkah pengerjaan algoritma pada program yang digunakan untuk menyelesaikan masalah VRP pada penelitian ini: a) Menentukan solusi awal Solusi awal yang digunakan dalam algoritma ini diperoleh dengan menggunakan solusi awal acak (random initial solution). Solusi awal acak ini diperoleh dari program dengan cara mengacak urutan rute pengiriman bahan bakar. Solusi awal yang diperoleh akan digunakan sebagai acuan awal sebagai pembanding ketika proses Tabu Search dimulai. Pada tahap ini ditentukan Sbest = S, C_itr = 0 (current iteration counter). b) Inisialisasi tabu search Menentukan skema tabu tenure (durasi tabu) serta nilai untuk tiap parameternya. Skema tabu tenure yg digunakan dalam algoritma ini adalah Fixed TS (F-Tabu) dimana durasi dari suatu solusi dianggap tabu adalah tetap selama proses iterasi berlangsung. Kemudian menentukan jumlah panjang / total iterasi T_itr dan B_itr = 0 (best iteration counter), panjang tabu list (tabu tenure) dan jumlah solusi tetangga. Ketiga parameter ini akan ditentukan dengan cara melakukan perubahan terhadap parameter-parameter ini untuk mencari kombinasi yang menghasilkan solusi paling optimal. Berdasarkan percobaan yang dilakukan untuk menentukan nilai tiap parameter tabu search, didapat bahwa nilai parameter untuk masingmasing parameter adalah jumlah solusi tetangga 30, panjang tabu list 15, dan panjang iterasi 600. c) Melakukan iterasi Melakukan move untuk membuat solusi tetangga. Mekanisme pembentukan solusi tetangga yang digunakan dalam algoritma ini adalah menggunakan local search dengan metode swap. Metode ini membentuk solusi tetangga dengan memilih secara acak dua bagian struktur untuk selanjutnya ditukar posisinya. Kemudian menentukan solusi saat ini (current solution) S menjadi S’, C_itr=C_itr+1. 6
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
d) Mengecek Tabu Untuk menghindari terulangnya langkah yang diambil, maka dilakukan tabu test. Tabu test memanfaatkan tabu list yang sudah ada. Tujuan sebenarnya dari tabu list bukan untuk mencegah terulangnya langkah-langkah yang telah diambil, tetapi lebih kepada agar tidak mundur untuk mencegah perulangan, daftar solusi yang telah dicapai disimpan dalam sebuah table. e) Aspiration Test Alternative move yang lolos tabu test harus melewati aspiration test. Jika tidak dapat melewati aspiration test, maka tidak akan diteruskan ke iterasi berikutnya. Jika alternative move mempunyai aspiration criteria yang lebih baik daripada aspiration threshold, maka dilakukan eksekusi terhadap alternative move tersebut dan memperbaharui memori yang tidak relevan. f) Mengecek Kendala Kapasitas Setelah rute terbaik didapat, kemudian dilakukan penugasan terhadap fuel truck yang digunakan. Jika kapasitas satu fuel truck tidak memenuhi lagi, maka fuel truck berikutnya ditugaskan. Begitu seterusnya sampai semua titik / loader dikunjungi. g) Pemberhentian Proses Iterasi Jika aturan pemberhentian sudah memenuhi syarat pemberhentian, maka pencarian berhenti. Kriteria penghentian pada Tabu Search adalah : § § § §
Tidak ada solusi yang mungkin di solusi tetangga Iterasi lebih besar dari jumlah iterasi maksimum yang diperbolehkan Jumlah iterasi sejak perbaikan terakhir dari i* lebih besar dari angka tertentu Dapat dibuktikan bahwa solusi optimum telah diperoleh
Diagram alir algoritma Tabu Search bisa dilihat pada gambar 1.
7
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
Gambar 1 Mekanisme Penggunaan Algoritma Tabu Search
4. HASIL DAN PEMBAHASAN Untuk mencari rute pengisian bahan bakar loader yang optimal, maka dibutuhkan data seperti data loader, data fuel truck, matriks jarak, data waktu dan data lain yang berhubungan dengan operasional pengisian bahan bakar loader. Data ini kemudian disalin di dalam file Microsoft Excel yang kemudian akan diubah ke dalam bentuk matriks untuk mempermudah program dalam pengolahan datanya. Sebelum menggunakan program untuk melakukan proses pengolahan data, terlebih dahulu harus dilakukan verifikasi dan validasi program. Verifikasi merupakan tahapan untuk memeriksa apakah program yang dirancang untuk menyelesaikan permasalahan optimasi ini telah bekerja sesuai dengan konsep yang dimaksud. Setelah proses verifikasi selesai, 8
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
dilanjutkan dengan melakukan validasi program. Validasi bertujuan untuk mengetahui apakah program bekerja sesuai dengan fungsinya dan menghasilkan output yang benar. Program dikatakan tervalidasi jika output yang dihasilkan program sama dengan output yang dihasilkan dari perhitungan manual. Berikut merupakan perubahan penentuan parameter kontrol tabu search beserta hasilnya. Proses penentuan parameter kontrol ini sekaligus menjadi proses verifikasi program. Tabel 1 Penentuan Parameter Kontrol Jumlah Solusi Tetangga
Panjang Tabu List
Maksimum Iterasi
Total Jarak (m)
Total Cost (US$)
Waktu Komputasi (detik)
10
10
500
103118
704.9534433
23
20
10
500
88379
661.2007217
28
30
10
500
76579
625.505755
36
40
10
500
86321
655.0915483
43
50
10
500
88838
662.5632633
49
30
10
500
88917
662.797775
36
30
15
500
77311
628.3453633
36
30
20
500
95058
681.0273333
37
30
25
500
104468
708.9609183
37
30
30
500
81331
640.2787333
37
30
15
400
89124
663.4122533
28
30
15
500
78054
630.5509583
36
30
15
600
69037
603.783995
43
30
15
700
87087
657.36542
50
30
15
800
86768
656.4184683
58
30
15
900
73129
615.9310967
65
30
15
1000
93479
676.3400717
72
Berdasarkan hasil percobaan parameter kontrol tabu search yang dilakukan, diperoleh bahwa kombinasi parameter kontrol yang memberikan hasil terbaik adalah jumlah solusi tetangga 30, panjang tabu list 15, dan panjang iterasi 600. Dari proses penentuan parameter kontrol yang sekaligus menjadi proses verifikasi program ini, program dinyatakan telah terverifikasi.
9
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
Sedangkan proses validasi dilakukan dengan menggunakan 5 titik dummy pelanggan yang harus dilayani. Berikut merupakan data dummy yang digunakan untuk proses validasi: Tabel 2 Matriks jarak dummy Matriks Jarak (m)
0
1
2
3
4
5
Depot
0
0
4200
4800
5200
3900
5000
EX1768
1
4200
0
8900
9300
4400
5300
EX1053
2
4800
8900
0
5500
4500
9500
EX749
3
5200
9300
5500
0
9100
4000
EX1723
4
3900
4400
4500
9100
0
8900
EX731
5
5000
5300
4922
4000
8900
0
Dengan menjalankan program beberapa kali, dari program didapat bahwa rute terbaik adalah rute 0-3-5-2-4-1-0 dengan total jarak 27222 meter. Perhitungan manual untuk menghitung total jarak, ternyata memberikan nilai yang sama dengan output program. Untuk membuktikan apakah rute ini merupakan rute terbaik, maka akan dicari total jarak untuk kombinasi rute yang lain. Berikut merupakan total jarak untuk sebagian dari kombinasi rute lain yang mungkin dibentuk dari 5 titik tersebut: Tabel 3 Kombinasi Rute yang Mungkin dari Output Validasi Program Rute
Total Jarak
0-4-2-3-5-1-0
27400
0-1-4-2-3-5-0
27600
0-4-1-5-2-3-0
29222
0-4-2-1-5-3-0
31800
0-3-5-1-4-2-0
28200
Dari Tabel di atas bisa dilihat bahwa rute terbaik yang dihasilkan oleh program adalah rute terbaik dari semua kombinasi yang ada. Karena program yang digunakan telah sesuai dengan konsep awal dibuatnya yaitu untuk mencari rute terbaik dan menunjukkan hasil yang sama dengan perhitungan manual, maka program dikatakan telah tervalidasi. Data yang telah diinput kemudian diolah menggunakan program yang telah dirancang menggunakan MATLAB. Data ini akan diolah menggunakan parameter kontrol Tabu Search yang sebelumnya telah ditentukan, yaitu jumlah solusi tetangga 30, panjang tabu list 15, dan panjang iterasi 600. Rute pengisian bahan bakar unit loader terbaik akan dicari dengan 10
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
menggunakan 3 skenario yaitu menggunakan fuel truck berkapasitas 25000 L, menggunakan fuel truck berkapasitas 18000 L, dan menggunakan kombinasi kedua fuel truck. Setiap skenario akan di-run sebanyak 5 kali untuk mendapatkan hasil paling optimal. Run yang menunjukkan output terbaik, kemudian dipilih sebagai solusi optimal. Berikut merupakan hasil run program untuk skenario menggunakan fuel truck berkapasitas 25000 L: Tabel 1 Hasil Run Program untuk Fuel truck 25000 L Rute
Jarak (m)
Waktu (menit)
Biaya (US$)
FT 1
0-‐3-‐4-‐6-‐5-‐15-‐14-‐13-‐12-‐11-‐19-‐ 16-‐17-‐18-‐0
42022
375
371
FT 2
0-‐1-‐2-‐7-‐8-‐10-‐9-‐21-‐20-‐22
29901
244
241
71923
619
612
FT 25000 L
Run 1
Total
Run 2
FT 1
0-‐2-‐4-‐3-‐17-‐18-‐14-‐13-‐12-‐11-‐15-‐ 5-‐6-‐1-‐0
45856
386
382
FT 2
0-‐16-‐19-‐22-‐20-‐21-‐9-‐10-‐7-‐8-‐0
32382
252
249
78238
638
631
Total
Run 3
FT 1
0-‐17-‐18-‐16-‐12-‐11-‐14-‐13-‐15-‐4-‐3-‐ 2-‐1-‐7-‐8-‐0
44256
380
376
FT 2
0-‐6-‐5-‐10-‐9-‐21-‐22-‐20-‐19-‐0
26754
236
233
71010
616
609
Total
Run 4
FT 1
0-‐8-‐7-‐10-‐9-‐22-‐20-‐21-‐17-‐18-‐16-‐ 19-‐12-‐13-‐0
42844
377
373
FT 2
0-‐4-‐1-‐3-‐2-‐6-‐5-‐11-‐15-‐14-‐0
29702
243
241
72546
620
614
Total
Run 5
FT 1
0-‐19-‐16-‐21-‐22-‐20-‐9-‐10-‐7-‐8-‐5-‐6-‐ 3-‐2-‐0
39023
358
354
FT 2
0-‐1-‐4-‐15-‐13-‐14-‐11-‐12-‐18-‐17-‐0
30441
254
251
69464
612
605
Total
Dari beberapa kali run program, didapatkan rute terbaik untuk pengisian menggunakan fuel truck berkapasitas 25000 L saja adalah hasil run 5 dengan total jarak dan biaya yang terdapat pada tabel di atas. Utilitas rata-rata fuel truck yang digunakan untuk skenario ini adalah 80.6%.
11
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
Berikut merupakan hasil run program untuk skenario menggunakan fuel truck berkapasitas 18000 L: Tabel 2 Hasil Run Program untuk Fuel truck 18000 L FT 18000 L
Run 1
Rute
Jarak (m)
Waktu (menit)
Biaya (US$)
FT 1
0-‐5-‐6-‐7-‐8-‐10-‐9-‐22-‐20-‐21-‐0
28408
265
237
FT 2
0-‐4-‐15-‐11-‐12-‐13-‐14-‐16-‐17-‐ 18-‐19-‐0
32371
270
242
FT 3
0-‐3-‐1-‐2-‐0
10048
81
72
70827
616
551
Total
Run 2
FT 1
0-‐16-‐18-‐17-‐21-‐9-‐10-‐1-‐3-‐4-‐2-‐ 0
31769
274
245
FT 2
0-‐7-‐8-‐20-‐22-‐19-‐12-‐11-‐13-‐14-‐ 15-‐0
38062
289
259
FT 3
0-‐5-‐6-‐0
12856
88
79
82687
651
583
Total
Run 3
FT 1
0-‐14-‐11-‐13-‐12-‐15-‐4-‐2-‐3-‐1-‐5-‐ 0
31410
269
241
FT 2
0-‐19-‐22-‐21-‐20-‐9-‐10-‐7-‐8-‐6-‐0
30880
262
235
FT 3
0-‐17-‐18-‐16
12256
95
85
74546
626
561
Total FT 1
0-‐5-‐6-‐8-‐7-‐15-‐13-‐14-‐11-‐12-‐0
30167
264
237
Run 4 FT 2
0-‐3-‐1-‐2-‐4-‐10-‐9-‐21-‐20-‐22-‐19-‐ 0
31123
264
236
0-‐18-‐16-‐17-‐0
12256
95
85
73546
623
558
FT 3
Total
Run 5
FT 1
0-‐4-‐15-‐14-‐11-‐13-‐12-‐17-‐16-‐ 18-‐19-‐0
32371
270
242
FT 2
0-‐21-‐20-‐22-‐9-‐10-‐8-‐7-‐5-‐6-‐0
28408
264
237
FT 3
0-‐3-‐1-‐2-‐0
10048
81
72
70827
615
551
Total
Dari beberapa kali run program, didapatkan rute terbaik untuk pengisian menggunakan fuel truck berkapasitas 18000 L saja adalah hasil run 1 dan run 5 dengan total jarak dan biaya 12
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
yang terdapat pada tabel di atas. Utilitas rata-rata fuel truck yang digunakan untuk skenario ini adalah 74.6%. Berikut merupakan hasil run program untuk skenario menggunakan kobinasi fuel truck berkapasitas 25000 L dan 18000 L: Tabel 3 Hasil Run Program untuk Kombinasi FT 25000 L dan 18000 L FT 25000 L &18000 L
Run 1
Run 2
Rute
Jarak (m)
Waktu (menit)
Biaya (US$)
FT 1
0-‐15-‐13-‐14-‐11-‐12-‐17-‐1-‐61-‐18-‐20-‐ 21-‐4-‐1-‐3-‐2-‐0
42203
365
361
FT 2
0-‐5-‐6-‐7-‐8-‐9-‐22-‐19-‐0
30470
256
230
Total
72673
621
591
FT 1
0-‐10-‐9-‐20-‐22-‐21-‐17-‐18-‐16-‐19-‐11-‐ 14-‐15-‐12-‐13-‐0
41478
374
370
FT 2
0-‐2-‐4-‐3-‐1-‐6-‐5-‐8-‐7-‐0
25821
231
207
67299
605
577
Total Run 3
FT 1
0-‐20-‐21-‐22-‐9-‐10-‐8-‐7-‐5-‐6-‐3-‐2-‐1-‐4-‐0
36061
353
349
FT 2
0-‐18-‐17-‐16-‐19-‐12-‐11-‐15-‐13-‐14-‐0
27088
240
215
63149
593
564
Total
Run 4
FT 1
0-‐20-‐21-‐10-‐9-‐22-‐19-‐18-‐17-‐16-‐12-‐ 11-‐13-‐14-‐15-‐0
44290
382
378
FT 2
0-‐1-‐4-‐3-‐2-‐8-‐7-‐5-‐6-‐0
25821
231
207
70111
613
585
Total
Run 5
FT 1
0-‐2-‐3-‐1-‐4-‐15-‐12-‐13-‐14-‐11-‐20-‐21-‐ 22-‐9-‐10-‐0
41387
366
362
FT 2
0-‐5-‐6-‐8-‐7-‐19-‐18-‐16-‐17-‐0
31045
254
228
72432
620
590
Total
Dari beberapa kali run program, didapatkan rute terbaik untuk pengisian menggunakan kombinasi fuel truck berkapasitas 25000 L dan 18000 L adalah hasil run 3 dengan total jarak dan biaya yang terdapat pada tabel di atas. Utilitas rata-rata fuel truck yang digunakan untuk skenario ini adalah 93%. Dari hasil pengolahan data menggunakan 3 skenario penggunaan fuel truck di atas, bisa dilihat bahwa skenario yang memberikan biaya pengisian bahan bakar unit loader paling minimal adalah skenario pengisian menggunakan fuel truck berkapasitas 18000 L. Akan tetapi, skenario ini membutuhkan tiga fuel truck untuk melakukan pengisian dan memiliki 13
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
utilitas fuel truck yang rendah. Skenario menggunakan kombinasi fuel truck berkapasitas 25000 L dan 18000 L memberikan biaya pengisian yang sedikit lebih mahal dari skenario menggunakan fuel truck berkapasitas 18000 L. Akan tetapi, skenario ini hanya membutuhkan 2 fuel truck dan utilitas fuel truck yang digunakan juga tinggi. Pengisian bahan bakar unit loader yang ada di perusahaan saat ini masih dilakukan pada saat jam istirahat makan siang jam 12.00-13.00 dan tengah malam jam 24.00-01.00. Hal ini menyebabkan jumlah kendaraan yang dibutuhkan untuk mengisi bahan bakar unit loader lebih banyak karena time windows yang sangat sempit. Untuk pengisian bahan bakar unit loader saat ini, perusahaan bisa menggunakan 6 - 8 fuel truck. Penggunaan fuel truck sebanyak ini terjadi selain karena time windows yang sempit, juga karena pengisian bahan bakar unit loader saat ini masih digabung dengan pengisian bahan bakar ke pit stop. Hal ini tentunya membuat rute pengisian yang tidak optimal. Rute usulan yang didapat dari hasil optimasi program ini mencari rute yang paling efisien untuk pengisian bahan bakar unit loader jika perusahaan menerapkan sistem 24/7. Sistem 24/7 ini memungkinkan digunakannya fuel truck yang lebih sedikit karena time windows yang lebih lama. Time windows dari jadwal pengisian bahan bakar unit loader ini adalah selang waktu antar pengisian. Rute yang didapat dari program sekaligus menjadi urutan penjadwalan pengisian bahan bakar unit loader. Program yang dibuat untuk mencari rute dan jadwal pengisian bahan bakar unit loader yang optimal ini dirancang untuk bisa mengakomodasi adanya perpindahan posisi unit loader. Oleh karena itu, setiap adanya perubahan posisi loader beserta demand-nya masing-masing, maka perlu dilakukan update terhadap matriks jarak dan demand masing-masing loader di data Ms. Excel.
5. KESIMPULAN Berdasarkan penelitian optimasi rute dan jadwal pengisian bahan bakar unit loader menggunakan Algoritma Tabu Search, diperoleh kesimpulan sebagai berikut: •
•
•
Diperoleh suatu model rute dan jadwal pengisian bahan bakar unit loader dengan biaya yang optimal, bisa mengakomodasi perpindahan posisi unit loader, dan menghindari unit loader berhenti beroperasi karena kehabisan bahan bakar. Pengisian bahan bakar unit loader dilakukan setiap 12 jam dan pengisian ini bisa dilakukan pada jam berapa pun selama pengisian berikutnya dilakukan 12 jam kemudian. Dalam hal ini, urutan rute pengiriman sekaligus menjadi jadwal pengisian bahan bakar unit loader. Skenario pengisian bahan bakar unit loader yang memberikan hasil yang paling optimal adalah penggunaan kombinasi fuel truck berkapasitas 25000 L dan 18000 L jika dilihat dari segi total jarak dan utilitas fuel truck yang digunakan. Sedangkan jika dilihat dari segi biaya pengisian, skenario penggunaan fuel truck berkapasitas 18000 L memberikan biaya paling murah, tetapi skenario ini membutuhkan 3 fuel truck dan menghasilkan penggunaan fuel truck yang kurang optimal yang terlihat dari utilitas fuel truck yang rendah. Algoritma Tabu Search bisa digunakan untuk menyelesaikan masalah optimasi rute dan jadwal pengisian bahan bakar unit loader.
14
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
DAFTAR REFERENSI [1]
Diaz, Berbane Dorronsoro, 2004, “Vehicle http://neo.lcc.uma.es/vrp/vehicle-routing-problem/
[2]
Ballou, Ronald H. (1992). Business Logistics Management 4th ed. New Jersey: Prentice-Hall. Inc.
[3]
Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Philadelphia: Society for Industrial and Applied Mathematics.
[4]
J.-F. Cordeau and G. Laporte. (2002). Tabu Search Heuristics for the Vehicle Routing Problem. Les Cahiers du GERADG-2002-15
[5]
Bräysy, O. and Gendreau, M. (2001). Tabu Search Heuristics for the Vehicle Routing Problem with Time Windows. SINTEF Applied Mathematics, Research Council of Norway.
15
Perancangan Model ..., Febri Vabiono P, FT UI, 2013
Routing
Problem”,