PENERAPAN ALGORITMA CHEAPEST INSERTION HEURISTIC DALAM RUTE DISTRIBUSI BANTUAN SOSIAL DI KABUPATEN PACITAN

Abstrak

The distribution of social assistance requires optimal route planning to enhance the efficiency of time, operational costs, and labor. This study aims to identify an efficient distribution route for social assistance to 12 districts in Pacitan Regency. This issue is modeled as a Traveling Salesman Problem (TSP) and addressed using the Cheapest Insertion Heuristic (CIH) algorithm. This heuristic method gradually inserts points into the route while considering the minimal increase in distance. The data used consists of a distance matrix between districts as distribution points. The implementation of the CIH algorithm yielded an optimal route with the sequence 1-5-11-7-13-12-3-6-2-10-4-9-8-1, resulting in a total travel distance of 188.75 kilometers. This result indicates that the CIH algorithm can produce an efficient distribution route and can serve as a practical alternative solution for the Social Services Department of Pacitan Regency in planning the optimal distribution of assistance.