Application of ant optimization algorithms in the solution of the routing problem = Застосування мурашиних алгоритмів в рiшенні задачі маршрутизації

Abstract

The article discusses current issues of using evolutionary algorithms to solve the routing problem. Ant algorithms (MA), like most types of evolutionary algorithms, are based on the use of a population of potential solutions and are designed to solve combinatorial optimization problems, first of all, search for various paths on graphs. The cooperation between individuals (artificial ants) is implemented on the basis of stigmetry modeling. In addition, each agent, called artificial ant, is looking for a solution to the problem. Artificial ants consistently build a solution to the problem, moving around the graph, lay the pheromone and, when choosing a further section of the path, take into account the concentration of this enzyme. The higher the concentration of pheromone in the subsequent section, the greater the likelihood of its choice. Since MA is based on the movement of ants along some paths, MAs are effective, first of all, in solving problems that can be interpreted in the form of a graph. Computer experiments showed that the efficiency of MA increases with increasing dimension of the problem and for tasks on high-dimensional graphs they work faster than other evolutionary algorithms. Good results were also noted in solving non-stationary problems on graphs with a changing environment. In connection with this, the implementation of the meta - heuristic method is proposed as a modification of ant optimization algorithms. The scheme of the system is presented. A software product specification is also provided.

Дослідження показують, що 85-95% загальної тривалості логістичного ланцюга виробничого циклу товарного руху становить очікування на обробку, транспортування та інші операції, включаючи зберігання. Мета логістики - побудувати процес доставки «від дверей до дверей» з мінімальними втратами на місцях з'єднання, з мінімальними накопичувальними витратами та часом для сприяння інтегрованому логістичному потоку.У статті розглядаються актуальні питання використання еволюційних алгоритмів для вирішення задачі маршрутизації. Мурашині алгоритми, як і більшість видів еволюційних алгоритмів, засновані на використанні популяції потенційних рішень і розроблені для вирішення завдань комбінаторної оптимізації, перш за все, пошуку різних шляхів на графах. Кооперація між особинами (штучними мурашками) тут реалізується на основі моделювання стігметріі. При цьому кожен агент, званий штучним мурахою, шукає рішення поставленого завдання. Штучні мурашки послідовно будують рішення завдання, пересуваю-чись по графу, відкладають феромон і при виборі подальшого ділянки шляху враховують концентрацію цього ферменту. Чим більше концентрація феромону в подальшому ділянці, тим більша ймовірність його вибору. Оскільки в основі му-рашиного алгоритма лежить пересування мурах за деякими шляхах, то мурашині алгоритми ефективні, перш за все, при вирішенні завдань, які допускаю інтерпретацію у вигляді графа. Проведені комп'ютерні експерименти показали, що ефективність мурашиного алгоритма зростає при збільшенні розмірності задачі і для задач на графах високої розмірності вони працюють швидше, ніж інші еволюційні алгоритми. Відзначено також хороші результати при вирішенні нестаціонарних задач на графах зі змінною середовищем. В святи з цим пропонується реалізація мета -евристичного методу, як модифікації мурашиних алгоритмів оптимізації. Представлена схема роботи системи. Також представлена специфікація програмного продукту.Результатом дослідження стала розробка системи оптимізації перевезень, яка відповідає сучас-ним вимогам до програмного забезпечення. Програмне забезпечення адаптується до платформи Android.