Instance Collection
Last updated: …
284 BDSP instances across 12 source types. Sizes range from 8 tours (73 legs) to 981 tours (3129 legs). Lower bounds are computed using Branch-and-Price where available; rows highlighted in green with 0.0% gap are proven optimal. Click an instance name for the per-algorithm breakdown. For the formal definition, see the problem reference.
Download
The original real-world instances cannot be publicly shared due to agreements with bus companies. An instance generator was developed to create realistic instances following similar distributions.
| Source | Description |
|---|---|
| DBAI Repository | 50 real-world-like instances (realistic_10_1 to realistic_100_50) |
| Extended Collection | Additional 15 large instances (realistic_150_51 to realistic_250_65) |
| Solution Validator | Python tool to check feasibility and compute objective breakdown (web version) |
Data Access
Everything behind this collection is served as static files with stable URLs — plain JSON and CSV, no API key. Script against them directly:
| URL | Content |
|---|---|
/data/instances.json |
Index of all 284 instances: name, source, tours,
legs, stations, bks, lower_bound,
gap_pct, status, best_algorithm, per-algorithm results
(algorithms, old_algorithms), 59 instance features
(features), and a per-employee solution_breakdown for the
65 realistic instances. |
/downloads/instances/<name>.json |
Instance definition: legs — array of
{tour, start, end, startPos, endPos} with times in minutes, ordered by start
time — plus distances (position-indexed travel-time matrix) and
extra (per-position sign-on/sign-off times). |
/sols/<name>.csv |
Best archived solution matrix (65 realistic instances): header-less binary matrix, one row per employee, one column per leg in instance order. |
/downloads/collection.tar.gz |
Full instance archive. |
URLs are relative to https://tommanmaz.github.io. Example:
import json, urllib.request
BASE = "https://tommanmaz.github.io"
index = json.load(urllib.request.urlopen(f"{BASE}/data/instances.json"))
open_instances = [e["name"] for e in index if e["status"] == "open"]
inst = json.load(urllib.request.urlopen(f"{BASE}/downloads/instances/{open_instances[0]}.json"))
print(open_instances[0], len(inst["legs"]), "legs")
To validate solutions in bulk, use the
Python validator
(--mode folder) or load the web validator’s computation core directly in
Node.js: require('./js/bdsp_validator_core.js'). The JS core is tested for exact
numerical parity with the Python reference on every change.
Computational Setup
Hardware: Intel Xeon E5-2650 v4 @ 2.2 GHz
Time limit: 3600 seconds per instance for metaheuristics; Branch-and-Price ran until optimality or memory limit.
Software: Custom implementations in Python 3.10.14, executed with PyPy 7.3.17. Branch-and-Price was implemented in Java with OpenJDK 23.0.1, using Gurobi 12.0.0 for the master problem.
Instance Collection (284 instances)
Loading instance data…
Reporting New Best Solutions
Found a solution that beats a listed BKS? Open a submission issue and attach your solution CSV — a bot re-validates it within minutes and, if it is feasible and strictly better, publishes it here as the new BKS automatically, credited to your GitHub account. See the submission guide for the format. You can pre-check your file with the online validator, or email tommanmaz.math@gmail.com.