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

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

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

железнодорожные грузоперевозки, оптимальное планирование, линейное программирование, методы округления, теория расписаний

Получено

29.12.2022

Дата публикации

30.12.2022

Кол-во символов

15191

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Белоусов Ф. А. Один из методов округления решения в задаче управления парком грузовых вагонов // Вестник ЦЭМИ – 2022. – Tом 5. – Выпуск 4 [Электронный ресурс]. URL: https://cemi.jes.su/S265838870023767-6-1 (дата обращения: 19.07.2024). DOI: 10.33276/S265838870023767-6
MLA	Belousov, Fedor "One of the methods of rounding solutions in the problem of managing a fleet of freight railcars." Vestnik CEMI 5.4 (2022) DOI: 10.33276/S265838870023767-6
APA	Belousov F. (2022). One of the methods of rounding solutions in the problem of managing a fleet of freight railcars. Vestnik CEMI 5(4) DOI: 10.33276/S265838870023767-6

100 руб.

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

Оператором распространения коммерческих препринтов является ООО «Интеграция: ОН»


1	Введение
2	В статье рассматривается модель, которая изучалась автором в коллективе с другими соавторами [1; 2]. В указанных работах рассматриваются методы решения задачи, которые в общем случае в качестве ответа дают нецелочисленный результат. Однако на практике при составлении плана передвижения грузовых вагонов нецелочисленные решения по понятным причинам не применимы. Поэтому требуются либо методы, которые сразу дают целочисленное решение, либо методы округления полученного нецелочисленного решения.
3	Если говорить о способах, которые сразу дают точное целочисленное решение, то известно, что такие задачи относятся к классу NP-полных задач. Поэтому все методы, связанные с поиском целочисленных решений, главным образом основаны на итерационном решении линейной релаксации различных модификаций исходной задачи (то есть на каждой итерации находится нецелочисленное решение), и такие методы не гарантируют нахождение точного решения. Среди наиболее известных методов можно выделить метод ветвления и границ и метод Гомори. В условиях нашей задачи, которая характеризуется большой размерностью, напрямую такие подходы неприменимы, поскольку итерационный расчет целочисленного решения связан с большим временем, затраченным на поиск решения, что является неприемлемым для оперативного управления логистикой предприятия.
4	В работах [3; 4] рассматривается похожая постановка транспортной задачи, которую авторы решают с помощью метода генерации колонок. Они также получают нецелочисленные решения. В отличие от них мы в своем подходе не прибегаем к этому методу в силу того, что возможны трудности с его применением в случае, если исходная задача будет усложняться за счет учета новых типов ограничений. Поэтому в данной работе представлен другой, в чем-то более простой, подход получения нецелочисленного решения исходной задачи. Тем не менее, в предлагаемом методе округления заимствуются некоторые идеи метода декомпозиции Данцига-Вульфа и, соответственно, метода генерации колонок [5].
5	Основная идея метода генерации колонок состоит в переходе от задачи, сформулированной в терминах потоков, которая в английской литературе носит название multi-commodity flow (MCF) [6] к задаче, сформулированной в терминах готовых цепочек маршрутов. При этом алгоритм является итерационным, и на каждой итерации множество цепочек маршрутов постоянно увеличивается. По всей видимости, из-за большого количества полученных цепочек могут возникать проблемы с поиском целочисленного решения в задаче, сформулированной в терминах цепочек маршрутов. Основная идея подхода, изложенного в данной работе, состоит в нахождении нецелочисленного решения MCF задачи, после чего данное решение разбирается на цепочки решений, что дает относительно небольшое множество таких цепочек, затем на основе этого множества решается целочисленная задача, сформулированная в терминах цепочек маршрутов.

всего просмотров: 65

Оценка читателей: голосов 0

1. Белоусов, Ф. А. Моделирование и оптимизация планов грузовых железнодорожных перевозок, выполняемых транспортным оператором / Ф. А. Белоусов, И. В. Неволин, Н. К. Хачатрян // Бизнес-информатика. – 2020. – Т. 14, № 2. – с. 21–35. – URL : https://bijournal.hse.ru/data/2020/06/29/1610380184/BI%202_2020%20RU-21-35.pdf (дата обращения : 05.12.2022).

2. Белоусов, Ф. А. Снижение размерности в задаче оптимального управления парком грузовых вагонов с использованием беспилотных локомотивов / Ф. А. Белоусов, И. В. Неволин, Н. К. Хачатрян // Бизнес-информатика. – 2022. – Т. 16, № 2. – с. 7–20. – URL : https://bijournal.hse.ru/data/2022/06/30/1639228675/1.pdf (дата обращения : 05.12.2022).

3. Лазарев, А. А. Задача управления парком грузовых железнодорожных вагонов / А. А. Лазарев, Р. Р. Садыков // XII Всероссийское совещание по проблемам управления (ВСПУ 2014) ( Москва, 16–19 июня 2014) / ИПУ РАН. – Москва, 2014. – с. 5083–5093.

4. Sadykov, R. Solving a freight railcar flow problem arising in Russia / R. Sadykov, A. Lazarev, V. Shiryaev, A. Stratonnikov // Proceedings of 13th Workshop on Algorithmic Approach for Transportation Modelling, Optimization, and Systems (ATMOS’13) (Leibniz, Germany, 5 September 2013). – p. 55–67. – URL : https://drops.dagstuhl.de/opus/volltexte/2013/4244/pdf/6.pdf (дата обращения : 05.12.2022).

5. Desaulniers, G. Column generation / G. Desaulniers , J. Desrosiers , M. Solomon. – New York: Springer, 2005. – URL : https://link.springer.com/book/10.1007/b135457 (дата обращения : 05.12.2022).

6. Ahuja, Ravindra K. Capacity Scaling Algorithm / Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. // Network Flows: Theory, Algorithms and Applications. — Prentice Hall, 1993. – p. 210-211.

7. Fukasawa, Ricardo. Solving the freight car flow problem to optimality / Ricardo Fukasawa, Marcus Poggi de Aragão, Oscar Porto, and Eduardo Uchoa // Electronic Notes in Theoretical Computer Science. – 2002. – 66(6). – p. 42–52. – URL : https://www.sciencedirect.com/science/article/pii/S1571066104805280?via%3Dihub (дата обращения : 05.12.2022).