Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck Abstract . The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimization problem with the goal to design shifts to cover prearranged bus tours. The objective takes into account the operational cost as well as the satisfaction of drivers. This problem is heavily constrained due to strict legal rules and collective agreements. The objective of this article is to provide state-of-the-art exact and hybrid solution methods that can provide high-quality solutions for instances of different sizes. This work presents a comprehensive study of both an exact method, Branch and Price (B&P) , as well as a Large Neighborhood Search (LNS) framework which uses B&P or Column Generation (CG) for the repair phase to solve the BDSP . It further proposes and evaluates a novel deeper integration of B&P and LNS , storing the generated columns from the LNS subproblems and reusing them for other subproblems, or to find better global solutions. The article presents a detailed analysis of several components of the solution methods and their impact, including general improvements for the B&P subproblem, which is a high-dimensional Resource Constrained Shortest Path Problem (RCSPP) , and the components of the LNS . The evaluation shows that our approach provides new state-of-the-art results for instances of all sizes, including exact solutions for small instances, and low gaps to a known lower bound for mid-sized instances. We observe that B&P provides the best results for small instances, while the tight integration of LNS and CG can provide high-quality solutions for larger instances, further improving over LNS which just uses CG as a black box. The proposed methods are general and can also be applied to other rule sets and related optimization problems. 1. Introduction Scheduling employees for public transport is an area that needs to respect a variety of complex constraints, time schedules, spatial requirements, and conflicting objectives, giving rise to difficult optimization problems. Drivers bear great responsibility for their passengers, leading to a range of legal requirements, collective agreements and company policies that demand particular break assignments and shift characteristics. Companies require cost-efficient schedules, while drivers and labor unions request employee-friendly schedules to reduce stress and increase compatibility of the required shift work with the private life of the drivers. This paper is a significantly extended version of our previous conference papers presented at AAAI [ KMVH21 ] and ICAPS [ MKVHM24 ] . It presents exact and hybrid methods for a complex Bus Driver Scheduling Problem (BDSP) . The constraints of the BDSP depend on the country’s legal regulation, and in our case, they follow the Austrian collective agreement for employees in private omnibus providers [ WKO19 ] using the rules for regional lines. In particular, the collective agreement has stringent rules requiring drivers to take frequent breaks, with the eventual option of splitting them into multiple parts, and the objectives in this article combine cost optimization with several employee satisfaction criteria, such as reducing long unpaid breaks or frequent vehicle changes. As an exact approach, we propose Branch and Price (B&P) . This method works on a branching tree, and performs Column Generation (CG) at each node, where the problem is split into Set Partitioning as the master problem and the Resource Constrained Shortest Path Problem (RCSPP) as the subproblem. However, due to the complex set of constraints, the labels used in solving the subproblem have a high number of dimensions, leading to a slow determination of non-dominated labels when solving the subproblem. Therefore, several options to improve the generation of new columns in the presence of a high number of dimensions are investigated, ultimately leading to the use of k-d trees and bounding boxes in a two-stage dominance algorithm. This approach was originally published in a conference paper at AAAI [ KMVH21 ] . Although B&P gives very good results for small- to medium-sized instances, exact methods are computationally too expensive for large instances, and heuristic methods cannot obtain optimal solutions. Therefore, the study of new methods to tackle larger instances is of particular interest. In this paper, we present a novel approach based on the Large Neighborhood Search (LNS) framework, which has been successfully used for solving other challenging real-life problems. However, applying this method to the BDSP requires innovative ideas for the destroy and repair operators, as well as a detailed investigation into their impact and the choice of parameters. In particular, B&P (or the CG part of B&P ) is used as the repair operator, as it provides high-quality solutions for small sub-problems very quickly. This approach was originally published in a conference paper at ICAPS [ MKVHM24 ] . However, it is possible to see B&P and LNS not only as separate components, but to enforce a tighter integration between the two. Therefore, this article is a substantial extension of the previous conference papers, investigating how to boost performance even further by allowing exchange between the different sub-problems of LNS , in particular, by storing columns from sub-problems for use in later, different sub-problems, and by using the combined set of columns that are aggregated from different sub-problems to find better solutions even more quickly. This leads to significant improvements in the results, establishing this hybrid as the new state-of-the-art method for this version of the BDSP . The main contributions of this paper are: • A Branch and Price (B&P) approach provides an exact solution method that can solve small instances optimally, and provide high-quality solutions for medium size. • Several improvements in solving the Resource Constrained Shortest Path Problem (RCSPP) in general are proposed and evaluated, which allow solving high-dimensional RCSPPs much faster. • A novel Large Neighborhood Search (LNS) is proposed method, including innovative destroy operators, using the CG part of our B&P as a repair. • A detailed analysis of the effect of the different destroy and repair components of LNS is provided. • We propose a novel tight integration of LNS and CG , where columns from each sub-problem are aggregated and reused to significantly improve the search. • A detailed evaluation is provided on the complex Austrian BDSP using a public benchmark instance set, where our approach clearly constitutes the new state of the art, outperforming previous results across all sizes of instances. While this evaluation is specific to this version of the problem, the ideas used in B&P and LNS and their integration are generally applicable for complex personnel scheduling problems. The remainder of this article is structured as follows. Section 2 provides related work to the problem and methods, Section 3 introduces the formal definition of the problem, Section 4 contains the details about Branch and Price , Section 5 explains the details about Large Neighborhood Search , Section 6 provides the tight integration of the two approaches, Section 7 contains the experiments for the different approaches and their detailed analysis, and finally Section 8 provides conclusions and an outlook to future work. 2. Related Work There are many versions of employee scheduling problems and several surveys [ EJKS04 , VdBBDB+13 ] provide a good overview of this line of work. Driver scheduling, as a part of crew scheduling, resides between vehicle scheduling and driver rostering in the process of operating bus transport systems [ IRDGMn15 ] . Research on bus driver scheduling problems has a long history [ WR95 ] and uses a variety of solution methods. Exact methods mostly use column generation with a set covering or set partitioning master problem and a resource constrained shortest path subproblem [ SW88 , DS89 , PLPa09 , LH16 ] . Heuristic methods like greedy [ MT86 , DLFM11 , TK13 ] or exhaustive [ CSSC13 ] search, tabu search [ LPaP01 , SK01 ] , genetic algorithms [ LPaP01 , LK03 ] , or iterated assignment problems [ CdMdA+17 ] are used in different variations. However, most work so far focuses mainly on cost, rarely minimizing idle time and vehicle changes [ IRDGMn15 , CdMdA+17 ] . Break constraints are mostly simple, often including just one meal break. Complex break scheduling within shifts has been considered by authors in different contexts [ BGM+08 , BGM+10 , WM14 ] . There is not much work on multi-objective bus driver scheduling [ LPaP01 ] , but multi-objective approaches are used in other bus operation problems [ RMVP13 ] . Recent work includes automated weight setting [ KM23a ] and decision support for human planners [ FMKM24 ] . This article investigates a complex real-life Bus Driver Scheduling Problem that was first introduced by [ KM20 ] . This work explains the need for a combined objective function that goes beyond cost. The published instances were solved with simulated annealing and a hill climbing heuristic. Good results have also been provided using tabu search [ KMM22 ] and hyper-heuristics [ KMM22 , KM23b ] , while the state-of-the-art heuristic solutions beside the methods in this article are achived using Construct, Solve, Merge, and Adapt [ RKB+23 ] . Branch and Price is a decomposition technique for large mixed integer programs [ BJN+98 ] , where a master problem works on a set of columns, while a sub-problem is responsible for generating new columns with negative reduced cost, i.e., the potential to improve the solution to the master problem. This work uses set partitioning [ BP76 ] as the master problem and the RCSPP [ ID05 ] as the subproblem. Resources are modeled via resource extension functions (REF) [ Irn08 ] . Different techniques for dealing with pareto-front calculation can mostly be found as maxima-finding algorithms in a geometrical context [ Ben80 , CHT12 ] . Large neighborhood search [ Sha98 ] is an iterative solution method, where in each iteration a part of the solution is destroyed and rebuilt by dedicated destroy and repair operators. 3. Problem Description The investigated Bus Driver Scheduling Problem (BDSP) deals with the assignment of bus drivers to vehicles that already have a predetermined route for one day of operation. The problem specification was introduced by [ KM20 ] . 3.1. Problem Input The input of the BDSP consists of three pieces of data: • Positions and Distance Matrix A finite set P\subseteq\mathbb{N} of positions . A time distance matrix D=(d_{pq})\in\mathbb{R}^{(P\times P)} where d_{pq} represents the time needed for an driver to go from position p to q when not actively driving a bus. If no transfer is possible, then we set d_{pq} to a big constant M . If p\neq q , then d_{pq} is called passive ride time , whereas d_{pq} represents the time it takes to switch tour at the same position, but is not considered passive ride time. • Start and End Work : For each position p\in P , two values \mathit{startWork}_{p} and \mathit{endWork}_{p} represent respectively the time required to start or end a shift at that position. • Bus Legs : A set L of bus legs , where each leg \ell\in L is a 5 -tuple: \ell=(\mathit{tour}_{\ell},\mathit{startPos}_{\ell},\mathit{endPos}_{\ell},\mathit{start}_{\ell},\mathit{end}_{\ell}), representing the trip of a vehicle between two stops at a certain time: – \mathit{tour}_{\ell} is the ID of the vehicle – \mathit{startPos}_{\ell},\mathit{endPos}_{\ell}\in P are respectively the starting and the ending positions of the leg – \mathit{start}_{\ell}\in\mathbb{R} is the time at which the vehicle departs from position \mathit{startPos}_{\ell} – \mathit{end}_{\ell}\in\mathbb{R} is the time at which the vehicle arrives to position \mathit{endPos}_{\ell} Legs with the same tour t do not overlap, which means that the intervals (\mathit{start}_{\ell},\mathit{end}_{\ell}) for \ell with \mathit{tour}_{\ell}=t are disjoint. Note that L is totally ordered by \mathit{start} , using \mathit{tour} as tie-breaker. Therefore, the following result holds. Lemma 1 . Let \preceq be the relation on L defined as follows: for any \ell_{1},\ell_{2}\in L , write \ell_{1}\preceq\ell_{2} if either • \mathit{start}_{\ell_{1}}<\mathit{start}_{\ell_{2}} , or • \mathit{start}_{\ell_{1}}=\mathit{start}_{\ell_{2}} and \mathit{tour}_{\ell_{1}}\leq\mathit{tour}_{\ell_{2}} Then \preceq is an order relation, and (L,\preceq) is a totally ordered set. Proof. We first note that in the dataset, each pair (\mathit{start}_{\ell},\mathit{tour}_{\ell}) uniquely identifies a bus leg. That is, if two legs share the same start time and tour index, they are the same element of L . • Reflexivity : For each \ell\in L we have \mathit{start}_{\ell}=\mathit{start}_{\ell} and \mathit{tour}_{\ell}=\mathit{tour}_{\ell} . So \ell\preceq\ell . • Antisymmetry Let \ell_{1},\ell_{2}\in L be such that \ell_{1}\preceq\ell_{2} and \ell_{2}\preceq\ell_{1} . This implies that \mathit{start}_{\ell_{1}}=\mathit{start}_{\ell_{2}} , \mathit{tour}_{\ell_{1}}\leq\mathit{tour}_{\ell_{2}} , and \mathit{tour}_{\ell_{2}}\leq\mathit{tour}_{\ell_{1}} . So \ell_{1}=\ell_{2} . • Transitivity Let \ell_{1},\ell_{2},\ell_{3}\in L be such that \ell_{1}\preceq\ell_{2} , and \ell_{2}\preceq\ell_{3} . Then there are four cases: (1) \mathit{start}_{\ell_{1}}<\mathit{start}_{\ell_{2}}<\mathit{start}_{\ell_{3}} . Then \mathit{start}_{\ell_{1}}<\mathit{start}_{\ell_{3}} and therefore \ell_{1}\preceq\ell_{3} . (2) \mathit{start}_{\ell_{1}}=\mathit{start}_{\ell_{2}}<\mathit{start}_{\ell_{3}} so \ell_{1}\preceq\ell_{3} . (3) \mathit{start}_{\ell_{1}}<\mathit{start}_{\ell_{2}}=\mathit{start}_{\ell_{3}} so \ell_{1}\preceq\ell_{3} . (4) \mathit{start}_{\ell_{1}}=\mathit{start}_{\ell_{2}}=\mathit{start}_{\ell_{3}} and \mathit{tour}_{\ell_{1}}\leq\mathit{tour}_{\ell_{2}}\leq\mathit{tour}_{\ell_{3}} . This implies \ell_{1}\preceq\ell_{3} . • Totally ordered : For any \ell_{1},\ell_{2}\in L , exactly one of the following holds: – \mathit{start}_{\ell_{1}}<\mathit{start}_{\ell_{2}} , – \mathit{start}_{\ell_{1}}>\mathit{start}_{\ell_{2}} , or – \mathit{start}_{\ell_{1}}=\mathit{start}_{\ell_{2}} In the first two cases, \ell_{1}\preceq\ell_{2} or \ell_{2}\preceq\ell_{1} follows directly. If \mathit{start}_{\ell_{1}}=\mathit{start}_{\ell_{2}} , then \mathit{tour}_{\ell_{1}}\leq\mathit{tour}_{\ell_{2}} or \mathit{tour}_{\ell_{1}}\geq\mathit{tour}_{\ell_{2}} . Thus, \ell_{1}\preceq\ell_{2} or \ell_{2}\preceq\ell_{1} . Hence, (L,\preceq) is totally ordered. ∎ \ell \mathit{tour}_{\ell} \mathit{start}_{\ell} \mathit{end}_{\ell} \mathit{startPos}_{\ell} \mathit{endPos}_{\ell} 1 1 400 495 0 1 2 1 510 555 1 2 3 1 560 502 2 1 4 1 508 540 1 0 Table 1 . A Bus Tour Example Table 1 shows a short example of one particular bus tour. The vehicle starts at time 400 (6:40 AM) at position 0 , does multiple legs between positions 1 and 2 with waiting times in between and finally returns to position 0 . A valid tour never has overlapping bus legs and consecutive bus legs satisfy \mathit{endPos}_{i}=\mathit{startPos}_{i+1} . A tour change occurs when a driver has an assignment of two consecutive bus legs i and j with \mathit{tour}_{i}\neq\mathit{tour}_{j} . 3.2. Solution A solution S to the BDSP is an assignment of drivers to bus legs. Formally, it is represented as a set partition of L , expressed as S=\{s_{1},s_{2},\dots,s_{n}\} . Each block s_{i} , is called a shift . In practical terms, a shift corresponds to the work scheduled to be performed by a driver in one day [ Wre04 ] . For a given shifts s , we denote L_{s}\subseteq L as the subset of bus legs assigned to s . While s and L_{s} are mathematically equivalent, we conceptually distinguish them: L_{s} represents only a set of bus legs, whereas s also contains additional details such as breaks, passive ride time, etc…. Those additional information are uniquely determined by the set of legs L_{s} , this means that, if necessary, the reader can think about s and L_{s} interchangeably. From Lemma 1 , it follows that the notion of consecutive bus legs in a shift is well-defined. Note that a priori, the number of shifts of a solution \left\lvert S\right\rvert is not given. Nevertheless, we can imagine to set it as large as we need in order to get a feasible solution. An immediate upper bound is \left\lvert S\right\rvert\leq\left\lvert L\right\rvert . This represents the situation in which each shift is composed by only one leg. Each shift s\in S must be feasible according to the following criteria: • No overlapping bus legs are assigned to s . • Changing tour or position between consecutive legs i,j\in s requires \mathit{start}_{j}\geq\mathit{end}_{i}+d_{\mathit{endPos}_{i},\mathit{startPos}_{j}}. • The shift s respects all hard constraints regarding work regulations as specified in the next section. 3.3. Work and Break Regulations start work \ell_{1} rest \ell_{2} rest passive ride \ell_{3} end work Working time W_{s} ? ? Driving time D_{s} Total time T_{s} Figure 1 . Example shift [ KM20 ] Valid shifts for drivers are constrained by work regulations and require frequent breaks. First, different measures of time related to an employee e containing the set of bus legs L_{s} need to be distinguished, as visualised in Figure 1 : • The total amount of driving time: D_{s}=\sum_{i\in L_{s}}{\mathit{drive}_{i}} . • The span from the start of work until the end of work T_{s} with a maximum of T_{\text{max}}=$14\text{\,}\mathrm{h}$ . • The working time W_{s}=T_{s}-\mathit{unpaid}_{s} , which does not include certain unpaid breaks. 3.3.1. Driving Time Regulations. The maximum driving time is restricted to D_{\text{max}}=$9\text{\,}\mathrm{h}$ . The whole distance \mathit{start}_{j}-\mathit{end}_{i} between consecutive bus legs i and j qualifies as a driving break, including passive ride time. Breaks from driving need to be taken repeatedly after at most 4\text{\,}\mathrm{h} of driving time. In case a break is split in several parts, all parts must occur before a driving block exceeds the 4\text{\,}\mathrm{h} limit. Once the required amount of break time is reached, a new driving block starts. The following options are possible: • One break of at least 30\text{\,}\mathrm{min} ; • Two breaks of at least 20\text{\,}\mathrm{min} each; • Three breaks of at least 15\text{\,}\mathrm{min} each. 3.3.2. Working Time Regulations. The working time W_{s} cannot exceed 10\text{\,}\mathrm{h} and has a soft minimum of 6.5\text{\,}\mathrm{h} . If the employee is working for a shorter period of time, the difference has to be paid anyway. A minimum rest break is required according to the following options: • W_{s}<$6\text{\,}\mathrm{h}$ : no rest break; • $6\text{\,}\mathrm{h}$\leq W_{s}\leq$9\text{\,}\mathrm{h}$ : at least 30\text{\,}\mathrm{min} ; • W_{s}>$9\text{\,}\mathrm{h}$ : at least 45\text{\,}\mathrm{min} . unpaid rest 2\text{\,}\mathrm{h} 2\text{\,}\mathrm{h} 3\text{\,}\mathrm{h} 3\text{\,}\mathrm{h} paid rest paid rest centred 30\text{\,}\mathrm{min} break Figure 2 . Rest break positioning [ KM20 ] The rest break may be split into one part of at least 30\text{\,}\mathrm{min} and one or more parts of at least 15\text{\,}\mathrm{min} . The first part has to occur after at most 6\text{\,}\mathrm{h} of working time. Whether rest breaks are paid or unpaid depends on break positions according to Figure 2 . Every period of at least 15\text{\,}\mathrm{min} of consecutive rest break is unpaid as long as it does not intersect the first 2 or the last 2 hours of the shift (a longer rest break might be partially paid and partially unpaid). The maximum amount of unpaid rest is limited: • If 30 consecutive minutes of rest break are located such that they do not intersect the first 3\text{\,}\mathrm{h} of the shift or the last 3\text{\,}\mathrm{h} of the shift, at most 1.5\text{\,}\mathrm{h} of unpaid rest are allowed; • Otherwise, at most one hour of unpaid rest is allowed. 3.3.3. Shift split If a rest break is at least 3\text{\,}\mathrm{h} long, it is instead considered a shift split, which is unpaid and does not count towards W_{s} . However, such splits are typically poorly regarded by the drivers. A shift split counts as a driving break, but does not contribute to rest breaks. 3.4. Objective Function We minimize the objective function combining cost and employee satisfaction defined in previous work [ KM20 ] : (1) z(S)=\sum_{s\in S}\left(2\,W_{s}^{\prime}+T_{s}+\mathit{ride}_{s}+30\,\mathit{change}_{s}+180\,\mathit{split}_{s}\right) The objective function z represents a linear combination of six criteria for each employee e . The actual paid working time W_{s}^{\prime}=\max\{W_{s},390\} is the main objective, and it is combined with the total time T_{s} to reduce long unpaid periods for employees. The next sub-objectives reduce the passive ride time \mathit{ride}_{s} and the number of tours changes \mathit{change}_{s} , which is beneficial for both employees and efficient schedules. The last objective aims to reduce the number of split shifts \mathit{split}_{s} as they are very unpopular. The weights were determined by previous work [ KM20 ] based on preferences agreed by different stakeholders at Austrian bus companies and employee scheduling experts. 4. Branch and Price Input: Problem instance Output: Best solution (optimal if no timeout occurs) 1 columns\leftarrow initialize columns; 2 best\leftarrow\infty ; 3 nodes\leftarrow\{\mathrm{root}\} ; 4 while nodes is not empty and no timeout do 5 node,columns\leftarrow\mathrm{choose}(nodes,columns) ; 6 if node_{lb}\geq best then 7 continue ; 8 end if 9 while no timeout do 10 rmp,~duals\leftarrow solve relaxed master problem( columns ); 11 new\_columns\leftarrow solve subproblem( duals ); 12 if new_columns is empty then 13 break ; 14 end if 15 columns\leftarrow columns\cup new\_columns ; 16 end while 17 if timeout then 18 if best=\infty then 19 best\leftarrow solve integer master problem( columns ); 20 end if 21 return best ; 22 end if 23 if rmp is integer then 24 best\leftarrow\min(rmp,best) ; 25 else 26 best\leftarrow\min(\text{solve integer master problem}(columns),best) ; 27 nodes\leftarrow nodes\cup{} branch( rmp ); 28 end if 29 end while 30 return best ; Algorithm 1 Branch and Price An exact solution to the BDSP can be computed by Branch and Price (B&P) [ BJN+98 ] . The general procedure is shown in Algorithm 1 . The outer loop (lines 4 to 29) iterates over the nodes in the branching tree. The inner loop (lines 9 to 16) performs Column Generation (CG) for each node. Set Partitioning is used as the master problem (line 10) and the Resource Constrained Shortest Path Problem (RCSPP) as the subproblem (line 11). The duals of the relaxed master problem are used to find new shifts that have the potential to improve the solution of the master problem. This is repeated until no columns with potential for improvement are found (lines 12 to 14). Branching occurs when the resulting solution is not integer (line 27). The process continues until all branches either result in integer solutions (lines 23 to 24) or are cut off by the current objective bounds (lines 6 to 8). 4.1. Master Problem The goal of the master problem is to select a subset of the shift set \mathbf{S} , such that each bus leg is covered by exactly one shift while minimizing total cost. This corresponds to the set partitioning problem: (2) minimize \displaystyle\sum_{s\in\mathbf{S}}{\mathit{cost}_{s}\cdot x_{s}} (3) subject to \displaystyle\sum_{s\in\mathbf{S}}{\mathit{cover}_{s\ell}\cdot x_{s}}=1 \displaystyle\forall\ell (4) \displaystyle x_{s}\in\{0,1\} \displaystyle\forall s Here x_{s} is the variable for the selection of shift s . The objective ( 2 ) minimizes the total cost, Equation ( 3 ) states that each bus leg needs to be covered exactly once (using \mathit{cover}_{s\ell}\in\{0,1\} to indicate whether shift s covers leg \ell ), and Equation ( 4 ) states the integrality constraint. This constraint is relaxed to 0\leq x_{s}\leq 1 for the relaxed master problem which is repeatedly solved at each node of the branching tree (line 10 in Algorithm 1 ). Instead of the full set of possible shifts \mathbf{S} , a subset columns is maintained by the algorithm. Once no more new shifts can be found by the subproblem, the result of the relaxed master problem provides a local lower bound for the solution of the integer problem. In some cases, the resulting solution might already be integer (line 23). Usually, however, the result will be fractional. Then, the integer version of the master problem is solved with the current set of columns (line 26). While there are no guarantees regarding the quality of the integer solution in this case, in practice, solutions are often very close to the lower bound already. In any case, the result from the integer master problem is a feasible solution that provides a global upper bound for the problem. If the solution is not integer, branching will be done, resuming calculation on one of the open branches. 4.2. Subproblem The goal of the subproblem (line 11 in Algorithm 1 ) is to find the column (shift) with the lowest reduced cost. For the BDSP this corresponds to the Resource Constrained Shortest Path Problem (RCSPP) on an acyclic graph. In this problem, a graph G=(\mathbf{N},\mathbf{A}) is given where \mathbf{N} is the set of n nodes, corresponding to all bus legs, a source node s , and a target node t , and \mathbf{A} is the set of arcs, which connect bus legs that can be scheduled consecutively in the same shift. As the bus legs are naturally ordered by time, the RCSPP is acyclic. Each node and arc is associated with a cost and an r -dimensional resource vector representing the resource consumption when using the node or arc. A shift is defined as a path from s to t such that the path satisfies all feasibility criteria associated with the resources. Each node corresponding to a bus leg is associated with a dual from the master problem. The reduced cost of a path is therefore the cost of a path minus the sum of the duals along the path. The RCSPP aims at finding the least-cost feasible path from s to t . There is an arc from node s to each node i except i=t , and there is an arc from each node i except i=s to node t . Nodes corresponding to bus legs i and j are only connected by an arc ij if chaining the bus legs is feasible according to their times and the distance matrix d . Building the graph is done once per instance in O(n^{2}) . Figure 3 shows such a graph for a small toy instance, skipping most arcs from s and to t for visual clarity. The remainder of this section goes into the details of this graph, its costs, and its constraints. Due to the complex regulations, solving this sub-problem is very challenging and requires several novel optimizations. s 0 63 1 111 2 111 3 90 4 87 5 144 6 105 7 84 8 60 9 105 t 45 78 45 45 57 394 18 72 78 255 42 489 296 72 30 30 30 Figure 3 . RCSPP graph for a Toy Instance 4.2.1. Costs The costs for nodes and arcs are based on objective ( 1 ). The cost c_{i} for each node i corresponding to a bus leg i is defined as c_{i}=3\cdot\mathit{length}_{i} as each bus leg contributes its length to both W_{s} (weight 2) and T_{s} (weight 1). By definition, c_{s}=c_{t}=0 . Several helpful properties of arcs from node i to node j are defined and used for defining the arc costs: (5) \displaystyle\mathit{length}_{ij} \displaystyle=\begin{cases}\mathit{start}_{j}-\mathit{end}_{i}&\text{if }i\neq s\land j\neq t\\ \mathit{startWork}_{\mathit{startPos}_{j}}&\text{if }i=s\\ \mathit{endWork}_{\mathit{endPos}_{i}}&\text{if }j=t\end{cases} (6) \displaystyle\mathit{ride}_{ij} \displaystyle=\begin{cases}d_{\mathit{endPos}_{i},\mathit{startPos}_{j}}&\text{if }i\neq s\land j\neq t\land\mathit{endPos}_{i}\neq\mathit{startPos}_{j}\\ 0&\text{otherwise}\end{cases} (7) \displaystyle\mathit{change}_{ij} \displaystyle=\begin{cases}1&\text{if }i\neq s\land j\neq t\land\mathit{tour}_{i}\neq\mathit{tour}_{j}\\ 0&\text{otherwise}\end{cases} (8) \displaystyle\mathit{split}_{ij} \displaystyle=\begin{cases}1&\text{if }i\neq s\land j\neq t\land\mathit{length}_{ij}-\mathit{ride}_{ij}\geq 3\cdot 60\\ 0&\text{otherwise}\end{cases} (9) \displaystyle\mathit{remain}_{ij} \displaystyle=\begin{cases}\mathit{length}_{ij}-\mathit{ride}_{ij}&\text{if }\mathit{split}_{ij}=0\\ 0&\text{otherwise}\end{cases} (10) \displaystyle\mathit{rest}_{ij} \displaystyle=\begin{cases}\mathit{remain}_{ij}&\text{if }i\neq s\land j\neq t\land\mathit{remain}_{ij}\geq 15\\ 0&\text{otherwise}\end{cases} Equation ( 5 ) defines the length of an arc, taking into account start and end arcs. Equation ( 6 ) states the passive ride time, Equation ( 7 ) whether a tour change occurs, Equation ( 8 ) whether the arc corresponds to a shift split, Equation ( 9 ) captures the remaining arc length after removing the passive ride time and the shift split time, and Equation ( 10 ) captures a potential rest break. The cost c_{ij} for arc ij (i.e., bus leg i to j ) is defined as (11) c_{ij}=2\cdot\mathit{remain}_{ij}+\mathit{length}_{ij}+3\cdot\mathit{ride}_{ij}+30\cdot\mathit{change}_{ij}+180\cdot\mathit{split}_{ij} Note that unpaid rest cannot be determined at this point, therefore all rest is treated as paid for this computation. Unpaid rest is separately treated when solving the subproblem. \mathit{ride}_{ij} contributes to both working time W_{s} and the additional passive ride penalty. 4.2.2. Resources The solution method is a label-setting algorithm [ ID05 ] . Due to the acyclic nature of the graph, each node can be processed in temporal order, starting with an initial label representing an empty path at s where each resource usage is 0. For each node i and each label x on that node, all arcs ij are processed and a label y is placed at the end node j of the arc unless some constraints are violated. Therefore, each label x represents a path from s to its node i , capturing the nodes in the path, the cost, and the resource usage. In total, eleven resources need to be tracked in order to satisfy the BDS constraints. The first resources are classical additive resources with a maximum allowed usage. (12) \displaystyle d_{y} \displaystyle=d_{x}+\mathit{drive}_{j} (13) \displaystyle s_{y} \displaystyle=s_{x}+\mathit{length}_{ij}+\mathit{length}_{j} Equation ( 12 ) tracks driving time, Equation ( 13 ) the span. (14) \displaystyle\mathit{rd}_{y} \displaystyle=\begin{cases}\mathit{true}&\text{if }\mathit{length}_{ij}\geq 30\lor(\mathit{length}_{ij}\geq 20\land\mathit{b20}_{x}\geq 1)\lor(\mathit{length}_{ij}\geq 15\land\mathit{b15}_{x}\geq 2)\\ \mathit{false}&\text{otherwise}\end{cases} (15) \displaystyle\mathit{dc}_{y} \displaystyle=\begin{cases}0&\text{if }\mathit{rd}_{y}\\ \mathit{dc}_{x}+\mathit{drive}_{j}&\text{otherwise}\end{cases} (16) \displaystyle\mathit{b15}_{y} \displaystyle=\begin{cases}0&\text{if }\mathit{rd}_{y}\\ \mathit{b15}_{x}+1&\text{if }\neg\mathit{rd}_{y}\land\mathit{length}_{ij}\geq 15\\ \mathit{b15}_{x}&\text{otherwise}\end{cases} (17) \displaystyle\mathit{b20}_{y} \displaystyle=\begin{cases}0&\text{if }\mathit{rd}_{y}\\ \mathit{b20}_{x}+1&\text{if }\neg\mathit{rd}_{y}\land\mathit{length}_{ij}\geq 20\\ \mathit{b20}_{x}&\text{otherwise}\end{cases} Resources for monitoring drive breaks need to be reset at each full drive break. Equation ( 14 ) defines a helping flag to indicate whether the current drive block is finished. Equation ( 15 ) uses this flag to reset or increase the current driving time. Equation ( 16 ) tracks the number of 15-minute breaks in the current driving block and Equation ( 17 ) the number of 20-minute breaks. 30-minute breaks do not need to be tracked as each of them resets the driving block. Constraints regarding rest breaks need to consider different sums of rest breaks and their positioning. (18) \displaystyle w_{y} \displaystyle=w_{x}+u_{x}-u_{y}+\mathit{remain}_{ij}+\mathit{ride}_{ij}+\mathit{length}_{j} (19) \displaystyle r_{y} \displaystyle=\min(r_{x}+\mathit{rest}_{ij},~45) (20) \displaystyle\mathit{b30}_{y} \displaystyle=\mathit{b30}_{x}\lor\mathit{rest}_{ij}\geq 30 (21) \displaystyle\mathit{rest}_{ij}^{\prime} \displaystyle=\mathit{rest}_{ij}-\max(2\cdot 60-s_{x},~0)-\max(\mathit{end}_{i}+\mathit{rest}_{ij}-(\mathit{end}_{y}-2\cdot 60),~0) (22) \displaystyle u_{y} \displaystyle=\min\left(u_{x}+\begin{cases}\mathit{rest}_{ij}^{\prime}&\text{if }\mathit{rest}_{ij}^{\prime}\geq 15\\ 0&\text{otherwise}\end{cases},~90\right) (23) \displaystyle\mathit{bc30}_{y} \displaystyle=\mathit{bc30}_{x}\lor\mathit{rest}_{ij}^{\prime\prime}\geq 30 Equation ( 18 ) tracks working time, assuming that all of u_{y} is unpaid so far, which constitutes a lower bound for the actual value. Equation ( 19 ) tracks the amount of required rest time, capping it at 45 as higher values do not matter. Equation ( 20 ) deals with the occurrence of a 30-minute rest break. s 0 1 2 3 t (a) Original graph s 0_{0} 0 1 2_{3} 3_{3} 2_{2} 0_{1} 1_{1} t (b) Extended graph Figure 4 . Extension of RCSPP graph to deal with distance to shift end Equation ( 21 ) captures the part of the rest break that can be unpaid depending on the position. However, this requires knowing the end time of the shift \mathit{end}_{y} which violates the general assumption of the algorithm that nodes can be processed in temporary order. Therefore, for each node j , with known end time \mathit{end}_{j} if j is the last bus leg in the shift, new nodes are added to the graph: \mathbf{N}_{j} is the set of nodes reachable within 3 hours from \mathit{end}_{j} when traversing the network backwards from j (including j itself). For each node i\in\mathbf{N}_{j} a new node i_{j} is created. For each pair of nodes i and k both in \mathbf{N}_{j} , an arc i_{j}k_{j} is added if ik is in the original graph. For i\not\in\mathbf{N}_{j} and k\in\mathbf{N}_{j} , an arc ik_{j} is added if ik is in the original graph. The arc j_{j}t replaces the arc jt . Each new node is associated with the end time \mathit{end}_{j} . All original nodes have end time \mathit{\infty} . This solves the problem, but increases the graph size by a factor of 6 for small instances up to more than 30 for large instances. Figure 4 shows this extension on a very small graph, assuming that only node n-1 is in the 3 hour window ending at the end of node n . The extended graph contains sub-networks for each final node, e.g., at node s going to node 0_{1} locks into a path ending with node 1_{1} , while going to 0 keeps the choice open to end via 2_{2} or 3_{3} , but not directly via 0_{0} or 1_{1} any more. The potential total amount of unpaid rest is captured in Equation ( 22 ). Equation ( 23 ) tracks the existence of a centered 30-minute break using \mathit{rest}_{ij}^{\prime\prime} defined like in ( 21 ) except with 3\cdot 60 instead of 2\cdot 60 . Finally, the cost needs to be computed. (24) \displaystyle\mathit{cost}_{y}^{\prime} \displaystyle=\mathit{cost}_{x}^{\prime}+2\cdot(u_{x}-u_{y})+c_{ij}+c_{j}-\mathit{dual}_{j} (25) \displaystyle\mathit{cost}_{y} \displaystyle=\mathit{cost}_{y}^{\prime}+2\cdot\max(W_{min}-w_{i},~0) Equation ( 24 ) takes into account the unpaid rest and the duals for the bus legs. Equation ( 25 ) further considers the minimum working time. 4.2.3. Constraints A shift is a path from s to t that does not violate any resource constraints. The following resource constraints need to be satisfied for every label x : d_{x}\leq D_{max} , s_{x}\leq T_{max} , \mathit{dc}_{x}\leq 4\cdot 60 , w_{x}\leq W_{max} , and r_{x}\geq 15 if w_{x}\geq 6\cdot 60 . Additionally, at node t , all labels x need to satisfy: r_{x}\geq 45 if w_{x}>9\cdot 60 and \mathit{b30}_{x} if w_{x}\geq 6\cdot 60 . 4.2.4. Dominance In order to track only paths with the potential to become minimum-cost paths, only pareto-optimal labels with respect to both cost and resource usage are kept at each node, i.e., labels which are not dominated. Regarding more complex constraints, it is important to observe that, if label x dominates label y at a node i , extensions of x to future nodes must still dominate extensions of y . Finally, the least-cost label at node t represents the minimum-cost path. Therefore, a label x dominates label y if all following conditions are true: d_{x}\leq d_{y} , s_{x}\leq s_{y} , \mathit{dc}_{x}\leq\mathit{dc}_{y} , \mathit{b20}_{x}\geq\mathit{b20}_{y} , \mathit{b15}_{x}\geq\mathit{b15}_{y} , w_{x}+u_{x}\leq w_{y} , r_{x}\geq r_{y} , \mathit{b30}_{x}\lor\neg\mathit{b30}_{y} , \mathit{bc30}_{x}\lor\neg\mathit{bc30}_{y} , c_{x}+2\cdot u_{x}\leq c_{y} . In general, lower values dominate for resources with upper bounds and higher values dominate for resources with lower bounds. The most complex case arises from the fact that the maximum value of unpaid break might be 0, 60, or 90 depending on the existence and position of a 30-minute rest break. This results in neither higher nor lower values of u_{i} being dominant. Rather, the uncertain amount of unpaid rest weakens the domination power of cost and working time, as those might vary in the amount of unpaid rest until the end of the path. However, in the next section a more useful way to deal with this problem is described. 4.3. Branching Branching (line 27 in Algorithm 1 ) is performed on the connections between bus legs in a shift that correspond to arcs in the subproblem. The branching considers a connection between bus legs i and j that appears fractionally in the solution to the relaxed master problem, and selects the most fractional (closest to 0.5 ) to maximize impact. In the left branch, all columns containing i or j , but not both consecutively, are removed. In the RCSPP graph all outgoing arcs from i except for the one connecting to j are removed. In the right branch, all columns with i and j assigned consecutively are removed, as well as the arc from i to j in the RCSPP graph. 4.4. Lagrangean Bound In the case when the column generation terminates at the root node, small optimality gaps are typically achieved. However, when there is not enough time to complete the column generation at the root node, a Lagrangean lower bound can be computed as O(\mathit{RMP})+\kappa\cdot O(\mathit{PP}) , where O(\mathit{RMP}) is the optimum of the reduced master problem, \kappa is an upper bound on the number of shifts and O(PP) is the optimum of the pricing problem. \kappa can be bounded by \kappa=\lfloor O(\mathit{RMP})/\mathit{minCost}\rfloor , where \mathit{minCost}=2\cdot W_{min}+\min_{\ell\in\mathbf{L}}{\mathit{length}_{\ell}} . The minimum reduced cost is only known when no more throttling (see next section) is in play. Otherwise a lower bound for the minimum reduced cost can be computed where the constraints regarding break positions for unpaid breaks are relaxed. However, these bounds turned out to be rather weak for the BDSP . 4.5. Handling the Subproblem Dimensionality As described in the previous section, due to the complex constraints for valid shifts, the subproblem complexity is very high. In particular, eleven resources are tracked in the labels. However, the efficiency of the label-setting algorithm depends on its ability to keep a small number of non-dominated labels. The more dimensions the labels have, the easier it is for labels to be non-dominated, drastically increasing the number of labels for processing. Therefore, the increase in the number of processed labels turns out to be the bottleneck of scaling the solution method to larger instances. Several novel improvements to reduce this bottleneck are introduced. These are generally applicable to other problems with similar characteristics. 4.5.1. Subproblem Partitioning Instead of generating all possible shifts from one graph, the subproblem is split into three similar, but disjoint RCSPP problems, removing the uncertainty for unpaid breaks depending on whether the maximum amount of rest break is 0, 60, or 90. This depends on the existence and position of a 30-minute rest break: • No 30-minute rest break : All arcs corresponding to rest breaks of at least 30 minutes can be removed, making the graph very spare and therefore fast to process. Unpaid rest is guaranteed to be 0, all rest break resources are ignored. • Uncentered 30-minute rest break : \mathit{b30}_{y} must be true at t . The maximum of u_{y} is changed to 60, but the current amount of u_{y} is guaranteed to be unpaid. Therefore, w_{x}\leq w_{y} and w_{x}+u_{x}\leq w_{y}+u_{y} can be used instead of w_{x}+u_{x}\leq w_{y} as the domination criterion (same change for c_{x} and c_{y} ), reducing the number of undominated labels. • Centered 30-minute rest break: \mathit{b30}_{y} and \mathit{b30c}_{y} must be true at t . The maximum of u_{y} is set to 90, but the improved dominance criteria from the previous graph still apply as again all of u_{y} is guaranteed to be unpaid. The pricing subproblem is used to add multiple columns (up to 1000 per graph) at once. Indeed, solving the relaxed master problem even with thousands of columns is much faster than solving the pricing subproblem. Therefore, accepting some unnecessary columns while reducing the number of times the subproblem is solved pays off. The different graphs are ordered by their complexity, measured by the number labels they expand. 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). 4.5.2. Cost Bound An upper bound for the reduced cost for each node can be computed by processing the RCSPP graph backwards with the current duals. The upper bound describes the maximum reduced cost at each node, such that there is still a path to arrive at t with reduced cost <0 , disregarding resource constraints. All labels above this bound can be discarded during the solution process. 4.5.3. Exponential Arc Throttling While it might be hard to find the best column, at least in the beginning of the solving process, there are many columns with negative reduced cost. Two options were considered to reduce the size of the subproblem in early iterations. The first option is to reduce the number of labels at each node. This can be done either by rejecting new labels after a certain threshold or only retaining labels according to certain criteria, e.g., the best 100 by cost. The better option is to exploit the fact that good columns are unlikely to include very costly arcs. It proposes a new throttling mechanism that imposes a maximum cost per arc, starting at 100 (just enough for a 30 min break). This greatly reduces the size of the graph and therefore the number of labels. Once the number of new columns is small, this factor is multiplied by 2. This is repeated until all arcs are included. While a lot of arcs are not present in the early stage, the focus on arcs that are likely to appear in good columns leads to very fast convergence to good solutions, even if there is not enough time to finish the column-generation process. 4.5.4. Improved Elimination of Non-Dominated Labels Even with the previously mentioned improvements, the majority of runtime is spent figuring out which labels are non-dominated. The naive approach is to compare each new label on a node with each label in the current set of non-dominated labels. However, the runtime complexity of this method is quadratic in the number of non-dominated labels. Therefore, two different methods are explored to speed up the dominance checks. The first method is the multi-dimensional divide-and-conquer [ Ben80 ] : It is based on recursively solving the k -dimensional problem with n labels by two k -dimensional problems of size n/2 and one k-1 -dimensional problem of size n . The second method is a two-stage approach based on k-d trees and bounding boxes [ CHT12 ] . The two-stage approach is more effective for several reasons. First, the algorithm is based on two stages. Instead of comparing each new label with all previously non-dominated labels both ways and deleting dominated labels in the process, two passes are performed. Labels are added as long as they are not dominated, but no removal operations are executed. The second pass is performed in opposite order before expanding the labels at a node, ensuring that only non-dominated labels are expanded. Second, instead of storing labels in a list, a k -dimensional tree is used for storage. For each node r on level \ell , the left child is better with respect to dimension \ell\text{ mod }k and the right child is worse (or equal). Finally, each node r is associated with a bound u_{r} where each dimension contains the best value among all nodes in the subtree rooted at r . Therefore, if a label is not dominated by u_{r} , it is not dominated by any label in the subtree rooted at r , saving several comparisons. 5. Large Neighborhood Search The Large Neighborhood Search (LNS) algorithm was introduced by Paul Shaw in 1998 [ Sha98 ] . The algorithm starts from an already feasible solution. The main idea is to destroy part of a solution in order to obtain a sub-problem that is easy to solve optimally or at least close to optimality. Selecting the part to destroy is done by a set \Omega of destroy operators (or destroyers ), the operator to apply is chosen randomly proportional to a given weight vector \bm{\rho} . Solving the sub-problem is done by a repair operator , often an exact method. We accept the new solution S^{\prime} if z(S^{\prime})