Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Algoritme Particle Swarm Optimization

Abstract

Capacitated vehicle routing problem (CVRP) merupakan salah satu permasalahan pendistribusian yang memperhatikan kendala kapasitas kendaraan. Ada beberapa metode yang dapat digunakan untuk menyelesaikan permasalahan ini. Pada karya ilmiah ini, digunakan metode meta-heuristic Particle Swarm Optimization (PSO) dengan bantuan algoritme Sweep. Pada tahap pertama algoritme sweep digunakan untuk pembentukan grup dari sejumlah pelanggan berdasarkan urutan sudut polar setiap posisi pelanggan terhadap depot. Selanjutnya algoritme PSO digunakan dalam penentuan rute pendistribusian di setiap grup. Diawali dengan inisialisasi parameter yang digunakan. Kemudian membangkitkan kecepatan dan posisi awal secara acak. Tahap selanjutnya menghitung nilai fungsi tujuan serta yang terakhir menentukan P_best (posisi terbaik dari suatu partikel) dan G_best (posisi terbaik dari seluruh partikel). Aplikasi permasalahan CVRP pada karya ilmiah ialah penentuan rute pendistribusian roti dengan meminimumkan jarak tempuh.

Capacitated vehicle routing problem (CVRP) is one of the distribution problem that takes into account vehicle capacity constraints. There are several methods that can be used to solve this problem. In this research, the meta-heuristic Particle Swarm Optimization (PSO) method is used with Sweep algorithm. In the first step, the sweep algorithm is used to form a group from a number of customers based on the polar angle order of each customer position towards the depot. Furthermore, the PSO algorithm is used in determining of distribution routes in each other. Starting with the initialization of the parameter used. Then increase the speed and starting position randomly. Next stage is to calculate the objective function value and the last is measuring P_best (best position of a particle) and G_best (best position of all particles). The application of CVRP problems in this research is determining of route distribution of the bread by minimizing the mileage.