OPTIMIZATION OF GOODS DISTRIBUTION ROUTE ASSISTED BY GOOGLE MAP WITH CHEAPEST INSERTION HEURISTIC ALGORITHM (CIH)

Abstract

In the distribution of goods, the efficiency of goods delivery one of which was determined by the path that passed to deliver the goods. The problem of choosing the shortest route was known as the Traveling Salesman Problem (TSP). To solve the problem of choosing the shortest route in the distribution of goods, the algorithm to be used was Cheapest Insertion Heuristic (CIH). This study aims to determine the minimum distance traveled by using the CIH algorithm. Researchers determine the route and distance of each place visited by using google map. The concept in the CIH algorithm was to insert an unexpired city with an additional minimum distance until all cities are passed to get the solution of the problem. The step completion problem with CIH algorithm was: 1) search, 2) making sub tour; 3) change the direction of the relationship, 4) repeat the steps so that all places are included in the sub tour. Theoretically, the total distance calculated using the CIH algorithm is 20.2 km, while the total distance calculated previously traveled with the ordered route is 25.2 km. There was a difference of 5 km with the application of CIH algorithm. The difference between the distance certainly has an impact on the optimal distribution of goods to the destination. Therefore, CIH algorithm application can provide a solution for determining the shortest route from the distribution of goods delivery.

Keywords

• Optimization
• Route
• Sub tour: Algorithm
• Graph