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.

1. Kovács G. Optimization method and software for fuel cost reduction in case of road transport activity. Acta Polytechnica, 2017, no. 57, no. 3, pp. 201–208. doi: 10.14311/AP.2017.57.0201

2. Goryaev N.K., Khabibullozoda Кh.Кh., Faizalizoda F.H. Research of factors affecting yrucks fuel consumption: review. IOP Conference Series: Earth and Environmental Science, 2021, vol. 666, pp. 042056. doi: 10.1088/1755-1315/666/4/042056

3. Chikishev E., Chainikov D. Assessment of external factors influence on the fuel consumption of a diesel bus operating on a city route. Transportation Research Procedia, 2022, vol. 61, pp. 354–360. doi: 10.1016/j.trpro.2022.01.057

4. Rizzoli A., Casagrande N., Donati A.V., Gambardella L.M., Lepori D., Montemanni R., Pina P., Zaffalon M. Planning and optimisation of vehicle routes for fuel oil distribution. Proc. of the MODSIM International Congress on Modelling and Simulation, 2003, pp. 1–6.

5. Pérez M.A.J, Loaiza R.E.P., Flores P.M.Q, Ponce O.A., Peralta C.F. A heuristic algorithm for the routing and scheduling problem with time windows: a case study of the automotive industry in Mexico. Algorithms, 2019, vol. 12, no. 5, pp. 111. doi: 10.3390/a12050111

6. Kelner J.A., Spielman D.A. A randomized polynomial-time simplex algorithm for linear programming. Proc. of the 38^th Annual ACM Symposium on Theory of Computing, 2006, pp. 51–60. doi: 10.1145/1132516.1132524

7. Spielman D.A., Teng S.-H. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Journal of the ACM, 2001, vol. 51, no. 3, pp. 385–463. doi: 10.1145/990308.990310

8. Wang H., Mao W., Eriksson L. A Three-Dimensional Dijkstra’s algorithm for multi-objective ship voyage optimization. Ocean Engineering, 2019, vol. 186, pp. 106131. doi: 10.1016/j.oceaneng.2019.106131

9. Xu B., Chen X., Li K., Hu M., Bian Y., Yu Q., Wang J. Double-layer speed optimization for reducing fuel consumption with vehicle-to-infrastructure communication. Journal of Intelligent Transportation Systems: Technology, Planning and Operations. 2019, vol. 23, no. 5, pp. 513–524. doi: 10.1080/15472450.2019.1578565

10. Abousleiman R., Rawashdeh O. A Bellman-Ford approach to energy efficient routing of electric vehicles. Proc. of the IEEE Transportation Electrification Conference and Expo (ITEC), 2015, pp. 1–4. doi: 10.1109/ITEC.2015.7165772

11. Hossain M.A., Ahmedy I., Harith M.Z., Idris M., Soon T.K., Noor R.M., Yusoff S.B. Route optimization by using Dijkstra’s algorithm for the waste management system. Proc. of the 3^rd International Conference on Information Science and Systems, 2020, pp. 110–114. doi: 10.1145/3388176.3388186

12. Korepanova A., Esin M., Sabrekov A. Approaches to the development of a fuel cost accounting and route adaptation service according to user parameters. Proc. of the Regional Informatics and Information Security, 2023, no. 12, pp. 294–297. (in Russian)

13. Zhang Y., Cao W., Zhao H., Gao S. Route planning algorithm based on dynamic programming for electric vehicles delivering electric power to a region isolated from power grid. Artificial Life and Robotics, 2023, vol. 28, no. 3, pp. 583–590. doi: 10.1007/s10015-023-00879-7

14. Choi G.-H., Lee W., Kim T. Voyage optimization using dynamic programming with initial quadtree based route. Journal of Computational Design and Engineering, 2023, vol. 10, no. 3, pp. 1185–1203. doi: 10.1093/jcde/qwad055

15. Bazaraa M., Jarvis J., Sherali H. Linear Programming and Network Flows. John Wiley & Sons, 2009, 768 p.

16. Zolotykh D.A., Sabrekov A.A., Esin M.S., Korepanova A.A. Automating the construction of an optimal refuelling plan along a car route taking into account the limit on the number of stops. Proc. of the 27^th International Conference on Soft Computing and Measurements (SCM), 2024, pp. 389–392. doi: 10.1109/SCM62608.2024.10554122

17. Hou J., Zhai Q., Zhou Y., Guan X. A fast solution method for large-scale unit commitment based on lagrangian relaxation and dynamic programming. IEEE Transactions on Power Systems, 2024, vol. 39, no. 2, pp. 3130–3140. doi: 10.1109/TPWRS.2023.3287199

18. Esin M.S., Korepanova A.A., Sabrekov A.A. Aggregation and analysis of information from logistics companies to build a complex cargo transportation route. Software & Systems, 2023, vol. 36, no. 2, pp. 309–319. (in Russian). doi: 10.15827/0236-235X.142.309-319