Penyelesaian Travelling Salesman Problem Menggunakan Algoritma Hill Climbing

Abstract

Peningkatan volume distribusi akibat pesatnya perkembangan sistem belanja daring memicu kebutuhan akan rute pengiriman barang yang lebih efisien untuk menekan biaya transportasi. Travelling Salesman Problem dibutuhkan dengan fokus permasalahan pada pencarian rute terpendek yang dapat mengurangi biaya distribusi. Penelitian ini bertujuan untuk menentukan rute Travelling Salesman Problem menggunakan algoritma Hill Climbing serta mengevaluasi kinerjanya dengan membandingkan waktu eksekusi dan total jarak yang diperoleh dengan metode eksak dalam bentuk Integer Linear Programming. Pada proses pencariannya, algoritma Hill Climbing memanfaatkan konsep neighbourhood dan neighbourhood yang digunakan pada penelitian ini yaitu 2-exchange neighbourhood dan insert neighbourhood. Berdasarkan hasil yang diperoleh, algoritma Hill Climbing menunjukkan kinerja yang lebih cepat dibandingkan dengan metode eksak untuk setiap kasus yang diuji. Pada kasus dengan jumlah node yang cukup banyak, Hill Climbing menghasilkan total jarak yang mendekati optimal atau mendekati hasil dari solusi eksak. Pada kasus dengan jumlah node yang lebih sedikit, algoritma Hill Climbing mampu menghasilkan total jarak yang sama dengan metode eksak.

The increase in distribution volume due to the rapid development of online shopping systems triggers the need for more efficient delivery routes to reduce transportation costs. Travelling Salesman Problem is needed with the focus of the problem to find the shortest route that can reduce the distribution cost. This research aims to determine the Travelling Salesman Problem route using the Hill Climbing algorithm and evaluate its performance by comparing the execution time and total distance with the exact method in the form of Integer Linear Programming. The Hill Climbing algorithm applies neighborhood concepts, with 2-exchange and insert neighborhoods used in this study. Based on the results obtained, the Hill Climbing algorithm shows faster performance than the exact method for each case tested. In the case of a large number of nodes, Hill Climbing produces a solution that is close to optimal or close to the result of the exact solution. In the case with a smaller number of nodes, the Hill Climbing algorithm is able to produce the same total distance as the exact method.