Розв’язання задачі комівояжера на основі еволюційного моделювання
DOI:
https://doi.org/10.35681/1560-9189.2019.21.3.183550Ключові слова:
задача комівояжера, генетичний алгоритм, еволюційна модель, мінімальна відстань, графАнотація
Запропоновано еволюційну модель для розв’язання задачі комівояжера, виконано її апробацію у сфері аптечного бізнесу шляхом оптимізації процесу роботи засобу подачі ліків. У розробленій моделі використано модифіковані оператори ініціалізації початкової популяції. Розроблені оператори ініціалізації початкової популяції передбачають створення початкової множини рішень, виходячи з особливостей розв’язуваної задачі, що дозволяє генерувати більш пристосовані хромосоми (хромосоми з кращими значеннями функції пристосованості) на початковому етапі пошуку та наблизити початкові точки до області глобального екстремуму, зменшити час оптимізації і обсяг використаних ресурсів комп’ютера. Розроблену еволюційну модель для розв’язання задачі комівояжера було імплементовано шляхом її програмної реалізації і впровадження в аптечній мережі «Аптека низьких цін». У програмі реалізовано можливість побудови контуру обходу для пошуку ліків у роботизованому складі на 1000 чарунок, тривалість пошуку ліків є прийнятною для підприємства та складає не більше п’яти секунд.
Посилання
The Travelling Salesman Problem and its Applications. CO@W Berlin, 2009. URL: http://coat-work.zib.de/berlin2009/downloads/2009-09-21/2009-09-21-1600-MG-TSP-and Applications.pdf
Gen M., Cheng R. Genetic algorithms and engineering design. New Jersey: John Wiley & Sons, 1997. 352 p.
Haupt Randy L., Haupt Sue Ellen. Practical genetic algorithms. 2nd ed., 2004. 261 p.
Kleiman H. The General Traveling Salesman Problem. Createspace Independent Pub, 2014. 470 с. ISBN: 149438714X 9781494387143.
Mudrov V.I. Zadacha o kommivojazhere. URSS, 2019. 70 s. ISBN: 978-5-397-04106-5.
Tan W., Chua S., Yong K., Wu T. Impact of Pharmacy Automation on Patient Waiting Time: An Application of Computer Simulation. Simulating Impact of Pharmacy Automation. 2009. Vol. 38. P. 501–507.
Oliinyk A.O., Subbotin S.O., Oliinyk O.O. Evolyutsiyni obchyslennya ta prohramuvannya: navch. posib. — Zaporizhzhya: ZNTU, 2010. 324 s.
Subbotin S.O. Podannya y obrobka znan u systemakh shtuchnoho intelektu ta pidtrymky pryynyattya rishen: navch. posib. — Zaporizhzhya: ZNTU, 2008. 341 s.
Dubrovin V.I., Subbotin S.O. Metody optymizatsiyi ta yikh zastosuvannya v zadachakh navchannya neyronnykh merezh: navch. posib. — Zaporizhzhya: ZNTU, 2003. 136 s.
Stroustrup Bjarne. The C++ programming language. Fourth edition. 2013. 1366 p.
Shlee M. Qt 5.5 Professional'noe programmirovanie na C++. Sankt-Peterburg: «BHV-Peterburg», 2015. 896 s.
Dopico J. Encyclopedia of artificial intelligence; Eds.: J.R. Dopico, J.D. de la Calle, A.P. Sierra. New York: Information Science Reference. 2009. Vol. 1–3. 1677 p.
Nagata Y., Kobayashi S. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. 2012. P. 346–363. doi: 10.1287/ijoc.1120.0506.
Hoffman K., Rinaldi G. Traveling Salesman Problem. Advertising Response, Encyclopedia of Operations Reseach. 2013. P. 1573–1578. doi: 10.1007/978-1-4419-1153-7_1068.
Wang Y. The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem. Computers & Industrial Engineering. 2014. Vol. 70. P. 124–133. doi: 10.1016/j.cie.2014.01.015.
Sanches D., Whitley D. Improving an exact solver for the traveling salesman problem using partition crossover. Proceedings of the Genetic and Evolutionary Computation Conference. 2017. P. 337–344. doi: 10.1145/3071178.3071304.
Hussain A., Muhammad Y. Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator. Computational Intelligence and Neuroscience. 2017. Vol. 2017. P. 7. doi: 10.1155/2017/7430125.
Tsai C., Tseng S. A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case. The Scientific World Journal. 2014. Vol. 2014. P. 14. doi: 10.1155/2014/178621.
Progressivnye tehnologii modelirovanija, optimizacii i intellektual'noj avtomatizacii jetapov zhiznennogo cikla aviadvigatelej: monografija/Boguslaev A.V. i dr.; pod red. D.V. Pavlenko, S.A. Subbotina. Zaporozh'e: OAO «Motor Sich», 2008. 468 s.
Rassel S., Norvig P. Iskusstvennyj intellekt: sovremennyj podhod. Moskva: Vil'jams, 2006. 1408 s.
Applegate David L., Robert E. Bixby, Chvatal Vasek. The Traveling Salesman Problem A Computational Study. Princeton University Press Princeton, NJ, USA, 2007. 608 с. ISBN: 0691129932 9780691129938.
Rudenko O.H., Bodyans'kyy Ye.V. Shtuchni neyronni merezhi. Kharkiv: Kompaniya SMIT, 2006. 404 s.
Cook William J. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, 2012. 228 р. ISBN: 0691152705 9780691152707.
Zuhori S.Т. Traveling Salesman Problem. Lap Lambert Academic Publishing GmbH KG, 2012. 56 р. ISBN: 3846583057 9783846583050.
The practical handbook of genetic algorithms / Еd. L.D. Chambers. Florida: CRC Press, 2000. Vol. I: Applications. 520 p.
Chambers L. The practical handbook of genetic algorithms / Еd. L.D. Chambers. Florida: CRC Press, 2000. Vol. II: New frontiers. 421 p.
Chambers L. The practical handbook of genetic algorithms / Еd. L.D. Chambers. Florida: CRC Press LLC, 2000. Vol. III: Complex coding systems. 659 p.
Cantu-Paz E. Efficient and accurate parallel genetic algorithms.Massachusetts: Kluwer Aca-demic Publishers, 2001. 162 p.
Bao Lin Xiaoyan Sun and Sana Salous. Solving Travelling Salesman Problem with an Im-proved Hybrid Genetic Algorithm. Journal of Computer and Communications. 2016. 4. Р. 98–06. URL: http://www.scirp.org/journal/jcc. ISSN Online: 2327-5227. ISSN Print: 2327-5219.
