Pendekatan Goal Programming untuk Penentuan Rute Kendaraan pada Kegiatan Distribusi (A Goal Programming Approach to Vehicle Routing Problems of Distribution) Oleh: VINAYANTI EKA RAHMAWATI
(1207 100 020)
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2011
DAFTAR ISI
PENDAHULUAN
TINJAUAN PUSTAKA
METODOLOGI PENELITIAN
PENGEMBANGAN MODEL DAN PENGUMPULAN DATA
HASIL DAN PEMBAHASAN
KESIMPULAN DAN SARAN
PENDAHULUAN
LATAR BELAKANG •Kegiatan produksi dan distribusi adalah fungsi operasional terpenting dalam supply chain
• Penentuan rute salah satu kegiatan penyampaian barang
utama dalam alur
• Biaya dan waktu menjadi unsur utama dalam perencanaan kegiatan distribusi • Pendekatan metode goal programming digunakan untuk membuat sistem penentuan rute kendaraan pada kegiatan distribusi
Rumusan masalah
1
2
• Bagaimana memodelkan rute kunjungan kendaraan ke SPBU kedalam goal programming?
• Bagaimana menyelesaikan model goal programming sehingga didapatkan rute kunjungan kendaraan ke SPBU yang optimal?
Batasan masalah • Model penentuan rute kunjungan menggunakan goal programming. • Customer yang menjadi objek penelitian adalah SPBU di Surabaya.
• Kendaraan yang digunakan satu jenis
• Data yang diangkat dalam penelitian ini dibatasi hanya pada produk Pertamina BBM jenis premium.
asumsi • Jumlah permintaan SPBU konstan
• Tidak terdapat batasan kelas jalan • SPBU dapat dikunjungi satu kali dalam sehari • Kendaraan selalu tersedia
TUJUAN & MANFAAT
Tujuan
Manfaat
• Untuk memodelkan rute kunjungan kendaraan ke SPBU kedalam goal programming. • Untuk menyelesaikan model goal programming sehingga didapatkan rute kunjungan kendaraan ke SPBU yang optimal. • Sebagai rekomendasi pada perusahaan dalam menentukan kebijakan lebih lanjut. • Mendapatkan peluang untuk dapat memecahkan dan mencari solusi permasalahan-permasalahan di perusahaan dari sudut pandang akademis.
TINJAUAN PUSTAKA
PERMASALAHAN DISTRIBUSI
• Pada perusahaan nonproduksi, kegiatan distribusi menjadi yang paling utama dalam alur penyampaian barang hingga sampai ke tangan pelanggan. • PT. Pertamina selama ini menjalankan kegiatan distribusi yaitu berupa kegiatan pengiriman bahan bakar minyak ke SPBU. • Kegiatan penentuan rute kendaraan pada kegiatan distribusi masih dijalankan secara manual.
KONSEP VEHICLE ROUTING
PROBLEMS
Vehicle routing problem
adalah permasalahan bagaimana menentukan sebuah rute yang terdiri atas beberapa lokasi tujuan. Lokasi tujuan tersebut tersebar secara geografis dan memiliki jarak yang berbeda-beda. Akan disusun sebuah rute kunjungan kendaraan yang berawal dari depot dan akan berakhir di depot kembali. Tujuannya adalah untuk meminimumkan total jarak dari semua rute.
GOAL PROGRAMMING
Goal programming adalah salah satu metode matematis yang dipakai sebagai dasar mengambil keputusan untuk menganalisis dan membuat solusi permasalahan yang melibatkan banyak tujuan sehingga diperoleh alternatif pemecahan masalah yang optimal. Goal programming merupakan perluasan dari model pemrograman linear (linear programming).
GOAL PROGRAMMING (Lanjutan)
Pendekatan dasar dari goal programming adalah untuk menetapkan suatu tujuan yang dinyatakan dengan angka tertentu untuk setiap tujuan, merumuskan suatu fungsi tujuan, dan kemudian mencari penyelesaian dengan meminimumkan jumlah (tertimbang) penyimpangan penyimpangan dari fungsi tujuan (Hillier dan Lieberman, 1990).
GOAL PROGRAMMING (Lanjutan)
Beberapa istilah yang digunakan dalam goal Programming 1. Variabel keputusan (decision variabel) 2. Nilai sisi kanan (right hand sides values) 3. Koefisien teknologi (technology coefficient) 4. Variabel deviasional (penyimpangan) 5. Fungsi tujuan 6. Fungsi tujuan mutlak 7. Prioritas
Model umum goal programming Misalnya dalam perusahaan terdapat keadaan: Z ST
C1 X1
C2 X 2
C3 X 3
...
Ci X i
: a1 X1
a2 X 2
a3 X 3
...
b1 X1
b2 X 2
b3 X 3
...
ai X i bi X i
Yi Di
Dimana: Z : Fungsi Tujuan ST : Fungsi Pembatas Xi : Jumlah produk i yang dikirim Yi : Jumlah tenaga kerja yang tersedia Di : Jumlah bahan baku yang tersedia
Metode penyelesaian goal programming
Maka, hal ini dapat diselesaikan dengan model goal programming sebagai berikut:
Min Z
P1 d1
d1
P2 d2
d2
n ai X i
di
di
Yi
bi X i
di
di
Di
i 1 n i 1
Dimana: Pi=Tujuan-tujuan yang ingin dicapai di-=Penyimpangan negatif di+=Penyimangan positif
... Pi di
di
Metode penyelesaian goal programming
Ada 2 metode dalam menyelesaikan permasalahan goal programming. Kedua metode sama-sama menggabungkan tujuan yang banyak menjadi tujuan tunggal. Kedua metode tersebut adalah: 1.Metode preemptive 2.Metode non-preemptive (pembobotan)
Metode penyelesaian goal programming (lanjutan) Metode preemptive
Pada metode preemptive, pembuat keputusan harus membuat prioritas (rangking) terhadap tujuan yang ingin dicapai sesuai dengan tingkat kepentingan masing-masing tujuan. Meminimumkan Gi, i= 1,2…,n Fungsi Tujuan: Meminimumkan Gi= p1(prioritas tertinggi) . . Meminimumkan Gn= pn (prioritas terendah)
Metode penyelesaian goal programming (lanjutan) Metode non-preemptive
Pada metode ini masing-masing koefisien pada fungsi tujuan dapat diberikan bobot yang berbeda-beda sesuai dengan kepentingan. Misalkan dalam model goal programming terdapat n tujuan dan pada tujuan ke-i diberikan fungsi sebagai berikut : Meminimumkan G , i= 1,2,...,n Bentuk kombinasi dari fungsi tujuan dengan metode pembobotan adalah : Meminimumkan Z w1G1 w2G2 ... wnGn
Menghitung jarak Metode euclidean
Karena koordinat SPBU berupa longitude dan latitude, maka perhitungan jarak antar dua titik ini mengacu pada jarak antar dua titik di bumi (titik dengan sistem longitude dan latitude) dengan persamaan berikut (Simchi-Levi, 1997):
Dab
69
lona
lonb 2
lata
latb 2
METODOLOGI PENELITIAN 1. Pengumpulan Data Data yang digunakan merupakan data sekunder yang diperoleh dari data tugas akhir Deni Irawan, 2010. Data meliputi data SPBU di Surabaya, data longitude dan latitude letak SPBU di Surabaya serta data permintaan SPBU. 2. Menghitung jarak antar SPBU, waktu perjalanan dan biaya variabel tiap SPBU. 3. Perhitungan manual konfigurasi rute, waktu dan biaya minimum. 4. Merancang model optimasi penentuan rute. 5. Verifikasi model. 6. Running komputasi. 7. Penarikan kesimpulan.
Studi Literatur Studi Lapangan
Tahap Identifikasi Masalah
METODOLOGI PENELITIAN (lanjutan)
Pengumpulan Data: 1. Gambaran umum sistem pemesanan dan distribusi existing. 2. Data jumlah dan lokasi SPBU di Surabaya yang disuplai oleh ISG Pertamina. 3. Spesifikasi mobil tanki yang digunakan untuk pendistribusian.
Formulasi dan Pengembangan Model
Penerjemahan Model ke Bahasa LINGO
No
Verifikasi
Yes
Running Komputasi
Tahap Pengumpulan Data dan Pengembangan Model
Analisa dan Interpretasi
Tahap Analisa, Interpretasi, dan Kesimpulan Kesimpulan dan Saran
Gambar 3. Flowchart Metodologi Penelitian
PENGEMBANGAN MODEL DAN PENGUMPULAN DATA Pembuatan model disini yaitu pembuatan model matematik rute kunjungan dengan menggunakan pendekatan goal programming. Model matematik rute kunjungan dibuat berdasarkan model yang dibuat oleh Calvete, H.I., dkk (2007) tetapi tidak diaplikasikan secara langsung karena memerlukan perubahan-perubahan dari model tersebut agar sesuai dengan kondisi nyata.
Pengembangan model
Variabel keputusan
X ij
1, jika kendaraanmengunjungi SPBU i ke j 0, untuk yang lain
Pengembangan model
Fungsi tujuan
Pada tugas akhir ini fungsi tujuan yang diselesaikan meliputi empat bagian. Tiga diantara empat bagian tersebut merupakan fungsi tujuan mutlak. Prioritas pencapaian dari fungsi tujuan ini berada pada urutan pertama. Sedangkan fungsi tujuan yang keempat adalah variabel deviasi yang merupakan pelanggaran terhadap kendala. Minimumkan:
Z
d1
d2
d3
d4
d4
Pengembangan model
Batasan-batasan
1. Batasan 1 Batasan 1 merupakan batasan model terhadap fungsi tujuan mutlak. Batasan ini memiliki penyimpangan positif dan atau negatif bernilai nol.
d ij xij d1 0 (i , j ) A
Persamaan ini menjamin bahwa rute yang akan terbentuk terdiri dari rute kunjungan SPBU dengan jarak antar SPBU yang paling minimum.
Pengembangan model (lanjutan)
t ij xij i, j
d2
0
A
Persamaan menjamin bahwa waktu perjalanan yang ditempuh kendaraan untuk mengunjungi rute tertentu adalah paling minimum.
cij xij i, j
d3
0
A
Persamaan menjamin bahwa biaya perjalanan pada kunjungan rute adalah yang paling kecil.
Pengembangan model (lanjutan)
2. Batasan 2 n
n
qi i 2
xij
Vk
d4
d4
0
j 1
Batasan 2 merupakan batasan model terhadap variabel deviasi yang pada fungsi tujuan akan diminimumkan nilainya. Batasan ini merepresentasikan bahwa total permintaan dari SPBU pada rute tertentu tidak melebihi kapasitas kendaraan yang akan mengunjungi.
Pengembangan model (lanjutan)
3. Batasan 3 n
n
xij
1
x ji
1
i 1 j 2 n
n
i 1 j 2
Batasan 3 merupakan batasan model yang menjamin bahwa hanya ada satu kendaraan yang akan mengunjungi SPBU.
Pengembangan model (lanjutan)
4. Batasan 4 88
xii
0
i 2
Batasan 4 mensyaratkan untuk setiap SPBU, bahwa kendaraan tidak akan mengunjungi SPBU ke SPBU itu sendiri.
Pengembangan model (lanjutan)
5. Batasan 5 n
x1 j
1
j 2
n
xi1 i 2
1
Batasan 5 menjamin bahwa kendaraan akan berangkat dari depot dan akan kembali ke depot.
Pengumpulan data
1. Data SPBU di Surabaya Di Surabaya terdapat 88 Stasiun pengisian Bahan Bakar Umum (SPBU) atau sekitar 2,2 % dari total seluruh SPBU yang dilayani. Objek penelitian ini adalah 20 SPBU. 2. Koordinat SPBU Koordinat SPBU diperoleh dari google earth dalam bentuk koordinat longitude dan latitude yang masing-masing menunjukkan koordinat lintang dan bujur di bumi. 3. Demand Rate SPBU untuk Bahan Bakar Jenis Premium Angka permintaan SPBU disebut juga dengan demand rate. Pada penelitian ini digunakan demand SPBU yang besar kapasitas demand adalah 8 KL.
Pengolahan data
1. Perhitungan Jarak antar SPBU Jarak antar 2 SPBU akan dihitung dengan menggunakan metode Euclidian 2. Perhitungan Waktu Perjalanan untuk menghitung waktu perjalanan dari depot ke SPBU dan waktu antar SPBU adalah dengan melakukan pembagian antara jarak dibagi dengan kecepatan rata-rata. 3. Perhitungan Biaya Perjalanan Biaya perjalanan akan dihitung berdasarkan persamaan berikut: Total JarakTempuh k c ij
Kendaraank x H arg a BahanBakar / Liter RatioKebutuhanBahan Bakar Kendaraank
FORMULASI LINGO
Model akan disimulasikan dengan menggunakan software LINGO.11. Untuk itu model akan diterjemahkan terlebih dahulu ke dalam bahasa LINGO.
HASIL DAN PEMBAHASAN 1. Verifikasi Model Verifikasi model dilakukan dengan membandingkan hasil perhitungan manual dengan hasil perhitungan software. Apabila hasil yang diperoleh sama dengan hasil perolehan komputasi, maka dapat dikatakan model verified. Perhitungan manual dilakukan dengan mencoba semua kemungkinan dari variabel keputusan. Untuk perhitungan manual digunakan data 3 SPBU. Hasil perhitugan manual 2. Hasil Komputasi Digunakan software LINGO 11.0 untuk mencari solusi optimal dari penyelesaian. Output dari penyelesaian ini didapatkan hasil rute yang terbentuk, jarak minimum, waktu, dan biaya perjalanan.
Gambar 5.1 LINGO Solver Status dari Uji Verifikasi
Gambar 5.2 Solution Report dari Uji Verifikasi
Running komputasi Penyelesaian model yang telah dibangun dengan software LINGO membutuhkan waktu yang sangat lama dan tidak praktis dari segi waktu komputasi apabila diselesaikan dalam jumlah besar. Selain itu terdapat batasan variabel sehingga running komputasi hanya dapat dilakukan pada sample yang kecil. Dari hasil percobaan yang dilakukan, penyelesaian 88 SPBU sekaligus belum memiliki penyelesaian global. Berdasarkan kondisi tersebut, penelitian ini mengijinkan pencapaian solusi sub-optimal untuk problem. Untuk pengelompokan SPBU digunakan teknik clustering K-means dengan program Matlab menggunakan ukuran dissimilarity berupa jarak yang dihitung dengan metode Euclidean. Jumlah cluster yang diinginkan sebanyak lima cluster. Selain itu penelitian ini dibatasi pada SPBU dengan demand rate sebesar 8 KL sehingga terdapat 20 objek yang digunakan.
Running komputasi
Hasil Running
KESIMPULAN DAN SARAN KESIMPULan •Dengan menggunakan metode pendekatan goal programming, dapat diperoleh model penentuan rute kunjungan kendaraan pada studi kasus SPBU yang dilayani oleh PT. Pertamina Surabaya.. •Model yang didapat dapat membentuk rute dengan jarak minimum sehingga dapat mempersingkat waktu kunjungan dan dapat meminimumkan total biaya pengiriman. Selain itu model juga telah memenuhi fungsi kendala yang dimiliki perusahaan.
KESIMPULAN DAN SARAN saran 1. Perencanaan penentuan rute dapat dikembangkan untuk kasus kendaraan multikapasitas. 2. Penggunaan model penentuan rute goal programming dapat menjadi alternatif bagi manajemen perusahaan dalam menentukan rute optimal pada kegiatan distribusi di Pertamina. 3. Bagi peneliti selanjutnya disarankan untuk melakukan penelitian pada kasus dimana terdapat batasan kelas jalan.
DAFTAR PUSTAKA Calvete, H.I., et al. 2007. A Goal Programming Approach to Vehicle Routing Problems With Soft Time Windows. European Journal of Operational Research 177 (2007) 1720-1733. Kurniawan, N.D. 2008. Penentuan Rute Pengiriman Barang dan Pengalokasian Armada di Bagian Distribusi PT. Dua Kelinci Pati. Tugas Sarjana. Universitas Sumatera Utara. Irawan, Deni. 2010. Pengembangan Model Periodic Inventory Routing Problem untuk Penjadwalan Truk Tangki Multi Kapasitas (Studi Kasus: ISG PT. PERTAMINA UPms V Surabaya). Tugas Akhir. Teknik Industri ITS. Megasari, Kartika. 2010. Goal Programming untuk Perencanaan Produksi Agregat dengan Kendala Sumber Daya. Tugas Akhir. Metematika ITS. Taha, Hamdy A, 2003. Operations Research: An Introduction Seventh Edition. Prentice Hall, Pearson Education, Inc, Upper Saddle River, New Jersey.
DAFTAR PUSTAKA Desrosiers, J, et al, 1995. Time Constrained Routing and Scheduling. Handbooks in OR & MS Vol. 8, Chapter 2, Elsevier Science B. V. Sembiring, Anita, C. 2008. Penentuan Rute Distribusi Produk yang Optimal dengan Menggunakan Algoritma Heuristik pada PT. Coca Cola Bottling Indonesia Medan. Tugas Sarjana. Universitas Sumatera Utara. Tamiz, M, et al. 1998. Goal programming for decision making: An overview of the current state-of-the-art. European Journal of Operational Research 111 (1998) 569-581. Ballou, H. Ronald. 1999. Business Logistic Management. New Jersey: Prentice-Hall: United State. pp. 199. Chen Z-L. 2004. Integrated Production and Distribution Operations: Taxonomy, Models, and Review. In: Simchi-Levi D, Wu D, Chen Z-L, editors. Handbook of Quantitative Supply Chain Analysis: Modelling in the E-Business Era. Boston, MA: Academic Publishers, Kluwer; 2004. p. 711–46.
TERIMA. KASIH
