Improvement of Decision Support System for Rail Depot Planning

Visa enkel post
dc.contributor.authorBeygo, Berkay
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.date.accessioned2019-07-03T13:07:32Z
dc.date.available2019-07-03T13:07:32Z
dc.date.issued2013
dc.description.abstractThe 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.
dc.identifier.urihttps://hdl.handle.net/20.500.12380/173945
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectData- och informationsvetenskap
dc.subjectComputer and Information Science
dc.titleImprovement of Decision Support System for Rail Depot Planning
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
173945.pdf
Storlek:
2.1 MB
Format:
Adobe Portable Document Format
Beskrivning:
Fulltext
Ladda ner
Samling
Examensarbeten för masterexamen