Построение оптимального плана дозаправок с использованием агрегированных сведений о значениях параметров маршрута из открытых источников

   Введение. Представлены результаты исследования подходов к решению задачи комбинаторной условной оптимизации плана дозаправок вдоль фиксированного автомобильного маршрута с учетом ограничений на объем бака, начального и конечного объема топлива, а также постоянного расхода топлива. Методы решения подобных задач основаны на применении алгоритмов поиска кратчайших путей, а также на методах линейного программирования. Их недостатком является недостаточная детализация состояний, получение нецелочисленных решений и высокая вычислительная сложность.

   Новизна представленного решения заключается в использовании расширенного пространства состояний и в разработке точного алгоритма, гарантирующего целочисленность планов и более низкую асимптотическую сложность.

   Метод. Предложенный алгоритм основан на применении двумерного динамического программирования, при котором для каждого узла маршрута и остатка топлива пересчитывается минимальная стоимость достижения состояния путем выбора между переходом без дозаправки и переходом с дозаправкой на одно деление бака. Алгоритм позволяет решать задачу оптимально за полиномиальное время при квадратичной сложности относительно числа узлов маршрута.

   Основные результаты. Апробация метода проводилась путем сравнения предложенного алгоритма с альтернативными подходами, основанными на графовых представлениях маршрута и методах линейного программирования. Для каждого подхода были построены алгоритмы решения поставленной задачи, после чего проведен сравнительный анализ их асимптотической сложности, а также точности и целочисленности получаемых решений. Предложенный алгоритм, в отличие от альтернативных вариантов, обеспечивает одновременно целочисленность компонент оптимального решения и имеет более низкую асимптотическую сложность.

   Обсуждение. Разработанные алгоритмы применимы для снижения затрат на топливо при транспортировке грузов, а также для повышения экономической эффективности туристических поездок по России. Дальнейшее направление исследования связано с учетом дополнительных факторов, влияющих на расход топлива, что потребует перехода к задачам большей размерности и разработке эвристических методов для их эффективного решения.

1. Kovács G. Optimization method and software for fuel cost reduction in case of road transport activity // Acta Polytechnica. 2017. N 57. N 3. P. 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. V. 666. P. 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. V. 61. P. 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. P. 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. V. 12. N 5. P. 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. P. 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. V. 51. N 3. P. 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. V. 186. P. 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. V. 23. N 5. P. 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. P. 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. P. 110–114. doi: 10.1145/3388176.3388186

12. Корепанова А.А., Есин М.С., Сабреков А.А. Подходы к разработке сервиса учетa расходов на топливо и маршрутной адаптации с учетом пользовательских параметров // Региональная информатика и информационная безопасность : Сборник трудов. 2023. № 12. С. 294–297.

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. V. 28. N 3. P. 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. V. 10. N 3. P. 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. P. 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. V. 39. N 2. P. 3130–3140. doi: 10.1109/TPWRS.2023.3287199

18. Есин М.С., Корепанова А.А., Сабреков А.А. Агрегация и анализ сведений логистических компаний для построения сложного маршрута перевозки груза // Программные продукты и системы. 2023. № 2. С. 309–319. doi: 10.15827/0236-235X.142.309-319