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.
Keywords
Full Text:
PDFReferences
Anggasari F, M. F. (2017). Optimasi kebutuhan gizi untuk balita menggunakan hybrid algoritma genetika dan simulated annealing. Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer, 1(12), 1668-1677.
Josi, A. (2017). Implementasi algoritma genetika pada aplikasi penjadwalan perkuliahan berbasis web dengan mengadopsi model waterfall. Jurnal Informatika: Jurnal Pengembangan IT, 2(2), 77-83.
Li, X. G., & Wei, X. (2008). An improved genetic algorithm-simulated annealing hybrid algorithm for the optimization of multiple reservoirs. Water Resources Management, 22, 1031-1049.
Permana, E. R., Midyanti, D. M., & Hidayati, R. (2020). Optimasi pencarian rute terpendek distribusi barang menggunakan metode simulated annealing (Studi kasus: PD Bumi Jaya Indah Kota Pontianak). Coding Jurnal Komputer dan Aplikasi, 8(3), 9-18.
Rahmi, A., Mahmudy, W. F., & Anam, S. (2017). Hibridisasi algoritma genetika dengan Variable Neighborhood Search (VNS) pada optimasi biaya distribusi. Jurnal Teknologi Informasi dan Ilmu Komputer, 4(2), 87-96.
Samana, E., Prihandono, B., & Noviani, E. (2015). Aplikasi simulated annealing untuk menyelesaikan travelling salesman problem. Bimaster: Buletin Ilmiah Matematika, Statistika dan Terapannya, 4(1), 25-32.
Shahab, M. L., & Irawan, M. I. (2016). Algoritma genetika ganda untuk capacitated vehicle routing problem. Jurnal Sains dan Seni ITS, 4(2), A19-A24.
Tamilarasi, A., & Kumar, T. A. (2010). An enhanced genetic algorithm with simulated annealing for job-shop scheduling. International Journal of Engineering, Science and Technology, 2(1), 144-151.
Wirdianto, E. et al. (2007). Penerapan algoritma simulated annealing pada penjadwalan distribusi produk. Optimasi Sistem Industri, 7(1), 7–20.
DOI: https://doi.org/10.17509/jem.v9i2.40080
Refbacks
- There are currently no refbacks.
Copyright (c) 2021 Jurnal EurekaMatika
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.