On the Scheduling Problem of Cargo Transportation on a Railway Network Segment and Algorithms for its Solution

Рассматривается задача составления расписания грузоперевозок на участке железнодорожной сети. Железнодорожная сеть представляется неориентированным мультиграфом. Движение по ребрам мультиграфа осуществляется только в определенные промежутки времени - с использованием "подниток". Формулируется новая математическая модель движения по ребрам графа. Предлагается универсальный критерий оптимальности для задачи составления расписания. Предлагается алгоритм поиска субоптимального решения. Рассматривается содержательный пример.

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

мультиграф; грузоперевозки; железнодорожная сеть; расписание; смешанное целочисленное линейное программирование.

Литература

1. Azanov, V.M. Algorithm and Software Development to Allocate Locomotives for Transportation of Freight Trains / V.M. Azanov, M.V. Buyanov, D.N. Gaynanov, S.V. Ivanov // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2016. - Т. 9, № 4. - С. 73-85.
2. Buyanov, M.V. Algorithm of Effective Transportation Work for Cargo Traffic / M.V. Buyanov, A.I. Kibzun // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2018. - Т. 11, № 1. - С. 75-83.
3. Ziarati, K. Locomotive Assignment with Heterogeneous Consists at CN North America / K. Ziarati, F. Soumis, J. Desrosiers, S. Gelinas, A. Saintonge // European Journal of Operational Research. - 1997. - № 97. - P. 281-292.
4. Ahuja, R.K. Solving Real-Life Locomotive-Scheduling Problems / R.K. Ahuja, Liu Jian, J. Orlin, D. Sharma, L. Shughart // Transportation Science. - 2005. - V. 39, № 4. - P. 503-517.
5. Босов, А.В. Модель передвижения поездов и маневровых локомотивов на железнодорожной станции в приложении к оценке и анализу вероятности бокового столкновения / А.В. Босов, А.Н. Игнатов, А.В. Наумов // Информатика и ее применения. - 2018. - Т. 12, № 3. - C. 107-114.
6. Cordeau, J. A Survey of Optimization Models for Train Routing and Scheduling / J. Cordeau, P. Toth, D. Vigo // Transportation Science. - 1998. - V. 32, № 4. - P. 380-404.
7. Caprara, A. Modeling and Solving the Train Timetabling Problem / A. Caprara, M. Fischetti, P. Toth // Operations Research. - 2002. - V. 50, № 5. - P. 851-861.
8. Kroon, L. Stochastic Improvement of Cyclic Railway Timetables / L. Kroon, G. Maroti, M. Helmrich // Transportation Research Part B: Methodological. - 2008. - V. 42, № 6. - P. 553-570.
9. Lazarev, A.A. The Problem of Trains Formation and Scheduling: Integer Statements / A.A. Lazarev, E.G. Musatova // Automation and Remote Control. - 2013. - V. 74, № 12. - P. 2064-2068.
10. Zinder, Y. Scheduling the Two-Way Traffic on a Single-Track Railway with a Siding / Y. Zinder, A.A. Lazarev, E.G. Musatova, I. Tarasov // Automation and Remote Control. - 2018. - V. 79, № 3. - P. 506-523.
11. Zinder, Y. Rescheduling Traffic on a Partially Blocked Segment of Railway with a Siding / Y. Zinder, A.A. Lazarev, E.G. Musatova // Automation and Remote Control. - 2020. - V. 81, № 6. - P. 955-966.
12. Ignatov, A.N. On Time Selection for Track Possession Assignment at the Railway Station / A.N. Ignatov, A.V. Naumov // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2019. - Т. 12, № 3. - С. 5-16.
13. Gainanov, D.N. On track Procession Assignment Problem at the Railway Network Sections / D.N. Gainanov, A.N. Ignatov, A.N. Ignatov, A.V. Naumov, V.A. Rasskazova // Automation and Remote Control. - 2020. - V. 81, № 6. - P. 967-977.
14. Буянов, М.В. Развитие математической модели управления грузоперевозками на участке железнодорожной сети с учетом случайных факторов / М.В. Буянов, С.В. Иванов, A.И. Kibzun, A.B. Naumov // Информатика и ее применения. - 2017. - T. 11, № 4. - С. 85-93.
15. Ignatov, A.N. On the Problem of Increasing the Railway Station Capacity / A.N. Ignatov, A.V. Naumov // Automation and Remote Control. - 2021. - V. 82, № 1. - P. 102-114.