@misc{Mett2018, type = {Master Thesis}, author = {Mett, Fabian}, title = {{\"U}ber die optimale Platzierung von Ladestationen f{\"u}r Elektrobusse}, pages = {76}, year = {2018}, abstract = {In dieser Arbeit wird die Platzierung von Ladestationen f{\"u}r Elektrobusse untersucht. Dabei soll f{\"u}r eine Menge an gegebenen Linien eine Menge an Ladestationen gefunden werden, sodass jede Linie mit Nutzung der Ladestationen befahren werden kann und gleichzeitig die Kosten minimal sind. Zun{\"a}chst wird der Fall betrachtet, dass die Batterie an jeder Station komplett vollgeladen werden k{\"o}nnte. Dieses Problem stellt sich als NP-schwer heraus. F{\"u}r einige einfachere F{\"a}llewerden zudem Algorithmen entwickelt und untersucht. Anschließend wird der Fall einer unbegrenzt großen Batterie betrachtet, wobei an jeder Station derselbe Wert geladen werden kann. Auch dieses Problem ist NP-schwer. Erneut werden Algorithmen zur L{\"o}sung vereinfachter Problemstellungen gegeben und analysiert. Wird zudem angenommen, an jeder Station w{\"u}rde ein individueller Wert geladen, so ist das Problem schon f{\"u}r nur eine einzige Linie NP-schwer. Dennoch werden zwei exakte und ein approximierender Algorithmus entwickelt. Schließlich wird eine Batteriekapazit{\"a}t hinzugef{\"u}gt und die zuvor entwickelten Algorithmen werden entsprechend angepasst. F{\"u}r die abschließende Problemdefinition werden verschiedene Batteriegr{\"o}ßen betrachtet und es werden zwei gemischt-ganzzahlige Programme aufgestellt. Anhand von existierenden Buslinien aus Berlin werden diese untersucht. Dabei stellt sich heraus, dass die Batteriekosten einen deutlich gr{\"o}ßeren Teil der Kosten ausmachen als die Ladestationen. Zudem sollten kleinere Batterien statt gr{\"o}ßerer und mehr Ladestationen genutzt werden.}, language = {de} } @misc{Jeschke2017, type = {Master Thesis}, author = {Jeschke, Bj{\"o}rn-Marcel}, title = {Alternativen zum Dijkstra Algorithmus in der (Nah-) Verkehrsoptimierung}, pages = {74}, year = {2017}, abstract = {In dieser Arbeit betrachten wir das Problem, f{\"u}r den Fahrplan eines (Nah-) Verkehrsnetzes schnellste Wege zu berechnen. Da die Verkehrsmittel zu unterschiedlichen Zeiten von den einzelnen Haltestellen/Bahnh{\"o}fen abfahren, kann das Problem nicht ohne Weiteres mit einem „statischen" Graphen modelliert werden. Es gibt zwei unterschiedliche Ans{\"a}tze f{\"u}r dieses zeitabh{\"a}ngige Problem: Erstens k{\"o}nnen die verschiedenen An-/Abfahrtereignisse an einem Halt durch „Kopien" dargestellt werden, das ist das zeit-expandierte Modell. Zweitens k{\"o}nnen die Gewichte der Kanten zeitabh{\"a}ngig sein, das ist das zeitabh{\"a}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{\"a}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 {\"u}berlegen ist f{\"u}r gen{\"u}gend große Nahverkehrsnetze. Wir testen anhand der echten Verkehrsnetze von Berlin und Aachen. Unsere Berechnungen zeigen, dass die gew{\"a}hlte Heuristik besonders gut ist f{\"u}r Start- und Zielknoten, welche unabh{\"a}ngig von ihrer Distanz nur 1-2 verschiedene m{\"o}gliche k{\"u}rzeste Pfade f{\"u}r alle Zeitschritte haben. Dort ist der A* Algorithmus bis zu 20-mal schneller. Dies kommt aber nicht h{\"a}ufig in unseren Testinstanzen vor. Die einzelnen Laufzeitvergleich zeigen, dass der A* Algorithmus durchschnittlich 7-mal so schnell ist wie der Dikstra-Algorithmus.}, language = {de} }