Improvement of Decision Support System for Rail Depot Planning

Examensarbete för masterexamen

Please use this identifier to cite or link to this item:
Download file(s):
File Description SizeFormat 
173945.pdfFulltext2.15 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Improvement of Decision Support System for Rail Depot Planning
Authors: Beygo, Berkay
Abstract: 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.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2013
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
Collection:Examensarbeten för masterexamen // Master Theses

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.