Algoritma Heuristik untuk Masalah Rute Kendaraan Berkapasitas Dua Tingkat
Intan Rahmawati, Dr. Indarsih, S.Si., M.Si.
2026 | Skripsi | MATEMATIKA
Masalah rute kendaraan berkapasitas dua tingkat atau biasa disebut 2E-CVRP merupakan pengembangan dari masalah rute kendaraan (VRP) yang menggunakan sistem distribusi dua tingkat, di mana pengiriman barang dari depot atau pabrik tidak dilakukan secara langsung ke pelanggan, melainkan melalui titik perantara yang disebut satelit. Pada tingkat pertama, barang dikirim dari depot ke satelit menggunakan kendaraan berkapasitas besar, kemudian pada tingkat kedua barang didistribusikan dari satelit ke pelanggan menggunakan kendaraan yang lebih kecil. Permasalahan ini bertujuan untuk menentukan rute distribusi yang optimal dengan memperhatikan kapasitas kendaraan pada setiap tingkat serta alokasi pelanggan ke satelit. Karena tingkat kompleksitas permasalahan 2E-CVRP yang tinggi, digunakan pendekatan algoritma heuristik untuk memperoleh solusi yang efisien. Digunakan kombinasi algoritma Cheapest Insertion sebagai metode pembentukan solusi awal dan Local Search sebagai metode perbaikan solusi. Hasil yang diperoleh menunjukkan bahwa algoritma heuristik tersebut mampu menghasilkan rute distribusi yang efisien dengan total jarak tempuh yang lebih minimum serta tetap memenuhi seluruh kendala kapasitas dan permintaan pelanggan.
Two-Echelon Capacitated Vehicle Routing Problem (2E-CVRP) is an extension of the Vehicle Routing Problem (VRP) that applies a two-level distribution system, where the delivery of goods from a depot or factory is not performed directly to customers, but through intermediate facilities called satellites. At the first level, goods are transported from the depot to satellites using high-capacity vehicles, and at the second level, they are distributed from satellites to customers using smaller vehicles. This problem aims to determine optimal distribution routes while considering vehicle capacity constraints at each level and the allocation of customers to satellites. Due to the high complexity of the 2E-CVRP, a heuristic algorithm approach is employed to obtain efficient solutions. A combination of the Cheapest Insertion algorithm is used to construct the initial solution, and the Local Search algorithm is applied to improve the solution. The results show that the proposed heuristic approach is able to generate efficient distribution routes with reduced total travel distance while satisfying all capacity constraints and customer demands.
Kata Kunci : 2E-CVRP, algoritma heuristik, Cheapest Insertion, Local Search, rute distribusi, masalah rute kendaraan berkapasitas dua tingkat