Konsep Navigasi pada Google Map

Mencari sebuah tempat atau menentukan rute jalan terpendek di gadget sekarang bukan lagi sebuah hal yang sulit. Google Map salah satu solusinya, dimana fitur-fitur yang memanfaatkan fungsi navigasi peta begitu hidup di sana. Teknologi GPS mengakomodir penentuan posisi device, sedangkan implementasi network analyst menjalankan fungsinya sebagai panduan dalam mencari jalan menuju suatu tempat.

Prinsip navigasi pada Google Map adalah menentukan lokasi awal dan tujuan untuk selanjutnya ditentukan alternatif rute jalan yang dapat dilalui. Lokasi awal didapatkan dari penentuan posisi device menggunakan satelit GPS, sedangkan lokasi tujuan ditentukan berdasarkan titik yang sudah kita tentukan di peta. Dengan data jalan yang tersedia, Google Map akan menentukan beberapa alternatif untuk kemudian dipilih segmen jalan yang terpendek sebagai pilihan utama yang diberikan. Setelah itu, user dapat menggunakannya sebagai panduan untuk sampai ke tempat tujuan.

Konsep navigasi pada Google Map menggunakan algoritma Djikstra, yaitu algoritma untuk menentukan rute terpendek dari vertex awal ke vertex tujuan pada segmen-segmen garis tertentu. Secara sederhana, algoritma Djikstra dapat dijelaskan melalui gambar di bawah ini.

Sumber: (Waldura, 2007)

Algoritma Djikstra mensyaratkan vertex, edge, dan weight, dimana vertex adalah titik-titik yang saling terhubung, edge adalah garis yang menghubungkan antar titik tersebut dan mempunyai arah, sedangkan weight adalah jarak dari edge yang menghubungkan antar vertex. Vertex tersebut pada Google Map dianalogikan sebagai point-point yang merepresentasikan lokasi awal dan tujuan serta titik-titik lain yang menghubungkannya, sedangkan edge adalah segmen jalan yang dapat dilalui. Misalkan pada gambar di atas, lokasi titik awal adalah vertex a, dan lokasi yang dituju adalah vertex d. Prinsip algoritma Djikstra adalah menentukan rute terpendek, sehingga setiap vertex akan menentukan weight terkecil dari setiap edge yang dapat dilalui dari sebuah vertex. Misalnya, vertex a secara edge mempunyai opsi menuju vertex b dan c, namun secara weight, jarak menuju ke vertex c lebih kecil daripada vertex b (2<4), sehingga jalur yang dipilih adalah a-c, bukan a-b. Vertex yang sudah digunakan tidak lagi dipertimbangkan untuk penentuan rute berikutnya, sehingga dari vertex c, vertex a tidak lagi diperhitungkan meski secara arah vertex c dapat menuju ke vertex a.

Untuk menuju ke vertex selanjutnya, jarak yang sudah dilalui sebelumnya juga diperhitungkan, sehingga jarak yang dihasilkan adalah jarak akumulasi dari weight masing-masing edge. Pada gambar di atas, karena jarak ke vertex b lebih pendek daripada ke vertex d ([2 + 1] < [2 + 5]), maka vertex yang dituju selanjutnya adalah b. Terakhir, karena tidak ada lagi opsi dari vertex b selain langsung menuju ke vertex d, maka rute berikutnya sekaligus yang terakhir adalah b-d.

Atas dasar itulah, dalam pembuatan basisdata unsur transportasi, konsep topologi yang digunakan adalah harus terputus di pertemuan setiap segmen jalan. Jika merujuk pada aturan topologi yang tersedia di software ArcGIS, maka dapat digunakan aturan Must Not Intersect Or Touch Interior. Aturan itu memungkinkan seluruh pertemuan segmen jalan akan di-split, sehingga vertex-vertex bisa dihasilkan pada setiap persimpangan jalan. Ketika persimpangan jalan sudah mempunyai vertex-nya masing-masing, maka opsi rute bisa ditentukan dengan benar, dan selanjutnya hanya bergantung pada jarak antar vertex yang ditentukan oleh shape length dari opsi segmen jalan yang mungkin untuk dilalui.    

Oleh karena itulah, topologi yang benar pada unsur transportasi akan sangat menentukan analisis spasial yang berkaitan dengan rute. Bisa dibayangkan ketika ada salah satu segmen jalan yang undershoot misalnya, dan network jalan tidak terbentuk di sana yang otomatis tidak ada vertex yang dihasilkan di titik yang seharusnya menjadi persimpangan jalan, maka rute jalan bisa jadi akan berputar lebih jauh. Ini tentu bisa menjadi kesalahan yang fatal, terlebih ketika analisis rute tersebut digunakan untuk kepentingan bisnis yang dapat mengakibatkan kerugian. Maka dari itu, topologi yang benar tentu mutlak untuk setiap fitur peta dasar agar user dapat mengoptimalkan peta tersebut secara maksimal.

Dan untuk yang satu ini, sepertinya sudah berjalan dengan cukup baik di Google Map.