Keyhani, Mohammad Hossein ; Schnee, Mathias ; Weihe, Karsten (2014)
Path Finding Strategies in Stochastic Networks.
Report, Erstveröffentlichung
Kurzbeschreibung (Abstract)
We introduce a novel generic algorithmic problem in directed acyclic graphs, motivated by our train delay research. Roughly speaking, an arc is admissible or not subject to the value of a random variable at its tail node. The core problem is to precompute data such that a walk along admissible arcs will lead to one of the target nodes with a high probability. In the motivating application scenario, this means to meet an appointment with a high chance even if train connections are broken due to train delays.
We present an efficient dynamic-programming algorithm for the generic case. The algorithm allows us to maximize the probability of success or, alternatively, optimize other criteria subject to a guaranteed probability of success.
Moreover, we customize this algorithm to the application scenario. For this scenario, we present computational results based on real data from the national German railway company. The results demonstrate that our approach is superior to the natural approach, that is, to find a fast and convenient connection and to identify alternative routes for all tight train changes where the probability that the change breaks due to delays is not negligible.
| Typ des Eintrags: | Report |
|---|---|
| Erschienen: | 2014 |
| Autor(en): | Keyhani, Mohammad Hossein ; Schnee, Mathias ; Weihe, Karsten |
| Art des Eintrags: | Erstveröffentlichung |
| Titel: | Path Finding Strategies in Stochastic Networks |
| Sprache: | Englisch |
| Publikationsjahr: | 10 Dezember 2014 |
| URL / URN: | http://tuprints.ulb.tu-darmstadt.de/4302 |
| Kurzbeschreibung (Abstract): | We introduce a novel generic algorithmic problem in directed acyclic graphs, motivated by our train delay research. Roughly speaking, an arc is admissible or not subject to the value of a random variable at its tail node. The core problem is to precompute data such that a walk along admissible arcs will lead to one of the target nodes with a high probability. In the motivating application scenario, this means to meet an appointment with a high chance even if train connections are broken due to train delays. We present an efficient dynamic-programming algorithm for the generic case. The algorithm allows us to maximize the probability of success or, alternatively, optimize other criteria subject to a guaranteed probability of success. Moreover, we customize this algorithm to the application scenario. For this scenario, we present computational results based on real data from the national German railway company. The results demonstrate that our approach is superior to the natural approach, that is, to find a fast and convenient connection and to identify alternative routes for all tight train changes where the probability that the change breaks due to delays is not negligible. |
| URN: | urn:nbn:de:tuda-tuprints-43029 |
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): | 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik > Algorithmik 20 Fachbereich Informatik |
| Hinterlegungsdatum: | 14 Dez 2014 20:55 |
| Letzte Änderung: | 14 Dez 2014 20:55 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum