Tabu Search HGreX Crossover Untuk Penyelesaian Capacitated Vehicle Routing Problem

SUHERI, Dr. Azhari SN., MT.

2016 | Tesis | S2 Ilmu Komputer

Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu 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. Pemilihan rute yang tepat merupakan faktor penting dalam rangka meminimalkan biaya yang harus dikeluarkan oleh distributor. Kebutuhan akan adanya metode yang dapat diterapkan secara otomatis untuk menentukan rute optimal dalam kasus CVRP, menuntun munculnya berbagai pendekatan yaitu eksak, heuristik, dan metaheuristik. Salah satu algoritma dari pendekatan heuristik/metaheuristik yang telah banyak digunakan adalah Tabu Search. Algoritma Tabu Search 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 digunakan operator HGreX Crossover untuk meningkatkan kualitas solusi yang dihasilkan dan mengurangi waktu eksekusi. Hasil pengujian pada dataset Augerat dengan kode A-n32-k5 dan A-n39-k5 menunjukan bahwa penggunaan algoritma Tabu Search HGreX Crossover mampu meningkatkan kualitas solusi secara berturut-turut sebesar 14.88% dan 15.16% untuk 100 iterasi, 19.08% dan 15.28% untuk 500 iterasi, dan 14.04% dan 18.42% untuk 1000 iterasi jika dibandingkan dengan Tabu Search konvensional dan waktu yang dibutuhkan Tabu Search HGreX Crossover lebih cepat 4.43% dan 4.10% untuk 100 iterasi, 4.47% dan 4.88% untuk 500 iterasi, dan 3.44% dan 6.24% untuk 1000 iterasi dibandingkan dengan Tabu Search konvensional.

Capacitated Vehicle Routing Problem (CVRP) is a algoritm for optimal design problems to the vehicle fleet that serves the distribution of goods to a number of consumers with a certain number of requests that do not exceed the limit charge capacity of the fleet of vehicles used. Selection of the appropriate service is an important factor to minimize the costs and incurred by the distributor. The need for methods that can be applied automatically to determine the optimal route in case CVRP, leading the emergence of a variety of approaches are exact, heuristics, and metaheuristics. One algorithm of heuristic approach / Metaheuristic which has been widely used is Tabu Search. Tabu Search algorithm works by utilizing the techniques of search and local search solution space using the taboo list to be able to avoid a local optimum or premature convergence, but requires a long process because the search using local search techniques that are sequential. Instead, the operator HGreX Crossover to improve the quality of the resulting solution and reduce the execution time. The test results on the dataset Augerat with code A-n32-k5 and A-n39-k5 showed that the use of Tabu Search algorithm HGreX Crossover able to improve the quality of the solution, respectively by 14.88% and 15.16% for 100 iterations, 19.08% and 15.28% for 500 iterations, and 14.04% and 18.42% for 1000 iterations when compared with conventional Tabu Search and Tabu Search HGreX Crossover more faster 4.43 % and 4.10% for 100 iterations, 4.47% and 4.88% for 500 iterations, and 3.44% and 6.24% for 1000 iterations compared with conventional Tabu Search.

Kata Kunci : CVRP, Tabu Search, HGreX Crossover