Решение задачи маршрутизации в транспортной сети с использованием псевдополиномиальной модели

Авторы

  • Юлия Олеговна Полтавская Ангарский государственный технический университет

Ключевые слова:

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

Аннотация

Решение задачи маршрутизации транспортных средств заключается в построении маршрутов от автотранспортного предприятия к определенному количеству потребителей, расположенных в географическом пространстве. Разработка эффективных систем распределения позволяет минимизировать затраты на доставку, что является актуальным направлением совершенствования работы предприятия в современных экономических условиях, с целью обеспечения устойчивых транспортных связей между потребителями и для создания конкурентоспособности на рынке транспортных услуг. В статье рассматривается задача маршрутизации транспортных средств при обслуживании потребителей на нескольких маршрутах с учетом временных окон. Считается, что транспортное средство может быть назначено для работы более чем на одном маршруте за период планирования (рабочий день). Алгоритм решения задачи является итеративным и основан на использовании модели псевдополиномиального сетевого потока, узлы которой представляют моменты времени, а дуги – возможные маршруты транспортных средств. Алгоритм был протестирован на наборе данных из пяти потребителей и двух транспортных средств. Также стоит отметить, что вместимость транспортных средств является переменной, оказывающей существенное влияние на получение оптимального варианта решения задачи. В дальнейших исследованиях, направленных на поиск методов решения задачи маршрутизации, рекомендуется учитывать значение постоянных затрат, связанных с использованием транспортных средств, поскольку, оно оказывает значительное влияние на функцию минимизации затрат в случае применения на практике. Предлагаемый метод позволяет отследить данный момент, поскольку математическая модель и алгоритм принимают во внимание стоимостные затраты в целевой функции.

Биография автора

Юлия Олеговна Полтавская, Ангарский государственный технический университет

канд. техн. наук, доцент, доцент кафедры управления на автомобильном транспорте

Библиографические ссылки

Методы прогнозирования и оптимизации транспортной сети с учетом мощности пассажиро и грузопотоков / В.Е. Гозбенко, А.Н. Иванков, М.Н. Колесник и др. // Деп. рукопись 17.04.2008, № 330-В2008.

Лебедева О.А., Крипак М.Н. Моделирование грузовых перевозок в транспортной сети // Вестн. Ангар. гос. техн. ун-та. 2016. № 10. С. 182–184.

Лебедева О.А., Крипак М.Н. Развитие городских грузовых систем с учетом концепции городского планирования // Сб. науч. тр. Ангар. гос. техн. ун-та. 2016. Т. 1. № 1. С. 244–247.

Полтавская Ю.О. Оптимизация транспортной сети на основе минимума общих затрат на доставку грузов // Вестн. Ангар. гос. техн. ун-та. 2019. № 13. С. 178–183.

Казимиров А.О., Михайлов А.Ю., Шаров М.И. Современные особенности размещения логистических центров на примере города Иркутска // Авиамашиностроение и транспорт Сибири : сб. ст. XI Всерос. науч.-техн. конф. Иркутск, 2018. С. 28–32.

Казимиров А.О., Михайлов А.Ю. Задачи территориального размещения логистической инфраструктуры в городах // Авиамашиностроение и транспорт Cибири : сб. ст. IX Всерос. науч.-практ. конф. Иркутск, 2017. С. 351–355.

Просов С.Н., Жуков А.В. Эвристические процедуры сменно-суточного планирования развозочных маршрутов // Современные технологии управления в автотранспортных системах : сб. науч. тр. М. : МАДИ, 2007. С. 112–117.

Самуйлов В.М., Петров А.В., Зубарев А.К. Сравнительный анализ эвристических методов маршрутизации городского транспорта // Транспорт Урала. 2012. № 4 (35). С. 12–16.

Fuellerer K.G., Hartl D.R, Iori M. Metaheuristics for vehicle routing problems with three-dimensional loading constraints // European Journal of Operational Research. 2010. № 201 (3). Р. 751–759.

Lebedeva O., Kripak M., Gozbenko V. Increasing effectiveness of the transportation network by using the automation of a Voronoi diagram // Transportation Research Procedia. 2018. № 36. Р. 427–433.

Christiansen C.H., Lysgaard J. A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands // Operations Research Letters. 2007. Vol. 35. № 6. Р. 773–781.

Barkaoui M., Gendreau M. An adaptive evolutionary approach for real-time vehicle routing and dispatching // Computers & Operations Research. 2013. Vol. 40. № 7. Р. 1766–1776.

Sarasola B., Doerner K.F., Schmid V., Alba E. Variable neighborhood search for the stochastic and dynamic vehicle routing problem // Annals of Operations Research. 2016. Vol. 236. № 2. Р. 425–461.

Azi M.N., Potvin G.J.-Y. An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles // European Journal of Operational Research. 2010. 202. Р. 756–763.

Заводченко М.М., Карманов В.С. Эвристические методы решения задачи маршрутизации транспорта с временными окнами // Наука. Технологии. Инновации : тр. конф. В 9 ч. Новосибирск : Изд-во НГТУ, 2019. С. 247–250.

Lijun S., Xiangpei H., Zheng W. Research progress on vehicle path planning problems and solving methods // Systems Engineering. 2006. Vol. 24. Р. 31–36.

Чернышев Ю.О., Кубил В.Н. Обзор динамических задач маршрутизации транспорта // Программные продукты и системы. 2020. № 3. С. 491–501.

Оленцевич В.А., Гозбенко В.Е. Методическое и программное обеспечение прогнозирования значений уровня безопасности функционирования железнодорожной транспортной системы. Иркутск : Изд-во ИрГУПС, 2019. 172 с.

Колесник М.Н. Применение динамической транспортной задачи с задержками для согласования ритмов работы поставщиков и перевозчиков // Вестн. Иркут. гос. техн. ун-та. 2009. № 1 (37). С. 63–65.

Косенко О.В., Косенко Е.Ю., Номерчук А.Я. Анализ ограничений и вариации задач оптимизации при маршрутизации транспорта // Актуальные проблемы современной науки : материалы Междунар. науч.-практ. конф. В 4 ч. Уфа : Изд-во Башкир. государственный университет. Т 4. С. 163–167.

Лебедева О.А., Михайлов А.Ю. Классификация моделей, применяемая к грузовым системам // Сборник научных трудов Ангарского государственного технического университета. 2016. Т. 1. № 1. С. 248–251.

Solving a dynamic routing problem using an optimization algorithm / O.A. Lebedeva, J.O. Poltavskaya, V. Gozbenko et. al. // International Scientific Conference Energy Management of Municipal Facilities and Sustainable Energy Technologies : Journal of Physics: Conference Series. 2020. Р. 012101.

Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model / R. Macedo, C. Alves, J.M. Valério de Carvalho et al. // European Journal of Operational Research. 2011. 214(3). Р. 536–545.

Balagura A.A., Kuzmin O.V. Encoding and decoding algorithms for unlabeled trees // Journal of Physics: Conference Series. 2021. № 1847(1), Р. 012027. DOI:10.1088/1742-6596/1847/1/012027.

Kuzmin O.V., Khomenko A.P., Artyunin A.I. Development of special mathematical software using combinatorial numbers and lattice structure analysis // Advances and Applications in Discrete Mathematics. 2018. 19(3). Р. 229–242. DOI:10.17654/DM019030229.

Poltavskaya J., Lebedeva O., Gozbenko V. Automation of the solution to the problem of optimizing traffic in a multimodal logistics system // Advances in Intelligent Systems and Computing. 2021. Vol. 1258 AISC. Р. 255–261. DOI:10.1007/978-3-030-57450-5_23.

Гозбенко В.Е., Оленцевич В.А. Повышение безопасности работы железнодорожной транспортной системы на основе автоматизации технологии размещения и крепления груза в вагоне // Известия Транссиба. 2013. № 1 (13). С. 110–116.

Захаров В.В., Мугайских А.В. Динамическая адаптация генетического алгоритма маршрутизации транспорта на больших сетях // Управление большими системами. 2018. № 73. С. 108–133.

Емельянова Т.С. Эвристические и метаэвристические методы решения динамической транспортной задачи // Перспективные информационные технологии и интеллектуальные системы. 2007. №3 (31). С. 33–43.

Опубликован

2022-03-31

Как цитировать

Полтавская, Ю. О. (2022). Решение задачи маршрутизации в транспортной сети с использованием псевдополиномиальной модели. Современные технологии. Системный анализ. Моделирование, (1(73), 95-103. извлечено от https://ojs.irgups.ru/index.php/stsam/article/view/533

Наиболее читаемые статьи этого автора (авторов)