Algorithm and Software Development to Allocate Locomotives for Transportation of Freight Trains

We suggest a mathematical model to allocate locomotives for transportation of freight trains. The aim of the optimization in this model is to minimize the number of locomotives used for the transportation of the trains by choosing routes of the trains and locomotives. It is supposed that the trains can be transported only at defined time intervals (so-called train paths); every locomotive has possible routes called railway hauls. We take into account the necessity of periodic maintenance. We use graph theory and integer optimization to formulate the problem. We suggest mathematical definitions of a railway haul, a train path, a train route, and a locomotive route. An heuristic search algorithm to find an approximate solution of the problem is suggested. The main idea of the algorithm is maximal usage of locomotives that started earlier than other ones. The algorithm contains three stages. A solution of the previous stage is improved at each following stage. We use transfers of the locomotives to improve the current solution. We describe software development to optimize the model. We solve the problem using the historical data of Moscow railway.

Keywords

graph theory; integer optimization; allocation of locomotives.

References

1. Belyy O.V., Kokurin I.M. [Organization of Rail Freight: Ways Optimization]. Transport of the Russian Federation, 2011, no. 4 (35), pp. 28-30. (in Russian)
2. Kibzun A.I., Naumov A.V., Ivanov S.V. [Bilevel Optimization Problem for Railway Transport Hub Planning]. Large-Scale Systems Control, 2012, no. 38, pp. 140-160. (in Russian)
3. Lazarev A.A., Musatova E.G. The Problem of Trains Formation and Scheduling: Integer Statements. Automation and Remote Control, 2013, vol. 74, issue 12, pp. 2064-2068.
4. Lazarev A.A., Musatova E.G., Gafarov E.R., Kvaratskheliya A.G. Teoriya raspisaniy. Zadachi zheleznodorozhnogo planirovaniya [Sheduling. Problems of Rail Planning]. Moscow, Institute of Control Science of Russian Academy of Science, 2012. 91 p. (in Russian)
5. Tereshina N.P., Galaburda V.G., Trikhunkov et al. Ekonomika zheleznodorozhnogo transporta [Economics of Railway Transport]. Moscow, UMTs ZhDT, 2006. 801 p. (in Russian)
6. Shapkin I.N. Organizatsiya zheleznodorozhnykh perevozok na osnove informatsionnykh tekhnologiy [Organization of Rail Transport on the Basis of Information Technologies]. Moscow, UMTs ZhDT, 2011. 320 p. (in Russian)
7. Gainanov D.N., Ivanov S.V., Kibzun A.I., Osokin A.V. Model of Optimal Allocation Locomotives to Rail Freight. tIntellektual'nyye sistemy upravleniya na zheleznodorozhnov transporte-2015 [Intelligent control systems in railway transport-2015]. Moscow, NIIAS, 2015, pp. 45-47. (in Russian)
8. Floyd R.W. Algorithm 97 - Shortes Path. Communications of the ACM, 1962, vol. 5, no. 6, p. 345.