This paper considers a fast solving the practical problem in railway planning and scheduling. i.e., the problem of assigning given arrival and departure railway paths to routs. This problem is to execute as fully as possible the train traffic across the railway station, using a fixed amount of the resources. It appears that the problem may be solved by using any efficient maximum Independent set algorithm, which is known to be NP –hard. On the other hand, Simplicial vertex test is known heuristic that gives good quality solutions on sparse graphs. So, for solving the maximum independent set on sparse graphs, we propose an efficient heuristic based on the extended simplicial vertex test.