Implementasi Algoritma Cheapest Insertion Heuristic dalam Mobile App untuk Menentukan Rencana Perjalanan Kurir Barang

Abstract

The problem of determining the shortest route known as TSP (Traveling Salesman Problem) is a classic problem categorized as a hard combinatorial problem. This problem aims to visit a number of cities starting from one city to another with exactly one visit and return to the departure location. This research aims to obtain the shortest route of a goods courier travel route. So that it will further streamline the route traveled by couriers armed only with instinct. The system is built with a mobile application using the Google Maps API service as a map visualization. The Google Maps API offers many services that are partly used in the application, one of which is to obtain distance data between locations. The data obtained is processed to obtain a more optimal route using the CIH (Cheapest Insertion Heuristic) algorithm. The results of system trials show a decrease in distance from 14684 meters and 42017 meters to 12345 meters and 35968 meters with routes 1→3→5→4→2→1 and 1→6→4→5→7→3→10→8 →9→2→1 respectively. This algorithm is also tested to obtain a time complexity curve or big O. So that the results of the time complexity curve can be used as a comparison with algorithms that have similar functions.