1
I PENDAHULUAN Pada bagian awal bab ini, akan dijelaskan latar belakang dan tujuan penelitian yang dilakukan. Sementara itu pada bagian akhir bab ini akan diperlihatkan manfaat dari penelitian ini bagi perusahaan. 1.1 Latar Belakang Masalah transportasi dan distribusi produk dalam kehidupan sehari-hari dapat dimodelkan sebagai Vehicle Routing Problem (VRP). Model VRP akan menghasilkan sejumlah rute kendaraan untuk mengunjungi setiap konsumen. Setiap rute berawal dan berakhir pada tempat yang sama yang disebut depot. Selain itu, model VRP juga memastikan agar total permintaan pada suatu rute tidak melebihi kapasitas kendaraan yang beroperasi. Penggunaan model VRP diharapkan dapat meminimumkan total jarak tempuh dan jumlah kendaraan. Kendala waktu pada model VRP merupakan masalah yang rumit. Pada masalah tersebut, konsumen hanya melayani pengiriman produk pada selang waktu tertentu setiap harinya. Sebagai contoh, sebuah gudang hanya akan melayani pengiriman produk antara pukul 08.00 WIB sampai dengan pukul 15.00 WIB. Untuk memecahkan masalah tersebut digunakanlah Vehicle Routing Problem with Time Windows (VRPTW) yaitu model VRP dengan menambahkan kendala waktu. VRPTW terbagi menjadi dua kasus yaitu kasus hard time windows dan kasus soft time windows. Pada kasus hard time windows, pengiriman akan ditolak apabila tidak sesuai dengan waktu yang telah ditentukan oleh konsumen, sedangkan pada kasus soft time konsumen akan menerima windows pengiriman walaupun tidak sesuai dengan
waktu yang telah ditentukan sekaligus memberikan penalti atau biaya tambahan atas keterlambatannya. Pada penelitian ini model VRPTW dengan kasus soft time windows dipilih karena sesuai dengan masalah yang terjadi di lapangan. VRP sulit untuk dipecahkan karena merupakan gabungan antara masalah kapasitas (packing problem) dan masalah penentuan rute (salesman routing problem). Jika masalah yang dihadapi masih tergolong kecil, maka metode branch and bound dapat memberikan solusi terbaik dari masalah VRP. Jika masalahnya kompleks dan besar, salah satu cara untuk menyelesaikannya adalah dengan menggunakan metode heuristik. Dalam penelitian ini, metode heuristik akan digunakan untuk mencari solusi dari model VRPTW yang dihadapi. Solusi tersebut dapat dicari dengan bantuan software ILOG Dispatcher versi 2.1 dan ILOG Solver versi 4.4 yang dijalankan dengan Microsoft Visual C++ versi 6.0. 1.2 Manfaat Penelitian yang dilakukan memiliki manfaat yang berbeda bagi masing-masing level management pada perusahaan tersebut. Manfaat bagi top level management dan middle level management di perusahaan tersebut adalah mempermudah proses pengambilan keputusan. Dalam hal ini keputusan untuk meminimumkan biaya distribusi yang ditanggung oleh perusahaan, langkah yang dapat dilakukan adalah meminimumkan banyaknya kendaraan dan memaksimumkan banyaknya barang yang dibawa, sedangkan manfaat bagi low level management adalah dapat menentukan rute terpendek bagi setiap kendaraan.
II LANDASAN TEORI Dalam bab ini, akan dijelaskan beberapa metode yang digunakan dalam penelitian. Pertama akan dijelaskan tentang Traveling Salesman Problem (TSP) yang merupakan dasar dari Vehicle Routing Problem (VRP), kemudian akan diperlihatkan penggunaan metode heuristik untuk mencari solusi dari kasus VRP yang dihadapi pada.
2.1 Traveling Salesman Problem Dalam TSP, seorang salesman akan berangkat dari satu kota kemudian mengunjungi seluruh kota yang ada dan pada akhir perjalanannya salesman tersebut akan kembali ke kota awal atau depot. Tujuan dari TSP adalah menentukan rute yang melalui seluruh kota dan meminimumkan jarak.
2
Model TSP dapat dituliskan sebagai berikut: Variabel keputusan
xi , j =
1, jika kota ke - j dikunjungi setelah kota ke - i 0, selainnya
Fungsi objektif: m
min Z
= j=1
m
ci, j xi, j
(2.1)
i=1
Kendala-kendala: m
xi, j 1;
i 1,2,...,m
(2.2)
j 1
m
xi, j 1;
j 1, 2,..., m
(2.3)
i 1
x j L
i L
i, j
| L | 1; L {1,2,..., m }
xi , j {0,1}; i, j 1,2,..., m
(2.4) (2.5)
Fungsi objektif dalam TSP (persamaan 2.1) adalah meminimumkan jarak yang ditempuh dan mengunjungi setiap kota yang ada, dengan ci,j adalah jarak dari kota i ke kota j dan xi,j benilai 1 jika rute dari kota ke-i menuju kota ke-j digunakan dan bernilai 0 jika selainnya. Kendala (2.2) dan (2.3) memastikan bahwa setiap kota dikunjungi tepat satu kali, sedangkan kendala (2.4) memastikan tidak terdapat subtour pada rute tersebut. Pada kendala (2.5) diperlihatkan bahwa xi,j merupakan varibel biner untuk setiap i dan j yang ada (Hoffman & Padberg 2009).
Dalam perkembangannya, TSP memiliki beberapa variasi, yaitu: Traveling Salesman Problem with Time Windows (TSPTW) yang merupakan TSP dengan tambahan waktu pelayanan di setiap kota dan m-Traveling (m-TSP) yang Salesman Problem menggunakan sejumlah salesman untuk mengunjungi seluruh kota. 2.1.1 Traveling Salesman Problem with Time windows Traveling Salesman Problem with Time (TSPTW) merupakan Windows pengembangan dari TSP. Pada TSPTW rute yang ditempuh memiliki tambahan kendala waktu pelayanan (time windows) untuk masing-masing konsumen. Time windows pada masing-masing konsumen dapat berbeda satu sama lain, tetapi memiliki karakteristik yang sama yakni berupa selang waktu. Time windows [a1, bi] menunjukkan selang waktu pelayanan pada konsumen i, dengan ai sebagai batas awal dan bi sebagai batas akhir. Model untuk TSPTW tidak berbeda dengan model TSP di atas, dengan tambahan beberapa kendala:
ai Ti bi ; i 1,..., m i , j 1, ..., m Ti ti , j T j ; i j
(2.6) (2.7)
Pada (2.6) waktu pelayanan (Ti) berada di antara batas awal (ai) dan batas akhir (bi) dari time windows, sedangkan pada persamaan (2.7) dipastikan pelayanan di kota j (Tj) merupakan waktu tempuh antara kota i dan kota j (ti,j) ditambahkan dengan waktu pelayanan di kota i (Ti) (Sutapa et al. 2003).
Konsumen
Rute
Gambar 1 Contoh rute dalam Traveling Salesman Problem (TSP) .
3
2.1.2 m-TSP m-TSP adalah salah satu variasi dari TSP, dimana terdapat sebanyak m salesman mengunjungi seluruh kota, tetapi setiap kota hanya dapat dikunjungi oleh tepat satu salesman saja. Tiap salesman berawal dari suatu depot dan pada akhir perjalannya juga harus kembali ke depot tersebut. Tujuan dari m-TSP adalah meminimumkan total jarak dari setiap rute. Masalah m-TSP dikenal juga sebagai Vehicle Routing Problem (VRP), dimana sebuah kota diasosiasikan sebagai sebuah konsumen dan tiap kendaraan memiliki kapasitas tertentu. Total jumlah permintaan dalam suatu rute tidak boleh melebihi kapasitas dari kendaraan yang beroperasi (Larsen 1999). 2.2 Vehicle Routing Problem Masalah yang berkaitan dengan pencarian rute yang optimal untuk kendaraan dari satu depot dan melayani sejumlah konsumen disebut VRP. Dalam prakteknya VRP banyak digunakan pada masalah distribusi logistik. Berikut adalah karakteristik dari model VRP. Terdapat satu depot (dilambangkan dengan O) yang memiliki sebanyak k kendaraan untuk melakukan pengiriman, dengan kapasitas setiap kendaraan sebesar C. Kendaraan tersebut mengirimkan permintaan sebesar qi untuk n konsumen, dengan i=1,2,3,…,n. Jarak yang ditempuh setiap kendaraan sebisa mungkin adalah jarak yang paling minimum dengan ci,j adalah biaya pengiriman dari konsumen i ke konsumen j, dengan i= 1,2,…,n dan j=1,2,…,n. Jarak antarkonsumen bersifat simetris atau dapat ditulis sebagai ci,j = cj,i sedangkan jarak antara tempat yang sama bernilai nol atau ci ,i 0 . Solusi yang dihasilkan merupakan anggota {R1 ,..., Rk } yang mengirimkan n dari permintaan melalui k rute yang tersedia dan permintaan yang dikirim tidak melebihi kapasitas kendaraan yang tersedia untuk setiap rute (Machado et al. 2002).
Tujuan dari VRP adalah menentukan sejumlah rute untuk melakukan pengiriman pada setiap konsumen, dengan mengikuti beberapa ketentuan, antara lain: (1) setiap rute berawal dan berakhir di depot, (2) setiap konsumen dikunjungi tepat satu kali oleh tepat satu kendaraan, (3) jumlah permintaan tiap rute tidak melebihi kapasitas kendaraan dan (4) meminimumkan biaya perjalanan (Cordeau et al. 2002). Model VRP dapat direpresentasikan sebagai berikut:
min Z
n
n
l
ci, j xik, j
(2.8)
j 1 i 1 k 1
Kendala-kendala Konsumen n
l
xik, j 1; i 1 k 1 n
(2.9)
i 2, 3, ..., n
(2.10)
l
xik, j 1; j 1 k 1
j 2, 3,..., n
Depot n
x1,k j 1; j 2 n
xik,1 1; i 2
k 1, 2,..., l
(2.11)
k 1, 2, ..., l
(2.12)
Kekontinuan rute n
n
k 1, 2,..., l
i 2
i 2
u 1, 2, ..., n
xik,u xuk, j ;
(2.13)
Kapasitas n
n
qi xik, j Ck ; i 1 j 1
xik, j {0,1};
k 1, 2,..., l
i , j 1,2,...,n k 1,...l
Konsumen
Gambar 2 Contoh rute dalam Vehicle Routing Problem (VRP).
(2.14)
(2.15)
4
Fungsi objektif dari VRP (2.8) adalah meminimumkan total biaya perjalanan, dengan ci,j adalah biaya perjalanan dari konsumen i menuju konsumen j. Variabel keputusan
xik, j bernilai 1 jika rute dari
konsumen i menuju konsumen j dilayani oleh kendaraan k dan bernilai nol jika selainnya. Pada kendala (2.9) dan (2.10) dipastikan tepat satu kendaraan yang datang dan pergi dari konsumen i, sedangkan kendala (2.11) dan (2.12) memastikan bahwa tepat satu kendaraan yang pergi dan tiba di depot untuk satu rute. Kendala (2.13) memastikan kekontinuan rute dari setiap kendaraan yang beroperasi. Kendala (2.14) memastikan agar total permintaan (qi) pada satu rute tidak melebihi kapasitas kendaraan (Ck) yang beroperasi pada rute tersebut (Kritikos & Ioannou 2004). VRP adalah masalah optimisasi kombinatorial yang sulit, karena merupakan gabungan dari masalah kapasitas (packing problem) dan masalah rute kendaraan (traveling salesman problem). Pada VRP, hanya tipe masalah kecil dan sederhana yang dapat dicari solusi optimalnya. Hingga saat ini bila masalah VRP yang dihadapi relatif besar dan kompleks maka waktu yang dibutuhkan untuk mencari solusi optimal masalah tersebut relatif lama. Berdasarkan beberapa penelitian sebelumnya, nilai optimal dari fungsi objektif sulit untuk didapat dengan menggunakan exact algorithm (contohnya: branch and dan dynamic programming). bound Pendekatan exact algorithm dinyatakan tidak cukup baik untuk masalah yang dihadapi (VRP yang besar dan kompleks), sehingga dikembangkan metode heuristik sebagai salah satu alternatif untuk menyelesaikan masalah tersebut (Cordeau et al. 2002). 2.3. Vehicle Routing Problem with Time Windows (VRPTW) VRP dengan tambahan kendala waktu pelayanan disebut sebagai Vehicle Routing Problem with Time Windows (VRPTW). Kendala waktu adalah selang waktu tertentu sehingga setiap kendaraan dapat memberikan pelayanan pada konsumen. Biasanya selang waktu tersebut berbeda pada setiap konsumen (Hideki et al, 2006 dalam Kang et al, 2007). Dalam perkembangannya VRPTW dibagi menjadi Vehicle Routing Problem with Hard Time Windows (VRPHTW) dan Vehicle Routing Problem with Soft Time Windows (VRPSTW).
Dalam VRPHTW, konsumen hanya dapat dilayani selama selang waktu yang telah ditentukan. Sedangkan pada VRPSTW konsumen dapat dilayani setiap saat, tetapi bila melewati waktu yang ditentukan akan dikenakan biaya tambahan atau penalti (Kang. et al. 2007). Seperti halnya pada VRP, fungsi objektif bagi VRPTW adalah meminimalkan biaya perjalanan untuk semua kendaraan. Kendala yang digunakan pun sama seperti model VRP (2.9) - (2.15), tetapi perlu ditambahkan beberapa kendala yang berhubungan dengan time windows. Kendala tersebut, antara lain: k
t j ti fi ti , j M (1 xi , j );
(2.16)
i , j 2, 3,..., n; k 1, ..., l ; ai ti bi ; i 1, ..., n
(2.17)
ti 0; i 1,..., n
(2.18)
Kendala (2.16) memastikan waktu kedatangan kendaraan di konsumen j (tj) selalu lebih besar dari waktu kedatangan kendaraan di konsumen i (ti), dengan fi merupakan waktu service di konsumen i dan ti,j adalah waktu tempuh dari konsumen i menuju konsumen j, sedangkan M (disebut big-M) merupakan bilangan yang relatif besar, k sehingga jika M (1 xi , j ) besar maka rute dari i ke j tidak akan ditempuh dan sebaliknya. Kendala berikutnya (2.17) memastikan kedatangan kendaraan di konsumen i berada di antara selang waktu yang telah ditentukan, dengan batas awal ai dan batas akhir bi, sedangkan kendala terakhir (2.18) memastikan agar waktu kedatangan kendaraan ke setiap konsumen selalu positif (Larsen 1999). Pada penelitian ini akan digunakan VRPSTW, karena serupa dengan masalah yang ada di lapangan. 2.4 Metode Heuristik Penggunaan metode branch and bound untuk mencari solusi VRP yang memiliki banyak kota (lebih dari 50 kota) membutuhkan waktu komputasi yang lama. Alasan tersebut menjadi sebab dikembangkannya metode heuristik. Metode heuristik dapat memberikan solusi lebih cepat daripada metode branch and bound, tetapi tidak ada jaminan solusi yang dihasilkan optimal. Solusi dari metode heuristik didapat selain dengan cara trial and error juga dengan pendekatan secara intuitif (Winston 2004).
5
Dalam metode heuristik untuk masalah VRP dikenal adanya dua fase pendekatan untuk memecahkan masalah, yaitu route constructing sebagai fase pertama dan route improvement pada fase kedua. Pada penelitian ini metode nearest addition heuristic akan digunakan untuk mencari solusi pada fase pertama. Selanjutnya metode 2-opt, metode or-opt, metode relocate, metode exchange dan metode cross digunakan untuk memperbaiki solusi yang telah ada. 2.4.1 Nearest Addition Heuristic Metode nearest addition heuristic dimulai dengan menentukan banyaknya kendaraan yang tersedia di depot. Lokasi yang terdekat dengan depot akan dikunjungi pertama kali, kemudian lokasi yang dikunjungi selanjutnya adalah lokasi yang memiliki jarak terdekat dengan lokasi konsumen pertama, demikian seterusnya hingga kapasitas kendaraan atau time windows terpenuhi. Jika kapasitas kendaraan atau time windows telah dicapai maka kendaraan tersebut harus kembali ke depot. Kemudian jalankan kendaraan berikutnya dengan aturan yang sama seperti kendaraan pertama, sampai seluruh lokasi dikunjungi oleh kendaraan yang tersedia di depot. Algoritmenya sebagai berikut: 1) pandang kendaraan sebagai w, 2) mulai sebuah rute dari depot bagi kendaraan w, 3) temukan konsumen (v) yang terdekat dari posisi terakhir w. Jika tidak dimungkinkan untuk melakukan kunjungan tanpa melanggar kendala yang ada akhiri rute kendaraan w, pilih kendaraan lain dan lakukan lagi langkah 2. Jika masih terdapat konsumen yang belum dikunjungi maka gagal, 4) tambahkan depot pada akhir rute, 5) lakukan langkah 3. (ILOG, 2002). Solusi dari metode nearest addition dapat diperbaiki dengan heuristic menggunakan beberapa metode heuristik lainnya, antara lain: metode 2-opt, metode oropt, metode relocate, metode exchange dan metode cross. 2.4.2 Metode 2-opt Pada dasarnya metode 2-opt ialah memindahkan dua jalur pada rute yang ada, kemudian menghubungkan kembali jalur tersebut dengan pasangan konsumen yang berbeda. Sebagai catatan, metode 2-opt hanya
dapat dilakukan jika rute baru yang dihasilkan lebih baik daripada rute awal (Nilsson 2003). Algoritmenya, sebagai berikut: 1) pandang satu rute untuk satu kendaraan, 2) hapus 2 jalur yang menghubungkan 4 konsumen yang berbeda, cobalah untuk menghubungkan kembali keempat konsumen dengan pasangan yang berbeda, 3) jika biaya berkurang dan tidak melanggar kendala yang ada kembali ke langkah (2), 4) selesai. (ILOG, 2002).
Gambar 3 Contoh metode 2-Opt. Rute yang dihasilkan dapat disebut sebagai 2-optimal atau 2-opt, jika metode 2-opt digunakan pada setiap rute yang ada sampai tidak dimungkinkan lagi penggunaan metode tersebut. Metode or-opt identik dengan metode 2-opt, tetapi jumlah jalur yang dapat dihapus dan ditambahkan lebih dari 2 jalur. 2.4.3 Metode Relocate Pada metode relocate, sebuah tempat dalam satu rute dapat dipindahkan urutan kunjungannya. Dengan syarat biaya rute berkurang dan tidak melanggar kendala yang ada maka hal tersebut dapat dilakukan. Metode relocate ini dapat memindahkan sebuah kunjungan pada rute yang sama ke posisi yang berbeda. Seperti terlihat pada Gambar 4 dimana jalur yang ditempuh semula adalah (a0, a1), (a1, a2), (a2, b0) dan (b0, b1) berubah menjadi (a0, a2), (a2, b0), (b0, a1) dan (a1, b1).
Gambar 4 Contoh metode relocate pada satu rute. Metode relocate juga dapat memindahkan sebuah kunjungan dari satu rute dan menambahkan kunjungan tersebut ke rute lainnya. Seperti terlihat pada Gambar 5 dimana kunjungan menuju a1 yang semula berada pada rute (a0, a1), (a1, a2) dipindahkan ke rute (b0, b1). Metode tersebut merubah rute
6
yang ditempuh menjadi rute (a0, a2) dan rute (b0, a1), (a1, b1).
Gambar 6 Contoh metode exchange pada satu rute.
Gambar 5 Contoh metode relocate pada dua rute. 2.4.4 Metode Exchange Pada metode exchange, dua tempat dapat saling dipertukarkan urutan kunjungannya. Metode ini dapat diterapkan baik pada satu rute maupun dua rute kendaraan. Selama perubahan yang terjadi tidak melanggar kendala yang ada dan dapat mengurangi biaya yang dikeluarkan. Pada satu rute kendaraan, dua kunjungan yang berbeda dapat dipertukarkan urutannya. Dari Gambar 6 terihat bahwa metode exchange mempertukarkan kunjungan menuju a1 dan b1. Sehingga rute yang semula (a0, a1), (a1, a2), (a2, b0), (b0, b1) dan (b1, b2) berubah menjadi (a0, b1), (b1, a2), (a2, b0), (b0, a1) dan (a1, b2).
Metode exchange juga dapat di pergunakan pada dua rute kendaraan, seperti terlihat pada Gambar 7 dimana a1 dari rute (a0, a1), (a1, a2) dipertukarkan dengan b1 dari rute yang berbeda, (b0, b1), (b1, b2). Metode exchange ini merubah rute semula menjadi rute (a0, b1), (b1, a2) dan rute (b0, a1), (a1, b2).
Gambar 7 Contoh metode exchange pada dua rute. Kasus pada Gambar 7 disebut inter-route exchange. Sementara itu metode exchange yang diterapkan pada satu rute disebut intraroute exchange (Caric et al. 2008).
III METODE PENELITIAN 3.1 Waktu dan Lokasi Penelitian dilakukan di PT Nippon Indosari Corpindo (PT NIC), pada departemen Supply Chain Management (SCM). Kegiatan ini memakan waktu dua minggu, dimulai pada Senin, 27 Oktober sampai dengan Jumat, 7 November 2008. 3.2 Teknik Pengumpulan Data Kombinasi antara data sekunder dan data primer digunakan untuk mendukung kesempurnaan dari penelitian ini. Selain itu pengumpulan data melalui wawancara dengan pihak yang terkait juga dilakukan untuk memahami tentang proses distribusi pada perusahaan tersebut. 3.3 Ruang Lingkup Penelitian Dalam penelitian ini, pembahasan akan dibatasi pada proses distribusi untuk saluran retail/outlet (RO) di daerah Bekasi dan sekitarnya. Saluran RO dipilih karena jumlahnya yang terbesar dibandingkan dengan
saluran lain yang ada. Selain itu, saluran RO merupakan saluran yang memliki rantai distribusi paling pendek dibandingkan dengan saluran lain yang ada. 3.4. Pengolahan Data Setelah mendapatkan informasi yang dibutuhkan, penelitian dilanjutkan dengan memformulasikan masalah distribusi yang ada sebagai sebuah model VRP. Selanjutnya, digunakan program ILOG Dispatcher versi 2.1 dan ILOG Solver versi 4.4, yang dijalankan dalam Microsoft Visual C++ versi 6.0, sebagai alat untuk mencari solusi dari model VRP yang dihadapi. Data yang diperoleh dari kegiatan tersebut, antara lain: letak konsumen, permintaan konsumen dan waktu bongkar - muat di tempat konsumen. Sedangkan diasumsikan kecepatan kendaraan konstan, waktu buka tutup gudang konsumen adalah seragam yakni pada pukul 06.00 sampai dengan pukul 16.00,
