Управление сложными логистическими процессами современных предприятий требует разработки адекватных математических моделей, позволяющих рассчитать оптимальные планы перевозки. Одной из таких моделей является транспортная задача с фиксированными доплатами, особенностью которой является нелинейность функции цели. Настоящее исследование посвящено разработке генетического алгоритма решения транспортной задачи с фиксированными доплатами. Основу исследования составляет проведенный анализ существующих подходов к решению различных модификаций транспортных задач. Особенностью предлагаемого алгоритма является формирование на каждом из этапов хромосом, удовлетворяющих ограничениям задачи, что позволяет сократить время решения. В исследовании подробно представлены шаги алгоритма формирования начальной популяции, кроссинговера и мутации, адаптированные к условиям транспортной задачи с фиксированными доплатами. В основу формирования начальной популяции положен подход случайного выбора пары «поставщик-потребитель», что обеспечивает ее достаточное разнообразие. Оператор кроссинговера реализуется посредством разработки алгоритма, основанного на делении по модулю двух сумм генов родителей и последующем перераспределении остатков от деления между потомками. Алгоритм мутации хромосомы основан на изменении плана перевозок для случайно выбранных строк и столбцов при сохранении допустимости особи. Для проведения вычислительного эксперимента разработан программный продукт на языке Python, приведен демонстрационный пример расчета. Результаты проведенных расчетов для группы сельхозпроизводителей позволили сделать выводы о практической значимости предлагаемого алгоритма и выявили возможности его использования для решения многоэтапных транспортных задач, актуальных для крупных производственных и логистических компаний.
Managing complex logistics processes of modern enterprises requires the development of adequate mathematical models that make it possible to calculate optimal transportation plans. One of these models is the transport problem with fixed surcharges, the feature of which is the nonlinearity of the goal function. This study is devoted to the development of a genetic algorithm for solving a transport problem with fixed surcharges. The basis of the study is the analysis of existing approaches to solving various modifications of transport problems. A feature of the proposed algorithm is the formation at each stage of chromosomes that satisfy the constraints of the problem, which allows reducing the solution time. The study presents in detail the steps of the algorithm for forming the initial population, crossing over and mutation, adapted to the conditions of the transport problem with fixed surcharges. The formation of the initial population is based on the approach of randomly selecting a “supplier-consumer” pair, which ensures its sufficient diversity. The crossing over operator is implemented by developing an algorithm based on dividing modulo two the sum of the genes of the parents and subsequent redistribution of the remainders from the division between the descendants. The chromosome mutation algorithm is based on changing the transportation plan for randomly selected rows and columns while maintaining the admissibility of the individual. To conduct a computational experiment, a software product was developed in Python, and a demonstration example of the calculation is given. The results of the calculations for a group of agricultural producers allowed us to draw conclusions about the practical significance of the proposed algorithm and identified the possibilities of its use for solving multi-stage transport problems that are relevant for large manufacturing and logistics companies.
The authors declare that there are no conflicts of interest present.