Maximum independent set in planning freight railway transportation

Abstract

This work is devoted to the problem of planning of freight railway transportation. We define a special conflict graph on the basis of a set of acceptable train routes. The investigation aims to solve the classical combinatorial optimization problem in relation to the maximum independent set of vertices in undirected graphs. The level representation of the graph and its tree are introduced. With use of these constructions, the lower and upper bounds for the number of vertices in the maximum independent set are obtained.

Keywords

independent set / algorithm / planning of transportation / two-sided estimate

References

[1] Akimova E, Gainanov D, Golubev O (2015). The problem of scheduling for the linear section of a single-track railway with independent edges orientations. In: Proceedings of CEUR Workshop. 1513: 130–136

[2] Burdett O, Kozan E (2010). A disjunctive graph model and framework for constructing new train schedules. European Journal of Operational Research, 200(1): 85–98

[3] Dasgupta S, Papadimitriou C, Vazirani U (2006). Algorithms. New York: McGraw-Hill

[4] Duarte A, Pantrigo J, Pardo E, Mladenovic N (2015). Multi-objective variable neighborhood search: An application to combinatorial optimization problems. Journal of Global Optimization, 63(3): 515–536

[5] Gafarov E, Dolgui A, Lazarev A (2015). Two-station single-track railway scheduling problem with trains of equal speed. Computers & Industrial Engineering, 85: 260–267

[6] Gainanov D, Konygin A, Rasskazova V (2016). Modelling railway freight traffic using the methods of graph theory and combinatorial optimization. Automation and Remote Control, 77(11): 1928–1943

[7] Gainanov D, Rasskazova V (2016). An inference algorithm for monotone boolean functions associated with undirected graphs. Bulletin of the SUSU, 9(3): 17–30

[8] Gholami O, Sotskov Y N (2014). Scheduling algorithm with controllable train speeds and departure times to decrease the total train tardiness. Int Journal of Industrial Engenering Computations, 5(2): 281–294

[9] Gholami O, Sotskov Y N, Werner F (2012). Job-shop problems with objectives appropriate to train scheduling in a single-track railway. In: Proceedings of 2nd International Conference on Simulation and Modeling Methodologies, Roma. Technologies and Applications: 425–430

[10] Hansen P, Mladenovic N, Todosijevic R, Hanafi S (2017). Variable neighborhood search: basics and variants. European Journal on Computational Optimization, 5(3): 423–454

[11] Korte B, Vygen J (2008). Combinatorial Optimization. Berlin: Springer

[12] Lazarev A, Nekrasov I, Pravdivets N (2018). Evaluating typical algorithms of combinatorial optimization to solve continuous-time based scheduling problem. Algorithms, 4(11): 1–13

[13] Pei J, Cheng B, Liu X, Pardalos P M, Kong M (2017a). Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time. Annals of Operations Research, doi: 10.1007/s10479-017-2481-8

[14] Pei J, Liu X, Fan W, Pardalos P M, Lu S (2017b). A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega, doi: 10.1016/j.omega.2017.12.003

[15] Skiena S (2008). The Algorithm Design Manual. Berlin: Springer

[16] Todosijevic R, Mladenovic N (2016). Nested general variable neighborhood search for the periodic maintenance problem. European Journal of Operational Research, 252(2): 385–396

RIGHTS & PERMISSIONS

The Author(s) 2018. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)