СИСТЕМА ПОБУДОВИ ОПТИМАЛЬНИХ МАРШРУТІВ НА ОСНОВІ АЛГОРИТМІВ НАЙКОРОТШИХ ШЛЯХІВ

Автор(и)

  • Альона Яковенко Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Україна
  • Марк Фолькін Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Україна

DOI:

https://doi.org/10.20535/2617-8974.2019.2.185416

Ключові слова:

алгоритми точного та неточного пошуку, алгоритм Дейкстри, алгоритм А*, задача комівояжера, javafx, GoogleMaps API, дискретна оптимізація, безперервна оптимізація

Анотація

На сьогодні з великою різноманітністю транспортних засобів, люди часто не можуть визначити найкращі шляхи пересування, це все спричинено надлишком інформації, яку людині важко запам’ятати. Тому проблема створення маршрутів, за допомогою яких людина змогла б в найкоротший термін дістатися до запланованої цілі постає в найбільшому вигляді. Багато сучасних сервісів дозволяють будувати маршрути від точки А до точки Б, але вони не можуть задовольнити користувача, якому необхідно об’їхати декілька адрес. Для розробки було обрано середовище програмування Eclipse, бібліотеку зв’язку з картографічним сервісом GmapsFX, реалізовану на мові Java. В результаті розроблено програму для пошуку найкоротшого маршруту на карті з використанням алгоритмів оптимальних шляхів, розроблено функціонал сімейного лікаря: перегляд пацієнтів, історія викликів.

Посилання

Jonker, Roy; Volgenant, Ton. "Transforming asymmetric into symmetric traveling salesman problems". Operations Research Letters. 2 (161–163): 1983.

Костевич Л. С. Математическое программирование: Информ. Технологи оптимальныхрешений: Учеб. пособие / Л. С. Костевич. — Мн.: Новоезнание, 2003. ил., стр. 150, ISBN 985-6516-83-8

Haider A Abdulkarim, Ibrahim F Alshammari. "Comparison of Algorithms for Solving Traveling Salesman Problem". International Journa lof Engineering and Advanced Technology (IJEAT) ISSN: 2249 – 8958, Volume-4 Issue-6, August 2015

Jayakumar S. Rigidflatfoot. / S. Jayakumar, H. Cowell. // Clin Orthop Relat Res.. – 2017. – №22. – С. 77–84.

Angel E., Zissimopoulos V. On the classification of NP-complete problems in termsof their correlation coefficient // Discrete Appl. Math. 2. V. 9. P. 261–277.

Yannakakis M. Computationa complexity. In: Aarts E., Lenstra J. (Eds.) Local search in combinatorial optimization. NY:Wiley, 1997.

Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design (2nd ed.). Addison-Wesley. p. 464. ISBN 0-321-37291-3.

Korte B, Vugen J. Combinatorial optimization. Berlin: Springer, 2007.

Yannakakis M. Computational complexity. In: Aarts E., Lenstra J. (Eds.) Local search in combinatorial optimization. NY:Wiley, 1997.

Ежов А., Шумский С. Нейрокомпьютинг и его применения в экономике и бизнесе . — М.: МИФИ, 1998. — С. 216

##submission.downloads##

Опубліковано

2019-11-29

Номер

Розділ

Статті