BAB I PENDAHULUAN
1.1.
Latar Belakang Vehicle Routing Problem (VRP) merupakan konsep umum yang digunakan
untuk semua permasalahan yang melibatkan perancangan rute optimal untuk armada kendaraan yang melayani sejumlah customer dengan batasan-batasan tertentu (Baldacci et al., 2012) yang merupakan perluasan dari permasalahan Traveling Salesman Problem (TSP) (Toth and Vigo, 2002a). Salah satu varian dari VRP adalah Capacitated Vehicle Routing Problem (CVRP) yang merupakan pemodelan untuk permasalahan perancangan rute optimal untuk armada kendaraan yang melayani pendistribusian barang kepada sejumlah konsumen dengan jumlah permintaan tertentu yang tidak melebihi batasan kapasitas muatan dari armada kendaraan yang digunakan dengan tujuan untuk meminimalkan total biaya perjalanan yang berupa jarak tempuh, dimana dapat direpresentasikan seperti pada Gambar 1.1.
Gambar 1.1 Contoh Ilustrasi Kasus CVRP 13
14
Pada Gambar 1.1 di atas v0 mewakili sebuah depot atau pusat pendistribusian barang, sedangkan v1 sampai dengan v10 menunjukkan konsumen yang melakukan permintaan barang. Tujuan dari CVRP adalah meminimalkan total biaya perjalanan yang berupa jarak tempuh dengan batasan berupa muatan yang dibawa oleh armada kendaraan tidak boleh melebihi kapasitas muatan armada kendaraan itu sendiri. CVRP merupakan jenis permasalahan kombinatorial yang diklasifikasikan sebagai NP-hard problem. Oleh karena itu, diperlukan suatu metode khusus untuk dapat menyelesaikan permasalahan CVRP. Terdapat
beberapa
pendekatan
yang
dapat
digunakan
untuk
menyelesaikan permasalahan CVRP, yaitu pendekatan eksak, heuristik, dan metaheuristik. Salah satu algoritma dari pendekatan metaheuristik yang telah banyak digunakan dan mampu menyelesaikan kasus CVRP dengan kinerja yang baik adalah algoritma Tabu Search (Guan et al., 2010), (Jia et al., 2013), (Toth and Vigo,
2002b).
Algoritma
Tabu
Search
konvensional
bekerja
dengan
memanfaatkan teknik pencari ruang solusi local search dan menggunakan tabu list untuk dapat terhindar dari local optimum atau konvergensi yang prematur, namun memerlukan proses yang panjang dikarenakan pencarian menggunakan teknik local search yang bersifat sekuensial. Oleh karena itu, penulis mengusulkan ide penggunaan operator crossover sebagai satu tahapan yang perlu dilakukan untuk memperbaiki solusi yang digunakan dalam pembentukan solusi tetangga (neighborhood) dengan harapan bahwa proses penemuan solusi yang mendekati dan atau global optimum akan menjadi lebih cepat. Adapun operator crossover yang digunakan adalah HGreX, dimana operator HGreX merupakan salah satu dari 3 (tiga) operator crossover algoritma genetika yang memberikan hasil terbaik dari 8 (delapan) operator crossover yang diuji kinerjanya untuk penyelesaian kasus VRP (Puljić and Manger, 2013) dan sejauh ini belum ada penelitian yang mencoba menggabungkan algoritma Tabu Search konvensional dengan operator HGreX Crossover. Oleh karena itu, penelitian ini
15
akan mencoba menggabungkan kedua buah metode tersebut dengan harapan operator HGreX Crossover dapat meningkatkan kinerja dari algoritma Tabu Search konvensional. 1.2.
Rumusan Masalah Berdasarkan latar belakang yang telah diuraikan di atas, maka rumusan
masalah dalam penelitian ini adalah apakah penggunaan operator crossover HGreX untuk pembentukan solusi yang akan digunakan dalam proses pembentukan solusi tetangga (neighborhood) pada algoritma Tabu Search dapat mempercepat proses konvergensi dalam mencapai solusi yang mendekati dan atau global optimum. 1.3.
Batasan Masalah Batasan masalah dalam penelitian yang akan dilakukan adalah: 1. Penerapan algoritma Tabu Search dengan Crossover HGreX untuk menyelesaikan permasalahan CVRP dengan studi kasus menggunakan dataset Augerat (1995) dengan kode A-n32-k5 dan A-n53-k7. 2. Operator Crossover HGreX yang digunakan mengacu pada penelitian yang dilakukan oleh (Puljić and Manger, 2013) dan diterapkan sebagai satu tahapan yang perlu dilakukan terhadap sebuah solusi sebelum dilanjutkan untuk proses pembentuk solusi tetangga (neighborhood). 3. Pembentukan solusi tetangga menggunakan konsep permutasi dengan metode swap antara 2 buah simpul. 4. Pengujian dilakukan dengan membandingkan hasil dari algoritma Tabu Search tanpa Crossover dengan Tabu Search HGreX Crossover yang berupa kualitas solusi dan waktu yang dibutuhkan untuk memperoleh solusi tersebut.
16
1.4.
Tujuan Penelitian Tujuan penelitian ini adalah menerapkan algoritma Tabu Search dengan
Crossover HGreX untuk menyelesaikan Capacitated Vehicle Routing Problem, sehingga mampu memberikan solusi yang mendekati dan atau global optimum dalam waktu yang lebih singkat. 1.5.
Manfaat Penelitian Penelitian yang akan dilakukan diharapkan dapat memberikan manfaat
yaitu: 1. Memberikan gambaran penggunaan algoritma Tabu Search dengan operator Crossover HGreX dalam rangka menyelesaikan Capacitated Vehicle Routing Problem. 2. Menjadi acuan dalam upaya melakukan peningkatan (improvement) maupun digunakan
pengembangan
terhadap
untuk menyelesaikan
algoritma-algoritma
Capacitated Vehicle
yang Routing
Problem. 1.6.
Keaslian Penelitian Penelitian dengan domain permasalahan optimasi solusi untuk CVRP
dengan menggunakan algoritma Tabu Search sudah pernah dilakukan. Selain itu, penelitian tentang penggunaan operator Crossover HGreX yang digunakan untuk pembentukan kromosom baru dalam algoritma Evolutionary Algorithms untuk VRP juga sudah pernah dilakukan. Berdasarkan referensi dan kajian pustaka, penelitian mengenai penyelesaian Capacitated Vehicle Routing Problem dengan menggunakan algoritma Tabu Search HGreX Crossover untuk menentukan solusi yang mendekati dan atau global optimum belum pernah dilakukan. Adapun penelitian terdahulu yang berkaitan dengan domain permasalahan tersebut dipaparkan dalam tinjauan pustaka dalam usulan penelitian ini.
17
1.7.
Metodologi Penelitian Metodologi penelitian yang dilakukan dalam penelitian ini secara garis
besar adalah: 1. Studi literatur Tahap ini dilakukan guna mengumpulkan dan mempelajari informasi dan ilmu yang berhubungan dengan Capacitated Vehicle Routing Problem, algoritma Tabu Search, operator HGreX Crossover yang diperoleh dengan membaca literatur pendukung berupa buku-buku, jurnal-jurnal ilmiah, maupun sumbersumber di internet. 2. Pengumpulan data Tahap ini melakukan pengumpulan data yang berhubungan dengan objek penelitian, yaitu data depot, kapasitas muatan, koordinat tujuan (konsumen), demand, dan data pelengkap lainnya yang diperoleh dari dataset Augerat (1995) dengan kode A-n32-k5 dan A-n53-k7 melelui situs http://neo.lcc.uma.es/vrp/vrpinstances/capacitated-vrp-instances/. 3. Rancangan model Tahap ini berisi tentang rancangan model penggunaan algoritma Tabu Search dan operator Crossover HGreX yang diimplementasikan untuk menyelesaikan Capacitated Vehicle Routing Problem yang diharapkan dengan adanya penggunaan operator Crossover HGreX dapat meningkatkan kualitas solusi dan mempercepat proses konvergensi untuk memperoleh solusi yang mendekati dan atau global optimum. 4. Impementasi dan pengujian Pada tahap ini rancangan model dari sistem yang telah dibuat dikembangkan menjadi perangkat lunak. Selanjutnya dilakukan pengujian untuk mengukur kinerja sistem dalam menentukan solusi optimal berupa rute atau jarak terdekat dan waktu yang diperlukan dalam pencapaian solusi optimal. Pengujian dilakukan dengan membandingkan hasil dari sistem yang dibuat dengan menggunakan algoritma Tabu Search HGreX Crossover dengan sistem
18
yang dibuat hanya menggunakan algoritma Tabu Search konvensional pada dataset yang sama terhadap kualitas solusi dan waktu eksekusi. Adapun parameter yang digunakan untuk membandingkan hasilnya adalah berupa solusi akhir dan waktu eksekusi. 5. Analisis dan kesimpulan Pada tahap ini dilakukan analisis berdasarkan hasil pengujian yang telah dilakukan dari masing-masing algoritma yang digunakan, yaitu Tabu Search HGreX Crossover dan Tabu Search dengan variabel kualitas solusi dan waktu yang dihasilkan. 1.8.
Sistematika Penulisan Sistematika penulisan dalam penelitian ini dibagi menjadi beberapa Bab.
untuk memudahkan dalam pembahasannya, pembagian tersebut diantaranya: BAB I PENDAHULUAN Bab ini membahas mengenai latar belakang masalah, rumusan masalah, batasan masalah, tujuan penelitian, manfaat penelitian, keaslian penelitian, metodologi penelitian, dan sistematika penulisan. BAB II TINJAUAN PUSTAKA Bab ini menjelaskan tentang penelitian yang pernah dilakukan oleh para peneliti lain untuk dijadikan sebagai referensi dalam penelitian. BAB III LANDASAN TEORI Bab ini membahas mengenai teori-teori yang dibutuhkan dan berhubungan dengan masalah yang dibahas dalam penelitian. BAB IV ANALISIS DAN PERANCANGAN SISTEM Bab ini membahas mengenai analisis masalah, analisis perangkat lunak, analisis perangkat keras, batasan perancangan, perancangan proses, perancangan
perangkat
lunak,
perancangan
masukan, dan perancangan keluaran.
menu,
perancangan
19
BAB V IMPLEMENTASI SISTEM Bab ini membahas mengenai implementasi sistem sesuai dengan rancangan. BAB VI HASIL DAN PEMBAHASAN Bab ini berisi pengujian dan analisis terhadap hasil pengujian sistem yang telah dikembangkan. BAB VII KESIMPULAN DAN SARAN Bab ini membahas mengenai kesimpulan yang diperoleh dari masalah yang telah dicapai serta saran untuk pengembangan sistem selanjutnya.
