PENENTUAN RUTE OPTIMAL PADA DISTRIBUSI TABUNG GAS LPG 3 KG DI WILAYAH SLEMAN (STUDI KASUS DI PT SUHADI JAYA ABADI)

Distribution is an important for the company. It aims to deliver the product on time and in the right quantity according to customer orders. In its implementation, distribution needs to be carried out optimally by the company where the route taken must pay attention to the distance factor, the allocation of the amount of capacity, and the required cost. PT Suhadi Jaya Abadi is a company that provides 3 kg LPG located in Prambanan, Yogyakarta. This company delivers LPG to all station in the Sleman area with four vehicles. Based on interviews and observations, the capacity of the vehicle used has not been utilized optimally and in determining the route taken by each vehicle is only based on the driver's intuition and does not considering the distance, cost, and vehicle capacity factors so that it does not guarantee that the route is optimal. Therefore, mathematical calculations are needed to determine the optimal route that can be applied by the company using the nearest neighbor and tabu search method. The nearest neighbor method in this research is used to determine the initial solution in the form of grouping the route with the shortest distance based on capacity, while the tabu search method is used to optimize the route in the previous stage by moving each node in one route so as to produce the optimal route with the shortest distance. Based on processing using the MATLAB application, the tabu search method produces a total mileage of 1,320.5 km with a savings of 16% compared to the company route. The total cost required for the tabu search method requires a cost of Rp.971,511 and saves Rp.182,531 or 16% compared to route costs. The results are expected to be applicable and helpful companies to improve their performance in the distribution of LPG to customers