Bus Driver Scheduling Problem
Problem Definition
The Bus Driver Scheduling Problem (BDSP) is a complex combinatorial optimization problem in public transportation. Given predetermined bus tours, the goal is to create driver shifts that minimize total cost while satisfying operational constraints.
Download Instance Collection
The complete BDSP instance collection is available for download:
| File | Description | Size |
|---|---|---|
| collection.tar.gz | Complete collection of 285 BDSP instances | 80 MB |
Instance Sets
Real-world Instances (50 instances)
Instances range from 8 tours with 73 legs to 98 tours with 924 legs, derived from actual bus transportation networks. Lower bounds are computed using Branch-and-Price (BP).
The table shows the gap between best known solutions and lower bounds: \[\text{GAP} = \frac{\text{solution} - \text{bound}}{\text{bound}} \times 100\%\]
Rows highlighted in green with 0.00% gap represent proven optimal solutions.
| Instance | Tours | Legs | Best Solution | Lower Bound | Gap (%) | Algorithm |
|---|---|---|---|---|---|---|
| realistic_10_1 | 8 | 73 | 14417 | 14417.00 | 0.00 | BP |
| realistic_10_2 | 8 | 77 | 14572 | 14572.00 | 0.00 | BP |
| realistic_10_3 | 8 | 81 | 15103 | 15103.00 | 0.00 | BP |
| realistic_10_4 | 8 | 78 | 15148 | 15148.00 | 0.00 | BP |
| realistic_10_5 | 8 | 76 | 14306 | 14306.00 | 0.00 | BP |
| realistic_20_6 | 17 | 169 | 30427 | 30427.00 | 0.00 | BP |
| realistic_20_7 | 17 | 166 | 30610 | 30587.67 | 0.07 | BP |
| realistic_20_8 | 17 | 165 | 30437 | 30437.00 | 0.00 | BP |
| realistic_20_9 | 17 | 160 | 29520 | 29520.00 | 0.00 | BP |
| realistic_20_10 | 17 | 174 | 30480 | 30480.00 | 0.00 | BP |
| realistic_30_11 | 29 | 273 | 48731 | 48677.32 | 0.11 | BP |
| realistic_30_12 | 29 | 283 | 51115 | 50920.05 | 0.38 | BP |
| realistic_30_13 | 29 | 265 | 50962 | 50780.95 | 0.36 | BP |
| realistic_30_14 | 29 | 256 | 48802 | 48444.75 | 0.73 | BP |
| realistic_30_15 | 29 | 265 | 49622 | 49548.86 | 0.15 | BP |
| realistic_40_16 | 39 | 367 | 66417 | 66301.80 | 0.17 | BP |
| realistic_40_17 | 39 | 356 | 67695 | 67595.47 | 0.15 | BP |
| realistic_40_18 | 39 | 346 | 67424 | 67059.64 | 0.54 | BP |
| realistic_40_19 | 39 | 358 | 66478 | 66424.70 | 0.08 | BP |
| realistic_40_20 | 39 | 363 | 66923 | 66519.74 | 0.60 | LNS |
| realistic_50_21 | 50 | 437 | 83148 | 82618.88 | 0.64 | BP |
| realistic_50_22 | 50 | 457 | 84836 | 84575.75 | 0.31 | BP |
| realistic_50_23 | 50 | 456 | 83595 | 83414.95 | 0.22 | BP |
| realistic_50_24 | 50 | 447 | 85628 | 85326.67 | 0.35 | BP |
| realistic_50_25 | 50 | 458 | 84498 | 84274.42 | 0.26 | BP |
| realistic_60_26 | 58 | 517 | 99403 | 99289.61 | 0.11 | BP |
| realistic_60_27 | 58 | 534 | 101209 | 100368.75 | 0.83 | BP |
| realistic_60_28 | 58 | 546 | 99178 | 99004.73 | 0.17 | BP |
| realistic_60_29 | 58 | 528 | 99373 | 98991.82 | 0.38 | BP |
| realistic_60_30 | 58 | 549 | 99472 | 99015.22 | 0.46 | BP |
| realistic_70_31 | 70 | 629 | 116863 | 94569.16 | 19.08 | BP |
| realistic_70_32 | 70 | 652 | 118472 | 118305.82 | 0.14 | BP |
| realistic_70_33 | 70 | 643 | 119073 | 92676.61 | 22.17 | LNS |
| realistic_70_34 | 70 | 636 | 118983 | 117298.42 | 1.42 | BP |
| realistic_70_35 | 70 | 637 | 118406 | 117565.69 | 0.71 | LNS |
| realistic_80_36 | 79 | 764 | 133384 | 107444.68 | 19.45 | BP |
| realistic_80_37 | 79 | 739 | 134813 | 84899.52 | 37.02 | BP |
| realistic_80_38 | 79 | 741 | 135354 | 135133.51 | 0.16 | BP |
| realistic_80_39 | 79 | 713 | 135508 | 109028.34 | 19.54 | BP |
| realistic_80_40 | 79 | 732 | 133510 | 95989.84 | 28.10 | BP |
| realistic_90_41 | 88 | 810 | 149342 | 105743.38 | 29.19 | BP |
| realistic_90_42 | 88 | 841 | 149985 | 119680.32 | 20.21 | BP |
| realistic_90_43 | 88 | 826 | 151170 | 94474.61 | 37.50 | LNS |
| realistic_90_44 | 88 | 849 | 149956 | 82276.30 | 45.13 | BP |
| realistic_90_45 | 88 | 832 | 151325 | 122065.95 | 19.34 | BP |
| realistic_100_46 | 98 | 924 | 165821 | 80858.12 | 51.24 | LNS |
| realistic_100_47 | 98 | 860 | 165268 | 108262.39 | 34.49 | BP |
| realistic_100_48 | 98 | 906 | 167760 | 108025.40 | 35.61 | LNS |
| realistic_100_49 | 98 | 924 | 168925 | 117095.14 | 30.68 | LNS |
| realistic_100_50 | 98 | 876 | 165554 | 100052.18 | 39.57 | LNS |
Large Instances (15 instances)
Larger real-world instances with up to 250 tours and over 2300 legs. Solutions obtained using Large Neighborhood Search (LNS).
| Instance | Tours | Legs | Best Solution | Algorithm |
|---|---|---|---|---|
| realistic_150_51 | 148 | 1371 | 251712 | LNS |
| realistic_150_52 | 148 | 1403 | 257458 | LNS |
| realistic_150_53 | 148 | 1383 | 257146 | LNS |
| realistic_150_54 | 148 | 1375 | 256662 | LNS |
| realistic_150_55 | 148 | 1376 | 254608 | LNS |
| realistic_200_56 | 197 | 1806 | 339683 | LNS |
| realistic_200_57 | 197 | 1840 | 341608 | LNS |
| realistic_200_58 | 197 | 1820 | 336886 | LNS |
| realistic_200_59 | 197 | 1814 | 338072 | LNS |
| realistic_200_60 | 197 | 1892 | 336906 | LNS |
| realistic_250_61 | 250 | 2323 | 427739 | LNS |
| realistic_250_62 | 250 | 2329 | 429168 | LNS |
| realistic_250_63 | 250 | 2280 | 427930 | LNS |
| realistic_250_64 | 250 | 2313 | 429545 | LNS |
| realistic_250_65 | 250 | 2339 | 426803 | LNS |
References
- Kletzander, L., & Musliu, N. (2020). Solving large real-life bus driver scheduling problems with complex break constraints. ICAPS 2020. DOI
- Kletzander, L., Mazzoli, T. M., & Musliu, N. (2022). Metaheuristic algorithms for the bus driver scheduling problem with complex break constraints. GECCO 2022. DOI
- Mazzoli, T. M., Kletzander, L., Van Hentenryck, P., & Musliu, N. (2024). Investigating Large Neighbourhood Search for Bus Driver Scheduling. ICAPS 2024. DOI
- Mannelli Mazzoli, T., Kletzander, L., Musliu, N., & Smith-Miles, K. (2024). Instance Space Analysis for the Bus Driver Scheduling Problem. PATAT 2024. PDF