Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Algoritme Clarke-Wright dan Algoritme Genetika

Abstract

Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu variasi dari Vehicle Routing Problem (VRP) dengan kapasitas angkut kendaraan sebagai kendala yang dihadapi. Ada beberapa metode yang dapat digunakan untuk menyelesaikan permasalahan ini. Pada karya ilmiah ini, digunakan algoritme Clarke-Wright dan algoritme genetika untuk menyelesaikan CVRP. Pada tahap pertama algoritme Clarke-Wright digunakan untuk pembentukan grup dari sejumlah pelanggan berdasarkan konsep penghematan jarak. Tahap kedua digunakan algoritme genetika untuk penentuan rute pendistribusian di setiap grup yang sudah terbentuk. Model diimplementasikan pada pendistribusian roti. Hasil implementasi model memperlihatkan algoritme yang diusulkan lebih baik dibandingkan dengan algoritme greedy.

Capacitated Vehicle Routing Problem (CVRP) is a variation of Vehicle Routing Problem (VRP) with the vehicle carrying capacity as an obstacle. There are several methods that can be used to solve this problem. In this scientific work, the Clarke-Wright algorithm and genetic algorithm are used to solve CVRP. In the first step, the Clarke-Wright algorithm is used to form groups of a number of customers based on the concept of distance saving. In the second step, genetic algorithms are used to determine the distribution route in each group that has been formed. The model is implemented in bread product delivery. The result of model implementation shows that the proposed algorithm is better than the greedy algorithm.