BABI PENDAHULUAN 1.1
Latar Belakang Pencarian jalur tercepat saat melakukan perjalanan merupakan hal yang
perlu dilakukan. Pemilhan jalur tercepat bermanfaat untuk menghindari pusat keramaian [1], menjadikan waktu perjalanan lebih efektif seperti dalam mencari lokasi wisata [2] dan membantu mobil ambulan menuju rumah sakit [3]. Selain efektivitas waktu perjalanan, pemilihan jalur tercepat juga bermanfaat untuk meminimalkan biaya perjalanan karena semakin menghemat bahan bakar dan tenaga. Penelitian tentang pencarian jalur tercepat telah banyak dilakukan. Beberapa penelitian berusaha mencari algoritme terbaik seperti membandingkan algoritme Depth First, Breath First, dan Hill Climbing [4], membandingkan algoritme Exhaustive, algoritme Genetika dan algoritme Jaringan Syaraf Tiruan Hopfield untuk pencarian rute terpendek [5] , dan membandingkan algoritme Dijkstra dan algoritme Bellman-Ford pada jaringan grid [6]. Beberapa penelitian lain hanya mengaplikasikan algoritme yang sudah ada untuk mengatasi pencarian jalur tercepat seperti penggunaan graph separator untuk menghindari pusat keramaian [1], penggunaan algoritme Dijkstra dan Astar pada SIG berbasis web untuk pemetaan pariwisata kota Sawahlunto [2], pembuatan aplikasi untuk mencari jalur terpendek pada jaringan transportasi umum [7], perancangan algoritme Genetika untuk menentukan jalur terpendek [8], pencarian jalur terpendek menggunakan algoritme Semut [9], pembuatan aplikasi penentuan rute terbaik berbasis sistem informasi geografis [10], dan pembuatan aplikasi untuk mobil ambulan dalam mencari jalur tercepat menuju rumah sakit [3]. Algoritme Dijkstra merupakan algoritme yang sering digunakan dalam kasus pencarian jalur tercepat [11] . Algoritme Dijkstra adalah algoritme untuk mendapatkan
jalur terpendek dengan nilai bobot tiap jalur non-negatif [12].
Algoritme ini menyelesaikan suatu permasalah dalam memilih rute perjalanan dengan menghasilkan satu rute [13], dari lokasi awal menuju lokasi tujuan [14], 1
untuk mendapatkan rute terdekat, tercepat ataupun termudah [15]. Berdasarkan penelitian yang telah dilakukan, nilai bobot tiap ruas jalur pada algoritme Dijkstra telah ditetapkan terlebih dahulu sebelum melakukan pencarian rute. Pada kenyataanya, suatu ruas jalur memiliki waktu tempuh yang tidak tetap. Suatu ruas jalur biasanya memiliki waktu tempuh yang berbeda antara waktu padat dan waktu longgar. Dengan demikian penggunaan nilai bobot
yang tetap akan
menghasilkan keputusan pemilihan rute yang kurang tepat. Oleh sebab itu diperlukan suatu metode untuk menghitung bobot jalur. Metode ini diharapkan mampu mengatasi ketidakpastian nilai bobot waktu ruas jalur pada algoritme Dijkstra. 1.2
Perumusan masalah Dari latar belakang diperoleh permasalahan pada penelitian ini. Pencarian
jalur tercepat dengan algoritme Dijkstra dilakukan dengan menggunakan nilai bobot ruas jalur yang bernilai tetap. Pada kenyataanya, waktu tempuh suatu ruas jalur bernilai tidak tetap. Oleh karena itu diperlukan metode perhitungan bobot ruas jalur yang dapat mengatasi nilai bobot suatu ruas jalur yang tidak tetap sehingga keputusan pemilihan rute lebih tepat. 1.3
Keaslian penelitian Penelitian yang dilakukan untuk mencari ketepatan pemilihan jalur tercepat
telah banyak dilakukan para peneliti. Pada bagian ini, diberikan kajian dari beberapa penelitian sebelumnya mengenai metode pencarian jalur tercepat. Kajian dilakukan untuk memberikan informasi mengenai perbedaan dan kebaruan antara penelitian-penelitian sebelumnya dengan penelitian yang dilakukan pada saat ini. Penelitian yang dilakukan oleh Feddy dan Anggraini [4] mengenai metode pencarian rute terpendek dilakukan dengan melakukan perbandingan algoritme Depth First, Breath First, dan Hill Climbing dengan menggunakan bahasa C. Penelitian tersebut menghasilkan kesimpulan banhwa algoritme terbaik untuk mendapatkan rute terpendek dan paling efektif adalah algoritme Breadth First dan algoritme Hill Climbing. Selanjutnya pada penenelitian yang dilakukan oleh 2
Rudy, dkk. [5] dengan membandingkan algoritme Exhaustive, algoritme Genetika dan algoritme Jaringan Syaraf Tiruan Hopfield untuk pencarian rute terpendek dengan menggunakan bahasa pemrograman Borland Delphi 7. Penelitian tersebut menghasilkan kesimpulan bahwa secara umum algoritme Genetika bekerja lebih cepat dari kedua algoritme pembandingnya. Penelitian yang dlakukan oleh Ardi [16] tentang pencarian jalur terpendek dilakukan dengan membandingkan algoritme Jaringan Syaraf Tiruan metode kohonen self-organizing maps dengan algoritme Jaringan Syaraf Tiruan metode boltzmann machine. Penelitian tersebut menghasilkan bahwa metode boltzmann machine menghasilkan kinerja lebih optimal dan cepat dari metode kohonen self-organizing maps. Dari ketiga penelitian yang telah dilakukan tersebut masih menggunakan nilai bobot jalur yang telah ditetapkan dan bernilai statis. Penelitian dengan membandingkan algoritme Dijkstra dengan algoritme lain dilakukan oleh Michi [6] dan Yudhi, dkk. [17] menunjukkan bahwa algoritme Dijkstra memiliki pencarian jalur yang lebih cepat dibandingkan dengan algoritme Bellman-Ford, floyd, dan algoritme two queues. Selain membandingkan algoritme Dijkstra dengan algoritme lain, penelitian dengan memperbaiki algoritme Dijkstra juga telah dilakukan. Hanafi, dkk. [18] melakukan modifikasi algoritme Dijkstra dengan menggunakan algoritme Fuzzy. Algoritme Fuzzy digunakan untuk mencari nilai bobot jalur tiap ruas jalur dengan parameter panjang jalan dan kepadatan jalur. Penggunaan algoritme tesebut digunakan untuk mengatasi keadaan kepadatan jalan yang berubah-ubah. Namun demikian, nilai kepadatan jalan yang digunakan hanya dikategorikan menjadi tiga keadaan yaitu keadaan padat, normal, dan longgar. Dengan demikian maka hasil yang didapatkan masih kurang tepat karena akan sulit mengatasi apabila kepadatan jalan memiliki nilai kepadatan yang berbeda namun masih dalam satu kelompok keadaan. Penelitian lain yang dilakukan oleh Zang, dkk.[19] melakukan modifikasi algoritme Dijkstra dengan menambahkan variabel kepadatan jalan. Penambahan variabel tersebut dilakukan untuk mencari nilai bobot jalur agar sesuai dengan kondisi nyata jalan. Namun demikian penelitian tersebut menggunakan nilai bobot jalur yang tetap dan bersifat statis. Dengan demkian penelitian yang dilakukan hampir sama 3
dengan penelitian yang dilakukan oleh Hanafi, dkk [18]. Selain itu, penelitian yang dilakukan oleh Siddharta, dkk. [20] juga melakukan modifikasi algoritme Dijkstra. Modifikasi tersebut dilakukan dengan menggunakan multigraph untuk menggambarkan keadaan jalan yang lebih nyata. Namun demikian, nilai bobot tiap ruas jalur yang digunakan masih tetap dan bersifat statis. Penelitian untuk mengatasi keadaan ruas jalur yang dinamis telah dilakukan. Lukman, dkk. [21] melakukan penelitian dengan memodifikasi algoritme Dijkstra dengan menambahkan nilai koefisien tiap ruas jalur sehingga bobot ruas jalur ditentukan tidak hanya berdasarkan panjang ruas jalur. Untuk mengatasi keadaan ruas jalur yang dinamis, dilakukan update nilai koefisien setiap saat. Server melakukan update data secara realtime untuk memberikan informasi ke administrator. Kemudian administrator melakukan perhitungan nilai bobot jalur tiap ruas jalur. Namun demikian, cara ini akan mengalami kesulitan karena dilakukan secara manual. Penelitian lain dilakukan oleh Xiaoge, dkk [22] untuk mengatasi keadaan ruas jalur yang dinamis. Namun penelitian ini hanya membandingkan algoritme Amoeba, Bellman-Ford, dan Label Setting untuk mencari algoritme terbaik apabila keadaan ruas jalur berubah. Dari penelitian-penelitian yang telah ada sebelumnya belum menunjukkan metode yang baik untuk mengatasi keadaan ruas jalur yang dinamis. Pada penelitian
ini
dikembangkan
algoritme
Dijkstra
dengan
melakukan
pengelompokan waktu keadaan jalan berdasarkan kecepatan rata-rata pengguna jalan. Pengelompokan tersebut dimaksudkan agar nilai bobot ruas jalur yang digunakan sesuai dengan kondisi waktu keberangkatan. Kecepatan rata-rata dan panjang ruas jalan digunakan untuk menghitung bobot waktu tempuh tiap ruas jalur. Dengan demikian maka nilai bobot ruas jalur yang digunakan menyesuaikan keadaan jalan pada saat waktu keberangkatan, sehingga diharapkan pemilihan rute akan lebih tepat.
4
1.4
Tujuan Penelitian Tujuan utama dari penelitian ini adalah untuk meningkatkan ketepatan
pemilihan rute algoritme Dijkstra pada kasus pencarian jalur tercepat dengan memperbaiki perhitungan bobot jalur. 1.5
Manfaat Penelitian Manfaat yang diharapkan dari penelitian ini adalah dapat menentukan jalur
tercepat yang lebih tepat untuk menunju tempat tujuan, efisiensi waktu perjalanan, dan meminimalkan biaya perjalanan.
5
