Modyfikacje algorytmów planowania trasy uwzględniające ograniczenia czasowe i odległościowe

• Autorzy: Wolanin Mateusz , Korniszuk Klaudia , Smołka Jakub

Warianty tytułu

EN

Modification of path-finding algorithms introducing time and distance limitations

• Języki publikacji: PL

Abstrakty

PL

Artykuł przedstawia modyfikacje algorytmów wyszukiwania ścieżki w grafie mające na celu wprowadzenie ograniczeń: czasowych lub odległościowych do znalezionej trasy. Zmodyfikowane zostały dwa algorytmy: A* oraz BFS. Zaproponowana została również modyfikacja algorytmu A*, która łączy atuty tych dwóch algorytmów – wygenerowanie najkrótszych tras o jak najmniejszej liczbie wierzchołków. Zmodyfikowane algorytmy umożliwią stworzenie aplikacji pozwalającej na łatwiejsze i bardziej oszczędne poruszanie się z wykorzystaniem usług typu rowerem miejski.

EN

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.

Słowa kluczowe

PL

wyznaczanie trasy; rower miejski; algorytm A*; algorytm BFS

EN

route planning; bike sharing system; algorithm A*; algorithm BFS

• Wydawca: Wydawnictwo Politechniki Lubelskiej
• Czasopismo: Journal of Computer Sciences Institute
• Rocznik: 2019
• Tom: Vol. 10
• Strony: 18--23
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Wolanin Mateusz

• Politechnika Lubelska, Instytut Informatyki, Nadbystrzycka 36B, 20-618 Lublin, Polska

autor

Korniszuk Klaudia

• Politechnika Lubelska, Instytut Informatyki, Nadbystrzycka 36B, 20-618 Lublin, Polska

autor

Smołka Jakub

• Politechnika Lubelska, Instytut Informatyki, Nadbystrzycka 36B, 20-618 Lublin, Polska

Bibliografia

• [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

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).