Implementasi Algoritma Branch and Bound dalam Lampu Lalu Lintas

PENGERTIAN ALGORITMA BRANCH and BOUND      

  Algoritma Branch and Bound merupakan algoritma yang digunakan dalam mengoptimasi suatu persoalan tanpa melanggar batasan persoalan tersebut. Cara kerja algoritma Branch and Bound adalah dengan membangun suatu pohon ruang status. Setiap simpul pada pohon diberi nilai cost yang merupakan taksiran lintasan termurah ke simpul status solusi. Tujuannya adalah agar tidak semua simpul dibangkitkan, tetapi hanya simpul dengan nilai cost paling optimal. Pembangiktan simpul umumnya menggunakan aturan best-first rule. Cara penentuan cost masing-masing simpul menerapkan fungsi pembatas atau fungsi obyektif. Jika nilai fungsi obyektif tidak lebih baik dari nilai terbaik, tidak merepresentasikan solusi yang feasible, dan melanggar batasan, maka simpul tersebut dimatikan. Solusi yang feasible adalah solusi terbaik dari simpul lainnya. Algoritma tersebut dapat digambarkan dengan daftar antrian priority queue atau dengan pohon ruang status. Berikut algoritma Branch and Bound secara umum:

 

 1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi, maka solusi telah ditemukan. Berhenti.
 

2. Jika Q kosong, tidak ada solusi. Berhenti.

3. Jika Q tidak kosong, pilih antrian Q simpul ke i yang mempunyai nilai cost ĉ(i) paling optimal. Jika terdapat beberapa simpul i yang memenuhi, ikuti aturan best-first rule atau pilih secara sembarang.

4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, berhenti. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2. Pohon merupakan graf terhubung yang tidak membentuk sirkuit. Pohon berakar adalah pohon yang memperlakukan sebuah simpulnya sebagai akar dan sisi-sisinya diberi arah. Pada pohon berakar, terdapat beberapa terminologi, yakni anak (simpul yang terhubung dan satu level lebih bawah), orangtua 1 

5. Untuk setiap anak j dari simpul i, hitung ĉ(j), dan masukkan semua anak-anak tersebut ke dalam Q. 

6. Kembali ke langkah 2.

 

 Algoritma Branch and Bound diterapkan pada beberapa persoalan, yakni persoalan N-Ratu, persoalan Travelling Salesman Problem, 15-Puzzle, Knapsack Problem, dan persoalan-persoalan lainnya.

Sistem kemudian menganalisis keadaan lalu lintas, berapa banyak mobil yang bergerak ke arah masing-masing lampu. Sistem kemudian merancang sebuah jadwal pergantian lampu hijau ke lampu merah atau lampu merah ke lampu hijau untuk masing-masing lampu dan mengomunikasikannya ke semua lampu. Setiap lampu harus “mengetahui” jadwal semua lampu dan keadaan lalu lintas semua jalur. Masing-masing lampu lalu lintas bekerja sesuai dengan jadwal tersebut. Proses penjadwalan dilakukan pada setiap satuan waktu tertentu mengikuti keadaan lalu lintas. Proses penjadwalan tersebut bergantung pada dua hal, yakni kepadatan masing-masing jalur, dan waktu maksimal bergerak atau berhenti. 

 

ANALISIS KEADAAN LALU LINTAS SIMPANG DAGO

Lampu lalu lintas pintar adalah sebuah sistem lampu lalu lintas yang memanfaatkan teknologi dan intelejensia buatan agar lampu lalu lintas dapat ‘berpikir’ sendiri apa yang harus dilakukan berdasarkan lalu lintas saat itu. Sistem ini menggunakan proses pengiriman sinyal dan perekaman keadaan lalu lintas saat itu. Misalkan pada sebuah perempatan, terdapat empat buah lampu lalu lintas. Masing-masing lampu memiliki sebuah kamera untuk merekam keadaan lalu lintas. Beberapa sistem tidak menggunakan kamera dalam menangkap keadaan lalu lintas, tetapi menggunakan sensor penangkap sinyal kendaraan atau menggunakan perangkat nirkabel pendeteksi kendaraan

Perempatan Simpang Dago membatasi empat ruas jalan, yakni Jalan Ir. H. Juanda bagian lebih Utara ke arah , Jalan Ir. H. Juanda bagian lebih Selatan, Jalan Dipati Ukur, dan Jalan Siliwangi. Keempat Jalan tersebut merupakan jalan besar yang hampir setiap saat dipadati oleh kendaraan. Perempatan Simpang Dago sendiri memiliki empat buah lampu lalu lintas aktif. Letak lampu lalu lintas dapat dilihat pada gambar di atas. Titik merah menggambarkan letak lampu lalu lintas dan titik hitam menggambarkan arah lampu lalu lintas tersebut. Penulis mengamati kondisi lalu lintas perempatan Simpang Dago berdasarkan kepadatan jalan pada saat lampu sedang menyala bewarna merah. Kepadatan jalan diukur dari banyaknya mobil per satuan luas wilayah jalan tersebut.

Semakin berkembangnya zaman, semakin dinamisnya pergerakan zaman, kebutuhan akan suatu kota yang pintar semakin tinggi. Kota yang pintar dapat dibangun oleh kemajuan teknologi, informasi, dan komunikasi yang baik. Kota pintar dibangun dengan tujuan meningkatkan fasilitas yang baik bagi penduduk kota dan menyelesaikan masalah yang kerap kali muncul dan mengganggu bagi kehidupan penduduk kota. Salah satu masalah yang sering timbul dan menjadi kegelisahan penduduk kota pintar Bandung adalah kemacetan. Kemacetan, yang dapat menimbulkan konsumsi bahan bakar berlebihan yang sia-sia dan membuang-buang waktu dengan percuma, disebabkan oleh padatnya kendaraaan yang melintasi jalanan kota Bandung dan ketidaksesuaian lampu lalu lintas dengan keadaan di jalanan. Penulis mengajukan suatu solusi untuk mengatasi masalah kemacetan ini, yakni membangun suatu lampu lalu lintas pintar yang tidak hanya beroperasi berdasarkan satuan waktu tertentu, tetapi juga dengan melihat keadaan jalan yang ada. Lampu hijau akan lebih diprioritaskan kepada jalan yang memiliki kepadatan jalan lebih besar dibandingkan dengan jalan lainnya. Dengan menggunakan sistem penjadwalan yang baik dengan implementasi algoritma Branch and Bound dan mencantumkan batas waktu kendaraan menunggu lampu merah sebagai fungsi pembatas pada algoritma tersebut, penulis berharap sistem penjadwalan tersebut dapat menciptakan lampu lalu lintas yang pintar dan membantu mengurangi kemacetan.

 

Referensi

https://adoc.pub/penerapan-algoritma-branch-and-bound-dalam-lampu-lalu-lintas.html