OPTIMALISASI RUTE DISTRIBUSI PENGANGKUTAN GAS LPG PT. X

PT. X is an LPG gas distributor in Magetan Regency. The demand for each base is predetermined and fixed. This company delivers LPG Gas from Monday - Saturday and in one day there are two delivery routes with two vehicles. Routes owned by PT. X in distributing LPG gas was less than optimal because there was delivery to two bases close to each other with two different vehicles. This causes the company's profits to be less than optimal. This research aims to determine the optimization of LPG gas distribution routes by PT. X. Method saving matrix used to determine temporary routes. This route will then be optimized using two methods, namely method Nearest Neighbor and methods Branch and Bound. The total distance from the company's initial route for a week was 554.5 km. Meanwhile, the results of route optimization using these two methods show the method branch and bound more optimal than the method nearest neighbor. Method branch and bound get a total distance in a week of 491.69 km, while the results of the method nearest neighbor in a week amounting to 538.99 km. From these results, it was found that the total distance during the week was reduced by 11.3% of the total distance from the company's initial route or 62.81 km. The reduction in distance also has an impact on reducing fuel costs from previously costing Rp628,431 a week to Rp557,247.

Key word : route, optimization, branch and bound, nearest neighbor, saving matrix