Artificial Immune System untuk Penyelesaian Vehicle Routing Problem with Time Windows
Dosen Pembimbing : Ir. Budi Santosa, M.S., Ph.D Oleh : Sas Wahid Hamzah
2507100054
Pendahuluan
Pendahuluan Fungsi Objektif • Minimasi Jumlah Kendaraan • Minimasi Jarak Konstrain • Semua rute berawal dan berakhir pada depot pusat. • Setiap titik customer hanya dikunjungi sekali • Demand yang akan dipenuhi oleh kendaraan tidak boleh melebihi kapasitas. • Waktu perjalanan tidak melebihi yang ditentukan. • Konstrain time windows. • Semua customer dilayani
Pendahuluan Batasan • Data Sets Solomon • Komputasi dengan MATLAB Asumsi • Kendaraan semuanya memiliki kapasitas yang sama • Hanya terdapat satu depot
• Hard time windows • Jarak Euclidean dan simetris • Satu unit jarak sama dengan satu unit waktu
Pendahuluan Artificial Immune System “Sistem komputasi yang terinspirasi dari imunologi teoretik yang mengamati fungsi, prinsip, dan mekanisme kekebalan tubuh vertebrata yang diaplikasikan untuk menyelesaikan suatu problem”.
Pendahuluan Alasan Pemilihan AIS • Relatif baru (untuk kasus optimasi mulai populer pada 2002)
• Telah sukses diaplikasikan pada beberapa problem seperti : flow shop scheduling problem, job shop scheduling
problem,
travelling
salesman
problem,
resource constraint project scheduling problem, dan
economic dispatch
Pendahuluan • Sistem Imunitas Vertebrata
Pendahuluan • Alur Kerja Sistem
Contoh Data Sets
Tinjauan Pustaka Metode Penyelesaian VRPTW ALGORITMA EKSAK
METAHEURISTIK
• Branch & Bound
• Tabu Search
• Branch & Price
• Genetic Algorithm
• Branch & Cut
• Simulated Annealing
• Column Generation
• Ant Colony System
• Lagrangian Relaxation
Tinjauan Pustaka Posisi Penelitian
AIS untuk TSP
AIS untuk VRP
(de Castro dan Von Zuben, 2002)
(Xu Jiangang, 2009)
AIS untuk VRPTW
Algoritma Usulan Route Construction
Solomon Insertion Heuristics I1 (Solomon, 1987)
Route Minimization
Prosedur Ejection Pool (Lim and Zhang, 2007)
Distance Improvement
Artificial Immune System
Metode Encoding • Yaitu integer encoding, suatu angka merepresentasikan nomer customer, dengan angka 1 adalah depot. Contoh :
S
= <|1 – 3 – 7 – 5 – 1| 1 – 4 – 2 – 1| 1 – 6 – 1|>
Solomon Insertion Diusulkan oleh Marius M. Solomon (1987) 1. Diawali dengan membuat seed route, Contoh Seed route = [ 1 – 6 – 1 ] Seed Customer
• Seed customer dapat dipilih, baik customer yang : Memiliki jarak terjauh dari depot, atau Customer dengan earliest due date *1 = depot
Solomon Insertion 2. Identifikasilah letak insersi untuk seluruh customer yang belum masuk ke rute, dengan syarat bahwa letak insersi tersebut adalah feasible Taruhlah sebagai rute sekarang, dengan : υ0 = depot, υm+1 = depot
Solomon Insertion 3. Hitung posisi insersi terbaik, yakni
dengan syarat bahwa insersi u diantara 2 node yakni υq dan υq+1 adalah feasible, u adalah unrouted customer.
Solomon Insertion • Kriteria c1 dihitung dengan cara
= waktu mulai pelayanan di node j setelah dilakukan insersi = waktu mulai pelayanan di node j sebelum dilakukan insersi = jarak node i ke unrouted customer = jarak unrouted customer ke node j = jarak node i ke node j
Solomon Insertion 4. Apabila nilai c1* sudah dihitung untuk setiap customer, maka hitung nilai c2 untuk setiap customer yang memiliki nilai c1* . (Customer yang tidak bisa di-insersi di ruang manapun, maka tidak memiliki nilai c1 dan demikian tidak memiliki nilai c1* dan c2 ) dengan
Solomon Insertion 5. Pilihlah customer yang memiliki nilai c2 paling maksimum untuk di-insert-kan. Insert customer tersebut ke dalam rute yang sedang dibentuk, sesuai dengan posisi terbaiknya yang ditunjukkan c1
Solomon Insertion 6. Apabila rute yang sedang dibangun sudah tak lagi bisa dilakukan insersi, maka buatlah rute baru (seed route), dan ulangi algoritma 7. Apabila semua customer telah berada dalam rute (tidak ada yang tidak terlayani), maka hentikan proses, dan lanjutkan ke phase selanjutnya.
Prosedur Ejection Pool Diusulkan oleh Lim dan Zhang (2007) • Hapuslah beberapa rute dengan jumlah customer sedikit • Masukkan customer – customer tersebut ke dalam ejection pool (EP) • Selama EP masih berisi customer dan iterasi kurang dari iterasi maksimum, lakukan langkah berikut : • Pilih salah satu customer u dari EP • Tentukan posisi insersi u pada rute eksisting • Hapus u dari EP dan masukkan u pada rute target • Apabila rute target tidak feasible, maka • Ambil salah satu customer dari rute tersebut dan masukkan ke dalam EP • Lakukan exchange, relocate, 2-Opt, Or-Opt, Cross Exchange. • Akhir iterasi
Algoritma Usulan START
Solusi inisial, data koordinat kota, demand, waktu pelayanan, due date, waktu paling awal pelayanan, kapasitas kendaraan, jumlah kendaraan maksimal
Urutkan solusi – solusi berdasarkan nilai objektif yakni total jarak
Berikan rangking, yakni rangking pertama merupakan solusi dengan total jarak terpendek, dan seterusnya
Ambil beberapa solusi terbaik berdasrkan peringkat
Lakukan cloning berdasarkan peringkat solusi yang bersangkutan
A
B
Perbandingan Hasil yang dari algoritma yang diusulkan dibandingkan dengan hasil yang diperoleh pada paper : Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles dalam European Journal of Operational Research oleh Lau et al. (2003)
Perbandingan No
Hal
1 Jumlah Fase Metode 2 Pembentukan Rute Metode 3 Improvement 4 Local Search Subyek Local 5 Search
Tabu Search dengan Nested 2 Phase 2 fase terkurung Tabu Search Tabu Search Relocate dan Exchange
Artificial Immune System 2 fase terpisah Solomon Insertion & Prosedur Ejection Pool Artificial Immune System Relocate, Exchange, 2-Opt, Or-Opt, 2-Swap, Re-insertion
Rute yang sedang Sebuah rute, atau 2 dibangun dan rute yang berbeda Holding List
Hasil • Untuk 25 Customer dengan Gap Terkecil Solusi Optimal (Eksak) Type
Problem
C1
C101 C102 C103 C104 C105 C106 C107 C108 C109
Kendaraan 3 3 3 3 3 3 3 3 3
Jarak 191.3 190.3 190.3 186.9 191.3 191.3 191.3 191.3 191.3
Immune System Kendaraan 3 3 3 3 3 3 3 3 3
Jarak 191.8 190.7 190.7 187.4 191.8 191.8 191.8 191.8 191.8
Gap (%) 0.27 0.23 0.23 0.29 0.27 0.27 0.27 0.27 0.27
Hasil • Untuk 25 Customer dengan Gap Terbesar Solusi Optimal (Eksak) Type
Problem
R2
R201 R202 R203 R204 R205 R206 R207 R208 R209 R210 R211
Kendaraan 4 4 3 2 3 3 3 1 2 3 2
Jarak 463.3 410.5 391.4 355.0 393.0 374.4 361.6 328.2 370.7 404.6 350.9
Immune System Kendaraan 3 4 2 2 3 2 2 1 2 2 2
Jarak 479.9 412.2 411.0 386.1 408.8 387.5 378.7 331.8 376.8 425.6 365.0
Gap (%) 3.59 0.41 5.00 8.76 4.02 3.49 4.74 1.10 1.64 5.18 4.01
Hasil • Untuk 100 Customer dengan Gap Terkecil Solusi Acuan Type Problem
C2
C201 C202 C203 C204 C205 C206 C207 C208
Kendaraan 3 3 3 3 3 3 3 3
Jarak 591.56 619.36 604.01 644.23 601.43 588.88 608.94 591.83
Immune System Kendaraan 3 3 3 3 3 3 3 3
Jarak 591.56 630.08 608.35 591.56 588.88 612.54 608.16 613.75
Gap (%) 0.00 1.73 0.72 -8.18 -2.09 4.02 -0.13 3.70
Hasil • Untuk 100 Customer dengan Gap Terbesar Solusi Acuan Type Problem
RC2
RC201 RC202 RC203 RC204 RC205 RC206 RC207 RC208
Kendaraan 4 4 3 3 4 3 3 3
Jarak 1468.46 1222.69 1171.88 839.32 1338.70 1201.27 1139.48 985.60
Immune System Kendaraan 4 4 3 3 4 3 3 3
Jarak 1648.7 1649.0 1280.7 1031.6 1642.8 1436.1 1453.6 1113.8
Gap (%) 12.27 34.87 9.29 22.91 22.72 19.55 27.57 13.01
Analisis Faktor Penyebab Buruknya Performansi 1. Pengurangan Kendaraan seringkali menyebabkan jarak menjadi lebih buruk 2. Solusi yang masuk ke AIS seringkali hanya berjumlah satu 3. Jumlah kendaraan yang tidak boleh bertambah membatasi gerak solusi
Kesimpulan 1
AIS kompetitif untuk problem dengan skala kecil (customer sebanyak 25)
2
AIS efektif menyelesaikan problem untuk tipe customer yang terletak secara tercluster.
3
Performa AIS banyak dipengaruhi oleh inisialisasi dan mutasi (local Search)
Saran 1
2
3
Modifikasi algoritma untuk bisa menghasilkan solusi dengan diversitas yang bagus (lolos dari local optima)
Modifikasi algoritma dengan melibatkan bagian lain dari sistem imunitas, seperti network theory, negative selection
Menggunakan data set yang lebih besar
SEKIAN
TERIMA
KASIH
