Разработка мобильного приложения для построения велосипедных туристических маршрутов
Аннотация
Задача построения оптимального маршрута является одной из самых популярных задач комбинаторики. Именно эту задачу решают авторы данной статьи, рассматривая ее в отрасли путешествий. Туристу необходимо построить интересный и познавательный маршрут, который будет включать в себя максимально возможное количество достопримечательностей. Важно учитывать, что у путешественника чаще всего время ограничено, кроме этого, туристы часто желают остановиться у каждой из достопримечательностей, чтобы подробнее изучить их и сфотографировать. Таким образом, в данной статье решается задача коммивояжера. За основу решения взят жадный алгоритм, однако из-за добавления в задачу новых условий (ограниченность туриста по времени, дополнительное время на просмотр достопримечательностей) он немного видоизменяется. Помимо алгоритма в статье содержится подробное описание мобильного приложения, которое может использовать турист для решения данной задачи. В данном мобильном приложении на стартовой странице пользователь вводит следующие параметры: количество свободного времени, название города, адрес стартовой точки и количество времени, которое он желает потратить для более подробного изучения достопримечательностей или фотографию. Стартовой точкой пользователь также может выбрать свое местоположение, если у него включена служба геолокации, и он разрешил приложению использовать ее. После введения параметров приложение рисует на карте предлагаемый оптимальный маршрут. Авторы в своей статье рассказывают обо всех особенностях разрабатываемого мобильного приложения: способе хранения данных о достопримечательностях разных городов, используемых фреймворках, интерфейсе и т.д. Приложение разрабатывается на iOS, поэтому в качестве языка программирования был выбран Swift 5.
Литература
2. Khashirova T.Yu., Amshokov E.T., Tokmakova D.A., Retova F.R. Intelligent Tourist Assistance System: IT-Service for Creating a Personal Tourist Route in the Kabardino-Balkar Republic. Kachestvo. Innovacii. Obrazovanie. 2021;(4):72-79. (In Russ., abstract in Eng.) https://doi.org/10.31145/1999-513x-2021-4-72-79
3. Kireev V.A., Roshchina E.V. Analysis of Mobile Application Development Tools for Building Urban Tourist Routes. In: V.V. Dolgov (ed.) Intelligent Information Technologies and Mathematical Modeling: Proceedings of the International Scientific Conference. Rostov-on-Don: Don State Technical University; 2022. p. 237-239. (In Russ., abstract in Eng.) EDN: UQUMBY
4. Bast H. Car or Public Transport – Two Worlds. In: Albers S., Alt H., Näher S. (eds.) Efficient Algorithms. Lecture Notes in Computer Science. Vol. 5760. Berlin, Heidelberg: Springer; 2009. p. 355-367. https://doi.org/10.1007/978-3-642-03456-5_24
5. Khoufi I., Laouiti A., Adjih C. A Survey of Recent Extended Variants of the Traveling Salesman and Vehicle Routing Problems for Unmanned Aerial Vehicles. Drones. 2019;3(3):66. https://doi.org/10.3390/drones3030066
6. Hu Y., Yao Y., Lee W.S. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge-Based Systems. 2020;204:106244. https://doi.org/10.1016/j.knosys.2020.106244
7. Hromkovič J. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Texts in Theoretical Computer Science. An EATCS Series. Berlin, Heidelberg: Springer; 2004. 538 p. https://doi.org/10.1007/978-3-662-05269-3
8. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Combinatorial Optimization. Vol. 12. Boston, MA: Springer; 2007. 830 p. https://doi.org/10.1007/b101971
9. Polupanova E.E., Polyakov A.S. Population-Based Algorithm for Solving the Traveling Salesman Problem. Modern Information Technologies and IT-Education. 2021;17(2):324-333. (In Russ., abstract in Eng.) https://doi.org/10.25559/SITI-TO.17.202102.324-333
10. Melnikov B.F. About the Object-Oriented Implementation of the Branch and Boundary Method for the Travelling Salesman Problem. Part I. Modern Information Technologies and IT-Education. 2022;18(2):287-299. (In Russ., abstract in Eng.) https://doi.org/10.25559/SITITO.18.202202.287-299
11. Ozden S.G., Smith A.E., Gue K.R. Solving large batches of traveling salesman problems with parallel and distributed computing. Computers & Operations Research. 2017;85:87-96. https://doi.org/10.1016/j.cor.2017.04.001
12. Gera R., Hedetniemi S., Larson C. Graph Theory: Favorite Conjectures and Open Problems – 1. Problem Books in Mathematics. Cham: Springer; 2016. 291 p. https://doi.org/10.1007/978-3-319-31940-7
13. Makarkin S.B., Melnikov B.F. Geometric Methods for Solving the Pseudo-Geometric Version of the Traveling Salesman Problem. Stochastic Optimization in Informatics. 2013;9(2):54-72. (In Russ., abstract in Eng.) EDN: PWVBDY
14. Xu X., Li J., Zhou M. Bi-Objective Colored Traveling Salesman Problems. IEEE Transactions on Intelligent Transportation Systems. 2022;23(7):6326-6336. https://doi.org/10.1109/TITS.2021.3086625
15. Munerman V.I., Samoylova T.A. Algebraic Approach to Algorithmization of Routing Problems. Highly Available Systems. 2018;14(5):50-56. (In Russ., abstract in Eng.) https://doi.org/10.18127/j20729472-201805-081
16. Kozlov S.V. Use of a mathematical apparatus of implicative matrixes in the creation and support of information systems. International Journal of Open Information Technologies. 2017;5(12):16-23. (In Russ., abstract in Eng.) EDN: XHKJYW
17. Morozov S.A., Munerman V.I., Simakov V.A. Experimental analysis of multidimensional matrix approach to constructing routings in a graph. Proc. Univ. Electronics. 2022;27(5):676-686. (In Russ., abstract in Eng.) https://doi.org/10.24151/1561-5405-2022-27-5-676-686
18. Kozlov S.V. Interpretation of invariants of the theory of counts in the context of use of compliance of Galois at creation and support of information systems. International Journal of Open Information Technologies. 2016;4(7):38-44. (In Russ., abstract in Eng.) EDN: WCMIYL
19. Kozlov S.V. Applying Galois Compliance for Data Analysis in Information Systems. Traektoriâ Nauki = Path of Science. 2016;2(3):18. (In Russ., abstract in Eng.) EDN: VRDJOZ
20. Rusakov A.M., Yushkova N.A. Investigation of Structural Properties of Information Systems Based on Spectral Graph Theory. Naukosfera. 2023;(6-1):192-199. (In Russ., abstract in Eng.) https://doi.org/10.5281/zenodo.8055586
21. Kirsch R., Sibley C., Sprangel E. Graph universal cycles: Compression and connections to universal cycles. Advances in Applied Mathematics. 2023;148:102522. https://doi.org/10.1016/j.aam.2023.102522
22. Nigodin E.A., Polupanova E.E., Polyakov A.S. Hybrid Algorithm for Solving the Traveling Salesman Problem. In: Applied Mathematics of the 21st Century: Modern Problems of Mathematics, Computer Science, and Modeling: Proceedings of the All-Russian Scientific and Practical Conference. Krasnodar: Russian Energy Agency of the Ministry of Energy of Russia, Krasnodar Center for Scientific and Technical Information Branch of the Russian Energy Agency of the Ministry of Energy of Russia; 2019. p. 252-259. (In Russ., abstract in Eng.) EDN: ITDYEX.
23. Shen A. Algorithms and Programming: Problems and Solutions. Springer Undergraduate Texts in Mathematics and Technology. New York, NY: Springer; 2010. 272 p. https://doi.org/10.1007/978-1-4419-1748-5
24. Sharma P.K. Design And Development of a Multi Featured IOS Mobile Application Using Swift 3. Journal 4 Research – J4R Journal. 2018;3(11):1-6.
25. Masum A.K.M., Shahjalal M., Faruque M.F., Sarker M.I.H. Solving the Vehicle Routing Problem using Genetic Algorithm. International Journal of Advanced Computer Science and Applications. 2011;2(7):126-131. https://doi.org/10.14569/IJACSA.2011.020719
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
