Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Algoritme Improved K-Means Clustering dan Simulated Annealing

Abstract

Capacitated Vehicle Routing Problem (CVRP) adalah salah satu varian dari Vehicle Routing Problem (VRP) yang memperhitungkan kapasitas angkut kendaraan sebagai batasan utama. Ada berbagai metode yang dapat diterapkan untuk menyelesaikan masalah ini. Dalam penelitian ini, digunakan kombinasi algoritme Improved K-Means Clustering dan metode pendekatan algoritme Simulated Annealing (SA) untuk menyelesaikan CVRP. Pada langkah pertama, algoritme Improved K-Means Clustering diterapkan untuk mengklasterkan pelanggan berdasarkan permintaan maksimum pelanggan dan jarak titik koordinat terdekat antar pelanggan. Langkah kedua menggunakan metode pendekatan algoritme SA untuk menentukan rute distribusi pada setiap klaster yang telah terbentuk. Model ini diterapkan pada distribusi produk makanan, hasilnya menunjukkan bahwa penentuan rute menggunakan algoritme yang diusulkan memberikan hasil yang sama ketika dibandingkan dengan penentuan rute menggunakan metode eksak Integer Linear Programming (ILP) yang sudah diklastersasi.

The Capacitated Vehicle Routing Problem (CVRP) is a variant of the Vehicle Routing Problem (VRP) that considers vehicle capacity as a primary constraint. Various methods can be applied to solve this problem. In this research, a combination of the Improved K-Means Clustering algorithm and the Simulated Annealing (SA) approach is used to solve the CVRP. In the first step, the Improved K-Means Clustering algorithm is applied to cluster customers based on their maximum demand and the proximity of their coordinates. The second step uses the SA approach to determine the distribution routes within each formed cluster. This model is applied to food product distribution, and the results show that the route determination using the proposed algorithm produces outcomes equivalent to those generated by the exact method of Integer Linear Programming (ILP) after clustering has been applied.