Autoren: Matthias Müller-Hannemann und Mathias Schnee
Zusammenfassung: Im folgenden die sinngemäße Übersetzung des Abstract-Inhalts:
Bahnhofsuhr mit Zug (C) Pexels Dom.J
Wir betrachten effiziente Algorithmen für Fahrplanauskünfte im Öffentlichen Personenverkehr unter mehrfachen Präferenzen der Kunden, wie z.B. Fahrtzeit, Ticketpreis und Anzahl der Umstiege zwischen verschiedenen Verkehrsmitteln. Im vorliegenden Papier konzentrieren wir uns auf ein vollkommen realistisches Szenario im öffentlichen Bahnverkehr, wie wir es in der Praxis vorfinden, während frühere Arbeiten nur einfachere Modelle betrachteten. Aus algorithmischer Sicht führt dies zu Problemen der multikriteriellen "kürzesten Distanz" in sehr langen Graphen. Bei mehreren Zielen der Kunden besteht die Herausforderung darin, alle Verbindungen zu finden, die möglicherweise für den Kunden attraktiv sein könnten. Um dieses informelle Ziel zu erreichen, führen wir den Begriff der "gelockerten Pareto-Dominanz" ein. Eine weitere Schwierigkeit entsteht dadurch, dass durch die komplizierten Tarif-Regeln bereits das Ein-Kriterien-Problem der Optimierung des Fahrpreises fast unlösbar erscheint. Deshalb müssen wir bei der Suche nach guten Verbindungen mit Fahrpreisschätzungen arbeiten.
In Zusammenarbeit mit Deutsche Bahn Systems realisierten wir dieses Szenario in einer prototyphaften Umsetzung, die wir PARETO auf Basis eines zeit-erweiterten Graphenmodells nannten. Berechnungsexperimente mit unserem PARETO-Server demonstrieren, dass der derzeitige zentrale Server von Deutsche Bahn AG häufig nicht in der Lage ist, optimale Empfehlungen für verschiedene Nutzergruppen zu ermitteln. Im Unterschied dazu ist es eine Wichtige Eigenschaft eines PARETO-Servers, die Fähigkeit aufzuweisen, viele attraktive Alternativen anzubieten.
Den Artikel können Sie hier (nur in Englisch) herunterladen: Mueller-Hannemann, Schnee: Attraktive Zugverbindungen durch multikriterielle Pareto-Suche