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

Есин Максим Сергеевич, Абрамов Максим Викторович

doi:10.17586/2226-1494-2025-25-4-780-788

2025 , ТОМ 25, НОМЕР 4 ( июль-август )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

doi: 10.17586/2226-1494-2025-25-4-780-788

УДК 004.021

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

Есин М.С., Абрамов М.В.

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования:

Есин М.С., Абрамов М.В. Построение оптимального плана дозаправок с использованием агрегированных сведений о значениях параметров маршрута из открытых источников // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 4. С. 780–788. doi: 10.17586/2226-1494-2025-25-4-780-788

Аннотация

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

Ключевые слова: оценка стоимости поездки, динамическое программирование, комбинаторная оптимизация, алгоритм пересчета динамики, асимптотическая оценка сложности

Благодарности. Работа выполнена в рамках проекта по государственному заданию СПб ФИЦ РАН № FFZF-2025-0006.

Список литературы

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. https://doi.org/10.14311/AP.2017.57.0201
Goryaev N.K., Khabibullozoda Kh.Kh., Faizalizoda F.H. Research of factors affecting yrucks fuel consumption: review // IOP Conference Series: Earth and Environmental Science. 2021. V. 666. P. 042056. https://doi.org/10.1088/1755-1315/666/4/042056
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. https://doi.org/10.1016/j.trpro.2022.01.057
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.
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. https://doi.org/10.3390/a12050111
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. https://doi.org/10.1145/1132516.1132524
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. https://doi.org/10.1145/990308.990310
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. https://doi.org/10.1016/j.oceaneng.2019.106131
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. http://doi.org/10.1080/15472450.2019.1578565
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. https://doi.org/10.1109/ITEC.2015.7165772
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. https://doi.org/10.1145/3388176.3388186
Корепанова А.А., Есин М.С., Сабреков А.А. Подходы к разработке сервиса учетaрасходов на топливо и маршрутной адаптации с учетом пользовательских параметров // Региональная информатика и информационная безопасность: Сборник трудов. 2023. № 12. С. 294–297.
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. https://doi.org/10.1007/s10015-023-00879-7
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. https://doi.org/10.1093/jcde/qwad055
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. https://doi.org/10.1109/SCM62608.2024.10554122
Bazaraa M., Jarvis J., Sherali H. Linear Programming and Network Flows. John Wiley & Sons, 2009. 768 p.
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. https://doi.org/10.1109/TPWRS.2023.3287199
Есин М.С., Корепанова А.А., Сабреков А.А. Агрегация и анализ сведений логистических компаний для построения сложного маршрута перевозки груза // Программные продукты и системы. 2023. № 2. С. 309–319. https://doi.org/10.15827/0236-235X.142.309-319

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License