“PENERAPAN METODE CROSS ENTROPY DALAM PENYELESAIAN CAPACITATED VEHICLE ROUTING PROBLEM (Study Kasus : Distribusi Koran Jawa Pos Surabaya)” Gladiez Florista Rera dan Budi Santosa Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected]
Abstrak Capacitated Vehicle Routing adalah satu jenis permasalahan penentuan rute terdekat yang dibatasi dengan kapasitas kendaraan angkut. CVRP dapat diselesaikan dengan menggunakan exact optimization seperti integer programming, akan tetapi dalam penyelesaiannya diperlukan waktu komputasi yang sangat lama, terutama untuk problem berukuran besar (jika jumlah titik yang dilayani cukup banyak) dan menggunakan pendekatan heuristik, yaitu tabu search, yang sering dipakai karena menghasilkan ongkos total yang lebih kecil dibanding metode yang lain. Cross Entropy (CE) merupakan suatu metode optimasi yang baru dikembangkan dengan dua prosedur utama, yaitu melakukan generate sampel data dengan distribusi tertentu dan melakukan update parameter distrubusi berdasarkan sampel terbaik untuk menghasilkan sampel yang lebih baik pada iterasi berikutnya. Penelitian ini merupakan penelitian lanjutan dan pembuktian secara fisik bagaimana CE diterapkan dalam kondisi permasalahan yang sebenarnya. Pada penelitian ini akan diterapkan permasalahan nyata CVRP yang terjadi pada proses distribusi logistik eksemplar koran. Hasil yang diharapkan adalah algoritma, eksperimen yang bisa menunjukkan performansi CE-CVRP, dan program komputer untuk implementasi algoritmanya. Kata kunci: capacitated vehicle routing problem, cross entropy, tabu search ABSTRACT Capacitated Vehicle Routing problem is one of the closest route determination which is limited by the capacity of transport vehicles. CVRP can be solved by using exact optimization such as integer programming optimization, but the solution will take a very long computation, especially for large problems (if the number of points served by is quite a lot) and using a heuristic approach, , such as taboo which is usually used because it can produces smaller total cost than the other methods. Cross Entropy (CE) is a new optimization method developed by two main procedures, generating sample data with a particular distribution and updating the parameters based on best sample distrubution to produce a better sample in the next iteration. This research is a continuation research and a physical evidence of how CE can be applied in the real problem. In this study, CE would be applied in real problems of CVRP that occur in the process of newspaper logistics ditribution. The expected results are the algorithm, an experiment that could show performance of CE-CVRP, and computer programs for the implementation of the algorithm. Keywords: capacitated vehicle routing problem, cross entropy, tabu search
1. Pendahuluan Semakin berkembangnya peradaban manusia, mengakibatkan kebutuhan akan cepatnya informasi yang didapat semakin tinggi. Setiap perusahaan penerbitan harian pagi khususnya berlomba-lomba menyajikan berita sepagi mungkin. Belum lagi tantangan untuk menyebarkan harian pagi tersebut ke seluruh wilayah segmentasi, tentunya membuat penerbit satu dengan lainnya bersaing dalam masalah penyebaran logistik eksemplar koran. Tentunya setiap perusahaan harian pagi menginginkan penyaluran atau distribusi logistik eksemplar
koran yang efektif dengan biaya traversing cost yang minimum. Capacitated Vehicle Routing adalah satu jenis permasalahan yang mewakili problem yang disebutkan tadi. Sudah banyak metode atau model penyelesaian yang dikembangkan oleh beberapa peneliti untuk menyelesaikan permasalahan CVRP. Diantaranya adalah integer programming (Kulkarni and Bhave,1985), mixed integer programming (Longo and Aragao,2004), tabu search (Fermin and Roberto, 2004), genetic algorithm (Baker and Ayechew, 2003), simulated annealing (Tavakkoli et al, 2005), ant
colony (Bell and McMullen,2004) dan lain-lain. Dalam menggunakan exact optimization seperti integer programming, akan diperlukan waktu komputasi yang sangat lama terutama untuk problem berukuran besar (jika jumlah titik yang dilayani cukup banyak). Dalam pendekatan heuristik, bisa dikatakan bahwa tabu search adalah salah satu metode yang sering dipakai karena menghasilkan ongkos total yang lebih kecil dibanding metode yang lain. Seiring dengan berkembangnya metode optimasi ditemukan beberapa pendekatan baru dalam menyelesaikan Vehicle Routing Problem. Salah satunya melalui pendekatan Cross entropy method (CE). CE merupakan algoritma baru yang telah diaplikasikan untuk penyelesaian optimasi kombinatorial dan optimasi multi extermal, serta rare-event simulation. Aplikasi metode CE untuk Traveling Sales Problem telah banyak diteliti dan dibuktikan bahwa pendekatan metode CE dapat menyelesaikan permasalahan ini. Namun pada penelitian sebelumnya belum dijelaskan bagaimana model dan bentuk penyelesaian algoritma yang dibangun. Penelitian ini merupakan penelitian lanjutan dan pembuktian secara fisik bagaimana CE diterapkan dalam kondisi permasalahan yang sebenarnya. Pada penelitian ini akan diterapkan permasalahan nyata tentang VRP yang terjadi pada proses disribusi logistik eksemplar koran. Dalam penelitian ini akan dilakukan pengembangan algoritma Cross Entropy untuk permasalahan CVRP (CE-VRP). Hasil yang diharapkan adalah algoritma, eksperimen yang bisa menunjukkan performansi CE-VRP, dan program komputer untuk implementasi algoritmanya. Penelitian ini dilengkapi batasan seperti ketentuan maksimum kendaraan, metode perhitungan jarak, metode penentuan subtour, penentuan perhitungan permintaan, dan klasifikasi kasus dengan satu depot. Manfaat yang diharapkan pada penelitian ini adalah adanya pendekatan baru yang merupakan aplikasi metode Cross Entropy dalam menyelesaikan Capacitated Vehicle Routing Problem pada studi kasus pendistribusian koran dari depot utama ke semua agen koran yang terdapat di Surabaya. 2. Metodologi Penelitian Bab ini akan menjelaskan langkah-langkah terstruktur yang dilakukan dalam melakukan
penelitian ini. Langkah-langkah ini digunakan sebagai acuan sehingga penelitian dapat berjalan secara sistematis sesuai dengan tujuan dan waktu penelitian. Pada tahapan persiapan dilakukan perumusan masalah, tujuan penelitian, dan studi bahan pustaka dan literatur. Pada tahapan ini, peneliti merumuskan permasalahan yang akan diteliti, dimana dalam masalah yang akan diteliti adalah bagaimana pengaplikasian metode Cross Entropy untuk menyelesaikan permasalahan Capacitated Vehicle Routing agar didapatkan waktu komputasi yang lebih baik dengan total cost transportation yang minimum. Adapun masalah optimasi yang akan diselesaiakan menggunakan CE dapat dilihat pada persamaan 1 dan 9. Tujuan yang akan dicapai dalam penelitian ini adalah dapat mengaplikasikan CE dalam penyelesaian CVRP, yang diharapkan dapat mampu memberikan performansi lebih baik dari metode lain seperti Tabu Search. Studi literatur yang dilakukan untuk mengetahui penelitianpenelitian terdahulu yang telah dilakuakn dan mencari bahan penelitian yang dapat dikembangkan sebagai suatu permasalahan baru. Studi literatur ini dilakuakn untuk memperoleh dan lebih memahami teori-teori yang berhubungan dengan pemecahan masalah. Penelesuran referensi dilakukan untuk penyelesaian permasalahan optimasi CE untuk CVRP. Pada tahapan selanjutnya, dilakukan pengembangan model penyelesaian, yang kemudian akan diuji pada permaslahan validasi serta dibandingkan dengan metode lainnya seperti tabu search. Pengujian algoritma dilakukan dengan menggunakan software MATLAB. Untuk pengujian data uji dilakukan untuk empat kasus berbeda yaitu data uji 8 simpul, data uji 10 simpul, data uji 20 simpul dan data uji 44 simpul. Setelah dilakukan pengembangan model maka tahapan selanjutnya adalah tahap analisa. Pada tahapan ini, dilakuakan analisa dengan parameter performansi traversing cost dan waktu komputasi yang dibutuhkan untuk menjalankan model pada setiap permasalahan. CE menyelesaian suatu permasalahan dengan membangkitkan sejumlah N kandidat solusi yang dibangkitkan secara random dengan distribusi tertentu yang kemudian difitkan pada fungsi tujuan. Kemudian dari sampel tersebut dipilih sejumlah n sampel terbaik yang kemudian dijadikan inputan untuk membaharui parameter yanng digunakan sehingga kandidat
2
solusi pada iterasi berikutnya bersala dari sampel terbaik pad iterasi sebelumnya. Adapun pengembangan model CE dalam menyelesaikan permasalahan CVRP dapat dilihat dari tahapan pengembangan model sebagai berikut: 1. Mengumpulkan data penunjang yaitu data jarak antar 44 simpul agen Jawa Pos yang terdapat di Surabaya. 2. Menentukan paraemeter penunjuang seperti rho, alpha, par1, par 2, dan jumlah sampel rute N yang akan dibangkitkan pada setip iterasi. 3. Menentukan intial value matriks transisi P yang nilai diagonalnya adalah nol 4. Membangkitkan Nℓ lintasan r1, . . . , rNℓ dari transisi matriks P, kemudian menghitung probabilitas suatu simpul dilayani. 5. Menghitung total traversing cost yang sebanding dengan total jarak pada setiap rute yang dibangkitkan dimana expected cost of traversing ∑ , (1) 6.
7.
Memilih lintasan dengan traversing cost minimum sejumlah rho*N sampel yang dinotasikan sebagai ℓ (r1), … , ℓ ( ℓ ) . Kemudian menyimpan lintasan dengan nilai minimum sebagai (xmin,rmin). Serta menotasikan rute yang mempunyai nilai minimum dari objective function dengan xl* selama iterasi l Memperbaharui transisi dari matriks P berdasarkan pembangkitan lintasan yang sesuai dengan rumus berikut:
8.
9.
+
% , . "# & '() * ∑ , $% % +
% "# & '() * ∑ , $% %
(2)
Jika stopping criteria yang ditentukan telah tercapai maka iterasi berhenti, jika tidak sama maka proses kembali ke langkah 2 Jika stopping criterion terpenuhi, tahapan dilajutkan pada pembentukan subtour
3. Pengumpulan dan Pengolahan Data Bab ini meliputi tahap penentuan set data yang akan diujikan terhadap algoritma Cross Entropy (CE), serta bagaimana pengujian model dilakukan dengan kerangka penelitian yang telah dibuat. 3.1 Contoh Numerik Data yang digunakan untuk melakukan pengujian pada model klasifikasi yang telah
dikembangkan adalah data set kasus sederhana permasalahan distribusi. Sebelum melakukan uji coba metode penyelesaian permasalahan CVRP dengan menggunakan CE (CE-CVRP) pada data tersebut, sebuah contoh sederhana digunakan untuk uji coba numerik. Hal ini bertujuan untuk memvalidasi apakah algoritma yang disusun dapat digunakan untuk mencari solusi pada permasalahan klasifikasi. Pada contoh ini, data uji yang digunakan berupa permasalahan distribusi sederhana dengan mellibatkan 3 simpul agen dan 1 simpul depot. Penyelesaian akan dilakukan dengan menggunakan metode Tabu Search dan CE-CVRP. Tabel 3. 1 Matriks Jarak Simpul Validasi 1
2
3
4
1
0
7
5
4
2
7
0
2
5
3
5
2
0
3
4
4
5
3
0
Tabel 3.2 Matriks Jarak Simpul Validasi simpul
demand
1
0
2
2
3
5
4
3
3.1.1 Penyelesaian dengan Tabu Search Permasalahan yang akan diselesaikan untuk Tabu Search adalah mendapatkan rute optimum sehingga dapat meminimasi T (i) sebagai fungsi tujuan. Adapun tahapan proses penyelesaian permasalahan ini adalah sebagai berikut: Langkah 1 Tahap Insialisasi Pada tahapan ini di lakukan generate solusi awal dan menentukan ukuran tabu list. Adapun solusi awal yang ditentukan adalah 1-2-3-4-1 dan ukuran tabu list yang digunakan adalah 100000. Serta stooping criterion yang ditetapkan adalah maksimum iterasi sebanyak 10000. Langkah 2 Generate Kandidat Solusi Pada tahapan ini dilakukan generate kandidat solusi dari solusi tetangga (neighbour solution) Langkah 3 Pemilihan solusi terbaik pada kandidat solusi Pada tahapan ini semua kandidat solusi yang ada dihitung T(i) sebagai fungsi tujuannya. Kemudian dipilih solusi terbaik pada kandidat solusi.
3
Langkah 4 Update Tabu List Pada tahapan ini , solusi terbaik yang terpilih pada langkah 3 akan dimasukan pada tabu list. Langkah 5 Ulangi langkah 2 sampai dengan 4 Pengulangan dilakukan hingga stopping criterion terpenuhi. Pada contoh numerik ini, batasan yang digunakan adalah ketika iterasi mencapai iterasi maksimum yang ditentukan. Permasalahan diatas dapat diselesaikan menggunakan software MATLAB dengan fungsi tujuannya adalah mencari nilai minimum jarak pada rute yang dibangkitkan. Adapun penulisan m-file dari metode Tabu Search ini dapat dilihat pada lampiran A. Berikut merupakan solusi MATLAB untuk penyelesaian menggunakan Tabu Search. current tour cost = 16 best tour best_tour = 1 4 3 best obj =16
best obj =16 2
1
Gambar 3.1 Solusi MATLAB untuk metode Tabu Search
3.1.2 Penyelesaian dengan CE-CVRP Permasalahan yang akan diselesaikan dengan CE-CVRP adalah bagaimanan menentukan rute optimum untuk mendapatkan total jarak minimum. Dengan menggunakan data validasi diatas akan dicari untuk meminimasi T(i) sebagai fungsi tujuan. Adapun pengujian data validasi yang dilakukan adalah sebagai berikut: Langkah 1 Tahap inisialisasi Pada tahap ini ditetapkan Rho = 0.5, Par1= 5, Par2= 10, Kapasitas = 10, Alpha = 0.87, toleransi= 0.005 dengan sampel yang dibangkitkan adalah sebanyak 10. Langkah 2 Tahap pembangkitan bilangan random Pada tahapan ini dibangkitkan matriks transisi berukuran n x n. Dimana n adalah banyaknya node yang terdapt pada permasalahaan. Dalam hal ini n sejumlah 4. Adapun mekanisme pembangkitan matriks transisi adalah sebagai berikut: - ∑ . 1, … … . 1 2 - , … … 1 3
42 Dengan mengikuti tahapan diatas di dapatkan matriks transisi untuk uji validasi sebagai berikut: p= 0 0.3333 0.3333 0.3333
0.3333 0 0.3333 0.3333
0.3333 0.3333 0 0.3333
0.3333 0.3333 0.3333 0
Gambar 3.2 Solusi MATLAB untuk metode Tabu Search
Langkah 3 Tahap pembangkitan Nℓ lintasan Pada tahap ini dibangkitkan sejumlah N lintasan sebagai sampel awal. Dari tahapan ini diperoleh sebanyak Nℓ sebagai berikut: Tabel 3.2 Hasil Rute yang dibangkitkan pada iterasi 1
Langkah 4 Tahap penghitungan expected cost G(r) Setiap rute atau lintasan yang telah dibangkitkan, dihitung traversing cost untuk setiap lintasan.
5 ,
Yang mana dalam hal ini p (i) = 1 Dari tahapan diatas maka didapatkan biaya untuk rute 1 sampai 9 yang dibangkitkan adalah sebagai berikut: Tabel 3.4 Hasil Rute yang dibangkitkan pada iterasi 1
Langkah 5 Tahap pemilihan sample elits Setelah mendapatkan traversing cost untuk masing-masing lintasan yang dibangkitkan maka langkah selanjutnya adalah mengambil samples elite yang merupakan lintasan yang
4
mempunyai traversing cost T(i) minimum. Dengan mengacu pada biaya yang telah terhitung pada tahapan sebelumnya, pada tahapan ini diambil sebanyak rho*N terbaik. Adapun pada iterasi pertama ini diambil sebanyak 5 sampel yang terbaik. Adapun sampel elite iterasi 1 adalah sebagai berikut:
Gambar 3.3 Solusi MATLAB untuk metode Tabu Search
Tabel 3. 3 Tabel Data Sampel Elite Validasi
3.2 Deskripsi Data Uji Data yang digunakan dalam pengujian ini adalah set data jarak antar agen dan set data demand tiap agen. Dalam penelitian ini dilibatkan 43 agen Koran yang tersebar di seluruh wilayah surabaya dan 1 depot utama. Data demand yang digunakan merupakan rekapan rata-rata permintaan agen tiap bulannya.
Langkah 6 Update parameter Setelah didapatkan sekumpulan sampel terbaik yaitu sampel lintasan yang mempunyai traversing cost minimum, maka tahapan selanjutnya adalah update parameter. Parameter yang dimaksud dalam hal ini adalah matriks transisi. Parameter yang telah diperbaharui merupakan inputan baru untuk membangkitkan sampel lintasan yang lebih baik. Hasil pembaharuan parameter sesuai dengan langkah diatas adalah sebagai berikut: p= 3.4800 3.5233 3.5233 3.5233
3.5233 3.4800 3.5233 3.5233
3.5233 3.5233 3.4800 3.5233
3.5233 3.5233 3.5233 3.4800
Tabel 3.6 Tabel Data Sampel Elite Validasi
3.2.1 Data Koordinat Agen dan Depot di Wilayah Surabaya Data koordinat tiap lokasi agen merupakan lokasi dari tiap agen yang didekatkan pada pengukuran manual pada tiap lokasi agen yang tersebar di Surabaya yang mana pada tabel berikut dibawah ini simpul 1 (depot) merupakan pusat perhitungan. Adapun koordinatnya adalah sebagai berikut: Tabel 3.7 Tabel Data Sampel Elite Validasi
Gambar 3.2 Solusi MATLAB untuk metode Tabu Search
Langkah 7 Ulangi langkah 2 sampai dengan langkah 6 Pengulangan dilakukan hingga stopping criterion terpenuhi. Pada contoh numerik ini, batasan yang digunakan adalah ketika iterasi mencapai iterasi maksimum yang ditentukan. Langkah 8 Penentuan subtour Tahap 1 sampai 6 pada akhirnya akan menghasilkan satu lintasan yang optimal. Yang mana lintasan ini mempunyai traversing cost yang minimum. Tahapan selanjutnya adalah menentukan subtour dari lintasan tersebut karena mekanisme melayani suatu simpul dibatasi oleh fungsi kapasitas dari vehicle yang digunakan. Setelah melakukan 8 tahap diatas maka dalam uji validasi ini didapatkan rute optimum sebagai berikut: Ropt : 1-4-3-2-1 Subtour Rute 1: 1-4-3-2-1 dengan TC= 16, kapasitas 10
5
Data permintaan yang diinputkan dalam algoritma CE untuk CVRP ini adalah rata-rata permintaan koran setiap bulan dari setiap agen yang diinputkan. Adapun data demand dari tiaptiap agen adalah sebagai berikut: Tabel 3.8 Tabel Data Sampel Elite Validasi
3.2.2
Data Demand Koran
6
Tabel 3.9 Tabel Data Sampel Elite Validasi
3.3 Pengujian Data Pada subbab ini, pengujian metode aplikasi CE untuk kasus CVRP akan dibandingkan dengan pengujian metode tabu search dan ant colony. Parameter yang digunakan dalam pengujian data ini adalah matriks transisi yang pembangkitanya sesuai dengan rumusan pembangkitan matriks transisi yang telah ditentukan. Untuk iterasi pada CE-CVRP, stopping criterion yang digunakan adalah apabila nilai maksimum selisih antara matriks transisi dan matriks pold lebih dari toleransi yang ditentukan dan iterasi yang terjadi telah sampai dengan iterasi maksimum yang digunakan. Hasil uji yang dibandingkan antara metode CE dan Tabu Search adalah total traversing cost untuk setiap sub tour dari rute optimum yang dihasilkan dan waktu komputasi (CPU Time) pada implementasi model di software MATLAB dimulai dari tahapan awal sampai dengan mendapatkan rute optimum. 3.3.1. Pengujian Data dengan 8 simpul Data agen koran yang diambil hanya sebanyak 8 simpul akan diuji secara komputasi dengan software MATLAB menggunakan aplikasi CECVRP dan Tabu Search. Pada CE-CVRP dilakukan pembangkitan sampel rute sebanyak 7 faktorial (7!), hal ini ditujukan agar mengurangi kemungkinan solusi yang di hasilkan oleh CECVRP terletak pada local optimum. Selain itu juga ditetapkan beberapa parameter inisial seperti Rho = 0.002, Par1= 5, Par2= 10, Alpha = 0.9, toleransi= 0.005. Sedangkan pada Tabu Search dilakukan iterasi sebanyak 10000 iterasi. Dalam penentuan subtour digunakan maksimum kapasitas 2000 koran setiap kendaraannya. Adapun hasil dari kedua metode tersebut dapat dilihat pada tabel dibawah ini.
3.3.2 Pengujian Data dengan 10 simpul Data agen koran yang diambil hanya sebanyak 10 simpul akan diuji secara komputasi dengan software MATLAB menggunakan aplikasi CECVRP dan Tabu Search. Pada CE-CVRP dilakukan pembangkitan sampel rute sebanyak 6000 sampel rute. Selain itu juga ditetapkan beberapa parameter inisial seperti Rho = 0.002, Par1= 5, Par2= 10, Alpha = 0.87, toleransi= 0.005. Sedangkan pada Tabu Search dilakukan iterasi sebanyak 10000 iterasi. Dalam penentuan subtour digunakan maksimum kapasitas 2000 koran setiap kendaraannya. Adapun hasil dari kedua metode tersebut dapat dilihat pada tabel dibawah ini. Tabel 3.10 Tabel Data Sampel Elite Validasi 10 simpul Metode CE-CVRP
Tabu Search
waktu komputasi (detik)
ropt
subtour
1-8-9-10-5-1 19,6875 1-8-9-10-5-6-7-4-3-2-1 1-6-7-4-1 1-3-2-1 62,125 1-8-9-6-5-10-2-3-4-7-1 1-8-9-6-1 1-5-10-2-1 1-3-4-1 1-7-1
T (i) 190,2
211,4
3.3.3 Pengujian Data dengan 20 simpul Data agen koran yang diambil hanya sebanyak 20 simpul, akan diuji secara komputasi dengan software MATLAB menggunakan aplikasi CECVRP dan Tabu Search. pada CE-CVRP dilakukan pembangkitan sampel rute sebanyak 10000 sampel rute. Selain itu juga ditetapkan beberapa parameter inisial seperti Rho = 0.002, Par1= 5, Par2= 10, Alpha = 0.87, toleransi= 0.005. Sedangkan pada Tabu Search dilakukan iterasi sebanyak 10000 iterasi. Dalam penentuan subtour digunakan maksimum kapasitas 5000 koran setiap kendaraannya. Adapun hasil dari
7
kedua metode tersebut dapat dilihat pada tabel dibawah ini. Tabel 3.11 Tabel Data Sampel Elite Validasi
20000 sampel rute Metode
CE-CVRP
20 simpul Metode CE-CVRP
Tabu Search
waktu komputasi (detik)
ropt
205,59375
80,0625
subtour
T (i)
1-12-16-11-7-14-10-5-15-9- 1-12-16-11-7-14-10-517-6-18-4-2-3-13-4-16-1 15-9-1 1-17-6-18-4-2-3-13-1 1-4-16-1
238
waktu komputasi
ropt
subtour
T (i)
1-3-2-11-44-34-16-28-43-8-39-36-19-32-26-7-622-10-5-23-20-40-24-30-37-9-35-12-17-13-27- 547,18725 1-3-2-11-44-34-16-28-43-8-39-36-19-1 18-4-38-33-31-15-21-42-25-41-29- 14-1 577,26 1-32-26-7-6-22-10-5-23-1 1-20-40-24-30-37-9-35-1 1-12-17-13-27-18-4-38-33-1 1-31-15-21-42-25-41-29- 14-1
1-12-36-35-19-8-15-17-21-22-10-5-6-38-14-11Tabu Search 37-43-42-18-32-2-3-29-26-27-25-4-41-16-30-2440-28-34-39-7-44-23-20-13-33-9-31-1
215,563
1-12-36-35-19-8-15-17-21-22-10-5-6363.71 38-1 1-14-11-37-43-42-18-32-2-3-29-26-1 1-27-25-4-41-16-30-24-1 1-40-28-34-39-7-44-1 1-23-20-13-33-9-31-1
1-12-19-8-9-15-17-6-5-10-14- 1-12-19-8-9-15-17-6-5216,824 20-7-11-18-13-2-3-4-16-1 10-14-1
40000 sampel rute 1-20-7-11-18-13-2-3-1 1-4-16-1
3.3.4 Pengujian Data dengan 44 simpul Pada tahap pengujian ini digunakan data set sebenarnya yaitu dengan 1 depot utama dan 43 agen koran yang tersebar diseluruh wilayah Surabaya. Dengan menggunakan pembangkitan sampel rute yang telah ditentukan untuk CECVRP akan dibandingkan dengan hasil Tabu Search. Dalam perhitungan Tabu Search menggunakan stopping criterion maksimum iterasi sebanyak 10000 iterasi. Pada CE-CVRP ditetapkan beberapa parameter inisial seperti Rho = 0.0002, Par1= 5, Par2= 10, Alpha = 0.9, toleransi= 0.005. Adapun hasinya dapat dilihat pada tabel berikut: Tabel 3.11 Tabel Data Sampel Elite Validasi 10000 sampel rute waktu subtour T (i) komputasi 285,14 1-8-40-37-30-29-16-27-11 CE-CVRP 620,1 1-8-40-37-30-29-16-27-11-21-15-6-20-9-36-341-21-15-6-20-9-36-34-7-32-1 7-32-26-4-25-14-17-24-38-10-44-5-35-31-12-191-26-4-25-14-17-24-38-10-44-5-35-3113-18-22-33-23-42-39-41-28-2-3-43-1 1 1-12-19-13-18-22-33-23-1 1-42-39-41-28-2-3-43-1 1-12-36-35-19-8-15-17-21-22-10-5-6-38-14-111-12-36-35-19-8-15-17-21-22-10-5-6Tabu Search 37-43-42-18-32-2-3-29-26-27-25-4-41-16-30-24- 215,563 363.71 38-1 40-28-34-39-7-44-23-20-13-33-9-31-1 1-14-11-37-43-42-18-32-2-3-29-26-1 1-27-25-4-41-16-30-24-1 1-40-28-34-39-7-44-1 1-23-20-13-33-9-31-1 Metode
ropt
waktu subtour T (i) komputasi 1-35-15-21-10-14-39-41-18-38-31-6-23-28-40- 4.535,1406 1-35-15-21-10-14-39-41-18-38-31-6-1 574,73 CE-CVRP 30-33- 37-16-3-4-27-24-22-43-7-11-12-36-44-201-23-28-40-30-33- 37-1 32-29-42-2-26-25-13-34-9-5-19-17-8-1 1-16-3-4-27-24-22-43-7-11-1 1-12-36-44-20-32-29-42-2-26-25-1 1-13-34-9-5-19-17-8-1 1-12-36-35-19-8-15-17-21-22-10-5-6-38-14-111-12-36-35-19-8-15-17-21-22-10-5-6Tabu Search 37-43-42-18-32-2-3-29-26-27-25-4-41-16-30-24- 215,563 363.71 38-1 40-28-34-39-7-44-23-20-13-33-9-31-1 1-14-11-37-43-42-18-32-2-3-29-26-1 1-27-25-4-41-16-30-24-1 1-40-28-34-39-7-44-1 1-23-20-13-33-9-31-1 Metode
ropt
4 Analisa dan Pembahasan Pada bab analisa dan pembahasan akan dilakukan analisa terhadap hasil uji coba model yang telah dilakukan sebelumnya. Analisa dilakukan untuk setiap pendekatan yang digunakan. 4.1 Analisa Hasil Uji Data Validasi Pada pengujian data validasi, diterapkan dua metode pada tahap penyelesaiannya. Terlihat pada table 4.6, kedua metode ini memberikan solusi rute optimum yang sama. Yang mana kedua rute yang dihasilkan dengan metode yang berbeda ini memili traversing cost yang sama yaitu sebesar 16. Dari segi kecepatan komputasi (CPU time), CE-CVRP memperlihatkan performansi yang baik, yaitu hanya membutuhkan waktu sebesar 0.0625 detik. Hal ini lebih kecil dibandingkan dengan waktu komputasi yang diperlukan oleh Tabu Search yaitu sebesar 150.703 detik. Perbedaan waktu komputasi yang dibutuhkan baik Tabu Search dan CE-CVRP sangat dipengaruhi oleh stopping criterion yang diterapkan. Pada Tabu Search dalam penyelesaian permasalahan data validasi menggunakan stopping criterion maksimum iterasi sebanyak 10000 iterasi. Artinya setiap langkah pada tahapan penyelesaiannya dilakukan sebanyak 10000 kali. Tentunya hal ini
8
akan membutuhkan waktu komputasi lebih lama untuk mendapatkan rute optimum. Berbeda dengan Tabu Search, CE-CVRP membutuhkan waktu komputasi yang lebih kecil. CE-CVRP menerapkan stopping criterion yang ditentukan adalah selisih dari matriks transisi (parameter CE-CVRP) dengan matriks Pold, yang merupakan matrik transisi pada iterasi sebelumnya. Selain selisih parameter matriks, lamanya waktu komputasi juga dipengaruhi oleh banyaknya sampel yang dibangkitkan dalam setiap iterasi. Pada penyelesaian data uji validasi ditentukan sebanyak 10 sampel rute yang dibangkitkan. Dari hasil yang ditunjukan pada data validasi, terbukti bahwa CE-CVRP dapat menyelesaikan permasalahan CVRP. Untuk menguji apakah hasil rute optimum yang dihasilkan oleh CECVRP akan tetap baik dapat dilakukan iterasi dengan modifikasi jumlah sampel rute yang dibangkitkan dan toleransi yang digunakan dalam selisih matriks transisi. 4.2 Analisa Hasil Data Uji Dengan menggunakan data uji depot dan agen koran pada Tabel 4.7 dan Tabel 4.8, dilakukan pengujian data menggunakan metode Tabu Search dan CE-CVRP. Tahapan analisa hasil uji ini dibagi berdasarkan 4 kasus yang diangkat yaitu pada 8 simpul pertama, 10 simpul pertama, 20 simpul pertama dan 44 sampel. 4.2.1 Analisa Hasil Data Uji 8 Simpul Pada pengujian data uji 8 sampel, diselesaian dengan dua metode yaitu Tabu Search dan CECVRP. Tabu Search menghasilkan 3 subtour optimum, dengan total traversing cost yang dihasilkan adalah sebesar 170,1. Pada pengujian data menggunakan metode CE-CVRP, menghasilkan 3 subtour dengan total traversing cost yang dihasilkan adalah sebesar 169,8. Dari segi kecepatan komputasi (CPU time), CECVRP memperlihatkan performansi yang baik, yaitu hanya membutuhkan waktu sebesar 15.625 detik. Hal ini lebih kecil dibandingkan dengan waktu komputasi yang diperlukan oleh Tabu Search yaitu sebesar 59.718 detik. Performansi CE-CVRP yang lebih baik dibandingkan dengan Tabu Search didukung oleh prosedur penyelesaian CVRP menggunakan prinsip CE yang mana pada tahap inisialisasi, dibangkitkan sejumlah N rute dalam hal ini sebanyak 6000 rute, yang kemudian dihitung total jaraknya
sebagai traversing cost, dan adanya langkah pengambilan sebanyak 12 (rho*N) sampel terbaik yang akan menjadi acuan dalam pembangkitan sampel rute pada iterasi berikutnya. Dengan prinsip dasar penyelesaian seperti yang telah dijelaskan, tentunya pada generate sampel akan mengacu pada rute yang paling baik, sehingga kecepatan convergence dalam penyelesaian penentuan rute dapat lebih cepat dibandingkan dengan Tabu Search. Selain lebih cepat, penyelesaian dengan menggunakan CE-CVRP membuktikan adanya rute yang lebih baik dengan traversing cost yang paling minimum. Jika dibandingkan dengan Tabu Search dengan prinsip penyelesaian neighborhood solution, pendekatan penyelesaian lebih kearah penyelesaian nearest neighbor berbeda dengan CE-CVRP yang membangkitkan segala kombinasi rute yang terjadi. Sehingga dapat menyentuh global optima dalam penyelesaian permasalahan. 4.2.2 Analisa Hasil Data Uji 10 Simpul Pada pengujian data uji 10 simpul, diselesaikan dengan dua metode yaitu Tabu Search dan CECVRP. Tabu Search menghasilkan 4 subtour optimum, dengan total traversing cost yang dihasilkan adalah sebesar 211,4. Pada pengujian data menggunakan metode CE-CVRP, menghasilkan 3 subtour dengan total traversing cost yang dihasilkan adalah sebesar 190,2. Dari segi kecepatan komputasi (CPU time), CECVRP membutuhkan waktu komputasi yang lebih kecil yaitu selama 19,6875 detik dibandingkan dengan Tabu Search yang membutuhkan waktu selama 62.125 detik. Seperti halnya yang telah dipaparkan pada sub bab 5.2.1, yang mana dijelaskan penyelesaian CE-CVRP menghasilkan performansi yang lebih baik dibandingkan dengan Tabu Search dikarenakan penerapan prinsi CE yaitu pembangkitan 6000 sampel rute yang dihitung total jaraknya sebagai traversing cost dan kemudian diambil 12 sampel terbaik yang digunakan sebagai acuan dalam pembangkitan 6000 sampel rute baru pada iterasi berikutnya. Dengan membangkitkan sejumlah sampel rute sebagai kandidat solusi yang kemudian dilakukan proses pembaharuan pada sampel rute tersebut mengakibatkan pada CE-CVRP membuka peluang banyak kombinasi rute. Dibandingkan dengan Tabu Search yang menerapakan prinsip neighborhood solution,
9
hasil tbu search mendekati hasil nearest neighbor. Hal inilah yang memungkinkan rute yang dihasilkan oleh CE-CVRP lebih optimum dibandingkan dengan Tabu Search, seperti pada pengujian model dengan data uji 10 simpul. Selain itu dengan pembangkitan 6000 sampel rute pada setiap iterasinya yang terus dilakukan proses update didalamnya memungkinkan CECVRP lebih cepat dalam menemukan solusi optimal sehingga waktu komputasi yang dibutuhkan tidak sebanyak waktu komputasi yang dibutuhkan Tabu Search. 4.2.3 Analisa Hasil Data Uji 20 Simpul Pada pengujian data uji 20 simpul, seperti yang dicantumkan pada Tabel 4.11, CE-CVRP menghasilkan rute optimum dengan total traversing cost yang dihasillkan adalah sebesar 238. Hal ini lebih buruk dibandingkan ketika data uji diselesaikan oleh Tabu Search yang menghasilkan rute optimum dengan traversing cost sebesar 216.824. Selain total traversing cost, jika dibandingkan performansi antara Tabu Search dengan CE-CVRP, Tabu Search membutuhkan waktu komputasi sebanyak 80.0625 detik sedangkan CE-CVRP membutuhkan waktu 205.59375 detik. Pada pengujian model untuk data uji 20 simpul, CE-CVRP tidak memberikan performansi yang lebih baik dibandingkan dengan Tabu Search. Hal ini dikarenakan banyaknya kombinasi rute yang seharusnya dibangkitkan sebanding dengan jumlah simpul yanga da dalam permasalaha. Jika dikalkulasikan setidaknya terdapat 19 ! (baca: faktorial) kombinasi rute yang ada jika awal setiap rute adalah simpul 1. Lamanya waktu komputasi yang dibutuhkan CE-CVRP dapat disebabkan setidaknya oleh dua hal yaitu stopping criterion dan 10000 sampel yang dibangkitkan pada permasalahan dengan 20 simpul. Selain beberapa alasan yang telah dicantumkan, penyebab turunya performansi CE-CVRP pada pengujian model dengan data uji 20 sampel ini dapat dikarenakan oleh keterbatasan rancangan matlab code yang telah dirancang. Namun jika dilihat dari hasil yang terdapat pada Tabel 4.11, hasil dari CE-CVRP hanya selisih 21.176 dari hasil rute optimum oleh Tabu Search. Artinya ada peluang CE-CVRP dapat menghasilkan rute yang mempunyai traversing cost yang sama atau mungkin lebih optimum dibandingkan rute yang dihasilkan oleh Tabu Search. Adapun upaya yang dapat dilakukan
untuk memperbaiki hasil dari CE-CVRP adalah dengan membangkitkan lebih banyak sampel rute sejumlah kemungkinan kombinasi yang dihasilkan dan memodifikasi matlab code yang telah dirancang sehingga dapat menghasilkan rute yang lebih optimum dibandingkan Tabu Search dengan waktu komputasi yang minimum. 4.2.4 Analisa Hasil Data Uji 44 Simpul Pada data uji 44 sampel, pengujian dilakukan dengan jumlah sampel rute yang berbeda. Sesuai yang tercantum pada Tabel 4.12, pengujian model dilakukan dengan membangkitkan 3 macam jumlah sampel rute yang berbeda. Pada pengujian dengan pembangkitan 10000 sampel rute, CE-CVRP menghasilkan rute-rute dengan total traversing cost besar yaitu senilai 620,1 dengan waktu komputasi yang dibutuhkan adalah senilai 285.14 detik. Sedangkan Tabu Search menghasilkan rute dengan traversing cost senilai 363.71, dengan waktu komputasi sebesar 215.563 detik. Pada pengujian model dengan pembangkitan 20000 sanpel rute, CECVRP menghasilkan rute dengan traversing cost sebesar 577,26 dan waktu komputasi yang dibutuhkan sebesar 547.18725 detik. Hal ini masih jauh berbeda deibandingkan dengan rute yang dihasilkan Tabu Search. Tabu Search menghasilkan rute dengan traversing cost yang sama pada pengujian 10000 sampel yaitu senilai 363.71 dan waktu komputasi ang dibutuhkan sebesar 215.563 detik. Pada pengujian model dengan 40000 sampel rute yang dibangkitkan, Tabu Search memberikan hasil yang sama pada pengujian sebelumnya. Sedangkan untuk CECVRP menghasilkan rute dengan traversing cost sebesar 574.73 dan membutuhkan waktu komputasi 4535.1406 detik. Performansi yang diperlihatkan oleh 3 macam percobaan mengalami kenaikan, dalam artian rute yang dihasilkan semakin baik. Namun jika dibandingkan dengan Tabu Search, hasil yang diberikan CE-CVRP masih lebih buruk baik dilihat dari rute yang dihasilkan maupun waktu komputasi yang dibutuhkan dalam penyelesaian permasalahan.
10
traversing cost
CE-CVRP CVRP VS TABU SEARCH 1000 500 0
CE-CVRP Tabu Search
Gambar 4. 1 Perbandingan T(i) pada Data Uji 44 Simpul
Kecenderungan semakin baik rute yang dihasilkan pada 3 macam pengujian ini mengindikasikan dibutuhka semakin banyak sampel yang sebanding dengan banyaknya simpul pada permasalahan. Rute yang dihasilkan oleh CE-CVRP CVRP secara umum dari ketiga percobaan dalam penyelesaian 44 simpul mempunyai traversing cost yang lebih besar dibandingkan dengan rute yang hasilkan oleh Tabu Search.. Hal ini dapat dikarenakan, kurangnya sampel rute yang dibangkitkan. dibangkit Pada CE-CVRP CVRP semakin banyak simpul yang terdapat pada permasalahan, maka semakin banyak pula kombinasi rute yang dapat dihasilkan. Jika pada setiap iterasi dapat membangkitkan banyak kombinasi rute, maka peluang untuk kmendapatkan rute optimum akan semakin makin besar. Namun dengan cara memperbesar sampel rute akan mengakibatkan waktu komputasi yang dibutuhkan semakin besar. Oleh karena itu perlu modifikasi matlab code sebagai program penyelesaian permasalahan agar dapat memperkecil kebutuhan waktu komputasi yang dibuthkan untuk penyelesaian permasalahan. 4.3 Analisa Performansi Keseluruhan Pengujian dilakukan dengan 5 klasifikasi kasus yaitu data uji validasi, data uji 8 simpul, data uji 10 simpul, data uji 20 simpul dan data uji 44 simpul. Dari ke lima kasus yang diuji, 3 diantaranya dilakukan dengan baik oleh CECE CVRP. Terbukti pada pengujian data validasi yang berjumlah 4 simpul, data uji 8 simpul dan data uji 10 simpul, CE-CVRP CVRP tidak hanya h menghasilkan rute yang memiliki memi traversing cost lebih minimum dibandingkan ibandingkan rute yang diasilkan Tabu Search,, waktu komputasi yang dibutuhkan CE-CVRP CVRP juga lebih sedikit dibandingkan waktu komputasi Tabu Search. Search Sedangkan untuk data uji 20 sampel dan 44 sampel, Tabu Search menghasilkan rute yang
lebih optimal karena rute rut yang dihasilkan memiliki traversing cost minimum dibandingkan dengan CE-CVRP. CE Selain itu dalam hal waktu komputasi, CE-CVRP CE membutuhkan waktu yang lebih lama dibandingkan Tabu Search. Search Banyaknya sampel yang dibangkitkan pada setiap iterasi, sangat mempengaruhi aruhi performansi CE-CVRP CE dalam menghasilkan rute yang optimum. Jumlah sampel yang dibangkitkan seharusnya sesuai dengan banyaknya kemungkinan kombinasi rute yang dapat dihasilkan. Semakin banyak sampel rute yang dibangkitkan maka peluang untuk menemukan rute ute dengan traversing cost minimum, semakin besar. Waktu komputasi selain dipengaruhi oleh banyaknya sampel yang dibangkitkan juga dipengaruhi oleh banyaknya simpul yang terdapat pada permasalahan. Semakin banyak simpul dan semakin banyak sampel yang dibangkitkan gkitkan maka waktu komputasi yang dibutuhkan akan semakin besar. Penyelesaian enyelesaian data uji 20 simpul dan 44 simpul, CE-CVRP CVRP tidak menghasilkan rute optimum. Hal ini berbeda dengan Tabu Search yang menghasilkan rute dengan traversing cost lebih baik. Dengan mekanisme kanisme neighbour solution, Tabu Search membangkitkan kandidat solusi. Hasilnya akan sama jika digunakan nearest neighbor dalam penyelesaian data uji. Berbeda dengan Tabu Search yang membangkitkan satu solusi awal CE-CVRP CVRP membangkitkan sejumlah sampel rute yang ditentukan sebagai solusi awal, yang kemudian dilakukan mekanisme cross entropy untuk mendapatkan sampel rute baru sebagai solusi baru pada iterasi berikutnya. Hal inilah yang menyebabkan dibutuhkannya semakin banyak sampel yang dibangkitkan sesuai dengan engan banyaknya simpul yang terdapat pada permasalahan. Sedangkan untuk data uji dengan simpul ukuran kecil, CE-CVRP CE dapat menyelesaikannya dengan lebih cepat dibandingkan Tabu Search.. Hal ini dikarenakan metode heuristic CE yang diterapkan mampu mencari beberapa eberapa solusi rute yang sesuai dengan banyaknya rute yang dibangkitkan sekaligus sebagai kandidat solusi.
5 Kesimpulan dan Saran Bab ini berisi tentang kesimpulan hasil penelitian dan saran-saran saran yang berkaitan dengan penelitian selanjutnya.
11
5.1 Kesimpulan 1. Metode optimasi Cross Entropny dapat diaplikasikan untuk penyelesaian masalah Capacitated Vehicle Routing dengan melakukan insialisasi matriks transisi sebagai parameter utama yang berguna dalam pembangkitan sejumlah sampel rute sebagai kandidat solusi. 2. Metode CE-CVRP dalam penyelesaian permasalahan sangat bergantung pada stopping criterion yang ditentukan dan banyaknya sampel rute yang dibangkitkan pada setiap iterasinya. 3. CE-CVRP dapat menunjukan performansi yang lebih baik dibandingkan tabu search pada permasalahan 4 simpul, 8 simpul, dan 10 simpul. Sedangkan pada permasalahan 20 simpul dan 44 simpul, tabu search mampu menunjukan performansi yang lebih baik. 5.2 Saran 1. Penelitian selanjutnya bisa dilakukan dengan memodifikasi algoritma sehinga dapat meminimalkan jumlah sampel yang perlu dibangkitkan pada permasalahan yang melibatkan banyak simpul. 2. Sebaiknya dilakukan penelitian dan pengembangan program komputasi dengan meletakan depot tidak pada pusat koordinat dan adanya konstrain ketersediaan vehicle yang dapat digunakan. 6 Daftar Pustaka De Boer, et al, (2005). A Tutorial on the Crossentropy method, Annals of Operations Research, vol. 134, No. 1, pp. 19-67 Kroese & K.-P. Hui. (2007). Applications of the Cross-Entropy Method in Reliability Computational Intelligence in Reliability Engineering (SCI) 40. 37– 82 Rubinstein,R.Y. (1999). The Cross-Entropy Method for Combinatorial and Continuous Optimization, Methodology and Computing in Applied Probability, vol 1. 127-190. Kluwer Academic Publishers: Boston, Rubinstein, R., & Kroese., D, (2004). The crossentropy method: A unified approach to combinatorial optimization, MonteCarlo simulation, and machinelearning, Springer-Verlag,.
Rubinstein, R.Y. (2005) Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and RareEvent, Estimation Methodology and Computing in Applied Probability, 7, 5– 50. Ralphs, et al, On the Capacitated Vehicle Routing Problem, Mathematical programming, submitted Lawjer, el al. (1985). The Traveling Salesman Problem. England: SERC. Rubinstein, & Kroese, D. P. (2008). Simulation and The MOnte Carlo Method. USA: A John Wiley and Sons. Rubinstein, & Kroese. (2004). The Cross Entropy; A Unified Approach to Combinatorial Optimiztion, Monte Carlo Simulation and Machine Learning. USA: Springer. Chepuri, & Homem. (2003). Solving The Vehicle Routing Problem with Stochastic Demands Using The Cross Entropy Method. Elsevier-ScienceDirect . Lagua, & Marti. (2007). Hybridizing The Cross Entropy Method: An Application in The Max-Cut Poblem. ElsevierScienceDirect . Mohemmed, et al (2008). Solving Shortest Path Problem Using Particle Swarm Optimiztion. Elsevier-ScienceDirect . Rubinstein, & Kroese. (2004). The Cross Entropy; A Unified Approach to Combinatorial Optimiztion, Monte Carlo Simulation and Machine Learning. USA: Springer. Shi, et al. (2007). Particle Swarm Optimization Based Algorithms for TSP and Generalized TSP. ElsevierScienceDirect.
12
