OPTIMASI JALUR DISTRIBUSI GAS LPG 3 KG DENGAN METODE BRANCH AND BOUND (Studi Kasus: PT Cahaya Bintang Lestari (CBL)) BENGKULU

Penelitian ini bertujuan untuk menemukan rute terpendek dalam penyelesaian
Travelling Salesperson Problem (TSP) pada jalur pendistribusian Gas LPG 3 Kg
oleh PT CBL di Kabupaten Mukomuko dengan menggunakan metode Branch and
Bound. Parameter yang digunakan dalam penelitian ini adalah jarak jalan yang
dilalui oleh mobil pendistribusi Gas LPG 3 Kg dari Pangkalan ke Pangkalan dengan
memanfaatkan Google Maps. Prosedur menemukan rute terpendek ditempuh
melalui titik awal, yakni gudang PT CBL di Kota Bengkulu, ke setiap pangkalan
dan kembali lagi ke gudang PT CBL dengan syarat tiap pangkalan hanya
dikunjungi satu kali saja. Permasalahan TSP ini dimodelkan ke dalam masalah
integer programming. Model ini diselesaikan dengan bantuan software LINGO
11.0 untuk memperoleh solusi optimal. Hasil yang diperoleh dari penelitian ini
berupa rute terpendek dengan total jarak terpendek adalah 610 km.
Kata kunci: Travelling Salesperson Problem, integer programming, Branch and
Bound, software LINGO 11.0