The paper discusses the concept of a trip cost estimation service, which allows minimizing fuel expenses by constructing an optimal refueling plan along a fixed route. The service operates based on solving a discrete optimization problem related to finding the globally optimal refueling plan considering the locations of refueling stations and constraints on the total number of stops. To construct the optimal plan, it is proposed to use methods of three-dimensional dynamic programming with state dynamics recalculation. The study includes an asymptotic analysis of the constructed polynomial algorithm, as well as performance measurements of the algorithm, demonstrating a high degree of practical applicability of the results.