Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Ant Colony Optimization dan Simulated Annealing

Abstract

Capacitated Vehicle Routing Problem (CVRP) merupakan variasi dari Vehicle Routing Problem (VRP). CVRP bertujuan mencari rute yang meminimalkan biaya transportasi untuk melayani semua pelanggan dengan tetap memperhatikan kendala kapasitas kendaraan. CVRP bersifat NP-Hard problem sehingga sulit menyelesaikan masalah ini secara langsung. Terdapat beberapa metode metaheuristic yang dapat digunakan untuk menyelesaikan permasalahan ini. Pada karya ilmiah ini, metode metaheuristic yang digunakan untuk menyelesaikan CVRP adalah metode Ant Colony Optimization (ACO) dan metode Simulated Annealing (SA). Penelitian ini menggunakan tujuh kasus CVRP. Hasil penelitian memperlihatkan bahwa waktu eksekusi metode SA relatif lebih cepat untuk kasus dengan jumlah node yang sedikit, tetapi relatif lebih lama untuk jumlah node yang lebih banyak dibandingkan metode ACO. Selain itu, total jarak yang dihasilkan metode SA lebih optimal dibandingkan total jarak yang dihasilkan metode ACO.

Capacitated Vehicle Routing Problem (CVRP) is a variation of the Vehicle Routing Problem (VRP). CVRP aims to find routes that minimize transportation costs to serve all customers while taking into account vehicle capacity constraints. CVRP is an NP-Hard problem so it is difficult to solve this problem directly. There are several metaheuristic methods that can be used to solve this problem. In this scientific work, the metaheuristic methods used to solve CVRP are the Ant Colony Optimization (ACO) method and the Simulated Annealing (SA) method. This research uses seven CVRP cases. The results show that the execution time of the SA method is relatively faster for cases with a small number of nodes, but relatively longer for a larger number of nodes than the ACO method. In addition, the total distance generated by the SA method is more optimal than the total distance generated by the ACO method.