Branch and Price for Bus Driver Scheduling with Complex Break Constraints
Authors: Lucas Kletzander, Nysret Musliu, Pascal Van Hentenryck11853-11861
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Evaluation on a publicly available set of benchmark instances shows that the approach provides the first provably optimal solutions for small instances, improving best-known solutions or proving them optimal for 48 out of 50 instances, and yielding an optimality gap of less than 1% for more than half the instances. |
| Researcher Affiliation | Academia | 1Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling DBAI, TU Wien, Karlsplatz 13, 1040 Vienna, Austria 2Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, USA |
| Pseudocode | No | The paper describes the algorithm steps in detail using text and equations, but it does not include any formal pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the methodology described. |
| Open Datasets | Yes | The method was evaluated on a publicly available set of benchmark instances (Kletzander and Musliu 2020). |
| Dataset Splits | No | The paper evaluates its approach on 'benchmark instances' but does not describe conventional training, validation, and test dataset splits (e.g., percentages or counts of samples for each split) as typically found in machine learning contexts. |
| Hardware Specification | Yes | The evaluation was performed on Windows 10 Professional using an Intel Core i7-6700K with 4x4.0 GHz and 32 GB RAM. |
| Software Dependencies | Yes | The implementation uses Java (Open JDK 14.0.1), the master problem is solved by CPLEX 12.10. |
| Experiment Setup | Yes | The runtime for the Branch and Price was limited to one hour and up to one more hour to finish the last ongoing computation. [...] It proposes a new throttling mechanism that imposes a maximum cost per arc, starting at 100 [...] this factor is multiplied by 2. [...] The pricing subproblem avoids searching more complex graphs, as long as those with less complexity still produce enough shifts with negative reduced costs (usually 10, 100 if the objective did not change, 1000 if the objective did not change repeatedly). |