PENENTUAN RUTE DISTRIBUSI BARANG DALAM VEHICLE ROUTING PROBLEM DENGAN KOMBINASI SIMULATED ANNEALING DAN ALGORITMA GENETIKA

SYAMSUL ARIFIN, Dr. Azhari SN., MT dan Anny Kartikasari.,S.Si., M.Sc., Ph.D

2016 | Tesis | S2 Ilmu Komputer

Vehicle Routing Problem (VRP) adalah salah satu pemodelan dalam distribusi dan transportasi, capacitated vehicle routing problem (Capacitated VRP) merupakan pemodelan distribusi dan transportasi yang mempertimbangkan kapasitas muatan kendaraan yang digunakan. Pemilihan rute yang tepat merupakan salah satu faktor penting yang harus dikuasai oleh pihak yang terkait dalam jaringan distribusi dan transportasi. Pemilihan rute yang tepat tentunya dapat meminimalkan biaya yang ditimbulkan yang juga mempertimbangkan kapasitas muatan kendaraan yang digunakan. Berdasarkan kebutuhan tersebut, semakin banyak metode yang dikembangkan untuk dapat menyelesaikan permasalahan capacitated VRP secara optimal sehingga biaya yang dikeluarkan menjadi lebih efisien, diantaranya Simulated Annealing (SA) dan Genetic Algorithm (GA). GA cenderung terjebak dalam local optima / premature convergence, Sedangkan SA mampu terhindar dari lokal optima akan tetapi SA memerlukan waktu proses yang panjang karena SA bersifat sekuensial. Penggabungan SA dan GA (SAGA) diharapkan dapat meningkatkan kualitas solusi dan mengurangi waktu eksekusi. Hasil pengujian dengan menggunakan beberapa dataset Capacitated VRP yang ada, menunjukkan bahwa kombinasi SAGA menghasilkan nilai objektif yang relative sama dengan GA dan meningkat 0.57 % dibandingkan SA, dan waktu yang dibutuhkan SAGA lebih cepat 0.97 % dan 26.26% dibandingkan GA dan SA.

Vehicle Routing Problem (VRP) is one of distribution and transportation modeling, capacitated vehicle routing problem (VRP Capacitated) is the distribution and transportation modeling that considers a payload capacity of the vehicle used. Selection of the proper path is one of the important factors that must be controlled by the parties involved in the distribution and transportation networks. Selection of the right path can certainly minimize the costs incurred and also considering vehicle payload capacity used. Based on these needs, more methods are being developed to solve the problems of capacitated VRP optimally in order to minimize the cost, including Simulated Annealing (SA) and Genetic Algorithm (GA). GA tends to get stuck in local optima / premature convergence, while SA is able to avoid local optima thought it takes a long process because it is sequential. The incorporation of SA and GA (SAGA) is expected to improve the quality of the solution and reduce the execution time. The test results by using multiple datasets Capacitated VRP available, indicates that the SAGA combination produces the same objective value relative to GA and increace 057%, when compared with SA, end the execution time SAGA more faster 0.97% and 26.26% compared GA and SA.

Kata Kunci : Capacitated VRP, Simulated Annealing, Genetic Algorithm