PENGEMBANGAN ALGORITMA HYBRID CROSS ENTROPYTABU SEARCH UNTUK PENYELESAIAN TRAVELLING REPAIRMAN PROBLEM
Pembimbing : Ir. Budi Santosa, M.S., Ph.D NIP. 196905121994021001
LOGO
Peneliti : Muchammad Aminuddin NRP. 2507100041
LOGO
Contents 1
PENDAHULUAN
2
TINJAUAN PUSTAKA
3
METODOLOGI PENELITIAN
4
EKSPERIMEN DAN ANALISIS
5
KESIMPULAN DAN SARAN
LOGO
PENDAHULUAN 1
LATAR BELAKANG
2
PERUMUSAN MASALAH
3
TUJUAN PENELITIAN
4
BATASAN PENELITIAN
5
MANFAAT PENELITIAN
LOGO
Latar Belakang (1)
TSP
(Travelling Salesman Problem)
NP--Hard Problem NP Pengembangan
TRP
(Travelling Repairman Problem)
LOGO
Latar Belakang (2)
Dynamic Programming
Polynomial Time Algorithms
Branch and Bound
Lagrangian Relaxation Approximation Algorithm
GRASP + VND
Improved Genetic Algorithm
Hybrid Cross Entropy-Tabu Search
LOGO
Latar Belakang (3) Traveling Repairman Problem
Penentuan rute petugas bengkel untuk melayani order dari customer di lokasi yang berbeda
Penentuan rute tim penyelamat bencana untuk mengunjungi beberapa pos penyelamatan korban
Pengembangan model algoritma Hybrid Cross Entropy-Tabu Search untuk menyelesaikan permasalahan Travelling Repairman Problem sehingga bisa digunakan untuk menyelesaikan kasus serupa dengan dimensi yang berbeda-beda
LOGO
Perumusan Masalah
Bagaimana penggabungan algoritma Cross Entropy dan Tabu Search untuk menyelesaikan permasalahan Travelling Repairman Problem agar didapatkan rute yang lebih baik dengan total waktu tunggu customer yang minimum
LOGO
Tujuan Penelitian CE-TS for TRP
Mendapatkan algoritma Hybrid Cross EntropyTabu Search untuk kasus Travelling Repairman Problem
Menghasilkan kode MATLAB untuk implementasi permasalahan Travelling Repairman Problem dalam kasus yang berbeda
Membandingkan performansi algoritma Hybrid Cross EntropyTabu Search untuk penyelesaian Travelling Repairman Problem dengan algoritma lain
LOGO
Ruang Lingkup Penelitian
Penelitian ini menggunakan data sekunder yang didapatkan dari TSPLIB95 Komputasi model dilakukan dengan software Matlab, dengan jenis spesifikasi komputer yang telah ditentukan sebelumnya
Jarak antar node menggunakan euclidean distance (sesuai dengan data penelitian jurnal pembanding) Waktu tunggu customer pada suatu rute yang terbentuk didekati dengan jarak posisi customer dalam rute dihitung dari kota awal repairman
LOGO
Manfaat Penelitian
Adanya pendekatan baru yang merupakan pengembangan dari algoritma Hybrid Cross Entropy-Tabu Search dalam menyelesaikan Travelling Repairman Problem pada berbagai kasus
LOGO
TINJAUAN PUSTAKA 1
TRAVELLING SALESMAN PROBLEM
2
TRAVELLING REPAIRMAN PROBLEM
3
CROSS ENTROPY (CE)
4
CROSS ENTROPY UNTUK TSP
5
TABU SEARCH
6
CRITICAL REVIEW
LOGO
Perbedaan TSP dan TRP
TSP
TRP
Minimasi total jarak tempuh salesman
Minimasi total waktu tunggu customer
Fokus pada minimasi traveling cost
Fokus pada costumer satisfaction
Hal kritis pada TRP ini adalah sedikit perubahan pada struktur rute TRP akan menyebabkan perubahan signifikan pada TRP sehingga sangat rawan terjebak pada local optimal.
LOGO
Formulasi TSP
Formulasi matematis TSP (Langevin, 2005) : (1) Subject to (2)
(3) (4)
Keterangan : xij = 1 jika rute dari kota i ke kota j dilalui 0 jika tidak cij = jarak atau biaya (cost) dari kota i ke kota j S = jumlah kota
Formulasi TRP
LOGO
Keterangan : Xij = 1 jika repairman melalui ruas (i,j) 0 jika tidak Yij = µi jika Xij = 1 0 jika tidak i menunjukkan posisi node dalam tour
Formulasi matematis TRP (Ezzine et al., 2010) : (1) Subject to
(2) (3)
(4) (5) (6) (7) (8) (9) (10) (11)
LOGO
Cross Entropy
Algoritma umum Cross Entropy
Pembangkitan sampel Random dengan mekanisme tertentu
Update Parameter dari sampel elite untuk membangkitkan sampel random yang lebih baik pada Iterasi selanjutnya
LOGO
Algoritma CE for TSP
2
1
Pembangkitan kandidat solusi rute berdasarkan matriks transisi
Generate matriks transisi -Node Transition -Node Placement
3 Pengambilan sampel elite sesuai parameter rho*N
4 Update Parameter 5
LOGO
Tabu Search
Tabu Search dikembangkan oleh Fred Glover 1988 merupakan metaheuristik yang berdasarkan prosedur local search untuk menjelajahi kemungkinan solusi di luar local optimal. Keunggulan : penggunaan adaptive memory, yaitu struktur memori yang fleksibel yang disebut Tabu List. Algoritma Tabu Search BEGIN T = [ ]; s = solusi awal; s* = s REPEAT Temukan yang terbaik yang diterima s` ϵ N(s); IF f(s`) < f(s*) THEN s* = s; s = s`; Update Tabu List; UNTIL kriteria pemberhentian: STOP
LOGO
Critical Review
Polynomial time algorithms (Wu, B. Y, 2000)
• Metoda ini menggunakan pendekatan dynamic programming, hasil lebih baik dari penelitian sebelumnya
Exact Algorithm (Wu, B., Z. Huang, 2004)
• Metoda yang digunakan adalah dynamic programming dan branch and bound, keduanya meningkatkan performansi signifikan
Lagrangian Relaxation (Rocha, A., E. Fernandes, 2005)
• Metoda masih terbatas pada permasalahan dengan ukuran yang kecil
Approximation Algorithm (Archer, A., Levin, A., and D.P. Williamson, 2007)
GRASP+ VND (Salehipour, A., K. Sörensen, 2008)
Improved Genetic Algorithm (Bang, B. H. and N. D. Nghia, 2010)
• Perbaikan dari Approximation Algorithm pada tahun 2003, best result known pada tahun 2007. • Metoda metaheuristik pertama untuk TRP, mampu menyelesaikan TRP dengan waktu komputasi yang wajar • Solusi memiliki rata-rata rasio yang lebih baik dari penelitian sebelumnya, tetapi hasil belum cukup optimal untuk aplikasi praktis
LOGO
Algoritma Cross Entropy (1) START
Pengumpu lan Data
Penentuan Parameter
Generate Matriks Transisi P
A
LOGO
Algoritma Cross Entropy (2) A
Pembangkitan nRute sebagai kandidat solusi Penghitungan fitness untuk masing-masing rute Pemilihan sampel elite sesuai parameter ρ x N
B
C
LOGO
Algoritma Cross Entropy (3) B Update matriks transisi dengan acuan sampel elite Apakah stopping criteria terpenuhi?
Pemunculan solusi optimal CE STOP
C
LOGO
Hybrid Cross Entropy-Tabu Search (1) START Pengumpu lan Data Penentuan Parameter Pembangkitan Kandidat solusi Tabu Search (menggunakan neighborhood selection)
Algoritma Tabu Search
Pemilihan solusi terbaik dari kandidat solusi A
B
LOGO
Hybrid Cross Entropy-Tabu Search (2) A
B
Update Tabu List
Apakah maksimum iterasi Tabu Search tercapai?
Penginputan rute-rute dalam Tabu List sebagai sampel awal CE C
Algoritma Cross Entropy
LOGO
Hybrid Cross Entropy-Tabu Search (3) C Pembangkitan matriks transisi P berdasarkan pembobotan peluang empiris rute dalam Tabu List Pembangkitan Nrute sebagai kandidat solusi awal Penghitungan fitness untuk masing-masing rute Pemilihan sampel elite sesuai parameter ρ x N D
E
LOGO
Hybrid Cross Entropy-Tabu Search (4) D Update matriks transisi dengan acuan sampel elite Apakah stopping criteria terpenuhi? STOP
E
LOGO
Neighborhood Selection
- Rute dibangkitkan secara random misal : 1-3-5-4-2-1 - Copy rute sebanyak n (banyaknya kota) 1-3-5-4-2-1 1-3-5-4-2-1 1-3-5-4-2-1 1-3-5-4-2-1 1-3-5-4-2-1 - Lakukan pertukaran tetangga tiap rute yang telah di-copy 1-3-5-4-2-1
1-5-3-4-2-1
1-3-5-4-2-1
1-3-4-5-2-1
1-3-5-4-2-1
1-3-5-2-4-1
Hitung fitness masing-masing
LOGO
Tabu List
Berisi rute-rute terbaik hasil iterasi Tabu Search. Tabu List adalah short term memory dalam Tabu Serach yang mencegah solusi yang sudah pernah muncul dan tidak terpilih (tabu) muncul kembali. Aturan update Tabu List : - Jika rute yang dibangkitkan melalui neighborhood selection lebih baik daripada rute yang ada dalam Tabu List saat ini, maka rute akan masuk dalam Tabu List dan rute tersebut digunakan untuk neighborhood selection selanjutnya - Jika rute yang dibangkitkan melalui neighborhood selection tidak lebih baik daripada rute yang ada dalam Tabu List, maka tidak ada update Tabu List dan dibangkitkan rute secara random untuk neighborhood selection selanjutnya
Pembangkitan matriks transisi dalam Hybrid CE-TS
LOGO
Rute dalam Tabu List pada contoh numerik
P
P
P
=
No Tabu List 1 2 3
α*
Rute 1-4-5-3-2 1-4-5-2-3 1-3-5-2-4
Wij
=
α*
0 0,33 0,33 0,33 0
=
0 0,3 0,3 0,3 0,1
0,1 0 0,2 0,1 0,5
0 0 0,33 0 0,67
0,33 0,33 0 0 0,33
0,67 0,33 0 0 0
0,3 0,3 0 0,1 0,3
0,5 0,3 0,1 0 0,1
0,1 0,1 0,3 0,5 0
0 0 0,33 0,67 0
+
(1-α) *
+
0 0,25 (1-α) * 0,25 0,25 0,25
Pold 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
Pada CE, matriks transisi awal adalah matriks di atas yang didapatkan dengan memberikan bobot yang sama untuk setia Pij, yaitu 1/(n-1)
LOGO
P
=
0 0,3 0,3 0,3 0,1
Pembangkitan Rute dengan Matriks Transisi menggunakan Roulette Wheel Selection 0,1 0 0,2 0,1 0,5
0,3 0,3 0 0,1 0,3
0,5 0,3 0,1 0 0,1
0,1 0,1 0,3 0,5 0
Roulette Wheel Selection dilakukan hingga terbentuk sebanyak N-rute
Kota pertama langsung dipilih kota 1 sebagai kota awal jadikan 0 untuk kolom 1, dan lakukan normalisasi Kota kedua (lihat baris 1): Rand = 0,43 berada antara kota 3 dan 4 sehingga dipilih kota 4 Lalu, jadikan 0 untuk kolom 4, lalu lakukan normalisasi Kota ketiga (lihat baris empat): Rand = 0,55 berada antara kota 4 dan 5 sehingga dipilih kota 5 Lalu, jadikan 0 untuk kolom 5, lalu lakukan normalisasi
LOGO
Kota ke1 2 3 4 5
Koordinat x y 15 37 22 5 13 22 17 29 11 17
Perbandingan hasil antara Enumerasi, CEdan CE-TS
Validasi Koordinat kota untuk Validasi
Valid Metoda
Rute 1-4-3-5-2-1
Total Wait Time 84.2208
Waktu Komputasi -
Enumerasi Cross Entropy (CE) Hybrid Cross Entropy-Tabu Search (CETS)
1-4-3-5-2-1
84.2208
0.0468
1-4-3-5-2-1
84.2208
0.390003
Eksperimen dengan Set Data Eil51 (51 kota)
LOGO
Algoritma Waktu Tunggu Gap
CE Rata-rata 10.537
AA
Terbaik 10.352 38,92% lebih baik
Rata-rata
Waktu Tunggu Gap
14.638
10.488,6
CE-TS dengan Seleksi
Algoritma
Rata-rata
Terbaik
10.785
10.385
Waktu Tunggu Gap
AA Terbaik
10.406 39,56% lebih baik
14.638
AA 14.638
35,73% lebih baik
CE Algoritma
CE-TS
Algoritma
CE-TS
CE-TS Seleksi
Rata-rata
Terbaik
Rata-rata
Terbaik
Rata-rata
Terbaik
Waktu Tunggu
10.537
10.352
10.488,6
10.406
10756
10385
Waktu Komputasi
3.655
3.313
4.362
4.126
4595,7
4429,3
Iterasi Optimal
37
34
37
35
41,6
40
Keterangan : CE Cross Entropy CE-TS Hybrid Cross Entropy-Tabu Search AA Approximation Algorithm
LOGO
Algoritma Waktu Tunggu Gap
Eksperimen dengan Set Data KroA100 (100 kota) CE Rata-rata 1.168.967
AA
Terbaik 1.123.700 11,84% lebih baik
CE-TS
Algoritma Waktu Tunggu Gap
Algoritma Waktu Tunggu Waktu Komputasi Iterasi Optimal
1.307.340
Rata-rata 1.183.367
Terbaik 1.173.100 10,48% lebih baik
CE Rata-rata 1.168.967 41.008 93
AA 1.307.340
CE-TS Terbaik 1.123.700 39.581 90
Keterangan : CE Cross Entropy CE-TS Hybrid Cross Entropy-Tabu Search AA Approximation Algorithm
Rata-rata 1.183.367 41.720 91
Terbaik 1.173.100 41.208 89
LOGO
Algoritma Waktu Tunggu Gap
Eksperimen dengan Set Data KroA150 (150 kota) CE Rata-rata 2.391.900
AA Terbaik 2.391.900 4,3% lebih baik
Algoritma Waktu Tunggu Gap
Algoritma Waktu Tunggu Waktu Komputasi Iterasi Optimal
2.494.782
CE-TS Rata-rata 2.567.267
Terbaik 2.481.700 2,9% lebih buruk
CE Rata-rata 2.391.900 250.733,33 220
AA 2.494.782
CE-TS Terbaik 2.391.900 249.360 220
Keterangan : CE Cross Entropy CE-TS Hybrid Cross Entropy-Tabu Search AA Approximation Algorithm
Rata-rata 2.567.267 229.020 194
Terbaik 2.481.700 216.390 183
LOGO
Analisis
•Algoritma CE-TS memberikan hasil yang lebih bagus daripada CE untuk problem kecil, namun untuk problem yang lebih besar CE memberikan hasil yang lebih bagus daripada CE-TS. • Pada problem yang besar, hasil Tabu Search pada algoritma CE-TS belum tentu bagus karena kemungkinan solusi yang sangat banyak, namun untuk problem kecil hasil Tabu Search relatif bagus sehingga cukup membantu algoritma CE dengan mengatur pembangkitan awal CE dengan sampel yang bagus sehingga mempengaruhi hasil akhir CE-TS. •Bila dibandingkan dengan algoritma pembanding, CE dan CE-TS memberikan performansi yang lebih bagus daripada algoritma Approximation Algorithm (Archer et al., 2008), namun tidak lebih baik bila dibandingkan dengan Improved GA (Bang and Nghia, 2010).
LOGO
Kesimpulan
1. Algoritma Cross Entropy (CE) dan Hybrid Cross EntropyTabu Search (CE-TS) dapat diaplikasikan untuk penyelesaian Travelling Repairman Problem (TRP) 2. Algoritma Hybrid Cross Entropy-Tabu Search menghasilkan total waktu tunggu customer yang lebih baik daripada Cross Entropy pada problem berukuran kecil, namun pada problem berukuran besar algoritma Cross Entropy mampu menghasilkan total waktu tunggu customer lebih baik. 3. Algoritma Cross Entropy dan Hybrid Cross Entropy-Tabu Search menghasilkan performansi yang lebih baik daripada algoritma Approximation Algorithm, namun masih kurang baik jika dibandingkan dengan algoritma Improved Generic Algorithm.
LOGO
Saran
Penelitian selanjutnya bisa dikembangkan untuk varian Travelling Repairman Problem lain, seperti seperti TRP with repairtimes, TRP with profits, TRP with deadline, dan sebagainya.
LOGO
Daftar Pustaka (1)
Archer, A., Levin, A. & Williamson, D. P. 2008. A faster, better approximation algorithm for the minimum latency problem. SIAM Journal on Computing, 37, 1472-1498. Archer, A. & Williamson, D. P. 2003. Faster approximation algorithms for the minimum latency problem. Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. Baltimore, Maryland: Society for Industrial and Applied Mathematics. Bang, B. H. & Nghia, N. D. 2010. Improved genetic algorithm for minimum latency problem. Proceedings of the 2010 Symposium on Information and Communication Technology. Hanoi, Viet nam: ACM. Dewilde, T., Cattrysse, D., Coene, S. & CR, F. Year. Heuristics for the Traveling Repairman Problem with Profits. In., 34. Ezzine, I., Semet, F. & Chabchoub, H. Year. NEW FORMULATIONS FOR THE TRAVELING REPAIRMAN PROBLEM. In, 2010. Citeseer. Glover, F. & Laguna, M. 1998. Tabu search, Kluwer Academic Pub. Langevin, A., Riopel, Diane 2005. Logistics Systems : Design and Optimization. Springer-Verlag Berlin Heidelberg. Lechmann, M. 2009. The traveling repairman problem. Pirim, H., Bayraktar, E. & Eksioglu, B. 2008. Tabu Search: A Comparative Study. IN-TECH. Rocha, A., Fernandes, E. & Soares, J. Year. Solving the Traveling Repairman problem with differentiated waiting times through Lagrangian relaxation. In.: Citeseer, 972-99841. Rocha, M. & Neves, J. 2004. Preventing premature convergence to local optima in genetic algorithms via random offspring generation. Multiple Approaches to Intelligent Systems, 127-136. Rubinstein, R., & Kroese., D. 2004. The cross-entropy method: A unified approach to combinatorial optimization, Monte-Carlo simulation, and machine-learning. Springer-Verlag Berlin Heidelberg.
LOGO
Daftar Pustaka (2)
Salehipour, A., Sorensen, K., Goos, P. & Braysy, O. 2008. An efficient GRASP+ VND metaheuristic for the traveling repairman problem. Working Papers. Santosa, B. & Willy, P. 2011. Metoda Metaheuristik : Konsep dan Implementasi, Surabaya, Guna Widya. Shi, X. H., Liang, Y. C., Lee, H. P., Lu, C. & Wang, Q. X. 2007. Particle swarm optimization-based algorithms for TSP and generalized TSP. Information Processing Letters, 103, 169-176. Wu, B., Huang, Z. & Zhan, F. 2004. Exact algorithms for the minimum latency problem. Information Processing Letters, 92, 303-309. Wu, B. Y. 2000. Polynomial time algorithms for some minimum latency problems. Information Processing Letters, 75, 225-229.
LOGO
