Penyelesaian Capacitated Vehicle Routing Problem menggunakan Algoritma Modified Fuzzy C-Means dan Artificial Bee Colony.

Abstract

Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu variasi dari Vehicle Routing Problem (VRP) yang mempertimbangkan kapasitas angkut kendaraan sebagai batasan yang harus dipenuhi. Terdapat beberapa metode yang dapat digunakan untuk menyelesaikan permasalahan ini. Pada karya ilmiah ini CVRP diselesaikan menggunakan metode pendekatan metaheuristik dengan algoritma Modified Fuzzy C-Means dan Artificial Bee Colony (ABC) melalui dua tahap. Pada tahap pertama, algoritma Modified Fuzzy C-Means digunakan untuk menentukan klaster dari sejumlah pelanggan berdasarkan nilai fuzzy pada setiap derajat keanggotaan. Pada tahap kedua, algoritma ABC dan Integer Linear Programming (ILP) digunakan untuk menentukan rute perjalanan di setiap klaster dan waktu komputasi. Permasalahan model CVRP diimplementasikan pada masalah pendistribusian roti. Hasil implementasi memperlihatkan bahwa algoritma ABC mampu menghasilkan solusi yang sangat mendekati solusi ILP dengan selisih perbedaan yang kecil dan waktu komputasi menggunakan algoritma ABC lebih cepat dibandingkan dengan solusi ILP.

The Capacitated Vehicle Routing Problem (CVRP) is a variation of the Vehicle Routing Problem (VRP) that considers vehicle capacity a constraint that must be satisfied. Various methods are available to solve this problem. In this scientific paper, the CVRP solved used a metaheuristic approach with the Modified Fuzzy C-Means algorithm and the Artificial Bee Colony (ABC) algorithm in two stages. In the first stage, the Modified Fuzzy C-Means algorithm is used to determine clusters of customers based on fuzzy values for each degree of membership. In the second stage, the ABC algorithm and Integer Linear Programming (ILP) determine travel routes within each cluster and computation time. The models of CVRP implemented the bread distribution problem. The implementation results show that the ABC algorithm produces solutions that closely approximate the ILP solution, with a small margin of difference. Additionally, the computation time of the ABC algorithm is faster than that of the ILP solution.