OPTIMASI RUTE SILATURAHMI DENGAN PEMODELAN TRAVELING SALESMAN PROBLEM (TSP) MENGGUNAKAN ALGORITMA PEMROGRAMAN DINAMIK

Abstract

The problem of determining an efficient social visit route can be modeled as the Traveling Salesman Problem (TSP), which is a route optimization problem aimed at minimizing the total travel distance. This study aims to model and optimize a social visit route starting from Randudongkal to four destination villages, namely Mejagong, Moga, Warungpring, and Sikasur, by applying a deterministic dynamic programming algorithm. Distance data between locations were obtained from Google Maps and represented in the form of weighted distance matrix. The solution was carried out using backward recursion approach based on Bellman’s principle of optimality. The result show that the minimum total distance obtained is 29.200 meters, with two symmetric optimal routes, namely Randudongkal – Warungpring – Moga – Mejagong – Sikasur – Randudongkal and Randudongkal – Sikasur – Mejagong – Moga – Warungpring – Randudongkal. These results demonstrate the effectiveness of dynamic programming in producing exact solutions for small-scale TSP instances in a non-commercial context and provide a foundation for further research on route optimization problems with greater scale and complexity.
Keywords: Route Optimization, Social Visit Route, Traveling Salesman Problem (TSP), Dynamic Programming, Backward Recursion