Penentuan Jalur Shuttle Bus Menggunakan Algoritma Semut

JURNAL IT - Algoritma semut (Ant Colony Optimization/ACO) adalah teknik optimasi yang terinspirasi oleh perilaku semut dalam mencari jalan menuju sumber makanan. 

Shutlle Bus

Algoritma ini menggunakan suatu mekanisme khusus yang disebut feromon untuk menandai jalur yang telah dilalui oleh semut dan menghindari jalur yang kurang optimal.

Dalam algoritma semut, semut diletakkan pada sebuah graf, dan setiap semut mencari jalur terpendek dari titik awal ke titik akhir. Setiap kali semut melewati suatu jalur, mereka melepaskan suatu jumlah feromon kecil pada jalur tersebut. 

Jumlah feromon yang ditinggalkan semut pada jalur tersebut bergantung pada panjang jalur dan kualitas solusi yang ditemukan.

Selanjutnya, semut-semut lain akan mengikuti jalur yang memiliki feromon yang lebih tinggi, sehingga secara bertahap akan terbentuk jalur-jalur yang lebih optimal. Dalam setiap iterasi, feromon pada jalur akan menguap dan berkurang, sehingga jalur yang kurang optimal akan diabaikan.

Algoritma semut telah berhasil diterapkan pada berbagai masalah optimasi, seperti masalah jalan terpendek, penjadwalan, dan pengoptimalan rute kendaraan.

Algoritma semut diperkenalkan oleh Moyson dan Manderick dan secara meluas dikembangkan oleh Marco Dorigo. 

Algoritma ini menggunakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik. Algoritma ini diambil dengan analogi oleh perilaku semut dalam menemukan jalur dari koloninya menuju makanan.

Algoritma

Baik, berikut adalah implementasi algoritma semut pada kasus penentuan jalur shuttle bus:

Langkah 1: Inisialisasi

• Buat graf yang merepresentasikan jaringan jalur shuttle bus.
• Setiap titik pada graf merepresentasikan lokasi halte bus.
• Setiap sisi pada graf merepresentasikan rute antar halte bus.
• Tentukan jumlah semut yang akan digunakan dalam algoritma.
• Inisialisasi feromon pada setiap sisi pada graf dengan nilai yang sama.

Langkah 2: Setiap Semut Mencari Jalur

• Setiap semut diletakkan pada titik awal acak pada graf.
• Semut bergerak menuju titik tujuan dengan memilih sisi berdasarkan aturan probabilistik yang memperhatikan nilai feromon pada sisi tersebut dan jarak ke titik tujuan.
• Setelah mencapai titik tujuan, semut kembali ke titik awal dengan memilih sisi berdasarkan aturan yang sama.

Langkah 3: Update Feromon

• Setelah semua semut menyelesaikan perjalanannya, nilai feromon pada setiap sisi diupdate berdasarkan kualitas jalur yang dilalui oleh semut.
• Sisi-sisi yang dilalui oleh semut yang berhasil menemukan jalur terpendek akan diberi nilai feromon yang lebih besar.
• Sisi-sisi yang kurang optimal akan diberi nilai feromon yang lebih kecil.

Langkah 4: Ulangi Langkah 2 dan 3

• Langkah 2 dan 3 diulangi beberapa kali sampai nilai feromon pada jalur yang optimal terbentuk dan nilai kesalahan minimum tercapai.
• Setelah itu, jalur optimal dapat diambil dari graf.

Demikianlah implementasi algoritma semut pada kasus penentuan jalur shuttle bus. Algoritma semut ini dapat membantu dalam menentukan jalur shuttle bus yang optimal dan efisien, dengan mempertimbangkan faktor-faktor seperti jarak dan waktu tempuh.

Contoh Graf jalur efektif tujuan pusat kota

Graf adalah suatu struktur data matematika yang terdiri dari simpul-simpul (nodes) yang terhubung dengan sisi-sisi (edges). Dalam konteks penentuan jalur shuttle bus, graf ini merepresentasikan jaringan jalur shuttle bus yang tersedia, di mana setiap simpul merepresentasikan lokasi halte bus dan setiap sisi merepresentasikan rute antar halte bus.

Contohnya, jika terdapat 4 halte bus dalam jaringan shuttle bus, maka graf-nya terdiri dari 4 simpul yang merepresentasikan lokasi halte bus dan sisi-sisi yang menghubungkan antar simpul merepresentasikan rute antar halte bus. Graf dapat digambarkan dengan menggunakan diagram yang terdiri dari simpul-simpul dan sisi-sisi yang menghubungkannya.(*)