PENERAPAN METODE CROSS ENTROPY DALAM PENYELESAIAN CAPACITATED LOCATION-ROUTING PROBLEM

PENERAPAN METODE CROSS ENTROPY DALAM PENYELESAIAN CAPACITATED LOCATION-ROUTING PROBLEM Nuresti Prabaningtyas dan Budi Santosa Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email: [email protected] ; [email protected]

Abstrak Capacitated Location-Routing Problem (CLRP) merupakan bidang penelitian yang menggabungkan dua komponen kunci dari sistem logistik, yaitu facility location dan vehicle routing. Tujuan dari CLRP adalah menyelesaikan masalah penempatan lokasi suatu fasilitas dan permasalahan vehicle routing dari fasilitas tersebut secara bersamaan dengan memperhitungkan kapasitas depot maupun kendaraan yang digunakan. Penelitian untuk penyelesaian CLRP telah banyak dilakukan baik dengan pendekatan eksak maupun heuristik/ metaheuristik, akan tetapi hingga saat ini penelitian terus dilakukan untuk mendapatkan hasil yang optimal. Cross Entropy (CE) sebagai salah satu metoda metaheuristik yang relatif baru merupakan metoda yang diusulkan untuk menyelesaikan problem CLRP tersebut. Metoda ini sebelumnya telah diaplikasikan pada permasalahan optimasi kombinatorial, optimasi multi eksternal, serta rare event simulation, dengan hasil penyelesaian yang optimal. Hasil yang diperoleh pada penelitian ini menunjukkan algoritma yang diusulkan memiliki performansi yang cukup bagus dan sangat kompetitif untuk problem dengan ukuran data kurang dari 30 node. Pengukuran performansi ini diperoleh dari perbandingan total biaya hasil metoda CE dengan Best Known Solution (BKS) yang didapatkan dari penelitian sebelumnya.

Kata kunci: CLRP, cross entropy, optimasi, metaheuristik ABSTRACT Capacitated Location-Routing Problem (CLRP) is a research field that combines two key components of logistics system, namely the facility location and the vehicle routing. The goal of this CLRP is to solve the problem of placement location of a facility and vehicle routing problems of the facility simultaneously, by taking into account the capacity of depots and vehicles used. Research for the completion of CLRP has been done by both the exact and heuristic approaches / metaheuristic, but the research continues to be done to get optimal results. Cross Entropy (CE), as one of metaheuristik method that is relatively new, is a method proposed to solve the CLRP problem. This method has previously been applied to combinatorial optimization problems, optimization of multi external, and rare event simulation, with optimal solution. The results obtained in this study showed that the proposed algorithm had a pretty good performance and was very competitive for the problem with the data size of less than 30 nodes. These performance measurements were obtained from the comparison of the total cost of the CE method and the Best Known Solution (BKS) obtained from the previous studies. Key words: CLRP, cross entropy, optimization, metaheuristic

1.

Pendahuluan

Distribusi produk kepada customer merupakan salah satu kegiatan yang penting dalam suatu perusahaan. Menurut Tuzun et al. (1998) transportasi dan pergudangan merupakan dua hal yang banyak mengkonsumsi biaya, oleh karena itu penghematan yang besar dapat dicapai dengan memperbaiki sistem distribusi, walaupun perbaikan tersebut hanya dalam jumlah yang kecil. Lokasi dari fasilitas dan distribusi

produk dari fasilitas tersebut dalam memenuhi demand customer merupakan dua komponen kunci dari sistem distribusi. Dalam berbagai permasalahan, dua komponen ini saling berhubungan, sehingga perlu mempertimbangkan lokasi fasilitas atau depot serta keputusan distribusi secara bersamaan. Permasalahan tersebut dapat didekati menggunakan location-allocation ketika customer dilayani secara individu dengan rute yang langsung dari depot ke customer (truckload). Tetapi ketika customer

memiliki permintaan less-than-truckload, model rute individu tidak dapat menggambarkan biaya transportasi secara akurat (Belenguer, et al.,2010). Kondisi tersebut lebih baik dimodelkan dengan menggunakan Location-Routing Problem (LRP) yang menggabungkan dua keputusan penting yaitu lokasi depot dan vehicle routing dari depot tersebut ke customer. Capacitated Location-Routing Problem (CLRP) merupakan permasalahan Location-Routing yang memiliki batasan kapasitas untuk masing-masing alternatif depot serta kendaraan yang digunakan. Tujuan dari CLRP adalah untuk menentukan satu atau lebih lokasi depot dari sekumpulan alternatif depot yang ditawarkan untuk dipilih serta menentukan rute kendaraan dari depot terpilih kepada customer dalam rangka meminimalkan penjumlahan biaya lokasi dan distribusi dengan memperhatikan kapasitas depot maupun kendaraan yang ada. CLRP termasuk dalam kelas masalah NPhard karena mencakup dua masalah NP-hard (location facility dan vehicle routing). Ketika ukuran masalah meningkat (depot dan jumlah titik customer yang dilayani cukup banyak), pendekatan heuristik maupun metaheuristik menjadi alternatif yang feasible (Lopes, et al., 2008). CLRP dapat diaplikasikan secara luas untuk berbagai bidang seperti distribusi makanan dan minuman, pengiriman surat kabar, pengumpulan sampah, pengiriman tagihan, pengiriman parsel, dan distribusi berbagai barang konsumen. Beberapa penelitian tentang problem CLRP tersebut telah banyak dilakukan, misalnya dengan menggunakan pendekatan heuristik yaitu two phase tabu search (Tuzun, et al.,1998), algoritma Simulated annealing (Yu, et al., 2009), dan greedy randomized adaptive search procedure (GRASP) (Duhamel, et al., 2009), maupun menggunakan metoda eksak yaitu branch and cut method (Belenguer, et al., 2010). Beberapa dari metoda tersebut mendapatkan hasil biaya opening facility dan distribusi kendaran yang kurang optimal, namun ada pula yang mendapatkan hasil biaya yang lebih minimal namun dengan waktu komputasi yang relatif lama. Metoda cross entropy sebagai salah satu metoda metaheuristik yang relatif baru telah digunakan dalam beberapa permasalahan optimasi kombinatorial, optimasi kontinu, optimasi noisy, dan rare event simulation (Kroese, 2009). Penelitian ini akan melakukan suatu pengembangan algoritma dengan pendekatan cross entropy (CE) untuk menyelesaikan permasalahan CLRP. Penggunaan pendekatan CE untuk mengembangkan algoritma dalam menyelesaikan permasalahan CLRP diharapkan menjadi alternatif untuk menghasilkan total biaya pembukaan depot dan biaya routing yang mendekati optimal.

Manfaat yang dapat diperoleh dari penelitian ini yaitu adanya metode pendekatan baru sebagai alternatif untuk penyelesaian Capacitated Location-Routing Problem (CLRP) sekaligus sebagai aplikasi CE pada permasalahan diskrit. 2. Metodologi Penelitian Pada bab ini akan dibahas mengenai model matematis Capacitated Location Routing serta langkah langkah pendekatan permasalahan tersebut menggunakan metoda Cross Entropy. 2.1 Model Matematis Adapun formulasi matematis untuk permasalahan CLRP ini dapat digambarkan sebagai berikut sesuai dengan model dari Prins et al. (2007). Misalkan G = (V, E) merupakan sebuah jaringan yang tidak terhubung langsung, dimana V adalah himpunan node/node yang terdiri dari himpunan I yang merupakan himpunan bagian dari m lokasi alternatif depot dan himpunan J = V / I dari n pelanggan. E adalah himpunan garis penghubung (edge) yang menghubungkan setiap pasang node di V. Hubungan yang terjadi pada masing-masing garis penghubung (i,j) E adalah biaya perjalanan C ij . Setiap lokasi depot i

I memiliki kapasitas W i dan memiliki

opening cost O i . Setiap pelanggan j J memiliki kebutuhan d j yang harus dipenuhi oleh satu kendaraan. Sebuah K himpunan kendaraan yang homogen dengan masing-masing kendaraan memiliki Q kapasitas tersedia. Setiap kendaraan, bila digunakan oleh i depot, maka depot dikenai tanggungan biaya tetap F i dan melakukan rute tunggal. Setiap rute harus dimulai dan berakhir pada stasiun yang sama, dan muatan total tidak boleh melebihi kapasitas kendaraan. Muatan total dari rute yang ditugaskan untuk depot harus sesuai dengan kapasitas depot. Tujuannya adalah untuk menentukan depot yang harus dibuka dan rute yang harus dibangun untuk meminimalkan total biaya depot dan routing.. Didefinisikan variabel biner y i = 1 jika depot i dibuka, f ij = 1 jika pelanggan j ditugaskan untuk depot i, dan x jik = 1 jika garis penghubung (j,i) dilalui dari j ke i pada rute yang dilakukan oleh kendaraan k K. Kemudian masalah dapat dirumuskan sebagai program integer biner berikut (Yu, et al): 𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧 = � 𝑂𝑂𝑖𝑖 𝑦𝑦𝑖𝑖 + � � � 𝑐𝑐𝑖𝑖𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 + � � � 𝐹𝐹𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖

(1)

� � 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 = 1

(2)

𝑖𝑖∈𝐼𝐼

Subject to: 𝑘𝑘∈𝐾𝐾 𝑖𝑖∈𝑉𝑉

� � 𝑑𝑑𝑗𝑗 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 ≤ 𝑄𝑄 𝑗𝑗 ∈𝐽𝐽 𝑖𝑖∈𝑉𝑉

𝑖𝑖∈𝑉𝑉 𝑗𝑗 ∈𝑉𝑉 𝑘𝑘∈𝐾𝐾

𝑘𝑘∈𝐾𝐾 𝑖𝑖∈𝐼𝐼 𝑗𝑗 ∈𝐽𝐽

∀𝑗𝑗 ∈ 𝐽𝐽

∀𝑘𝑘 ∈ 𝐾𝐾

(3)

2

� 𝑑𝑑𝑗𝑗 𝑓𝑓𝑖𝑖𝑖𝑖 ≤ 𝑊𝑊𝑖𝑖 𝑦𝑦𝑖𝑖 𝑗𝑗 ∈𝐽𝐽

� 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 − � 𝑥𝑥𝑗𝑗𝑗𝑗𝑗𝑗 = 0 𝑗𝑗 ∈𝑉𝑉

𝑗𝑗 ∈𝑉𝑉

� � 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 ≤ 1 𝑖𝑖∈𝐼𝐼 𝑗𝑗 ∈𝐽𝐽

� � 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 ≤ |𝑆𝑆| − 1 𝑖𝑖∈𝑆𝑆 𝑗𝑗 ∈𝑆𝑆

∀𝑖𝑖 ∈ 𝐼𝐼

∀𝑖𝑖 ∈ 𝑉𝑉, 𝑘𝑘 ∈ 𝐾𝐾 ∀𝑘𝑘 ∈ 𝐾𝐾

∀𝑆𝑆 ⊆ 𝐽𝐽, 𝑘𝑘 ∈ 𝐾𝐾

� 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 + � 𝑥𝑥𝑢𝑢𝑢𝑢𝑢𝑢 ≤ 1 + 𝑓𝑓𝑖𝑖𝑖𝑖 𝑢𝑢 ∈𝐽𝐽

𝑢𝑢∈𝑉𝑉∖{𝑗𝑗 }

𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 ∈ {0,1},

𝑦𝑦𝑖𝑖 ∈ {0,1},

𝑓𝑓𝑖𝑖𝑖𝑖 ∈ {0,1},

(4)

(5)

(6)

(7)

2.

∀𝑖𝑖 ∈ 𝐼𝐼, 𝑗𝑗 ∈ 𝐽𝐽, 𝑘𝑘 ∈ 𝐾𝐾 (8)

∀𝑖𝑖 ∈ 𝐼𝐼, 𝑗𝑗 ∈ 𝐽𝐽, 𝑘𝑘 ∈ 𝐾𝐾

∀𝑖𝑖 ∈ 𝐼𝐼

∀𝑖𝑖 ∈ 𝐼𝐼, 𝑗𝑗 ∈ 𝑉𝑉

(9)

(10)

(11)

Fungsi tujuan (1) merupakan jumlah dari biaya membuka depot dan routing cost yang terdiri dari travel cost dan fixed cost yang berhubungan dengan kendaraan yang digunakan. Batasan (2) memastikan bahwa setiap customer hanya berada dalam sebuah rute, batasan (3) dan (4) adalah batasan kapasitas yang berhubungan dengan rute dan depot. Batasan (5) dan (6) menjamin keberlangsungan setiap rute, dan bahwa setiap rute berakhir pada sebuah depot dimana rute tersebut bermula. Batasan (7) adalah batasan eliminasi subtour. Batasan (8) memastikan bahwa customer harus ditugasi oleh sebuah depot jika ada rute yang menghubungkannya. Dan yang terakhir,batasan (9),(10),dan (11) menetapkan variabel biner yang digunakan pada formula.

3.

4.

2.2 Algoritma yang diusulkan Langkah-langkah pendekatan permasalahan Capacitated Location-Routing Problem dengan metode CE adalah sebagai berikut: 1.

Pendefinisian input dan output yang dilakukan untuk menentukan input apa saja yang akan diproses dalam algoritma dan output apa saja yang akan ditampilkan sebagai hasil proses tersebut. Adapun pada penelitian ini, mengingat permasalahan yang diteliti adalah permasalahan CLRP dan metoda yang digunakan adalah cross entropy, maka input dan output yang digunakan adalah sebagai berikut: • Input: o Matriks koordinat customer dan depot (x,y) o Demand customer (dj) o Opening cost depot (Oi) o Kapasitas kendaraan (Q) dan kapasitas depot (Wi) o Fixed cost untuk setting up rute (Fi) o Jumlah sampel pembangkitan (N) o Parameter ρ o Parameter smoothing(α)

o Toleransi Pemberhentian (β) Output: o Depot terpilih dan urutan rute terbaik dari depot tersebut o Biaya pembukaan depot dan biaya routing yang optimum o Jumlah iterasi Menentukan parameter penunjang seperti ρ, α, dan jumlah sampel rute sebanyak N yang akan dibangkitkan pada setiap iterasi. Nilai α yang bagus adalah antara 0,7 sampai 1. Sedangkan N dan ρ ditentukan berdasarkan kasus yang diuji. Hal ini dikarenakan ρ merupakan parameter yang digunakan untuk menentukan sampel elite dari sampel sejumlah N. Menentukan intial value matriks transisi P yang nilai diagonalnya bernilai 0. Matriks transisi awal ini dihitung dengan rumus sebagai berikut. 𝑛𝑛 1 𝑃𝑃𝑖𝑖𝑖𝑖 = � − 1, … … . ∀ 𝑖𝑖 = 𝑗𝑗 𝑛𝑛

•

5.

6.

𝑃𝑃𝑖𝑖𝑖𝑖 =

𝑖𝑖

1

𝑛𝑛−1

, … … ∀𝑖𝑖 ≠ 𝑗𝑗

Untuk permasalahan location-routing ini, node pertama dalam suatu sampel harus ditempati oleh depot, sehingga node pertama ini dipilih secara random dari alternatif depot yang ada. Depot pada location-routing ini diberi indentitas dengan angka setelah konsumen untuk memudahkan perhitungan. Pembangkitan N sampel rute berdasarkan pada peluang matriks transisi yang dihitung mrnggunakan roullette wheel selection. Jika kumulatif peluang matriks transisi lebih besar dari suatu bilangan random yang dibangkitkan, maka node yang memiliki peluang tersebut merupakan node yang terpilih selanjutnya. Kemudian nilai setiap baris dari kolom node yang terpilih diganti menjadi 0 supaya tidak terpilih kembali dan dilakukan normalisasi supaya jumlah peluang setiap baris tetap bernilai 1. Penentuan rute yang disuplai oleh depot berdasarkan pada depot acuan yaitu node depot yang berada sebelum node konsumen. Jika setelah node depot tidak terdapat node depot juga atau terdapat dua node depot yang letaknya bersebelahan, maka depot yang awal tidak memiliki

3

7.

8.

konsumen dan boleh dihilangkan pada saat penentuan biaya. Penentuan subrute berdasarkan kapasitas kendaraan dan depot. Jika muatan suatu truk yang akan disuplai melebihi kapasitas kendaraan, maka untuk memenuhi node konsumen selanjutnya truk harus kembali ke depot. Dan jika jumlah muatan truk melebihi kapasitas depot, maka depot tidak dapat menyuplai lagi dan diganti oleh depot lain. Menghitung total biaya yaitu penjumlahan antara biaya perjalanan ,biaya pembukaan depot, dan setup rute. Biaya perjalanan sebanding dengan total jarak pada setiap rute yang dibangkitkan.

benar. Pada pengujian ini, digunakan data sederhana dengan melibatkan 4 konsumen dan 2 alternatif depot serta memiliki kapasitas kendaraan sebesar 40 unit dan kapasitas depot sebesar 80 unit seperti terlihat pada Tabel 3.1 dan 3.2. Tabel 3.1. Data Konsumen Koordinat Konsumen Demand no. (unit) x y 1 4 2 10 2 2 1 10 3 3 4 10

Depot no. 1 2

𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧 = � 𝑂𝑂𝑖𝑖 𝑦𝑦𝑖𝑖 + � � � 𝑐𝑐𝑖𝑖𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 + � � � 𝐹𝐹𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖 𝑖𝑖∈𝐼𝐼

𝑖𝑖∈𝑉𝑉 𝑗𝑗 ∈𝑉𝑉 𝑘𝑘∈𝐾𝐾

Tabel 3.2. Data Depot Biaya Koordinat pembukaan x y depot 1 3 5 4 4 5

Biaya setup rute 1 1

𝑘𝑘∈𝐾𝐾 𝑖𝑖∈𝐼𝐼 𝑗𝑗 ∈𝐽𝐽

Mengurutkan total biaya terbaik terlebih dahulu kemudian mengambil ρ*N terbaik yang dijadikan sebagai sampel elite. Sampel elite tersebut kemudian diplot kedalam matriks w dengan menggunakan node transition, dimana baris menyatakan node awal, dan kolom menyatakan node tujuan. 10. Memperbaharui transisi dari matriks P berdasarkan pembangkitan lintasan yang sesuai dengan rumus berikut: Pk+1 = α*w +(1-α)P Dengan w adalah probabilitas transisi yang dihitung dari sampel elite dan Pk adalah probabilitas transisi iterasi sebelumnya. 11. Jika syarat pemberhentian yang ditentukan telah tercapai maka iterasi berhenti dan hasil bisa diketahui, jika tidak sama maka proses kembali ke langkah 2. Syarat pemberhentian pada kasus ini adalah maksimum selisih Pk+1 dengan Pk ≤ 0,005.

9.

3. Uji Validasi Algoritma Pada bab ini akan dijelaskan mengenai contoh numerik Capacitated Location-Routing Problem (CLRP) yang diselesaikan dengan menggunakan algoritma Cross Entropy (CE) dan enumerasi sebagai uji validasi algoritma.

3.1 Contoh Numerik Sebelum menguji algoritma CE-CLRP dengan menggunakan set data, algoritma CE-CLRP diuji terlebih dahulu dengan menggunakan permasalahan sederhana untuk melakukan validasi apakah algoritma yang telah disusun dapat digunakan untuk mencari solusi atas permasalahan tersebut dengan

Tabel 3.3 Matriks Jarak Konsumen dan Depot

3.1.1 Penyelesaian dengan Enumerasi Penyelesaian dengan teknik enumerasi dilakukan dengan mencari permutasi dari matrik konsumen [1 2 3], kemudian mencoba menggabungkan hasil permutasi tersebut dengan alternatif depot satu persatu. Tabel 3.4 adalah hasil percobaan permutasi konsumen yang digabungkan dengan alternatif depot. Tabel 3.4. Penyelesaian dengan Enumerasi Depot 4 4 4 4 4 4 5 5 5 5 5 5

Permutasi rute konsumen 1 2 3 1 3 2 2 3 1 2 1 3 3 1 2 3 2 1 1 2 3 1 3 2 2 3 1 2 1 3 3 1 2 3 2 1

Hasil rute 4 4 4 4 4 4 5 5 5 5 5 5

1 1 2 2 3 3 1 1 2 2 3 3

2 3 3 1 1 2 2 3 3 1 1 2

3 2 1 3 2 1 3 2 1 3 2 1

4 4 4 4 4 4 5 5 5 5 5 5

Total Biaya buka Biaya setup jarak depot rute 10,79669 5 1 10,79669 5 1 10,79669 5 1 8,944272 5 1 8,944272 5 1 10,79669 5 1 8,398346 5 1 11,0039 5 1 9,634414 5 1 9,077687 5 1 9,077687 5 1 8,398346 5 1

3.1.2 Penyelesaian dengan CE Tahapan proses manual untuk penyelesaian permasalahan pada Tabel 3.1 dan Tabel 3.2 dengan algoritma CODEQ akan dijelaskan pada bagian berikut.

4

Total biaya 16,7967 16,7967 16,7967 14,9443 14,9443 16,7967 14,3983 17,0039 15,6344 15,0777 15,0777 14,3983

Langkah 1 Tahap inisialisasi Pada tahap ini ditetapkan parameter-parameter yang digunakan dalam perhitungan. Adapun parameter-parameter tersebut antaralain adalah: ρ = 0.3 α = 0.8 Toleransi pemberhentian (β) = 0.005 Jumlah sampel yang dibangkitkan(N) = 6. Langkah 2 Tahap pembangkitan matriks transisi awal Pada tahapan ini dibangkitkan matriks transisi berukuran n x n. Dimana n adalah banyaknya node yang terdapat pada permasalahaan. Dalam hal ini n berjumlah 5. Adapun mekanisme pembangkitan matriks transisi adalah sebagai berikut: 𝑛𝑛 1 𝑃𝑃𝑖𝑖𝑖𝑖 = � − 1, … … . ∀ 𝑖𝑖 = 𝑗𝑗 𝑛𝑛 𝑖𝑖 1 , … … ∀𝑖𝑖 𝑛𝑛−1

𝑃𝑃𝑖𝑖𝑖𝑖 = ≠ 𝑗𝑗 Dengan mengikuti tahapan diatas di dapatkan matriks transisi untuk uji validasi sebagai berikut: ⎡ ⎢ 𝑃𝑃𝑃𝑃 = ⎢ ⎢ ⎣

0 0,25 0,25 0,25 0 0,25 0,25 0,25 0 0,25 0,25 0,25 0,25 0,25 0,25

0,25 0,25 0,25 0 0,25

0,25 0,25 0,25 0,25 0

⎤ ⎥ ⎥ ⎥ ⎦

Langkah 3 Tahap pembangkitan N lintasan Pada tahap ini dibangkitkan sejumlah N lintasan sebagai sampel awal. Pembangkitan ini berdasarkan peluang yang terdapat pada matriks transisi. Untuk permasalahan LRP ini, node pertama dalam suatu sampel harus ditempati oleh sebuah depot. Oleh karena itu node pertama di pilih secara random dari alternatif depot yang diketahui. Depot diberi identitas dengan angka setelah konsumen untuk memudahkan perhitungan. Konsumen=[1 2 3] Depot=[4 5] Random depot = 4.

Untuk sampel pertama terpilih depot 4 sebagai node pertama. Sedangkan untuk entri selanjutnya dipilih berdasarkan bilangan random yang kurang dari atau sama dengan hasil kumulatif penjumlahan peluang untuk setiap node. Untuk lebih jelasnya, berikut contoh dari pembangkitan sampel pertama. Dikarenakan node terpilih 4, maka kolom ke 4 diubah menjadi 0 supaya tidak terpilih lagi. Matriks transisinya berubah sebagai berikut.

⎡ ⎢ 𝑃𝑃𝑃𝑃 = ⎢ ⎢ ⎣

0 0,25 0,25 0,25 0,25

0,25 0 0,25 0,25 0,25

0,25 0,25 0 0,25 0,25

0 0 0 0 0

0,25 0,25 0,25 0,25 0

⎤ ⎥ ⎥ ⎥ ⎦

Kemudian matriks transisi tersebut dinormalisasi sehingga tiap barisnya berjumlah satu seperti semula. Normalisasi dilakukan dengan membagi peluang tiap node dengan jumlah peluang tiap baris. 0 ⎡ 0,3333 ⎢ 𝑃𝑃𝑃𝑃 = ⎢ 0,3333 ⎢ 0,25 ⎣ 0,3333

0,3333 0 0,3333 0,25 0,3333

0,3333 0,3333 0 0,25 0,3333

0 0 0 0 0

0,3333 0,3333 0,3333 0,25 0

⎤ ⎥ ⎥ ⎥ ⎦

Dari normalisasi tersebut, dilihat angka probabilitas pada baris ke 4 kemudian dikumulatifkan untuk setiap node. Hal ini dilakukan karena node terpilih sebelumnya adalah 4. Berikut merupakan hasil kumulatif baris ke 4 tersebut. [0,25

0,5

0,75

0,75

1]

Kemudian dibangkitkan bilangan random untuk dibandingkan dengan kumulatif baris ke 4 tersebut. Pemilihan rute selanjutnya ini menggunakan roullette wheel selection untuk tiap baris. Dalam kasus ini bilangan random yang dibangkitkan adalah 0,939041. Bilangan random ini terletak antara nilai ke 3 dan ke 5, sehingga node ke 5 merupakan node yang terpilih. Hal ini berarti bahwa rute yang terbentuk adalah 4-5. Node selanjutnya dicari dengan cara yang sama yaitu dengan menjadikan 0 terlebih dahulu kolom 5 yang telah terpilih sebelumnya dan dinormalisasi sehingga setiap baris memiliki peluang yang berjumlah 1. Demikian seterusnya langkah ini dilakukan sampai terbentuk rute yang utuh dan hanya ada satu kolom matriks transisi yang berpeluang satu untuk setiap baris pada kolom yang sama yang berarti bahwa rute terakhir harus ditempati oleh node pada kolom tersebut. Dari tahapan ini diperoleh sebanyak N sampel yang ditampilkan pada Tabel 3.5 berikut. Tabel 3.5 Hasil Rute yang Dibangkitkan pada Iterasi 1

Sampel 1 Sampel 2 Sampel 3 Sampel 4

4 4 5 5

5 2 3 2

1 1 1 4

3 3 2 1

2 5 4 3

Sampel 5 Sampel 6

4 4

5 2

1 3

2 1

3 5

Langkah 4 Tahap penghitungan fungsi tujuan Setiap rute atau lintasan yang telah dibangkitkan, dihitung total biayanya untuk setiap sampelnya. Total

5

biaya ini dihitung dengan cara membagi depot acuan terlebih dahulu berdasarkan ada atau tidaknya customer. Misalkan untuk sampel pertama yang rutenya 4-5-1-3-2, depot 4 tidak diikuti oleh konsumen karena node setelah depot 4 adalah depot 5. Hal ini berarti bahwa depot 4 tersebut tidak dibuka. Sedangkan untuk depot 5, setelahnya ditempati oleh node 1-3-2 yang berarti bahwa konsumen 1-3-2 disuplai oleh depot 5 tersebut. Hal ini berarti bahwa node 5 tersebut bisa dibuka untuk melayani konsumen. Setelah dilakukan pemisahan menurut depot acuan tersebut maka bisa dihitung subtour untuk masing-masing pemisahan rute karena mekanisme melayani suatu node dibatasi oleh fungsi kapasitas dari kendaraan dan kapasitas depot yang digunakan. Dalam contoh sederhana ini jumlah permintaan kurang dari jumlah kapasitas depot dan kapasitas kendaraan, sehingga kedua batasan tersebut dapat diabaikan. Setelah terbentuk sub rute, maka jarak masing-masing sub rute yang telah dipisah dapat dihitung seperti pada tabel 3.6 berikut. Tabel 3.6 Perhitungan Jarak Dipecah menurut depot acuan Sampel 1 Sampel 2 Sampel 3 Sampel 4 Sampel 5 Sampel 6

4 4-2-1-3-4 5-3-1-2-5 5_2_5 4 4-2-3-1-4

5-1-3-2-5 5 4 4-1-3-4 5-1-2-3-5 5

Nilai jarak 0 11,0039 8,94427 0 9,07769 0 7,2111 7,634414 0 8,398346 10,7967 0

Jarak yang telah dihitung untuk masing-masing rute tersebut kemudian dijumlahkan dengan biaya pembukaan depot dan biaya setup rute untuk mendapatkan total biaya dari masing-masing sampel. Tabel 3.7 berikut merupakan hasil penjumlah seluruh biaya yang terlibat dalam penentuan depot dan rute ini. Tabel 3.7 Perhitungan Total Biaya Opening Setup Biaya depot rute perjalanan Sampel 1 11,00389691 5 1 Sampel 2 8,94427191 5 1 Sampel 3 9,07768723 5 1 Sampel 4 14,84551617 10 2 Sampel 5 8,398345638 5 1 Sampel 6 10,79669128 5 1

Total biaya 17,0039 14,9443 15,0777 26,8455 14,3983 16,7967

Langkah 5 Tahap pemilihan sample elite Setelah mendapatkan total biaya untuk masingmasing lintasan yang dibangkitkan, maka langkah selanjutnya adalah mengambil sample elite yang merupakan lintasan yang mempunyai total biaya minimum. Dengan mengacu pada biaya yang telah terhitung pada tahapan sebelumnya, pada tahapan ini diambil sebanyak

ρ*N terbaik. Biaya ini diurutkan terlebih dahulu untuk memudahkan pengambilan. Adapun pada iterasi pertama ini diambil sebanyak 2 sampel rute yang memiliki fungsi tujuan minimum. Adapun sampel elite iterasi 1 adalah sebagai berikut: Sampel 2

4

5

1

2

3

Sampel 5

4

2

1

3

5

Kedua sampel elite ini kemudian diplot kedalam matrik w yang akan digunakan untuk mengupdate matriks transisi. Berikut adalah matrik w yang merupakan node transition dari kedua sampel elite tersebut. Matriks w ini dihitung dengan menggunakan rumus (1/𝑔𝑔), dimana 𝑔𝑔 merupakan jumlah sampel elite yang diambil.

⎡ ⎢ 𝑤𝑤 = ⎢ ⎢ ⎣

0 0,5 0,5 0 0 0,5 0 0,5 0 0 ⎤ ⎥ 0 0 0 0,5 0,5 ⎥ 0 0,5 0 0 0,5 ⎥ 0,5 0 0 0,5 0,5 ⎦

Langkah 6 Update parameter Setelah didapatkan sekumpulan sampel terbaik yaitu sampel lintasan yang mempunyai total biaya 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. Parameter ini diperbaharui menggunakan rumus: Pk+1 = α*w +(1-α)Pk Dengan α= 0,8, Pk merupakan matriks transisi sebelumnya dan w adalah matriks hasil plot sampel elite.

Hasil pembaharuan parameter sesuai dengan langkah diatas adalah sebagai berikut: ⎡ ⎢ 𝑃𝑃 = ⎢ ⎢ ⎣

0 0,03 0,03 0 0,02 0,02 0,02 0,03 0,03 0,02

0,03 0,03 0 0,02 0,02

0,02 0,02 0,03 0 0,03

0,02 0,02 0,03 0,03 0

⎤ ⎥ ⎥ ⎥ ⎦

Langkah 7 Ulangi langkah 2 sampai dengan langkah 6 Pengulangan dilakukan hingga syarat pemberhentian terpenuhi yaitu ketika maksimum selisih Pk+1 dengan Pk ≤ 0,005. Tahap 1 sampai 6 pada akhirnya akan menghasilkan satu lintasan yang optimal, yang

6

mana lintasan ini mempunyai total biaya yang minimum. Setelah melakukan tahapan diatas maka dalam uji validasi algoritma ini didapatkan rute optimum untuk algoritma CE yang diperlihatkan pada Gambar 3.1 berikut.

rute terbaik

4- 5- 1- 2- 3

Subrute

5- 1- 2- 3- 5

total biaya

8,398

Gambar 3.1 Hasil Fungsi Tujuan Terbaik

Rute terbaik 4-5-1-2-3 tersebut berarti bahwa depot yang dipilih untuk dibuka adalah depot 5. Hal ini dikarenakan setelah depot 5 terdapat beberapa konsumen yang mengikutinya yaitu konsumen 1, 2, dan 3. Sedangkan depot 4 tidak memiliki konsumen sama sekali, karena setelah depot 4 langsung ditempati oleh depot 5.

Algoritma CE telah dituliskan dalam Matlab 7.10 (terlampir pada Lampiran) dan dapat digunakan untuk menyelesaikan problem pada Tabel 4.1 dan Tabel 4.2. Adapun solusi yang didapatkan setelah menjalankan program ini pada Matlab dapat dilihat di Tabel 3.8. Program ini dijalankan dengan nilai parameter yang sama seperti yang digunakan pada algoritma CE manual yaitu rho = 0,3, α = 0,8, toleransi pemberhentian = 0,005, dan sampel yang dibangkitkan= 6. Tabel 3.8. Solusi yang Didapatkan dari Metoda CE Replikasi

Rute terbaik

Depot yang dibuka

Total biaya

1 2

5-3-2-1-4 5-1-2-3-4

Depot 5 Depot 5

14,3983 14,3983

3

5-1-2-3-4

Depot 5

14,3983

3.2 Analisis Hasil Uji Data Validasi Pengujian validasi algoritma CE ini dilakukan dengan membandingkan solusi yang dihasilkan oleh algoritma CE baik secara manual maupun menggunakan matlab dengan solusi yang dihasilkan dengan cara enumerasi. Pada pengujian validasi, data yang digunakan adalah data sederhana dengan jumlah node konsumen sebanyak 3 buah, sedangkan node depot berjumlah 2 buah. Pengujian data menggunakan cara enumerasi tersebut dilakukan dengan mencari kombinasi depot dan urutan perjalanan konsumen. Untuk lebih memudahkan perhitungan, kombinasi konsumen dicari

terlebih dahulu kemudian baru digabungkan dengan alternatif depot satu per satu. Hal ini juga berdasarkan pada kapasitas depot yang dapat menyuplai keseluruhan konsumen, sehingga hanya diperlukan satu depot pada kasus sederhana ini. Dari keseluruhan permutasi tersebut kemudian dihitung total biaya pada setiap solusi sehingga dapat dilihat solusi yang menunjukkan total biaya terbaik yaitu rute 5-12-3 atau 5-3-2-1 dengan total biaya sebesar 14,3983. Pengujian menggunakan metode CE dilakukan sesuai tahapan algoritma yang telah dijelaskan pada Bab III dengan sampel yang dibangkitkan berjumlah 6 buah dengan manual dari algoritma CE. Hasil pengujian algoritma CE menunjukkan bahwa solusi yang dihasilkan algoritma CE sama dengan solusi hasil metode enumerasi sehingga algoritma CE untuk penyelesaian CLRP dikatakan valid. Hal ini juga membuktikan bahwa algoritma CE mempunyai kemampuan untuk mencapai solusi yang optimal karena solusi yang dihasilkan algoritma CE sama dengan solusi yang dihasilkan metode enumerasi dimana solusi yang dihasilkan metode enumerasi sudah pasti optimal. 4. Eksperimen dan Analisis Pada bab ini akan dilakukan pengujian terhadap set data capacitated location–routing problem (LRP) menggunakan algoritma Cross Entroppy (CE) serta analisis terhadap hasil pengujian algoritma yang dilakukan pada setiap set data. 4.1 Pengujian Data Set data yang digunakan untuk pengujian algoritma CE-CLRP adalah set data yang dibuat oleh Barreto (2004), Prins et al (2004), serta Tuzun dan Burke (1999). Set data yang akan digunakan dalam pengujian tersebut diambil dariClassicalinstancesforCLRP.http://prodhonc. free.fr/homepage. Set data Barreto (2004) ini merupakan permasalahan dengan data acak. Semua rute pada data ini memiliki kapasitas kendaraan dan beberapa data memiliki kapasitas depot. Tidak terdapat biaya variabel yang berhubungan dengan depot dan tidak ada pembulatan pada biaya perjalanan yang sebanding dengan jarak. Set data Prins et al.(2004) merupakan data yang memiliki kapasitas kendaraan maupun depot. Konsumen pada data ini terdiri dari beberapa kluster yang berbeda. Jumlah depotnya berkisar antara 5 atau 10, jumlah konsumen terdiri dari

7

20, 50, 100, atau 200, serta kapasitas kendaraan berkisar antara 70 atau 150. Data yang lain yaitu permintaan, kapasitas depot, dan biaya pembukaan depot merupakan data yang integer. Set data Tuzun dan Burke merupakan data yang memiliki kapasitas kendaraan dan dapat mengabaikan kapasitas depot. Hal ini ditunjukkan oleh jumlah permintaan konsumen yang lebih kecil dari kapasitas depot. Jumlah konsumen yang digunakan terdiri dari 100, 150, atau 200. Jumlah depotnya berkisar antara 10 atau 20 dan kapasitas kendaraannya 150. Pada set data Tuzun dan Burke, tidak dilakukan pembulatan pada jarak. 4.1.1 Hasil Pengujian Set Data Barreto Parameter yang digunakan dalam pengujian set data Barreto ini didapat dari pengujian parameter algoritma sesuai dengan rentang yang dianjurkan pada penelitian sebelumnya. Tabel 4.1 berikut adalah hasil untuk pengujian set data Barreto yang memiliki nilai terbaik. Tabel 4.1 Hasil Pengujian Set Data Barreto Prod ID

Jumlah konsumen

Jumlah depot

Kapasitas kendaraan

B1 B2 B5 B6 B7 B8 B9 B10 B11 B12 B15 B17

21 22 32 36 50 75 100 12 55 85 27 88

5 5 5 5 5 10 10 2 15 7 5 8

6000 4500 11000 250 160 140 200 140 120 160 2500 9000000

Hasil CELRP Jumlah Total biaya depot terpilih 424,9 2 593,7 1 512,8 1 478,4 1 584,8 1 869,3 1 871,1 1 204 1 1138,5 3 1662,7 3 3062 1 376,7 2

Pengujian data set Barreto ini dilakukan pada 12 kasus dan menghasilkan output berupa total biaya. Kolom pertama dalam tabel menunjukkan identitas kasus yang diuji. Untuk lebih memperjelas output yang dihasilkan, ditampilkan pula jumlah depot terpilih pada setiap kasusnya. Total biaya yang ditampilkan tersebut merupakan total biaya terbaik yang dihasilkan dari beberapa replikasi percobaan dengan kombinasi pengujian parameter yang berbeda-beda. Total biaya tersebut kemudian akan dibandingkan dengan total biaya pada referensi pembanding yang dapat dilihat pada Tabel 5.8 berikut.

Tabel 4.2. Perbandingan Metoda CE dengan Metoda Lain pada Pengujian Set Data Barreto

Tabel 4.2 tersebut menunjukkan perbandingan antara CE dengan metoda-metoda lain dalam kasus yang sama. BKS pada kolom 1 merupakan Best Known Solutions yaitu solusi terbaik yang didapat dari referensi pembanding. Pembanding pada tabel tersebut antaralain Cluster Heuristic (CH) (Barreto et al, 2007), Simulated Annealing-Ant Colony System (SAACS) (Bouhafs et al.,2006), Greedy Randomized Adaptive Search Procedure (GRASP) (Prins et al.,2006b), Memetic Algorithm with Population Management (MA|PM) (Prins et al.,2006a), Lagrangean Relaxation-Granular Tabu Search (LGRTS) (Prins et al.,2007), Genetic Algorithm Hybridized with Local Search (GAHLS) (Duhamel et al.,2008), dan Simulated Annealing-Local Search Heuristic (SALRP) (Yu et a.,2010). Keseluruhan pembanding tersebut didapat dari paper SALRP (Yu et al.,2010). Untuk lebih memperjelas perbandingan antara beberapa metoda tersebut, berikut akan diperbandingkan pula persentase GAP antara setiap metoda dengan Best Known Solutions (BKS). Persentase ini dihitung dengan rumus: (Nilai solusi dari metoda terkait-BKS)/BKS. Perbandingan tersebut dapat dilihat pada Tabel 4.3 berikut.

8

Tabel 4.3 GAP dari Setiap Metoda (%) Pengujian Barreto

4.1.2 Hasil Pengujian Set Data Prins et al. Parameter yang digunakan dalam pengujian set data Prins et al. ini didapat dari pengujian parameter pada rentang yang diajurkan oleh penelitian sebelumnya. Hasil untuk pengujian set data Prins et al yang memiliki nilai terbaik ditunjukkan pada Tabel 4.4 berikut. Tabel 4.4. Hasil Pengujian Set Data Prins et al. Hasil CELRP Jumlah Jumlah Kapasitas Prod ID Jumlah depot konsumen depot kendaraan Total biaya terpilih P2 P5 P6 P13 P19 P26

20 50 50 100 100 200

5 5 5 5 10 10

150 70 150 70 70 150

39104 90471 65137 286492 323514 421373

2 2 2 3 3 3

Pengujian data set Prins et al. ini dilakukan pada 6 kasus dan menghasilkan output berupa total biaya. Kolom pertama dalam tabel menunjukkan identitas kasus yang diuji. Untuk lebih memperjelas output yang dihasilkan, ditampilkan pula jumlah depot terpilih pada setiap kasusnya.Total biaya hasil pengujian kemudian dapat dibandingkan dengan metode lain menurut pada referensi pembanding. Perbandingan tersebut dapat dilihat pada tabel 4.5 berikut.

Tabel 4.5 Perbandingan Metoda CE dengan Metoda lain pada Pengujian Set Data Prins et al.

Tabel 4.5 tersebut menunjukkan perbandingan antara CE dengan metoda-metoda lain dalam kasus yang sama. BKS pada kolom 1 merupakan Best Known Solutions yaitu solusi terbaik yang didapat dari referensi pembanding. Pembanding yang terdapat pada tabel tersebut antaralain Multi Start-Local Search (MSLS) (Prins et al, 2004), Greedy Randomized Adaptive Search Procedure (GRASP) (Prins et al.,2006b), Memetic Algorithm with Population Management (MA|PM) (Prins et al.,2006a), Lagrangean Relaxation-Granular Tabu Search (LGRTS) (Prins et al.,2007), Genetic Algorithm Hybridized with Local Search (GAHLS) (Duhamel et al.,2008), dan Simulated Annealing-Local Search Heuristic (SALRP) (Yu et a.,2010). Keseluruhan pembanding tersebut didapat dari paper SALRP (Yu et al.,2010). Untuk lebih memperjelas perbandingan antara beberapa metoda tersebut, pada tabel 4.6 berikut akan diperbandingkan pula persentase GAP antara setiap metoda dengan Best Known Solutions (BKS). Persentase ini dihitung dengan rumus: (Nilai solusi dari metoda terkait-BKS)/BKS. Tabel 4.6 GAP dari Setiap Metoda (%) Pengujian Prins et al.

4.1.3 Hasil Pengujian Set Data Tuzun dan Burke Parameter yang digunakan dalam pengujian set data Tuzun dan Burke ini didapat dari pengujian parameter seperti yang telah dijelaskan pada sub bab 5.2. Hasil untuk pengujian set data Barreto yang memiliki nilai terbaik dapat dilihat pada Tabel 4.7 berikut.

9

Tabel 4.7 Hasil Pengujian Set Data Tuzun dan Burke.

Hasil CELRP Prod ID

T2 T13 T14 T26

Jumlah konsumen

Jumlah depot

Kapasitas kendaraan

100 150 150 200

20 10 20 20

150 150 150 150

Total biaya 1545,09 2029,94 1919,74 2385,78

Jumlah depot terpilih 1 1 1 1

Pengujian data set Tuzun dan Burke ini dilakukan pada 4 kasus dengan output berupa total biaya. Kolom pertama dalam tabel menunjukkan identitas kasus yang diuji. Depot yang digunakan hanya 1 semuanya karena permintaan konsumen kurang dari kapasitas depot. Total biaya yang dihasilkan kemudian dapat dibandingkan dengan total biaya pada referensi pembanding yang dapat dilihat pada Tabel 4.8 berikut. Tabel 4.8 Perbandingan Metoda CE dengan Metoda Lain pada Pengujian Set Data Tuzun dan Burke

Tabel 4.8 tersebut menunjukkan perbandingan antara CE dengan metoda-metoda lain dalam kasus yang sama. BKS pada kolom 1 merupakan Best Known Solutions yaitu solusi terbaik yang didapat dari referensi pembanding. Pembanding yang terdapat pada tabel tersebut antaralain Two Phase Tabu Search (2-Phase Tabu Search) (Tuzun dan Burke, 1999), Greedy Randomized Adaptive Search Procedure (GRASP) (Prins et al.,2006b), Memetic Algorithm with Population Management (MA|PM) (Prins et al.,2006a), Lagrangean Relaxation-Granular Tabu Search (LGRTS) (Prins et al.,2007), Genetic Algorithm Hybridized with Local Search (GAHLS) (Duhamel et al.,2008), dan Simulated Annealing-Local Search Heuristic (SALRP) (Yu et a.,2010). Keseluruhan pembanding tersebut didapat dari paper SALRP (Yu et al.,2010). Untuk lebih memperjelas perbandingan antara beberapa metoda tersebut, pada tabel 4.9 berikut akan diperbandingkan pula persentase GAP antara setiap metoda dengan Best Known

Solutions (BKS). Persentase ini dihitung dengan rumus: (Nilai solusi dari metoda terkait-BKS)/BKS. Tabel 4.9 GAP dari Setiap Metoda (%) Pengujian Tuzun dan Burke

4.2 Analisis Hasil Data Uji Uji performansi algoritma digunakan untuk mengetahui performansi algoritma CE pada penyelesaian CLRP dibandingkan dengan algoritma yang lain pada kasus yang sama. Pada pengujian ini data yang digunakan terdiri set data Barreto sebanyak 12 kasus, set data Prins et al. sebanyak 6 kasus, serta set data Tuzun dan Burke sebanyak 4 kasus. Dalam kasus tersebut yang dibandingkan adalah total biaya keseluruhan seperti pada referensi pembanding. 4.2.1 Analisis Hasil Uji Set Data Barreto Dari 12 kasus yang diselesaikan, algoritma CE dapat menghasilkan solusi yang kompetitif dengan Best Known Solution (BKS) yaitu pada kasus B2 dan B5 yang memiliki GAP sekitar 1%. Sementara itu untuk kasus B1, B10, dan B15, algoritma CE mampu menghasilkan solusi yang sama dengan BKS. Sementara untuk problem yang lain, algoritma CE dapat memberikan solusi dengan GAP maksimum sebesar 5,87%. Untuk lebih jelasnya, Gambar 4.1 berikut mernunjukkan grafik perbandingan CE-LRP dengan BKS. 4000 3000 2000 1000 0

BKS CELRP

1

3

5

7

9

11

Gambar 4.1 Perbandingan hasil solusi algoritma CE dengan BKS

Performansi algoritma CE tersebut dapat dibilang cukup baik karena beberapa solusi mampu menyamai hasil dari BKS. Beberapa solusi yang tergolong bagus, umumnya memiliki jumlah node yang lebih sedikit yaitu dibawah 30 node. Hal ini sangat dipengaruhi

10

Problem B1 440 435 430 425 420 415

B1

Gambar 4.2 Perbandingan hasil solusi beberapa metode pada problem B1

Performansi yang bagus tersebut, didukung oleh kualitas solusi yang dihasilkan oleh matriks transisi yang diperbaharui dengan memperhatikan sampel terbaik sebagai sampel elite. Selain itu juga adanya pengaruh jumlah node yang memiliki kemungkinan solusi lebih sedikit, sehingga solusi lebih mudah ditemukan dengan algoritma CE. 4.2.2 Analisis Hasil Uji Set Data Prins et al. Dari 6 kasus yang diselesaikan, performansi algoritma menurun seiring dengan meningkatnya jumlah node pada permasalahan. Untuk 20 node, performansi algoritma sangat bagus pada kasus P2 karena dapat menghasilkan

solusi yang sama dengan BKS. Sedangkan untuk kasus P5 problem memiliki GAP kecil yaitu 0,39% yang membuktikan bahwa performansi CE cukup bagus walaupun tidak dapat meghasilkan solusi yang sama. Untuk kasus yang lain performansi CE cenderung lebih buruk. GAP maksimum mencapai angka 12,34% dari BKS. Hubungan performansi GAP dengan jumlah node ini dapat dilihat pada Gambar 4.3 berikut. 15 GAP (%)

oleh sampel yang dibangkitkan. Banyaknya sampel yang dibangkitkan pada setiap iterasi, sangat mempengaruhi performansi CE-CLRP 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 dengan total biaya minimum akan semakin besar. Apabila node pada permasalahan sedikit, maka jumlah kemungkinan solusi juga sedikit yang mengakibatkan solusi bisa dengan mudah ditemukan dan tentunya dalam waktu yang cepat pula. Sementara itu untuk perbandingan dengan metode-metode lain dalam kasus yang sama, performansi CE cukup dapat dibilang baik mengingat beberapa solusi mampu menyamai dan bahkan mengalahkan beberapa metode terdahulu. Hal ini salah satunya bisa dilihat pada problem B1 Gambar 4.2 berikut, yang mana algoritma CE mampu mengalahkan metode Cluster Heuristic (CH) dan juga Simulated Annealing-Ant Colony System (SA-ACS) serta mampu menyamai metode-metode yang lain dengan total biaya sebesar 424,9.

10 5 CELRP

0 20 50 50 100100200 jumlah node konsumen

Gambar 4.3 Performansi GAP dilihat dari jumlah node konsumen

Seperti halnya yang telah dipaparkan sebelumnya, performansi CE dipengaruhi oleh jumlah pembangkitan sampel dibandingkan dengan semakin banyaknya kemungkinan solusi. Walaupun demikian, dibandingkan dengan data set Barreto, GAP untuk set data prins et al. memiliki performansi yang lebih baik. Hal ini lebih disebabkan set data Prins et al. merupakan data yang terkluster, sehingga lebih mudah diselesaikan. Untuk perbandingan dengan metode lain dalam set data Prins et al., metode CE-LRP tidak memiliki performansi yang cukup bagus jika dibandingkan dengan metode SA-LRP. Pada keseluruhan set data Prins et al ini hasil GAP SA-LRP bernilai 0 yang menunjukkan banyak solusi optimal yang dihasilkan oleh SALRP. Hal ini merupakan pengaruh local search heuristik yang ditambahkan dalam metode tersebut. Local search ini membantu SA-LRP dalam menyiapkan solusi yang sudah bagus untuk diberikan pada SA-LRP pada saat pembangkitan sampel. Walaupun demikian, hasil CELRP tetap dapat dikatakan baik dengan performansi total biaya yang lebih bagus dari metode yang lain seperti Multi Start-Local Search (MSLS) pada kasus P5 dan P6 serta Greedy Randomized Adaptive Search Procedure (GRASP) pada kasus P5. Performansi ini dapat dilihat pada Gambar 4.4 berikut.

11

MSLS

GRASP

980799063290471

CELRP

721596476165137

P5

P6

Gambar 4.4 Perbandingan metode untuk kasus P5 dan P6

Performansi bagus ini umumnya disebabkan node yang tidak terlalu banyak. Ketika jumlah node permasalahan lebih dari 100, maka performansi akan cenderung menurun atau lebih buruk dari keseluruhan metode. Hal ini kembali lagi pada jumlah kemungkinan solusi yang bertambah dengan bertambahnya jumlah node kasus. 4.2.3 Analisis Hasil Uji Set Data Tuzun dan Burke

Untuk hasil uji 4 kasus dari set data Tuzun dan Burke ini, algoritma CE-LRP menghasilkan solusi dengan kualitas yang lebih buruk dibanding set data sebelumnya. Performansi yang buruk tersebut dapat dilihat dari GAP CELRP dibandingkan dengan BKS yang memiliki nilai GAP minimum sebesar 4,67%. Selain itu juga dapat dilihat dari perbandingan total biaya dari beberapa metode yang menunjukkan algoritma CE-LRP tidak dapat melebihi ataupun sama dengan total biaya metode lain dan juga persentase GAP dengan nilai tertinggi untuk setiap kasus yang dapat dilihat pada Gambar 4.5. Hal ini dikarenakan node yang dimiliki setiap kasus memiliki ukuran yang besar yaitu diatas 100. GAP (%)

10

SALRP CELRP

5

2-PhaseTS

0

GRASP

T2

T13

T14

Problem

T26

MA|MP LRGTS

Gambar 4.5 Perbandingan metode untuk set dat Tuzun dan Burke

Jumlah node yang banyak ini sangat mempengaruhi algoritma CE-LRP dalam menemukan solusi dikarenakan kemungkinan solusi juga semakin membesar. Ketika jumlah kemungkinan solusi semakin besar, maka jumlah sampel yang dibutuhkan untuk mencapai

optimal juga membesar. Apabila sampel yang dibangkitkan tidak sebanding dengan sampel yang dibutuhkan untuk menemukan solusi, solusi yang diperoleh tersebut memiliki kemungkinan akan terjebak dalam local optimal. Dilihat dari hasil pengujian set data Tuzun dan Burke ini mengindikasikan bahwa dibutuhkan lebih banyak sampel dalam pengujian yang sebanding dengan banyaknya node permasalahan. 4.2.4 Analisis Performansi Keseluruhan Secara umum performansi algoritma CE dalam menyelesaikan LRP mampu menghasilkan solusi yang kompetitif dengan Best Known Solution (BKS) untuk node permasalahan yang berukuran kecil, sedangkan untuk permasalahan dengan skala besar masih memiliki performansi solusi yang lebih buruk. Khususnya untuk permasalahan dengan node diatas 100, algoritma CE ini menghasilkan solusi total biaya yang buruk baik dibandingkan dengan BKS maupun dibandingkan dengan metode lain dalam penelitian yang sama. Performansi yang buruk tersebut disebabkan oleh jumlah node yang banyak mengakibatkan kemungkinan solusi juga bertambah banyak. Terlebih apabila jumlah alternatif depot berjumlah sangat banyak sedangkan jumlah depot yang dipakai hanya 1 depot seperti pada set data Tuzun dan Burke. Oleh karena itu, sampel yang dibangkitkan oleh CE harus sebanding dengan kemungkinan solusi yang terjadi. Ketika algoritma CE kurang mencukupi dalam menemukan solusi pada saat pembangkitan sampel, maka solusi akan cenderung terjebak ke dalam local optimal. Sedangkan untuk performansi yang baik pada beberapa kasus lebih disebabkan oleh mekanisme pengambilan sampel elite pada algoritma CE yang kemudian digunakan untuk memperbaharui paramater matriks transisi sehingga didapatkan hasil solusi yang semakin mengarah pada solusi yang optimal. Selain itu juga dikarenakan banyaknya pembangkitan sampel yang sudah sesuai dengan banyaknya kemungkinan solusi. Banyaknya pembangkitan sampel pada algoritma CE ini mempengaruhi kualitas solusi yang dihasilkan. Hal ini dikarenakan pembangkitan solusi awal algoritma CE dilakukan dengan membangkitkan sejumlah sampel rute baru sebagai solusi baru pada iterasi berikutnya, sehingga semakin banyak jumlah sampel yang dibangkitkan akan

12

membuat algoritma CE lebih banyak memiliki referensi kemungkinan solusi. Untuk perbandingan CELRP dengan SALRP, CELRP memperlihatkan performansi yang sama seperti perbandingan dengan BKS. Dengan kata lain SALRP memiliki performansi yang bagus karena memiliki nilai yang sama dengan BKS. Performansi SALRP yang baik ini lebih disebabkan local search yang ditambahkan dalam algoritma tersebut. Local search ini berfungsi untuk mempersiapkan solusi yang lebih baik untuk dimasukkan kedalam algorima SA, sehingga solusi yang diolah dalam algoritma SA tersebut merupakan solusi yang sudah baik. Untuk algoritma SA sendiri sebenarnya memiliki mekanisme yang hampir mirip yaitu update parameter yang digunakan untuk menyaring solusi terbaik untuk setiap iterasinya sehingga solusi akan menuju ke arah solusi yang lebih baik. 5. Kesimpulan Dari hasil penelitian maupun analisis yang telah dilakukan, maka dapat diambil beberapa kesimpulan sebagai berikut: 1. Metode optimasi Cross Entropy dapat diaplikasikan untuk penyelesaian masalah Capacitated Location Routing dengan menentukan node pertama pada rute sebagai hasil pengambilan satu depot secara random dan node berikutnya diperoleh dari matriks transisi sebagai parameter utama yang berguna dalam pembangkitan sejumlah sampel rute sebagai kandidat solusi. 2. CE-CLRP dapat menunjukan performansi yang lebih baik pada permasalahan dengan jumlah konsumen di bawah 30 node. Performansi ini tidak lepas dari pembaharuan matriks transisi yang berdasarkan pada sampel terbaik (sampel elite). 3. Metode CE-CLRP dalam penyelesaian permasalahan sangat bergantung pada banyaknya pembangkitan sampel rute yang menunjukkan banyaknya kemungkinan solusi yang digunakan. 6. Daftar Pustaka Fisher Belenguer, J.M., Benavent, E., Prins, C., Prodhon, C., dan Calvo, R.W., 2010. A Branch-and-Cut method for the capacitated Location-Routing Problem. Computer & Operation Research, vol. 38, pp. 931-941.

Caserta, M. dan Rico, E.Q., 2007. A cross entropyLagrangean hybrid algorithm for the multiitem capacitated lot-sizing problem with setup times. Computer & Operation Research, vol. 36, pp.530-548.

De Boer, P.T., Kroese, D.P., Mannor, S., dan Rubinstein, R.Y., 2005. A Tutorial on the Cross-entropy method, Annals of Operations Research, vol. 134, No. 1, pp. 19-67. Duhamel, C., Laccome, P., Prins, C., dan Prodhon, C., 2009. AGRASP×ELS approach for the capacitated location-routing problem. Computer & Operation Research, vol. 37, pp.1912-1923. Kroese, D.P., 2009. Cross entropy Methode. Brisbane: Mathematics Department, University of Queensland. Lagua, M. Duarte, A. dan Marti, R., 2007. Hybridizing The Cross Entropy Method: An Application in The Max-Cut Poblem. Computer & Operation Research, vol. 36, pp.487-496. Lopes, R.B., Barreto, S., Ferreira, C., dan Santos, B.S., 2008. A Decision-Support Tool for A Capacitated Location-Routing Problem. Decision Support Systems, vol. 46, pp.366375. Nagy, G. dan Salhi, S., 2006. Invited Review Location-routing: Issues, models and methods. European Journal of Operational Research, vol. 177, pp. 649-672. Prodhon, C., 2008. Classical instances for CLRP. http://prodhonc.free.fr/homepage [Diakses tanggal 22 Februari 2010]. Rera, G.F., 2010. Penerapan Metoda Cross Entropy dalam Penyelesaian Capacitated Vehicle Routing Problem – Studi Kasus: Distribusi Koran Jawa Pos Surabaya. Surabaya: Institut Teknologi Sepuluh Nopember. Santosa, B. dan Willy, P. Metoda Metaheuristik Konsep dan Implementasi. Surabaya: Gunawidya. Tuzun, D. dan Burke, L.I., 1998. Theory and Methodology : A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, vol. 116, pp.87-99. Widyarini, T., 2009.Aplikasi Metode Cross Entropy untuk Support Vector Machines. Surabaya: Institut Teknologi Sepuluh Nopember. Wikipedia. Cross Entropy Method. http://en.wikipedia.org/wiki/cross_Entropy_ Method. Diakses pada 19 februari 2011. Yu, V.F. Lin, S.W. Lee, W. dan Ting, C. J., 2009. A simulated annealing heuristic for the capacitated location routing problem. Computer & Operation Research, vol. 58, pp.288-299.

13