Penentuan Rute Optimal Distribusi Machining Part Menggunakan Metode Traveling Salesman Problem dan Nearest Neighbor (Studi Kasus PT. Defa N Precision Indonesia)

PT. Defa N Precision Indonesia merupakan perusahaan yang bergerak dalam bidang machining dan fabrication. Keadaan perusahaan saat ini belum memiliki rute yang tetap untuk pengiriman produk. Hal ini menciptakan rute transportasi yang tidak terstruktur, meningkatkan jarak dan waktu tempuh, dan menimbulkan biaya transportasi untuk pengiriman produk. Penelitian ini bertujuan untuk menentukan rute optimal pengiriman agar biaya pengiriman menjadi minimum. Penentuan solusi rute pengiriman dilakukan menggunakan metode Travelling Salesman Problem dengan algoritma branch and bound dan metode nearest neighbor, kedua metode ini lebih mengefisienkan rute dan bisa mengurangi jarak pengiriman serta biaya transportasi. Hasil perhitungan didapatkan dengan total jarak yang dihitung menggunakan metode Travelling Salesman Problem dengan algoritma branch and bound dan metode nearest neighbor dengan jumlah rute ke pelanggan yaitu 8 rute dengan jarak 99.9 Km yang sebelumnya dengan jarak perusahaan saat ini yaitu 112 Km. sehingga menghasilkan penurunan jarak sebesar 12.1 Km terjadi penghematan sebesar 10.8% . Sedangkan untuk biaya transportasi mengalami penghematan yang awalnya biaya transportasi sebesar Rp. 9,424,800,- setelah dihitung menggunakan metode branch and bound dan nearest neighbor menjadi Rp. 8,406,585,- mengalami penghematan sebesar Rp. 1,018,215,- atau terjadi penghematan sebesar 10.8%.

Kata Kunci : branch and bound, nearest neighbor, produk, rute, travelling salesman problem