PERBANDINGAN METODE SIMULATED ANNEALING DENGAN GENETIC ALGORITHM PADA VEHICLE ROUTING PROBLEM UNTUK PENENTUAN RUTE DISTRIBUSI BAHAN POKOK

NANDA PRATAMA PUTRA, Anna Maria Sri Asih, S.T., M.M., M.Sc., Ph.D.

2015 | Skripsi | S1 TEKNIK INDUSTRI

Vehicle Routing Problem (VRP) merupakan salah satu topik yang cukup menarik untuk diselesaikan. Salah satu implementasi untuk menyelesaikan kasus VRP adalah dengan penentuan rute optimal. Penentuan rute optimal bertujuan untuk meminimalkan biaya berdasarkan minimasi total waktu tempuh kendaraan yang melakukan proses distribusi. Terdapat beberapa metode untuk menyelesaikan kasus VRP salah satunya dengan menggunakan metode metaheuristik Simulated Annealing (SA) dan Genetic Algorithm (GA). Pada penelitian kali ini, peneliti ingin membandingkan performansi dari metode metaheuristik SA dan GA untuk menyelesaikan kasus VRP penentuan rute optimal untuk produk bahan pokok yaitu beras, gula pasir, dan minyak goreng. Penelitian ini menggunakan data set wilayah Yogyakarta dan sekitarnya. Rute dikatakan optimal apabila rute telah mengoptimalkan faktor waktu tempuh dan kapasitas kendaraan. Tahapan penelitian yaitu studi literatur, pengumpulan data, pemetaan koordinat dan pembuatan matriks waktu tempuh, modifikasi model SA dan GA menggunakan Matlab, verifikasi dengan membandingkan hasil SA, GA dan saving heuristic method, validasi model dengan hasil metode eksak. Penentuan parameter SA dan GA dilakukan dengan Design Of Experiment (DOE). Rute optimal diperoleh dengan menjalankan model SA dan GA dengan parameter yang sudah didapatkan. Rute optimal lalu dipetakan pada peta menggunakan Google Maps. Hasil metode SA dan GA untuk menyelesaikan kasus ini kemudian dibandingkan menggunakan uji hipotesis t-test dengan mempertimbangkan faktor waktu tempuh rute optimal yang dihasilkan, waktu komputasi yang dibutuhkan model untuk mencapai rute optimal dan jumlah kendaraan yang dihasilkan oleh kedua metode tersebut. Pada kasus ini, metode SA tidak menghasilkan perbedaan yang signifikan dibandingkan dengan menggunakan metode GA jika dilihat dari faktor waktu tempuh rute optimal dan juga faktor jumlah kendaraan yang dihasilkan. Dilihat dari faktor hasil waktu komputasi rute optimal yang dihasilkan, pada penelitian VRP ini menunjukkan metode SA berbeda signifikan dari hasil yang diperoleh dengan menggunakan metode GA. Selain itu, metode SA lebih efisien dibandingkan dengan metode GA untuk stopping criteria nilai optimal yang muncul sebanyak 10000 kali berturut-turut karena waktu komputasi yang lebih cepat dibandingkan GA.

Vehicle Routing Problem (VRP) is one of the most interesting topic to be discussed. One of the implementation to do the case of VRP is by determining the optimal route. The purpose of determining the optimal route is to have the distribution process. There are several methods for doing the VRP, such as metaheuristic’s method which includes Simulated Annealing (SA) and Genetic Algorithm (GA). In this research, the researcher would like to compare the performance of the metaheuristic’s method of SA and GA in the case of VRP for determining the optimal route of three staple products, which are rice, sugar, and cooking oil. The data will be taken in the region of Yogyakarta. The route is considered to be optimal if the route have optimized the time travel and the capacity of vehicle. There are seven steps to do this research, which are literature review, data collection, mapping coordinates and preparation of matrix time travel, the modification of SA and GA method by using Matlab software, verification of the comparison method of SA, GA, and saving heuristic method, and validate the model with the result of the model. Design of Experiment (DOE) is used to determine the SA and GA parameter. Optimal route is obtained by executing the SA and GA model with the parameter that already existed. Then, the optimal route will be mapped by using Google Maps. The result of using the SA and GA method will be compared by using the t-test hypothesis to consider the time travel factor, the computation of time to obtain route optimal and number of vehicles. In this case, SA method doesn’t give a significant result compared to GA method by considering the factor of time travel and number of vehicles. Although, by considering the computation time of route optimal, it shows that SA method give a significant result compared to GA method. Other than that, SA method is considered to be more efficient compared to GA method for stopping criteria optimal value that appears 10000 times in a row due to how fast the time computation is compare to GA method.

Kata Kunci : VRP, Rute Disribusi Optimal, Bahan Pokok, Genetic Algorithm, Simulated Annealing