OPTIMASI RUTE DISTRIBUSI PRODUK NESTLE MENGGUNAKAN METODE BRANCH AND BOUND DAN TWO-WAY EXCHANGE IMPROVEMENT HEURISTIC (STUDI KASUS : PT. PARIS JAYA MANDIRI – AMBON)

Abstrak Traveling Salesman Problem (TSP) merupakan permasalahan optimasi pencarian rute terpendek dari satu kota ke n-kota lain tepat satu kali dan akan kembali ke titik awal keberangkatan. TSP dikategorikan sebagai hard combinatorial problem sehingga banyak teknik maupun aproksimasi yang dikembangkan untuk pemecahannya. Penelitian ini bertujuan untuk membandingkan teknik branch and bound dengan two-way exchange improvement dalam pemecahan Traveling Salesmen Problem (TSP) didasarkan pada jarak tempuh terkecil dan total waktu tempuh terkecil kendaraan. Penelitian ini diaplikasikan pada kasus nyata permasalahan penentuan rute kendaraan untuk pengiriman produk nestle dari PT. Paris Jaya Mandiri di kota Ambon. Hasil penelitian menunjukan bahwa teknik Two-Way Exchange Improvement memberikan hasil terbaik dibandingkan dengan Branch and Bound, dengan persentase penghematan jarak sebesar 18.09% dan penghematan total waktu sebesar 7.99% dari rute regular perusahaan.