Algoritma Spotted Hyena Optimizer pada Capacitated Vehicle Routing Problem

PRAYOGA YUDHA P, Ir. Nur Mayke Eka Normasari, S.T.,M.Eng., Ph.D., IPM.

2023 | Tesis | MAGISTER TEKNIK INDUSTRI

Capacitated Vehicle Routing Problem (CVRP) merupakan permasalahan dasar yang dirujuk untuk mencari rute terbaik dengan biaya minimal. Meskipun demikian CVRP termasuk ke dalam combinatorial optimization yang menyebabkan banyaknya alternative solusi dan menjadi lama proses pencarian solusinya ketika diselesaikan dengan pendekatan enumerasi untuk skala permasalahan yang besar. Jalan tengah yang diambil adalah pendekatan metaheuristik karena menghasilkan solusi yang cukup baik namun dengan waktu yang lebih cepat. Beberapa algoritma metaheuristik telah diimplementasikan pada CVRP, namun masih memiliki gap terhadap nilai optimalnya, sehingga terdapat peluang untuk mengembangkan algoritma baru untuk mereduksi gap tersebut. Metaheuristik yang cukup baru adalah Spotted Hyena Optimizer (SHO) yang terinspirasi dari cara berburu hyena. Algoritma SHO telah diimplementasikan pada CVRP dengan menggunakan dataset Augerat sejumlah 60 instance. Dari 60 instance dibagi menjadi 15 kelompok untuk dilakukan parameter setting mengenai jumlah agen dan jumlah iterasi. Meskipun demikian, performa SHO secara individu tidak mampu mengungguli algoritma lain seperti GA, ACO, dan PSO, sehingga dilakukan hibridasi dengan algoritma Large Neighborhood Search (LNS) untuk menyokong kelemahan SHO dalam local search. Algoritma hybrid ini bernama SHOLNS dan didapatkan solusi yang jauh lebih baik bahkan dengan state-of-the-art dari metaheuristic seperti Differential Evolution dan Crow Search Algorithm. Dari 60 instance yang diuji, SHOLNS mengungguli (best) seluruh algoritma competitor pada 41 instance, cukup baik (better) dibandingkan salah algoritma competitor pada 11 instance, dan tidak lebih baik dibandingkan seluruh algoritma competitor pada 8 instance. Rata-rata error dan persentase standar deviasi yang dihasilkan dari SHOLNS adalah sebesar 13.75% dan 2.9% yang merupakan nilai terkecil dibandingkan seluruh algoritma competitor. Meskipun SHOLNS menghasilkan kualtias solusi terbaik dibandingkan kompetitornnya, SHOLNS memiliki kekurangan pada waktu komputasi paling lama dibandingkan algoritma lainnya, yaitu dengan rata-rata waktu komputasi sebesar 569.47 detik.

Capacitated Vehicle Routing Problem (CVRP) is a basic problem that is referred to to find the best route at minimal cost. However, CVRP is included in combinatorial optimization which causes many alternative solutions and becomes a long time to finding solutions when solved using enumeration on a large scale problems. Metaheuristic is taken because it produces a fairly good solution but with a faster time. Several metaheuristic algorithms have been implemented in CVRP, but they still have gaps to their optimal values, so there is an opportunity to develop new algorithms to reduce these gaps. A fairly new metaheuristic is the Spotted Hyena Optimizer (SHO) which is inspired by how hyenas hunt. The SHO algorithm has been implemented on CVRP using the Augerat dataset that consist of 60 instances. Of the 60 instances, it is divided into 15 groups to set parameters regarding the number of agents and iterations. However, SHO performance was unable to outperform other algorithms such as GA, ACO, and PSO, so it was hybridized using the Large Neighborhood Search (LNS) algorithm to support SHO's weaknesses in local search. This hybrid algorithm is called SHOLNS and gets a much better solution even with state-of-the-art from metaheuristic such as Differential Evolution and Crow Search Algorithm. Of the 60 instances tested, SHOLNS outperformed (best) all competitor algorithms on 41 instances, was quite good (better) compared to one of the competitor algorithms on 11 instances, and worst solution than all competitor algorithms in 8 instances. The average error and percentage of standard deviation generated by SHOLNS is 13.75% and 2.9% which is the smallest value compared to all competitor algorithms. Although SHOLNS produces the best solution compared to its competitors, it has the disadvantage of the longest computational time compared to other algorithms, with an average computational time of 569.47 seconds.

Kata Kunci : riset operasi, vehicle routing problem, metaheuristik, spotted hyena optimizer, large neighborhood search