Improved Breadth First Search For Public Transit Line Search Optimization
DOI:
https://doi.org/10.12928/mf.v5i1.7906Keywords:
BFS, Route Search, Optimization, Improved BFS, PathAbstract
People in general find it difficult to determine the transportation route, because to get to one destination there are many alternative paths that must be passed. This study aims to model the search for alternative bus route routes that are faster to produce routes that must be passed. The method used in this study is Improved Breadth first search by modifying BFS so that its performance is improved in producing route search completion. The improved BFS method is basically the same as BFS doing a level-by-level search stop if a false finish point is found. As the experiment above with a starting point of 175 and an end point of 54 the BFS algorithm takes 27 seconds 564 milliseconds, while the Improve BFS algorithm takes 171 milliseconds. The results showed that improved BFS can improve the performance of the BFS method. Research can be a model to be applied to other optimal route finding cases.
References
E. Mogaji, I. Adekunle, S. Aririguzoh, and A. Oginni, “Dealing with impact of COVID-19 on transportation in a developing country: Insights and policy recommendations,” Transp Policy (Oxf), vol. 116, pp. 304–314, Feb. 2022, doi: 10.1016/j.tranpol.2021.12.002.
A. Mourad, J. Puchinger, and C. Chu, “A survey of models and algorithms for optimizing shared mobility,” Transportation Research Part B: Methodological, vol. 123, pp. 323–346, May 2019, doi: 10.1016/j.trb.2019.02.003.
D. Dwi Rita Nova and N. Widiastuti, “Pembentukan Karakter Mandiri Anak Melalui Kegiatan Naik Transportasi Umum,” Comm-Edu (Community Education Journal), vol. 2, no. 2, p. 113, May 2019, doi: 10.22460/comm-edu.v2i2.2515.
M. Agustien, E. Buchari, and dkk, “Sosialisasi Pelayanan Teman Bus Sebagai Upaya Meningkatkan Minat Masyarakat Menggunakan Layanan Angkutan Umum Di Kota Palembang,” Community Jurnal Pengabdian, vol. 4, no. 1, pp. 29–38, 2022.
A. Dardas, B. Hall, J. Salter, and H. Hosseini, “A geospatial workflow for the assessment of public transit system performance using near real‐time data,” Transactions in GIS, vol. 26, no. 4, pp. 1642–1664, Jun. 2022, doi: 10.1111/tgis.12942.
F. Wang, M. Ye, H. Zhu, and D. Gu, “Optimization Method for Conventional Bus Stop Placement and the Bus Line Network Based on the Voronoi Diagram,” Sustainability, vol. 14, no. 13, p. 7918, Jun. 2022, doi: 10.3390/su14137918.
St. M. Hafran, M. T. Syarkawi, I. Syafei, I. Munsyir, and S. Saleh, “Analisis Kinerja Angkutan Umum BMA (Studi Kasus Rute Pinrang – Makassar PP),” PENA TEKNIK: Jurnal Ilmiah Ilmu-Ilmu Teknik, vol. 4, no. 2, p. 111, Jan. 2021, doi: 10.51557/pt_jiit.v4i2.590.
K. Meneses-Cime, B. Aksun Guvenc, and L. Guvenc, “Optimization of On-Demand Shared Autonomous Vehicle Deployments Utilizing Reinforcement Learning,” Sensors, vol. 22, no. 21, p. 8317, Oct. 2022, doi: 10.3390/s22218317.
C. Yang, X. Chen, X. Lin, and M. Li, “Coordinated trajectory planning for lane-changing in the weaving areas of dedicated lanes for connected and automated vehicles,” Transp Res Part C Emerg Technol, vol. 144, p. 103864, Nov. 2022, doi: 10.1016/j.trc.2022.103864.
Z. Buako, L. Yahya, and N. Achmad, “Aplikasi Algoritma Floyd-Warshall Dengan Pendekatan Madm Dalam Menentukan Rute Terpendek Pengangkutan Sampah,” Euler : Jurnal Ilmiah Matematika, Sains dan Teknologi, vol. 9, no. 2, pp. 62–70, Oct. 2021, doi: 10.34312/euler.v9i2.10979.
A. Ibraeva, G. H. de A. Correia, C. Silva, and A. P. Antunes, “Transit-oriented development: A review of research achievements and challenges,” Transp Res Part A Policy Pract, vol. 132, pp. 110–130, Feb. 2020, doi: 10.1016/j.tra.2019.10.018.
C. Iliopoulou and K. Kepaptsoglou, “Integrated transit route network design and infrastructure planning for on-line electric vehicles,” Transp Res D Transp Environ, vol. 77, pp. 178–197, Dec. 2019, doi: 10.1016/j.trd.2019.10.016.
N. Agatz, M. Hewitt, and B. W. Thomas, “‘Make no little plans’: Impactful research to solve the next generation of transportation problems,” Networks, vol. 77, no. 2, pp. 269–286, Mar. 2021, doi: 10.1002/net.22002.
P. A. Maldonado Silveira Alonso Munhoz et al., “Smart Mobility: The Main Drivers for Increasing the Intelligence of Urban Mobility,” Sustainability, vol. 12, no. 24, p. 10675, Dec. 2020, doi: 10.3390/su122410675.
S. L. Pardede, F. R. Athallah, Y. N. Huda, and F. D. Zain, “A Review of Pathfinding in Game Development,” [CEPAT] Journal of Computer Engineering: Progress, Application and Technology, vol. 1, no. 01, p. 47, May 2022, doi: 10.25124/cepat.v1i01.4863.
L. Hao, Y. Wang, Y. Bai, and Q. Zhou, “Energy management strategy on a parallel mild hybrid electric vehicle based on breadth first search algorithm,” Energy Convers Manag, vol. 243, p. 114408, Sep. 2021, doi: 10.1016/j.enconman.2021.114408.
Y. Wang and L. Feng, “An adaptive boosting algorithm based on weighted feature selection and category classification confidence,” Applied Intelligence, vol. 51, no. 10, pp. 6837–6858, Oct. 2021, doi: 10.1007/s10489-020-02184-3.
M. F. Bernov, A. D. Rahajoe, and B. M. Mulyo, “Route Optimization of Waste Carrier Truck using Breadth First Search (BFS) Algorithm,” JEECS (Journal of Electrical Engineering and Computer Sciences), vol. 7, no. 2, pp. 1293–1304, 2023, doi: 10.54732/jeecs.v7i2.23.
S. Sularno, D. P. Mulya, R. Astri, and D. Mulya, “Determination of The Shortest Route Based on BFS Algorithm for Purpose to Disaster Evacuation Shelter,” Scientific Journal of Informatics, vol. 8, no. 1, pp. 33–42, May 2021, doi: 10.15294/sji.v8i1.27863.
S. Sularno, R. Astri, P. Anggraini, D. Prima Mulya, and D. Mulya, “Geographical Information System of Bus and Travel Counter in Padang City Using BFS Method Based on Mobile Web,” Scientific Journal of Informatics, vol. 8, no. 2, pp. 304–313, Nov. 2021, doi: 10.15294/sji.v8i2.33117.
E. Wang et al., “Double Graph Attention Actor-Critic Framework for Urban Bus-Pooling System,” IEEE Transactions on Intelligent Transportation Systems, pp. 1–13, 2023, doi: 10.1109/TITS.2023.3238055.
H. Behrooz and Y. M. Hayeri, “Machine Learning Applications in Surface Transportation Systems: A Literature Review,” Applied Sciences, vol. 12, no. 18, p. 9156, Sep. 2022, doi: 10.3390/app12189156.
J. Wang, Y. Xie, S. Xie, and X. Chen, “Cooperative particle swarm optimizer with depth first search strategy for global optimization of multimodal functions,” Applied Intelligence, vol. 52, no. 9, pp. 10161–10180, Jul. 2022, doi: 10.1007/s10489-021-03005-x.
Y. Du, F. Li, T. Zheng, and J. Li, “Fast Cascading Outage Screening Based on Deep Convolutional Neural Network and Depth-First Search,” IEEE Transactions on Power Systems, vol. 35, no. 4, pp. 2704–2715, Jul. 2020, doi: 10.1109/TPWRS.2020.2969956.
O. Riansanti, M. Ihsan, and D. Suhaimi, “Connectivity algorithm with depth first search (DFS) on simple graphs,” J Phys Conf Ser, vol. 948, p. 012065, Jan. 2018, doi: 10.1088/1742-6596/948/1/012065.
A. Gaihre, Z. Wu, F. Yao, and H. Liu, “XBFS: eXploring Runtime Optimizations for Breadth-First Search on GPUs,” in Proceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing, New York, NY, USA: ACM, Jun. 2019, pp. 121–131. doi: 10.1145/3307681.3326606.
T. N. Lina and M. S. Rumetna, “Comparison Analysis of Breadth First Search and Depth Limited Search Algorithms in Sudoku Game,” Bulletin of Computer Science and Electrical Engineering, vol. 2, no. 2, pp. 74–83, Dec. 2021, doi: 10.25008/bcsee.v2i2.1146.
Bonifacius Vicky Indriyono and Widyatmoko, “Optimization of Breadth-First Search Algorithm for Path Solutions in Mazyin Games,” International Journal of Artificial Intelligence & Robotics (IJAIR), vol. 3, no. 2, pp. 58–66, Nov. 2021, doi: 10.25139/ijair.v3i2.4256.
Z. Guo, C. S. Lai, P. Luk, and X. Zhang, “Techno-economic assessment of wireless charging systems for airport electric shuttle buses,” J Energy Storage, vol. 64, p. 107123, Aug. 2023, doi: 10.1016/j.est.2023.107123.
L. Miteva, K. Yovchev, and I. Chavdarov, “Point-to-point Motion Planning with Obstacle Avoidance for Hard Constrained Redundant Robotic Manipulators,” in 2021 XXX International Scientific Conference Electronics (ET), IEEE, Sep. 2021, pp. 1–5. doi: 10.1109/ET52713.2021.9579820.
Q. Li et al., “FPS: Fast Path Planner Algorithm Based on Sparse Visibility Graph and Bidirectional Breadth-First Search,” Remote Sens (Basel), vol. 14, no. 15, p. 3720, Aug. 2022, doi: 10.3390/rs14153720.
K. Zhao, G. Yang, and S. Zhu, “Fire Site Map Construction Method Based on UWB Connectivity Fusion,” in 2022 4th International Conference on Natural Language Processing (ICNLP), IEEE, Mar. 2022, pp. 575–579. doi: 10.1109/ICNLP55136.2022.00105.
T. Liu et al., “Towards Indoor Temporal-variation aware Shortest Path Query,” IEEE Trans Knowl Data Eng, pp. 1–1, 2021, doi: 10.1109/TKDE.2021.3076144.
Downloads
Published
Issue
Section
License
Copyright (c) 2023 Suprihatin Kartoirono, Imam Riadi, Furizal, Ahmad Azhari
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Start from 2019 issues, authors who publish with JURNAL MOBILE AND FORENSICS agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Mobile and Forensics (MF)