Computing Multi-Modal Journey Plans under Uncertainty
Authors: Adi Botea, Akihiro Kishimoto, Evdokia Nikolova, Stefano Braghin, Michele Berlingerio, Elizabeth Daly
JAIR 2019 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We perform a detailed empirical analysis on realistic transport networks from cities such as Montpellier, Rome and Dublin. The results demonstrate the effectiveness of our algorithmic contributions, and the benefits of contingent plans as compared to standard sequential plans, when the arrival and departure times of buses are characterized by uncertainty. |
| Researcher Affiliation | Collaboration | Adi Botea EMAIL Akihiro Kishimoto EMAIL IBM Research Dublin, Ireland Evdokia Nikolova EMAIL The University of Texas at Austin Austin, TX, USA Stefano Braghin EMAIL Michele Berlingerio EMAIL Elizabeth Daly EMAIL IBM Research Dublin, Ireland |
| Pseudocode | Yes | Algorithm 1 Hybrid Deterministic Nondeterministic Search Algorithm 2 Update |
| Open Source Code | No | Our system, DIJA, is implemented in C++. It integrates ideas presented in this paper, including AO* search, the hybrid deterministic nondeterministic search approach, admissible heuristics for travel time and quotas, pruning techniques, and the cost metrics discussed earlier. It allows computing (contingent) journey plans and simulating their execution. No explicit statement about open-sourcing the code or a repository link is provided. |
| Open Datasets | No | We have used transportation data from three European cities, Montpellier, Dublin, and Rome. The original data is deterministic. This was extended with a stochastic noise assigned to the original deterministic arrival and departure times... We have set the mean arrival (departure) values to the scheduled arrival (departure) times available in the GTFS data for simplicity. While GTFS is a public format, the specific data for these cities, especially after modification, is not made explicitly available nor is a direct link or citation provided for access to the exact datasets used. |
| Dataset Splits | No | We used 1,000 journey plan requests (instances) for each city. The origins and the destinations are picked at random, and the departure time is 11AM. The paper does not specify any training/test/validation splits for these instances. |
| Hardware Specification | Yes | Tests are run on a Red Hat machine with an Intel Xeon CPU @ 3.47GHz. |
| Software Dependencies | No | Our system, DIJA, is implemented in C++. No specific versions of compilers, libraries, or other software dependencies are mentioned. |
| Experiment Setup | Yes | Quotas are set to at most 20 minutes of walking, and at most 5 segments per trip, unless explicitly mentioned otherwise. Tests are run on a Red Hat machine with an Intel Xeon CPU @ 3.47GHz. The original data is deterministic. This was extended with a stochastic noise assigned to the original deterministic arrival and departure times. The noise follows a Normal distribution, truncated to a confidence interval of 99.7%. We report results with two distinct levels of noise. The smaller level has σ2 = 1600 seconds, equal roughly to 2 minutes around the original deterministic arrival or departure times. In the larger noise level we set σ2 = 6400, which roughly corresponds to a 4-minute uncertainty interval. We have set the mean arrival (departure) values to the scheduled arrival (departure) times available in the GTFS data for simplicity. We used 1,000 journey plan requests (instances) for each city. The origins and the destinations are picked at random, and the departure time is 11AM. The optimality criterion is minimizing the worst-case travel time, with ties broken in favor of a better expected travel time. Based on the experiment presented here, cw = 0.005 arguably is a good trade-off between the travel time, the number of legs and the speed performance, which is why we have set this as the default value for the cw parameter. |