ANALISIS PENERAPAN METODE SIMULATED ANNAELING DAN GENETIC ALGORITHM PADA KASUS VRP PENENTUAN RUTE DISTRIBUSI TOKO RITEL

ARDIRANI RENSYTA, Anna Maria Sri Asih, S.T., M.M., M.Sc., Ph.D.

2015 | Skripsi | S1 TEKNIK INDUSTRI

Peningkatan permintaan akan barang kebutuhan masyarakat, peningkatan jumlah gerai toko ritel, serta adanya tantangan proses distribusi terhadap industri ritel akan mempengaruhi jaringan city logistic di Indonesia. Penelitian ini termasuk dalam penelitian besar city logistic Yogyakarta, dimana secara khusus Peneliti mencoba menganalisis bagaimana penentuan rute optimal pada permasalahan Vehicle Routing Problem (VRP) kendaraan distribusi toko ritel untuk komoditas beras, minyak goreng, dan gula pasir di Kota Yogyakarta dan sekitarnya sehingga pemecahan kasus VRP ini dapat diterapkan didalam suatu sistem city logistic. Rute dikatakan optimal apabila rute telah mengoptimalkan faktor waktu tempuh dan kapasitas kendaraan pengantar. Penelitian ini menggunakan metode metaheuristik Simulated Annealing (SA) dan metode Genetic Algorithm (GA) sebagai metode pembanding, dengan data set toko ritel Yogyakarta yang berlingkup pada kota Yogyakarta sampai Kecamatan Delanggu. Tahapan penelitian yaitu studi literatur, pengumpulan data, pemetaan koordinat dan pembuatan matriks waktu data, lalu pembangunan model SA dan GA menggunakan Matlab, serta verifikasi dengan membandingkan hasil SA dan GA dengan hasil metode eksak. Penentuan parameter SA dan GA dilakukan dengan Design Of Experiment (DOE). Rute optimal diperoleh dengan menjalankan model SA dengan parameter yang sudah didapatkan. Rute optimal lalu dipetakan pada peta menggunakan Google Maps. Hasil metode SA dibandingkan dengan metode GA dari faktor waktu tempuh rute optimal yang dihasilkan serta waktu komputasi yang dibutuhkan model untuk mencapai rute optimal kedua data dibandingkan menggunakan uji hipotesis t-test. Metode SA tidak menghasilkan perbedaan yang signifikan dengan metode GA dari sisi waktu tempuh rute optimal yang dihasilkan. Kemampuan metode SA untuk keluar dari solusi optimum lokal tidak membuat metode SA menghasilkan waktu tempuh yang lebih baik secara signifikan. Pada sisi tahapan dan pseudo-code, metode SA memiliki algoritma metropolis didalam iterasi SA dan 3 tipe transformasi. Pseudo-code GA memiliki tahapan mutasi dan kawin silang yang langsung berada pada tahapan dasar metode tersebut sehingga metode ini memiliki pseudo-code yang lebih sederhana. Ketika dilihat dari sisi waktu komputasi masing – masing metode, uji hipotesis t-test menunjukkan bahwa metode SA memiliki waktu komputasi yang berbeda secara signifikan dibandingkan dengan metode GA.

The increasing of demand and number of retail stores coupled with the challenges of distribution process in retail industries give several impacts to city logistic network in Indonesia. This research is included in the research of Yogyakarta city logistic system, which particularly analysing how the optimal distribution routes of vehicle routing problem (VRP) for basic commodities (oil, rice, and sugar) are in Yogyakarta city and its surrounding. Optimal routes are defined on the optimization of time and vehicle capacity. Metaheuristik Simulated Annealing (SA) method will be used in this research, and the Genetic Algorithm (GA) method as a comparation method, with data set of Yogyakarta which is included retail stores data in Yogyakarta until Delanggu regency. Several procedures of the research are literature review, data gathering, coordinats plotting and time matrix initiation, building SA and GA method pseudeo-codes using Matlab, and verification by approaching to exact method. Parameters of SA and GA are determined using Design of Experiment (DOE) method. Optimal distribution routes are figured by running the SA pseudo-code model with the parameters defined. The Procedures of SA consists of initial route initiation, defining initial temperature and cooling rate. Initial route will be transformed using one of 3 transformation types, and will defines its energy. Wether the energy will be accepted or not will be dependending on the metropolis criterion. After 100 iterations, process will be repeated until 10.000 iterations. This process is replicated 20 times and the best energy will be taken as the result. Both methods will be analysed on the aspect of time per route and computation time using the t-test hypothesis test. SA methods does not give result of time per route with significant difference compared to GA methods. The ability of SA method to jump off from the local optima solution does not make the method producing significantly better solution. On the side of stepsand pseudocodes, SA methods has the metropolis algorithm inside the SA iterations and 3 types of trasnformations which has to be done. GA’s pseudo-codes has mutation and crossover step which are basically inside the general method of GA itself, making the method has a more simple pseudo-code than SA. When we look at the computation time of both methods, the t-test hypothesis test shows that SA methods has a compotation time with a significant difference from GA methods.

Kata Kunci : VRP, Rute Optimal, Bahan Pokok, Toko Ritel, Genetic Algortihm, Simulated Annealing