This paper is based on an award winning rail scheduling project. It studies a high-speed trainrouting problem where the trains are operated on a large network with sparse stations. Therelatively long distance between train stations makes it unlikely to get a backup train unit in timewhen an operating train is out of service due to the need for maintenance. Therefore, regularmaintenance is carefully incorporated into the base routing plan and is strictly enforced. In thispaper, an integrated path based routing model is proposed to design train routes and schedulingoptimally. The objective is to cover the published trains and timetable with the least cost withoutviolating operational rules and maintenance requirements. The scheduling for each operationalcycle needs to be completed in a timely manner and be implementable in practice. A heuristic isproposed to solve the problem in a column generation framework. Numerical tests are conductedwith operational data from French National Railroad Company (SNCF). The test not only showsa significant cost saving but also indicates its efficiency in real world applications.
展开▼