Algoritma Mencari Jalur yang Optimal, Penting Banget Nih…


Assalamu’alaikum wa rochmatullohi wabarokatuh

Salam sejahtera buat kita semua, semoga kita semua selamat di perjalanan sampai ke tujuan


Mencari jalur terpendek selalu terlintas di benak para pengemudi atau rider. Apalagi terkait dengan pertimbangan efisiensi waktu dan biaya, jalur terpendek adalah most wanted. Inilah yang ada di otak para bapak yang sedang mengantar anaknya sekolah dengan persediaan waktu yang mepet.

Dengan maraknya jasa angkutan on line (ojol), salah satu keuntungan ojol adalah konsumsi bensin yang paling sedikit. Sedangkan keuntungan kastemer (customer) adalah waktu sesingkat mungkin. Kedua keuntungan ini akan dapat diraih dengan penentuan jalur terpendek yang paling optimum.

Ternyata, algoritma mencari jalur terpendek (shortest path) sudah lama diteliti. Biasanya menggunakan kasus perjalanan seorang salesmen yang harus mengunjungi banyak kota. Semakin pendek jarak total yang harus ditempuh, semakin menguntungkan. Kira-kira seperti ini trayek seorang salesmen untuk mengunjungi semua kota di amerika

kebetulan motogokil baru saja (ngarang) sebuah metode pencarian jalur paling optimum dengan mengandalkan informasi-informasi yang sudah sangat mudah didapatkan zaman ini. Metode ini berbasis argoritma breadth first search (BFS) dikombinasikan dengan gossip. Dimana pembobotan pemilihan jalur adalah dengan mempertimbangkan :

  1. Keberadaan banyaknya jalur setelahnya
  2. Jarak terdekat dari posisi awal
  3. Jarak terdekat dari posisi akhir

Dengan mempertimbangkan 3 point di atas maka dipilihlah sebuah titik tujuan awal. Kemudian akan dilanjutkan ke titik-titik selanjutnya sampai ke tujuan. Untuk kondisi lalu-lintas yang semakin kompleks maka perlu ditambah beberapa variabel lainnya yang haru diberika bobot seperti :

  1. Tingkat kemacetan (tergantung jam)
  2. Adakah tujuan lain sebelum tujuan akhir (mampir)
  3. Kondisi jalan yang sejuk berpohon (tidak panas dan berdebu)
  4. Posisi spbu (untuk motor dengan tangki bensin kecil)
  5. dll

Sehingga jalur yang dipilih bukan hanya terpendek, tetapi juga waktu tersingkat dan ternyaman. Tapi untuk sementara dibatasi pada 3 variabel awal dulu untuk memberikan gambaran yang paling sederhana.

Langkah awal, modelkan dulu titik yang terhubung dalam jalur yang akan ditempuh. Setiap titik punya koordinat, sehingga mudah dihitung jarak (panjang lintasan) antara titik-titik tersebut.

Kemudian beri indeks, titik awal sink = 0. Kemudian semua titik terdekat diberi indek 1. Dan semua titik yang terhubung dengan titik 1 diberi indeks 2 dan seterusnya. Yang diberi indeks adalah titik-titik yang sebelumnya belum berindeks. Peng-indeks-an inilah sebagai salah satu langkah dalam BFS

Kalau digambar tanpa jalur (supaya tidak semrawut) menjadi seperti ini

Dari gambar ini terlihat bahwa mau kemanapun harus menghasilkan hubungan antara titik dengan urutan 0(awal)-1-2-3-4-5-6-7(paling jauh). Ketika akan menuju titik 29, maka dengan mempertimbangkan 3 variabel di atas dipilihlah titik-titik yang harus dilalui untuk sampai ke titik 29.

Nah metode ini jika bisa diterapkan dalam penentukan jalur tentunya akan sangat berguna. Apalagi jika dilengkapi dengan variabel-variabel lain juga sangat menentukan seperti kondisi jalan, trafik dll. Sehingga baik tukang ojek maupun penumpangnya sama-sama mendapatkan keuntungan.

Sementara itu dulu bro and sis pemirsa motogokil semoga bermanfaat. Akhir kata mohon maaf jika ada salah dan kurangnya, wassalamu’alaikum wa rochmatullohi wa barokatuh.

 

Advertisements

$where = 0;

Semoga tercerahkan dan komen mas bro juga ikut mencerahkan