Study Kasus Tentang Jaringan Jalan Untuk Menentukan Rute Terpendek

Perancangan Pencarian Rute Terpendek pada Tempat Wisata di Bangka

Waktu dan biaya akan menjadi isu paling penting yang sangat diperhitungkan apabila seseorang akan melakukan perjalanan, baik itu perjalanan wisata, perjalanan kerja, dll. Karena tidak ada seorang pun yang mengenal semua wilayah yang akan dia datangi maka akan sangat sulit sekali untuk menemukan sebuah rute cepat menuju tempat tujuan anda. Dalam menentukan biaya serta informasi tempat wisata secara detail, digunakan algoritma Greedy untuk optimasi kunjungan tempat wisata.

Algoritma ini bekerja dengan mencari jalur terpendek antara setiap node dan menempatkannya pada solusi yang disediakan. Pada tugas penelitian ini, informasi yang diperlukan sistem sebagai input adalah tempat wisata. Setiap pengguna dapat memasukkan tempat wisata yang akan dia kunjungi. Kemudian sistem akan menerima inputan  tersebut dan menghitung jarak yang akan di lalui sebagai rute tercepat yang dipilih. dan keluaran yang diterima oleh pengguna dapat berupa  rute terpendek menuju tempat tujuan anda. Sehingga diharapkan, setiap pengguna dapat mengetahui informasi secara detail pada setiap kunjungan wisatanya.

A.    METODE PENELITIAN

Penelitian ini dilakukan dengan langkah-langkah sebagai berikut :

1.      Memilih dan merumuskan masalah

2.      Melakukan observasi dan wawancara

3.      Menelusuri sumber-sumber kepustakaan

4.      Melakukan analisis data

5.      Membuat laporan

Algoritma Greedy

Menurut Selly Yuvita yang ditulis pada (Makalah, 2010), Dalam bahasa Inggris, Greedy berarti rakus, tamak, atau loba. Definisi ini sangat sesuai dengan prinsip algoritma Greedy, yaitu “take what you can get now!”. Prinsip ini menggambarkan algoritma Greedy yang akan mengambil keputusan yang terbaik pada setiap langkah penyelesaian, tanpa memperhitungkan akibatnya pada keseluruhan permasalahan. Akan tetapi, agar algoritma Greedy benar-benar dapat menyelesaikan masalah optimasi, pada setiap langkah harus dibuat keputusan terbaik. Algoritma  Greedy merupakan salah satu algoritma yang sering digunakan untuk memecahkan permasalahan optimasi. Pada setiap langkah, kita harus membuat pilihan optimum lokal (local optimum), yang dapat diartikan sebagai keputusan terbaik yang diambil pada langkah tersebut. Karena algoritma  Greedy biasanya dilakukan dalam beberapa langkah, maka dalam satu permasalahan optimasi kita akan membuat beberapa pilihan optimum lokal, sesuai dengan banyaknya langkah yang harus dilakukan. Diharapkan bahwa setiap kali diambil pilihan optimum lokal, langkah-langkah setelahnya akan mengarah ke solusi optimum global. Perlu diingat bahwa algoritma  Greedy hanya memakai dua macam persoalan optimasi, yaitu maksimasi (maximization) dan minimasi (minimization).

Pada algoritma Greedy, ada beberapa elemen yang harus diperhatikan, yaitu :

1.        Himpunan kandidat (C)

Himpunan ini berisi elemen-elemen pembentuk solusi.

2.        Himpunan solusi (S)

Himpunan ini berisi kandidat-kandidat yang terpilih sebagai solusi dari permasalahan optimasi yang akan diselesaikan

3.        Fungsi seleksi

Fungsi ini akan memilih kandidat yang paling memungkinkan untuk mencapai solusi optimal. Sesuai dengan prinsip algoritma  Greedy, kandidat yang sudah dipilih pada suatu langkah tidak bisa diubah di langkah selanjutnya.

4.        Fungsi kelayakan

Fungsi ini akan memeriksa kelayakan suatu kandidat yang telah dipilih. Dalam arti, kandidat tersebut dan himpunan solusi yang terbentuk tidak melanggar constraints yang ada. Bila kandidat layak, maka kandidat tersebut akan dimasukkan ke dalam himpunan solusi, dan jika kandidat tersebut tidak layak, maka kandidat akan dibuang dan tidak akan dipertimbangkan lagi dalam pencarian solusi optimum.

5.        Fungsi obyektif

Fungsi ini akan membuat nilai solusi maksimum atau minimum, sesuai dengan jenis optimasi apa yang dibutuhkan.

Dengan kata lain, algoritma  Greedy akan melakukan pencarian sebuah himpunan bagian S dari himpunan kandidat C. Himpunan bagian S harus memenuhi beberapa criteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimisasi oleh fungsi obyektif.

Teori Graf

Menurut Deiby T. Salaki (Suatu Graf  G=(V,E)  didefinisikan sebagai pasangan himpunan  sisi dan simpul dengan V(G) = Himpunan simpul {v1, v2, ... , vn} dan E(G) = Himpunan sisi {e1, e2, ... , en}.

Setiap sisi berhubungan dengan satu atau dua simpul.  Dua buah simpul dikatakan berhubungan atau bertetangga (adjacent) jika ada sisi yang menghubungkan  keduanya. 

Berdasarkan orientasi yang ada pada sisinya, graf dapat dikelompokkan menjadi dua yaitu: Graf    berarah  (direct  graf) yaitu graf yang setiap sisinya diberikan arah sehingga untuk dua simpul  vi  dan  vj, maka  (vi,vj       vj,vi) dan graf tak berarah (undirect graf) yaitu graf yang sisinya tidak mengandung arah sehingga untuk dua simpul  vi  dan  vj, maka  (vi,vj) (vj,vi). Selain itu juga dikenal graf berbobot yaitu graf yang  sisinya memiliki bobot atau (Ahuja et al, 1993)..

Graf  (graph) adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Graf trival (satu titik tampa sisi satu pun) Jenis graf antara lain :

1.      Berdasarkan ada tidaknya sisi ganda

a.       Graf Sederhana

b.      Graf Tidak Sederhana

-       Graf ganda (multigraf)

-       Graf semu(pseudograf) adalah graf yang mengandung gelang (loop)
      graf sedrehana --> graf ganda
      graf ganda -x-> graf sederhana

2.      Berdasarkan orientasi arah

a.       Graf tak berarah (undirect graf) adalah graf yang orientasi sisinya tidak mempunyai arah

b.      Graf berarah(direct graf) adalah graf orientasi sisinya mempunyai arah sisi yang berarah

Terminologi dasar

2.      Bertetangga (adjacent) adalah 2 buah graf yang terhubung langsung dengan sebuah sisi.

3.       Bersisian (insident) adalah sembarang sisi yang bersisian dengan simpul u dan v

4.      Simpul terpencil (isolated vertex)  adalah simpul yang tidak bertetanggaan dengan simpul2 lainnya

5.      Graf kosong (null graph or empty graph) adalah graf yang himpunan sisinya adalah himpunan kosong

6.      Derajat (degree) adalah suatu simpul pada graf takberarah adalah jumlah sisi yang bersisian dengan simpul tersebut

7.      Lintasan (path) adalah panjang dari simpul awal hingga akhir

8.      Siklus (cycle)/ sirkuit (circuit) adalah lintasan yang berawal dan berahir pada simpul yang sama

9.      Terhubung (connected) adalah dua simpul yang terhubung

10.  Upagraf (subgraph) --> dan komplemen upagraf

11.  Upagraf merentang (spanning subgraf)

12.  Cut set.

13.  Graf berbobot (Weight graph) adalah graf yang setiap sisinya diberi sebuah harga (bobot)

-          Graph dual (dual graph)

Adalah graf yang terbentuk dengan cara penggambaran di titik luar dari graf yang asli.

-          Lintasan dan sirkuit euler

Lintasan euler adalah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. bila lintasan tersebut kembali ke asal, sehingga membentuk lintasan tertutup maka disebut sirkuit euler.

-          Lintasan dan sirkuit Hamilton

Lintasan hamilton adalah lintasan yang melalui tiap simpul didalam graf tepat satu kali. bila lintasan itu kembali ke asal membentuk lintasan tertutup(sirkuit), maka lintasan tersebut adalah sirkuit hamilton.
setiap graf lengkap adalah graf hamilton

-          Lintasan terpendek (shortest path)

Graf yang digunakan mencari lintasan terpendek adalah graf berbobot (weighted graph).
ada beberapa macam persoalan lintasan terpendek antara lain :
1. Lintasan terpendek antara 2 buah simpul tertentu
2. Lintasan terpendek antara semua pasangan simpul
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.