Research map / Learning theory and algorithms / Combinatorial and search optimization
Branch and Price for Bus Driver Scheduling with Complex Break Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Branch and Price to the bus-driver scheduling benchmarks | BDS · BDS benchmark sizes 10–90 | objective cost: 0.06 %; 1.63 %; 2.21 %; 3.09 %; 2.61 %; 3.74 %; 3.38 %; 3.72 %; 3.77 % | Helped |
| Apply Branch and Price rather than the previous method | BDS · BDS benchmark size 100 | objective cost: -0.18 % | Hurt |
| Split the pricing subproblem into cases for no, uncentered, and centered 30-minute breaks (ablation) | Branch and Price · BDS, instance 40 16 | runtime: 4 ms; 1.5 s; 1.9 s; 16 ms; 7.7 s; 51.1 s | Helped |
| Limit arc cost to 100 initially, then double the limit as needed (ablation) | Branch and Price pricing · BDS, instance 40 16 | runtime: 727 seconds | Helped |
| Use node-based throttling instead of arc-based throttling (ablation) | Branch and Price pricing · BDS, instance 40 16 | runtime: 1354 seconds vs 727 seconds | Hurt |
| Use cost-based throttling instead of arc-based throttling (ablation) | Branch and Price pricing · BDS | reduced master problem objective over time | Hurt |
| Use two-stage k-d tree and bounding-box dominance checks (ablation) | Branch and Price · BDS, instance 40 16 largest subproblem | runtime: 290 seconds -> 51 seconds | Helped |
| Use multi-dimensional divide-and-conquer dominance checks (ablation) | Branch and Price · BDS, instance 40 16 largest subproblem | runtime: 290 seconds -> 293 seconds | No clear effect |
| Use two-stage dominance rather than default dominance (ablation) | Branch and Price · BDS benchmark instances within the time limit | number of instances whose root node terminates: 25 -> 33 | Helped |
Closest papers by meaning
- Rolling Horizon Based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows (AAAI 2023 · similarity 0.81)
- A Complexity-theoretic Analysis of Green Pickup-and-Delivery Problems (AAAI 2021 · similarity 0.81)
- Efficient Constraint Generation for Stochastic Shortest Path Problems (AAAI 2024 · similarity 0.80)
- Differentiable Combinatorial Scheduling at Scale (ICML 2024 · similarity 0.79)
- Hybrid-Balance GFlowNet for Solving Vehicle Routing Problems (NeurIPS 2025 · similarity 0.78)
- Equity-Transformer: Solving NP-Hard Min-Max Routing Problems as Sequential Generation with Equity Context (AAAI 2024 · similarity 0.78)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.