S.S. Semenov - Dr. Sc. (Eng.), Associate Professor, Professor of Department, Military communication Academy n. a. S.M. Budenny (St.-Peterburg) E-mail: semsem@yandex.ru A.V. Pedan - Graduated, Military communication Academy n. a. S.M. Budenny (St.-Peterburg) E-mail: mycop14@mail.ru V.K. Goydenko - Graduated, Military communication Academy n. a. S.M. Budenny (St.-Peterburg) E-mail: lglvl@ya.ru

At present, logistical problems to find the optimal route of cargo delivery have become quite relevant. When the number of delivery points not great that this problem has a simple solution. In the case of a large number of delivery points for the task may require a significant resource of time. When time is limited resource for solving problems with a large number of delivery points there are different heuristic algorithms. They allow you to find an approximate solution of the problem in a finite time. There are many heuristic algorithms and their modifications allow us to solve the problem of finding the optimal route of deli-very. The aim of this study is to identify and formulate a criterion of applicability of a heuristic algorithm. The study of heuristic algorithms to find the optimal route of delivery of goods is reduced to solving the problem of the traveling salesman who must visit all city visiting each of them only once to return to the original city, the route of the traveling salesman has to be the shortest, then this task is repeated right number of times. The optimization problem statement refers to the class of very NP-hard problems, like most of its special cases. It is obvious that the problem can be solved by brute force attack detour options and selecting the best route. The problem is that the number of possible routes quickly increases with the number of cities. In consequence of that should give up trying to find the exact solution of the traveling salesman problem and focus on finding the approximate - though not optimal, but it is close to the route. In view of the great tasks of practical importance will be useful and heuristic solutions. There are many methods for the approximate solution of the traveling salesman problem of route search such as: an exhaustive search, greedy algorithm, the method of simulated annealing, ant algorithm, genetic algorithm. To evaluate the applicability of the area and options heuristic algorithms to find the optimal route of a Salesman series of experiments was carried out on them. The efficiency of heuristic algorithms was tested in simulation system. As a result was obtained statistics on the execution time and the length of each of the resulting route algorithms. Analysis of the collected statistics it possible to identify possible applicability of algorithms under certain conditions.

 

1. Kurejjchik V.M., Kazharov A.A. O nekotorykh modifikacijakh muravinogo algoritma // Izvestija JUFU. Tekhnicheskie nauki. 2008. № 4.
2. Kurejjchik V.M., Kazharov A.A. Ispolzovanie roevogo intellekta v reshenii NP-trudnykh zadach // Izv. JUFU. Tekhnicheskie nauki. 2011. № 7.
3. Savin A.N., Timofeeva N.E. Primenenie algoritma optimizacii metodom imitacii otzhiga na sistemakh parallelnykh i raspredelennykh vychislenijj // Izv. Saratovskogo un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika. 2012. № 1.
4. Anashkina N.V., SHurupov A.N. EHksperimentalnoe sravnenie algoritmov Balasha i imitacii otzhiga v zadache reshenija sistem linejjnykh neravenstv // PDM. Prilozhenie. 2014. № 7.
5. Kurejjchik V.M. Geneticheskie algoritmy // Izv. JUFU. Tekhnicheskie nauki. 1998. № 2.
6. Lucenko V.N. Geneticheskijj algoritm dlja reshenija transportnojj zadachi // Izvestija JUFU. Tekhnicheskie nauki. 1996. № 1.
7. Semenov S.S., Tkachev D.F., Pedan A.V., Alisevich E.A.., Popov A.V., Voroncov O.S., Kiselev D.V., Klimov I.S. Programma dlja reshenija zadachi kommivojazhera s pomoshhju geneticheskogo algoritma // KHroniki obedinennogo fonda ehlektronnykh resursov. Nauka i obrazovanie. 2016. № 6 (85). S. 32.
8. Semenov S.S., Tkachev D.F., Pedan A.V., Alisevich E.A.., Popov A.V., Voroncov O.S., Kiselev D.V., Klimov I.S. Programma dlja reshenija zadachi kommivojazhera s pomoshhju muravinogo algoritma // KHroniki obedinennogo fonda ehlektronnykh resursov. Nauka i obrazovanie. 2016. № 6 (85). S. 31.
9. Semenov S.S., Volovikov V.S., Tkachev D.F., Pedan A.V., Kiselev D.V., Kotljarov D.JU., Vishnjakov N.I. Imitacionnaja model vedenija tekhnicheskojj razvedki tekhniki svjazi i ASU s primeneniem sredstv robotizacii // KHroniki obedinennogo fonda ehlektronnykh resursov Nauka i obrazovanie. 2016. № 2 (81). S. 15.
10. Voevodin V.V. i dr. Parallelnye vychislenija. SPb: BKHV-Peterburg. 2002. P. 608.
11. Kormen T., Lejjzerson CH., Rivest R., SHtajjn K. Glava 16. ZHadnye algoritmy // Algoritmy: postroenie i analiz = Introduction to Algorithms / Pod red. I.V. Krasikova. Izd. 2-e. M.: Viljams 2005. 1296 s.