One of the core issues for operators of passenger railways is providing sufficient number of seats for passengers while keeping operating costs at a minimum. The process a railway operator undertakes in order to achieve this is called rolling stock planning. Rolling stock planning deals with deciding how to utilise the fleet of available train units in space and time. In this thesis, rolling stock planning has been studied, using as case study DSB S-tog, the suburban passenger railway operator of the City of Copenhagen. At DSB S-tog, the rolling stock planning process is subdivided according to time horizon into two subprocesses. Firstly, there is the long-term circulation planning process, in which planning is conducted for anonymous, virtual train units months in advance. Secondly, there is the short-term train unit dispatching process, which covers the execution of the long term circulation plan. In the train unit dispatching process, the anonymous, virtual train units from the circulation planning process will have real, physical train units assigned to them. The train unit dispatching process has a short-term time horizon of days, hours and minutes and makes sure the actual, real-world train services are performed. Disruptions are also handled in this process. In the long term circulation planning phase of rolling stock planning, a large number of railway-specific requirements must be taken into account: The physical railway infrastructure must be adhered to, e.g., platform and depot track capacities, the rules of the train control system and the order in which train units may be parked so as not to obstruct each other’s movements; All trains services of the timetable must have a least one train unit assigned; Only the available rolling stock can be used in the plan; The plan should provide seating capacity according to the passenger demand and provide an even distribution of flexible space for bicycles etc.; Planned shunting operations in the depot should have sucient personnel on duty; Train units must undergo interior and exterior cleaning, surface foil application and winter preparedness treatment at regular time intervals; At regular service distance intervals, train units must undergo scheduled maintenance etc., and consumables must be refilled; Certain train services must have train units with additional train control system equipment installed, special passenger counting equipment installed and/or perform predefined exposure of commercials.In the short-term train unit dispatching phase of rolling stock planning, additional railwayspecific requirements include: Exterior graffiti removal and unscheduled maintenance on demand and sometimes within a given time frame; Make available train units to meet surveillance video recording requests from the police within a given time frame. Due to the large number of railway-specific requirements and their nature, rolling stock planning is traditionally conducted in a step-by-step manner, in which the individual planning processes are not integrated with each other. Needless to say, this yields rolling stock plans that are either suboptimal or infeasible with regard to the requirements. In this thesis it is shown that it is possible to design and implement a rolling stock planning model integrating into one planning process all the railway-specific requirements of DSB S-tog, all at the same time. This integrated rolling stock planning model is implemented using a greedy heuristic and makes use of the novel (train) unit order conservation principle, implemented as special side constraints to a resource constrained shortest path algorithm. The integrated rolling stock planning model is tested extensively on 15 real-world, manually constructed rolling stock plan data instances. When run on these instances, the greedy heuristic can achieve an average economic gain of approx. 2% with processing times in all cases less than 1 hour 20 minutes. In addition to this, the greedy heuristic can make typically infeasible rolling stock plans feasible within just a few minutes of processing time. Moreover, in this thesis a number of different economic net value upper bound calculation models are designed, implemented and tested. The net value upper bound calculation models implement the railway-specific requirements to a varying degree and consequently expose different properties with regard to tightness of bounds and processing times. The net value upper bound model having the highest degree of requirements integration adheres to 47% of the requirements by count. Using this tightest net value upper bound calculation model, it is shown that the greedy heuristic mentioned before is able to gain approx. 1/3 of the relative gap between the net value of the original, manual plans and the net value upper bound. Moreover, it is shown that in most cases, the net value of the original, manual plans already lie close to the upper bound.Furthermore, a branch-and-price based matheuristic integrated rolling stock planning model is designed, implemented and tested. It is shown that this type of matheuristic model is able to adhere fully to all railway-specific requirements, and that the vast majority of requirements can be integrated into the optimisation steps of the atheuristic algorithm. The branch-andprice matheuristic model can solve small instances (e. g., in the form of matheuristic iterations) to optimality. Used in conjunction with the greedy heuristic, the two methods combined can achieve an additional small gain in objective value not achievable using each method by itself. With a yearly cost of the rolling stock operation in the hundreds of million DKK, the potential benefit of a real-world application of the models to DSB S-tog is in the order of several million DKK per year. In addition to this, a substantial benefit can be gained by the way the models can automate the current, manual planning procedures. This will enable planners to invest more creativity and meticulousness into the planning process as a result of being liberated from manual planning procedures. For these reasons, DSB S-tog is eager to proceed with the real-world application of the models developed in this thesis.
展开▼
