University of Twente Student Theses

Login

Optimale seinplaatsingen : een branch-and-bound algoritme voor de plaatsing van spoorwegseinen.

Feenstra, A. (2012) Optimale seinplaatsingen : een branch-and-bound algoritme voor de plaatsing van spoorwegseinen.

[img] PDF
934kB
Abstract:Het nederlandse spoorwegennetwerk is één van de drukste spoorwegnetwerken ter wereld. Het vinden van goede seinplaatsingen, om dit netwerk goed te benutten, is een lastige en tijdrovende taak. Software die goede seinplaatsingen genereert kan hierbij goed gebruikt worden. Het vinden van goede seinplaatsingen is echter een lastige taak. Dit nonlinear programming problem (NLP) is in een eerder onderzoek opgelost door een brute force methode.Uit de resultaten van dat onderzoek is gebleken dat rekentijden exponentieel hard opliepen. Om de rekentijden van een programma dat dit probleem oplost toch beperkt te houden is een Branch-&-Bound-algoritme geconstrueerd en gedeeltelijk geïmplementeerd. Daarbij worden subproblemen opgelost door middel van lineaire afschattingen. Hoewel de implementatie nog niet volledig compleet is, zijn de eerste testresultaten gunstig. In vergelijking tot de eerder geïmplementeerde brute force methode is deze implementatie sneller. Dit valt vooral toe te schrijven aan een efficiëntere implementatie van rijtijdberekeningen. De winst in rekentijd ten gevolge van het implementeren van een Branch-&-Bound-algoritme in plaats van een brute force methode zal nog moeten blijken. Het opnieuw implementeren van een solver voor dit probleem heeft zijn vruchten afgeworpen. Er is een snellere rijtijdberekentool en ook een aantal van de beperkingen in de vorige tool is verholpen. Het voordeel van het implementeren van een Branch-&-Bound-algoritme ten opzichte van een brute force methode is nog niet getest. Verwacht wordt dat hier significante winst mee wordt behaald en de rekentijd van de tool geen problemen meer oplevert voor de gebruiker.
Item Type:Essay (Master)
Clients:
Movares Nederland B.V., Nederland
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:55 traffic technology, transport technology
Programme:Electrical Engineering MSc (60353)
Link to this item:https://purl.utwente.nl/essays/62217
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page