Bus Driver Scheduling Problem

A benchmark suite for the Bus Driver Scheduling Problem (BDSP), a combinatorial optimization problem from public-transport planning. The collection bundles 284 generated instances modelling Austrian collective-agreement and EU driving-time regulations, together with best known solutions, a Python validator, and reproducible algorithm results.

284 instances across 12 source types · 9 proven optimal · 10 LNS variants · sizes from 8 tours (73 legs) to 981 tours (3129 legs).

• Browse the collection — filter, sort, and search all 284 instances; inspect best known solutions and per-algorithm results.
• Problem reference — formal definition, objective, key constraints, terminology, and instance file format.
• Validate a solution — upload a CSV solution and check feasibility and the objective breakdown in the browser.
• Submit an improved solution — open an issue with your solution CSV attached; it is auto-validated and, if better, published as the new BKS.
• Download the archive — full tarball of all 284 instance JSONs (also available individually from the collection page).
• Programmatic data access — stable JSON/CSV URLs for scripting: instance index, definitions, and best solutions.
• Validator on GitHub — standalone Python validator, the same logic as the in-browser version.
• Publications — JAIR 2025, ICAPS 2024, GECCO 2022, and PATAT 2024 — the papers behind the methods and data.

How to Cite

If you use these instances or solutions in your research, please cite the JAIR article that describes the integrated column-generation / LNS pipeline behind the best known solutions:

@article{kletzander2025jair,
  author  = {Kletzander, Lucas and Mannelli Mazzoli, Tommaso and Musliu, Nysret and Van Hentenryck, Pascal},
  title   = {Integrating Column Generation and Large Neighborhood Search
             for Bus Driver Scheduling with Complex Break Constraints},
  journal = {Journal of Artificial Intelligence Research},
  year    = {2025},
  doi     = {10.1613/jair.1.19027}
}

Contact

Improved solutions, bug reports, and questions are welcome at tommanmaz.math@gmail.com.