All issues

В данной работе проводится сравнительный анализ точного и эвристических алгоритмов, представленных методом ветвей и границ, генетическим и муравьиным алгоритмами соответственно, для поиска оптимального решения задачи коммивояжера на примере робота-курьера. Целью работы является определение времени работы, длины полученного маршрута и объема памяти, необходимого для работы программы, при использовании метода ветвей и границ и эволюционных эвристических алгоритмов. Также определяется наиболее целесообразный из перечисленных методов для применения в заданных условиях. В настоящей статье используются материалы проведенного исследования, реализованного в формате программы для ЭВМ, программный код для которой реализован на языке Python. В ходе исследования был выбран ряд критериев применимости алгоритмов (время работы программы, длина построенного маршрута и объем необходимой для работы программы памяти), получены результаты работы алгоритмов в заданных условиях и сделаны выводы о степени целесообразности применения того или иного алгоритма в различных заданных условиях работы робота-курьера. В ходе исследования выяснилось, что для малого количества точек ($\leqslant10$) метод ветвей и границ является наиболее предпочтительным, так как находит оптимальное решение быстрее. Однако при вычислении маршрута этим методом, при условии увеличения точек более 10, время работы растет экспоненциально. В таком случае более эффективные результаты дает эвристический подход с использованием генетического и муравьиного алгоритмов. При этом муравьиный алгоритм отличается решениями, наиболее близкими к эталонным, при увеличении точек более 16. Относительным недостатком его является наибольшая ресурсоемкость среди рассматриваемых алгоритмов. Генетический алгоритм дает схожие результаты, но при увеличении точек более 16 растет длина найденного маршрута относительно эталонного. Преимущество генетического алгоритма — его меньшая ресурсоемкость по сравнению с другими алгоритмами.

Практическая значимость данной статьи заключается в потенциальной возможности использования полученных результатов для оптимального решения логистических задач автоматизированной системой в различных сферах: складская логистика, транспортная логистика, логистика «последней мили» и т. д.

In this paper, a comparative analysis of the exact and heuristic algorithms presented by the method of branches and boundaries, genetic and ant algorithms, respectively, is carried out to find the optimal solution to the traveling salesman problem using the example of a courier robot. The purpose of the work is to determine the running time, the length of the obtained route and the amount of memory required for the program to work, using the method of branches and boundaries and evolutionary heuristic algorithms. Also, the most appropriate of the listed methods for use in the specified conditions is determined. This article uses the materials of the conducted research, implemented in the format of a computer program, the program code for which is implemented in Python. In the course of the study, a number of criteria for the applicability of algorithms were selected (the time of the program, the length of the constructed route and the amount of memory necessary for the program to work), the results of the algorithms were obtained under specified conditions and conclusions were drawn about the degree of expediency of using one or another algorithm in various specified conditions of the courier robot. During the study, it turned out that for a small number of points  $\leqslant10$, the method of branches and boundaries is the most preferable, since it finds the optimal solution faster. However, when calculating the route by this method, provided that the points increase by more than 10, the operating time increases exponentially. In this case, more effective results are obtained by a heuristic approach using a genetic and ant algorithm. At the same time, the ant algorithm is distinguished by solutions that are closest to the reference ones and with an increase of more than 16 points. Its relative disadvantage is the greatest resource intensity among the considered algorithms. The genetic algorithm gives similar results, but after increasing the points more than 16, the length of the found route increases relative to the reference one. The advantage of the genetic algorithm is its lower resource intensity compared to other algorithms.

The practical significance of this article lies in the potential possibility of using the results obtained for the optimal solution of logistics problems by an automated system in various fields: warehouse logistics, transport logistics, «last mile» logistics, etc.

В работе представлено экспериментальное исследование древовидной структуры, возникающей при медицинском обследовании. При каждой встрече с медицинским специалистом пациент получает некоторое количество направлений на консультации других специалистов или на анализы. Возникает дерево направлений, каждую ветвь которого должен пройти пациент. В зависимости от разветвленности дерева оно может быть как конечным (и в этом случае обследование может быть завершено), так и бесконечным, когда цель пациента не может быть достигнута. В работе как экспериментально, так и теоретически изучаются критические свойства перехода системы из леса конечных деревьев в лес бесконечных в зависимости от вероятностных характеристик дерева.

Для описания предлагается модель, в которой дискретная функция вероятности числа ветвей на узле повторяет динамику непрерывного гауссового распределения. Характеристики распределения Гаусса (математическое ожидание $x_0$, среднеквадратичное отклонение $\sigma$) являются параметрами модели. В выбранной постановке задача относится к проблематике ветвящихся случайных процессов (ВСП) в неоднородной модели Гальтона – Ватсона.

Экспериментальное изучение проводится путем численного моделирования на конечных решетках. Построена фазовая диаграмма, определены границы областей различных фаз. Проведено сравнение с фазовой диаграммой, полученной из теоретических критериев для макросистем, установлено адекватное соответствие. Показано, что на конечных решетках переход является размытым.

Описание размытого фазового перехода проведено с помощью двух подходов. В первом (стандартном) подходе переход описывается с помощью так называемой функции включения, имеющей смысл доли одной из фаз в общем множестве. Установлено, что такой подход в данной системе неэффективен, поскольку найденное положение условной границы размытого перехода определяется только размером выбранной экспериментальной решетки и не несет объективного смысла.

Предлагается второй (оригинальный) подход, основанный на введении в рассмотрение параметра порядка, равного обратной средней высоте дерева, и анализа его поведения. Установлено, что динамика такого параметра порядка в сечениях $\sigma = \text{const}$ с очень небольшими отличиями имеет вид распределения Ферми – Дирака ($\sigma$ выполняет ту же функцию, что и температура для распределения Ферми – Дирака, $x_0$ — функцию энергии). Для параметра порядка подобрано эмпирическое выражение, введен и рассчитан аналог химического потенциала, который и имеет смысл характерного масштаба параметра порядка, то есть тех значений $x_0$, при которых условно можно считать, что порядок сменяется беспорядком. Этот критерий положен в основу определе- ния границы условного перехода в данном подходе. Установлено, что эта граница соответствует средней высоте дерева, равной двум поколениям. На основании обнаруженных свойств предложены рекомендации для медицинских учреждений, позволяющие контролировать обеспечение конечности траектории пациентов.

Рассмотренная модель и метод ее описания с помощью условно-бесконечных деревьев имеют приложение ко многим иерархическим системам. К таким системам можно отнести сети маршрутизации интернет-соединений, бюрократические сети, торговые, логистические сети, сети цитирования, игровые стратегии, задачи популяционной динамики и пр.

The work presents an experimental study of the tree structure that occurs during a medical examination. At each meeting with a medical specialist, the patient receives a certain number of areas for consulting other specialists or for tests. A tree of directions arises, each branch of which the patient should pass. Depending on the branching of the tree, it can be as final — and in this case the examination can be completed — and endless when the patient’s goal cannot be achieved. In the work both experimentally and theoretically studied the critical properties of the transition of the system from the forest of the final trees to the forest endless, depending on the probabilistic characteristics of the tree.

For the description, a model is proposed in which a discrete function of the probability of the number of branches on the node repeats the dynamics of a continuous gaussian distribution. The characteristics of the distribution of the Gauss (mathematical expectation of $x_0$, the average quadratic deviation of $\sigma$) are model parameters. In the selected setting, the task refers to the problems of branching random processes (BRP) in the heterogeneous model of Galton – Watson.

Experimental study is carried out by numerical modeling on the final grilles. A phase diagram was built, the boundaries of areas of various phases are determined. A comparison was made with the phase diagram obtained from theoretical criteria for macrosystems, and an adequate correspondence was established. It is shown that on the final grilles the transition is blurry.

The description of the blurry phase transition was carried out using two approaches. In the first, standard approach, the transition is described using the so-called inclusion function, which makes the meaning of the share of one of the phases in the general set. It was established that such an approach in this system is ineffective, since the found position of the conditional boundary of the blurred transition is determined only by the size of the chosen experimental lattice and does not bear objective meaning.

The second, original approach is proposed, based on the introduction of an parameter of order equal to the reverse average tree height, and the analysis of its behavior. It was established that the dynamics of such an order parameter in the $\sigma = \text{const}$ section with very small differences has the type of distribution of Fermi – Dirac ($\sigma$ performs the same function as the temperature for the distribution of Fermi – Dirac, $x_0$ — energy function). An empirical expression has been selected for the order parameter, an analogue of the chemical potential is introduced and calculated, which makes sense of the characteristic scale of the order parameter — that is, the values of $x_0$, in which the order can be considered a disorder. This criterion is the basis for determining the boundary of the conditional transition in this approach. It was established that this boundary corresponds to the average height of a tree equal to two generations. Based on the found properties, recommendations for medical institutions are proposed to control the provision of limb of the path of patients.

The model discussed and its description using conditionally-infinite trees have applications to many hierarchical systems. These systems include: internet routing networks, bureaucratic networks, trade and logistics networks, citation networks, game strategies, population dynamics problems, and others.

В работе рассматриваются возможности реализации крупноблочных схем метода ветвей и границ для решения частично целочисленных задач линейного программирования. В качестве основы берется пакет оптимизации с открытым исходным кодом CBC. Анализируется возможность использования пакета для реализации крупноблочной схемы метода ветвей и границ. Система реализуется с использованием языка Erlang. Проводятся численные эксперименты на основе задачи о коммивояжере, показывающие заметное ускорение распределенной схемы решения задачи по сравнению с единичным однопоточным экземпляром пакета.

The paper presents an implementation of branch and bound algorithm employing coarse grained parallelism. The system is based on CBC (COIN-OR branch and cut) open-source MIP solver and inter-process communication capabilities of Erlang. Numerical results show noticeable speedup in comparison to single-threaded CBC instance.