Investigating Large Neighbourhood Search for Bus Driver Scheduling

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 15:48:56

Abstract: The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimisation problem with high practical relevance. The aim is to assign bus drivers to predetermined routes while minimising a specified objective function that considers operating costs as well as employee satisfaction. Since we must satisfy several rules from a collective agreement and European regulations, the BDSP is highly constrained. Hence, using exact methods to solve large real-life-based instances is computationally too expensive, while heuristic methods still have a considerable gap to the optimum.
Our paper presents a Large Neighbourhood Search (LNS) approach to solve the BDSP. We propose several novel destroy operators and an approach using column generation to repair the sub-problem.
We analyse the impact of the destroy and repair operators and investigate various possibilities to select them, including adaptivity.
The proposed approach improves all the upper bounds for larger instances that exact methods cannot solve, as well as for some mid-sized instances, and outperforms existing heuristic approaches for this problem on all benchmark instances.

Main paper: 
 introduction: 
 The BDSP has evident practical relevance. Rules stem from different sources like EU regulations, national laws, or collective agreements, and can become very complicated. For real-life application, it is very important to consider not only paid working time, but also the overall well-being of the employees.The BDSP can be seen as a highly complex part of the general transportation planning system, which includes Vehicle Scheduling, Crew Rostering, and Timetabling (Wren 2004 ). This problem is an NP-hard problem, even when only working time constraints are imposed (Fischetti, Martello, and Toth 1987) . Different variants of BD-SPs have been studied from the early 60's (Wren 2004; Wren and Rousseau 1995) . Regarding exact methods, the BDSP is often modelled as a Set Partitioning Problem and Column Generation is often used (Smith and Wren 1988; Lin and Hsu 2016; Portugal, Lourenc ¸o, and Paixão 2008; Kletzander, Musliu, and Van Hentenryck 2021) . However, due to the need to solve very large real-world problems in a reasonable time, several heuristic methods have been studied for BDSP: some examples are Greedy (Martello and Toth 1986) , Tabu Search (Shen and Kwan 2001; Kletzander, Mazzoli, and Musliu 2022) , Simulated Annealing (Kletzander and Musliu 2020), GRASP (De Leone, Festa, and Marchitto 2011) , CMSA (Rosati et al. 2023) , and Genetic Algorithm (Li and Kwan 2003; Lourenc ¸o, Paixão, and Portugal 2001) .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 (WKO 2019) using the rules for regional lines. In particular, the collective agreement has stringent rules requiring the drivers to take frequent breaks, with the eventual option of splitting them into multiple parts. This problem has been introduced recently in the literature, and to the best of our knowledge, the recently introduced exact approach based on Branch and Price (Kletzander, Musliu, and Van Hentenryck 2021) , and meta-heuristic and hyperheuristic based approaches (Kletzander and Musliu 2020; Kletzander, Mazzoli, and Musliu 2022; Kletzander and Musliu 2022; Rosati et al. 2023; Kletzander and Musliu 2023) represent the current state of the art for this problem. Although these approaches give very good results, exact methods are computationally too expensive for large real-life-based instances and heuristic methods cannot obtain optimal solutions. Therefore, the study of new methods to tackle this problem is an interesting research question with practical implications. In this paper, we present a novel approach based on the Large Neighbourhood Search framework, which has been successfully used for solving other challenging real-life problems. However, applying this method to our problem domain requires innovative ideas for the destroy and repair operators, as well as a detailed investigation into their impact and the choice of parameters. Our proposed approach significantly improves upon existing results, particularly for larger instances that cannot be solved with exact methods, and outperforms state-of-the-art heuristic approaches on all benchmark instances.The main contributions of this paper are:• Our paper presents a novel solution approach for the BDSP, based on Large Neighbourhood Search (LNS). The proposed method includes three innovative destroy operators and leverages a column-generation-based technique as repair operator.• We explore different strategies for operator selection including an adaptive approach.• We analyse the impact of destroy operators on the algorithm's performance and compare the use of Column Generation with full Branch and Price to repair the subproblems.• We evaluate the performance of our LNS algorithm by comparing it with other state-of-the-art methods using existing benchmark instances from the literature. The results demonstrate that our LNS algorithm improves the upper bound for a significant number of instances, including some mid-sized instances and all large instances, and it outperforms all existing heuristic methods. 
problem description: 
 The investigated Bus Driver Scheduling Problem deals with the assignment of bus drivers to vehicles that already have a predetermined route for one day of operation. The problem specification is taken from Kletzander and Musliu (2020) .The bus routes are given as a set L of individual bus legs, each leg ℓ ∈ L is associated with a tour tour ℓ (corresponding to a particular vehicle), a start time start ℓ , an end time end ℓ , a starting position startPos ℓ , and an end position endPos ℓ . The actual driving time for the leg is denoted by drive ℓ . The given instances use drive ℓ = end ℓ -start ℓ .The set L is totally ordered by start, using tour as tiebreaker.ℓ tour ℓ start ℓ end ℓ startPos ℓ endPos ℓ 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 endPos i = startPos i+1 . A tour change occurs when a driver has an assignment of two consecutive bus legs i and j with tour i ̸ = tour j . A time distance matrix specifies, for each pair of positions p and q, the time d p,q a driver takes to get from p to q when not actively driving a bus. If no transfer is possible, then d p,q = ∞. d p,q with p ̸ = q is called the passive ride time. d p,p represents the time it takes to switch tour at the same position, but is not considered passive ride time. Finally, each position p is associated with an amount of working time for starting a shift (startWork p ) and ending a shift (endWork p ) at that position. The instances in this paper use startWork p = 15 and endWork p = 10 at the depot (p = 0). These values are 0 for other positions. For the given instances, the number of legs is proportional to the number of bus tours with approximately n legs ≈ 10 • n tours .A solution S to the problem is an assignment S : L → E, where E ⊆ N is the set of employees. The number of drivers 135 is not given, but one can imagine setting it as large as needed to have a feasible solution.Equivalently, it is useful to represent a solution by a set of shifts, that is the work scheduled to be performed by a driver in one day (Wren 2004 ). More precisely, the shift of driver 140 e ∈ E is the preimage L e = S -1 ({e}) with the total order induced by L. Hence, the notion of consecutive bus legs in a shift is well-defined.Each shift of a driver e ∈ E must be feasible according to the following criteria:• No overlapping bus legs are assigned to e.• Changing tour or position between consecutive legs i, j ∈ L e requires start j ≥ end i + d endPosi,startPosj .• The shift L e respects all hard constraints regarding work regulations as specified in the next section. 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 e need to be distinguished, as visualised in Figure 1 : Driving Time Regulations. The maximum driving time is restricted to D max = 9 h. The whole distance start j -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 h of driving time. In 165 case a break is split in several parts, all parts must occur before a driving block exceeds the 4 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 min; Working Time Regulations. The working time W e cannot exceed 10 h and has a soft minimum of 6.5 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 e < 6 h: no rest break;• 6 h ≤ W e ≤ 9 h: at least 30 min;• W e > 9 h: at least 45 min.The rest break may be split into one part of at least 30 min and one or more parts of at least 15 min. The first part has to occur after at most 6 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 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 h of the shift or the last 3 h of the shift, at most 1.5 h of unpaid rest are allowed; • Otherwise, at most one hour of unpaid rest is allowed.Shift split. If a rest break is at least 3 h long, it is instead considered a shift split, which is unpaid and does not count towards W e . However, such splits are typically regarded badly by the drivers. A shift split counts as a driving break, but does not contribute to rest breaks.We minimise the objective function combining cost and employee satisfaction defined in previous work (Kletzander and Musliu 2020) :EQUATIONThe objective function z represents a linear combination of six criteria for each employee e. The actual paid working time W ′ e = max{W e , 390} is the main objective, and it is combined with the total time T e to reduce long unpaid periods for employees. The next sub-objectives reduce the passive ride time ride e and the number of tours changes chg e , which is beneficial for both employees and efficient schedules. The last objective aims to reduce the number of split shifts split e as they are very unpopular. The weights were determined by previous work (Kletzander and Musliu 2020) based on preferences agreed by different stakeholders at Austrian bus companies and employee scheduling experts.Algorithm 1 Adaptive Large Neighbourhood Search Input: s 0 (the initial solution), k 0 (initial destruction size) Output: s bsf 1: k ← k 0 2: s bsf ← s 3: Initialise the weights ρ 4: while time < t max do 5:Select destroy operator d ∈ Ω using ρ 6:s ′ ← CG (d(s bsf , k)) 7: if z(s ′ ) < z(x bsf ) then 8: s bsf ← s ′ 9:end if 10:Update weights ρ and sub-problem size k 11: end while 12: return s bsf 
large neighbourhood search: 
 The Large Neighbourhood Search (LNS) algorithm was introduced by Paul Shaw in 1998 (Shaw 1998) . The main idea is to destroy part of a solution in order to obtain a subproblem that is easy to solve optimally or at least close to 220 optimality. Selecting the part to destroy is done by a set Ω of destroy operators (or destroyers), the operator to apply is chosen randomly proportional to a given weight vector ρ. Solving the sub-problem is done by a repair operator, often an exact method. We accept the new solution s ′ if 225 z(s ′ ) < z (s bsf ), where z represents the objective function value ( 1) and s bsf is the best-so-far solution. Algorithm 1 shows the pseudo-code of the algorithm.Since our repair mechanism can only produce complete 230 shifts, the aim of the destroyers is to select a subset of employees E ′ ⊆ E that is removed from the current solution. The size of the sub-problem k = |E ′ | is given to the destroy operator. We propose three distinct ways to select E ′ : EU Employees uniform: Select k employees uniformly.EW Employees weighted: k 2 of the employees are selected using their cost as weight, the others uniformly. This is motivated by the fact that employees with high cost have a higher potential to benefit from reoptimisation. The split is done since a combination of high-cost and 240 low-cost shifts can have a better potential to balance the shifts in the sub-problem, e.g., by transferring some legs from the high-cost shift to an underutilised shift. TR Tour remover: A tour is uniformly selected and all employees that share at least one leg of this tour are re-245 moved. This process is iterated until at least k employees are removed. This operator is based on the idea of selecting employees that have something in common and therefore have a higher potential that useful recombinations of their shifts are possible, e.g., optimising when and where 250 a bus is handed over from one driver to the other. Note that this operator might select more than k employees because it removes all the employees who share a tour.However, tours are usually not shared by too many employees since this incurs extra cost, so |E ′ | does typically not exceed k by much.Once a set of removed employees E ′ is selected, the repair mechanism needs to solve the sub-instance that is created by using all legs ℓ assigned to any employee e ∈ E ′ together with the common data for the whole instance. This sub-instance represents a complete instance of BDSP and can therefore be solved with any solution method of choice. Since the Branch and Price approach (Kletzander, Musliu, and Van Hentenryck 2021) is the most powerful for small 265 instances (it can provide an optimal solution for instances with 10 tours within seconds), it is the best fit for solving these sub-instances.Branch and Price (Barnhart et al. 1998) works by splitting the problem into a master problem and a sub-problem. The master problem is set partitioning (Balas and Padberg 1976) which assumes that a set of shifts is already given including costs for each shift and tries to find the minimum cost subset of these shifts that covers each bus leg exactly once.EQUATIONHere x s is the variable for the selection of shift s. The Master problem and sub-problem are repeatedly solved until no more path with negative reduced cost can be found. This part of the process is called Column Generation and results in the optimal solution for the relaxed master problem, however this result is usually fractional. Therefore, branching is done and Column Generation is repeated on a modified problem where some connections from the graph are removed. This branching process is repeated until all branches are closed or until timeout.However, previous work (Kletzander, Musliu, and Van Hentenryck 2021) already shows that, for instances up to 60 tours, the results are very close to the optimum when only solving Column Generation on the root node and then solving the master problem with integrality constraint on the set of columns obtained during Column Generation. These solutions are often much faster, but achieve a gap of around 1% while the following branching process only closes this remaining gap very slowly.Therefore, we propose to drop the aim of optimally solving the sub-instance with Branch and Price, and instead only use Column Generation on the root node to get very good solutions to the sub-instance very fast. In the evaluation, we compare using Column Generation (CG) with using full Branch and Price (BP).Once the repair mechanism returns a solution consisting of employees E * that contain all bus legs from E ′ , the new solution for the full problem is provided by (E\E ′ ) ∪ E * .An important parameter for large neighbourhood search is the size of the sub-problem. However, the appropriate size depends on the destroy and repair operators. In the case of our system, the destroy operators are easy and fast to apply, but the complexity of Branch and Price increases rapidly with the size. Even when just applying Column Generation, the size of the RCSPP in the sub-problem still leads to considerable increases in runtime.Therefore, based on preliminary experiments, the smallest sub-problem size in use is k = 5. This size can still be solved in a few seconds, so it is fast enough, but it also leads to a high number of improvements, so it is large enough to allow meaningful changes of the solution. In the process of the search this size can be increased if too many iterations without improvement occur. This indicates that a larger size might be needed to escape local optima.We use a maximum size of k max = 20 since runtime grows rapidly and for larger size too much time would be spent on each individual sub-problem. When running the algorithm, the size starts with an initial value of k 0 , and is increased by 1 until reaching k max = 20 whenever the previous improvement was more than n max iterations ago. As soon as an improvement is found, k is set back to the initial value k 0 .Adaptive Large Neighbourhood Search (ALNS) is an extension of LNS, where the weights ρ for selecting the operators are adapted dynamically based on their performance (Ropke and Pisinger 2006).Our method takes into account the score and the time required by destroy operator i. At first, every component of the weight vector ρ is set to 1 |Ω| . The destroy operator is selected in a random way with weights ρ using the roulette wheel principle: the probability of choosing the i-th destroy operator is defined as follows:EQUATIONThe selected destroy operator is then applied to the current solution s, which results in a sub-problem that is passed to the repair operator r. At iteration n, we update the weight ρ n i of the i-th destroy operator using the following equation:ρ n+1 i = λρ n i + (1 -λ) n j=0 s j i n j=0 t j i (6)where s j i = 1 if the i-th operator has improved the bestknown-solution at iteration j, else 0. The denominator is a sum of runtimes, so t j i represents the time the i-th operator took for the entire process (destroying + repairing) at iteration j. If operator i was not selected at iteration j, then s j i = t j i = 0. The real parameter λ ∈ [0, 1] controls the sensitivity of the weights. A value of λ close to 0 implies that the most recent results have a large influence while a value of 1 keeps the initial weights static.As long as the denominator is 0, the value of the fraction is set to 0. In this case, ρ n+1 i = λρ n i . 
evaluation: 
 All executions were performed on a cluster with 11 nodes equipped with Ubuntu 22.04.2 LTS. Each node has two Intel Xeon E5-2650 v4 (max 2.20 GHz 12 physical cores, no hyperthreading). For each run, we set a memory limit of 4.267 GB and use one thread. The implementation is in Python, executed with PyPy 7.3.11. BP is implemented in Java, using OpenJDK 20, and CPLEX 22.11 for the master problem.We evaluate the quality of a solution using the relative gap (GAP) compared to the best-known solution in the literature:EQUATION)where x is the solution and x bks is the best-known solution.A negative value of GAP(x) means a new best-known solution has been found. We use the GAP to have a metric quality that does not scale with the instance dimension.All experiments are performed with 1 h of wallclock time. Our method is non-deterministic. Therefore, we execute 10 runs for each instance. Random seeds for different runs are recorded for reproducibility.We use the publicly available sets of benchmark instances provided by previous work (Kletzander and Musliu 2020; Kletzander, Mazzoli, and Musliu 2022) 1 . There are 65 instances in 13 sizes, ranging from around 10 to around 250 tours. Note that the last 3 sizes have much larger size changes than the previous sizes.The initial solutions were generated using a greedy construction method (Kletzander and Musliu 2020) , assigning bus legs to the employee where the lowest additional cost is incurred, or to a new employee if this would incur an extra cost of at most 500 compared to the best existing employee assignment.We first present the final results, obtained with the best configurations using k 0 = 10, n max = 50, the repair operator CG, and only the destroyer TR for LNS, or the parameter λ = 2 3 and all destroyers for ALNS. Details about the oper-410 ator selection are then presented in the next subsection.Table 2 shows the objective function values for LNS, ALNS, CMSA (Rosati et al. 2023 ) (same time budget) and BP (Kletzander, Musliu, and Van Hentenryck 2021) . For each size there are 5 instances, each value in the table is 415 the average of the 5 results per size due to space limitations. The full table is available as supplementary material.BP is the state-of-the-art method for smaller instances. It optimally solves the first 10 instances ( * ), except for instance 7. For the smallest size it only takes few seconds. 420 It has a known optimality gap of less than 1 % for all instances up to size 60 and provides the best-known solutions up to size 90 and 2 instances of size 100. However, it uses many resources. Results starting from size 60 use extra time on four threads after a full hour of BP to obtain an integer 425 solution, up to an additional hour ( † ), while our approach is very close to these results while always keeping to 1 h and a single thread. Up to size 100, the average of LNS outperforms previous BP results on 5 instances, the minimum on 8 instances. For instances larger than size 100, BP fails with 430 a memory error even when given 8 GB of RAM, and with larger memory allowance, it still produces solutions worse than the results from the construction heuristic, since the integer master problem is just becoming too large to solve in reasonable time.The previous state-of-the-art incomplete method, CMSA, was able to outperform earlier meta-heuristics like Simulated Annealing and Tabu search. In comparison, we can Figure 3 shows the average GAP for LNS, ALNS, BP, and CMSA. Points below the x-axis (i.e., instances with a negative GAP) show new best solutions.Statistical Significance. We compared CMSA and LNS across all 65 instances using the Wilcoxon signed-rank test (Calvo and Santafé 2016) . We used the scipy module (version 1.11.1) of Python. With a significance level of α = 0.05, the test confirms that the p-value is smaller than 2.4 × 10 -16 , showing a significant difference between the two algorithms. Moreover, we performed statistical tests using the R script SCMAMP (Calvo 2021) , also including Simulated Annealing and Hill Climbing (Kletzander and Musliu 2020) , and Tabu Search (Kletzander, Mazzoli, and Musliu 2022) . As described by Calvo (Calvo and Santafé 2016) , we first applied the Friedman test to detect whether all algorithms perform the same, which is rejected with a p-value smaller than 2.4 × 10 -16 . Then, we compared multiple algorithms using the Nemenyi post-hoc test (Calvo and Santafé 2016) .We graphically show the results on all instances with a Critical Difference (CD) plot in Figure 4 . Each considered algorithm is placed on the horizontal axis according to its average ranking for the instances (lower is better). The performances of those algorithm variants below the critical difference threshold (0.94) are considered statistically equivalent. In the CD plot, this is remarked by a horizontal bold bar that joins different algorithms.The results show that LNS performs better than ALNS, but not with significant difference, while both versions significantly outperform CMSA, which in turn significantly outperforms the previous meta-heuristics.To select our final parameters, we thoroughly analysed the impact of different algorithmic components on a subset of instances from the benchmark set. Since all algorithms show similar performance on instances of the same size, we chose one instance from each size, skipping the smallest size that can be solved to optimality with BP in seconds. Therefore, Repair Operator Selection. For fixed k 0 = 10, n max = 50, and equal selection of all destroyers, we compared BP and CG. Initial experiments showed that the performance of destroy and repair is rather independent from each other, which enables separate evaluation. Each repair operation has a maximum budget of 5 min, but is expected to usually terminate much faster.Results are shown in Figure 5 . The performance is very similar for the smaller instances, but CG is clearly the better choice for larger instances, showing that the extra time used for repairing in BP is not justified. Figure 6 shows that BP usually takes longer than CG, but while the average time in both cases is under 10 s, BP often reaches the time budget of 5 min, while CG is always below 2 min, showing a much better worst case behaviour.505 Initial Destruction Size. There are several options regarding the destroyers, first we investigated the initial destruction size k 0 , fixing all other parameters. The size remained constant, CG and all destroyers are used, and ρ i = 1/3 without adaptivity.We tested sizes k 0 ∈ {5, 10, 15, 20}. Figure 7 shows the results. While k 0 = 20 performs slightly better for smaller instances, it is outperformed on larger instances. Overall, We tested n max ∈ {5, 10, 15, 20, 30, 50}, but found no significant difference among them, as shown in Figure 8 . We decided to set n max = 50, since it still allows to increase the size when needed, but does not increase it very often. We tried starting with different values for k 0 , but found similar results, the initial size is more important than the step.Figure 9 shows the impact of n max on the number of iterations (CG calls). Larger values of n max imply less frequent size changes, so more iterations. Of note is that for the larger instances, the size barely changes, as improvements are frequently found even with the initial size until timeout.Destroyer Selection. In order to understand the impact of the destroy operators, we tested all the 7 possible combinations of them. Figure 10 shows that TR has the biggest impact on the performance. Is shows the best results on its own, with very similar results using in in any other combination, while all combinations without TR show significantly worse performance, with higher divergence among larger instances.The advantage of selecting employees that share tours is that the sub-problems are more likely to allow meaningful optimisations. This hypothesis is further backed by the success rate (percentage of iterations where the current solution could be improved) in Figure 11 , which shows that in general for larger instances more improvements in sub- problems can be found, but especially using just TR has a 545 higher success rate than any other set of destroyers. Additionally, Figure 12 shows that the Tour Remover operator is essential to obtain high-quality solutions (the EU and EW destroy operators alone are not enough).While only using TR is the best choice, we further invest-550 igated several non-uniform weight distributions with high weights for TR. Denoting the weights as (ρ EU , ρ EW , ρ TR ), we conducted experiments with (5, 5, 90), (10, 10, 80), and (25, 25, 50) . The first two where very similar to TR only, while (25, 25, 50) started to get slightly worse.555 Adaptivity. To investigate the impact of adaptivity, we conducted experiments by changing the parameter λ in (6), considering all three destroy operators. We tested three different values for λ: 1 3 , 1 2 , and 2 3 . Figure 13 suggests that the adaptivity does not improve the average GAP with respect to the solely TR, and different values of λ do not show significant difference. 
conclusions: 
 This paper studied a complex version of the Bus Driver Scheduling Problem and proposed a new hybrid approach based on Large Neighbourhood Search to solve it. The results show that our algorithm outperforms all previous metaheuristics on the problem, and significantly improves all best-known solutions for larger instances as well as some mid-sized instances. Although exact Branch and Price remains the best method for smaller instances, our results come very close on mid-sized instances while using fewer computational resources, making it the best choice for a wide range of realistic instance sizes.We further compared and evaluated several algorithmic components, including different repair options, several parameters for the destroy operator selection, and the role of adaptivity. Results show that Column Generation is more effective as a repair operator than full BP, and in particular the bus tour structure and the initial destruction size play a crucial role during the destruction phase.Note that while this paper only addresses one set of rules, the methodology of using LNS with Column Generation as a repair operator is applicable to different kinds of rule sets or even different problems with a similar structure where individual shifts need to cover a set of tasks. Adaptations to different problems can be done by changing only the subproblem (RCSPP) used in Column Generation. Adapting a different set of rules to fit into the framework of the RCSPP can be challenging, but all other components are independent of the specific rules. This will be interesting to investigate in future work. Moreover, since this method provides very good results, applying LNS with Column Generation to other complex problems will be considered for future work. 
: 
 we must satisfy several rules from a collective agreement and European regulations, the BDSP is highly constrained. Hence, using exact methods to solve large real-life-based instances is computationally too expensive, while heuristic methods still have a considerable gap to the optimum. Our paper presents a Large Neighbourhood Search (LNS) approach to solve the BDSP. We propose several novel destroy operators and an approach using Column Generation to repair the sub-problem. We analyse the impact of the destroy and repair operators and investigate various possibilities to select them, including adaptivity. The proposed approach improves all the upper bounds for larger instances that exact methods cannot solve, as well as for some mid-sized instances, and outperforms existing heuristic approaches for this problem on all benchmark instances. 
 
 Appendix:  


Decision: This paper presents a Large Neighborhood Search (LNS) approach to solving a real-world bus driver scheduling problem (BDSP) that attempts to optimize both operating costs and driver satisfaction, while satisfying complex constraints emanating from collective agreement rights and government regulations. The aim is an effective solution for large problem instances that are beyond the reach of exact methods. Several destroy and repair operators are proposed and configured to develop a baseline search procedure, and a mechanism for selecting them adaptively during the search is also explored. An experimental analysis is performed on a previously published set of benchmark problems, and new best-known results are obtained for all problems. 

Strengths: The technique is applied to a real-world problem with several complicated constraints that are not typically considered in research settings. The benchmark problem set considered in the paper are derived from the real-world problem faced by the Austrian bus drivers and can potentially impact the effectiveness of future operations. The analysis rightly focuses on large problem instances that are outside of the reach of exact methods, and technique is shown to produce new best-known results (with confirmed statistical significance. The presentation is clear and provides sufficient background for the paper to be self-contained.

Weaknesses: The main weakness of the paper is its perceived lack of novelty. The innovation in the approach over previous work is not emphasized in the presentation and appears to be quite limited. Several of the solution components comprising the configured LNS have been previously published, and the mechanisms of LNS /ALNS technology are generally well known. What are the keys to application success here? 

If the paper is accepted, please incorporate author(s) rebuttal comments made in response to reviewer questions about novelty and respond to other reviewer criticisms raised when preparing the final version of the paper.

Reviews: review: strength_weakness: strength_weakness: - I am not sure about the novelty of the paper. The studied problem (bus driver scheduling) is very specific, inspired from real-world but taken from the literature. This specific problem has been solved by a (similar) group of researchers using different methods, from exact method, meta-heuristics, and various search based methods (tabu, local search, and iterated local search). The authors of this work apply another search based method (LNS and ALNS) with relatively generic operators to this problem, using random removal, a weight based removal and a tour removal operator. These operators all have been suggested before for generic routing problems. Given the problem is very specific and the proposed LNS is a commonly used approach for scheduling and routing, I think the impact of this paper is limited. 
- As a paper submitted to the application track, I was hoping to see a good evaluation of the method in a realistic setting. However, the instances used are from the previous work and the properties (how close to real-world instances) were not described. The authors also didn’t  provide discussion on the impact of the work to the real-world problem. 
-  On of the main contributions of the work is its ability to get faster results, using lower resources. However, a study with different search budgets is missing from the work (how do LNS/ALNS perform when the search budget is e.g., halved/doubled).
- The writing of the paper can be improved; especially of the problem formulation is unclear. Also, the parameter tuning of the different proposed methods should be explained before the results section, and the authors do not explain the CMSA benchmarking method in the paper.
questions: questions: - Why have you not tuned the weight values of the ALNS and its sensitivity parameter λ, which are crucial for its performance.
- Why have you decided to not use any acceptance criterium in LNS and ALNS (such as simulated annealing)?
- In Figure 6, why is the runtime of BP max larger for instances of a smaller size, assuming that the destroy severity is remained the same? If these are edge cases, why do you only include the average runtime here (maybe with some standard deviations)?
strength_weakness: strength_weakness: The paper presents no major weaknesses. Maybe the mean weakness is the very limited significance of the results obtained from the adaptivity-related analysis, which did not keep the promises one would have hoped for. Indeed, the ALNS approach returned very marginal improvements, if any, which can only be explained by the fact that the superiority of the TR destroy operator w.r.t. EW and EU revealed so high that no dynamic combination of the other approaches could keep up. However, my impression is that this aspect will require further investigation.
questions: questions: 1) Section 3.4, page 5, 1st column, in the description of formula (6): how is the information about all the possible past improvements obtained by all the operators in the previous iterations kept?  

2) Relatively to the ALNS: being ALNS adaptive, one might expect that both procedures will eventually achieve the same performance, as the weight \rho should eventually "learn" to select the TR destroyer as this is the most effective (i.e., the one that has best improved the past solutions). Can the authors elaborate on this?
strength_weakness: strength_weakness: - The paper does not introduce any novel algorithm components or problem elements. ALNS algorithms are well-known. The proposed destroy operators are rather standard and generic. The repair operator is more advanced, but was previously published by the same authors. The problem itself and the used benchmark instances were previously published by the same authors. 
- The improvements over existing algorithms is very small (0.26 to 3.62%), but the authors show it is statistically significant.
- The evaluation is done by comparing the new algorithm only to methods previously published by the same authors.
questions: questions: - The concept of a 'tour' is not clearly explained in Section 2. Does it correspond one-to-one to a specific vehicle? 
- How did you define the probability update rule (6)?
- What is the reference value used to compute the GAP in Figure 3? Equation (7) refers to best-known solutions from the literature, but which results are these? Not from CMSA or BP?