Perbandingan Cheapest Insertion Heuristic dan Algoritma Christofides untuk Menentukan Tour Pasar Tradisional di Kota Bandar Lampung

The Traveling Salesman Problem is a problem to determine the cheapest cost for a salesman staring from original location to all destination on his objective and return to the original location. In this study, a comparison of the Cheapest Insertion Heuristic and the Christofides Algorithm will be carried out to determine the traditional market tour in Bandar Lampung. The results obtained show that the solution obtained manually using the Cheapest Insertion Heuristic and the Christofides Algorithm produce the same solution, which is 216 minutes, while using Python programming, the Cheapest Insertion Heuristic provides a solution in 217 minutes and using the Christofides Algorithm in 226 minutes. However, because the solution obtained manually or by programming still produces intersections in the tour, to get better solution, the tour may be revised/repaired by removing the intersections. After repairing the tour, the same solution is obtained, whether using the Cheapest Insertion Heuristic or the Christofides Algorithm, which is 216 minutes.