PENGEMBANGAN ALGORITMA CROSS ENTROPY DALAM PENYELESAIAN TRAVELING PURCHASER PROBLEM

PENGEMBANGAN ALGORITMA CROSS ENTROPY DALAM PENYELESAIAN TRAVELING PURCHASER PROBLEM Citra Maharani, Budi Santosa Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email: [email protected] ; [email protected]

Abstrak Permasalahan optimasi yang semakin rumit menyebabkan permasalahan yang diselesaikan dengan pendekatan Exact Optimization membutuhkan waktu yang lama. Hal tersebut dikarenakan banyaknya alternatif solusi yang terbentuk dalam penyelesaiannya. Salah satu permasalahan yang berat untuk diselesaikan dengan metode Exact Optimization adalah Traveling Purchaser Problem. Permasalahan ini menjadi berat untuk diselesaikan karena terlalu banyaknya kemungkinan rute yang muncul ketika dimensi data meningkat sehingga membutuhkan waktu yang sangat lama untuk menemukan solusi rute yang optimal. Cross Entropy (CE) merupakan suatu algoritma yang relatif baru dengan dua fase utama, yaitu pembangkitan sampel solusi dari data random dan pembaharuan parameter dari mekanisme random dengan tujuan menghasilkan sampel yang lebih baik pada iterasi selanjutnya. Pada penelitian ini melibatkan 50, 100, 150, dan 300 market. Hasil yang dicapai dari penelitian ini adalah, CE belum memberikan performansi yang lebih baik daripada Local Search Algorithm, Ant Colony Optimization Algorithm, dan Transgenetic Algorithm. Kata kunci: Traveling Purchaser Problem, Traveling Salesman Problem, Cross Entropy ABSTRACT The increasing complexity of optimization problems eventually causes Exact Optimization approach took longer time to complete. The numerous alternative solution generated is the main cause of this phenomena. One of the toughest problems to be dealt with Exact Optimization is Traveling Purchaser Problem. This problem considered to be one of the toughest due to the enormous route possibility that occurs when data dimension increases, of which took a very long time to find the optimum solution. Cross Entropy is a new generated algorithm with two main phases, solution sample generation from a random data and parameter regeneration from a random mechanism to produce a better sample on the next iteration. This research involves 50, 100, 150, and 300 market. This research concludes that Cross Entropy performance is not better than Local Search Algorithm, Ant Colony Optimization Algorithm, and Transgenetic Algorithm. Keywords: Traveling Purchaser Problem, Traveling Salesman Problem, Cross Entropy

1. Pendahuluan Permasalahan transportasi merupakan permasalahan yang populer dan masih menarik untuk dibahas sampai saat ini. Salah satu permasalahan transportasi yang tidak asing adalah Traveling Salesman Problem (TSP). Traveling Salesman Problem (TSP) merupakan suatu permasalahan untuk menemukan rute perjalanan dari sejumlah kota, dengan ketentuan setiap kota harus dikunjungi tepat sekali dan harus kembali ke kota awal dimana total biaya transportasi yang terjadi minimal. TSP pertama kali ditemukan oleh Euler pada tahun 1759 yang mempunyai permasalahan bagaimana menggerakkan kesatria ke setiap posisi pada

papan catur tepat sekali. Dalam perkembangannya, TSP menjadi permasalahan yang terkenal pada buku yang ditulis oleh German salesman BF Voight pada tahun 1832 dengan judul "How to be a successful traveling salesman". Beliau menjelaskan bagaimana cara mencakupi lokasi sebanyak mungkin tanpa mengunjungi kota yang sama dua kali dengan mempertimbangkan aspek penjadwalan dari perjalanan. Awal mula TSP dalam matematika sekitar tahun 1931. Salah satu bentuk pengembangan TSP adalah Traveling Purchaser Problem (TPP). Sejumlah kota dalam permasalahan TSP merupakan sejumlah market dalam permasalahan TPP. Traveling Purchaser

Problem (TPP) yang merupakan pengembangan dari TSP pertama kali ditemukan oleh Ramesh pada tahun 1981 (Ravi & Salman, 1999). TPP merupakan suatu permasalahan dimana seorang pembeli mengunjungi market untuk membeli semua jenis produk yang dijual market sesuai dengan jumlah kebutuhan masing-masing produk. Dalam permasalahan ini, tiap market menjual jenis produk yang berbeda dan dengan harga produk yang berbeda pula. Dengan demikian penyelesaian TPP digunakan dalam penentuan rute kunjungan market untuk meminimasi biaya transportasi dan pembelian. Minimasi biaya transportasi dan biaya pembelian produk dilakukan dengan penentuan jarak market yang optimal dan dengan biaya pembelian produk yang optimal pula. Permasalahan TPP merupakan salah satu permasalahan NP-Hard. Hal tersebut dikarenakan tidak ada informasi mengenai algoritma polynomial yang eksak sehingga waktu komputasi dibatasi oleh suatu polynomial dengan pangkat n. Model atau algoritma penyelesaian yang dikembangkan oleh beberapa penelitei untuk menyelesaikan permasalahan TPP cukup banyak. Dalam menggunakan Exact Optimization seperti Branch and Bound Algorithm (Singh & Oudheusden, 1997), akan diperlukan waktu komputasi yang sangat lama terutama untuk problem berukuran besar (jika jumlah market yang tersedia banyak). Saat ukuran permasalahan meningkat, waktu komputasi juga meningkat secara eksponensial sehingga metode Exact Optimization tidak dapat digunakan. Oleh karena itu banyak penelitei berfokus pada Heuristic Algorithm. Penyelesaian TPP dengan menggunakan algoritma tersebut bertujuan menemukan solusi optimal secara efisien. Algoritma yang telah diterapkan adalah Dynamic Tabu Search (Stefan, 1996) dan Pendekatan Heuristic (Ledesma & Gonzales, 2005). Selain metode heuristik, beberapa metode metaheuristik juga diaplikasikan untuk menyelesaikan TPP, diantaranya Transgenetic Algorithm (TA) (Goldbarg et al., 2008) dan Ant Colony Optimization (ACO) (Bontoux & Feillet, 2008). Metode heuristic dan metode metaheuristik seperti TA dan ACO telah diterapkan dalam penyelesaian TPP. Oleh karena itu, pada penelitian ini akan dilakukan penyelesaian permasalahan TPP dengan menggunakan metode metaheuristik yang lain yaitu Cross Entropy (CE). Algoritma CE dipilih

dalam penelitian kali ini karena algoritma ini adalah algoritma baru dan telah menunjukkan hasil yang bagus saat menyelesaikan beberapa permasalahan optimasi (Laguna et al., 2007). Selain itu, penelitian TPP dengan menggunakan CE belum pernah dilakukan sebelumnya. Dengan demikian, tujuan dari penelitian ini adalah mendapatkan algoritma CE untuk TPP dan membandingkan performansi algoritma CE berupa total biaya dengan algoritma lain (LS, TA, dan ACO) untuk permasalahan TPP) 2. Metodologi Penelitian Pada metodologi penelitian akan diuraikan langkah-langkah sistematis untuk melakukan penelitian, yaitu kerangka berpikir, formulasi, dan pengembangan algoritma, sehingga akhirnya bisa menemukan solusi atau menghasilkan koherensi pembahasan untuk mendapatkan kesimpulan penelitian. Metodologi penelitian dalam penelitian tugas akhir ini terdiri dari pengumpulan data, pengembangan algoritma, validasi dan perbandingan algoritma. 2.1 Pengumpulan Data Data pada penelitian ini diambil dari data sekunder yang berasal dari TPPLIB Laporte tahun 2000. Data tersebut meliputi data kebutuhan tiap produk, produk yang dijual tiap market, harga produk tiap market, jumlah produk yang tersedia di tiap market, dan jarak antar market. Untuk pengujian data uji dilakukan untuk empat kasus berbeda yaitu data uji untuk problem 50, 100, 150, dan 300 market. 2.2 Pengembangan Algoritma Pada tahap ini dilakukan pengembangan algoritma CE untuk menyelesaikan TPP yang dikemukakan Ramesh tahun 1981. Penyelesaian TPP dilakukan berdasarkan persamaan matematis dari TPP Singh & Oudheusden tahun 1997. Berikut ini adalah tahpan pengembangan algoritma: 1. Penentuan Parameter Pada tahap ini dilakukan penetapan parameter dari algoritma ini, diantaranya adalah alpha (𝛼), rho (𝜌), dan jumlah sampel (N). Parameter 𝛼 digunakan untuk memperbaharui matriks probabilitas berdasarakan pengambilan jumlah sampel elite.

2

Parameter 𝜌 digunakan untuk menentukan jumlah proporasi sampel elite (sampel terbaik berdasarkan fungsi tujuan). 2. Generate matriks probabilitas transisi Pada tahap ini digenerate matriks transisi dimana nilainya tiap cell adalah 1/(n-1), dan nilai dari semua diagonal matriks tersebut adalah nol. 3. Pembangkitan N rute sebagai kandidat solusi Pada tahapan ini dilakukan pembangkitan rute TSP berdasarkan matriks transisi. Berikut ini adalah persamaan matematis dari TSP (Lawjer & Leastra, 1985) : N 1 N

 c

Min

i 1 j i 1

xij

(1)

2

(2)

ij

subject to j 1

N

x i 1

x

ij 

k  j 1

 x iS jS

ij

jk

 S 1

xij  0,1

(3) (4)

Pada persamaan matematis diatas, cij menunjukkan biaya transportasi dari kota(i) ke kota(j). Sedangkan jika xij bernilai 1, maka kota(i) mengunjungi kota(j) dan begitupula sebaliknya jika nilai xij bernilai 0. Pada (1) menunjukkan fungsi tujuan TSP yaitu minimasi total biaya transportasi. Konstrain (2) digunakan untuk menjamin bahwa tiap kota akan dikunjungi satu kali. Sedangkan pada kontrain (3) menunjukkan untuk memastikan bahwa tidak terjadi aliran bolak-balik pada kota yang telah dilewati. 4. Pemotongan Subrute Pada tahapan ini dilakukan pemotongan rute berdasarkan rute TSP yang telah dibangkitkan. Pemotongan subrute akan dilakukan jika kontrain dalam TPP telah terpenuhi semua. Berikut adalah persamaan matematis dari TPP (Singh & Oudheusden, 1997) :

m

n

m

m

 cij xij   hik yik

Min

i 1 j 1

(5)

i 1 k 1

subject to m

x i 1

ij

 1; j  1,..., n

(6)

m

xij   yik ; i  1,..., n

(7)

k 1 m

xij   yki ; j  1,..., n

(8)

xij  0,1; i  1,..., m; j  1,..., n

(9)

yij  0,1; i  1,..., m; k  1,..., n

(10)

k 1

Pada persamaan matematis diatas, (5) menunjukkan fungsi tujuan dari TPP yaitu meminimasi biaya transportasi dan pembelian produk. Pada konstrain (6) digunakan untuk menjamin masingmasing produk akan dibeli pada suatu market. Pada konstrain (7) dan (8) untuk menjamin market dengan jarak yang optimal yang nantinya sebagai tempat pembelian produk. 5. Perhitungan total biaya Perhitungan biaya didapatkan dari biaya tranportasi market yang dikunjungi dan biaya pembelian produk pada suatu market. 6. Pemilihan sampel elite Pada tahap ini dilakukan pemilihan sampel elite dengan cara 𝜌*N sampel rute dengan total biaya terbaik. 7. Update probabilitas Update probabilitias dilakukan sebagai acuan pembangkitan solusi pada iterasi selanjutnya. 8. Pengecekan kriteria pemberhentian Pada tahap ini dilakukan pengecekan terhadap kriteria pemberhentian, apabila belum terpenuhi mana kembali ke langkah 3, dan apabila telah terpenuhi, stop iterasi. Kriteria pemberhentian yang digunakan adalah 0.005 dimana hal tersebut menunjukkan selisis antara matriks proabilitas yang baru dengan yang lama tidak lebih dari kriteria pemberhentian yang telah ditentukan

3

3. Pengumpulan dan Pengolahan Data Bab ini meliputi tahap penentuan data yang akan diujikan terhadap algoritma Cross Entropy (CE), serta bagaimana pengujian model dilakukan dengan kerangka penelitian yang telah dibuat.

perjalanan_opt = 1

5

4

2

1

biaya = 1.565,954

3.1 Contoh Numerik Pada contoh numerik, data yang digunakan untuk pengujian model Traveling Purchaser Problem memiliki dimensi 5 market dengan 5 produk. Hasil dari enumerasi dengan metode CE dalam Traveling Purchaser Problem akan dibandingkan dengan tujuan untuk melakukan validasi bahwa algoritma yang dikembangkan dapat menyelesaikan permasalahan Traveling Purchaser Problem. Tabel 3.1 Koordinat Market Market 1 2 3 4 5

X 445 155 383 406 463

Y 258 958 849 523 414

Ket Depo

Tabel 3.2 Harga dan Produk yang dijual pada Market Market 1 2 3 4 5

Jumlah Type Harga Jumlah Type Harga Jumlah Type Harga Jumlah Type produk produk Produk produk produk Produk produk produk Produk 0 2 3 8 1 2 10 1 3 5 9 1 4 9 1 1 1 1 2 5 3 1 1 1 1 2 5 8 1 4 4 1 -

Tabel 3.3 Demand Tiap produk Produk1 1

Produk 2 1

Produk3 1

Produk4 1

Produk5 1

3.1.1 Penyelesaian dengan Enumerasi Penyelesaian dengan enumerasi akan dilakukan dengan cara membangkitkan semua rute yang mungkin dari permasalahan ini. Rute yang akan dibangkitkan sebanyak kemungkinan yang terjadi yaitu 24 rute, sehingga solusi terbaik dari enumerasi tersebut pasti merupakan global optimum dari permasalahan ini. Permasalahan diatas diselesaikan dengan manual menggunakan excel. Berikut ini merupakan solusi dari enumerasi yang telah dilakukan:

Gambar 3.1 Solusi Enumerasi

3.1.2 Penyelesaian dengan CE-TPP Langkah 1 Tahap inisialisasi Pada tahap ini, ditetapkan parameter ρ = 0.3, α = 0.8, dengan sampel yang dibangkitkan N = 10, dan stopping criteria = 0.005. Langkah 2 Tahap pembangkitan matriks transisi Pada tahap, ini dibangkitkan matriks transisi berukuran n x n. Dimana n adalah banyaknya market yang terdapat pada permasalahaan. Berikut adalah matriks transisi untuk uji validasi : 0 0.25 P = 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.25 0.25 0.25 0 0.25

0.25 0.25 0.25 0.25 0

Gambar 3.2 Matriks Transisi

Langkah 3 Tahap Pembangkitan Rute Pada tahap ini, dibangkitkan rute perjalanan berdasarkan peluang dari matriks transisi, dimana semua market akan dikunjungi. Berikut ini adalah rute hasil pembangkitan : Tabel 3.4 Hasil Rute Awal No Rute 1 2 3 4 5 6 7 8 9 10

Rute Perjalanan Optimal 1 2 3 5 4 1 5 4 2 3 1 2 4 5 3 1 4 2 3 5 1 4 3 2 5 1 2 5 4 3 1 2 3 4 5 1 2 5 3 4 1 3 5 4 2 1 5 3 4 2

Langkah 4 Tahap subtour Pada tahap ini, akan dilakukan pemotongan rute jika kebutuhan tiap produk telah terpenuhi. Berikut ini adalah hasil subtour :

4

Tabel 3.5 Hasil Rute Subtour No Rute 1 2 3 4 5 6 7 8 9 10

Rute Perjalanan Optimal 1 2 3 1 1 5 4 2 1 1 2 4 5 1 1 4 2 3 1 1 4 3 2 1 1 2 5 4 1 1 2 3 1 1 2 5 3 1 1 3 2 1 1 5 3 2 1

Langkah 5 Tahap Total Biaya Pada tahap ini dilakukan perhitungan total biaya sesuai dengan fungsi tujuan dari permasalahan.

0 0.3333 0 0.3333 0.3333 0 0 0.3333 0.3333 0.3333 P = 0.6667 0.3333 0 0 0 0 0.3333 0.3333 0 0.3333 0.3333 0 0.3333 0.3333 0

Gambar 3.3 Matriks Probabilitas Empiris Semua Market Dikunjungi 0 0.3333 0 0.3333 0.3333 0 0 0 0.3333 0.3333 P = 0.6667 0.3333 0 0 0 0 0.3333 0.3333 0 0.3333 0.3333 0 0 0.3333 0

Gambar 3.4 Matriks Probabilitas Empiris Pemotongan Market

Tabel 3.6 Total Biaya dari Rute Subtour No Rute 1 2 3 4 5 6 7 8 9 10

Rute Perjalanan Optimal 1 2 3 1 1 5 4 2 1 1 2 4 5 1 1 4 2 3 1 1 4 3 2 1 1 2 5 4 1 1 2 3 1 1 2 5 3 1 1 3 2 1 1 5 3 2 1

Total Biaya 1641 1566 1566 1648 1636 1799 1641 2450 1641 1640

Langkah 6 Tahap Pemilihan Sampel elite Pada tahap ini, masing-masing rute yang dibangkitkan selanjutnya akan ditentukan suatu sampel elite. Pada tahapan ini dilakukan pengambilan sebanyak ρ*N yaitu sebanyak 3 sampel. Berikut ini merupakan sampel elite yang didapat: Tabel 3.7 Pemilihan Sampel Elite No Rute 2 3 5

Rute Perjalanan Optimal 1 5 4 2 1 1 2 4 5 1 1 4 3 2 1

Total Biaya 1566 1566 1636

Langkah 7 Tahap Update Parameter Pada tahap ini, akan dilakukan update parameter dengan menghitung peluang empiris dari sampel elite yang didapat. Berikut ini merupakan peluang empiris dari sampel elite :

Kemudian dilakukan update parameter, berikut adalah rumus yang digunakan dalam update parameter :

p(i, j )    r  (1   )  pold

Berikut adalah hasil update matriks probabilitas : 0 0.0500 P = 0.5833 0.0500 0.3167

0.3167 0 0.3167 0.3167 0.0500

0.0500 0.0500 0 0.3167 0.0500

0.3167 0.3167 0.0500 0 0.3167

0.3167 0.0500 0.0500 0.3167 0

Gambar 3.5 Matriks Probabilitas yang telah Update

Langkah 8 Penentuan rute optimal Berikut ini adalah solusi dari metode CE-TPP secara manual : perjalanan_opt = 1

5

4

2

1

biaya = 1.566 Gambar 3.6 Solusi Matlab CE-TPP

berikut ini merupakan hasil perbandingan solusi antara metode enumerasi dengan CE-TPP :

5

Tabel 3.8 Hasil Pengujian Data Validasi Metode Rute Perjalanan Optimal Total Biaya Enumerasi 1–5–4–2–1 1.565,954 CE-TPP 1–5–4–2–1 1.566

3.2 Pengujian Data Pengujian Algoritma CE dalam penyelesaian TPP dilakukan untuk 4 kasus. Hasil dari algoritma CE dengan jumlah 50, 100, dan 150 market akan dibandingkan dengan Algoritma LS, sedangkan hasil algoritma CE dengan jumlah 300 market akan dibandingkan dengan Algoritma ACO dan TA. Tiap kasus menggunakan parameter N, 𝜶, dan 𝝆 yang berbeda sejumlah n replikasi untuk masingmasing parameter dan output yang dihasilkan dipilih yang terbaik untuk kemudian dibandingkan dengan Algoritma lain. Untuk mengetahui performansi Algoritma, maka dilakukan perhitungan ARPD (Average Relative Percentage Deviation) yang besarnya dapat dihitung dengan menggunakan rumus :

ARPD 

best _ known  solusi  100% best _ known

dimana best known didapat dari solusi terbaik dari jurnal yang akan dijadikan pembanding. Pengujian dengan jumlah 50, 100, dan 150 market dilakukan dengan menggunakan 7 kombinasi parameter yang berbeda, sedangkan pada pengujian dengan jumlah 300 market dilakukan dengan menggunakan 5 kombinasi parameter yang berbeda. Stopping criteria yang digunakan dalam pengujian Algoritma CE adalah 0.005 dimana selisih maksimum dari matriks transisi dengan matriks transisi yang belum terupdate adalah kurang dari stopping criteria yang ditentukan. Berikut adalah parameter-parameter yang digunakan : Tabel 3.9 Kombinasi Parameter Algoritma CE Parameter 1 2 3 4 5 6 7

N 1000 1000 10000 10000 30000 50000 10000

Alpha 0.6 0.8 0.6 0.8 0.6 0.6 0.6

Rho 0.01 0.01 0.001 0.001 0.0008 0.001 0.01

solusi terbaik yang dihasilkan dari Algoritma CE : Tabel 3.10 Solusi Terbaik Algoritma CE Jumlah Market

CE

LS

50 100 150 300

1860 1484 1675 1305

1856 1468 1658 -

RPD CE - LS 0.22% 1.09% 1.03% -

ACO 1257

RPD CE-ACO 3.82%

TA 1256

RPD CE - TA 3.90%

3.2.1 Pengujian Data 50 Market Pengujian data sejumlah 50 market dengan 50 produk dilakukan dengan bantuan software MATLAB dengan menggunakan 7 kombinasi parameter yang berbeda. Berikut adalah solusi terbaik dari tiap parameter : Tabel 3.11 Hasil Pengujian Data 50 Market dengan 50 Produk Parameter 1 2 3 4 5 6 7

1 1 1 1 1 1 1

32 41 19 19 19 32 32

24 32 35 35 35 24 24

Rute 15 24 23 15 5 15 23 5 15 23 5 15 23 46 23 15 46 23 15 23

5

35 19 1 35 19 5 1 46 24 32 1 46 24 32 1 46 24 32 1 5 35 19 1 5 35 19 1

Biaya 1864 1952 1860 1860 1860 1860 1860

3.2.2 Pengujian Data 100 Market Pengujian data sejumlah 100 market dengan 50 produk dilakukan dengan bantuan software MATLAB dengan menggunakan 7 kombinasi parameter yang berbeda. Berikut adalah solusi terbaik dari tiap parameter : Tabel 3.12 Hasil Pengujian Data 100 Market dengan 50 Produk Parameter 1 2 3 4 5 6 7

1 1 1 1 1 1 1

69 75 69 69 69 54 4

69 69

Rute 94 75 86 53 10 94 60 53 10 75 94 53 10 75 94 53 75 94 86 53 22 75 94 86 53 22 75 94 86 53

22 22 22 22 22

1 1 1 1 1 1 1

Biaya 1525 1700 1508 1508 1493 1484 1485

3.2.3 Pengujian Data 150 Market Pengujian data sejumlah 150 market dengan 50 produk dilakukan dengan bantuan software MATLAB dengan menggunakan 7 kombinasi parameter yang berbeda. Berikut adalah solusi terbaik dari tiap parameter :

Dari hasil pengujian dengan beberapa parameter yang telah dilakukan, berikut adalah

6

Tabel 3.13 Hasil Pengujian Data 150 Market dengan 50 Produk Parameter 1 2 3 4 5 6 7

Rute 1 122 28 25 115 150 15 53 14 1 1 53 15 72 21 43 28 115 54 1 1 87 15 69 150 10 115 28 14 53 1 1 43 15 150 61 115 28 53 14 1 1 14 53 15 150 61 25 115 10 28 1 1 105 28 61 115 10 150 15 53 14 1 1 14 53 15 150 10 115 61 28 1

Biaya 1992 2156 1837 1846 1763 1675 1688

3.2.4 Pengujian Data 300 Market Pengujian data sejumlah 300 market dengan 50 produk dilakukan dengan bantuan software MATLAB dengan menggunakan 5 kombinasi parameter yang berbeda. Berikut adalah solusi terbaik dari tiap parameter : Tabel 3.14 Hasil Pengujian Data 300 Market dengan 50 Produk Parameter 1 2 3 4 7

Rute 1 169 211 176 279 42 216 179 146 1 1 129 14 169 211 85 248 42 50 138 1 1 118 150 262 186 103 84 122 146 197 1 1 84 226 103 85 119 118 68 1 1 94 185 281 169 199 179 154 1

Biaya 1943 2661 1477 1569 1305

3.3 Perbandingan Parameter Solusi Pada subbab ini akan dilakukan perbandingan kombinasi parameter solusi yang telah ditentukan. 3.3.1 Perbandingan Parameter Solusi CE-LS Berikut adalah hasil perhitungan ARPD Algoritma CE dengan Algoritma LS dalam penyelesaian TPP untuk 50, 100, dan 150 market dengan 50 produk : Tabel 3.15 Perbandingan Parameter Solusi CE-LS Parameter PAR 1 PAR 2 PAR 3 PAR 4 PAR 5 PAR 6 PAR 7 ARPD Terkecil

50 Market 5.39% 6.88% 0.29% 0.29% 0.22% 0.22% 0.22% 0.22%

ARPD 100 Market 150 Market 16.67% 26.80% 18.44% 37.86% 2.72% 19.88% 3.09% 32.45% 1.70% 9.85% 1.50% 9.79% 1.45% 5.65% 1.45%

5.65%

3.3.1 Perbandingan Parameter Solusi CEACO-TA Berikut adalah hasil perhitungan ARPD antara Algoritma CE dengan Algoritma ACO dan TA dalam penyelesaian TPP untuk 300 market dengan 50 produk :

Tabel 3.16 Perbandingan Parameter Solusi CE – ACO dan CE - TA Parameter PAR 1 PAR 2 PAR 3 PAR 4 PAR 7

ARPD CE - ACO CE - TA 57.73% 57.86% 111.69% 111.86% 20.90% 20.99% 24.82% 24.92% 3.82% 3.90%

4. Analisis dan Pembahasan Pada bab analisis dan pembahasan akan dilakukan analisis terhadap hasil uji coba model yang telah dilakukan sebelumnya. Analisis dilakukan untuk setiap pendekatan yang digunakan. 4.1 Analisis Hasil Uji Data Validasi Pada pengujian data validasi, dilakukan perbandingan antara penyelesaian secara enumerasi dengan penyelesaian dengan CETPP. Pengujian enumerasi dilakukan dengan membangkitkan semua kemungkinan rute yang ada untuk kemudian dibandingkan dengan penyelesaian dengan menggunakan algoritma CE, dimana parameter algoritma CE yang digunakan adalah N=10, 𝜌=0.3, 𝛼 =0.8, dan stopping criteria 0.005. Setelah didapatkan rute tersebut, maka dilakukan pengambilan sampel elite berdasarkan biaya transportasi dan biaya pembelian produk yang paling minimum sebanyak 𝜌*N yaitu 3 sampel dengan solusi terbaik. Pada Tabel 4.9 menunjukkan bahwa kedua metode perbandingan yang digunakan menghasilkan solusi rute dan total biaya yang sama. 4.2 Analisis Hasil data Uji Pengujian Algoritma CE dilakukan menggunakan 4 kasus dengan jumlah market yang berbeda. Tabel 4.11 menunjukkan solusi total biaya terbaik yang dicapai dengan menggunakan Algoritma CE. Pada kasus pertama dengan jumlah 50 market, solusi terbaik dari Algoritma CE menunjukkan RPD sebesar 0.22% lebih buruk dibandingkan dengan Algoritma LS. Pada kasus kedua dengan jumlah 100 market, solusi terbaik dari Algoritma CE menunjukkan RPD sebesar 1.09% dibandingkan dengan Algoritma LS. Pada kasus ketiga dengan jumlah 150 market, solusi terbaik dari Algoritma CE menunjukkan RPD sebesar

7

4.3 Analisis Perbandingan Parameter Solusi Pengujian Algoritma CE pada kasus sejumlah 50, 100, dan 150 market dilakukan dengan 7 kombinasi parameter yang berbeda untuk masing-masing kasus. Dari pengujian

yang telah dilakukan, kombinasi parameter 7 dengan jumlah N=10.000, 𝛼=0.6, dan 𝜌=0.01 menunjukkan ARPD yang paling kecil. Grafik perbandingan ARPD dengan kombinasi 7 parameter dapat dilihat pada Gambar 4.1. 40.00% 35.00% 30.00%

ARPD

25.00% 20.00%

50 Market

15.00%

100 Market 150 Market

10.00% 5.00% 0.00% PAR 1 PAR 2 PAR 3 PAR 4 PAR 5 PAR 6 PAR 7 Parameter

Gambar 4.1 Perbandingan ARPD antara CE dan LS untuk berbagai Parameter

Pengujian Algoritma CE untuk kasus 300 market dilakukan dengan 5 kombinasi parameter yang berbeda. Dari pengujian yang telah dilakukan, kombinasi parameter 7 dengan jumlah N=10.000, 𝛼=0.6, dan 𝜌=0.01 menunjukkan ARPD yang paling kecil. Grafik perbandingan ARPD dengan kombinasi 5 parameter dapat dilihat pada Gambar 4.2. 120.00% 100.00% 80.00%

ARPD

1.03% lebih buruk dibandingkan dengan Algoritma LS. Dalam pengujian ketiga kasus tersebut solusi dari Algoritma CE belum menghasilkan solusi yang lebih baik atau sama dengan Algoritma LS. Pada kasus keempat dengan jumlah 300 market, solusi terbaik dari Algoritma CE menunjukkan RPD sebesar 3.82% lebih buruk dibandingkan dengan Algoritma ACO. Jika dbandingkan dengan Algoritma TA, solusi terbaik dari Algoritma CE menunjukkan RPD yang lebih besar yaitu 3.90% lebih buruk. Dalam pengujian kasus keempat tersebut solusi dari Algoritma CE belum menghasilkan solusi yang lebih baik atau sama dengan Algoritma Metaheuristic yang lain. Perbedaan teknik inisialisasi dan teknik pencarian solusi yang digunakan juga berpengaruh terhadap solusi dari hasil pengujian. Pada Algoritma CE, teknik inisialisasi yang digunakan adalah pembangkitan bilangan random dengan menggunakan node transition dan teknik pencarian solusi yang digunakan adalah update parameter dari mekanisme bilangan random berdasarkan jumlah sampel elite terbaik yang terpilih. Pada LS Algorithm, teknik pencarian solusi yang digunakan adalah l-consecutive exchange dan insertion. Kedua prosedur tersebut dilakukan dengan tujuan untuk menyimpan solusi terbaik untuk kemudian digunakan sebagai perbaikan dalam pembangkitan sampel pada iterasi berikutnya. Pada ACO, teknik inisialisasi yang digunakan adalah Dynamic Multi Dimensional Anamorphic Traveling Ants Algorithm. Teknik tersebut menggunakan sistem penalti terhadap Traveling Ants yang dibangkitkan, sedangkan anamorphic digunakan sebagai parameter dalam pembangkitan sampel, dan teknik pencarian solusi yang digunakan adalah LS. Sedangkan pada TA, teknik insialisasi dilakukan dengan memodifikasi variasi random untuk mempermudah dalam pencarian solusi dan teknik pencarian solusi dilakukan dengan pertukaran gen dalam suatu cell ataupun antar cell.

60.00% CE - ACO 40.00%

CE - TA

20.00%

0.00% PAR 1

PAR 2

PAR 3

PAR 4

PAR 7

Parameter

Gambar 4.2 Perbandingan ARPD antara CE-ACO dan CE-TA untuk berbagai Parameter

Kombinasi parameter 7 menunjukkan prosentase ARPD yang kecil dalam pengujian 4 kasus karena proses pencarian solusi pembangkitan dilakukan dengan populasi yang cukup besar yaitu 10.000. Selain itu, parameter 𝛼 yang tidak terlalu besar yaitu 0.6 mengakibatkan proses update menjadi lebih smooth sehingga ada kemungkinan untuk menghasilkan solusi yang lebih baik dalam iterasi selanjutnya. Parameter 𝜌 yang tidak terlalu kecil yaitu 0.01 mengakibatkan

8

6.000% 5.000%

4.000% ARPD

pengambilan jumlah sampel elite yang lebih besar sehingga kemungkinan solusi terbaik yang dipilih lebih banyak dan konvergensi tidak terlalu cepat. Pada kasus sejumlah 50, 100 dan 150 market, jika kombinasi parameter 7 dibandingkan dengan kombinasi parameter 5 (N=30.000, 𝛼=0.6, dan 𝜌=0.0008) dan 6 (N=50.000, 𝛼=0.6, dan 𝜌=0.001), kombinasi parameter 7 sedikit lebih baik dibandingkan kombinasi parameter 5 dan 6. Hal tersebut dikarenakan penggunaan 𝜌 yang terlalu kecil pada kombinasi parameter 5 dan 6, sehingga mengakibatkan konvergensi yang terlalu cepat. Jika dibandingkan antara kombinasu parameter 5 dan 6, ARPD pada kombinasi parameter 6 jauh lebih kecil dibandingkan dengan kombinasi parameter 5. Hal tersebut dikarenakan pengambilan jumlah sampel elite pada kombinasi parameter 6 lebih besar dibandingkan dengan kombinasi parameter 5, sehingga konvergensinya tidak terlalu cepat. Faktor pengambilan dengan jumlah sample elite juga terjadi pada kasus dengan jumlah 300 market, pengambilan jumlah sampel elite pada kombinasi parameter 7 lebih besar dibandingkan dengan kombinasi parameter 4 (N=10. 𝛼=0.6, dan 𝜌=0.001) sehingga ARPD pada kombinasi parameter 7 jauh lebih kecil dibandingkan dengan kombinasi parameter 4. Dari hasil pengujian pada kasus 50, 100, dan 150 market, semakin tinggi jumlah market pada permasalahan TPP maka tingkat prosentase gap akan semakin tinggi pula. Hal tersebut dikarenakan kemungkinan kandidat solusi akan lebih banyak sehingga parameter yang digunakan perlu disesuaikan lagi. Perbandingan tersebut diambil dari rata-rata ARPD terkecil tiap parameter. Pada Gambar 4.3 menunjukkan grafik performansi Algoritma CE dengan kombinasi 7 parameter terhadap peningkatan dimensi permasalahan.

3.000% GAP Rata-rata Terkecil(%)

2.000% 1.000%

0.000% 50

100

150

Jumlah Market

Gambar 4.3 Performansi Algoritma CE

5. Kesimpulan dan Saran Bab ini berisi tentang kesimpulan hasil penelitian dan saran yang berkaitan dengan penelitian selanjutnya. 5.1 Kesimpulan Dari hasil eksperimen dan analisis, maka dapat diambil kesimpulan sebagai berikut : 1. Algoritma Cross Entropy berhasil dikembangkan untuk penyelesaian Traveling Purchaser Problem 2. Algoritma Cross Entropy diuji pada 4 set data dan hasilnya dibandingkan dengan Algoritma Local Search, Ant Colony Optimization, dan Transgenetic Algorithm 3. Dari hasil pengujian, Algoritma Cross Entropy belum menunjukkan performansi yang lebih baik dibandingkan dengan Algoritma lain 4. Kelemahan Cross Entropy adalah harus menggunakan sampel berukuran besar sehingga waktu komputasi yang dibutuhkan lama 5.2 Saran Saran yang sebaiknya dilakukan untuk penelitian selanjutnya sehingga dapat menyempurnakan penyelesaian Algoritma CE untuk TPP adalah perlu dilakukan modifikasi untuk meminimalkan waktu komputasi dan bisa mencari solusi yang lebih baik.

9

6. Referensi Bontoux, B. & Feillet, D., 2008. Ant colony optimization for the traveling purchaser problem. Computers and Operations Research, 35, pp.628-37.

Stefan, 1996. Dynamic tabu search strategies for the traveling purchaser problem. Annals of Operations Research, 63, pp.253-57.

Goldbarg, M.C., Bagi, L.B. & Goldbarg, E.F.G., 2008. Transgenetic algorithm for the Traveling Purchaser Problem. European Journal of Operational Research, 199, pp.36-45. Laguna, M., Duarte, A. & Marti, R., 2007. An Application in The Max-Cut Problem Hybridizing The Cross Entropy Method. Operational Reasearch, pp.1-16. Laporte, G., Ledesma, J.R. & Gonzales, J.S.J., 2003. A Branc and Cut Algorithm for the Undirected Traveling Purchaser Problem. Operations Research , 51, pp.142-52. Lawjer, E.L. & Leastra, J.K., 1985. The Traveling Salesman Problem : A Guided Tour of Combinatorial Problem. New York: Willey. Ledesma, J.R. & Gonzales, J.J.S., 2005. A heuristic approach for the Travelling Purchaser Problem. European Journal of Operational Research, 162, p.142–152. Ravi, R. & Salman, F.S., 1999. Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design. Proceedings of the 7th annual Eoropean symposium on algorithms, 1643, pp.29-40. Rubinstein, R.Y., 1999. The Cross Entropy Method for Combinatorial and Continuous Optimization. Methodology and Computing in Applied Probability, pp.127-90. Santosa, B. & Willy, P., 2011. Metode Metaheuristik Konsep dan Implementasi. 1st ed. Surabaya: Guna Widya. Singh, K.N. & Oudheusden, D.L.v., 1997. A branch and bound algorithm for the traveling purchaser. European Journal of Operational Research 97, pp.571-79.

10