Modification of path-finding algorithms introducing time and distance limitations
Mateusz Wolanin
mat.wol20@outlook.comLublin University of Technology (Poland)
Klaudia Korniszuk
Lublin University of Technology (Poland)
Jakub Smołka
Lublin University of Technology (Poland)
Abstract
This paper describes modifications of path-finding algorithms. The modifications add time and distance constraints to generated paths. A* and BFS algorithms are modified. Additionally, A* algorithm modification which combines the advantages (generating the shortest routes with the smallest number of vertices) of A* and BFS is presented.. This allows for creating a route planning app that enables users of bike sharing services to travel more easily and economically.
Keywords:
route planning; bike sharing system; algorithm A*; algorithm BFSReferences
[1] L GZhi Li, Jianhui Zhang, Jiayu Gan, Pengqian Lu, Fei Lin, Large-Scale Trip Planning for Bike-Sharing Systems, IEEE 14th International Conference on Mobile Ad Hoc and Sensor Systems, 2017
[2] Leonardo Caggiani, Rosalia Camporeale, Michele Ottomanelli, A real time multi-objective cyclists route choice model for a bike-sharing mobile application, Politecnico di Bari, 2017
[3] Wen Ouyang, Chang Wu Yu, Pei-Ju Huang, Huai-Tse Chang, Non-commutative path planning for tours with diversified attractions, Chung Hua University, 2017.
[4] Jing Luan, Zhong Yao, Futao Zhao, XinSong, A novel method to solve supplier selection problem: Hybrid algorithm of genetic algorithm and ant colony optimization, Mathematics and Computers in Simulation, Elsevier, 2019
[5] Haifeng Wang, Jiawei Zhou, Guifeng Zheng, Yun Liang, HAS:Hierarchical A-Star algorithm for big map navigation in special areas, 2014 International Conference on Digital Home, IEEE, 2014
[6] K. Khantanapoka, K. Chinnasarn: Pathfinding of 2D & 3D Game Real-Time Strategy with Depth Direction A*Algorithm for Multi-Layer, Eighth International Symposium on Natural Language Processing, IEEE, 2009
[7] W. Lu: Beginning Robotics Programming in Java with LEGO Mindstorms, Rozdział 9, 2016
[8] A. Chaudhari, M. Apsangi, A. Kudale: Improved A-star Algorithm with Least Turn for Robotic Rescue Operations, Computational Intelligence, Communications, and Business Analytics, Springer Nature, 2017
[9] Mapy Google, https://www.google.pl/maps/dir/ [dostęp 10.10.2018]
[10] dr inż. Tadeusz Kopta, mgr Aleksander Buczyński, Marcin Hyła, mgr inż. Bartłomiej Lustofin, Konkurencyjność roweru w zakresie czasu podróży, Warszawa-Kraków, czerwiec 2012
[2] Leonardo Caggiani, Rosalia Camporeale, Michele Ottomanelli, A real time multi-objective cyclists route choice model for a bike-sharing mobile application, Politecnico di Bari, 2017
[3] Wen Ouyang, Chang Wu Yu, Pei-Ju Huang, Huai-Tse Chang, Non-commutative path planning for tours with diversified attractions, Chung Hua University, 2017.
[4] Jing Luan, Zhong Yao, Futao Zhao, XinSong, A novel method to solve supplier selection problem: Hybrid algorithm of genetic algorithm and ant colony optimization, Mathematics and Computers in Simulation, Elsevier, 2019
[5] Haifeng Wang, Jiawei Zhou, Guifeng Zheng, Yun Liang, HAS:Hierarchical A-Star algorithm for big map navigation in special areas, 2014 International Conference on Digital Home, IEEE, 2014
[6] K. Khantanapoka, K. Chinnasarn: Pathfinding of 2D & 3D Game Real-Time Strategy with Depth Direction A*Algorithm for Multi-Layer, Eighth International Symposium on Natural Language Processing, IEEE, 2009
[7] W. Lu: Beginning Robotics Programming in Java with LEGO Mindstorms, Rozdział 9, 2016
[8] A. Chaudhari, M. Apsangi, A. Kudale: Improved A-star Algorithm with Least Turn for Robotic Rescue Operations, Computational Intelligence, Communications, and Business Analytics, Springer Nature, 2017
[9] Mapy Google, https://www.google.pl/maps/dir/ [dostęp 10.10.2018]
[10] dr inż. Tadeusz Kopta, mgr Aleksander Buczyński, Marcin Hyła, mgr inż. Bartłomiej Lustofin, Konkurencyjność roweru w zakresie czasu podróży, Warszawa-Kraków, czerwiec 2012
Wolanin, M., Korniszuk, K., & Smołka, J. (2019). Modification of path-finding algorithms introducing time and distance limitations . Journal of Computer Sciences Institute, 10, 18–23. https://doi.org/10.35784/jcsi.188
Authors
Klaudia KorniszukLublin University of Technology Poland
Authors
Jakub SmołkaLublin University of Technology Poland
Statistics
Abstract views: 224PDF downloads: 222
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
