Algoritma Simulated Annealing untuk Menentukan Rute Kendaraan Heterogen (Studi Kasus)

Abstrak

Permasalahan transportasi dalam supply chain management sangat penting untuk dikaji karena dapat menimbulkan biaya logistik yang sangat besar. Salah satu cara untuk mengurangi biaya transportasi adalah dengan penentuan rute kendaraan atau dikenal dengan istilah vehicle routing problem. Objek yang menjadi kajian merupakan perusahaan yang bergerak pada bidang distribusi produk untuk area kota Banda Aceh dan sekitarnya. Dalam proses distribusi, perusahaan ini menggunakan dua jenis kendaraan dengan kapasitas dan biaya operasional yang berbeda sehingga permasalahan menjadi heterogeneous fleet vehicle routing problem. Penentuan rute kendaraan dalam penelitian ini dilakukan dengan tiga metode, yaitu metode analitik, algoritma insertion heuristic sebagai metode heuristik, dan algoritma simulated annealing sebagai metode metaheuristik. Berdasarkan hasil yang diperoleh dari data ujicoba, algoritma simulated annealing merupakan algoritma yang paling baik dalam menyelesaikan permasalahan. Secara rata-rata, algoritma simulated annealing dapat menghasilkan kualitas solusi yang sama dengan metode analitik, namun dengan waktu komputasi yang lebih singkat. Selain itu, algoritma simulated annealing menghasilkan kualitas solusi yang lebih baik dibandingkan algoritma insertion heuristic yang dikembangkan dalam penelitian dan dapat meningkatkkan kualitas solusi sebesar 20,18% dari penelitian sebelumnya dengan waktu komputasi 19,27 detik.

Abstract

Transportation problems in supply chain are very important to be discussed because they can raises enormous logistic cost. Route determination of the vehicles known as vehicle routing problem is the one of ways to reduce transportation cost. The object discussed in this study is the distribution company for Banda Aceh city and its surroundings. The company uses two types of vehicle to distribute the product for customers. The differences each vehicle are vehicle capacity and operational cost. To cover these differences, the problem becomes heterogenous fleet vehicle routing problem. The study uses three methods to solve the problem. Analitycal method, insertion heuristic algorithm as heuristic method and simulated annealing algorithm as metaheuristic method are the methods used. According to the results, simulated anneling algorithm produces the better solutions than two others. On average, solutions produced by simulated annealing algorithm from dataset have same quality with analitycal method, but with faster computation. Furthermore, simulated anneling algorithm produces better quality of solutions than insertion heuristic algorithm both from this study and previous study. The solution improves 20,18% with computation time 19,27 seconds.