ABSTRAKSI: Pencarian rute yang optimal merupakan salah satu permasalahan yang sering muncul dalam kehidupan. Salah satu contoh kasus pencarian rute adalah pengiriman barang, dimana perusahaan harus mengirimkan barang ke sejumlah tempat dengan biaya yang seminimum mungkin. Masalah pengiriman barang ini termasuk kedalam Capacitated Vehicle Routing Problem with Time Windows, dimana terdapat sejumlah kendaraan dengan kapasitas sama yang harus mengirimkan barang ke sejumlah node sesuai dengan permintaan pelanggan dengan batasan waktu antar di tiap nodenya.
Rute yang optimal adalah memiliki total jarak yang singkat. Untuk mencari rute optimal dalam CVRPTW, digunakan penggabungan dari Differential Evolution dan Algoritma Genetika dalam penyelesaiannya. Algoritma genetika memiliki kelebihan dalam menyelesaikan masalah kombinatorial dengan crossover dan mutasinya, sedangkan DE memiliki kelebihan dalam proses mutasinya yang bersifat searah. Dengan menggabungkan kelebihan algoritma ini, diharapkan solusi yang mendekati optimal dapat tercapai.
Pengujian yang dilakukan adalah mencari parameter terbaik untuk mendapatkan solusi yang paling mendekati optimal. Pc dan Pm, CRmin, dan CRmax berpengaruh dalam menghasilkan solusi yang mendekati optimal, sedangkan nilai F tidak terlalu berpengaruh pada solusi yang dihasilkan. Selain pencarian parameter, akurasi penggabungan DE dan AG dapat dilihat dari perbandingan metode ini dengan Improved Ant Colony System- Simulated Annealing (IACS-SA) dan Harmony Search (HS). Dari hasil perbandingan, DE dan AG menghasilkan jarak tempuh yang paling panjang meskipun hasilnya tidak berbeda jauh dengan Harmony Search.Kata Kunci : pencarian rute optimal, CVRPTW, Differential Evolution, Algoritma Genetika.pencarian rute optimal, CVRPTW, Differential Evolution, Algoritma Genetika.ABSTRACT: Optimal route searching is one of the problems that commonly occurred in our life. One of the route searching cases is delivering some goods to some places with minimum cost. This delivery problem belongs to Capacitated Vehicle Routing Problem with Time Windows where there are a number of vehicles having same capacities which has to deliver some goods to a number of nodes in accordance with customer requests with time constraints between each node.
Optimal route has short total distance. To find an optimal route in CVRPTW, we can use the combination of of Differential Evolution and Genetic Algorithm as solving solution. Genetic Algorithm has some advantages in solving combinatorial problem with its crossover and mutation, while DE has some advantages in its direct mutation. By combining these advantages of these two algorithms, optimal solution is hoped to be gained.
Testing was done to get best parameters in order to yield nearly optimal solution. Pc, Pm, CRmin, and CRmax are significantly yielding nearly optimal solution, while F is not too significantly involved to the solution. Besides parameters’ searching, its accuration could be seen from the comparison between combination of DE and GA to another two methods, Improved Ant Colony System- Simulated Annealing (IACS-SA) and Harmony Search (HS). From these comparison methods, the combination of DE and GA has the most total distance although its solutions are not too different from Harmony Search.Keyword: optimal route searching, CVRPTW, Differential Evolution, Genetic Algorithm.