Multi-Depot Vehicle Routing with Heterogeneous Vehicles using Nearest Neighbor Combined with Simulated Annealing - Debby Agustine; Janson Naiborhu; Ikha Magdalena (Department of Mathematics, Faculty of Sciences and Technology, UIN Syarif Hidayatullah, 2025)
The Vehicle Routing Problem (VRP) is an essential component of contemporary logistics, which becomes more complex as the Multi-Depot Vehicle Routing Problem (MDVRP) and the Multi-Depot Vehicle Routing Problem with a Heterogeneous Fleet (MDVRPHF). The main objective of MDVRPHF is to meet all customer demands while minimizing total distribution costs by using vehicles with varying capacities. This paper proposes a metaheuristic framework that first uses the Nearest Neighbor (NN) algorithm to build initial routes and then employs the Simulated Annealing (SA) algorithm to optimize the arrangement of goods within each vehicle, ensuring capacity limits are met. Computational experiments using real-world inspired data, representing 20 items distributed from a Bandung depot to multiple customers with three heterogeneous vehicle types, showed that the proposed hybrid NN–SA method achieved an 18.4% reduction in total distribution cost compared to the NN method alone. These results indicate that this integrated approach offers a practical, computationally efficient solution to the complexities of MDVRPHF, establishing it as a useful tool for logistics planning. Keywords: Multi-Depot Vehicle Routing Problem; Heterogeneous Fleet; Nearest Neighbor; Simulated Annealing; Metaheuristics. Abstrak Vehicle Routing Problem (VRP) merupakan bagian penting dari logistik kontemporer, yang kompleksitasnya meningkat menjadi Multi-Depot Vehicle Routing Problem (MDVRP) dan Multi-Depot Vehicle Routing Problem with a Heterogeneous Fleet (MDVRPHF). Untuk MDVRPHF, tujuan utamanya adalah memenuhi seluruh permintaan pelanggan sambil meminimalkan biaya distribusi total dengan memanfaatkan kendaraan berkapasitas berbeda. Makalah ini mengusulkan kerangka kerja metaheuristik yang pertama-tama menggunakan algoritma Nearest Neighbor (NN) untuk membentuk rute awal, kemudian algoritma Simulated Annealing (SA) digunakan untuk mengoptimalkan penataan barang di setiap kendaraan agar batas kapasitas terpenuhi. Eksperimen komputasi menggunakan data uji berbasis kondisi nyata yang merepresentasikan distribusi 20 item dari satu depot di Bandung ke beberapa pelanggan dengan tiga jenis kendaraan heterogen. Hasil penelitian menunjukkan bahwa metode hibrida NN–SA ini menghasilkan penurunan biaya distribusi total sebesar 18,4% dibandingkan metode NN murni, yang menunjukkan bahwa pendekatan terpadu ini memberikan solusi praktis dan efisien secara komputasi untuk kompleksitas MDVRPHF. Kata Kunci: Multi-Depot Vehicle Routing Problem; Armada Heterogen; Nearest Neighbor; Simulated Annealing; Metaheuristik. 2020MSC: 90B06, 90C59.