One of the methods of rounding solutions in the problem of managing a fleet of freight railcars

The paper considers one of the methods of rounding a non-integer solution in the problem of optimal management of a fleet of railcars at a given time interval, which is reduced to solving a large-dimensional linear programming problem. There are a number of well-known methods for obtaining integer solutions or rounding methods that can be applied to an arbitrary linear programming problem, however, as is often the case, general methods are not always applicable to particular problems. Such tasks may require an individual approach, and the problem under consideration belongs to this type of tasks. The main limitation of the problem under consideration is its huge dimension, which in practice can reach several tens of millions of variables. The main idea of the presented approach is to obtain a non-integer solution at the first stage, then this solution is translated into the format of route chains, after which a new integer problem is solved, but already on the existing set of route chains. The new problem is characterized by a relatively small dimension and gives an integer answer no later than a few seconds.

Keywords

railway freight transportation, optimal planing, linear programming, rounding methods, theory of schedules

Received

29.12.2022

Publication date

30.12.2022

Number of characters

15191

Cite Download pdf To download PDF you should sign in

GOST	Belousov F. One of the methods of rounding solutions in the problem of managing a fleet of freight railcars // Vestnik CEMI – 2022. – V. 5. – Issue 4 [Electronic resource]. URL: https://cemi.jes.su/S265838870023767-6-1 (circulation date: 20.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 rub.

When subscribing to an article or issue, the user can download PDF, evaluate the publication or contact the author. Need to register.


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

Readers community rating: votes 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).