<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>7153</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>74</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>masterthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Alternativen zum Dijkstra Algorithmus in der (Nah-) Verkehrsoptimierung</title>
    <abstract language="deu">In dieser Arbeit betrachten wir das Problem, für den Fahrplan eines (Nah-) Verkehrsnetzes schnellste Wege zu berechnen. Da die Verkehrsmittel zu unterschiedlichen Zeiten von den einzelnen Haltestellen/Bahnhöfen abfahren, kann das Problem nicht ohne Weiteres mit einem „statischen“ Graphen modelliert werden. Es gibt zwei unterschiedliche Ansätze für dieses zeitabhängige Problem: Erstens können die verschiedenen An-/Abfahrtereignisse an einem Halt durch „Kopien“ dargestellt werden, das ist das zeit-expandierte Modell. Zweitens können die Gewichte der Kanten zeitabhängig sein, das ist&#13;
das zeitabhängige Modell. Wir untersuchen in dieser Arbeit, wie der „klassische“ Dijkstra-Algorithmus und der A* Algorithmus mit einer geeigneten Heuristik im Vergleich abschneiden. Die gewählte Heuristik ist der Abstand zum Zielknoten, wenn die Abfahrtszeiten ignoriert werden. Nach unseren Untersuchungen zeigt sich, dass der A* Algorithmus dem Dijkstra-Algorithmus weit überlegen ist für genügend große Nahverkehrsnetze. Wir testen anhand der echten Verkehrsnetze von Berlin und Aachen. Unsere Berechnungen zeigen, dass die gewählte Heuristik besonders gut ist für Start- und Zielknoten, welche unabhängig von ihrer Distanz nur 1–2 verschiedene mögliche kürzeste Pfade für alle Zeitschritte haben. Dort ist der A* Algorithmus bis zu 20-mal schneller. Dies kommt aber nicht häufig in unseren Testinstanzen vor. Die einzelnen Laufzeitvergleich zeigen, dass&#13;
der A* Algorithmus durchschnittlich 7-mal so schnell ist wie der Dikstra-Algorithmus.</abstract>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <advisor>Ralf Borndörfer</advisor>
    <author>Björn-Marcel Jeschke</author>
    <submitter>Ralf Borndörfer</submitter>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Freie Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>5181</id>
    <completedYear/>
    <publishedYear>2012</publishedYear>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>bachelorthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Spezielle Eigenschaften von Simulated Annealing</title>
    <advisor>Marcus Weber</advisor>
    <author>Björn-Marcel Jeschke</author>
    <submitter>Adam Nielsen</submitter>
    <collection role="institutes" number="num">Numerical Mathematics</collection>
    <collection role="institutes" number="compmol">Computational Molecular Design</collection>
    <collection role="projects" number="MIP_FORMATION">MIP_FORMATION</collection>
    <thesisGrantor>Freie Universität Berlin</thesisGrantor>
  </doc>
</export-example>
