APLIKASI ALGORITMA KOLONI LEBAH DAN METODE NEAREST NEIGHBOUR UNTUK PENYELESAIAN CAPACITATED VEHICLE ROUTING PROBLEM

Abstract

Abstrak

Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu variasi paling umum dari masalah Vehicle Routing Problem (VRP) untuk menentukan rute yang optimal dengan penambahan kendala berupa kapasitas kendaraan yang homogen. Masalah CVRP yang dibahas yaitu menentukan rute pendistribusian roti sandwich Sari Roti pada CV. Jogja Transport di wilayah Bantul. Tujuan penelitian ini untuk membuat model matematika permasalahan CVRP untuk roti sandwich Sari Roti, menyelesaikan dengan Algoritma Koloni Lebah dan Metode Nearest Neighbour yang selanjutnya dilakukan analisis perbandingan untuk melihat metode mana yang menghasilkan jarak terpendek. Hasil penelitian menunjukkan bahwa berdasarkan perbandingan terhadap jumlah roti yang diangkut, Metode Nearest Neighbour menghasilkan rute yang dapat memaksimalkan kapasitas angkut kendaraan yaitu mengangkut hingga 97,86% atau sebanyak 411 buah roti dari total kapasitas maksimum 420 roti. Berdasarkan perbandingan terhadap jarak tempuh, Algoritma Koloni lebah menghasilkan total jarak tempuh sebesar 87,1 km. Jarak tersebut lebih efektif 2,51 km dari Metode Nearest Neighbour.

Kata kunci: CVRP, Distribusi, Algoritma Koloni Lebah, Metode Nearest Neighbour

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is one of the most common variations of the Vehicle Routing Problem (VRP) to determine the optimal route using a homogeneous vehicle capacity constrain. In this research, we determine the distribution route of sandwich bread of Sari Roti in CV. Jogja Transport in Bantul. The purposes of this research are to formulate mathematical model of CVRP problem for Sari Roti sandwich bread, to solve model using Bee Colony Algorithm and Nearest Neighbor Method. In the end, comparative analysis is done to see which method produce the shortest distance. The results showed that based on the ratio of bread quantity transported, the Nearest Neighbors Method can maximizes the vehicle carrying capacity. It carry up to 97.86% or 411 loaves of bread from a maximum capacity of 420 loaves. Based on mileage comparison, Bee Colonies algorithm produces a total mileage 87.1 km. This distance is 2.51 km more effective than the Nearest Neighbor Method.

Keywords: CVRP, distribution, Bee Colony Algorithm, Nearest Neighbour Method