Penerapan Teori Graf dan Tree dalam Aplikasi: Global Positioning System (GPS)

Pada jaman sekarang ini teknologi satelit sudah semakin maju dan banyak digunakan dalam kehidupan sehari-hari. Sebagai contoh yakni GPS (Global Positioning System) atau biasa dikenal sebagai sistem navigasi. Untuk lebih memahami cara kerja GPS dan tidak hanya sekedar menggunakannya saja maka dilakukan pendekatan terhadap algoritma dan logika yang digunakan untuk mengoperasikan sebuah GPS. Pendekatan dengan menggunakan graf berarah dan berbobot dan juga pohon keputusan merupakan pendekatan yang paling tepat dan sesuai dengan system ini. Gambar jalan-jalan yang diterima dari satelit diubah menjadi sebuah graf berarah berbobot dan digunakan Tree atau yang disebut pohon keputusan, untuk menentukan jalan mana yang harus diambil (jalan yang paling efektif).

Untuk lebih memahaminya, berikut merupakan pengertian dan definisi sebenarnya dari GPS, graf, dan tree, yang selanjutnya menghasilkan pengeertian terhadap pengaplikasian nyata dalam kehidupan nyata. Hal ini penting untuk dibahas dan diketahui karena sekarang ini jalan-jalan yang terutama terletak di daerah perkotaan seringkali macet, ada perbaikan dan sebagainya. Contohnya yaitu jalan di Kota Bandung sekarang ini banyak yang sedang diperbaiki sehingga menyebabkan macet dan akan menghambat kegiatan penduduk. Dengan teknologi GPS maka kita akan dapat menggunakan jalan alternatif tanpa harus mengalami macet terlebih dahulu. Maka pemahaman terhadap cara kerja dan logika pada algoritma GPS sederhana sangatlah diperlukan agar kita tidak hanya dikendalikan oleh mesin dan teknologi (menjadi “budak teknologi”) tetapi kita dapat mengendalikan dan mengembangkan teknologi agar jadi lebih bermanfaat bagi kehidupan manusia

1.    Global Positioning System (GPS)

GPS adalah sebuah sistem yang menggunakan fasilitas satelit dalam barbagai bidang kehidupan. Umumnya GPS yang kita kenal digunakan sebagai sistem navigasi, yang pada dasarnya digunakan untuk keperluan militer dan pertahanan, lalu kemudian berkembang untuk keperluan navigasi baik untuk di darat maupun di laut dan juga di udara pada pesawat-pesawat udara (sebagai contoh Boeing 737 sudah ada yang menggunakan GPS untuk navigasi, menentukan posisi pesawat berada dan berapa jauh jaraknya dari tempat tujuan atau tempat mendarat terdekat). GPS dikembangkan oleh Departemen Pertahanan Amerika Serikat dengan nama NAVSTAR GPS. Ada beberapa kegunaan GPS secara umum, namun ruang lingkup pembahasan ini difokuskan pada GPS sebagai sistem navigasi.

 1.1.  GPS Sebagai Sistem Navigasi

Beberapa jenis kendaraan telah dilengkapi dengan GPS untuk alat bantu nivigasi, dengan menambahkan peta, maka bisa digunakan untuk memandu pengendara, sehingga pengendara bisa mengetahui jalur mana yang lebih cepat dan sebaiknya dipilih untuk mencapai tujuan yang diinginkan. Perangkat navigasi GPS adalah perangkat yang dapat mengetahui posisi koordinat bumi secara tepat yang dapat secara langsung menerima sinyal dari satelit. Perangkat GPS modern menggunakan peta sehingga merupakan perangkat modern dalam navigasi di darat, kapal di laut, sungai dan danau serta pesawat udara. Perangkat ini biasa dipasang pada kendaraan atau telepon seluler untuk menunjukkan posisi kendaraan atau telepon seluler tersebut berada sehingga tidak akan tersesat adan dapat menunjukkan jalan terdekat menuju tempat tujuan. Sistem navigasi kendaraan adalah perangkat navigasi berkendaraan modern yang digunakan untuk memandu perjalanan dari suatu tempat ke suatu tujuan tertentu, dengan menggunakan perangkat peta digital dan informasi posisi dengan menggunakan satelit GPS. Untuk penentu posisi di lapangan, saat ini dilakukan dengan menggunakan alat yang disebut GPS receiver, yang kemudian diolah untuk mendapatkan posisi koordinat buminya. Dengan menggunakan peta digital yang yang didownload ke perangkat sistem navigasi kendaraan, sehingga dapat mengetahui posisi saat ini di peta dan arah lintasan yang akan dilalui dari koordinat awal menuju tempat tujuan dengan koordinat tertentu pada peta.

Gambar 1: Hasil Gambar yang Diterima Perangkat Navigasi GPS dari Satelit

Gambar jalan dan tempat-tempat yang menjadi titik acuan pada peta ini kemudian diubah menjadi graf berarah dan berbobot agar dapat diamati dan kemudian diolah datanya agar dapat memberikan arah yang tepat dan efektif untuk dapat sampai ke tempat tujuan. Kita akan membahas fungsi GPS pada kendaraan bermotor sebagai penunjuk jalan atau pada telepon seluler. Berikut akan dibahas cara merepresentasikan jalan yang dapat dilalui kendaraan bermotor dan pengambilan keputusan dalam pemilihan jalan tercepat dan terefektif.

2.    GRAF

Seperti yang sudah dipelajari pada mata kuliah Matematika Diskrit, graf dapat digunakan untuk merepresentasikan berbagai hal. Graf terbagi menjadi beberapa bagian yaitu graf berarah dan tak berarah. Dalam bahasan kali ini yang akan digunakan untuk merepresentasikan jalan dan tempat-tempat acuannya adalah graf berarah.

2.1. Graf Berarah

Sebuah graf terarah atau digraf G terdiri dari suatu himpunan V dari verteks-verteks (atau simpul-simpul) dan suatu himpunan E dari rusuk-rusuk (atau busur-busur) sedemikian rupa sehingga setiap rusuk e ∈ E menghubungkan pasangan verteks terurut.

Gambar 2 : Contoh Graf Berarah

Graf berarah dianggap yang paling tepat untuk merepresentasikan masalah ini karena jalan-jalan di bumi memiliki arah dan tidak semua jalan “dua arah” ada juga jalan “satu arah”. Oleh karena itu dengan graf berarah masalah tersebut dapat terselesaikan. Sehingga jalan tercepat menuju ke tempat tujuan dapat ditemukan tanpa perlu khawatir akan jalan “satu arah”.

Tetapi masih ada masalah selanjutnya yaitu kepadatan jalan-jalan di perkotaan yang sering menimbulkan kemacetan terutama di saat liburan seperti libur Natal dan tahun baru menyebabkan jalan macet dan perlu mencari jalan alternatif. Masalah ini dapat diselesaikan dengan merepresentasikan gambar jalan yang diterima oleh perangkat navigasi GPS dari satelit dengan graf berbobot. 

2.2. Graf Berbobot

Sebuah graf dengan bilangan-bilangan pada rusuk-rusuknya disebut graf berbobot (weighted graph). Dalam sebuah graf berbobot, panjang lintasan adalah jumlah bobot rusuk-rusuk dalam lintasan. Dalam bahasan ini bobot setiap lintasan tidak hanya merepresentasikan panjang lintasan saja, tetapi juga merepresentasikan tingkat kepadatan/ kemacetan jalan/lintasan. Jadi akumulasi dari panjang jalan dari suatu titik/tempat acuan di jalan yang nyata ke titik berikutnya dan tingkat kepadatan pada jalan tersebut merupakan bobot untuk setiap lintasan.

Gambar 3 : Contoh graf berbobot tak berarah.

Semakin besar bobot suatu lintasan maka akan menghabiskan waktu yang semakin lama untuk melalui lintasan itu. Jadi bobot pada graf berbanding lurus dengan waktu tempuh dan efektifitas jalan untuk dilalui.

Untuk merepresentasikan gambar jalan yang diterima dari satelit pada perangkat navigasi GPS maka kedua bentuk graf yang sudah dibahas di atas perlu digabung sehingga membentuk graf berbobot dan berarah. Dengan graf berbobot dan berarah maka kedua masalah utama untuk merepresentasikan lintasan atau jalan dapat diatasi, yaitu masalah jarak/panjang lintasan dan tingkat kepadatan jalan. Sekarang masih ada satu masalah yang sangat penting untuk dicari solusinya yaitu mengambil keputusan jalan mana yang akan dipilih. Hal tersebut akan dilakukan pendekatan dengan menggunakan tree atau pohon keputusan.

3.    Pohon Keputusan (Tree)

Secara umum pohon keputusan digunakan untuk memodelkan persoalan yang terdiri dari serangkaian keputusan yang mengarah ke solusi. Tiap simpul pada pohon keputusan menyatakan keputusan, setiap daun menyatakan solusi dan seitap cabang menyatakan keputusan yang diambil. Pohon keputusan adalah model prediksi menggunakan struktur pohon atau struktur berhirarki. Konsep dari pohon keputusan adalah mengubah data menjadi pohon keputusan dan aturan-aturan keputusan. Manfaat utama dari penggunaan pohon keputusan adalah kemampuannya untuk mem-break down proses pengambilan keputusan yang kompleks menjadi lebih simpel sehingga pengambil keputusan akan lebih menginterpretasikan solusi dari permasalahan.

Gambar 4 : Contoh pohon keputusan

Gambar di atas adalah contoh pohon keputusan apakah akan pergi bermain atau tidak dengan cuaca sebagai faktor penentu. Contoh pohon keputusan di atas sangat sesuai untuk menantukan jalan yang akan dipilih dengan panjang lintasan dan tingkat kepadatan jalan (bobot lintasan) sebagai faktor penentu, yang juga menggambarkan tata cara serupa dalam pengambilan keputusan jalan mana/solusi mana yang terbaik dan akan diinformasikan pada pengguna sistem navigasi GPS.

Ketika menemui cabang jalan atau simpul pada graf berarah dan berbobot yang telah dibentuk, kita tidak dapat langsung memilih jalan / lintasan dengan bobot terkecil begitu saja karena jalan/lintasan dari suatu titik asal ke titik tempat tujuan belum tentu hanya terdiri dari sebuah lintasan saja, sehingga lintasan tercepat dan terefektif tidak dapat ditentukan jika hanya memilih jalan dengan bobot terkecil setiap kali menemui cabang jalan atau simpul pada graf yang telah terbentuk dari data yang diterima dari satelit pada sistem navigasi GPS.

Dengan meenggunakan pohon keputusan maka kita dapat menentukan jalan mana yang terbaik, lintasan yang pada awalnya memiliki bobot yang tinggi mungkin saja pada pilihan jalan / cabang berikutanya adapat menghantarkan kita pada tujuan dengan lebih cepat karena jalan selanjutnya memiliki bobot yang kecil. Sedangkan jalan / lintasan yang bobot awalnya kecil mungkin saja lintasan-lintasan berikutnya berbobot besar dan akan semakin menghambat jalan ke titik tujuan. Untuk itu diperlukan pohon keputusan dan algoritma pohon secara rekusif untuk setiap cabang pohon agar dapat memperoleh solusi terbaik dengan cara yang efisien. Setiap cabang jalan pada graf atau pada kehidupan nyata merupakan simpul atau node pada keputusan dimana pada pohon akan dilakukan perbandingan bobot pada masing-masing cabang jalan / lintasan dan begitselanjutanya untuk setiap cabang jalan yang ditemui, kita akan dihadapkan pada pilihan yang harus diambil pada pohon keputusan sampai diperoleh jalan yang terbaiak lalu diinformasikan pada pengguna sistem navigasi GPS cabang jalan mana atau arah mana yang harus dipilih.

4.    Contoh Persoalan Representasi untuk GPS

Berikut merupakan contoh soal sederhana dan pembahasannya.

 

Gambar 5 : Graf Contoh Persoalan Representasi untuk GPS

Graf di atas adalah contoh data masukkan dalam bentuk graf yang masuk ke dalam Pusat Informasi untuk kemudian diproses. Kita ingin mencari jalan tercepat dari posisi awal kita yaitu titik A sampai tiba ke titik D. Dari graf di atas maka pohon keputusan yang dibentuk untuk mennetukan jalur terbaik adalah sebagai berikut.

Gambar 6 : Contoh Pohon Keputusan untuk Menyelesaikan Persoalan GPS

Dapat di lihat pada gambar di atas adalah pohon dibentuk hasil transformasi graf input, titik awal dan titik akhir. Jadi di sini menjadi lebih jelas bahwa setiap cabang pada simpul adalah semua cabang jalan / jalur yang terdapat pada simpul / titik tersebut tanpa mengikut sertakan cabang jalur kedatangan. Pada pohon di atas seharusnya ada simpul C karena dari titik A pada graf juga terdapat cabang yang menghubungkan titik A dengan titik C, tetapi cabang tersebut tidak dimasukkan pada pohon karena arahnya. Jadi cabang atau sisi pada graf yang berlawanan arah tidak dimasukkan ke dalam simpul pohon agar mempermudah pemrosesan kemudian.

Sekarang kita akan mulai membahas cara penentuan solusi jalur terbaik dengan menggunakan pohon keputusan tersebut. Bila ditinjau bobot tiap simpul maka bobot simpul B adalah 7 dan bobot simpul E adalah 8, sedangkana bobot simpul A adalah 0 karena belum ada jalur yang diambil. Bobot akhir pada daun BD adalah 22, pada daun ED1 14 dan pada daun ED2 10. Bobot pada daun adalah akumulasi dari bobot semua lintasan dari akar sampai ke daun tersebut. Maka jelas bahwa jalur tercepat adalah dari titik A ke titik E lalu ke titik D melelui sisi yang berbobot 2. Jika kita telusuri jalurnya satu per satu maka kita akan menamui cabang jalan pertama yaitu dari A ke B atau dari A ke E. Apabila kita hanya memilih saja secara langsung tentu jalur dari A ke B yang akan dipilih karena bobotnya lebih kecil, padahal pada sisi selanjutnya yaitu dari B ke D mempunyai bobot yang sangat besar dan jalur yang dipilih menjadi tidak efektif jika dibandingkan dengan kita memilih jalur dari A ke E terlebih dahulu.

Meskipun memiliki bobot yang lebih besar pada percabangan pertama tetapi pada sisi selanjutnya jalur dari A ke E memiliki akumulasi bobot yang lebih kecil dari pada jalur A-B-D. Selanjutnya yang jadi masalah adalah menentukan cabang mana yang akan dipilih pada simpul E, karena kedua cabang langsung menuju ke D maka dapat langsung dipilih cabang dengan bobot terkecil yaitu cabang dengan bobot 2. Tetapi kita tidak dapat begitu saja menentukan jalur dengan mudah seperti kasus pada simpul E ini. Untuk memperoleh jalur terbaik dari titik A ke titi D maka dalam penelusuran pohon keputusan perlu digunakan metode rekursif. Pada akar dan setiap simpul dalam fungsi atau prosedur untuk mencari jalur terbaik dipanggil kembali. Maka pada satiap simpul pemanggilan prosedur atau fungsi tersebut dilakukan sebanyak n kali, dimana n adalah jumlah cabang pada masing-masing simpul. Begitu terus proses berlanjut dengan cara rekursif sampai pada daun atau tempat tujuan sehingga diperoleh bobot untuk masing-masing daun. Dengan suatu algoritma sederhana kita tentu dapat memilih solusi terbaik jika bobot untuk masing- masing solusi telah diperoleh. Hanya dengan mencari bobot minimum maka akan diperoleh solusi tebaik atau jalur tercepat dari titik awal sampai ke titik tujuan.