Максим Сергеевич Есин, младший научный сотрудник
199178; Санкт-Петербург
sc 58493347500
Maxim S. Esin, Junior Researcher
199178; Saint Petersburg
sc 58493347500
Максим Викторович Абрамов, кандидат технических наук, ведущий научный сотрудник
199178; Санкт-Петербург
sc 56938320500
Maxim V. Abramov, PhD, Leading Researcher
199178; Saint Petersburg
sc 56938320500
Введение. Представлены результаты исследования подходов к решению задачи комбинаторной условной оптимизации плана дозаправок вдоль фиксированного автомобильного маршрута с учетом ограничений на объем бака, начального и конечного объема топлива, а также постоянного расхода топлива. Методы решения подобных задач основаны на применении алгоритмов поиска кратчайших путей, а также на методах линейного программирования. Их недостатком является недостаточная детализация состояний, получение нецелочисленных решений и высокая вычислительная сложность.
Новизна представленного решения заключается в использовании расширенного пространства состояний и в разработке точного алгоритма, гарантирующего целочисленность планов и более низкую асимптотическую сложность.
Метод. Предложенный алгоритм основан на применении двумерного динамического программирования, при котором для каждого узла маршрута и остатка топлива пересчитывается минимальная стоимость достижения состояния путем выбора между переходом без дозаправки и переходом с дозаправкой на одно деление бака. Алгоритм позволяет решать задачу оптимально за полиномиальное время при квадратичной сложности относительно числа узлов маршрута.
Основные результаты. Апробация метода проводилась путем сравнения предложенного алгоритма с альтернативными подходами, основанными на графовых представлениях маршрута и методах линейного программирования. Для каждого подхода были построены алгоритмы решения поставленной задачи, после чего проведен сравнительный анализ их асимптотической сложности, а также точности и целочисленности получаемых решений. Предложенный алгоритм, в отличие от альтернативных вариантов, обеспечивает одновременно целочисленность компонент оптимального решения и имеет более низкую асимптотическую сложность.
Обсуждение. Разработанные алгоритмы применимы для снижения затрат на топливо при транспортировке грузов, а также для повышения экономической эффективности туристических поездок по России. Дальнейшее направление исследования связано с учетом дополнительных факторов, влияющих на расход топлива, что потребует перехода к задачам большей размерности и разработке эвристических методов для их эффективного решения.
The paper presents the results of a study of approaches to solving the problem of combinatorial conditional optimization of the refueling plan along a fixed automobile route, taking into account restrictions on tank volume, initial and final fuel volumes as well as constant fuel consumption. Methods for solving such problems are based on the use of algorithms for finding the shortest paths as well as linear programming methods. Their disadvantage is the lack of granularity of states, obtaining non-integer solutions, and high computational complexity. The novelty of the solution lies in the use of an expanded state space and the development of an accurate algorithm that guarantees a high number of plans and a lower asymptotic complexity. The proposed algorithm is based on the application of two-dimensional dynamic programming in which for each node of the route and the remaining fuel, the minimum cost of reaching the state is recalculated by choosing between a transition without refueling and a transition with refueling by one tank division. The algorithm allows solving the problem optimally in polynomial time with quadratic complexity relative to the number of nodes on the route. The method was tested by comparing the proposed algorithm with alternative approaches based on graph representations of the route and linear programming methods. Algorithms for solving the problem were constructed for each approach after which a comparative analysis of their asymptotic complexity, as well as the accuracy and integers of the solutions obtained, was carried out. The proposed algorithm simultaneously ensures the integers of the components of the optimal solution and has a lower asymptotic complexity, unlike the alternative ones. The developed algorithms are applicable to reduce fuel costs during cargo transportation as well as to increase the economic efficiency of tourist trips in Russia. The further direction of the study is related to considering additional factors affecting fuel consumption which will require a transition to higher-dimensional tasks and the development of heuristic methods for their effective solution.
The authors declare that there are no conflicts of interest present.