Algoritma Heuristik untuk Vehicle Routing Problem dengan Tujuan Minmax

AULIYA NUR ASYIFA, Dr. Irwan Endrayanto A., S.Si., M.Sc.

2022 | Skripsi | S1 MATEMATIKA

Pada skripsi ini, dibahas Masalah Vehicle Routing Problem (VRP) dengan fungsi tujuan Minmax. Minmax-VRP adalah masalah penentuan rute untuk mendistribusikan sejumlah permintaan dari masing-masing pelanggan dengan memperhatikan kapasitas kendaraan dengan tujuan meminimalkan total waktu kedatangan kendaraan pada pelanggan yang dilayani. Masalah minmax VRP akan dimodelkan menggunakan program bilangan bulat dan akan diselesaikan menggunakan algoritma heuristik. Konsep algoritma heuristik yang diajukan menggunakan algoritma Cheapest Insertion dan Local Search. Dari hasil yang diperoleh, algoritma heuristik tersebut dapat menghasilkan solusi yang optimal dari masalah minmax-VRP, yaitu rute yang terbentuk memiliki jarak atau waktu tempuh minimum.

In this thesis, the Vehicle Routing Problem with Minmax Objective (MinmaxVRP) is studied. Minmax VRP is a problem of determining the route to distribute the demands for each customer according to vehicle capacity with the aim of minimize total latest time all customer receives service. Minmax-VRP will be modeled using integer programming and solved by the heuristic algorithm. The Cheapest Insertion algorithm and Local Search technique are proposed for the heuristic algorithm. The result shows that the heuristic algorithm can produce an optimal solution for minmax-VRP, that the route formed has a minimum distance or travel time.

Kata Kunci : vehicle routing problem, rute, heuristik, insertion