Penyelesaian Travelling Salesman Problem (TSP) di CV. Telaga Mulya dengan Nearest Neighbor Algorithm dan Branch and Bound Algorithm

HAFIYYAN NAUFAL, Dr. Kuncoro Harto Widodo, S.T.P., M.Eng.; Dr. Ir. Dyah Ismoyowati, M.Sc.

2022 | Skripsi | S1 TEKNOLOGI INDUSTRI PERTANIAN

CV. Telaga Mulya merupakan produsen Air Minum dalam Kemasan (AMDK) mineral lokal yang mendistribusikan produknya secara langsung tanpa bantuan pihak ketiga kepada pelanggannya yang terletak di Daerah Istimewa Yogyakarta. Kegiatan distribusi CV. Telaga Mulya menghabiskan biaya kurang lebih sebesar Rp2.400.000-, tiap minggu untuk membeli Bahan Bakar Minyak (BBM) bagi seluruh armada truk. Agar dapat bersaing, perusahaan perlu mengoptimalkan biaya transportasi sebagai kontributor terbesar dalam pengeluaran logistik. Biaya BBM dapat dikurangi dengan mengurangi jarak tempuh dari kegiatan distribusi armada truk tanpa mempertimbangkan kondisi lalu lintas. Rute kegiatan distriusi yang ditentukan secara subjektif oleh masing-masing sopir memungkinkan digunakannya rute yang tidak optimal, sehingga terjadi pemborosan BBM. Permasalahan ini termasuk ke dalam Travelling Salesman Problem (TSP) yang dapat diselesaikan dengan Nearest Neighbor Algorithm sebagai algoritma heuristik dan Branch and Bound Algorithm sebagai algoritma eksak. Penyelesaian dilakukan dengan bantuan software WinQSB. Kegiatan distribusi armada Kota Yogyakarta di hari Selasa dan Kamis sudah memberlakukan rute kegiatan distribusi optimal dengan jarak tempuh masing-masing sebesar 53,96 km dan 67,45. Pada kedua kegiatan distribusi tersebut, Nearest Neighbor Algorithm juga menghasilkan solusi optimal. Pada kegiatan distribusi armada Kota Yogyakarta di hari Senin, rute kegiatan distribusi existing menghasilkan jarak tempuh sebesar 75,63 km. Nearest Neighbor Algorithm juga menghasilkan jarak tempuh sebesar 75,63 km. Keduanya belum mencapai solusi optimal karena dengan Branch and Bound Algorithm dihasilkan jarak tempuh sebesar 65,12 km atau didapat penghematan sebesar 13,89%.

CV. Telaga Mulya is a local mineral bottled water producer that distributes it’s products directly without third party assistance to it’s customers located in the Special Region of Yogyakarta. CV. Telaga Mulya’s distribution activity costs approximately IDR 2,400,000 every week to purchase fuel for the entire truck fleets. In order to be competitive, company need to optimize transportation cost as the largest contributor to logistics expenditure. Fuel cost can be reduced by reducing the mileage from the distribution activities of the truck fleets without considering traffic condition. The routes of distribution activities that is determined subjectively by each driver allows the use of routes that are not optimal, resulting in wastage of fuel. This problem is included in the Travelling Salesman Problem (TSP) which can be solved using the Nearest Neighbor Algorithm as a heuristic algorithm and Branch and Bound Algorithm as an exact algorithm. The solution was done with the help of WinQSB software. The distribution activities of the Yogyakarta City fleet on Tuesday and Thursday have implemented optimal distribution activity routes with mileage of 53.96 km and 67.45 km, respectively. In both distribution activities, the Nearest Neighbor Algorithm also produces optimal solutions. In the Yogyakarta City fleet distribution activity on Monday, the existing distribution route resulted in mileage of 75.63 km. Nearest Neighbor Algorithm also produces a mileage of 75.63 km. Both have not reached the optimal solution because with the Branch and Bound Algorithm, the mileage is 65.12 km or a savings of 13.89% was obtained.

Kata Kunci : travelling salesman problem, nearest neighbor algorithm, branch and bound algorithm, air minum dalam kemasan