We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a O(n log n) algorithm to solve this problem. Next, we formalize a notion of fairness among workers, and impose that each worker performs the same work over time. We analyze the resulting trade-off between efficiency and fairness, showing that the price of fairness is at most one extra worker, and that such a fair solution can always be found using the Nearest Neighbor heuristic. We characterize all instances that admit a solution that is both fair and efficient, and use this result to develop a O(n log n) exact algorithm for the fair periodic assignment problem. Finally, we show that allowing aperiodic schedules never reduces the price of fairness.

We consider robust tactical crew scheduling for a large passenger railway operator, who aims to inform crew early on about their work schedules while also maintaining the ability to respond to changes in the daily timetables. To resolve this conflict, the operator considers a template-based planning process, templates being time windows during which duties can later be scheduled. The goal is to select a cost-efficient set of templates that is robust with respect to uncertainty in the work to be performed in the operational phase. A set of templates is deemed robust when few excess duties are required to cover all work in the operational planning phase. To enable the construction of efficient template-based rosters, we impose several template rostering constraints that proxy the actual rostering rules of later planning steps. We propose a two-phase accelerated Benders decomposition algorithm that can incorporate these restrictions. Computational experiments on real-life instances from Netherlands Railways, featuring up to 948 tasks per day, show that historical planning information can be used to obtain robust templates and that parsimonious solutions can be obtained at negligible extra costs. Compared to a literature benchmark, our Benders decomposition method solves three times as many instances without rostering constraints to optimality. 

In many real-life settings, the size and complexity of work allocation problems necessitate the use of operations research (OR) techniques. Traditionally, OR models have prioritised efficiency objectives, such as cost minimisation. However, there is a growing interest in methods that ensure fair work allocations. This thesis applies OR techniques to design models and methods that achieve fairness in work assignments. 

The first part of this thesis focuses on railway crew planning, addressing practical problems that arise in the proposed crew planning process of Netherlands Railways. The first study considers tactical crew scheduling, introducing a Benders decomposition approach for robust template selection. The second study examines fair operational crew scheduling under the assumption that template-based rosters have already been constructed. It proposes a tailored column generation heuristic to construct individual crew schedules that are fair over time. The third study presents an efficient exact pricing algorithm to accelerate column generation algorithms for basic railway crew scheduling problems.

The second part of this thesis takes a more theoretical perspective, developing general optimisation methods for fairness-oriented work allocation. The first study centers on fairness over time in settings where work must be assigned online to homogeneous workers. It provides theoretical and experimental justifications for using an intuitive work allocation policy. The second study investigates branch-and-price methods for minimising the range and other order-based objective functions, introducing a generic branching rule that enables the use of classical, efficient branch-and-price methods for this type of problem.

Passenger railway operators typically employ large numbers of drivers and guards, and are interested in providing them with fair and attractive working conditions. At Netherlands Railways (NS), the largest passenger railway operator in The Netherlands, this challenge is addressed through the use of Sharing-Sweet-and-Sour rules, which specify a fair allocation of sweet (attractive) and sour (unattractive) work over the different crew bases. While these rules are currently implemented at the crew base level and in the tactical planning phase, NS is considering formulating these rules at the individual level, in the operational planning phase, and with respect to a given planning period. This gives rise to a new problem, which we call the railway crew planning problem with fairness over time. We propose a rolling horizon approach with a penalty-based feedback mechanism and a column generation heuristic to solve this problem. On several real-life instances from NS, including up to 572 unique guards, this method is able to satisfy the individual rules for on average 95.2% of the employees. 

We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch-and-price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and is compatible with any problem-specific branching scheme. We show several desirable properties of range branching and show its effectiveness on a series of fair capacitated vehicle routing instances. Range branching significantly improves multiple classical branching schemes in terms of computing time, optimality gap, and size of the branch-and-bound tree, allowing us to solve many more large instances than classical methods.  

There is growing interest in including fairness in optimization models. In particular, the concept of fairness over time, or, long-term fairness, is gaining attention. In this paper, we focus on fairness over time in online optimization problems involving the assignment of work to multiple homogeneous workers. This encompasses many real-life problems, including variants of the vehicle routing problem and the crew scheduling problem. The online assignment problem with fairness over time is formally defined. We propose a simple and interpretable assignment policy with some desirable properties. In addition, we perform a case study on the capacitated vehicle routing problem. Empirically, we show that the most cost-efficient solution usually results in unfair assignments while much more fair solutions can be attained with minor efficiency loss using our policy. 

The railway crew scheduling problem consists of selecting a least cost set of duties that cover all tasks. Large-scale crew scheduling problems are typically solved with column generation, where in each iteration a pricing problem needs to be solved. When the duty constraints consist in a maximum duty length, a meal break constraint, and the requirement to start and end at the same crew depot, the fastest known exact pricing algorithm has O(|N|3) complexity, |N| being the number of tasks. In this work we propose an O(|N|2) exact pricing algorithm. We compare the two algorithms on randomly generated instances and show that a reduction in computation time of 95% is attained on instances of size |N|=1,250. 

Planned maintenance and construction activities are crucial for heavily used railway networks to cope with the ever increasing demand. These activities lead to changes in the timetable and rolling stock schedule (often for multiple days) and can have a major impact on the crew schedule, as the changes can render many planned duties infeasible. In this paper, we propose a novel integrated approach to crew re-planning, i.e., the construction of new duties and rosters for the employees given changes in the timetable and rolling stock schedule. In current practice, the feasibility of the new rosters is ‘assured’ by allowing the new duties to deviate only slightly from the original ones. This allows the problem to be solved on a day-by-day basis. In the Integrated Crew Re-Planning Problem (ICRPP), we loosen this requirement and allow for more flexibility: The ICRPP considers the re-scheduling of crew for multiple days simultaneously, thereby explicitly taking the feasibility of the rosters into account. By integrating the scheduling and rostering decisions, we can allow for larger deviations from the original duties. We propose a mathematical formulation for the ICRPP, strengthen it using a family of valid cover inequalities, and develop a column generation approach to solve the problem. We apply our solution approach to practical instances from Netherlands Railways, and show the benefits of integrating the re-planning process. 

In this paper we investigate the incorporation of graph-based features into LOD path-based recommender systems, an approach that so far has received little attention. More specifically, we propose two normalisation procedures that adjust user-item path counts by the degree centrality of the nodes connecting them. Evaluation on the MovieLens 1M dataset shows that the linear normalisation approach yields a significant increase in recommendation accuracy as compared to the default case, especially in settings where the most popular movies are omitted. These results serve as a fruitful base for further incorporation of graph measures into recommender systems, and might help in establishing the recommendation diversity that has recently gained much attention. 

We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch and price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and can be used on top of problem-specific branching schemes. We show several desirable properties of range branching and show its effectiveness on a series of instances of the fair capacitated vehicle routing problem and fair generalized assignment problem. Range branching significantly improves multiple classical branching schemes in terms of computing time, optimality gap, and size of the branch-and-bound tree, allowing us to solve many more large instances than classical methods. Moreover, we show how range branching can be successfully generalized to order-based objective functions, such as the Gini deviation.

Netherlands Railways is considering a shift towards a novel crew planning process featuring individual Sharing-Sweet-and-Sour rules, designed to provide each crew member with a fair and varied work schedule. This approach replaces the current, crew base-level fairness mechanisms. In the new process, template-based rosters specify generic time windows, to which personalised duties are assigned in the operational phase. To evaluate the feasibility of the novel process, we develop a scalable simulation framework that accurately models the operational crew planning phase. The framework features a column generation heuristic to construct personalised duties, a network decomposition strategy to reduce computing times, and stochastically generated disruptions to simulate daily operations. Simulating the process for 3,265 guards throughout the year 2024, we find high conformance with the proposed individual Sharing-Sweet-and-Sour rules, with over 93% compliance for four out of six attributes. Our results yield valuable inputs for ongoing discussions with the works council and provide company experts with a powerful strategic tool. These insights are relevant to other transport operators, showing that fair and attractive individual work schedules can be constructed and highlighting the practical benefits of tailored simulation tools.