Mathematical modelling of locomotives' traffic problem by graph theory and combinatorial optimization methods

Аuthors

Gainanov D. N.^*, Rasskazova V. A.^**

Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia

*e-mail: damir.gainanov@gmail.com
**e-mail: varvara.rasskazova@mail.ru

Abstract

The paper tackles the problem of railway cargo transportation planning and organizing. Oriented multi-graph of a train traffic energy efficient strategies and a set of this multi-graph permitted paths, i. e. a set of normative threads of a train schedule, are put under consideration. Non-oriented conflict graph is determined on the set of train schedule normative threads, associated with a monotonous Boolean function. The paper envisages the problem of creating a conflict-free set of train schedules, reduced to the monotonous Boolean function maximum upper zero search. The conflict-free schedule threads herein should ensure the specified volume of transportation. For this purpose, conditions of amount of traffic provision should be met, given by correspondence matrix. The transportation plan for the available set of locomotives is formed based on non-conflict set of the graph normative thread sets. A problem of locomotives’ assignment and movement is formulated for the transportation plan, which optimizes the number of completed transportation assignments, a number of used locomotives and a number of «empty runnings». The graph-combinatorial problem of subgraph nodes of oriented graph of transportations dependencies coverage by oriented paths. The above-mentioned criteria herein are formulated in terms of the determined coverage properties. The algorithmic diagram.

The main results of the research consist in mathematical formulation of the problem of optimal assignments of locomotives and its reducingtion to the dual graph-combinatorial problem, which solution structure is offered. The obtained results could find an application for solving practical problems on railway transportations optimization with regard to the required fleet of locomotives and its utilization ratio.

Keywords:

assignments of locomotives, algorithm, optimization

References

1. Malinina N.L. Trudy MAI, 2010, no.37: http://www.mai.ru/science/trudy/eng/published.php?ID=13440

2. Kobko L.I. Trudy MAI, 2001, no. 3: http://www.mai.ru/science/trudy/eng/published.php?ID=34687

3. Lazarev A.A. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki, 2009, vol. 49, no. 2, pp. 14–34.

4. Gafarov E.R., Lazarev A.A. Doklady akademii nauk, 2008, vol. 424, no. 2, pp. 7–9.

5. Burdett O., Kozan E. A Disjunctive Graph Model and Framework for Constructing New Train Schedules. Eur. J. Oper. Research, 2010, vol. 200, pp. 85–98.

6. Gholami O., Sotskov Y.N. Mixed Graph Model and Algorithms for Parallel‑Machine Job‑shop Scheduling Problems. Int. J. Production Research, 2015, vol. 8, pp. 1–16.

7. Lusby R., Ryan D. Railway Track Allocation: Models and Methods. Oper. Res. Spektrum, 2011, vol. 33, pp. 843–883.

8. Osipov S.I, Osipov S.S. Osnovy tyagi poezdov (Train traction fundamentials), Moscow, UMK MPS, 2000, 592 p.

9. Gainanov D.N. Kombinatornaya geometriya i grafy v analize nesovmestnykh sistem i raspoznavanii obrazov (Graphs for pattern recognition in feasible systems of linear inequalities), Moscow, Nauka, 2014, 152 p.

10. Gainanov D. N., Rasskazova V. A. An inference algorithm for monotone boolean functions associated with undirected graphs. Bulletin SUSU, 2016, vol. 9, no. 3, pp. 17–30.

Download