Building an optimal refueling plan using aggregated information about route parameter values from open sources

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.