Improvement of Decision Support System for Rail Depot Planning
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Publicerad
2013
Författare
Beygo, Berkay
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
The thesis is implementing an improvement for the depot planning decision support system at DSB S-tog (Danish State Railways S-train). In the literature, for the sake of tractability, rail depot planning (shunt planning) is divided into different sub-problems and each is solved independently. In the Jeppesen system we have divided the problem into following sub-problems: Composition and rotation steps, parking problem and driver scheduling. The parking problem which was proved to be NP-Hard was seen as the hardest step of the overall plan in some literature, and the focus of the thesis is on that problem. Given a timetable and the specifications of trains in the timetable, the problem focuses on parking the trains at shunt tracks which will be idle for a while and will operate later by considering the topology of the shunt yard and the demands of shunt planners. In the current system used at Jeppesen, the composition and rotation steps are solved quite efficiently for real life instances, and the parking problem is modeled as a Set Partitioning Problem in which all the feasible assignments for each track are generated explicitly. The current model then chooses at most one assignment for each shunt track. Since the number of feasible assignments grows exponentially in the number of trains, it is hard to solve the problem for some real life cases. In the thesis, by taking into consideration the requirements from DSB S-tog, a MIP model is developed that has polynomial number of variables in the number of trains and shunt tracks. All the shunt tracks at DSB are of type LIFO that allows the trains get in/out using a single end. Although the new model satisfies all the requirements of the customer, some extensions existing in the literature are not included in the system, and some extensions differ from the ones in literature. Compared to the current model being used, instead of generating all the feasible assignments for each track which leads to an exponential number of decision variables, all the requirements are modeled as constraints. The model is tested and applied to 6 depots at DSB S-tog. The results show that the new MIP model is superior for most of the small and medium instances. For the larger instances, which were hard to solve by the current system and sometimes could not be solved at all, the MIP model finds the optimal solutions in a reasonable amount of time.
Beskrivning
Ämne/nyckelord
Data- och informationsvetenskap , Computer and Information Science