Penyelesaian Capacitated Vehicle Routing Problem dengan Menggunakan Gabungan Algoritma Genetika dan Simulated Annealing

Abstract

The capacitated vehicle routing problem (CVRP) is a problem of distributing a number of goods using vehicles with limited carrying capacity that needed to pick up or deliver items at various locations, such as round trips from a store to customers. The goal of CVRP is to obtain a route with shortest travel distance. This research proposed the combination of genetics algorithm with simulated annealing (GASA) to solve CVRP. The first step in GASA is to represent customer as chromosomes, calculate fitness values, selection, crossover, and mutation. After that we continue to optimize the problem using SA algorithm by modifying the best solution produced by GA algorithm, comparing the fitness of modified best solution with the best solution of GA, and return to GA algorithm until maximum iteration achieved. Thus, GASA has greater chance to obtain global optimal solution. To simulate the algorithm, GASA was used for CVRP of an ice cream company in Bandung City and was able to solve it well.

Keywords: Capacitated Vehicle Routing Problem (CVRP), Genetic Algorithm (GA), Optimization, Simulated Annealing (SA).

Abstrak

Capacitated Vehicle Routing Problem (CVRP) adalah permasalahan pendistribusian sejumlah barang oleh kendaraan yang tersedia dengan kapasitas tertentu dari suatu depot ke sejumlah pelanggan lalu kembali ke depot. Tujuan penyelesaian CVRP adalah untuk menentukan rute pendistribusian dengan total jarak terpendek. Pada penelitian ini, digunakan gabungan algoritma genetika dan simulated annealing (GASA) untuk menyelesaikan permasalahan CVRP. Algoritma GASA bekerja dengan cara melakukan tahapan-tahapan pada Algoritma GA yaitu merepresentasikan kromosom, menghitung nilai fitness, seleksi, crossover, dan mutasi, kemudian dilanjutkan ke tahapan-tahapan Algoritma SA yaitu memodifikasi solusi terbaik yang diperoleh dari Algoritma GA sebelumnya, membandingkan nilai fitness solusi hasil modifikasi dengan solusi terbaik pada Algoritma GA, setelah itu melakukan kembali tahapan-tahapan Algoritma GA sampai iterasi maksimum tercapai. Dengan demikian gabungan GA dan SA mempunyai peluang besar untuk memberikan solusi optimal global. Hasil implementasi model CVRP dan Algoritma GASA pada masalah pendistribusian es krim suatu perusahaan di Kota Bandung diperoleh kesimpulan bahwa Algoritma GASA dapat menyelesaikan masalah tersebut dengan baik.