Implementasi Algoritma Branch and Bound

Nama : Aulia Rahma Salsabilla

NPM  : 19312104

Kelas : IF 19D

Mata Kuliah : Analisis dan Strategi Algoritma

Alamat Web Universitas :

https://teknokrat.ac.id/

Alamat Web Fakultas :

https://ftik.teknokrat.ac.id/

Algoritma Branch And Bound

Branch and bound merupakan merupakan metode algoritma yang umum digunakan untuk menentukan penyelesaian optimal dari masalah optimisasi, khususnya pada diskrit dan optimisasi kombinatorial. Pada intinya algoritma ini menggunakan pendekatan enumerasi dengan cara mematikan search space yang tidak mengarah pada penyelesaian. 

Pada tahun 1960, algoritma branch and bound diperkenalkan oleh A.H. Land dan A.G. Doig. Sesuai dengan namanya branch and bound memiliki dua alat yaitu branching dan bounding. 

Branching dilakukan dengan cara meng-cover daerah penyelesaian yang layak dengan beberapa sub daerah layak yang lebih kecil. 

Bounding dilakukan dengan cara menentukan nilai batas atas dan batas bawah untuk penyelesaian optimal di dalam sub daerah yang layak. 

Proses branching menggunakan skema Breadth First Search (BFS). Simpul atau titik yang dibangkitkan terlebih dahulu merupakan simpul yang bertetangga dengan simpul akar. Namun proses pemilihan simpul yang akan diperluas (simpul expand) tidak seperti pada BFS murni. Tidak seperti BFS murni yang memilih simpul expand berdasarkan urutan pembangkitan, pada algoritma branch and bound pemilihan simpul expand didasarkan pada nilai fungsi objektif. Masalah optimisasi biasanya memiliki fungsi untuk menghasilkan nilai batas yang unik. Sedangkan pada algoritma branch and bound pemilihan formula fungsi menggunakan metode heuristic, berdasarkan pada pengalaman dan instinc pembuat program dan tidak ada bukti matematisnya. Hasil optimisasi yang diperoleh melalui algoritma ini bergantung pada keakuratan pemilihan fungsi batas tersebut. Tidak ada cara baku untuk menentukan fungsi batas karena masalah yang sama bisa saja memiliki rumus perhitungan nilai batas yang berbeda.

Langkah-langkah algoritma branch and bound untuk menyelesaikan TSP adalah sebagai berikut.

Langkah 1:

Tetapkan penyelesaian awal masalah. Penyelesaian yang ditetapkan merupakan rute perjalanan lengkap. Tentukan batas tertinggi pada nilai minimum fungsi objektif dengan mencari berbagai kemungkinan rute perjalanan. Batas atas ini dinotasikan dengan f_U .

 

Langkah 2:

Buat cabang awal dengan mengatur X₁ =1 untuk masing-masing kota j = 2,3,...,n . Untuk i = j, nilai C_ij = M untuk menyatakan rute yang tidak mungkin. Hitung batas terendah yang dinotasikan dengan f_L pada nilai minimum fungsi objektif di setiap titik. Dari data awal, hapus baris pertama dan kolom ke j, serta ganti C_ij = M. Tentukan penyelesaian masalah dan tambahkan harga f ke C_ij untuk memperoleh f_L sehingga f_L  = C_ij + f. Jika f_L <= f_U  aktifkan simpul, dan jika sebaliknya hapus simpul.

 

Langkah 3:

Jika tidak ada simpul aktif pada langkah ini maka penyelesaian terbaik saat ini adalah optimal. Jika tidak, pilih simpul dengan nilai f_L terkecil dan buat cabang baru dengan mengatur X_jk = 1 untuk setiap kota yang belum dikunjungi sebelumnya.

 

Langkah 4:

Buat batasan f pada setiap simpul dengan menghapus baris j dan kolom k dari data pada simpul aktif diatasnya. Tambahkan nilai f ke C_jk dengan seluruh nilai sebelumnya.

 

HASIL DAN PEMBAHASAN

Penerapan Algoritma Branch And Bound Pada TSP

Misalkan terdapat 5 kota yang harus dikunjungi dengan jarak antar kota seperti pada tabel 1.

Tabel 1. Jarak Antar Kota

Langkah 1.

Penyelesaian awal untuk masalah TSP ditetapkan X₁₂ = X₂₃ =  X₃₄ = X₄₅ = X₅₁ =1 dengan nilai 131 + 139 + 127 + 130 + 131 = 658, sehingga   f¹_U = 658 .

 

Langkah 2.

Buat cabang X₁₂ =1 (simpul 2), X₁₃ =1 (simpul 3), X₁₄ =1 (simpul 4), X₁₅ =1 (simpul 5). Pada simpul 2 hapus baris pertama dan kolom kedua dari data awal serta ganti C₂₁ = M , sehingga diperoleh :

Penyelesaiannya adalah

X₂₃ =  X₃₅ = X₅₄ = X₄₁ =1dengan nilai 139 + 118 + 130 + 144 = 531, dengan f = 531. Jadi fL = C₁₂ + f = 131 + 531 = 662. Atur f²_U  = 662, kemudian simpan penyelesaian ini sebagai penyelesaian baru dan simpul 2 sebagai simpul aktif sementara. Pada simpul 3 hapus baris pertama dan kolom ketiga dari data awal serta ganti C₃₁ = M, sehingga diperoleh:

Penyelesaiannya adalah

X₃₅ =  X₅₄ = X₄₂ = X₂₁ =1 dengan nilai 118 + 130 + 153 + 131 = 532, dengan f = 532. Jadi fL = C₁₃ + f = 120 + 532 = 652 . Karena fL < f²_U, maka simpan penyelesaian ini sebagai penyelesaian baru. Hapus simpul 2 dan atur simpul 3 sebagai simpul aktif sementara. Pada simpul 4 hapus baris pertama dan kolom keempat dari data awal serta ganti C₄₁ = M , sehingga diperoleh :

 

Penyelesaiannya adalah

X₄₃ =  X₃₅ = X₅₂ = X₂₁ =1  dengan nilai 127 + 118 + 154 + 131 = 530, dengan f = 530. Jadi fL = C₁₄ + f = 144 + 530 = 674. Karena fL > f²_U, maka hapus simpul 4. Pada simpul 5 hapus baris pertama dan kolom kelima dari data awal serta ganti C₅₁ = M , sehingga diperoleh:

 

Penyelesaiannya adalah

X₅₃ =  X₃₄ = X₄₂ = X₂₁ =1  dengan nilai 118 + 127 + 153 + 131 = 529, dengan f = 529.

Jadi fL = C₁₅ + f = 131 + 529 = 660. Karena fL > f²_U, maka hapus simpul 5.

 

Langkah 3.

Terdapat satu simpul aktif yaitu simpul 3 dengan  fL = 652. Buat cabang X₃₂  =1 (simpul 6), X₃₄  =1 (simpul 7), X₃₅  =1 (simpul 8). Buat batasan pada simpul 6, 7, 8, dengan memodifikasi data pada simpul 3. Pada simpul 6 hapus baris ketiga dan kolom kedua dari data di simpul 3 serta ganti C₂₁ = M , sehingga diperoleh:

Penyelesaiannya adalah

X₂₄ =  X₄₅ = X₅₁ =1  dengan nilai 153 + 130 + 131 = 414, dengan f = 414. Jadi fL = C₁₃ + C₃₂ + f = 120 + 139 + 414 = 673. Atur f³_U = 673, kemudian simpan penyelesaian ini sebagai penyelesaian baru dan simpul 6 sebagai simpul aktif sementara. Pada simpul 7 hapus baris ketiga dan kolom keempat dari data di simpul 3 serta ganti C₄₁ = M, sehingga diperoleh :

Penyelesaiannya adalah

X₄₅ =  X₅₂ = X₂₁ =1  dengan nilai 130 + 154 + 131 = 415, dengan f = 415. Jadi fL = C₁₃ + C₃₄ + f = 120 + 127 + 415 = 662. Karena fL < f³_U, maka simpan penyelesaian ini sebagai penyelesaian baru. Hapus simpul 6 dan atur simpul 7 sebagai simpul aktif sementara. Pada simpul 8 hapus baris ketiga dan kolom kelima dari data di simpul 3 serta ganti C₅₁ = M , sehingga diperoleh:

Penyelesaiannya adalah

X₅₄ =  X₄₂ = X₂₁ =1   dengan nilai 130 + 153 + 131 = 414, dengan f = 414. Jadi fL = C₁₃ + C₃₅ + f = 120 + 118 + 414 = 652. Karena fL < f³_U, maka simpan penyelesaian ini sebagai penyelesaian baru. Hapus simpul 7 dan atur simpul 8 sebagai simpul aktif.

 

Langkah 4.

Terdapat satu simpul aktif yaitu simpul 8 dengan fL =  652. Buat cabang X₅₂ =1 (simpul 9), X₅₄ =1 (simpul 10). Pada simpul 9 hapus baris kelima dan kolom kedua dari data di simpul 8 serta ganti C₂₁ = M, sehingga diperoleh :

Penyelesaiannya adalah

X₂₄ = X₄₁ =1 dengan nilai 153 + 144 = 297, dengan f = 297. Jadi

f_L = C₁₃ + C₃₅ + C₅₂ + f

    = 120 + 118 + 154 + 297

    = 689

Karena fL > f³_U, maka hapus simpul 9.

Pada simpul 10 hapus baris kelima dan kolom keempat dari data di simpul 8 serta ganti C₄₁ = M, sehingga diperoleh :

Penyelesaiannya adalah

X₄₂ = X₂₁ =1 dengan nilai 153 + 131 = 284, dengan f = 284. Jadi

fL = C₁₃ + C₃₅ + C₅₄ + f

     = 120 + 118 + 130 + 284

     = 652. Karena fL > f³_U, maka hapus simpul 10. Tidak ada simpul yang aktif. Terdapat alternatif perjalanan yang optimal yaitu 1 - 3 - 5 - 4 - 2 - 1 dengan nilai 652. Pohon algoritma branch and bound diperlihatkan pada gambar 1.

 

Perbandingan Hasil Algoritma Branch And Bound Dengan Exhaustive Search Hasil iterasi pada exhaustive search diperlihatkan pada tabel 2.

Dari tabel di atas terlihat bahwa penyelesaian optimal yang diperoleh dengan exhaustive search sama dengan algoritma branch and bound yaitu 1-3-5-4-2-1 atau dengan rute terbalik 1-2-4-5-3-1 memiliki nilai optimal 652. Karena exhaustive search akan memberikan hasil 100% benar, maka untuk contoh kasus ini hasil yang diperoleh melalui algoritma branch and bound juga pasti benar.

 

Gambar 1. Pohon algoritma branch and bound