Penyelesaian masalah perjalanan pedagang keliling dengan pick-up dan delivery menggunakan algoritma branch and bound

Abstract

TSPD (Traveling Salesman Problem with Pick-up and Delivery) adalah suatu masalah menentukan rute dengan biaya minimum atau jarak terpendek bagi seorang pedagang keliling yang menggunakan kendaraan untuk melakukan kegiatan perngambilan barang (pick-up) dan pengiriman barang (delivery). Perjalanan tersebut dimulai dan berakhir di gudang dalam satu kali perjalanan. Dalam tulisan ini dibuktikan teorema-teorema yang digunakan untuk penyelesaian Masalah P dan contoh kasus dengan tiga pelanggan pick up dan tiga pelanggan delivery. Model TSPD dengan Masalah P dapat diselesaikan dengan menggunakan algoritma Branch and Bound (Kalantari).