faculteit: "FNWI" en publicatiejaar: "2005"
| Auteur||V.S. Jaddoe|
|Titel||Selecting sets of disjoint paths in a railway graph|
|Faculteit||Faculteit der Natuurwetenschappen, Wiskunde en Informatica|
|Instituut/afd.||FNWI: Instituut voor Informatica|
|Opleiding||FNWI BSc Informatica|
|Samenvatting||A procedure to find an as large as possible set of disjoint paths in a graph at runtime can be useful to maintain railway traffic flow in a large station. This can be done by mapping trains to routes in such a way, that as much as possible trains can be simultaneously routed through the station. A railway infrastructure can be modelled as a graph where switches and crossings are taken into account.|
When switches and crossings are represented by vertices, pathfinding algorithms may return paths which are, due to the physical construction of switches and crossings, impossible. To solve this problem, the double vertex graph method has been chosen to model a railway infrastructure as a graph. Preprocessing has been used to optimise calculation speed at runtime. All possible paths between two
signals, and for each path, a maximum speed, priority and the set of conflicting paths are calculated in advance. The problem of finding a set of disjoint paths for a given set of trains that is as close as possible to an optimal set, has been formulated as the problem of finding the maximum independent set in a graph. To solve this problem, an independent set selection heuristic has been used in conjunction with an instance reduction algorithm. A discrete event simulator has been used to test both procedures and to simulate the train service, the actual state of the infrastructure and the mapping of trains to routes at an existing railway station with an existing schedule.
Using this simulator, it has been shown that the developed method is able to independently map a set of trains to a set of routes, which has been manually marked as the best set beforehand, within the time specified.
|Soort document|| scriptie bachelor|
Gebruik dit adres om naar deze pagina te linken: http://dare.uva.nl/scriptie/448007
Vraag/opmerking over dit recordMail aan een collega
Toevoegen aan bewaarset