Application of the Nearest Neighbor Algorithm to the Traveling Salesman Problem (TSP) for Determining the Shortest Food Delivery Route from a Restaurant to Multiple Customer Destinations

Abstrak

Penelitian ini bertujuan merancang dan mengimplementasikan sistem optimasi rute pengantaran makanan dari sebuah restoran menuju sejumlah titik tujuan pelanggan menggunakan algoritma Nearest Neighbor. Permasalahan pengantaran ke banyak titik ini dimodelkan sebagai Traveling Salesman Problem (TSP) dan diselesaikan melalui pendekatan kuantitatif berbasis simulasi dengan data dummy. Jarak antartitik dihitung menggunakan Haversine Formula dan disusun ke dalam matriks jarak, kemudian algoritma Nearest Neighbor diterapkan untuk menentukan urutan kunjungan dengan prinsip greedy, yaitu selalu memilih titik terdekat yang belum dikunjungi. Pengujian dilakukan pada dua klaster wilayah distribusi. Hasil penelitian menunjukkan bahwa algoritma Nearest Neighbor mampu menghasilkan rute dengan total jarak tempuh 12,05 km untuk Wilayah User 1 dan 11,50 km untuk Wilayah User 2 dengan kompleksitas waktu O(n²). Meskipun sifat greedy berpotensi menghasilkan solusi yang tidak optimal secara global, khususnya pada pemilihan titik-titik akhir, pendekatan ini terbukti cepat, sederhana, dan praktis. Dapat disimpulkan bahwa algoritma Nearest Neighbor layak dijadikan solusi awal optimasi rute layanan pengantaran makanan berskala lokal dengan jumlah titik terbatas (≤10 titik) yang membutuhkan perhitungan secara real-time.