Bees algorithm dengan operator pencarian lokal SBESTSO pada capacitated vehicle routing problem

Syahidah, Karima (2026) Bees algorithm dengan operator pencarian lokal SBESTSO pada capacitated vehicle routing problem. Sarjana thesis, UIN Sunan Gunung Djati Bandung.

Preview	Text 1_cover.pdf Download (411kB) | Preview
Preview	Text 2_abstrak.pdf Download (173kB) | Preview
Preview	Text 3_skbebasplagiarism.pdf Download (665kB) | Preview
Preview	Text 4_daftarisi.pdf Download (211kB) | Preview
Preview	Text 5_bab1.pdf Download (205kB) | Preview
	Text 6_bab2.pdf Restricted to Registered users only Download (455kB) | Request a copy
	Text 7_bab3.pdf Restricted to Registered users only Download (444kB) | Request a copy
	Text 8_bab4.pdf Restricted to Registered users only Download (265kB) | Request a copy
	Text 9_bab5.pdf Restricted to Registered users only Download (157kB) | Request a copy
	Text 10_daftarpustaka.pdf Restricted to Registered users only Download (143kB) | Request a copy
	Text 11_lampiran.pdf Restricted to Repository staff only Download (2MB) | Request a copy

Abstract

Capacitated Vehicle Routing Problem (CVRP) merupakan permasalahan optimasi distribusi yang bertujuan menentukan rute kendaraan dengan total jarak tempuh minimum dengan tetap memenuhi batas kapasitas kendaraan. Permasalahan ini termasuk kategori NP-hard sehingga metode eksak kurang fisien untuk permasalahan berskala besar. Salah satu metode metaheuristik yang dapat digunakan adalah Bees Algorithm (BA), namun kualitas solusi yang dihasilkan masih dapat ditingkatkan karena proses eksploitasi lokal belum memanfaatkan ruang pencarian secara optimal. Oleh karena itu, penelitian ini bertujuan mengimplementasikan operator pencarian lokal Subtour of Beginning or End of a Salesman Tour Swapping Operator (SBESTSO) pada Bees Algorithm serta membandingkan kinerjanya dengan Bees Algorithm tanpa operator SBESTSO. Implementasi dilakukan menggunakan Python pada sepuluh dataset standar CVRPLIB. Evaluasi dilakukan berdasarkan total jarak tempuh dan waktu komputasi. Hasil penelitian menunjukkan bahwa integrasi operator SBESTSO yang dimodifikasi mampu memperkuat proses eksploitasi Bees Algorithm, sehingga menghasilkan nilai fungsi objektif yang lebih optimal pada seluruh dataset uji. Rata-rata peningkatan kinerja yang diperoleh adalah sebesar 10,698%, dengan peningkatan tertinggi mencapai 16,210% pada dataset E-n101-k8 dan peningkatan terendah sebesar 4,196% pada dataset A-n33-k6. Meskipun terjadi peningkatan waktu komputasi akibat penambahan mekanisme pencarian lokal dan evaluasi orientasi rute (reversed), operator ini terbukti efektif dalam menghindar dari optimum lokal. Dengan demikian, modifikasi operator SBESTSO terbukti secara signifikan meningkatkan performa Bees Algorithm dalam menyelesaikan Capacitated Vehicle Routing Problem (CVRP). The Capacitated Vehicle Routing Problem (CVRP) is a distribution optimization problem aimed at determining vehicle routes with minimum total travel distance while satisfying vehicle capacity constraints. As an NP-hard problem, exact methods are inefficient for solving large-scale instances. Although the Bees Algorithm (BA) is a metaheuristic method commonly used for this problem, its solution quality can still be enhanced, as the local exploitation process does not fully utilize the search space. Therefore, this study aims to implement the Subtour of Beginning or End of a Salesman Tour Swapping Operator (SBESTSO) local search operator within the Bees Algorithm and compare its performance against the standard Bees Algorithm without SBESTSO. The implementation was conducted using Python on ten benchmark datasets from CVRPLIB, with evaluation based on total travel distance and computational time. The results demonstrate that integrating the modified SBESTSO operator significantly enhances the local exploitation process of the Bees Algorithm, leading to superior objective function values across all tested datasets. An average performance improvement of 10.698% was achieved, with the highest improvement reaching 16.210% on the E-n101-k8 dataset and the lowest at 4.196% on the A-n33-k6 dataset. Although computational time increased due to additional local search mechanisms and route orientation (reversed) evaluations, the operator effectively prevented the algorithm from getting trapped in local optima. Consequently, the modified SBESTSO operator is proven to effectively improve the performance of the Bees Algorithm in solving the Capacitated Vehicle Routing Problem (CVRP).

Actions (login required)

View Item