Aplikasi Algoritma Branch and Bond dan Bahasa Pascal dalam menentukan biaya perjalanan minimum: Studi kasus pada P.T. Mayatama Manunggal Sentosa

ABSTRAK

Masalah travelling salesman problem adalah suatu masalah transportasi yang bertujuan untuk menentukan biaya total perjalanan minimum dari bermacam-macam alternatif rute yang ada. Masalah ini menyangkut salesman yang harus meninggalkan suatu lokasi awal (tempat dimana salesman berada) untuk mengunjungi lokasi yang lainnya (tiap lokasi hanya dikunjungi sekali) dan kemudian kembali ke kota semula.

Untuk mencapai panyelesaian akhir optimal dari masalah tersebut digunakan algoritma branch and bound. Metode brand and bound merupakan bagian dari traveling. Dimana masalah tersebut diselesaikan dalam jumlah iterasi hingga diperoleh hasil yang optimal (biaya perjalanan minimum). Hasil optimal disini diperoleh dengan cara mengalikan jarak total minimum yang dicapai dari iterasi pertama sampai iterasi terahir dengan harga satuan oahan bakar yang telah ditentukan.

Algoritma branch and bound dapat diterapkan pada perusahaan P.T. Mayatama Manunggal Sentosa untuk menentukan suatu urutan kota-kota yang harus dilewati salesman agar biaya total yang dikeluarkan dalam sehuah ekspedisi seminimal mungkin. Setelah terbentuk suati algoritma yang sistematis, maka alur algoritma tersebut dirangkaikan dalam pemrograman yang memakai bahasa pascal.

Untuk menyelesaikan metode branch and bound, data perjalanan harus dimodelkan dahulu ke dalam bentuk matriks. Elemen-elemen baris ke-i dan kolom ke-j menunjukkan besarnya jarak dari kota i ke kota j. Adapun biaya total perjalanan yang minimum diperoleh berdasarkan total jarak minimum yang didapat dari hasil analisis data untuk mencapai lokasi sebanyak mungkin tanpa mengunjungi sebuah lokasi dua kali, kecuali kota awal.

Sehingga dengan Algoritma branch and bound dan bahasa pascal didapatkan total biaya perjalanan minimum yang dikehendaki untuk masing-masing koordinator wilayah yang dikehendaki. Sedangkan biaya perjalanan yang minimum berasal dari pengalian jarak daerah yang dikunjungi dengan satuan harga bahan bakar yang digunakan.