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

We consider the problem of scheduling cargo transportation on a railway network segment. The railway network is represented by an undirected multigraph. The traffic along the edges of the multigraph is carried out only at certain intervals - using ``subthreads''. We formulate a new mathematical model of traffic along the edges of the multigraph. A universal criterion of optimality for the scheduling problem is proposed. We propose an algorithm to find a suboptimal solution. A meaningful example is given.

Keywords

multigraph; cargo transportation; railway network; timetable; mixed integer linear programming.

References

1. Azanov V.M., Buyanov M.V., Gaynanov D.N., Ivanov S.V. Algorithm and Software Development to Allocate Locomotives for Transportation of Freight Trains. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2016, vol. 9, no. 4, pp. 73-85. DOI: 10.14529/mmp160407
2. Buyanov M.V., Kibzun A.I. Algorithm of Effective Transportation Work for Cargo Traffic. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2018, vol. 11, no. 1, pp. 75-83. DOI: 10.14529/mmp180107
3. Ziarati K., Soumis F., Desrosiers J., Gelinas S., Saintonge A. Locomotive Assignment with Heterogeneous Consists at CN North America. European Journal of Operational Research, 1997, no. 97, pp. 281-292. DOI: 10.1016/S0377-2217(96)00198-1
4. Ahuja R.K., Liu Jian, Orlin J., Sharma D., Shughart L. Solving Real-Life Locomotive-Scheduling Problems. Transportation Science, 2005, vol. 39, no. 4, pp. 503-517. DOI: 10.1287/trsc.1050.0115
5. Bosov A.V., Ignatov A.N., Naumov A.V. Model of Transportation of Trains and Shunting Locomotives at a Railway Station for Evaluation and Analysis of Side-Collsion Probability. Informatics and Applications, 2018, vol. 12, no. 3. pp. 107-114. DOI: 10.14357/19922264180315 (in Russian)
6. Cordeau J., Toth P., Vigo D. A Survey of Optimization Models for Train Routing and Scheduling. Transportation Science, 1998, vol. 32, no. 4, pp. 380-404. DOI: 10.1287/trsc.32.4.380
7. Caprara A., Fischetti M., Toth P. Modeling and Solving the Train Timetabling Problem. Operations Research, 2002, vol. 50, no. 5, pp. 851-861. DOI: 10.1287/opre.50.5.851.362
8. Kroon L., Maroti G., Helmrich M. Stochastic Improvement of Cyclic Railway Timetables. Transportation Research Part B: Methodological, 2008, vol. 42, no. 6, pp. 553-570. DOI: 10.1016/j.trb.2007.11.002
9. Lazarev A.A., Musatova E.G. The Problem of Trains Formation and Scheduling: Integer Statements. Automation and Remote Control, 2013, vol. 74, no. 12, pp. 2064-2068. DOI: 10.1134/S0005117913120084
10. Zinder Y., Lazarev A.A., Musatova E.G., Tarasov I. Scheduling the Two-Way Traffic on a Single-Track Railway with a Siding. Automation and Remote Control, 2018, vol. 79, no. 3, pp. 506-523. DOI: 10.1134/S0005117918030098
11. Zinder Y., Lazarev A.A., Musatova E.G. Rescheduling Traffic on a Partially Blocked Segment of Railway with a Siding. Automation and Remote Control, 2020, vol. 81, no. 6, pp. 955-966. DOI: 10.1134/S0005117920060016
12. Ignatov A.N., Naumov A.V. On Time Selection for Track Possession Assignment at the Railway Station. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2019, vol. 12, no. 3, pp. 5-16. DOI: 10.14529/mmp190301
13. Gainanov D.N., Ignatov A.N., Naumov A.V., Rasskazova V.A. On Track Procession Assignment Problem at the Railway Network Sections. Automation and Remote Control, 2020, vol. 81, no. 6, pp. 967-977. DOI: 10.1134/S0005117920060028
14. Buyanov M.V., Ivanov S.V., Kibzun A.I., Naumov A.V. Development of the Mathematical Model of Cargo Transportation Control on a Railway Network Segment Taking into Account Random Factors. Informatics and Applications, 2017, vol. 11, no. 4, pp. 85-93. DOI: 10.14357/19922264170411 (in Russian)
15. Ignatov A.N., Naumov A.V. On the Problem of Increasing the Railway Station Capacity. Automation and Remote Control, 2021, vol. 82, no. 1, pp. 102-114. DOI: 10.1134/S0005231019010074