IJCCS, Vol.x, No.x, Julyxxxx, pp. 1~5 ISSN: 1978-1520
1
PENERAPAN ALGORITMA GREEDY UNTUK PENCARIAN JALUR TERPENDEK PADA JAKABARING SPORT CITY SECARA VIRTUAL REALITY M Jefri Anugerah1, M Hasbi2, M Rizky Pribadi3, Yoannita4 STMIK GI MDP; JL. Rajawali No.14 Palembang, 0711-376400 3 Jurusan Teknik Informatika, STMIK GI MDP, Palembang e-mail:
[email protected],
[email protected],
[email protected],
[email protected].
Abstrak Greedy merupakan salah satu algoritma yang dapat digunakan sebagai metode untuk mencari nilai optimasi. Penerapan algoritma ini digunakan untuk mengetahui apakah algoritma greedy dapat diterapkan untuk mencari jalur terpendek dari peta pada Jakabaring Sport City. Untuk mencapai suatu tempat dengan jarak yang dekat akan dicari lintasan terpendek dari tiap titik yang dibuat pada graf peta Jakabaring Sport City dengan jumlah titik sebanyak 149 titik. Lintasan terpendek ini akan memperhitungkan apakah titik yang dipilih bisa sampai pada tujuan atau tidak, apakah titik sudah pernah dilalui atau belum pernah dilalui, dan juga memberi batas maksimal titik yang boleh dilalui. Aplikasi ini dibangun menggunakan metodologi prototyping dan dibuat dengan menggunakan software Unity 3D dan Autodesk Maya serta didukung dengan teknologi berbasis virtual reality. Dari hasil pengujian penerapan algortima greedy dalam mencari lintasan terpendek yang dilakukan dengan cara pengujian black-box pada sistem yang dibangun didapatkan bahwa algoritma greedy ada yang dapat menunjukkan lintasan terpendek dan ada juga yang tidak menunjukkan lintasan terpendek. Dari hasil pengujian melalui kuesioner yang dibuat, didapatkan bahwa aplikasi ini memiliki lingkungan yang hampir menyerupai bentuk asli dari lingkungan Jakabaring Sport City. Kata kunci: Pencarian Jalur Terpendek, Greedy, Unity, Prototype, Virtual Reality Abstract Greedy algorithm is one that can be used as a method for finding the value of optimization. The application of this algorithm is used to find out if the greedy algorithm can be applied to find the shortest path from the map at the Jakabaring Sport City. To reach somewhere with the close proximity of the shortest path will be sought from each point made in graf map Jakabaring Sport City with a number of points as much as 149 points. This shortest path would take into account whether the selected point can get on purpose or not, whether the point has already been passed or have never traveled, and also gives the maximum limit point which can be traversed. This application was built using a prototyping methodology and created using the software Unity 3D and Autodesk Maya and supported by technology-based virtual reality. From the results of testing the application of greedy algorithms in finding the shortest path which is done by way of blackbox testing on systems that are built there greedy algorithm that was obtained by the shortest path can show and there is also the shortest path does not show. From the results of testing through a questionnaire that was made, that the application has obtained an environment that almost resemble the original form of environment Jakabaring Sport City. Received June1st,2012; Revised June25th, 2012; Accepted July 10th, 2012
2
ISSN: 1978-1520
Keywords: Shortest Path Search, Greedy, Unity, Prototype, Virtual Reality 1. PENDAHULUAN
J
akabaring Sport City adalah sebuah komplek olahraga di atas lahan seluas 325 hektar yang terletak di wilayah Seberang Ulu sejauh 5 km dari pusat kota Palembang. Jakabaring Sport City memiliki berbagai fasilitas gedung olahraga yang sering dikunjungi oleh para wisatawan maupun altlet yang ingin menuju ke lokasi gedung untuk melihat sebuah pertandingan cabang olahraga[1]. Biasanya alat bantu pencarian maupun petunjuk arah ke gedung – gedung olahraga di Jakabaring Sport City hanya berupa papan tulisan atau gambar petunjuk jalan, dan petunjuk jalan yang ada di jakabaring Sport City kurang lengkap dikarenakan masih kurangnya papan petunjuk arah di jalan – jalan Jakabaring Sport City. Hal itu pun sering membingungkan para wisatawan maupun atlet yang ingin menuju ke lokasi gedung olahraga yang ingin dituju tetapi tidak optimal. Semua itu terjadi dikarenakan alat petunjuk jalan tersebut hanya menampilkan papan tulisan atau gambar petunjuk arah dan itu tidak menggambarkan keadaan jalan yang sebenarnya. Dari permasalahan tersebut pengembang aplikasi menerapkan algoritma greedy untuk menentukan rute yang optimal untuk menuju ke lokasi gedung olahraga pada Jakabaring Sport City secara virtual reality guna membantu para wisatawan maupun atlet menuju ke lokasi gedung olahraga dengan cepat dan benar.
2. METODE PENELITIAN Metodologi prototyping merupakan metodologi penelitian yang mengekspresikan logika maupun fisik antarmuka eksternal yang ditampilkan. Konsumen potensial menggunakan prototyping dan menyediakan masukan untuk tim pengembang sebelum pengembangan skala besar dimulai. Adapun tahapan – tahapan yang dimiliki prototyping seperti perencanaan prototyping, mendesain prototyping, evaluasi prototyping, membangun sistem, menguji sistem, dan mengimplementasi sistem [3]. 2.1 Perencanaan Prototyping Pada tahap ini, pengembang aplikasi mengumpulkan kebutuhan berkaitan dengan aplikasi yang akan dibangun. Dimana meliputi jurnal-jurnal, buku-buku dan e-book yang berkaitan dengan penerapan algoritma Greedy, peta Jakabaring Sport City dan Virtual Reality. 2.2 Simulasi Penerapan Algoritma Greedy Simulasi algiritma greedy dilakukan dengan cara mengambil contoh persoalan seperti (Gambar.1) yang mensimulasikan cara kerja algoritma greedy untuk mencapai jalur terpendek dari titik 77 (H) ke titik 137 (C). Dalam simulasi yang dilakukan dijelaskan langkah -perlangkah cara kerja dari algoritma greedy.
IJCCS Vol. x, No. x, July201x : first_page–end_page
IJCCS
3
ISSN: 1978-1520
F 15
10 74
11
140
7
16
65
2 66
75
68
H
28
70
13 67
138
72
139
17 73 2
13
77 13
2
2 2 3
19 1 18
20 2
2 3 22 1 21
137
C
6 110
69
Keterangan: 1. Garis yang berwarna hitam 2. Garis yang berwarna merah 3. Garis yang berwarna biru
= Lintasan Satu Arah = Lintasan Dua Arah = Lintasan Terpendek
Gambar 1. Graf dari Titik 77 (H) ke 137 (C) Untuk mencapai jalur terpendek dari titik 77 (H) ke titik 137 (C) seperti garis berwarna biru yang merupakan jalur terpendek menuju titik 137 (C) dari titik 77 (H), yang didapat dari hasil hitung manual dari graf peta (Gambar 1). Langkah selanjutnya mencari jalur terpendek dengan menggunakan algoritma greedy. Berikut langkah - langkah Algoritma Greedy yang diterapkan: 1. Periksa apakah titik saat ini adalah titik awal. 2. Periksa apakah titik saat ini adalah titik tujuan. 3. Periksa titik yang terhubung dengan titik saat ini. 4. Periksa apakah titik selanjutnya adalah titik tujuan, jika bukan lanjut ke langkah (5). 5. Cari nilai local maximum ke titik selanjutnya. 6. Tandai titik sekarang sebagai titik yang telah dilalui, dan pindah ke local maximum yang telah ditentukan. 7. Periksa apakah titik selanjutnya sudah pernah dilalui, jika pernah dilalui titik tidak akan dipilih dan mundur ketitik sebelumnya. 8. Kembali ke langkah (1) sampai titik tujuan ditemukan. Jika menerapkan langkah - langkah di atas untuk menemukan rute terpendek dari persoalan graf peta (Gambar 1) yaitu dari titik 77 (H) ke titik 137 (C) maka akan didapat pergerakan sebagai berikut: 1. Mulai dari titik awal (titik 77) periksa apakah titik saat ini merupakan titik awal, dan apakah titik saat ini merupakan titik tujuan. 2. Ambil seluruh titik yang dapat dikunjungi dari titik saat ini dan periksa apakah titik berikutnya merupakan titik tujuan, jika bukan ambil nilai local maximum dari titik yang terhubung seperti (Gambar 2).
Title of manuscript is short and clear, implies research results (First Author)
4
ISSN: 1978-1520
2
77 73
2 2 3
19 1 18
13
2
2
3
2
22
137
20
1
21
6 110
23
Gambar 2. Langkah Pertama Greedy Local maximum yang dipilih adalah titik 19, karena jarak titik 19 adalah nilai yang paling dekat dari titik 77 seperti (Gambar 3). 77 73 2 137
2
13
19 1 18
2 2 3
20
2 3 2 22 1 21 6 110
23
Gambar 3. Langkah Kedua Greedy
3.
Berikutnya Tandai titik sekarang sebagai titik yang telah dilalui, dan pindah ke local maximum yang telah di tentukan yaitu 19 (Gambar 3) dan periksa apakah titik selanjutnya sudah pernah dilalui, jika pernah dilalui titik tidak akan dipilih dan mundur ketitik sebelumnya. Karena titik selanjutnya belum pernah dilalui dan juga bukan merupakan titik tujuan maka ulangi langkah seperti diawal, yaitu dari titik saat ini titik 19 ambil seluruh titik yang dapat dikunjungi dari titik saat ini dan periksa apakah titik berikutnya merupakan titik tujuan, jika bukan ambil nilai local maximum dari titik yang terhubung seperti (Gambar 4).
77 73 2 137
2
13
2 2 3
19 1 18
20 2
3
2
19 1 18
22 1 21
2 3
20 2 21
6 110
23
Gambar 4. Langkah Ketiga Greedy Local maximum yang dipilih adalah titik 18, karena jarak titik 18 adalah nilai yang paling dekat dari titik 19 seperti (Gambar 5).
IJCCS Vol. x, No. x, July201x : first_page–end_page
IJCCS
5
ISSN: 1978-1520
77 73 2
2
2 2 3
19 1 18
20
2 3 2 22 1 21
13
137
6 110
23
Gambar 5. Langkah Keempat Greedy
4.
Berikutnya Tandai titik sekarang sebagai titik yang telah dilalui, dan pindah ke local maximum yang telah di tentukan yaitu 18 (Gambar 5) dan periksa apakah titik selanjutnya sudah pernah dilalui, jika pernah dilalui titik tidak akan dipilih dan mundur ketitik sebelumnya. Karena titik selanjutnya belum pernah dilalui dan juga bukan merupakan titik tujuan maka ulangi langkah seperti diawal, yaitu dari titik saat ini titik 18 ambil seluruh titik yang dapat dikunjungi dari titik saat ini dan periksa apakah titik berikutnya merupakan titik tujuan, jika bukan ambil nilai local maximum dari titik yang terhubung seperti (Gambar 6). 2
77 73 2
2 2 3
19 1 18
13
3 2 22 1
137
20 2 21
6 110
23
Gambar 6. Langkah Kelima Greedy Local maximum yang dipilih adalah titik 73, karena jarak titik 73 adalah nilai yang paling dekat dari titik 18 seperti (Gambar 7). 77 73 2 137
2
13
19 1 18
2 2 3
20
2 3 2 22 1 21 6 110
23
Gambar 7. Langkah Keenam Greedy Berikutnya tandai titik sekarang sebagai titik yang telah dilalui, dan pindah ke local maximum yang telah di tentukan yaitu 73 (Gambar 7) dan periksa apakah titik selanjutnya sudah pernah dilalui, jika pernah dilalui titik tidak akan dipilih dan mundur ketitik sebelumnya.
Title of manuscript is short and clear, implies research results (First Author)
6 5.
ISSN: 1978-1520
Karena titik selanjutnya belum pernah dilalui dan juga bukan merupakan titik tujuan maka ulangi langkah seperti diawal. Dari titik saat ini yaitu titik 73 periksa apakah titik selanjutnya adalah titik tujuan. jika titik berikutnya merupakan titik tujuan maka pindah ketitik tersebut seperti (Gambar 8). 77 73 2 137
2
13
2 2 3
19 1 18
20 2
3
2
22
1
21
6 110
23
Gambar 8. Langkah Ketujuh Greedy Hasil akhir yang didapat sebagai jarak terpendek dari titik awal (H) ke titik tujuan 137 (C) (Gambar 8) adalah 77-19-18-73-137 dengan total jarak yg didapat 2 + 1 + 13 + 2 = 18. 2.3 Mendesain Prototyping Setelah tahap perencanaan dilakukan, maka tahapan selanjutnya adalah menganalisis alur sistem dan pembuatan rancangan sementara tentang aplikasi Jakabaring Sport City berbasis virtual reality. Dalam mendesain prototyping yang akan dirancang, maka dibuat perancangan sementara objek 3D bangunan dan gedung olahraga mengenai Jakabaring Sport City menggunakan aplikasi Autodesk Maya 2013, setelah membuat bentuk 3D yang telah dirancang di Autodesk Maya 2013 kemudian di import ke Unity yang telah ditata berdasarkan denah peta Jakabaring Sport City.
Gambar 9. Tampilan Gerbang Utama Jakabaring Sport City
Gambar 10. Tampilan Jakabaring Sport City dari Atas IJCCS Vol. x, No. x, July201x : first_page–end_page
IJCCS
ISSN: 1978-1520
7
2.4 Evaluasi Prototyping Pada tahap ini, desain prototyping yang sudah dirancang sementara dievaluasi lagi dengan penataan gedung apakah sudah sesuai dengan letak yang ada pada Jakabaring Sport City apabila belum sesuai maka dirancang lagi tata letak gedung sampai sesuai dengan denah peta Jakabaring Sport City serta penambahan tekstur rumput.
Gambar 11. Tampilan Tekstur Rumput 2.5 Membangun Sistem Pada tahap ini, setelah prototyping yang sudah dirancang dan dilakukan evaluasi tampilan aplikasi Jakabaring Sport City berbasis virtual reality. Selanjutnya dilakukan pengembangan aplikasi sesuai dengan kebutuhan berdasarkan GUI dan user friendly. Menu pilihan yang dirancang di Unity menggunakan button yang terdiri dari Peta, Informasi JSC, Daftar Gedung, Lihat Lokasi, Tentang, Tutorial, dan Exit.
Gambar 12. Tampilan Menu Utama 2.6 Menguji Sistem Pada setiap sistem yang telah dibangun pasti selalu dilakukan pengujian sebuah sistem guna membantu pengembang aplikasi dalam mengetahui apakah aplikasi sudah sesuai dengan yang diinginkan apa belum sesuai [3]. Pengujian sistem yang telah dibangun pada aplikasi Jakabaring Sport City berbasis virtual reality menggunakan pengujian black-box testing serta pengujian kuesioner.
Title of manuscript is short and clear, implies research results (First Author)
8
ISSN: 1978-1520 3. HASIL DAN PEMBAHASAN
3.1 Tampilan Aplikasi Antarmuka
(a)
(b)
(c)
(d)
Gambar 13. Tampilan Antarmuka Aplikasi Hasil dari sebagian tampilan aplikas yang telah di buat dapat di lihat pada (Gambar 13). Awal aplikasi berjalan aplikasi akan menampilkan sebuah lingkungan Jakabaring Sport City dalam bentuk visualisasi 3D seperti yang diperlihatkan pada (Gambar 13) (a), selajutnya user dapat menjalan kan aplikasi menuju menu utama dan dapat memilih menu yang ada di dalam aplikasi seperti yang diperlihatkan (Gambar 13) (b),(c),(d). 3.2 Kuesioner Terhadap Aplikasi Dari hasil keseluruhan kuesioner yang diperoleh dari 20 responden dapat dilihat pada (Gambar 14), (Gambar 15) dan (Gambar 16).
70%
0% 5%
25%
70%
65%
60% 35%
30% 0%10% 20% 0% 5%
75%
70%
65%
0% 5%
25%
0%10% 15% 0%20% 15% 0% 5%
TAMPILAN MENU TATA LETAK OBJEK 3D PADA PERPADUAN DESAIN PADA JENIS HURUF DAN APLIKASI UTAMA APLIKASI PILIHAN MENU APLIKASI VIRTUAL WARNA YANG APLIKASI VIRTUAL UKURAN HURUF MEMILIKI AREAMUDAH DAN TOMBOL REALITY DIGUNAKAN PADA REALITY SANGAT YANG AREA YANG DIMENGERTI PADA APLIKASI MENYERUPAI APLIKASI SANGAT MENARIK. DIGUNAKAN PADA NYATA DENGAN VIRTUAL REALITY BENTUK ASLINYA, SESUAI. APLIKASI SESUAI BENTUK ASLINYA. BAGUS DAN HAMPIR DAN MUDAH TELAH SESUAI DIKATAKAN DIBACA. MIRIP.
STS
TS
S
SS
Gambar 14. Grafik Keseluruhan Tampilan Antarmuka Aplikasi
IJCCS Vol. x, No. x, July201x : first_page–end_page
IJCCS
9
ISSN: 1978-1520
Pada (Gambar 14) merupakan grafik keseluruhan yang menggambarkan dari hasil pengujian pada bagian tampilan antarmuka aplikasi virtual reality.
85% 75%
70% 55% 40% 0% 5%
10%
APLIKASI VIRTUAL REALITY SANGAT MUDAH DIGUNAKAN.
0% 5%
25%
0% 5%
APLIKASI VIRTUAL REALITY YANG DIBUAT MUDAH DIPAHAMI.
STS
0% 5%
20%
INFORMASI YANG MELALUI APLIKASI DITAMPILKAN PADA VIRTUAL REALITY INI APLIKASI VIRTUAL PENGGUNA MENJADI REALITY DAPAT TAHU, MENGENAL, DAN MENAMBAH WAWASAN. PAHAM DENGAN PENGETAHUAN YANG DISAJIKAN. TS
S
SS
Gambar 15. Grafik Keseluruhan Kemudahan Penggunaan Aplikasi Pada (Gambar 15) merupakan grafik keseluruhan yang menggambarkan hasil dari pengujian kemudahan dalam mengunakan aplikasi.
55% 45% 45%
40%
30% 30% 0% 5%
0% 5%
0% 10%
ANDA PUAS DENGAN ANDA PUAS DENGAN MANFAAT APLIKASI APLIKASI YANG DIBUAT VIRTUAL REALITY YANG KARENA DAPAT TELAH DIBUAT. MENJADI APLIKASI PILIHAN ALTERNATIF SEBAGAI MEDIA PROMOSI WISATA. STS
TS
20%
10%
APLIKASI YANG DIBANGUN SANGAT MENGHIBUR.
S
0%
20%
ANDA AKAN MENGANJURKAN KEPADA ORANG LAIN UNTUK MENGGUNAKAN APLIKASI VIRTUAL REALITY YANG TELAH DIBUAT.
SS
Gambar 16. Grafik Keseluruhan Kepuasan Pengguna Aplikasi Pada (Gambar 16) merupakan grafik keseluruhan yang menggambarkan hasil dari pengujian pada kepuasan pengguna dalam mencoba aplikasi.
4. KESIMPULAN Pada penelitian ini didapatkan beberapa kesimpulan berdasarkan hasil proses pengembangan dan pengimplementasian, yaitu:
Title of manuscript is short and clear, implies research results (First Author)
10 1.
2.
ISSN: 1978-1520
Algoritma greedy yang diterapkan pada graf peta Jakabaring Sport City mampu menunjukan jalan terpendek dalam menuju beberapa gedung olahraga, walaupun tidak semua hasil yang didapatkan optimal. Dari hasil pengujian aplikasi Jakabaring Sport City berbasis virtual reality ini dapat menjadi salah satu alternatif sebagai media promosi dalam membantu memajukan wisata olahraga Jakabaring Sport City. 5. SARAN
Saran yang dapat direkomendasikan dalam pengembangan berikutnya pada aplikasi ini adalah: 1. Menambahkan jumlah gedung pada aplikasi seperti pembangunan venue di Jakabaring Sport City pastinya akan selalu bertambah karena banyaknya cabang olahraga yang selalu update dipertandingkan maka dari itu diharapkan aplikasi pastinya akan menambahkan juga venue 3D agar sesuai seperti aslinya. 2. Menambah pilihan menu online seperti Penambahan pilihan menu notification bersifat online akan membuat aplikasi lebih menarik dikarenakan dapat membantu user dalam mengetahui informasi atau jadwal sebuah event olahraga yang akan dipertandingkan. 3. Dari hasil analisis yang didapat untuk kasus penerapan pencarian jalur terpendek pada aplikasi virtual reality Jakabaring Sport City penerapan algoritma greedy kurang menghasilkan lintasan yang optimal dan disarankan dapat mencoba algoritma pencarian jalur terpendek yang lainnya. DAFTAR PUSTAKA
[1]Suzan 2015, Jakabaring Sport City, diakses Tanggal 11 Januari 2016, dari http://www.hellopalembang.com. [2] Munir, Rinaldi 2013, Algoritma Greedy. Program Studi Teknik Informatika ITB, Bandung. [3] Simarmata, Janner 2012, Rekayasa Perangkat Lunak, Andi Offset, Yogyakarta [4] Nurhayati, Enty, Antoni Yohanes 2014, Pencarian Rute Terpendek Menggunakan Algoritma Greedy, Seminar Nasional IENACO, Semarang. [5] Roedavan, Rickman 2014, Unity Tutorial Game Engine, Informatika, Bandung. [6]Bonafix, Dominicus Nunnun 2005, Animasi Profesional dengan Maya, Elex Media Komputindo, Jakarta. [7] Andra, Renusa Prayogo 2013, Penggunaan Algoritma Greedy dalam Penentuan Rute Wisata, Makalah IF2211 Strategi Algoritma, Bandung. [8] Nugroho, Adi 2010, Algoritma & Struktur Data Dengan C#, Andi Offset, Yogyakarta. [9] Nadya, Arieza 2013, Analisis Pengimplementasian Algoritma Greedy untuk Memilih Rute Angkutan Umum, Makalah IF2211 Strategi Algoritma, Bandung. [10] P, Yudhi M, Wamiliana dan Fitriani 2013, Perbandingan Program Dinamis dan Algoritma Greedy dalam Menyelesaikan Masalah Chinese Postman Problem, Prosiding Semirata FMIPA Universitas Lampung, Lampung. [11] Maximillian, Audrey Herli, Indra Kharisma Raharjana, Purbandini 2015, Sistem Pencarian Hotel Berdasarkan Rute Perjalanan Terpendek dengan Mempertimbangkan Daya Tarik Wisata Menggunakan Algoritma Greedy, Journal of Information Systems Engineering and Business Intelligence, Vol 1 , No 1, Surabaya. [12] Mediputra, Andika 2011, Pencarian Jalur Terpendek dengan Menggunakan Graf dan Greedy dalam Kehidupan Sehari-hari, Makalah IF3051 Strategi Algoritma, Bandung.
IJCCS Vol. x, No. x, July201x : first_page–end_page
