Iterative Train Scheduling under Disruption with Maximum Satisfiability
Authors: Alexandre Lemos, Filipe Gouveia, Pedro T. Monteiro, Inês Lynce
JAIR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The performance of our approach is evaluated with the real-world Swiss Federal Railway (SBB) Crowd Sourcing Challenge benchmark and Periodic Event Scheduling Problems benchmark (PESPLib). The execution time of the proposed approach is shown to be, on average, twice as fast as the best existing solution for the SBB instances. In addition, we achieve a significant improvement over SAT-based solutions for solving the PESPLib instances. We also analyzed real schedule data from Switzerland and the Netherlands to create a disruption generator based on probability distributions. |
| Researcher Affiliation | Academia | Alexandre Lemos EMAIL Filipe Gouveia EMAIL Pedro T. Monteiro EMAIL Ines Lynce EMAIL Instituto Superior T ecnico, Universidade de Lisboa INESC-ID, Rua Alves Redol 9, 1000-029 Lisboa, Portugal |
| Pseudocode | Yes | Algorithm 1: core-guided Algorithm Input: An unsat core Output: A relaxed problem instance 1 for clause unsat do 2 update domain(clause) Algorithm 2; Algorithm 2: update domain Function Input: A clause Output: A set of nodes that may be affected by the domain change (nodes). 1 for st1 τ1,v1 clause do ... Algorithm 3: core-guided and propagation Algorithm Input: An unsat core Output: A relaxed problem instance 1 for unsat Clause unsat do 2 changed := update domain(unsat Clause) Get the nodes to be propagated from Algorithm 2; ... |
| Open Source Code | Yes | Our implementation is publicly available at https://github.com/ADDALemos/train-schedule-optimisation. |
| Open Datasets | Yes | The performance of our approach is evaluated with the real-world Swiss Federal Railway (SBB) Crowd Sourcing Challenge benchmark and Periodic Event Scheduling Problems benchmark (PESPLib). In order to evaluate the proposed approach to TSOP and TSOPu D, we considered the SBB benchmark (Abels et al., 2020b; Jordi et al., 2019). To further test our approach, we considered the PESPLib (Goerigk et al., 2013) benchmark. Our data sets and disruption scenarios were obtained from the SBB open data11. 11 The data was extracted from https://data.sbb.ch/pages/home/. (accessed November 2020) |
| Dataset Splits | No | The paper evaluates its approach on predefined benchmark instances (SBB and PESPLib) and generates additional "disrupted instances" for testing. However, it does not describe specific training, validation, or test dataset splits in the conventional sense (e.g., percentages or counts for machine learning model development and evaluation). The experiments involve solving optimization problems on given instances rather than training models on partitioned data. |
| Hardware Specification | Yes | The evaluations were performed on a computer with Fedora 14, with a 2.6 GHz CPU and 128 Gb of RAM. |
| Software Dependencies | Yes | The evaluations were performed on a computer with Fedora 14, with a 2.6 GHz CPU and 128 Gb of RAM. The best-performing solver shown in Table 4 and 5 is TT-Open-WBO-Inc-20 (Nadel, 2020a), which is also the winner of the incomplete weight track of the 2020 Max SAT competition. Note that we do not show the results for the RC2 (Ignatiev et al., 2019) solver. |
| Experiment Setup | Yes | During each iteration, we add 30 new entry time variables (30 seconds) to each node, the time constraints clauses are adjusted accordingly, and soft clauses representing the delay introduced with each new variable are added. This approach requires a low number of iterations, but we may have to deal with a large domain in each iteration since all entry time domains are increased. There are two stopping criteria in all the algorithms proposed in this paper: (i) timeout (no information about the optimality), and (ii) we found a global optimum. The proposed approach was executed considering a time limit of 900 seconds. |