TEORI GRAF DAN IMPLEMENTASINYA DALAM MENENTUKAN RUTE EFEKTIF PERJALANAN WISATA PDF

Preview

Summary

TEORI GRAF DAN IMPLEMENTASINYA DALAM MENENTUKAN RUTE EFEKTIF PERJALANAN WISATA Ilham Hendra Pratama1, Abiyoga Hendra Wijaya2 1 Universitas Amikom Yogyakarta [email protected] 2 Universitas Amikom Yogyakarta [email protected] ABSTRAK Makalah ini membahas tentang teori ...

Description

TEORI GRAF DAN IMPLEMENTASINYA DALAM MENENTUKAN RUTE EFEKTIF PERJALANAN WISATA Ilham Hendra Pratama1, Abiyoga Hendra Wijaya2 1 Universitas Amikom Yogyakarta [email protected] 2 Universitas Amikom Yogyakarta [email protected]

ABSTRAK Makalah ini membahas tentang teori graf dan implementasinya dalam mencari rute efektif perjalanan wisata. Makalah ini menyajikan tentang gambaran umum, definisi graf, hingga sampai pada tataran implementasi, yaitu bagaimana teori graf diterapkan dalam bidang pemetaan khususnya dalam menentukan rute efektif dalam melakukan perjalanan wisata. Penentuan rute efektif termasuk dalam kategori kasus Traveling Salesman Problem (TSP), untuk menyelesaikan kasus tersebut dapat menerapkan jenis penyelesaian dengan algoritma Best-First Search (BEFS). Dalam penerapan algoritma Best-First Search dapat menghasilkan berupa solusi rute terbaik yang dapat dilalui agar perjalanan wisata menjadi lebih efisien. Kata Kunci : graf,peta,rute,TSP,BEFS.

ABSTRACT This paper discusses graph theory and its implementation in finding effective travel routes. This paper presents a general description, definition of graph, up to the level of implementation, namely how graph theory is applied in the field of mapping, especially in determining the best route in carrying out travel. Determining effective routes is included in the category of Traveling Salesman Problem (TSP), to solve the case can apply the type of settlement with the Best-First Search (BEFS) algorithm. In applying the Best-First Search algorithm it can produce the best route solution that can be passed so that travel becomes more efficient. Keywords : graph, map, route, TSP, BEFS.

PENDAHULUAN Graf adalah salah satu materi dalam matematika diskrit, graf digunakan untuk memberikan visualisasi atau gambaran antar objek yang disimbolkan dengan titik dan dihubungkan dengan garis. Graf merupakan struktur diskrit yang terdiri atas dua himpunan, yakni himpunan titik/simpul (vertex) dan himpunan sisi (edge), biasa dinotasikan G(V,E). V merupakan notasi himpunan (tak kosong) berhingga, obyek yang selanjutnya dinamakan titik/simpul (vertex) dan E adalah notasi dari himpunan sisi (edge) yang menghubungkan dua simpul di himpunan V.

1

Graf dibagi menjadi : 1.

Sederhana (tidak memiliki unsur sisi yang ganda).

Gambar 1. Graf Sederhana

2.

Ganda (tidak memiliki pengulangan).

Gambar 2. Graf Ganda

3.

Semu (mengandung perulangan).

Gambar 3. Graf Semu

Di dalam graf terdapat juga istilah yang digunakan untuk membedakan dengan graf yang lain yaitu : 1. Bertetangga (Adjecent) Memiliki sisi yang saling terkait antar dua titik.

Gambar 4. Bertetangga

2

2. Beririsan (Incidency) Memiliki sisi yang saling terkait dengan dua titik dan dapat dikatakan dengan simbol e = (v1,v2).

Gambar 5. Beririsan

3. Simpul Terpencil (Isolated Vertex) Tidak beririsan dan tidak bertetangga.

Gambar 6. Simpul Terpencil

4. Derajat Jumlah sisi yang saling terkait dengan simpul.

Gambar 7. Derajat

Dengan kemampuannya dalam menyelesaikan kasus, teori graf terus berkembang dan banyak diterapkan dalam berbagai permasalahan. Salah satu permasalahan yang biasa digunakan adalah pencarian rute efektif perjalanan, dimana masalah penentuan rute efektif perjalanan dapat dikategorikan sebagai kasus Traveling Salesman Problem (TSP).

3

Pencarian rute efektif merupakan hal yang cukup rumit. Permasalahan kasus pencarian rute efektif adalah mencari rute untuk mengunjungi beberapa tempat tujuan dan kembali lagi ke titik keberangkatan. Terdapat banyak algortima yang dapat digunakan untuk mencari rute efektif, diantaranya algoritma Dijkstra, algoritma Best-First Search dan algoritma A Star (A*). Pemilihan algoritma Best-First Search untuk menentukan rute efektif karena dinilai lebih baik dibandingkan dengan algortima atau metode yang lain, algoritma Best-First Search bekerja dengan mementingkan pemeriksaan titik - titik yang berurut dan berada pada arah yang benar, sehigga dapat lebih memberikan hasil yang maksimal untuk mencari rute yang paling efektif. Travelling Salesman Problem (TSP) adalah persoalan yang berhubungan dengan kombinasi permasalahan. Dalam melakukan pemecahan pada persoalan Travelling Salesman Problem dapat dengan representasi graf yang mana beberapa persoalan dapat diselesaikan dengan permodelan tersebut. Contoh Permasalahan Travelling Salesman Problem adalah mencari rute tercepat suatu perjalanan wisata ke beberapa titik, dengan tujuan untuk menekan angka pengeluaran biaya transportasi. Dan persoalan yang muncul setelah itu adalah bagaimana agar titik awal dalam sebuah graf dapat menemukan rute tercepat dengan ketentuan harus melewati titik yang lain dan kembali ke titik semula. Bobot yang digunakan sendiri berarti berapa biaya minimum, jarak minimum, banyak bahan bakar, dan waktu yang terpakai dan lain sebagainya. Dalam melakukan implementasi teori Travelling Salesman Problem yaitu dengan mencari jumlah jalur yang mungkin akan dilalui dengan menggunakan rumus permutasi yaitu

Gambar 8. Rumus Permutasi

Yang mana n adalah kuantitas dari seluruh titik dan k merupakan jumlah titik yang terseleksi. Jenis – jenis Travelling Salesman Problem, antara lain : 1.

Asimetris Merupakan jenis TSP yang jumlah jalurnya adalah hasil dari permutasi jumlah titik dibagi jumlah titik. Sebagai contoh jika terdapat urutan n123 = n231 = n312 maka jalur n123 tidak sama dengan 321.

4

2.

Simetris Merupakan jenis TSP yang mana jumlah jalusnya adalah hasil dari permutasi jumlah titik dibagi dengan 2x jumlah titik. Sebagai contoh jika terdapat urutan n123 = n231 = n321 dikarenakan biaya rute dari n12 = n21 maka jalur dengan urutan n123 itu sama dengan n321 Sejarah Travelling Salesman Problem diawali adanya permaslahan mengenai

Travelling Salesman Problem telah dikemukakan oleh matematikawan yang berasal dari Irlandia yang bernama William Rowan Hamilton dan juga Matematikawan yang berasal dari Inggris dengan nama Thomas Penyngton. Di dalam Travelling Salesman Problem ada beberapa jenis Algoritma yang dapat digunakan untuk memecahkan masalah diantaranya yaitu : 1.

Branch and Bound Algoritma yang penyelesaiannya tidak mempertimbangkan satu demi Satu. Dalam implementasinya, algoritma ini sebenarnya ditujukan untuk melakukan perhitungan pemrograman linier. Akan tetapi dalam implementasi ke depannya ternyata metode ini dapat menyelesakan permasalahan yang berkaitan dengan Travelling Salesman Problem. Dalam proses pengerjaannya, metode ini menerapkan pohon pencarian yang mana tiap titik pada pohon merepresentasikan dari jumlah kemungkinan solusi yang dapat diterapkan untuk memecahkan masalah dalam Travelling Salesman Problem.

2.

Nearest Neighbor Algoritma heuristic yang dalam hasil implementasinya mendapatkan sebuah hasil yang optimal. Dalam memecahkan masalah algoritma ini memulai dengan mencari titik – titik dan kemudian mencari titik terdekat untuk menghubungkannya dan ditambahkan dengan titik terdekatnya lagi hingga membentuk sebuah rute yang mengarah kembali ke titik semula.

3.

Cutting Plane Algoritma yang merupakan perkembangan dari permasalahan program integer linier yang berawal optimal. Agar dapat mengerti perbedaan diantara algoritma - algoritma yang ada maka

disajikan tabel mengenai kelebihan dan kekurangan dalam melakukan penyelesaian permasalahan yang terkait dengan TSP.

5

Tabel 1. Kelebihan Dan Kekurangan Algoritma

Algoritma Branch and Bound

Kelebihan 1. Dalam

Kekurangan

memberikan

solusi,

hasil

yang

1. Dalam menyelesaikan masalah, Branch

and

diberikan berupa hasil

membutuhkan

yang optimal.

relatif lebih lama. 2. Tingkat

Bound

waktu

kesulitan

yang

dalam

melakukan penyelesaian cukup rumit. 3. Dan

memiliki

kompleksitas

waktu yang dapat dirumuskan (n-1)!. Nearest Neighbor

1. Dalam menyelesaikan masalah,

Nearest

membutuhkan relative

singkat

waktu

menimbulkan solusi yang tidak

lebih

optimal dan juga hasil yang

dibandingkan

dengan yang lain. 2. Tingkat

terjadi dengan banyak titikyang harus dikunjungi maka akan

Neighbor

yang

1. Apabila dalam kasus persoalan

kurang bermutu. 2. Sama seperti Branch and Bound

kemungkinan

yaitu memiliki kompleksitas

terjadi

sebuah

waktu yang dapat dirumuskan

kesalahan

ditekan

(n-1)!.

hingga sangat kecil 3. Dalam

melakukan

pengerjaan

atau

penyelesaian masalah, prosesnya lebih mudah. Cutting Plane

1. Solusi

dalam

1. Dalam melakukan penyelesaian

memecahkan

masalah

masalah, pengerjaan atau proses

lebih

optimal

pemecahan masalahnya sangat

dibandingkan

dengan

lama.

algoritma yang lain.

6

2. Untuk menggunakan algoritma ini,

haruslah

beberapa

menguasai pemrograman

computer.

METODE PENELITIAN Identifikasi permasalahan dalam makalah ini adalah menentukan rute efektif perjalanan wisata dengan menggunakan metode Traveling Salesman Problem (TSP), dimana algoritma yag digunakan adalah algoritma Best-First Search. Penelitian di awali dengan studi kepustakaan yaitu mengumpulkan referensi baik dari buku, jurnal maupun makalah tentang teori graf serta referensi lainnya yang menunjang tercapainya tujuan penelitian. Selanjutnya, metode yang digunakan dalam melaksanakan penelitian adalah dengan metode studi kasus, dimana peneliti melakukan penelitian untuk mengumpulkan data dan informasi yang dapat menunjang penelitian. Subyek dalam penelitian ini adalah algoritma Best-First Search guna menentukan rute efektif perjalanan wisata. Peneliti melakukan pengumpulan data dan informasi nama - nama objek wisata yang berada di kota Yogyakarta. Sumber data yang digunakan adalah peta Kota Yogyakarta, dimana objek wisata yang dipilh adalah objek wisata yang memiliki jarak cukup dekat dengan Universitas Amikom Yogyakarta. Setelah pengumpulan data metode selanjutnya yang dilakukan adalah metode analisis hasil penyelesaian masalah penentuan rute efektif perjalanan wisata secara manual dengan algoritma Best-First Search. Pembahasana inti dari penelitian ini adalah menentukan rute efektif perjalanan wisata menggunakan algoritma Best-First Search. Peneliti mencari rute efektif dari beberapa objek wisata yang cukup dekat dengan Universitas Amikom Yogyakarta. Selanjutnya, permasalahan akan direpresentasikan ke dalam bentuk graf dan kemudian dilakukan penghitungan dengan menggunakan algortma Best-First Search.

HASIL DAN PEMBAHASAN Bahan penelitian yang digunakan adalah peta Kota Yogyakarta, dimana pada peta tersebut diberikan titik untuk menandai tempat wisata dan garis sebagai penghubung antar titik. Berdasarkan peta Kota Yogyakarta, dapat dibuat menjadi graf seperti pada gambar.

7

Gambar 9. Peta Wisata Kota Yogyakarta

Implementasi dalam graf dapat di visualkan seperti pada gambar.

Gambar 10. Graf Peta Wisata Kota Yogyakarta

Pada gambar 10 merupakan graf berbobot tak berarah yang terdiri simpul 1 atau A adalah Universitas Amikom Yogyakarta, simpul B, C, D, secara berurutan mewakili Benteng Vandenberg, Sindu Edu Park, dan Monumen Yogya Kembali (Monjali). Penelitian ini menggunakan bobot berupa jarak (dalam kilometer) dan mengabaikan kemacetan atau arus lalulintas. Dalam melakukan penentuan rute efektif yang dapat dilalui jika titik keberangkatan di simpul A, maka dari itu menghitung siklus hemilton di dalam graf lengkap dengan n simpul yaitu : (n -1)! /2. Graf di atas memiliki (4-1)!/2 = 3 dengan siklus yang dapat digambarkan melalui table sebagai berikut :

8

Tabel 2. Penghitungan Siklus

Siklus

Rute

Panjang

Jarak Tempuh

Siklus 1

A-B-C-D-A

10.4 + 5.3 + 4.5 + 8.3

28.5

Siklus 2

A-C-B-D-A

10.3 + 5.3 + 10.3 + 8.3

34.2

Siklus 3

A-C-D-B-A

10.3 + 4.5 + 10.3 + 10.4

35.5

Berdasarkan table x dapat dilihat bahwa rute efektif ada pada siklus 1 dengan total jarak 28.5 kilometer. Dengan awal titik dari Universitas Amikom Yogyakarta lalu ke Benteng Vandenburg lalu ke Sindu Education Park lalu menuju ke Monument Yogya Kembali dan menuju titik awal yaitu Universitas Amikom Yogyakarta.

KESIMPULAN Berdasarkan hasil penelitian yang telah dilakukan, peneliti dapat menyimpulkan bahwa rute efektif dalam melakukan perjalanan wisata adalah dengan awal keberangkatan dari kampus Universitas Amikom Yogyakarta lalu menuju ke Benteng Vandenburg dengan jarak 10.4 kilometer dilanjutkan menuju Sindu Education Park dengan jarak tempuh dari Benteng Vandenburg 5.3 kilometer, selanjutnya ke Monumen Yogya Kembali dengan jarak 4.5 km dari Sindu Education Park, dan diakhiri dengan kembali ke Universitas Amikom Yogyakarta dengan jarak tempuh 8.3 Kilometer.

REKOMENDASI 1.

Acuan yang digunakan pada penelitian ini adalah berupa jarak (dalam satuan kilometer) dan mengabaikan permasalahan yang mungkin terjadi di jalan, seperti kemacetan arus lalu lintas, jalan yang ditutup dan kerusakan pada jalan. Diharapkan untuk penelitian selanjutnya dapat mempertimbangkan masalah - masalah yang mungkin terjadi baik berupa kemacetan lalu lintas maupun adanya masalah yang dapat menghambat perjalanan wisata.

2.

Untuk algoritma yang digunakan pada makalah ini adalah algoritma Best-First Search, diharapkan untuk penelitian selanjutnya dapat lebih menjelajahi algoritma yang lain yang mungkin dapat memberikan hasil yang lebih optimal dan akurat.

3.

Makalah ini hanya membahas penerapan algoritma Best-First Search secara manual, tanpa disertai simulasi secara komputasi, untuk penelitian selanjutnya diharapkan dapat

9

memberikan paparan yang lebih komprehensif yang disertai dengan simulasi secara komputasi menggunakan aplikasi. UCAPAN TERIMAKASIH Dalam melakukan penyusunan makalah ini, tidak lepas dari kontribusi dan bantuan dari banyak pihak, baik berupa saran, materi, semangat dan doa. Penulis mengucapkan puji syukur dan rasa terima kasih yang pertama kepada Tuhan Yang Maha Esa dikarenakan Ridho dan Berkah-Nya dalam memberikan kemudahan sehingga dalam proses penulisan makalah ini dapat berjalan dengan baik hingga penulisan selesai. Ucapan terima kasih kepada bapak Ferry Wahyu Wibowo, S.Si M.Cs selaku dosen Matematika Diskrit dan tak luput atas dukungan serta doa dari teman - teman.

REFERENSI Adiwijaya. (2016). Matematika Diskrit dan Aplikasinya. Bandung: Alfabeta.

Wibisono, Samuel. (2013). Matematika Diskrit. Yogyakarta : Graha Ilmu.

Nur, Rike . (2015). Implementasi Algoritma Best-First Search. Journal Online(digilib.uinsuka.ac.id), diakses pada tanggal 20 Oktober 2018.

10...