DOI: https://doi.org/10.35681/1560-9189.2019.21.3.183550

Розв’язання задачі комівояжера на основі еволюційного моделювання

A. О. Oliinyk, Iе. М. Fedorchenko, О. О. Stepanenko, M. S. Rud

Анотація


Запропоновано еволюційну модель для розв’язання задачі комівояжера, виконано її апробацію у сфері аптечного бізнесу шляхом оптимізації процесу роботи засобу подачі ліків. У розробленій моделі використано модифіковані оператори ініціалізації початкової популяції. Розроблені оператори ініціалізації початкової популяції передбачають створення початкової множини рішень, виходячи з особливостей розв’язуваної задачі, що дозволяє генерувати більш пристосовані хромосоми (хромосоми з кращими значеннями функції пристосованості) на початковому етапі пошуку та наблизити початкові точки до області глобального екстремуму, зменшити час оптимізації і обсяг використаних ресурсів комп’ютера. Розроблену еволюційну модель для розв’язання задачі комівояжера було імплементовано шляхом її програмної реалізації і впровадження в аптечній мережі «Аптека низьких цін». У програмі реалізовано можливість побудови контуру обходу для пошуку ліків у роботизованому складі на 1000 чарунок, тривалість пошуку ліків є прийнятною для підприємства та складає не більше п’яти секунд.


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


задача комівояжера; генетичний алгоритм; еволюційна модель; мінімальна відстань; граф

Повний текст:

PDF

Посилання


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.