ARTIFICIAL IMMUNE SYSTEM UNTUK PENYELESAIAN VEHICLE ROUTING PROBLEM WITH TIME WINDOWS Sas Wahid Hamzah dan Budi Santosa Jurusan Teknik Industri Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus ITS Sukolilo Surabaya 60111 Email:
[email protected] ;
[email protected] Abstrak Permasalahan vehicle routing problem with time windows adalah suatu masalah penting dalam bidang logistik. Permasalahan yang dihadapi adalah bagaimana melayani sejumlah customer dengan biaya seminimum mungkin tanpa melanggar konstrain rentang waktu yang ditetapkan customer dan konstrain kapasitas kendaraan. Persoalan VRPTW dapat dijumpai pada pengiriman bank, pos, routing bus sekolah, dan lain – lain. VRPTW dapat dipandang sebagai persoalan optimasi dengan dua kriteria. Tujuan pertama adalah meminimasi jumlah rute, dan tujuan kedua adalah meminimasi jarak yang ditempuh. Dalam penelitian ini diusulkan suatu algoritma artificial immune system berbasis clonal selection untuk menyelesaikan persoalan tersebut. Algoritma yang diusulkan diimplementasikan pada 56 problem solomon dengan ukuran 25 dan 100 customer. Hasil yang diperoleh menunjukkan bahwa algoritma yang diusulkan sangat kompetitif untuk problem dengan ukuran 25 customer. Lebih jauh, algoritma memiliki performansi yang baik untuk kumpulan customer yang terletak secara terklaster dibanding customer yang terletak secara random. Kata kunci : artificial immune system, clonal selection, vehicle routing problem with time windows ABSTRACT The Vehicle Routing Problem with Time Windows (VRPTW) is an important problem in logistics. The problem is to serve a number of customers at minimum cost without violating the customers’ time window constraints and the vehicle capacity constraint. The VRPTW has a wide range of applications such as bank deliveries, postal deliveries, school bus routing and so on. The VRPTW can be viewed a bi-criterion optimization problem. The primary objective is minimization of the number of routes, total travelled distance is considered as secondary aim. An artificial immune system based on clonal selection algorithm is proposed to solve the problem. The artificial immune system was implemented on 56 Solomon problems with sizes 25 and 100 customers. The derived results show that the proposed algorithm is very competitive for problem with 25 customer. Moreover, the algorithm works well for problem with clustered customers position, than the random one. Key words : artificial immune system, clonal selection, vehicle routing problem with time windows 1. Pendahuluan Vehicle routing problem (VRP) merupakan suatu nama umum yang diberikan pada suatu kelompok masalah untuk menentukan suatu himpunan rute – rute kendaraan, dimana setiap kendaraan berangkat dari depot yang sama, melayani suatu himpunan customer, dan kembali ke depot yang sama. Berbagai macam tipe layanan muncul pada situasi praktisnya, dimana pengiriman barang merupakan yang paling umum. Selain pengiriman barang terdapat juga
layanan pengambilan barang yang dapat dilakukan secara simultan dengan pengiriman barang. Sedangkan dari sisi jumlah depot, kasus VRP bisa saja melibatkan sebuah depot ataupun multidepot. Salah satu varian dari VRP adalah vehicle routing problem with time windows dimana dalam varian ini, customer dengan demand tertentu dilayani dengan sejumlah kendaraan dengan kapasitas tertentu dimana setiap kendaraan memiliki kapasitas yang sama. Rute diasumsikan bermula dan berakhir di depot.
Setiap customer menyediakan interval waktu untuk dilakukannya pekerjaan seperti bongkar muat dari dan ke kendaraan. Tujuan yang ingin dicapai adalah untuk meminimasi jumlah rute, dan kemudian dalam jumlah rute yang sama, diminimumkan jarak total yang harus ditempuh, disamping juga customer harus dilayani dalam rentang waktu yang sudah ditentukan, dan total muatan yang dibawa oleh suatu kendaraan tidak boleh melebihi kapasitasnya (Cordeau et al, 2002). VRPTW muncul dalam berbagai praktek pengambilan keputusan seperti routing bus sekolah, pengiriman surat dan koran, pengiriman bahan bakar, dan pengumpulan sampah. Permasalahan VRPTW merupakan permasalahan yang tergolong permasalahan NP-Hard (Savelsbergh, 1985), oleh karenanya, metodologi pendekatan eksak dalam menyelesaikan problem tersebut secara umum tidaklah efisien (Desrochers, Desrochers, & Solomon, 1992). Untuk mengatasi problem dengan skala menengah dan besar, untuk memenuhi kondisi riil system distribusi, maka dalam pemikirannya harus dikonsentrasikan pada pendekatan solusi heuristik dan metaheuristik yang mampu menghasilkan kualitas solusi yang tinggi dengan waktu komputasi yang relatif pendek. Beberapa penelitian untuk mendapatkan penyelesaian permasalahan VRPTW secara heuristik ataupun metaheuristik tersebut telah dilakukan, antara lain: pendekatan dengan algoritma decomposition technique and genetic algorithm (Cheng dan Wang, 2009), parallel hybrid genetic algorithm (Berker dan Barkaoui, 2004), two-phase hybrid metaheuristics (Homberger dan Gehring, 2005). Beberapa metode tersebut mampu mendapatkan hasil rute yang cukup kompetitif, dan bahkan pada beberapa kasus dapat diselesaikan dengan solusi optimal. Artificial immune system telah digunakan dalam menyelesaikan berbagai bidang seperti optimasi, klasifikasi, clustering, deteksi anomali, machine learning, adaptive control, dan associative memories (Dasgupta and Nino, 2009). Khususnya untuk penerapannya dalam bidang optimasi, artificial immune system lebih dipopulerkan oleh de Castro dan Von Zuben (2002) yakni CLONALG. Metode artificial immune system sebagai salah satu metode metaheuristik telah digunakan dalam beberapa permasalahan kombinatorial seperti
penjadwalan job shop maupun flow shop, travelling salesman problem, resource constraint scheduling problem, dan economic dispatch. Dalam penelitian ini akan dilakukan suatu pengembangan algoritma dengan pendekatan artificial immune system berbasis clonal selection (CLONALG) untuk menyelesaikan permasalahan VRPTW. Penggunaan pendekatan artificial immune system untuk mengembangkan algoritma dalam menyelesaikan permasalahan VRPTW diharapkan menjadi alternatif untuk menghasilkan rute dengan jarak yang optimal. 2. Metodologi Algoritma yang dikembangkan untuk penyelesaian vehicle routing problem with time windows ini dapat dibagi menjadi 2 fase, yaitu fase route construction – route minimization dan fase distance improvement. Pada fase pertama digunakan digunakan algoritma Solomon insertion heuristic I1 yang dirangkai dengan prosedur ejection pool seperti yang diusulkan oleh Lim dan Zhang (2007). Sedangkan pada fase kedua digunakan artificial immune system untuk mengurangi total jarak dari solusi yang dihasilkan pada fase inisialisasi. 2.1 Tahap Route Construction – Route Minimization Tahap route construction dalam hal ini dapat dibagi lagi menjadi dua sub tahapan, yaitu sub tahapan route construction yang menggunakan metode inisialisasi insersi Solomon I1 (Solomon, 1987) dan sub tahapan kedua adalah pengurangan jumlah rute yang menggunakan metode ejection pool (Lim and Zhang, 2007). Route Construction Algoritma untuk pembentukan rute – rute mengacu pada algoritma insersi I1 yang diusulkan oleh Solomon (1987) yang dapat diilustrasikan sebagai berikut : Notasi : 𝑡𝑗′ = waktu mulai pelayanan di node j setelah dilakukan insersi 𝑡𝑗 = waktu mulai pelayanan di node j sebelum dilakukan insersi 𝑑𝑖𝑢 = jarak antara node i dan u (unrouted customer) 𝑑𝑢𝑗 = jarak dari u (unrouted customer) ke node j 𝑑𝑖𝑗 = jarak dari node i ke node j
Langkah – langkahnya adalah sebagai berikut : 1. Buatlah seed route yang berisi satu customer Contoh : {1 6 1} dalam hal ini customer no 6 adalah seed customer, dengan 1 sebagai depot. Seed customer dapat dipilih, baik customer yang : Memiliki jarak terjauh dari depot, atau Customer dengan earliest due date, atau Selang – seling jarak terjauh maupun earliest due date 2. Identifikasilah letak insersi untuk seluruh customer yang belum masuk ke rute, dengan syarat bahwa letak insersi tersebut adalah feasible taruhlah : {𝜐0 = 0, 𝜐1 , 𝜐2 , … , 𝜐𝑚 , 𝜐𝑚 +1 = 0} sebagai rute sekarang, dengan υ0 = depot υm+1 = depot 3. Hitung posisi insersi terbaik, yakni 𝑐1 𝑢 = min 𝑐1 (𝜐𝑞 , 𝑢, 𝜐𝑞+1 ) 𝑞=0,…,𝑚
dengan syarat bahwa insersi u diantara 2 node yakni υq dan υq+1 adalah feasible, u adalah unrouted customer. Kriteria c1 dihitung dengan cara : 𝑐1 𝑖, 𝑢, 𝑗 = 𝛼1 . 𝛿𝑑 + 𝛼2 . ( 𝑡𝑗′ − 𝑡𝑗 ) dimana 𝛿𝑑 = 𝑑𝑖𝑢 + 𝑑𝑢𝑗 − 𝜇. 𝑑𝑖𝑗 dengan 𝛼1 + 𝛼2 = 1 𝛼1 , 𝛼2 , 𝜇 ≥ 0 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 ) Kriteria c2 dihitung dengan cara : 𝑐2 𝑢 = 𝜆. 𝑑0𝑢 − 𝑐1 𝑢 dengan λ ≥ 0 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 𝑐2 𝑖 𝑢∗ , 𝑢 ∗ , 𝑗 𝑢∗ = 𝑜𝑝𝑡𝑖𝑚𝑢𝑚 𝑐2 𝑖 𝑢 , 𝑢, 𝑗 𝑢 , Dengan catatan bahwa u belum masuk ke rute dan insersi bersifat feasible
6. Apabila rute yang sedang dibangun sudah tak lagi bisa dilakukan insersi, maka buatlah rute baru (seed route), dan ulangi algoritma (kembali ke langkah 1) 7. Apabila semua customer telah berada dalam rute (tidak ada yang tidak terlayani), maka hentikan proses, dan lanjutkan ke sub tahapan route minimization. Route Minimization Setelah didapatkan rute dari proses pembenukan rute pada sub tahapan satu, maka langkah berikutnya dalam hal ini adalah mengurangi jumlah rute apabila rute yang dihasilkan dalam sub tahapan pertama melebihi batas jumlah kendaraan yang tersedia. Algoritma yang digunakan dalam sub tahapan ini adalah seperti yang diusulkan oleh Lim dan Zhang (2007) yang menggunakan prosedur ejection pool untuk menampung kumpulan customer yang berasal dari rute yang dianggap berlebih. Rute yang berlebih dan harus dieliminir adalah rute ke-m+1 dan seterusnya, dimana m adalah jumlah kendaraan yang dikehendaki, dimana rute – rute tersebut memiliki jumlah customer yang paling sedikit dari keseluruhan rute yang ada. Customer – customer yang berada dalam rute – rute tersebut ditampung dalam ejection pool yang selanjutnya akan mengalami insersi maupun penukaran dengan rute yang ada, disamping itu rute – rute yang eksis juga mengalami local search yang mana dengan local search ini diharapkan mampu membentuk ruang insersi untuk customer yang berada di ejection pool. Langkah – langkah algoritma prosedur pengurangan rute dengan ejection pool dapat disajikan sebagai berikut : 1. Hapuslah beberapa rute sisa yang memiliki jumlah customer paling sedikit 2. Masukkan customer – customer tersebut ke dalam ejection pool (EP) 3. Selama EP masih berisi customer dan iterasi kurang dari iterasi maksimum, lakukan langkah berikut 4. Pilih salah satu customer u dari EP 5. Tentukan posisi insersi u pada rute yang eksis 6. Hapus u dari EP dan masukkan u pada rute target 7. Apabila rute target tidak feasible, maka
8. Ambil salah satu customer dari rute tersebut dan masukkan ke dalam EP 9. Lakukan exchange, relocate, 2-Opt, OrOpt. 10. Akhir iterasi 11. Apabila prosedur ejection pool gagal mengurangi jumlah rute, maka solusi akan kembali pada solusi yang dihasilkan pada Solomon insertion. Namun dalam hal ini tidak digunakan prosedur seketat algoritma tersebut. Misalnya saja untuk penentuan posisi insersi tidak dilakukan, melainkan dengan strategi first accept, artinya apabila customer u bisa diinsersi tanpa melanggar konstrain, maka insersi dilakukan saat itu juga. Disamping itu juga tidak digunakan parameter minimum delay (mdl). Local Search Local search memiliki peranan penting pada performansi suatu algoritma dalam menghasilkan solusi yang berkualitas. Dalam hal ini digunakan beberapa local search yang dapat dikelompokkan menjadi 2 yaitu single-route dan multi-route, bergantung bagaimana local search tersebut dioperasikan, apakah pada satu rute ataukah dua rute. Taruhlah terdapat dua rute, yaitu : 𝑟 = 𝑣0 , … , 𝑣𝑖−1 , 𝑣𝑖 , 𝑣𝑖+1 , … , 𝑣𝑗 −1 , 𝑣𝑗 , 𝑣𝑗 +1 , … , 𝑣𝑚
dan
′ ′ ′ ′ 𝑟 ′ = 𝑣0′ , … , 𝑣𝑝−1 , 𝑣𝑝′ , 𝑣𝑝+1 , … , 𝑣𝑞−1 , 𝑣𝑞′ , 𝑣𝑞+1 , … , 𝑣𝑛′
dimana kedua rute tersebut adalah dua rute yang berbeda, dan untuk lebih memudahkan, perubahan yang terjadi pada rute diberikan huruf tebal. Operasi – operasi yang akan dilakukan pada salah satu atau kedua rute tersebut adalah sebagai berikut : a) Single-route Yaitu operasi local search dilakukan hanya terhadap suatu rute dan tidak berdampak pada rute lain. 1) Relocate Yaitu memindahkan suatu customer vi sebelum customer vj dalam suatu rute 𝑟 = 𝑣0 , … , 𝑣𝑖−1 , 𝑣𝑖+1 , … , 𝑣𝑗−1 , 𝒗𝒊 , 𝑣𝑗 , 𝑣𝑗 +1 , … , 𝑣𝑚
2) Exchange Yaitu menukar posisi dua customer yaitu vi dan vj dalam suatu rute 𝑟 = 𝑣0 , … , 𝑣𝑖−1 , 𝒗𝒋 , 𝑣𝑖+1 , … , 𝑣𝑗−1 , 𝒗𝒊 , 𝑣𝑗 +1 , … , 𝑣𝑚
3) 2-Opt Yaitu membalik urutan customer sebanyak w (dengan w ≤ 4) 𝑟 = 𝑣0 , … , 𝑣𝑖−1 , 𝒗𝒊+𝒘−𝟏 , … , 𝒗𝒊 , 𝑣𝑖+𝑤 , … , 𝑣𝑚
4) Or-Opt Yaitu memindah sejumlah customer 𝑣𝑖 , … , 𝑣𝑖+𝑤 −1 sebanyak w ke posisi yang lain (dengan w ≤ 3) 𝑟 = 𝑣0 , … , 𝑣𝑖−1 , 𝑣𝑖+𝑤 , … , 𝑣𝑗 −1 , 𝒗𝒊 , … , 𝒗𝒊+𝒘−𝟏 , 𝑣𝑗 , 𝑣𝑚
b) Multi-route Yaitu local search dilakukan terhadap sepasang rute (dua rute) 1) Relocate Yaitu memindahkan suatu customer vi dari r sebelum customer v’p pada rute r’ 𝑟 = 𝑣0 , … , 𝑣𝑖−1 , 𝑣𝑖+1 , … , 𝑣𝑚 ′ 𝑟 ′ = 𝑣0′ , … , 𝑣𝑝−1 , 𝒗𝒊 , 𝑣𝑝′ , … , 𝑣𝑛′ 2) Exchange Yaitu menukar customer vi pada r dengan v’p pada rute r’ 𝑟 = 𝑣0 , … , 𝑣𝑖−1 , 𝒗′𝒑 , 𝑣𝑖+1 , … , 𝑣𝑚 ′ ′ 𝑟 ′ = 𝑣0′ , … , 𝑣𝑝−1 , 𝒗𝒊 , 𝑣𝑝+1 , … , 𝑣𝑛′ 3) 2-Opt* Yaitu menukar bagian ekor/belakang dari masing masing rute 𝑟 = 𝑣0 , … , 𝑣𝑖−1 , 𝒗′𝒑 , … , 𝒗′𝒏 ′ , 𝒗𝒊 , … , 𝒗𝒎 𝑟 ′ = 𝑣0′ , … , 𝑣𝑝−1 Dalam penggunaannya, local search yang dilakukan tidak boleh menghasilkan solusi yang bersifat infeasible, artinya solusi yang dihasilkan tidak melanggar konstain apapun, baik kapasitas kendaraan, time windows, maupun jumlah kendaraan yang dihasilkan. Satu rute hanya boleh dilayani oleh sebuah kendaraan, dan dengan demikian operasi local search yang melibatkan dua rute hanya boleh menghasilkan jumlah kendaraan maksimum dua. 2.2 Tahap Improvement Total Jarak Artificial immune system menyelesaikan suatu persoalan hampir menyerupai algoritma genetika, hanya saja terdapat perbedaan mendasar. Dalam artificial immune system setelah sejumlah solusi inisial sebanyak N diperoleh, maka sejumlah solusi tersebut diurutkan berdasarkan nilai fungsi objektifnya atau fitness-nya. Kemudian diambil populasi terbaik sebanyak α . N, dimana α menyatakan prosentase solusi terbaik yang telah ditetapkan sebelumnya. Kemudian solusi – solusi sejumlah α.N tersebut mengalami cloning yang sebanding dengan nilai fitness-nya, semakin bagus nilai fitness suatu fungsi, maka akan semakin banyak solusi hasil cloning-nya. Kemudian setiap solusi hasil cloning akan mengalami mutasi sesuai dengan nilai fitness-
Urutkan solusi – solusi berdasarkan nilai objektif yakni total jarak
nya. Fitness yang lebih baik akan memberi mutasi yang lebih sedikit kepada solusi yang bersangkutan. Dari hasil mutan tersebut kemudian dilakukan seleksi berdasarkan sistem turnamen, yang dalam hal ini beberapa individu dari hasil clone diambil dan dicari yang terbaik hingga sejumlah populasi. Antibodi – antibodi hasil seleksi turnamen tersebut akhirnya kemudian memasuki iterasi berikutnya. Dalam hal ini perlu diperhatikan juga bahwa mutasi yang dilakukan bukanlah memutasi solusi keseluruhan melainkan mutasi dilakukan terhadap rute – rute dengan menggunakan local search yang telah disebutkan diatas. Dengan melakukan mutasi terhadap rute –rute tersebut tentunya diharapkan solusi juga mengalami perubahan. Berikut ini disajikan alur dari algoritma artificial immune system untuk mengurangi jarak dari solusi – solusi yang telah dihasilkan pada fase sebelumnya.
Berikan rangking, yakni rangking pertama merupakan solusi A dengan total jarak terpendek, dan seterusnya
Ambil beberapa solusi terbaik berdasrkan peringkat
Lakukan cloning berdasarkan peringkat solusi yang bersangkutan dengan cara
Dimana :
Lakukan mutasi untuk setiap solusi hasil clone
Tournament Selection dilakukan sebanyak jumlah individu
Populasi baru telah terkumpul START
Stopping criteria terpenuhi?
Solusi inisial, data koordinat kota, demand, waktu pelayanan, due date, waktu paling awal pelayanan, kapasitas kendaraan, jumlah kendaraan maksimal
Tidak
Ya Ambil solusi terbaik sebagi hasil akhir
FINISH
Urutkan solusi – solusi berdasarkan nilai objektif yakni total jarak
Gambar 1 Alur Algoritma AIS untuk VRPTW (lanjutan)
Berikan rangking, yakni rangking pertama merupakan solusi dengan total jarak terpendek, dan seterusnya
Ambil beberapa solusi terbaik berdasrkan peringkat
A
Gambar Alur Algoritma AIS untuk VRPTW Lakukan cloning1berdasarkan peringkat solusi yang bersangkutan dengan cara Dimana :
Lakukan mutasi untuk setiap solusi hasil clone
Tournament Selection dilakukan sebanyak jumlah individu
Populasi baru telah terkumpul
Stopping criteria terpenuhi?
B
3. Hasil Komputasi Algoritma yang diusulkan diujicobakan pada problem Solomon yabg berisi 25 dan 100 customer. Untuk problem dengan 25 customer algoritma yang diusulkan diperbandingkan dengan algoritma eksak, dimana referensi terkait hasil algoritma eksak ini dapat dilihat di http://w.cba.neu.edu/~msolomon/problems.ht m, sedangkan untuk problem dengan 100 customer algoritma yang diusulkan diperbandingkan dengan algoritma tabu search yang diusulkan oleh Lau et al.(2003). Dalam hal ini yang diperbandingkan adalah jumlah kendaraan dan total jarak, namun dalam analisisnya nanti hasil terkait jumlah kendaraan tidak akan dibahas panjang lebar. Perhitungan gap dihitung dengan cara :
B
𝐺𝑎𝑝 =
𝑠𝑜𝑙𝑢𝑠𝑖 𝑎𝑙𝑔𝑜𝑟𝑖𝑡𝑚𝑎 − 𝑠𝑜𝑙𝑢𝑠𝑖 𝑎𝑐𝑢𝑎𝑛 𝑥 100% 𝑠𝑜𝑙𝑢𝑠𝑖 𝑎𝑐𝑢𝑎𝑛
3.1 Hasil Komputasi untuk Problem dengan 25 Customer Algoritma yang diusulkan tersebut menghasilkan keluaran yang disajikan pada tabel sebagai berikut : Tabel 1 Hasil Eksperimen untuk Tipe C1 dengan 25 Customer Solusi Eksak Immune System Gap Tipe Problem Kendaraan Jarak Kendaraan Jarak (%) C101 3 191.3 3 191.8 0.27 C102 3 190.3 3 190.7 0.23 C103 3 190.3 3 190.7 0.23 C104 3 186.9 3 187.4 0.29 C1 C105 3 191.3 3 191.8 0.27 C106 3 191.3 3 191.8 0.27 C107 3 191.3 3 191.8 0.27 C108 3 191.3 3 191.8 0.27 C109 3 191.3 3 191.8 0.27 Tabel 2 Hasil Eksperimen untuk Tipe C2 dengan 25 Customer Solusi Eksak Immune System Gap Tipe Problem Kendaraan Jarak Kendaraan Jarak (%) C201 2 214.7 2 215.5 0.39 C202 2 214.7 2 215.5 0.39 C203 2 214.7 2 215.5 0.39 C204 2 213.1 2 215.5 1.15 C2 C205 2 214.7 2 215.5 0.39 C206 2 214.7 2 215.5 0.39 C207 2 214.5 2 215.3 0.39 C208 2 214.5 2 215.4 0.41 Tabel 3 Hasil Eksperimen untuk Tipe R1 dengan 25 Customer Solusi Eksak Immune System Gap Type Problem Kendaraan Jarak Kendaraan Jarak (%) R101 8 617.1 8 632.3 2.47 R102 7 547.1 7 549.4 0.41 R103 5 454.6 5 464.2 2.12 R104 4 416.9 4 443.4 6.35 R105 6 530.5 6 542.3 2.22 R106 3 465.4 5 474.7 1.99 R1 R107 4 424.3 4 452.3 6.60 R108 4 397.3 4 424.5 6.84 R109 5 441.3 5 456.0 3.33 R110 4 444.1 4 449.1 1.14 R111 5 428.8 5 440.0 2.62 R112 4 393.0 4 401.9 2.26
Tabel 4 Hasil Eksperimen untuk Tipe R2 dengan 25 Customer Solusi Eksak Immune System Gap Type Problem Kendaraan Jarak Kendaraan Jarak (%) R201 4 463.3 3 479.9 3.59 R202 4 410.5 4 412.2 0.41 R203 3 391.4 2 411.0 5.00 R204 2 355.0 2 386.1 8.76 R205 3 393.0 3 408.8 4.02 R2 R206 3 374.4 2 387.5 3.49 R207 3 361.6 2 378.7 4.74 R208 1 328.2 1 331.8 1.10 R209 2 370.7 2 376.8 1.64 R210 3 404.6 2 425.6 5.18 R211 2 350.9 2 365.0 4.01
Tabel 5 Hasil Eksperimen untuk Tipe RC1 dengan 25 Customer
Type Problem
RC1
RC101 RC102 RC103 RC104 RC105 RC106 RC107 RC108
Solusi Eksak Immune System Gap Kendaraan Jarak Kendaraan Jarak (%) 4 461.1 4 462.2 0.23 3 351.8 3 353.0 0.33 3 332.8 3 334.4 0.48 3 306.6 3 307.1 0.18 4 411.3 4 419.7 2.05 3 345.5 3 346.5 0.29 3 298.3 3 299.5 0.40 3 294.5 3 297.6 1.05
Tabel 6 Hasil Eksperimen untuk Tipe RC2 dengan 25 Customer
Type Problem
RC2
RC201 RC202 RC203 RC204 RC205 RC206 RC207 RC208
Solusi Eksak Immune System Gap Kendaraan Jarak Kendaraan Jarak (%) 3 360.2 3 361.2 0.29 3 338.0 3 339.6 0.48 3 326.9 3 333.7 2.07 3 299.7 3 305.0 1.78 3 338.7 3 338.9 0.07 3 324.0 3 325.1 0.34 3 298.3 3 298.9 0.22 2 269.1 3 273.6 1.68
3.2 Hasil Komputasi untuk Problem dengan 100 Customer Untuk problem dengan jumlah customer sebanyak 100, algoritma yang diusulkan tersebut menghasilkan keluaran yang disajikan pada tabel sebagai berikut :
Tabel 7 Hasil Eksperimen untuk Tipe C1 dengan 100 Customer Tipe Problem C101 C102 C103 C104 C1 C105 C106 C107 C108 C109 Total
Tabu Search Kendaraan 10 10 10 10 10 10 10 10 10 90
Immune System
Jarak Kendaraan Jarak 828.94 10 828.94 834.64 10 851.56 834.56 10 865.64 846.32 10 871.74 828.94 10 828.94 828.94 10 828.94 828.94 10 828.96 828.94 10 832.16 828.94 10 828.94 90
Gap (%) 0.00 2.03 3.72 3.00 0.00 0.00 0.00 0.39 0.00
Tabel 4. 1 Hasil Eksperimen untuk Tipe R2 dengan 100 Customer Tipe Problem R201 R202 R203 R204 R205 R2 R206 R207 R208 R209 R210 R211 Total
Tabu Search Kendaraan 4 3 3 3 3 3 3 2 3 3 3 33
Immune System
Gap (%)
Jarak Kendaraan Jarak 1292.53 4 1490.8 15.34 1158.98 4 1271.1 9.67 980.70 3 1069.0 9.00 847.74 3 965.30 13.87 1146.80 3 1270.5 10.79 1007.00 3 1130.8 12.29 869.94 3 1034.7 18.94 790.46 3 878.52 11.14 1020.06 3 1108.9 8.71 1032.65 3 1133.5 9.77 866.10 3 979.04 13.04 35
Tabel 8 Hasil Eksperimen untuk Tipe C2 dengan 100 Customer
Tipe Problem C201 C202 C203 C204 C2 C205 C206 C207 C208 Total
Tabu Search Kendaraan 3 3 3 3 3 3 3 3 24
Immune System
Jarak Kendaraan Jarak 591.56 3 591.56 619.36 3 630.08 604.01 3 608.35 644.23 3 591.56 601.43 3 588.88 588.88 3 612.54 608.94 3 608.16 591.83 3 613.75 24
Gap (%) 0.00 1.73 0.72 -8.18 -2.09 4.02 -0.13 3.70
Tabel 9 Hasil Eksperimen untuk Tipe R1 dengan 100 Customer Tipe Problem R101 R102 R103 R104 R105 R106 R1 R107 R108 R109 R110 R111 R112 Total
Tabu Search Kendaraan 20 18 14 10 15 12 12 10 13 11 11 10 156
Immune System
Gap (%)
Jarak Kendaraan Jarak 1765.00 19 1712.4 -2.98 1548.61 17 1629.5 5.22 1258.34 14 1533.9 21.90 1018.48 10 1182.6 16.11 1462.69 14 1605.9 9.79 1328.66 12 1462.0 10.04 1160.08 12 1274.7 9.88 1045.83 10 1164.0 11.30 1259.09 13 1332.7 5.85 1127.70 11 1314.3 16.55 1097.10 11 1248.5 13.80 1021.95 10 1171.9 14.67 153
Tabel 4. 2 Hasil Eksperimen untuk Tipe RC1 dengan 100 Customer Tipe Problem RC101 RC102 RC103 RC104 RC1 RC105 RC106 RC107 RC108 Total
Tabu Search Kendaraan 15 13 12 10 15 12 11 10 98
Immune System
Gap (%)
Jarak Kendaraan Jarak 1657.46 15 1812.1 9.33 1535.79 13 1694.0 10.30 1386.03 11 1476.6 6.53 1213.25 10 1278.5 5.38 1625.13 15 1712.2 5.36 1426.07 12 1547.1 8.49 1330.59 11 1383.7 3.99 1175.88 11 1303.6 10.86 98
Tabel 4. 3 Hasil Eksperimen untuk Tipe RC2 dengan 100 Customer
Tipe Problem RC201 RC202 RC203 RC204 RC2 RC205 RC206 RC207 RC208 Total
Tabu Search Kendaraan 4 4 3 3 4 3 3 3 27
Immune System
Gap (%)
Jarak Kendaraan Jarak 1468.46 4 1648.7 12.27 1222.69 4 1584.9 29.62 1171.88 3 1280.7 9.29 839.32 3 1031.6 22.91 1338.70 4 1642.8 22.72 1201.27 3 1436.1 19.55 1139.48 3 1453.6 27.57 985.60 3 1113.8 13.01 27
4. Analisis dan Pembahasan Analisis yang dilakukan dalam hal ini adalah analisis terkait hasil uji algoritma pada problem dengan 25 customer dan problem dengan 100 customer.
4.1 Analisis Hasil Data Uji 25 Customer Dari 56 problem yang diselesaikan, khususnya untuk kasus C1, C2, RC1, dan RC2 menghasilkan solusi yang kompetitif dengan solusi eksak dengan deviasi tidak lebih dari 1%, sedangkan untuk problem R1 dan R2 menghasilkan deviasi sebesar 3.2% dan 3.81%. Hal ini menunjukkan bahwa untuk persoalan dengan customer yang terletak secara terklaster akan lebih mudah diselesaikan dengan artificial immune system, dibandingkan dengan persoalan dimana customer terdistribusi secara random. Dari 56 problem yang dilakukan eksperimen, tidak ada satupun solusi hasil artificial immune system yang menyamai atau lebih baik dibandingkan dengan solusi pembanding. Hal ini mengingat bahwa algoritma yang digunakan oleh referensi pembanding adalah algoritma eksak. Performansi algoritma yang bagus dalam menyelesaikan kasus dengan skala kecil tersebut tidak lepas dari metode inisialisasi yang digunakan, yaitu solomon insertion, yang dalam beberapa kasus sudah mampu menghasilkan solusi dengan kualitas yang baik. Disamping itu proses intensifikasi dengan mekanisme cloning juga sangat berdampak pada algoritma untuk mencapai solusi optimal dengan lebih cepat. 4.2 Analisis Hasil Data Uji 100 Customer Dari 56 problem yang diselesaikan, khususnya untuk problem C1 dan C2, algoritma artificial immune system mampu menghasilkan solusi yang kompetitif dengan solusi yang dihasilkan oleh metode pembanding, disamping itu jumlah kendaraan yang dihasilkan juga sama dengan jumlah kendaraan yang dihasilkan oleh solusi pembanding. Bahkan dalam beberapa kasus, hasil yang diperoleh artificial immune system mampu mengalahkan hasil yang diperoleh metode pembanding, yaitu pada problem C204, C205, dan C207. Sementara itu, untuk kasus C101, C105, C106, C107, C109, dan C201 algoritma artificial immune system mampu menghasilkan solusi yang sama dengan solusi yang dihasilkan oleh tabu search. Sementara untuk problem yang lain utnuk tipe C1 dan C2, algoritma yang diusulkan mampu memberikan solusi dengan deviasi maksimum sebesar 5%. Apabila dihitung secara rata – rata, untuk problem C1 artificial immune system menghasilkan deviasi sebesar 1,02% dan untuk problem C2 adalah -
0,03%, dengan kata lain untuk tipe C2 artificial immune system mampu memberikan solusi yang lebih baik . Performansi algoritma artificial immune system tersebut dapat dibilang cukup baik mengingat beberapa solusi yang dihasilkan mampu menyamai dan mengalahkan solusi dari algoritma pembanding. Performansi yang bagus tersebut lebih karena didukung oleh kualitas solusi yang dihasilkan oleh Solomon insertion yang sudah cukup bagus, dan dengan demikian artificial immune system hanya membutuhkan sedikit usaha improvement untuk menjadikannya sebagai solusi optimal. Untuk Kasus R1, R2, RC1, dan RC2 algoritma artificial immune system menghasilkan solusi dengan kualitas yang lebih buruk dibandingkan pada problem C1 dan C2. Secara rata – rata, untuk problem R1, R2, RC1, dan RC2, secara berturut - turut deviasi dari hasil yang diperoleh pembanding adalah 11,01%, 10.84%, 7,53%, dan 20,27%. Deviasi – deviasi tersebut cukup besar, mengingat bahwa dalam literatur, perbedaan hasil solusi pada umumnya hanya berkisar 0 – 3%. Kondisi ini disebabkan oleh beberapa hal yaitu sebagai berikut : 1) Beberapa solusi yang dihasilkan oleh solomon insertion memiliki jumlah kendaraan yang melebihi jumlah kendaraan maksimum, yang mana dalam hal ini mengacu pada referensi pembanding, dan dengan demikian langkah lanjutan yaitu prosedur ejection pool dilakukan. Prosedur ejection pool, yang dalam implementasi kali ini membuang parameter minimum delay, ternyata seringkali menghasilkan jarak yang lebih buruk, sekalipun bahwa jumlah kendaraan bisa dikurangi. Dengan demikian menurunkan kualitas solusi dari tahap inisialisasi. 2) Untuk beberapa kasus, solusi yang masuk ke dalam algoritma artificial immune system hanya berjumlah satu. Sekalipun bahwa dalam tahap cloning solusi tersebut diperbanyak, tetap saja bahwa dari sisi diversitas solusi tersebut tidak bagus, dengan kata lain solusi akan lebih susah keluar dari local optimum. Solusi lebih cenderung pada intensifikasi dan bukan diversifikasi. 3) Jumlah kendaraan yang tidak boleh bertambah juga membatasi gerak solusi untuk mengalami diversifikasi dan
perbaikan dalam hal jarak, hal ini dikarenakan bahwa setiap solusi hasil mutasi tidak diperkenankan memiliki kendaraan yang melebihi jumlah kendaraan yang ditetapkan, sekalipun mendapatkan jarak yang lebih pendek. 4.3 Analisis Performansi Algoritma Secara Keseluruhan Secara umum performansi algoritma artificial immune system dalam menyelesaikan problem VRPTW untuk customer dengan ukuran kecil mampu menghasilkan solusi yang kompetitif dengan solusi eksak, sedangkan untuk problem dengan skala besar, yaitu 100 customer, masih kalah. Khususnya untuk problem dengan customer sebanyak 100, artificial immune system menghasilkan solusi yang lebih buruk, khususnya terkait dalam hal jarak. Untuk jumlah kendaraan, algoritma yang diusulkan mampu memberikan jumlah kendaraan yang lebih sedikit, yaitu 427, sdangkan tabu search menghasilkan jumlah kendaraan sebesar 428. Tentu saja jumlah kendaraan yang minimum tersebut berada diluar kerangka immune system, karena solusi dengan jumlah kendaraan yang lebih minim diselesaikan dengan metode lain, yaitu Solomon insertion dan prosedur ejection pool. Sedangkan dari sisi jarak, artificial immune system menghasilkan solusi dengan deviasi rata – rata sebesar 8,93%. Dalam hal pengembangan algoritma immune system ini, tahapan inisialisasi memang tidak dibuat rumit. Hal ini dikarenakan bahwa tahapan inisialisasi yang terlalu rumit, yang bertujuan meminimasi jumlah kendaraan dan jarak, tidak akan memberikan ruang yang luas bagi algoritma utama untuk melakukan improvement. Dengan demikian nilai tambah dari pengembangan algoritma utama, dalam hal ini artificial immune system, hanya bernilai kecil. Oleh karenanya fase pertama dari algoritma yang diusulkan hanya bertujuan untuk meminimasi jumlah kendaraan. 5. Kesimpulan dan Saran Dari hasil eksperimen maupun analisis yang telah dilakukan, maka dapat diambil beberapa kesimpulan yakni Artificial immune system mampu menghasilkan solusi yang kompetitif untuk problem dengan skala kecil (ukuran customer sebanyak 25), sedangkan untuk kasus dengan skala besar, yaitu 100
customer, artificial immune system menghasilkan solusi yang lebih buruk, Artificial immune system sangat efektif menyelesaikan problem VRPTW Solomon untuk tipe customer yang terletak secara tercluster (C1 dan C2), dibandingkan dengan customer yang terletak secara random (R1, R2, RC1, RC2). Performansi algoritma artificial immune system dalam menghasilkan solusi pada penelitian ini tidak lepas dari tahapan inisialisasi dan tahapan mutasi (local search) Sedangkan saran yang bias diberikan untuk penelitian selanjutnya adalah penelitian selanjutnya bisa dilakukan dengan memodifikasi algoritma sehinga dapat melakukan proses diversifikasi dengan baik, dan agar tidak mudah terjebak pada local optimum. Penelitian selanjutnya bisa dilakukan dengan cara memodifikasi algoritma artificial immune system yang tidak hanya mengacu pada clonal selection, melainkan juga melibatkan proses artificial immune system yang lain, yaitu negative selection, maupun network theory. Penelitian berikutnya bisa dilakukan dengan menggunakan data set yang lebih besar yaitu lebih dari 200 customer untuk mengetahui lebih jauh performansi algoritma. 6. Daftar Pustaka Berger, J., Barkaoui, M. (2004). A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research, 31, 2037–2053 Balseiro, S.R, Loiseau, I, Ramonet, J. (2011). An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows. Computers & Operations Research 38, 954–966 Brownlee, J. (2005). Clonal Selection Theory & Clonalg, The Clonal Selection Classification Algorithm (CSCA). Swinburne University of Technology Cheng, C, Wang, K. (2009). Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm. Expert Systems with Applications, 36, 7758–7763 Cordeau, J.F., Desaulniers, G., Desrosiers, J., Solomon M., Soumis, F. (2002). The VRP with time windows. In: Toth P, Vigo D, editors. The vehicle routing problem,
SIAM monographs on discrete mathematics and applications, Society for Industrial & Applied Mathematics, Philadelphia, USA. Dasgupta, D., Nino, L. F., (2009). Immunological Computation. Washington: Auerbach Publications de Castro, L., & Zuben, F. V. (2002). Learning and optimization using the clonal selection principle. IEEE Transactions Evolutionary Computation 6, 239–251 Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40 (2), 342–354 Engin, O., Doyen, A. (2004). A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Computer Systems, 20, 1083–1095 Gong, M., Jiao, L., Zhang, X. (2008). A population-based artificial immune system for numerical optimization. Neurocomputing, 72, 149–161 Homberger, J & Gehring, H. (2005). A twophase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research, 162, 220–238 Jiangang, X. (2009). The Vehicle Routing Problem based on Immune Algorithm. Quebec: Universite du Quebec a Chicoutimi. Lau, H.C. , Sim, M., Teo, K. M.. (2003). Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles. European Journal of Operational Research 148, 559–569
Lim A, Zhang X. (2007). A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. INFORMS Journal on Computing, 19 (3) 443–457 Mingyong, L., Erbao, C. (2010). An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence, 23, 188–195 Savelsbergh, M. (1985). Local search in routing problems with time windows. Annals of Operations Research, 4, 285– 305. Solomon M. (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35 (2) 254–65 Tan, K. C., Goh, C.K., Mamun, A.A., Ei, E.Z. (2008). An evolutionary artificial immune system for multi-objective optimization. European Journal of Operational Research, 187, 371–392 Tan, K. C., Lee, L. H., Ou, K. (2001). Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engineering Applications of Artificial Intelligence, 14, 825 – 837 Zachariadis, E., Tarantilis, C., Kiranoudis, C. (2009). A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert Systems with Applications, 36, 1070–1081.
