Penerapan Algoritma Best First Search (BFS) untuk Penentuan Slot Parkir

Penerapan Algoritma Best First Search (BFS) untuk Penentuan Slot Parkir

Abstrak

Parkir Motor Kampus X merupakan salah satu area parkir yang disediakan oleh Kampus X untuk mahasiswanya. Area parkir ini sering kali mengalami kepadatan, terutama pada jam-jam sibuk perkuliahan, sehingga menyebabkan kesulitan bagi pengguna dalam menemukan slot parkir yang tersedia. Penempatan motor yang tidak teratur dapat membuat pengguna kesulitan menemukan kembali kendaraannya. Oleh karena itu, diperlukan sebuah sistem yang mampu mengatur dan menentukan slot parkir secara efisien. Tujuan dari penelitian ini adalah mengembangkan sistem dengan algoritma Best First Search (BFS) yang dapat menentukan slot parkir secara otomatis. Algoritma BFS adalah algoritma yang menggunakan pendekatan pencarian dengan mengutamakan node yang paling menjanjikan berdasarkan fungsi heuristik pada setiap langkahnya. Implementasi algoritma BFS menghasilkan sistem yang mampu menempatkan motor pada slot yang kosong berdasarkan kedekatan dengan pintu masuk parkir, sehingga memudahkan mahasiswa dalam mencari dan menempatkan kendaraan mereka dengan lebih teratur serta membantu karyawan (juru parkir kampus) dalam mengatur parkir di Parkir Motor Kampus X. Metodologi penelitian diambil berdasarkan best first search, sistem informasi geografis dan struktur tree.

Kata Kunci: BFS, Kampus X, Parkir, Penempatan, Slot

1. Pendahuluan

Parkir motor merupakan salah satu fasilitas penting yang harus disediakan dalam setiap kampus. Dengan semakin bertambahnya Mahasiswa di setiap tahunnya pastinya akan membuat kendaraan di setiap tahun akan meningkat, sehingga pencarian data letak kendaraan menjadi lebih lama dan kurang efisien, terlebih jika pencarian data letak kendaraan tersebut belum tersistemasi secara maksimal sehingga memiliki tingkat efisiensi rendah, yang pada akhirnya mempersulit pengguna untuk menemukan kembali kendaraannya. Melihat kondisi tersebut diatas, maka diperlukan adanya sebuah sistem yang mampu melakukan pencarian data letak kendaraan secara efisien. Area parkir di Kampus X total 10 slot parkir yang terbagi ke dalam satu petak tempat parkir. Meskipun telah disediakan slot yang memadai, pengaturan dan penempatan motor yang efektif masih menjadi tantangan utama. Dalam rangka mengatasi permasalahan ini, penelitian ini bertujuan untuk mengembangkan sebuah sistem penempatan slot parkir otomatis dengan menggunakan algoritma Best First Search (BFS). Masalah penentuan rute biasanya diselesaikan dengan menggunakan metode Best-First Search. Memilih rute dengan algoritma BFS, dimana pencarian rute boleh mengunjungi node pada level rendah jika node pada level tinggi memiliki nilai tidak baik, dapat digunakan untuk menyelesaikan masalah pencarian rute terbaik untuk tujuan tempat parkir. Algoritma ini memilih node yang paling menjanjikan pada setiap tahap prosedur pencarian terbaik pertama. Manfaat dari breadth first pertama dan depth first search digabungkan dalam pendekatan Best First Search. Setelah itu, secara langsung membangun node yang dipilih dengan menggunakan aturan untuk membuat penggantinya. Dengan menggunakan pendekatan ini, diharapkan sistem yang dikembangkan dapat menentukan slot parkir yang kosong secara cepat dan efisien, serta menempatkan motor berdasarkan kedekatan dengan pintu masuk parkir. Pemilihan algoritma BFS untuk penentuan slot parkir dalam lingkungan kampus didasarkan pada kebutuhan untuk menemukan slot parkir terdekat dengan pintu masuk atau fasilitas utama. BFS memungkinkan pencarian dilakukan secara sistematis dengan menjelajahi slot parkir pada level yang sama sebelum beralih ke level berikutnya, memastikan bahwa slot terdekat yang tersedia akan ditemukan lebih dahulu. Selain itu, kesederhanaan dan keefektifan BFS dalam struktur graf statis menjadikannya pilihan yang sesuai untuk lingkungan parkir kampus yang relatif tidak dinamis. Penelitian Yosdarso Afero (2021), menyoroti keunggulan Algoritma Best First Search dalam menentukan solusi optimal untuk mengukur jarak dari satu titik ke titik lain yang akan dikunjungi. Algoritma ini sangat efektif dalam memudahkan pencarian solusi optimal. Pengambilan keputusan dapat dibantu dengan penerapan Best First Search dalam sistem informasi geografis. Implementasi Best First Search dalam Sistem Informasi Geografis dapat berfungsi sebagai alat bantu dalam pengambilan keputusan sistem. Penelitian Mardiana (2022), menjelaskan tentang pencarian jalur terbaik menuju lokasi pustaka untuk Sistem Navigasi AR, hasil dari penelitian ini diperoleh sistem navigasi augmented reality perpustakaan dengan berdasarkan 4 user story yang ditentukan, 9 backlog dan 10 task card. Sistem berhasil memberikan informasi mengenai informasi rak buku tujuan berdasarkan nomor katalog dan terdapat juga informasi navigasi seperti jarak, waktu serta rute untuk sampai ke rak buku tujuan. Hasil juga menunjukkan bahwa Algoritma A Star (A*) memiliki total jalur yang tepat sebanyak 7 dengan persentase keakuratan 70%, Algoritma Dijkstra memiliki total jalur yang tepat sebanyak 9 dengan persentase keakuratan 90%, dan Algoritma BFS memiliki total jalur yang tepat 0 dengan persentase keakuratan 0%. Penelitian Ryano Alderio (2023), menjelaskan mengenai pencarian Rute menggunakan metode Branch and Bound dengan perbandingan pendekatan Breadht First Search, Depth First Search dan Best First Search. Dan hasil perbandingan yang didapat adalah pendekatan Breadth First Search memerlukan perhitungan lebih banyak dengan 28 kali perhitungan, sedangkan untuk pendekatan Depth First Search membutuhkan 25 kali perhitungan, dan untuk pendekatan Best First Search membutuhkan 23 kali perhitungan. Penelitian ini berbeda dengan penelitian sebelumnya karena mengaplikasikan algoritma BFS secara efektif dengan menggunakan pemodelan pohon. Pemodelan ini membantu dalam membimbing kendaraan menuju slot parkir yang tersedia berdasarkan kedekatan dengan pintu masuk, sehingga mengurangi manuver dan kemacetan yang tidak diperlukan.

2. Metodologi Penelitian

2.1. Best First Search (BFS)

Prosedur pencarian pelebaran pertama adalah prosedur yang menjamin bahwa suatu solusi diperoleh jika solusi ada dengan jumlah cabang pohon yang terbatas. Jika adalah solusi, maka adalah jalur berhingga dari keadaan awal keadaan tujuan. Pencarian yang diperluas ini pertama-tama mencari semua jalur dengan panjang satu (yang panjangnya berhingga), kemudian mencari semua jalur dengan panjang dua (yang juga berhingga). Nilai pencarian heuristik digunakan oleh Algoritma Best First Search untuk membantu menemukan solusi dari permasalahan. Proses ini berlanjut hingga semua lintasan teridentifikasi sehingga solusi dapat ditemukan. Prosedur ini memastikan tidak hanya menemukan solusi, tetapi juga solusi yang mengambil jalur terpendek menuju tujuan.

Untuk memvisualisasikan prosedur pencarian ini, sebuah flowchart digunakan untuk menggambarkan langkah-langkah sistematis yang diambil oleh algoritma BFS. Jika solusi ditemukan, flowchart pada gambar 1 menunjukkan bagaimana algoritma memastikan bahwa jalur terpendek dipilih. Menggambarkan alur proses pencarian slot parkir yang dilakukan secara berurutan berdasarkan baris dan slot yang tersedia. Proses dimulai dengan memasukkan kendaraan ke area parkir, di mana sistem akan mengecek apakah terdapat slot kosong pada baris parkir saat ini. Jika slot kosong ditemukan, kendaraan akan langsung diparkir pada slot tersebut, dan proses selesai. Namun, jika tidak ada slot kosong pada baris yang sedang diperiksa, sistem akan melanjutkan ke baris berikutnya untuk mengecek apakah ada slot kosong di sana. Proses ini terus berlanjut hingga semua baris dan slot diperiksa. Jika pada akhirnya semua slot parkir penuh, sistem akan menyatakan bahwa parkiran penuh dan proses selesai. Flowchart ini sesuai dengan penerapan algoritma Best First Search (BFS) dalam pencarian slot parkir, yang dilakukan dengan mengecek secara berurutan baris demi baris hingga ditemukan slot yang sesuai atau hingga semua opsi diperiksa.

2.2. Sistem Informasi Geografis

Sistem Informasi Geografis, sering disebut juga Sistem Informasi Geografis (SIG), adalah teknologi pemetaan berupa sistem informasi komputer yang dirancang untuk bekerja dengan data yang berisi informasi spasial atau referensi spasial. Teknologi pemetaan banyak digunakan untuk mempermudah pekerjaan masyarakat. SIG sebagai sistem yang dapat mengakomodasi data spasial dengan data atribut dalam sebuah tabel yang mampu memberikan analisis spasial, dapat digunakan untuk memberikan informasi dalam perencanaan untuk diambil keputusan. Sistem informasi geografis dapat mengambil manfaat dari penggunaan Best First Search sebagai sarana untuk mendukung proses pengambilan keputusan.

2.3. Struktur Tree

Struktur tree adalah struktur data yang mengandung aspek hierarki yang dibentuk melalui pengelompokkan elemen atau node dalam tingkatan tertentu. Struktur ini terdiri dari satu node utama yang disebut root, dan node lainnya yang disebut child. Setiap node, kecuali root, memiliki tepat satu parent dan dapat memiliki nol atau lebih child. Node yang tidak memiliki child disebut leaf atau daun. Struktur tree digunakan untuk merepresentasikan hubungan hierarki antara elemen-elemen, seperti dalam organisasi, silsilah keluarga, atau struktur folder dalam sistem file komputer. Selain itu, struktur tree juga sering digunakan dalam algoritma pencarian dan pengurutan, serta untuk mengelola data dalam database dan sistem manajemen informasi.

3. Hasil dan Pembahasan

3.1. Pengukuran

Pada studi kasus penentuan slot parkir di Kampus X, terdapat 10 titik objek lokasi blok parkir. Algoritma Best First Search (BFS) digunakan untuk menentukan slot parkir yang tersedia secara efisien. Dalam Gambar 1 baris balok akan dikonversi menjadi pohon baris parkir di sampingnya. Struktur pohon ini terdiri dari 10 slot parkir yang diwakili oleh node angka dari angka 1 sampai dengan 10.

Dalam pemodelan ini, struktur pohon biner dengan 10 slot parkir diwakili oleh node dengan angka 1 hingga 10. Warna hijau menandakan baris parkiran penuh, biru muda menunjukkan baris parkiran sedang dibuka atau dipertimbangkan, dan putih menandakan baris parkiran yang ditutup atau belum dipertimbangkan. Proses dimulai dari node akar (node 1) yang diperiksa terlebih dahulu dan kemudian berubah menjadi hijau ketika penuh. Pergerakan berlanjut ke anak node 2 dan 3, mengikuti alur BFS yang mengeksplorasi setiap tetangga sebelum melanjutkan ke level berikutnya. Algoritma BFS diterapkan untuk memastikan setiap slot parkir diperiksa secara sistematis, dimulai dari node akar dan melanjutkan ke anak node. Setiap node diperiksa untuk menentukan status ketersediaan slot parkir, memastikan setiap slot diperiksa dengan efisien. Proses ini membantu mengelola slot parkir dengan lebih efektif dan menunjukkan kecepatan serta efisiensi dalam menemukan slot parkir kosong dibandingkan dengan metode pencarian lainnya. Dari hasil penerapan algoritma ini, dapat diidentifikasi bagaimana setiap keputusan diambil oleh BFS, membantu dalam pengambilan keputusan yang lebih baik untuk manajemen parkir di Kampus X.

3.2. Hasil Rancangan dan Implementasi

Algoritma BFS adalah salah satu metode pencarian yang digunakan untuk menelusuri graf atau pohon secara sistematis, lapis demi lapis. Dalam konteks penentuan slot parkir, algoritma ini sangat berguna untuk menemukan slot parkir yang terdekat dari pintu masuk atau lokasi awal kendaraan, dengan cara mengeksplorasi semua kemungkinan slot parkir di satu level sebelum berpindah ke level berikutnya. Proses Best First Search dari node 1 hingga 3 ditunjukkan pada tabel 2.

Pada hasil akhir dari penerapan Algoritma BFS yang ditunjukkan dalam gambar, seluruh node pada pohon graf telah terisi. Setiap node dalam graf ini mewakili slot parkir, dan proses pengisian slot parkir telah dilakukan secara bertahap sesuai dengan level dalam graf.

Hasil ini menunjukkan bahwa kendaraan-kendaraan yang ingin parkir diarahkan untuk mengisi slot parkir yang terdekat terlebih dahulu sebelum mengisi slot yang berikutnya. Proses BFS memastikan bahwa seluruh slot pada level yang lebih rendah terisi penuh sebelum membuka akses ke slot pada level yang lebih tinggi. Ini menghasilkan distribusi slot parkir yang optimal, di mana kendaraan dapat diparkir di tempat yang paling efisien sesuai dengan jarak terdekat dari pintu masuk.

Pseudocode yang disajikan menggambarkan proses sistematis untuk menentukan slot parkir yang tersedia menggunakan metode antrian yang diadaptasi dari algoritma BFS. Berikut diberikan prosedur dari algoritma BFS.

Proses dimulai dengan inisialisasi antrian yang berisi semua baris parkir dan variabel slot ditemukan untuk melacak apakah slot parkir kosong telah ditemukan. Selanjutnya, dalam loop utama, sistem akan terus mencari slot parkir selama ada kendaraan yang masuk dan belum ditemukan slot kosong. Pada setiap iterasi, sistem akan mengambil baris parkir dari antrian dan memeriksa setiap slot parkir dalam baris tersebut. Jika ditemukan slot kosong, kendaraan akan diparkir, dan loop berhenti. Jika pada iterasi tersebut tidak ditemukan slot kosong, dan baris parkir penuh, sistem akan melanjutkan ke baris berikutnya. Namun, jika baris tidak penuh, baris tersebut akan dimasukkan kembali ke antrian untuk diperiksa nanti. Apabila seluruh baris telah diperiksa dan tidak ada slot kosong yang ditemukan, sistem akan menampilkan pesan "Parkir penuh" dan menghentikan proses pencarian. Pseudo code ini menggambarkan alur logis yang efisien dalam menentukan slot parkir yang tersedia, dan sesuai dengan alur flowchart yang telah dihasilkan sebelumnya. Simulasi gambar slot parkir ditunjukkan pada gambar 5 dan 6.

Berdasarkan Gambar 5 dan 6, menunjukkan bahwa dari gambar pengaplikasian UI saling terhubung. Yang mana Gambar 5 adalah tampilan utama aplikasi penentuan slot parkir yang sudah tersedia didalam aplikasi. Sedangkan Gambar 6 adalah hasil dari salah satu slot parkir yang di klik dalam aplikasi tersebut. Dengan menampilkan hasil dari total slot parkir sebanyak 50 slot, terisi 36 slot, dan yang tersedia 14 slot. Proses ini mengilustrasikan bagaimana algoritma BFS dapat diterapkan untuk mengelola slot parkir dengan lebih efisien. Dengan memulai dari node akar dan mengevaluasi setiap anak node, algoritma ini dapat mengidentifikasi slot parkir yang penuh dan yang masih tersedia secara sistematis. Hasil dari penerapan algoritma ini menunjukkan efisiensi dalam menemukan dan mengelola slot parkir, membantu memastikan penggunaan ruang parkir yang optimal di Kampus X.

4. Kesimpulan

Penelitian ini mengembangkan sistem penentuan slot parkir otomatis menggunakan algoritma Best First Search (BFS) di area parkir motor Kampus X. Algoritma BFS dipilih karena kemampuannya dalam melakukan pencarian rute optimal berdasarkan fungsi heuristik. Hasil implementasi menunjukkan bahwa sistem dapat secara efisien menentukan slot parkir yang tersedia, memulai dari node akar dan mengevaluasi setiap anak node secara sistematis. Hal ini meningkatkan efisiensi dalam menemukan slot parkir kosong dan mengelola penempatan kendaraan. Secara keseluruhan, sistem ini membantu pengguna dan petugas parkir dalam mengatur area parkir dengan lebih efektif, mengurangi kemacetan, dan meningkatkan keteraturan penempatan kendaraan. Oleh karenanya, peneliti menyarankan untuk mengintegrasikan sistem ini dengan teknologi sensor atau kamera untuk lebih meningkatkan akurasi dan efisiensi dalam penentuan slot parkir untuk penelitian selanjutnya.