Algoritma Customizable Route Planning (CPR) – Bing Maps

Masih seputar Shortest Path Problem, kali ini kita akan membahas algoritma yang di terapkan Microsoft dalam teknologi Bing Mapsnya. Dimulai dari bagaimana cara kerja algoritma Customizable Route Planing (CPR) pada Bing Maps hingga apa yang membuat algoritma CPR ini berbeda dengan Algoritma Djikstra.

Algoritma Customizable Route Planing sebenarnya adalah algoritma yang di-custom dari algoritma djikstra. Ini dilakukan oleh Microsoft Research team dan diimplementasikan pada Bing Maps saat ini. Menurut peneliti, algoritma djikstra telah digunakan di beberapa tahun belakang, dan alasan kenapa dilakukan custom pada algoritma djikstra, karena algoritma ini masih belum sempurna untuk diterapkan terhadap beberapa kondisi-kondisi yang ada dijalan secara real. Oleh karena itu dilakukan modifikasi maupun optimasi terhadap algoritma djisktra ini.

Maps CPR

Dari penelitian dan eksperimen yang dilakukan Microsoft Research Team hingga adanya perubahan, ternyata perhitungan terhadap rute menjadi 2 kali lebih cepat. Lalu bagaimana hal itu bisa bekerja 2 kali lebih cepat ?

Itu semua dapat bekerja dalam 3 tahapan, antara lain :

  1. Metric-Independent Preprocessing :
    – Exploit topology of the network;
    – May take a few minutes, linear space overhead
  2. Metric Customization :
    – Fast: < 30 sec per metric;
    – Space overhead: small fraction of input
  3. Real time query calculation :
    – Reasonably fast for each metric;
    – Worst-case guarantees

Menurut Ricky_Brundritt (2015) Microsoft employee, yang membuatnya lebih cepat adalah karena algoritma ini memecah peta maps menjadi lebih kecil dan membatasi node maupun jarak yang ada. Hal ini lah yang memungkinkan algoritma untuk fokus pada daerah yang kecil saat menghitung semua jaringan jalan yang ada didunia. Untuk cara kerja lebih detailnya dapat melihat slide ini.


 

Referensi :

Iklan

Good People write good comments ..

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s