Peningkatan Performa Komputasi Sistem Navigasi Transportasi Publik Pada Perangkat Bergerak Melalui Penerapan Teknik Kompresi Data dan Penyederhanaan Graf
DOI:
https://doi.org/10.25126/jtiik.1078054Kata Kunci:
API, Dijkstra, Douglas-Peucker, kompresi, optimasi, transportasiAbstrak
Penelitian ini bertujuan untuk menyelesaikan permasalahan di bidang transportasi terkait penentuan rute perjalanan menggunakan transportasi umum dengan mengembangkan sistem dan aplikasi perangkat bergerak yang mampu merekomendasikan rute perjalanan angkutan umum di kota Malang. Rekomendasi rute perjalanan dihasilkan dari penerapan algoritme Dijkstra dari rute transportasi angkutan umum di Kota Malang yang dimodelkan dalam struktur data graf. Bagian yang akan dinilai pada penelitian ini adalah perbandingan efektivitas penggunaan format JSON terutama pada penghematan bandwidth. Teknik kompresi yang digunakan pada penelitian ini adalah Zlib yang dikombinasikan dengan encoding Base64. Analisis juga dilakukan terhadap beban tambahan dan penggunaan memori akibat proses kompresi serta analisis waktu komputasi dan penggunaan memori akibat penyederhanaan struktur data graf melalui pendekatan visual dengan algoritme Douglas-Peucker. Penggunaan dokumen dalam format JSON terbukti efektif digunakan sebagai media komunikasi, penggunaan kompresi data dapat menghemat penggunaan bandwidth untuk mendistribusikan data di Internet sebesar 64,61%, dan memberikan beban tambahan pada memori yang diperlukan oleh server untuk kompresi data sebesar 0,44%. Selain itu, dengan penyederhanaan graf secara visual, waktu proses yang diperlukan untuk merekomendasikan rute transportasi menjadi lebih singkat 81,24% serta berkurangnya penggunaan memori hingga 72,99%.
Abstract
This research aims to solve problems in the field of transportation related to determining travel plans using public transportation by developing systems and mobile applications based on Google Android that recommend public transport plans in Malang City. The plans are generated from the implementation of Dijkstra's algorithm, which is modeled in the graph data structure. This study determines the effectiveness of using JSON format, the bandwidth saved for distributing data on the Internet from Zlib data compression and Base64 encoding, and analyzes additional memory usage due to compression and the impact of data simplification through a visual approach on transport network graphs with the Douglas-Peucker algorithm. This study suggested that the use of JSON format is effective as a communication medium, and the use of data compression allows clients to save bandwidth usage by up to 64.61% with an additional 0.44% of memory load for data compression. Additionally, visually simplifying the graph data improved the system's performance; it reduced the average processing time to recommend transportation routes by 81.24% and reduced memory usage by up to 72.99%.
Downloads
Referensi
COOKSEY, BRIAN. 2014. Chapter 3: Data formats. Zapier. https://zapier.com/learn/apis/chapter-3- data-formats/
DOUGLAS, DAVID; PEUCKER, THOMAS 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer. 10 (2): 112–122. doi:10.3138/FM57-6770-U75U-7727.
FERRAGINA, P.I., NITTO, I. 2009. Text Compression. In: LIU, L., ÖZSU, M.T. (eds) Encyclopedia of Database Systems. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-39940-9_1151
FOEAD, D., GHIFARI, A., KUSUMA, M.B., HANAFIAH, N., & GUNAWAN, E., 2021. A Systematic Literature Review of A* Pathfinding. Procedia Computer Science, Vol. 179, pp. 507-514.
https://doi.org/10.1016/j.procs.2021.01.034.
FRIASWANTO, MELKI & LISANGAN, ERICK & SUMARTA, SEAN. 2021. The Simulation of Traffic Signal Preemption using GPS and Dijkstra Algorithm for Emergency Fire Handling at Makassar City Fire Service. International Journal of Applied Sciences and Smart Technologies. 3. 185-202. doi:10.24071/ijasst.v3i2.3821.
GUEDRI, HICHEM., BAJAHZAR, ABDULLAH., BELMABROUK, HAFEDH. 2021. ECG compression with Douglas- Peucker algorithm and fractal interpolation, [J]. Mathematical Biosciences and Engineering, 18(4): 3502-3520. doi: 10.3934/mbe.2021176
JILIN, CHEN., MIN, ZHAO., ZHONGHUA, GUO., WEIJIANG, QIU., YONG, CHEN., AND WEIXI, WANG. 2018. The Application of Douglas-Peucker Algorithm in Collaborative System for Power Grid Operation Mode Calculation. MATEC Web of Conferences 175.
JONES, THOMAS. 2021. What is an API Integration? (A guide for non-technical people). https://www.gend.co/blog/what-is-api-integration-a-guide-for-non-technical-people
KANJILAL, JODIP. 2017. Compressing Web API responses to reduce payload. InfoWorld. https://www.infoworld.com/article/3174597/compressing-web-api-responses-to-reduce- payload.html
KHARISMA, A. P., & PINANDITO, A. 2017. Design of REST API for Local Public Transportation Information Services in Malang City. Journal of Information Technology and Computer Science, 2(2). https://doi.org/10.25126/jitecs.20172226
KHARISMA, A. P., JONEMARO, E. M. A., & ARWANI, I. 2019. Paratransit Trip Data Collection System with Smartphone GPS and REST Web Service in Malang,
Indonesia. Indonesian Journal of Electrical Engineering and Informatics (IJEEI), 9(1). http://dx.doi.org/10.52549/ijeei.v9i1.2507
KHOTARI, VIVEK. 2023. Difference between JSON and XML. Geeks for Geeks. https://www.geeksforgeeks.org/difference-between-json-and-xml/
LAKHERA, SAKSHAM, AND PRAVEENA T. 2020. Visual Analysis using Modified Ramer-Douglas–Peucker Algorithm on Time Series Data.
International Research Journal of Engineering and Technology (IRJET), Vol. 07 (05), pp. 4225-4229
LIU, BO, XUECHAO LIU, DAJUN LI, YU SHI, GABRIELA FERNANDEZ, AND YANDONG WANG. 2020. A Vector Line Simplification Algorithm Based on the Douglas–Peucker Algorithm, Monotonic Chains and Dichotomy. ISPRS International Journal of Geo-Information, 9(4): 251. https://doi.org/10.3390/ijgi9040251
MDN. 2023. Introduction to web APIs. Mozilla Developer Network. https://developer.mozilla.org/en-US/docs/Learn/JavaScript/Client-side_web_APIs/Introduction
NAYAGAM, R. DEIVA., SELVATHI, D., GEETA, R., GOPINATH, D., AND SIVAKUMAR, G. 2023. Mobile Application based Indoor Positioning and Navigational System using Dijkstra's Algorithm.
Journal of Physics: Conference Series, Volume 2466, 4th National Conference on Communication Systems (NCOCS 2022), DOI 10.1088/1742-6596/2466/1/012007
OPHEIM, H. 1981. Smoothing a digitized curve by data reduction methods. Eurographics’ 81. Pp.127- 135.
PARULEKAR, M., PADTE, V., SHAH, T., SHROFF, K., AND SHETTY, R., 2013. "Automatic vehicle navigation using Dijkstra's Algorithm," 2013 International Conference on Advances in Technology and Engineering (ICATE), Mumbai, India, pp. 1-5, doi: 10.1109/ICAdTE.2013.6524721.
PINANDITO, ARYO. 2017. Framework Design for Modular Web-based Application Using Model- CollectionService-Controller-Presenter (MCCP) Pattern. Journal of Information Technology and Computer Science 2(1). DOI: 10.25126/jitecs.20172120
PINANDITO, ARYO AND WULANDARI, CHANDRAWATI PUTRI. 2021. Integrating douglas-peucker line simplification into routeboxer algorithm on a map-based Android application. In Proceedings of the 5th International Conference on Sustainable Information Engineering and Technology (SIET '20). Association for Computing Machinery, New York, NY, USA, 213–219. https://doi.org/10.1145/3427423.3427446
RACHMAWATI, D. & GUSTIN, L. 2020. Analysis of Dijkstra's Algorithm and A* Algorithm in Shortest Path Problem. J. Phys.: Conf. Ser. 1566 012061. doi:10.1088/1742-6596/1566/1/012061
REIN, LISA. 1998. Handling Binary Data in XML Documents. XML.com. https://www.xml.com/pub/a/98/07/binary/binary.html
REUMANN, K., AND WITKAM, A.P.M. 1974. Optimizing Curve Segmentation in Computer Graphics. International Computing Symposium. Amsterdam, North Holland, pp. 467-472.
ROSNER, FRANK. 2017. Hiding Complexity Does Not Make It Go Away, Or Does It?. Dev.to. https://dev.to/frosnerd/hiding-complexity-does-not-make-it-go-away-or-does-it-51i
RUAN, CHUANG., LUO, JIANPING., AND WU, YU 2014. Map navigation system based on optimal Dijkstra algorithm," 2014 IEEE 3rd International Conference on Cloud Computing and Intelligence Systems, Shenzhen, pp. 559-564, doi: 10.1109/CCIS.2014.7175798.
SALEM, I. E., MIJWIL, M. M., ABDULQADER, A. W., ISMAEEL, M. M. 2022. Flight-schedule using Dijkstra's algorithm with comparison of routes findings. Int J Elec & Comp Eng, Vol. 12(2), pp. 1675-1682. http://doi.org/10.11591/ijece.v12i2.pp1675-1682
SALOMON D., 2007. Data Compression: The Complete Reference, 4th edn., Springer, London.
SAMAH, ABU., FARIZA, KHYRINA AIRIN., & SHARIP, A. & MUSIRIN, PROFESSOR DR. ISMAIL & SABRI, N. & SALLEH, M. 2020. Reliability study on the adaptation of Dijkstra’s algorithm for gateway KLIA2 indoor navigation. Bulletin of Electrical Engineering and Informatics. 9. 10.11591/eei.v9i2.2081.
SARNACKI, PIOTR. 2013. Client and API isolation. Travis CI. https://blog.travis-ci.com/2013-03-13- client-and-api-isolation
SAYOOD, KHALID. 2018. Huffman Coding. Introduction to Data Compression (Fifth ed.).
SHI, WENZHONG & CHEUNG, CHUIKWAN. 2006. Performance Evaluation of Line Simplification Algorithms for Vector Generalization. Cartographic Journal, The. 43. pp. 27-44. doi:10.1179/000870406X93490.
SHIOTSU, YOSHITAKA. 2021. What Is PHP and Why Should You Use It?. Upwork Resource Center. https://www.upwork.com/resources/why-use-php
SINGH, Y., SHARMA, S., SUTTON, R., HATTON, D. 2018. Towards use of Dijkstra Algorithm for Optimal Navigation of an Unmanned Surface Vehicle in a Real-Time Marine Environment with results from Artificial Potential Field. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 12, No. 1, doi:10.12716/1001.12.01.14, pp. 125-131,
SUGIHARJA, DANUR DAN PAHLEVI, OMAR. 2019. The RPTRA Geographic Information System Application in Central Jakarta City Using the Dijkstra Algorithm Based on Android. Journal Publications & Informatics Engineering Research. Vol. 3, No. 2. pp. 56-60.
https://doi.org/10.33395/sinkron.v3i2.10043
SUJATHA RAJKUMAR, SHREYAS LOYA, DHRUV HARIBHAKTI, SIVAKUMAR SUBRAMANIAM. 2020. Pollution based Intelligent Navigation System using Dijkstra’s Algorithm. International Journal of Advanced Science and Technology, 29(3), 11242 - 11250. Retrieved from: http://sersc.org/journals/index.php/IJAST/article/view/28023
TUPITSIN, ANDREY; PUZRIN, VITALY. 2022. Pako. http://nodeca.github.io/pako/
TSCHABITSCHER, HEINZ. 2020. How Base64 Encoding Works. Lifewire. https://www.lifewire.com/base64-encoding-overview-1166412
Visvalingam, M., & Whyatt, J. D. (992. Line generalisation by repeated elimination of the smallest area. Cartographic Information Systems Research Group, University of Hull
VISVALINGAM, M. & WHYATT, DUNCAN. 2007. The Douglas‐Peucker Algorithm for Line Simplification: Re‐evaluation through Visualization. Computer Graphics Forum. 9. 213 - 225. 10.1111/j.1467- 8659.1990.tb00398.x.
WANG, XIAOFEI., ZHANG, JIE., YOU, LEI., 2021. A Douglas-Peucker Algorithm Combining Node Importance and Radial Distance Constraints. AIAM2021: 2021 3rd International Conference on Artificial Intelligence and Advanced Manufacture, pp. 265–269.
https://doi.org/10.1145/3495018.3495063
XU, YICHENG., WEN, ZHIGANG., ZHANG, XIAOYING. 2015. Indoor optimal path planning based on Dijkstra Algorithm. Proceedings of the 2015 International Conference on Materials Engineering and Information Technology Applications. pp. 309-313. https://doi.org/10.2991/meita-15.2015.57
ZHAO, Z., & SAALFELD, A. 2008. Linear-time sleeve-fitting polyline simplification algorithms. Cartogis. pp. 214-223.
ZHOU, M, & GAO, N. 2019. Research on Optimal Path based on Dijkstra Algorithms. Proceedings of the 3rd International Conference on Mechatronics Engineering and Information Technology (ICMEIT 2019). https://doi.org/10.2991/icmeit-19.2019.141
ZIV, JACOB; LEMPEL, ABRAHAM. 1977. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory. 23 (3): 337–343. CiteSeerX 10.1.1.118.8921. doi:10.1109/TIT.1977.105571.
Unduhan
Diterbitkan
Terbitan
Bagian
Lisensi
Hak Cipta (c) 2023 Jurnal Teknologi Informasi dan Ilmu Komputer
Artikel ini berlisensiCreative Commons Attribution-ShareAlike 4.0 International License.
Artikel ini berlisensi Creative Common Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
Penulis yang menerbitkan di jurnal ini menyetujui ketentuan berikut:
- Penulis menyimpan hak cipta dan memberikan jurnal hak penerbitan pertama naskah secara simultan dengan lisensi di bawah Creative Common Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) yang mengizinkan orang lain untuk berbagi pekerjaan dengan sebuah pernyataan kepenulisan pekerjaan dan penerbitan awal di jurnal ini.
- Penulis bisa memasukkan ke dalam penyusunan kontraktual tambahan terpisah untuk distribusi non ekslusif versi kaya terbitan jurnal (contoh: mempostingnya ke repositori institusional atau menerbitkannya dalam sebuah buku), dengan pengakuan penerbitan awalnya di jurnal ini.
- Penulis diizinkan dan didorong untuk mem-posting karya mereka online (contoh: di repositori institusional atau di website mereka) sebelum dan selama proses penyerahan, karena dapat mengarahkan ke pertukaran produktif, seperti halnya sitiran yang lebih awal dan lebih hebat dari karya yang diterbitkan. (Lihat Efek Akses Terbuka).
