# An overview of optimization approaches for scheduling and rostering
resources in public transportation

Lucas Mertens  Lena-Antonia Wolbeck  David Rößler  Lin Xie  Natalia Kliewer

###### Abstract

Public transport is an essential component in satisfying people’s growing need
for mobility. Thus, providers are required to organize their services well in
order to meet the high demand of service quality at low operational costs. In
practice, optimized planning can lead to considerable improvements for
providers, customers, and municipalities. The planning process related to
public transport consists of various decision problems, of which the providers
are usually responsible for vehicle and crew planning. There is a growing body
of literature that recognizes the shift from sequential and iterative to
integrated solution approaches for these problems. Integrated optimization of
several planning phases enables higher degrees of freedom in planning, which
allows for operational costs savings and increased service quality. This paper
provides an overview of solution approaches for integrated optimization based
on operations research techniques for the vehicle scheduling, crew scheduling,
and crew rostering problem, extended by a selected number of relevant related
approaches from other industries. Therefore, existent optimization approaches
are analyzed with regard to different aspects such as mathematical modeling,
optimization objective, and method, as well as the source and scope of the
data used for evaluation. Additionally, we analyze the problem dimensions that
are usually required in practical applications. In doing so, we are able to
point out directions for future research, such as a stronger focus on
objectives besides cost-minimization like robustness, schedule regularity, or
fairness.

##  1 Introduction

Urbanization in developed and developing countries leads to quickly growing
needs for urban mobility. Cities and municipalities face severe challenges in
providing the necessary infrastructure to satisfy these needs. Individual
motorized traffic is rather part of the problem than of the solution: Traffic
jams leading to adverse effects such as long commuting times, frequent
accidents, and air pollution are just some of the issues that arise from
cities being overflown with cars [136]. An efficient public mass
transportation system can remedy these problems [115]. In addition to the
advantage of accommodating the growing mobility demand at lower external
effects and costs, public mass transport is safer as well as more resource-
efficient than individual transport [122].

Traditionally, public transport used to be provided solely by the public
sector. However, it has been deregulated in many countries. Nowadays, the
transport services offered by private companies are substantial, and
competition in this area is increasing [112]. For a public transport provider,
an effective and efficient operation is crucial to face the trade-off between
operating costs and service quality. Thus, in each phase of the planning
process, this trade-off is considered. Moreover, further goals like schedule
robustness, regularity, travel satisfaction, and fairness for employees have
gained more attention in recent years [88, 93, 76].

Since the underlying decision problems are not trivial to solve (to
optimality), public transport planning has been extensively studied in the
literature. Usually, the public transport planning process is divided into
planning steps that have to be performed subsequently. However, recent
advances in optimization methods allow a gradual integration of the
optimization subproblems arising from subsequent planning steps. While better
network designing, line planning, and timetabling effect both customer
satisfaction and cost structure, vehicle scheduling, crew scheduling, and crew
rostering mainly influence the provider’s profit as well as operational
timeliness. Superior calculated vehicle and crew schedules lead to lower
investments due to less required vehicles and personnel and lower variable
costs due to decreased deadheading distances and improved duty allocation.
Furthermore, crew rostering impacts costs and employee satisfaction likewise,
as crew members desire a fair distribution of duties and workload. Integrating
two or three subproblems increases the degree of freedom for these decision
problems, and thus, schedule and roster quality may improve. Other industries
like railway or aircraft face similar challenges, therefore their solution
approaches might be transferable to public transport planning.

The last decade has witnessed an enormous increase in publications on
integrated optimization approaches for public transport planning problems. In
2015, [115] conducted a literature review on solution approaches for bus
transport systems. In order to extend and update this overview, we will
analyze the state-of-the-art approaches that follow different variants of
integration and objectives in this paper. We first introduce the operational
problems in public transport and point out the contribution of the sequential
approach in Section 2. Second, we point out the ongoing shift from sequential
to an integrated approach in Section 3.

##  2 Decision problems within the operational public transport planning
process

The planning process in public transport comprises various decision problems,
which can be grouped according to their planning horizons (see Figure 1). On a
strategical level, public transport providers plan long-term, e.g., the
network design and the planning of lines (routes, frequencies). Tactical
decisions, however, aim to provide timetables and to reduce the operational
costs in the medium term [115]. In practice, such decisions are most likely
made by the principal, e.g., the municipality [113]. We consider strategical
and tactical planning decisions regarding routes, frequencies, and timetables
as input for the operational planning tasks of vehicle scheduling, crew
scheduling, and crew rostering. Therefore, in the scope of this paper, we
assume that public transport providers focus on minimizing costs concerning
vehicles and staff in the short term when operationally deciding on their
transport and employee schedules [115]. Following this, we look at three
decision problems: The Vehicle Scheduling Problem (VSP), the Crew Scheduling
Problem (CSP), and the Crew Rostering Problem (CRP), which are introduced in
the following.

Figure 1: The sequential planning process in public bus transit, as
illustrated in [143].

###  2.1 Vehicle scheduling problem

Given a timetable with specified service trips, the VSP relates to generating
an optimal vehicle schedule that covers all service trips and achieves the
lowest operational costs or optimizes further objectives [95]. A service trip
is defined by the line it belongs to, a departure and arrival time, as well as
the corresponding locations. To achieve a sequence of compatible trips,
additional deadhead trips can be added to connect subsequent service trips.
These deadhead trips comprise all unloaded trips, including the departure from
(pull-out) and arrival at (pull-in) the depot. A solution to the VSP
corresponds to a vehicle schedule consisting of vehicle blocks, each
representing a feasible sequence of trips for one vehicle [84]. Thus, a
vehicle block comprises one or several vehicle rotations starting from a
depot, executing one or more service trips, and returning to a depot.

Solving a VSP is not a trivial task and can vary greatly depending on
practical requirements and circumstances. The fundamental VSP is characterized
by a single depot, a homogeneous fleet, and the objective to minimize costs
only [95]. One of the first optimal solutions of such a VSP originates from
[134]. However, modern VSP evolved to cover a more complex environment.
Opposed to originating from one depot only, the Multi Depot Vehicle Scheduling
Problem (MDVSP) considers multiple depots as well as multiple vehicle types
and vehicle type groups. This enhancement majorly affects the way of solving
the problem. Whereas the single-depot VSP is described as a polynomially
solvable minimum cost flow problem, the MDVSP is considered to be NP-hard
[83]. By utilizing a linear programming approach with column generation, [123]
exactly solve the MDVSP. Considering multiple depots as well as a
heterogeneous fleet, [118] present a Time Space Network (TSN) to efficiently
model a network associated to the MDVSP. By modeling the MDVSP as a TSN, the
solution space can be reduced significantly. As a result, optimally solving
the multicommodity min-cost flow MIP-formulation of the MDVSP for real-world
instances is made possible. However, not only the underlying problem shifted
to a more complex model, but also the objective itself adapted. Whereas in the
beginning, the focus was primarily on cost-related objectives, other goals
like the schedule robustness are increasingly considered in recent years [119,
128]. Different dimensions regarding constraints such as the limited ranges of
electric buses [77, 131] and objectives shape each VSP individually. Several
modeling approaches, as well as specialized solution strategies for the VSP
and its extensions, have been developed in the last decades. For an overview
on vehicle scheduling and corresponding solution approaches, we refer to [90]
and [129].

###  2.2 Crew scheduling problem

In sequential planning, the decision problem of crew scheduling arises
succeeding to vehicle scheduling. The CSP (also known as driver, duty, or
shift scheduling) aims at finding a daily cost-optimal duty allocation that
encompasses all trips of the vehicle blocks [86]. These duties are not
assigned to specific drivers yet. Each anonymous duty is associated with a
predefined generic duty type. These heterogeneous duty types are characterized
by different lengths and attributes. A duty type, e.g., considers legal
requirements on working and break times as well as company-specific
regulations such as the kind of qualifications required [103].

Due to the vast amount of possible solutions based on the predefined duty
types covering the vehicle schedule’s trips, solving the CSP is considered to
be NP-hard [100]. The complexity of finding a solution to the CSP correlates
with the number of trips and especially with the quantity and diversity of the
generic duty types. Depending on practical requirements, each duty type at
least considers legal, union-related, and company-defined regulations. These
characteristics vary significantly regarding each problem specification. In
solving the CSP, it has prevailed to split all vehicle blocks into segments
according to predefined relief points [96]. Relief points indicate locations
at specific times, which allow an exchange of drivers. The tasks between two
relief points represent the smallest unit of work that has to be covered by
the same driver and is called duty element. Combining consecutive duty
elements and adding sign-on and sign-off tasks results in a possible shift,
and is called a piece of work. Final duties are composed of one or more pieces
of work, where usually two pieces of work are separated by a break [96].

Since the emerging duties are not associated with specific drivers yet,
commonly cost criteria shape the objective of solving the CSP [99, 113].
Depending on the practical application, both minimizing the total amount of
daily duties as well as minimizing the total required work time are achievable
tasks. Whereby the former determines the minimum demand of employees on a
daily basis, the latter aims at an optimal duty structure by avoiding
unnecessary breaks or waiting times. Utilizing fixed costs for duties and an
hourly rate for the working time, these objectives are usually transformed
into one that minimizes the total costs [96]. Commonly, for solving the CSP a
column generation approach in combination with Lagrangian or LP-relaxation
considering a set covering or partitioning problem is utilized. Solution
approaches for crew scheduling are reviewed in detail in [113] and [99].

###  2.3 Crew rostering problem

The crew rostering (or driver rostering) is concerned with assigning
anonymized duties to specific drivers. The results are individual schedules
for every crew member, so-called crew rosters [103]. As opposed to crew
scheduling, where the foremost objective is to minimize operative costs, crew
rostering takes crew welfare, such as balancing workload and additional
individual characteristics of each crew member and efficiency objectives,
e.g., minimizing layovers and crew deadheading, into account. Complementing
the legal daily duty requirements, already respected within the CSP, further
law and labor union rules have to be considered, solving a CRP. These
additional requirements range from minimal break times between two consecutive
shifts to a maximum weekly workload for a single driver. In constructing
personalized schedules, two different kinds of crew rosters can be
distinguished, namely cyclic and non-cyclic rosters [148]. The cyclic roster
occurs to be the less sophisticated approach and is developed for a group of
drivers with similar qualifications and preferences. A regular, repeating
working pattern is established for the entirety of drivers. This pattern is
constructed as such that all legal requirements are met, and the workload is
allocated evenly. However, this roster occurs not to feature a high degree of
individuality. Non-cyclic rosters, on the other hand, offer the possibility to
develop personalized schedules for a medium to long period of time [148].
Depending on the extent to consider individual preferences and shift requests,
constructing a non-cyclic pattern requires sophisticated techniques. A
multicommodity network flow formulation is developed in [148] to deal with
both cyclic and non-cyclic rostering, also in [127] for non-cyclic rostering.
In order to deal with the complexity, (Meta-)heuristics are applied to solve
non-cyclic rostering, such as in [147], [127]. [99] and [141] cover the crew
rostering problem in their literature reviews and elaborate approaches to
solve the CRP utilizing both cyclic and non-cyclic rosters. As a first step
towards more robustness in crew rostering, [145] consider a simplified version
of rostering but incorporate possible reserve shifts to cover the absences of
drivers.

##  3 Partial Integration & Integrated approaches

The three decision problems – more precisely VSP, CSP and CRP– have been
extensively studied by scholars. Various methods have been proposed to find
optimal or close-to-optimal solutions to each of these problems [90, 99, 141].
These problems constitute consecutive phases [96] within the operational
public transport planning process. Thus, choosing a sequential approach to
solving the entirety of these problems is straightforward. In such an
approach, the output of the previous phase is used as an input for the
subsequent planning problem. However, this traditionally utilized approach may
not lead to a globally optimal solution. A slightly adjusted timetable, e.g.,
might lead to more freedom for solving the VSP and hence a lower demand for
buses. Here, the gain from consecutive steps can outweigh the loss of the
adjusted prior phase or, due to choosing an indifferent solution of a previous
step, a Pareto-efficient improvement might even be possible. As a result,
iteratively solving the three sequential phases in order to leverage knowledge
gained in every iteration can improve the overall solution. However, repeated
executions of each phase might lead to prohibitively long run times or, due to
a fixed number of iterations, to local optima. Opposed to sequential or
iterative approaches, which solve each of the problems separately, integrated
approaches solve the VSP, CSP, or CRP conjointly. As a result, superior
solutions are attainable within acceptable computation time, even for problem
instances of realistic size.

We distinguish between the integration of the first two phases (VSP \+ CSP in
the following referred to as VCSP) and the last two phases (CSP + CRP in the
following referred to as CSRP). The highest level of integration is achieved
by simultaneously considering all three decision problems (VSP \+ CSP \+ CRP
in the following referred to as VCSRP).

The number of publications for integrated solution approaches is unevenly
distributed. In contrast to the wide range of publications considering the
VCSP, there are only three approaches for the VCSRP. The main objective in
either integrated approach is usually minimizing costs – while in recent
years, additional objectives such as robustness, regularity, and fairness have
become increasingly important. Similar to publications covering the VSP only,
there exists an evident trend to modeling the underlying problem as a TSN
instead of a connection-based Network (CBN). Due to the integration of the
planning phases, many approaches use column generation and (meta-)heuristics
(such as genetic algorithms, simulated annealing, ant colony algorithms) to
solve the remaining complexity problem. More than two-thirds of the evaluated
solution approaches use real data for evaluation and thus examine the
applicability of the methods in practice. It is noteworthy that the majority
of approaches employ combinations of solution approaches instead of individual
exact or heuristic methods. Looking at the methods, special attention is paid
to column generation, as it is prevalent in the sample, as well as non-exact
heuristics that are used. The right choice of model and combination of
solution algorithms facilitates solving problem instances of realistic size.
However, within the regarded sample, only a few publications from the bus
industry solve VSP instances of realistic urban size [[,
e.g.,]]kliewer2012multiple, amberg2018robust, steinzen2010time. Many rely on
evaluation using the random benchmark instances published in [113].

Similar decision problems under consideration occur in several industries.
Three are identified as the major industries: Airline, railway, and public
buses. Regarding vehicle scheduling, similarities, as well as differences, are
evident. All three industries have the goal in common to minimize the
operational costs and utilize the least possible number of vehicles. However,
the details of either industry differ greatly. Due to high initial costs for
rolling stock and railroads, as well as long construction times for the
latter, planning in the railway industry is highly constrained by its
infrastructure. In contrast, vehicle scheduling for a public bus provider
offers more decision-making possibilities. Various existing roads can be used,
and different vehicle types offer higher degrees of freedom in planning. Given
a fixed number of vehicles, scheduling for the airline industry is the least
restricted one. Changing the route of an airplane is usually only restricted
by costs, but not by infrastructural conditions. Depending on the
preconditions of each unique industry, mathematical modeling might be more
challenging given increased infrastructural requirements. The number of
constraints correlates strongly with the model’s degrees of freedom. More
flexibility in planning leads to an increased solution space. Both the
quantity of constraints and the size of the solution space enable different
solution approaches and might lead to different expedient ways of solving the
specific planning problem. Similar to vehicle scheduling, both crew scheduling
and crew rostering share similarities but differ in detail. As previously
described, labor law and other legal provisions, as well as collective and
individual agreements, restrict the CSP and CRP within the mentioned
industries [103, 111, 148]. However, buses, e.g., only need one driver while
airplanes and trains must have a crew. Crews typically consist of more than
two members who have to fulfill specific tasks and functions, and are thus
typically planned as teams [103]. Compared to public bus transport, the
railway and airline industry possibly cover huge distances. Thus, the crew
rostering has to consider individual home bases, take lodging into account and
return each crew member to its origin at some point [142].

Most studies in our sample deal with the public bus transport industry (in
either urban or rural environments). There are some important exceptions from
other industries, especially concerning Crew Scheduling Rostering Problem
(CSRP) such as [135], [103], [111], [124] and [138] in the airline industry
and [103] as well as [87] in railway.

In the following sections, we discuss the solution approaches from the
literature concerning the pairwise integrated problems (i.e., the VCSP and the
CSRP), and the “fully” integrated problem (i.e., the VCSRP) in more detail.

##  4 Pairwise integrated optimization

###  4.1 Integrated vehicle and crew scheduling

The majority of solution approaches for the VCSP in our sample follow a column
generation scheme to generate vehicle schedules and anonymous duties for a
given timetable and corresponding service trips. The VCSP is the master
problem, and duties are generated as columns by solving the pricing problem as
a constrained shortest path problem. All approaches investigated have in
common that minimizing costs is the central objective criterion. In recent
years, further optimization objectives such as robustness [114, 78, 117, 79]
and schedule regularity [140, 81, 80] have been considered.

For the corresponding VSP, the underlying network is usually explicitly
modeled. Historically, integrated optimization approaches have focused on
using a CBN with depots and stops as nodes, and all possible connections,
including pull-ins and pull-outs, are enumerated as arcs, such as in [82],
[104], [105], [106], [101] and [102]. This approach might be most intuitive
and was used mostly in the last century. Recent network modeling approaches
shift towards a TSN where time-space nodes represent possible arrivals and
departures at a location and where only feasible connections are modeled as
arcs such as in [110], [116], [139], [81], [78], [117] and [79]. The TSN
method has the advantage that much fewer connections are included, which
reduces the model complexity tremendously – especially for larger instances.
[109] report that the number of arcs in the TSN amounts to 1-3% of all arcs in
an equivalent CBN. Thus, the problem size could be reduced significantly
without reducing the solution space because all compatible trips are
implicitly connected.

###  4.2 Integrated crew scheduling and rostering

In the airline and railway industries, crew scheduling and crew rostering are
usually considered sequentially (see [91, 120, 149, 124] since it is not yet
possible to find an optimal solution for one of the two planning steps with
current state-of-the-art technologies for realistically sized models. An
overview of the developments until 1998 for air and rail transport was
presented in [98].

Integrated planning has received increasing attention since the 2000s, with a
focus on airlines and railways. Due to the high combinatorial complexity of
integrated planning, approaches to partial or iterative integration were first
published. In [97] the number of paired personnel crews in crew scheduling is
taken into account.

Most integrated crew scheduling and crew rostering approaches deal with
airline optimization [103, 111, 124, 138] and only a few tackle the public bus
transit [[, e.g.]]xie2012integrated, xie2013column, xie2017metaheuristics,
xie2015cyclic and the railway industry [[, e.g.]]borndoerfer2014integrierte,
lin2019integrated.

An iterative method through a feedback mechanism between the CSP and CRP is
implemented in [92]. All duties are generated in the first phase, and the
number of duties is reduced by heuristics in the second phase, such that
instances with various compositions with real-world characteristics can be
solved. [111] focus on partial integration based on the aggregated TSN. In the
first step, instead of a single duty, a chain of duties is generated, taking
into account the individual activities of the crew members planned in advance.
In addition, the number of crews is also taken into account in this step
[111]. The approach can solve even instances of up to 1977 tasks, considering
188 crew members, in acceptable time ($\sim$ 15.5 minutes).

In [150] the integration problem is formulated as an integer linear program,
and a new heuristic method is developed, which is used in a search procedure
for a subtree based on a rounding strategy. A decision support system is
developed in [103] for integrated crew scheduling in the airline and railway
sector, and a general set partitioning model is formulated, and a state-of-
the-art branch and price solver is generated. In [132] and [133] a column
generation approach is used to reduce the computing time of the sub-problem.

In further research projects regarding the complete integration of the two
planning phases, meta-heuristics, in particular specialized genetic
algorithms, are successfully used to solve the integrated problem [[,
see]]souai2009genetic, chen2013integrated.

Because of lower operational costs, optimization approaches for public
transport were developed only about ten years later than in the integrated
planning for the airline and railway industry. A Bender’s decomposition
approach is used in [85], where the crew rostering was simplified in such a
way that the duty sequences are anonymous and shift and duty templates were
used instead of services. In [144] it is shown that in practice, it is often
critical to underlay shifts with concrete duties.

[121] propose a Branch-and-Price-and-Cut (BPC) algorithm for solving the CSRP
for the Taiwanese railway system with regard to standby personnel. They
compare the results with solution approaches using expert knowledge or rules
of thumb, commercial standard solvers for the associated Mixed Integer Linear
Problem (MILP) and a sequential Depth-First Search (DFS) based algorithm for
several instances reaching real-world problem sizes regarding the number of
tasks to be performed. The employed DFS first enumerates all potential duties,
then identifies the minimum required duties to cover all tasks as a set
partitioning problem, and finally solves the shift-assignment to optimality.
Only the BPC algorithm was capable of solving all instances, whereas Gurobi
and the DFS-based algorithm are only tractable for the smallest and second-
smallest instance, respectively. For the smallest instances, the BPC can
recreate the optimal solution in less time and is the only algorithm capable
of solving all problem instances.

In addition to cost minimization, younger approaches aim at optimizing for
further goals such as the maximization of fairness of the drivers’ shift
allocation and the regularity of duty rosters to increase satisfaction [[,
e.g.]]borndoerfer2017integration, quesnel2020improving).

##  5 Integrated vehicle and crew scheduling and rostering

Few publications look into integrating all three phases, all of which take up
the bus industry. [137] consider several data sets and circumstances. They use
data from the Beijing Bus group to point out the practical constraints that
derive from Chinese law and culture. These include built-in meal periods,
multi-type bus scheduling, and restricting drivers to one or two particular
buses. The authors develop an iterative sequential heuristic algorithm that
consists of three steps: Firstly, the VSP is solved with a local search based
on $n$-opt operators. Then, the CSP is solved using a tabu-search heuristic.
Finally, driver rosters are proposed to the user and can be modified through
an interface. According to the authors, it is possible to find feasible
solutions for instances up to 107 buses and 164 duties within an appropriate
time frame of some minutes. The authors report savings in vehicle costs close
to 4.5% and driver wages of approximately 9.9% when comparing with manually
built solutions.

[125] use data from a bus company in Lisbon to demonstrate their preemptive
goal programming-based heuristic approach that prioritizes the Vehicle Crew
Scheduling Problem (VCSP) over the CRP part. Their approach is able to
generate optimal solutions within a short computing time for most instances.
When considering all costs, however, some instances could not be solved within
a reasonable time limit. Their integer formulation consists of a preemptive
goal programming framework that prioritizes the integrated vehicle-crew-
scheduling goals over the driver rostering goals. The problem is first
decomposed to solve one VSP \+ CSP per day and then establish a roster for a
longer time horizon.

Two years later, [126] manage to outperform the traditional sequential
approach by integrating VSP, CSP and CRP with a Bender’s decomposition problem
formulation using a multicommodity network flow formulation, set covering and
covering-assignment elements. They tackle the integrated problem by dividing
it into a master problem that contains the VSP and CSP and a sub-problem for
the CRP. Information from the sub-problem and its dual solution are used to
find better duties for the CSP. The authors minimize vehicle and driver costs
and take into account constraints regarding roster balancing and coverage of
all daily duties. Using data from two bus companies in Portugal, their rosters
have to match predefined days-off patterns based on the requirements of these
companies. The planning horizon for rosters is seven weeks long.

All three papers, [137], [125], and [126], evaluate their proposed algorithms
on real-world instances. However, they are too small (108 to 238 timetable
trips) to represent a larger, realistic urban bus system.
In summary, public transport providers recognize the necessity to organize
their services efficiently. Because of increasing urbanization, the demand for
public transport is rising, and thus competition and the need for efficiency
in the public transport planning process rise as well. Integrating the
operational phases of VSP, CSP, and CRP gives public transport providers more
degrees of freedom and can lead to better schedules and rosters.

Our findings include that there are three forms of integrated problems that
are solved in the literature. While most authors focus on the VCSP, some
approaches consider the CSRP and a few recent publications tackle the
challenge of solving the VCSRP.

All approaches to solving the VCSRP deal with the bus industry. This might be
because crew rostering is much easier when considering only one driver, as
compared to multiple-person crews in airline or railway planning, which would
exacerbate the integration even more.

Moreover, the majority of scholars focus on minimizing costs in their
approaches. However, a few authors have considered other objectives such as
robustness (see an overview of different robustness approaches in public
transit in [108]), regularity, and fairness of schedules in recent years. This
indicates that diverse objective functions are becoming more common over time.
In a recent study, [107] showed that adding a robustness objective to the
VCSRP model of [126] does not take much additional computational time in this
application, which is an interesting result. Many standard combinatorial
optimization models are used for decision problems, including the minimum cost
flow problem and its various special cases (e.g., the resource-constrained
shortest path problem, the multicommodity flow problem, and the linear
assignment problem). Set partitioning formulations are often used to solve the
CSP. Some authors prefer the easier set covering formulation where crew
members become passengers in the case of overlapping assignments. The TSN
formulation is a powerful tool to reduce network size and thus computing time
compared to Connection-Based Network (CBN), where all deadhead trips are
explicitly modeled.

In terms of solution techniques, column generation stands out as the most
powerful operations research method to solve integrated decision problems. It
is usually accompanied by relaxation techniques. Lagrangian relaxation seems
to work best for quickly finding reasonable bounds for the integer solution.
Branch-and-bound and branch-and-price techniques are popular to find feasible
integer solutions. Heuristics and meta-heuristics are used to speed up the
solution process. They include tabu-search, simulated annealing, ant colony
algorithms, genetic algorithms, and smaller-scale greedy heuristics. In
conclusion, we can say that there exists no single best approach to integrated
solve the VSP, CSP, and CRP. Which solution approach yields the best results
is always subject to the specific problem settings. Among others, it is
important to take into account the source and nature of data that is used, the
size of the instances, and the relevant constraints. Every new approach can be
a game-changer for some situations, while in others, it might prove less
useful.

##  6 Future Research

For future research, we propose to focus on further integrating the public
transport planning process. Since there are only three approaches towards a
threefold integration of all operational phases and the first results are
promising, more effort is needed in this direction. In addition, strategic
decision problems may also be included in integrated planning. In the
literature, the first approaches towards integrating timetabling or vehicle
routing with vehicle scheduling can be found. The long-term aim of an
integrated public transport planning process where all sub-problems are solved
simultaneously and thus making it possible to use all degrees of freedom is
still a long way off.

At the same time, the existing approaches should be enhanced in order to make
them suitable for real-world use with larger instances and more complex data
sets, such as public transport providers in larger cities. Furthermore,
schedule robustness, regularity, crew or driver preferences, and fairness as
optimization objectives should be examined more closely. There are some first
steps taken in individual publications in integrated scheduling. The crew
scheduling literature offers many more starting points that could be
incorporated into integrated planning as well. More publications that
explicitly deal with these topics are desirable.

## References

  * [1] Roberto F Abenoza, Oded Cats and Yusak O Susilo  “Travel satisfaction with public transport: Determinants, user classes, regional disparities and their evolution”  In _Transportation Research Part A: Policy and Practice_ 95 Elsevier, 2017, pp. 64–84
  * [2] Jonathan D Adler  “Routing and scheduling of electric and alternative-fuel vehicles”, 2014
  * [3] Bastian Amberg, Boris Amberg and Natalia Kliewer  “Increasing delay-tolerance of vehicle and crew schedules in public transport by sequential, partial-integrated and integrated approaches”  In _Procedia-Social and Behavioral Sciences_ 20, 2011, pp. 292–301
  * [4] Bastian Amberg, Natalia Kliewer and Michael Beck  “Robuste Effizienz bei der Einsatzplanung für Bus und Fahrer: -Aktuelle Entwicklungen von Optimierungskomponenten für verspätungstolerante Umlauf-und Dienstplanung im Busverkehr”  In _Der Nahverkehr_ 30.1, 2012, pp. 15–19
  * [5] Bastian Amberg, Boris Amberg and Natalia Kliewer  “Robust Efficiency in Urban Public Transportation: Minimizing Delay Propagation in Cost-Efficient Bus and Driver Schedules”  In _Transportation Science_ 53.1 Institute for Operations Researchthe Management Sciences (INFORMS), 2018, pp. 89–112  DOI: 10.1287/trsc.2017.0757
  * [6] Boris Amberg, Bastian Amberg and Natalia Kliewer  “Approaches for increasing the similarity of resource schedules in public transport”  In _Procedia-Social and Behavioral Sciences_ 20, 2011, pp. 836–845
  * [7] Michael Ball, Lawrence Bodin and Robert Dial  “A matching based heuristic for scheduling mass transit crews and vehicles”  In _Transportation Science_ 17.1, 1983, pp. 4–31
  * [8] Alan A Bertossi, Paolo Carraresi and Giorgio Gallo  “On some matching problems arising in vehicle scheduling models”  In _Networks_ 17.3 Wiley Online Library, 1987, pp. 271–281
  * [9] Lawrence Bodin and Bruce Golden  “Classification in vehicle routing and scheduling”  In _Networks_ 11.2 Wiley Online Library, 1981, pp. 97–108
  * [10] Ralf Borndörfer, Martin Grötschel and Andreas Löbel  “Duty scheduling in public transit”, 2001
  * [11] Ralf Borndörfer et al.  “Rapid Branching”  In _Public Transport_ 5.1-2 Springer Berlin Heidelberg, 2012, pp. 3–23
  * [12] Ralf Borndörfer et al.  “Integrierte Dienst-und Dienstreihenfolgeplanung zur Erhöhung der Fahrerzufriedenheit”, 2014
  * [13] Ralf Borndörfer et al.  “Duty rostering in public transport-facing preferences, fairness, and fatigue”, 2015
  * [14] Ralf Borndörfer, Christof Schulz, Stephan Seidl and Steffen Weider  “Integration of duty scheduling and rostering to increase driver satisfaction”  In _Public Transport_ 9.1-2, 2017, pp. 177–191  DOI: 10.1007/s12469-017-0153-3
  * [15] Stefan Bunte and Natalia Kliewer  “An overview on vehicle scheduling models”  In _Public Transport_ 1.4 Springer, 2009, pp. 299–317  DOI: 10.1007/s12469-010-0018-5
  * [16] Alberto Caprara et al.  “Solution of large-scale railway crew planning problems: The Italian experience”  In _Computer-aided Systems in Public Transport_ Springer, 1999, pp. 1–18  DOI: 10.1007/978-3-642-85970-0\\_1
  * [17] Alberto Caprara, Michele Monaci and Paolo Toth  “A global method for crew planning in railway applications”  In _Computer-aided Systems in Public Transport_ Springer, 2001, pp. 17–36  DOI: 10.1007/978-3-642-56423-9\\_2
  * [18] Oded Cats  “The robustness value of public transport development plans”  In _Journal of Transport Geography_ 51 Elsevier, 2016, pp. 236–246
  * [19] Chiu-Hung Chen, Tung-Kuan Liu and Jyh-Horng Chou  “Integrated short-haul airline crew scheduling using multiobjective optimization genetic algorithms”  In _IEEE Transactions On Systems, Man, and Cybernetics: Systems_ 43.5 IEEE, 2013, pp. 1077–1090
  * [20] Joachim R Daduna and José M Pinto Paixão  “Vehicle scheduling for public mass transit—an overview”  In _Computer-aided transit scheduling_ Springer, 1995, pp. 76–90
  * [21] Guy Desaulniers and Mark D Hickman  “Public transit”  In _Handbooks in operations research and management science_ 14 Elsevier, 2007, pp. 69–127
  * [22] Andreas T. Ernst et al.  “An integrated optimization model for train crew management”  In _Annals of Operations Research_ 108.1-4, 2001, pp. 211–224  URL: https://link.springer.com/article/10.1023/A:1016019314196
  * [23] Andreas T. Ernst et al.  “Rail crew scheduling and rostering optimization algorithms”  In _Computer-aided Systems in Public Transport_ Springer, 2001, pp. 53–71  DOI: 10.1007/978-3-642-56423-9\\_4
  * [24] Andreas T. Ernst, Houyuan Jiang, Mohan Krishnamoorthy and David Sier  “Staff scheduling and rostering: A review of applications, methods and models”  In _European Journal of Operational Research_ 153.1, 2004, pp. 3–27
  * [25] Matteo Fischetti, Silvano Martello and Paolo Toth  “The fixed job schedule problem with spread-time constraints”  In _Operations Research_ 35.6 INFORMS, 1987, pp. 849–858
  * [26] Richard Freling, Albert P.. Wagelmans and José Paixão  “An overview of models and techniques for integrating vehicle and crew scheduling”  In _Computer-aided Systems in Public Transport_ 471 Springer, 1999, pp. 441–460
  * [27] Richard Freling, Dennis Huisman and Albert P.. Wagelmans  “Applying an integrated approach to vehicle and crew scheduling in practice”  In _Computer-aided Systems in Public Transport_ Springer, 2001, pp. 73–90  DOI: 10.1007/978-3-642-56423-9\\_5
  * [28] Richard Freling, Dennis Huisman and Albert P.. Wagelmans  “Models and algorithms for integration of vehicle and crew scheduling”  In _Journal of Scheduling_ 6.1, 2003, pp. 63–85
  * [29] Richard Freling, Ramon M. Lentink and Albert P.. Wagelmans  “A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm”  In _Annals of Operations Research_ 127.1-4, 2004, pp. 203–222
  * [30] Christian Friberg and Knut Haase  “An exact branch and cut algorithm for the vehicle and crew scheduling problem”  In _Computer-aided Systems in Public Transport_ Springer, 1999, pp. 63–80  DOI: 10.1007/978-3-642-85970-0\\_4
  * [31] A. Gaffi and M. Nonato  “An integrated approach to ex-urban crew and vehicle scheduling”  In _Computer-aided Systems in Public Transport_ Springer, 1999, pp. 103–128
  * [32] Liping Ge et al.  “Revisiting the richness of integrated vehicle and crew scheduling”  In _Public Transport_ Springer, 2022, pp. 1–27  DOI: 10.1007/s12469-022-00292-6
  * [33] Liping Ge, Stefan Voß and Lin Xie  “Robustness and disturbances in public transport”  In _Public Transport_ 14.1 Springer, 2022, pp. 191–261
  * [34] Vitali Gintner, Natalia Kliewer and Leena Suhl  “Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice”  In _OR Spectrum_ 27.4 Springer, 2005, pp. 507–523
  * [35] Vitali Gintner, Natalia Kliewer and Leena Suhl  “A crew scheduling approach for public transit enhanced with aspects from vehicle scheduling”  In _Computer-aided Systems in Public Transport_ Springer, 2008, pp. 25–42  DOI: 10.1007/978-3-540-73312-6\\_2
  * [36] Yufeng Guo, Taieb Mellouli, Leena Suhl and Markus P. Thiel  “A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases”  In _European Journal of Operational Research_ 171.3, 2006, pp. 1169–1181
  * [37] Robert Hrelja, Tom Rye and Caroline Mullen  “Partnerships between operators and public transport authorities. Working practices in relational contracting and collaborative partnerships”  In _Transportation Research Part A: Policy and Practice_ 116 Elsevier, 2018, pp. 327–338
  * [38] Dennis Huisman  “Integrated and dynamic vehicle and crew scheduling: Geïntegreerde en dynamische voertuig- en personeelsplanning: Zugl.: Rotterdam, Erasmus Univ., Diss., 2003” 325, Research series / Erasmus University Rotterdam  Amsterdam: Thela Thesis, 2004
  * [39] Dennis Huisman, Richard Freling and Albert PM Wagelmans  “A robust solution approach to the dynamic vehicle scheduling problem”  In _Transportation Science_ 38.4 INFORMS, 2004, pp. 447–458  DOI: 10.1287/trsc.1030.0069
  * [40] Omar J. Ibarra-Rojas, F. Delgado, R. Giesen and J.. Muñoz  “Planning, operation, and control of bus transport systems: A literature review”  In _Transportation Research Part B: Methodological_ 77, 2015, pp. 38–75  DOI: 10.1016/j.trb.2015.03.002
  * [41] Andras Keri and Knut Haase  “Simultaneous Vehicle and Crew Scheduling with Trip Shifting”  In _OPERATIONS RESEARCH PROCEEDINGS 2007_ , Operations Research Proceedings  Springer-Verlag Berlin, 2008, pp. 467–472
  * [42] Natalia Kliewer, Taieb Mellouli and Leena Suhl  “A time–space network based exact optimization model for multi-depot bus scheduling”  In _European journal of operational research_ 175.3 Elsevier, 2006, pp. 1616–1627  DOI: 10.1016/j.ejor.2005.02.030
  * [43] Natalia Kliewer, Bastian Amberg and Boris Amberg  “Multiple depot vehicle and crew scheduling with time windows for scheduled trips”  In _Public Transport_ 3.3, 2012, pp. 213–244  DOI: 10.1007/s12469-011-0049-6
  * [44] Stefan Kramkowski, Natalia Kliewer and Christian Meier  “Increasing delay-tolerance of vehicle schedules in public bus transport”  In _Proceedings of the Metaheuristic International Conference VIII_ , 2009  Hamburg Germany  DOI: 10.1016/J.SBSPRO.2011.08.035
  * [45] Chi-Kong Lee and Chao-Hui Chen  “Scheduling of train driver for Taiwan railway administration”  In _Journal of Eastern Asia Society of Transportation Studies_ 5, 2003, pp. 292–306
  * [46] Dung-Ying Lin and Meng-Rung Tsai  “Integrated crew scheduling and roster problem for trainmasters of passenger railway transportation”  In _IEEE Access_ 7 IEEE, 2019, pp. 27362–27375
  * [47] Todd Litman  “The hidden traffic safety solution: public transportation”, 2016
  * [48] Andreas Löbel  “Solving large-scale multiple-depot vehicle scheduling problems”  In _Computer-Aided Transit Scheduling_ Springer, 1999, pp. 193–220  DOI: 10.1007/978-3-642-85970-0\\_10
  * [49] Claude P. Medard and Nidhi Sawhney  “Airline crew scheduling from planning to operations”  In _European Journal of Operational Research_ 183.3, 2007, pp. 1013–1027  DOI: 10.1016/j.ejor.2005.12.046
  * [50] Marta Mesquita et al.  “A new model for the integrated vehicle-crew-rostering problem and a computational study on rosters”  In _Journal of Scheduling_ 14.4, 2011, pp. 319–334  DOI: 10.1007/s10951-010-0195-8
  * [51] Marta Mesquita, Margarida Moz, Ana Paias and Margarida Pato  “A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern”  In _European Journal of Operational Research_ 229.2, 2013, pp. 318–331  DOI: 10.1016/j.ejor.2013.02.055
  * [52] Marta Mesquita, Margarida Moz, Ana Paias and Margarida Pato  “A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off pattern”  In _European Journal of Operational Research_ 245.2 Elsevier, 2015, pp. 423–437
  * [53] Marc Naumann, Leena Suhl and Stefan Kramkowski  “A stochastic programming approach for robust vehicle scheduling in public bus transport”  In _Procedia Social and Behavioral Sciences_ 20 Elsevier, 2011, pp. 826–835  DOI: 10.1016/j.sbspro.2011.08.091
  * [54] Ann-Sophie Pepin, Guy Desaulniers, Alain Hertz and Dennis Huisman  “A comparison of five heuristics for the multiple depot vehicle scheduling problem”  In _Journal of Scheduling_ 12.1, 2009, pp. 17–30  DOI: 10.1007/s10951-008-0072-x
  * [55] Frédéric Quesnel, Guy Desaulniers and François Soumis  “Improving air crew rostering by considering crew preferences in the crew pairing problem”  In _Transportation Science_ 54.1 INFORMS, 2020, pp. 97–114
  * [56] Josephine Reuer, Natalia Kliewer and Lena Wolbeck  “The Electric Vehicle Scheduling Problem A study on time-space network based and heuristic solution”  In _Proceedings of the Conference on Advanced Systems in Public Transport_ , 2015
  * [57] Mohammed Saddoune, Guy Desaulniers, Issmail Elhallaoui and François Soumis  “Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods”  In _European Journal of Operational Research_ 212.3, 2011, pp. 445–454  DOI: 10.1016/j.ejor.2011.02.009
  * [58] Mohammed Saddoune, Guy Desaulniers, Issmail Elhallaoui and François Soumis  “Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation”  In _Transportation Science_ 46.1, 2012, pp. 39–55  DOI: 10.1287/trsc.1110.0379
  * [59] JL Saha  “An algorithm for bus scheduling problems”  In _Journal of the Operational Research Society_ 21.4 Springer, 1970, pp. 463–474
  * [60] Rivi Sandhu and Diego Klabjan  “Integrated Airline Fleeting and Crew-Pairing Decisions”  In _Operations Research_ 55.3, 2007, pp. 439–456  DOI: 10.1287/opre.1070.0395
  * [61] David Schrank, Tim Lomax and Bill Eisele  “2019 urban mobility report”  In _Texas Transportation Institute. Available: http://mobility. tamu.edu/ums/report_ , 2019
  * [62] Yindong Shen and Jiahong Xia  “Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation”  In _International Transactions in Operational Research_ 16.2, 2009, pp. 227–242  DOI: 10.1111/j.1475-3995.2009.00673.x
  * [63] Nadia Souai and Jacques Teghem  “Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem”  In _European Journal of Operational Research_ 199.3, 2009, pp. 674–683  DOI: 10.1016/j.ejor.2007.10.065
  * [64] Ingmar Steinzen, Leena Suhl and Natalia Kliewer  “Branching strategies to improve regularity of crew schedules in ex-urban public transit”  In _OR Spectrum_ 31.4, 2009, pp. 727–743
  * [65] Ingmar Steinzen, Vitali Gintner, Leena Suhl and Natalia Kliewer  “A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots”  In _Transportation Science_ 44.3 INFORMS, 2010, pp. 367–382  URL: http://www.jstor.org/stable/25769505
  * [66] Jorne van den Bergh et al.  “Personnel scheduling: A literature review”  In _European Journal of Operational Research_ 226.3, 2013, pp. 367–385
  * [67] Xin Wen, Xuting Sun, Yige Sun and Xiaohang Yue  “Airline crew scheduling: Models and algorithms”  In _Transportation research part E: logistics and transportation review_ 149 Elsevier, 2021, pp. 102304
  * [68] Lin Xie  “Decision Support for Crew Rostering in Public Transit: Web-Based Optimization System for Cyclic and Non-Cyclic Rostering”  Springer, 2014
  * [69] Lin Xie  “Decision Support for Crew Rostering in Public Transit – Web-based Optimization System for Cyclic and Non-Cyclic Rostering”  Wiesbaden: Springer Fachmedien Wiesbaden, 2015  DOI: 10.1007/978-3-658-08167-6
  * [70] Lin Xie and Leena Suhl  “Cyclic and non-cyclic crew rostering problems in public bus transit”  In _OR Spectrum_ 37.1, 2015, pp. 99–136  DOI: 10.1007/s00291-014-0364-9
  * [71] Lin Xie, Natalia Kliewer and Leena Suhl  “Integrated Driver Rostering Problem in Public Bus Transit”  In _Procedia-Social and Behavioral Sciences_ 54, 2012, pp. 656–665  DOI: 10.1016/j.sbspro.2012.09.783
  * [72] Lin Xie, Natalia Kliewer and Leena Suhl  “A column generation approach for the cyclic and non-cyclic bus driver rostering problem.”, 2013
  * [73] Lin Xie, Marius Merschformann, Natalia Kliewer and Leena Suhl  “Metaheuristics approach for solving personalized crew rostering problem in public bus transit”  In _Journal of Heuristics_ 23.5, 2017, pp. 321–347  DOI: 10.1007/s10732-017-9348-7
  * [74] Tallys H. Yunes, Arnaldo V. Moura and Cid C. Souza  “Hybrid Column Generation Approaches for Urban Transit Crew Management Problems”  In _Transportation Science_ 39.2, 2005, pp. 273–288  DOI: 10.1287/trsc.1030.0078
  * [75] F.. Zeghal and M. Minoux  “Modeling and solving a Crew Assignment Problem in air transportation”  In _European Journal of Operational Research_ 175.1, 2006, pp. 187–209  DOI: 10.1016/j.ejor.2004.11.028

## References

  * [76] Roberto F Abenoza, Oded Cats and Yusak O Susilo  “Travel satisfaction with public transport: Determinants, user classes, regional disparities and their evolution”  In _Transportation Research Part A: Policy and Practice_ 95 Elsevier, 2017, pp. 64–84
  * [77] Jonathan D Adler  “Routing and scheduling of electric and alternative-fuel vehicles”, 2014
  * [78] Bastian Amberg, Boris Amberg and Natalia Kliewer  “Increasing delay-tolerance of vehicle and crew schedules in public transport by sequential, partial-integrated and integrated approaches”  In _Procedia-Social and Behavioral Sciences_ 20, 2011, pp. 292–301
  * [79] Bastian Amberg, Boris Amberg and Natalia Kliewer  “Robust Efficiency in Urban Public Transportation: Minimizing Delay Propagation in Cost-Efficient Bus and Driver Schedules”  In _Transportation Science_ 53.1 Institute for Operations Researchthe Management Sciences (INFORMS), 2018, pp. 89–112  DOI: 10.1287/trsc.2017.0757
  * [80] Bastian Amberg, Natalia Kliewer and Michael Beck  “Robuste Effizienz bei der Einsatzplanung für Bus und Fahrer: -Aktuelle Entwicklungen von Optimierungskomponenten für verspätungstolerante Umlauf-und Dienstplanung im Busverkehr”  In _Der Nahverkehr_ 30.1, 2012, pp. 15–19
  * [81] Boris Amberg, Bastian Amberg and Natalia Kliewer  “Approaches for increasing the similarity of resource schedules in public transport”  In _Procedia-Social and Behavioral Sciences_ 20, 2011, pp. 836–845
  * [82] Michael Ball, Lawrence Bodin and Robert Dial  “A matching based heuristic for scheduling mass transit crews and vehicles”  In _Transportation Science_ 17.1, 1983, pp. 4–31
  * [83] Alan A Bertossi, Paolo Carraresi and Giorgio Gallo  “On some matching problems arising in vehicle scheduling models”  In _Networks_ 17.3 Wiley Online Library, 1987, pp. 271–281
  * [84] Lawrence Bodin and Bruce Golden  “Classification in vehicle routing and scheduling”  In _Networks_ 11.2 Wiley Online Library, 1981, pp. 97–108
  * [85] Ralf Borndörfer et al.  “Integrierte Dienst-und Dienstreihenfolgeplanung zur Erhöhung der Fahrerzufriedenheit”, 2014
  * [86] Ralf Borndörfer, Martin Grötschel and Andreas Löbel  “Duty scheduling in public transit”, 2001
  * [87] Ralf Borndörfer et al.  “Rapid Branching”  In _Public Transport_ 5.1-2 Springer Berlin Heidelberg, 2012, pp. 3–23
  * [88] Ralf Borndörfer et al.  “Duty rostering in public transport-facing preferences, fairness, and fatigue”, 2015
  * [89] Ralf Borndörfer, Christof Schulz, Stephan Seidl and Steffen Weider  “Integration of duty scheduling and rostering to increase driver satisfaction”  In _Public Transport_ 9.1-2, 2017, pp. 177–191  DOI: 10.1007/s12469-017-0153-3
  * [90] Stefan Bunte and Natalia Kliewer  “An overview on vehicle scheduling models”  In _Public Transport_ 1.4 Springer, 2009, pp. 299–317  DOI: 10.1007/s12469-010-0018-5
  * [91] Alberto Caprara et al.  “Solution of large-scale railway crew planning problems: The Italian experience”  In _Computer-aided Systems in Public Transport_ Springer, 1999, pp. 1–18  DOI: 10.1007/978-3-642-85970-0\\_1
  * [92] Alberto Caprara, Michele Monaci and Paolo Toth  “A global method for crew planning in railway applications”  In _Computer-aided Systems in Public Transport_ Springer, 2001, pp. 17–36  DOI: 10.1007/978-3-642-56423-9\\_2
  * [93] Oded Cats  “The robustness value of public transport development plans”  In _Journal of Transport Geography_ 51 Elsevier, 2016, pp. 236–246
  * [94] Chiu-Hung Chen, Tung-Kuan Liu and Jyh-Horng Chou  “Integrated short-haul airline crew scheduling using multiobjective optimization genetic algorithms”  In _IEEE Transactions On Systems, Man, and Cybernetics: Systems_ 43.5 IEEE, 2013, pp. 1077–1090
  * [95] Joachim R Daduna and José M Pinto Paixão  “Vehicle scheduling for public mass transit—an overview”  In _Computer-aided transit scheduling_ Springer, 1995, pp. 76–90
  * [96] Guy Desaulniers and Mark D Hickman  “Public transit”  In _Handbooks in operations research and management science_ 14 Elsevier, 2007, pp. 69–127
  * [97] Andreas T. Ernst et al.  “An integrated optimization model for train crew management”  In _Annals of Operations Research_ 108.1-4, 2001, pp. 211–224  URL: https://link.springer.com/article/10.1023/A:1016019314196
  * [98] Andreas T. Ernst et al.  “Rail crew scheduling and rostering optimization algorithms”  In _Computer-aided Systems in Public Transport_ Springer, 2001, pp. 53–71  DOI: 10.1007/978-3-642-56423-9\\_4
  * [99] Andreas T. Ernst, Houyuan Jiang, Mohan Krishnamoorthy and David Sier  “Staff scheduling and rostering: A review of applications, methods and models”  In _European Journal of Operational Research_ 153.1, 2004, pp. 3–27
  * [100] Matteo Fischetti, Silvano Martello and Paolo Toth  “The fixed job schedule problem with spread-time constraints”  In _Operations Research_ 35.6 INFORMS, 1987, pp. 849–858
  * [101] Richard Freling, Dennis Huisman and Albert P.. Wagelmans  “Applying an integrated approach to vehicle and crew scheduling in practice”  In _Computer-aided Systems in Public Transport_ Springer, 2001, pp. 73–90  DOI: 10.1007/978-3-642-56423-9\\_5
  * [102] Richard Freling, Dennis Huisman and Albert P.. Wagelmans  “Models and algorithms for integration of vehicle and crew scheduling”  In _Journal of Scheduling_ 6.1, 2003, pp. 63–85
  * [103] Richard Freling, Ramon M. Lentink and Albert P.. Wagelmans  “A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm”  In _Annals of Operations Research_ 127.1-4, 2004, pp. 203–222
  * [104] Richard Freling, Albert P.. Wagelmans and José Paixão  “An overview of models and techniques for integrating vehicle and crew scheduling”  In _Computer-aided Systems in Public Transport_ 471 Springer, 1999, pp. 441–460
  * [105] Christian Friberg and Knut Haase  “An exact branch and cut algorithm for the vehicle and crew scheduling problem”  In _Computer-aided Systems in Public Transport_ Springer, 1999, pp. 63–80  DOI: 10.1007/978-3-642-85970-0\\_4
  * [106] A. Gaffi and M. Nonato  “An integrated approach to ex-urban crew and vehicle scheduling”  In _Computer-aided Systems in Public Transport_ Springer, 1999, pp. 103–128
  * [107] Liping Ge et al.  “Revisiting the richness of integrated vehicle and crew scheduling”  In _Public Transport_ Springer, 2022, pp. 1–27  DOI: 10.1007/s12469-022-00292-6
  * [108] Liping Ge, Stefan Voß and Lin Xie  “Robustness and disturbances in public transport”  In _Public Transport_ 14.1 Springer, 2022, pp. 191–261
  * [109] Vitali Gintner, Natalia Kliewer and Leena Suhl  “Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice”  In _OR Spectrum_ 27.4 Springer, 2005, pp. 507–523
  * [110] Vitali Gintner, Natalia Kliewer and Leena Suhl  “A crew scheduling approach for public transit enhanced with aspects from vehicle scheduling”  In _Computer-aided Systems in Public Transport_ Springer, 2008, pp. 25–42  DOI: 10.1007/978-3-540-73312-6\\_2
  * [111] Yufeng Guo, Taieb Mellouli, Leena Suhl and Markus P. Thiel  “A partially integrated airline crew scheduling approach with time-dependent crew capacities and multiple home bases”  In _European Journal of Operational Research_ 171.3, 2006, pp. 1169–1181
  * [112] Robert Hrelja, Tom Rye and Caroline Mullen  “Partnerships between operators and public transport authorities. Working practices in relational contracting and collaborative partnerships”  In _Transportation Research Part A: Policy and Practice_ 116 Elsevier, 2018, pp. 327–338
  * [113] Dennis Huisman  “Integrated and dynamic vehicle and crew scheduling: Geïntegreerde en dynamische voertuig- en personeelsplanning: Zugl.: Rotterdam, Erasmus Univ., Diss., 2003” 325, Research series / Erasmus University Rotterdam  Amsterdam: Thela Thesis, 2004
  * [114] Dennis Huisman, Richard Freling and Albert PM Wagelmans  “A robust solution approach to the dynamic vehicle scheduling problem”  In _Transportation Science_ 38.4 INFORMS, 2004, pp. 447–458  DOI: 10.1287/trsc.1030.0069
  * [115] Omar J. Ibarra-Rojas, F. Delgado, R. Giesen and J.. Muñoz  “Planning, operation, and control of bus transport systems: A literature review”  In _Transportation Research Part B: Methodological_ 77, 2015, pp. 38–75  DOI: 10.1016/j.trb.2015.03.002
  * [116] Andras Keri and Knut Haase  “Simultaneous Vehicle and Crew Scheduling with Trip Shifting”  In _OPERATIONS RESEARCH PROCEEDINGS 2007_ , Operations Research Proceedings  Springer-Verlag Berlin, 2008, pp. 467–472
  * [117] Natalia Kliewer, Bastian Amberg and Boris Amberg  “Multiple depot vehicle and crew scheduling with time windows for scheduled trips”  In _Public Transport_ 3.3, 2012, pp. 213–244  DOI: 10.1007/s12469-011-0049-6
  * [118] Natalia Kliewer, Taieb Mellouli and Leena Suhl  “A time–space network based exact optimization model for multi-depot bus scheduling”  In _European journal of operational research_ 175.3 Elsevier, 2006, pp. 1616–1627  DOI: 10.1016/j.ejor.2005.02.030
  * [119] Stefan Kramkowski, Natalia Kliewer and Christian Meier  “Increasing delay-tolerance of vehicle schedules in public bus transport”  In _Proceedings of the Metaheuristic International Conference VIII_ , 2009  Hamburg Germany  DOI: 10.1016/J.SBSPRO.2011.08.035
  * [120] Chi-Kong Lee and Chao-Hui Chen  “Scheduling of train driver for Taiwan railway administration”  In _Journal of Eastern Asia Society of Transportation Studies_ 5, 2003, pp. 292–306
  * [121] Dung-Ying Lin and Meng-Rung Tsai  “Integrated crew scheduling and roster problem for trainmasters of passenger railway transportation”  In _IEEE Access_ 7 IEEE, 2019, pp. 27362–27375
  * [122] Todd Litman  “The hidden traffic safety solution: public transportation”, 2016
  * [123] Andreas Löbel  “Solving large-scale multiple-depot vehicle scheduling problems”  In _Computer-Aided Transit Scheduling_ Springer, 1999, pp. 193–220  DOI: 10.1007/978-3-642-85970-0\\_10
  * [124] Claude P. Medard and Nidhi Sawhney  “Airline crew scheduling from planning to operations”  In _European Journal of Operational Research_ 183.3, 2007, pp. 1013–1027  DOI: 10.1016/j.ejor.2005.12.046
  * [125] Marta Mesquita et al.  “A new model for the integrated vehicle-crew-rostering problem and a computational study on rosters”  In _Journal of Scheduling_ 14.4, 2011, pp. 319–334  DOI: 10.1007/s10951-010-0195-8
  * [126] Marta Mesquita, Margarida Moz, Ana Paias and Margarida Pato  “A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern”  In _European Journal of Operational Research_ 229.2, 2013, pp. 318–331  DOI: 10.1016/j.ejor.2013.02.055
  * [127] Marta Mesquita, Margarida Moz, Ana Paias and Margarida Pato  “A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off pattern”  In _European Journal of Operational Research_ 245.2 Elsevier, 2015, pp. 423–437
  * [128] Marc Naumann, Leena Suhl and Stefan Kramkowski  “A stochastic programming approach for robust vehicle scheduling in public bus transport”  In _Procedia Social and Behavioral Sciences_ 20 Elsevier, 2011, pp. 826–835  DOI: 10.1016/j.sbspro.2011.08.091
  * [129] Ann-Sophie Pepin, Guy Desaulniers, Alain Hertz and Dennis Huisman  “A comparison of five heuristics for the multiple depot vehicle scheduling problem”  In _Journal of Scheduling_ 12.1, 2009, pp. 17–30  DOI: 10.1007/s10951-008-0072-x
  * [130] Frédéric Quesnel, Guy Desaulniers and François Soumis  “Improving air crew rostering by considering crew preferences in the crew pairing problem”  In _Transportation Science_ 54.1 INFORMS, 2020, pp. 97–114
  * [131] Josephine Reuer, Natalia Kliewer and Lena Wolbeck  “The Electric Vehicle Scheduling Problem A study on time-space network based and heuristic solution”  In _Proceedings of the Conference on Advanced Systems in Public Transport_ , 2015
  * [132] Mohammed Saddoune, Guy Desaulniers, Issmail Elhallaoui and François Soumis  “Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods”  In _European Journal of Operational Research_ 212.3, 2011, pp. 445–454  DOI: 10.1016/j.ejor.2011.02.009
  * [133] Mohammed Saddoune, Guy Desaulniers, Issmail Elhallaoui and François Soumis  “Integrated Airline Crew Pairing and Crew Assignment by Dynamic Constraint Aggregation”  In _Transportation Science_ 46.1, 2012, pp. 39–55  DOI: 10.1287/trsc.1110.0379
  * [134] JL Saha  “An algorithm for bus scheduling problems”  In _Journal of the Operational Research Society_ 21.4 Springer, 1970, pp. 463–474
  * [135] Rivi Sandhu and Diego Klabjan  “Integrated Airline Fleeting and Crew-Pairing Decisions”  In _Operations Research_ 55.3, 2007, pp. 439–456  DOI: 10.1287/opre.1070.0395
  * [136] David Schrank, Tim Lomax and Bill Eisele  “2019 urban mobility report”  In _Texas Transportation Institute. Available: http://mobility. tamu.edu/ums/report_ , 2019
  * [137] Yindong Shen and Jiahong Xia  “Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation”  In _International Transactions in Operational Research_ 16.2, 2009, pp. 227–242  DOI: 10.1111/j.1475-3995.2009.00673.x
  * [138] Nadia Souai and Jacques Teghem  “Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem”  In _European Journal of Operational Research_ 199.3, 2009, pp. 674–683  DOI: 10.1016/j.ejor.2007.10.065
  * [139] Ingmar Steinzen, Vitali Gintner, Leena Suhl and Natalia Kliewer  “A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots”  In _Transportation Science_ 44.3 INFORMS, 2010, pp. 367–382  URL: http://www.jstor.org/stable/25769505
  * [140] Ingmar Steinzen, Leena Suhl and Natalia Kliewer  “Branching strategies to improve regularity of crew schedules in ex-urban public transit”  In _OR Spectrum_ 31.4, 2009, pp. 727–743
  * [141] Jorne van den Bergh et al.  “Personnel scheduling: A literature review”  In _European Journal of Operational Research_ 226.3, 2013, pp. 367–385
  * [142] Xin Wen, Xuting Sun, Yige Sun and Xiaohang Yue  “Airline crew scheduling: Models and algorithms”  In _Transportation research part E: logistics and transportation review_ 149 Elsevier, 2021, pp. 102304
  * [143] Lin Xie  “Decision Support for Crew Rostering in Public Transit: Web-Based Optimization System for Cyclic and Non-Cyclic Rostering”  Springer, 2014
  * [144] Lin Xie  “Decision Support for Crew Rostering in Public Transit – Web-based Optimization System for Cyclic and Non-Cyclic Rostering”  Wiesbaden: Springer Fachmedien Wiesbaden, 2015  DOI: 10.1007/978-3-658-08167-6
  * [145] Lin Xie, Natalia Kliewer and Leena Suhl  “Integrated Driver Rostering Problem in Public Bus Transit”  In _Procedia-Social and Behavioral Sciences_ 54, 2012, pp. 656–665  DOI: 10.1016/j.sbspro.2012.09.783
  * [146] Lin Xie, Natalia Kliewer and Leena Suhl  “A column generation approach for the cyclic and non-cyclic bus driver rostering problem.”, 2013
  * [147] Lin Xie, Marius Merschformann, Natalia Kliewer and Leena Suhl  “Metaheuristics approach for solving personalized crew rostering problem in public bus transit”  In _Journal of Heuristics_ 23.5, 2017, pp. 321–347  DOI: 10.1007/s10732-017-9348-7
  * [148] Lin Xie and Leena Suhl  “Cyclic and non-cyclic crew rostering problems in public bus transit”  In _OR Spectrum_ 37.1, 2015, pp. 99–136  DOI: 10.1007/s00291-014-0364-9
  * [149] Tallys H. Yunes, Arnaldo V. Moura and Cid C. Souza  “Hybrid Column Generation Approaches for Urban Transit Crew Management Problems”  In _Transportation Science_ 39.2, 2005, pp. 273–288  DOI: 10.1287/trsc.1030.0078
  * [150] F.. Zeghal and M. Minoux  “Modeling and solving a Crew Assignment Problem in air transportation”  In _European Journal of Operational Research_ 175.1, 2006, pp. 187–209  DOI: 10.1016/j.ejor.2004.11.028


# Pre-Trained Language Models Augmented with Synthetic Scanpaths for Natural
Language Understanding

Shuwen Deng1, Paul Prasse1, David R. Reich1, Tobias Scheffer1, Lena A.
Jäger1,2
1 Department of Computer Science, University of Potsdam, Germany
2 Department of Computational Linguistics, University of Zurich, Switzerland
{deng, prasse, david.reich<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

Human gaze data offer cognitive information that reflects natural language
comprehension. Indeed, augmenting language models with human scanpaths has
proven beneficial for a range of NLP tasks, including language understanding.
However, the applicability of this approach is hampered because the abundance
of text corpora is contrasted by a scarcity of gaze data. Although models for
the generation of human-like scanpaths during reading have been developed, the
potential of synthetic gaze data across NLP tasks remains largely unexplored.
We develop a model that integrates synthetic scanpath generation with a
scanpath-augmented language model, eliminating the need for human gaze data.
Since the model’s error gradient can be propagated throughout all parts of the
model, the scanpath generator can be fine-tuned to downstream tasks. We find
that the proposed model not only outperforms the underlying language model,
but achieves a performance that is comparable to a language model augmented
with real human gaze data. Our code is publicly
available.111https://github.com/aeye-lab/EMNLP-SyntheticScanpaths-NLU-
PretrainedLM.

##  1 Introduction and Related Work

When humans read, they naturally engage in the cognitive process of
comprehending language, which, in turn, is reflected in their gaze behavior
(Just and Carpenter, 1980). In a nutshell, a scanpath (i.e., sequence of
consecutive fixations) on a stimulus text approximates the reader’s attention,
which can be exploited to inform Natural Language Processing (NLP) tasks.

Figure 1: Synthetic scanpath-augmented language model: the Scanpath Generation
Model predicts a sequence of fixations for an input sentence; token embeddings
are rearranged according to the order of fixations.

Gaze data has been shown to be beneficial in various NLP tasks, such as part-
of-speech-tagging Barrett et al. (2016), named entity recognition (Hollenstein
and Zhang, 2019), generating image captions (Takmaz et al., 2020) and question
answering (Sood et al., 2021). Researchers have explored the use of aggregated
word-level gaze features to regularize neural attention mechanisms (Barrett et
al., 2018; Sood et al., 2020). Moreover, non-aggregated scanpaths, which
capture the complete sequential ordering of the reader’s gaze behavior, have
also demonstrated promise in NLP tasks (Mishra et al., 2017, 2018a; Yang and
Hollenstein, 2023).

However, collecting gaze data is a resource-intensive endeavor, even for very
small text corpora. Hence, human gaze data is scarce, and NLP task-specific
gaze recordings are even scarcer. Moreover, applying a language model that
additionally consumes gaze data requires gaze data to be available for the
input text at deployment time—which is unrealistic for most use cases. To
overcome these limitations, researchers have proposed a multi-task learning
approach for NLP tasks such as sentence compression (Klerke et al., 2016),
sentiment analysis (Mishra et al., 2018b), and predicting text readability
(González-Garduño and Søgaard, 2017). In this approach, labeled data for the
specific NLP task is used as the primary task, while a separate eye-tracking
corpus is utilized as an auxiliary task. While this approach helps mitigate
the need for task-specific gaze data during training and testing, the problem
of general scarcity of gaze samples remains and hinders effective supervision
for data-intensive architectures.

In this paper, we propose an alternative approach by using synthetic gaze
data, which can be generated easily for any given text, to provide cognitive
signals across NLP tasks. The seminal work of Sood et al. (2020), which
integrates eye movement data generated by a computational cognitive model of
eye-movement-control-during-reading for tasks such as sentence compression and
paraphrase generation, demonstrated the potential of synthetic eye-gaze data.
Khurana et al. (2023) explored a proof-of-concept model that integrated
synthetic gaze data across multiple NLP tasks, but their results did not reach
the performance of a fine-tuned BERT model Devlin et al. (2019) without eye
gaze on the General Language Understanding Evaluation (GLUE) benchmark. In our
work, we build on recent advances in the development of machine-learning
models for generating human-like scanpaths during reading Deng et al. (2023);
Bolliger et al. (2023); Khurana et al. (2023); Nilsson and Nivre (2011).

We develop a model that combines synthetic scanpath generation with a
scanpath-augmented language model, eliminating the need for human gaze data.
The model allows for fine-tuning the scanpath generator to downstream tasks by
propagating the error gradient through the entire model. Our approach not only
outperforms the underlying language model in multiple tasks on the GLUE,
especially in low-resource settings, but even reaches a performance comparable
to an eye-gaze augmented model that uses real, rather than synthetic, eye
movement data in sentiment classification.

##  2 Model

We develop a model that combines a scanpath generation model with a scanpath-
augmented language model to perform NLP downstream tasks. Figure 1 depicts the
proposed model architecture.

#### Scanpath Generation Model

We adopt Eyettention Deng et al. (2023), an open-source state-of-the-art model
for scanpath generation over text. Eyettention predicts consecutive fixation
locations, represented as word indices, based on a stimulus sentence and the
preceding fixations. It consists of two encoders, one for embedding the
stimulus sentence, and the other for embedding the scanpath history. A cross-
attention layer aligns the outputs of the two encoders, and a decoder produces
a probability distribution over saccade ranges at each timestep. The next
fixated word index is determined by sampling from this distribution.

#### Scanpath-Augmented Language Model

We adopt the PLM-AS framework Yang and Hollenstein (2023), which augments pre-
trained language models with human scanpaths for sentiment classification.
This framework uses a language model to extract token embeddings for a
sentence, associating each embedding with its position index. By utilizing a
human scanpath (fixation index sequence) as input, the model rearranges the
token embedding sequence based on the order in which the words are fixated by
the reader. The transformed sequence is then fed into a scanpath encoder,
implemented as a layer of gated recurrent units (GRU), where the output of the
last step is used as the final feature for sentiment classification. This
framework allows for the use of different language models and achieves high
performance through fine-tuning. In this work, we employ BERTBASE222Note that
BERT can be substituted with other advanced pre-trained language models,
potentially leading to further enhancements in task performance. Devlin et al.
(2019) as the language model, following Yang and Hollenstein (2023).

#### Joint Modeling for NLP Tasks

To eliminate the need for human gaze data, we integrate the synthetic scanpath
generated by the Eyettention model consisting of a fixation index sequence
into the PLM-AS framework. Before integration, the word index sequence
generated by Eyettention is converted into a token index sequence. During
training, the error gradient of the scanpath-augmented language model can be
back-propagated through the Eyettention model, allowing its parameters to be
adapted for a specific NLP task. To handle the non-differentiable sampling
from a categorical distribution involved in scanpath generation, we employ the
Gumbel-softmax distribution Jang et al. (2017) as a fully differentiable
approximation. The training process consists of two phases. First, we pre-
train the Eyettention model on a natural reading task. Second, we train the
entire model, which includes fine-tuning the language model and the
Eyettention model, as well as training the scanpath encoder from scratch. For
the Eyettention model, we add residual connections in both encoders to enhance
its performance.

##  3 Experiments

In this section, we describe the data and present the evaluation results of
our model for a wide range of NLP tasks. Further details about training and
hyper-parameter tuning can be found in Appendix B.

###  3.1 Data Sets

CELER Berzak et al. (2022): We pre-train the scanpath generation model
Eyettention on the L1 subset of CELER, which contains eye-tracking recordings
collected from 69 native speakers of English during natural reading of 5,456
sentences.

ETSA Mishra et al. (2016) contains task-specific gaze recordings for sentiment
classification of 7 subjects who each read 383 positive and 611 negative
sentences, including sarcastic quotes, short movie reviews, and tweets.

GLUE Wang et al. (2018) includes sentiment analysis (SST-2), linguistic
acceptability (CoLA), similarity and paraphrase tasks (MRPC, STS-B, QQP), and
natural language inference tasks (MNLI, QNLI, RTE). No gaze data are
available.

###  3.2 Sentiment Classification

Table 1 presents the results of our model on the sentiment classification task
ETSA (Mishra et al., 2016), in comparison to BERT and previous state-of-the-
art eye-gaze augmented models. We follow a 10-fold cross-validation regime. In
each iteration, BERT is fine-tuned on the training portion of the ETSA text
corpus, and PLM-AS is fine-tuned on the training portion of the ETSA text
corpus and gaze data. Our model is fine-tuned on the training portion of the
ETSA text corpus and, instead of the ETSA gaze data, synthetic gaze data
generated by Eyettention. Since each sentence is associated with multiple
scanpaths, we compute the final prediction by averaging the pre-softmax logits
obtained from the models across all scanpaths for the PLM-AS baseline. Our
model averages equally many synthetic scanpaths. We make multiple notable
observations in Table 1:
(a) Our model outperforms both BERT and the state-of-the-art ScanTextGAN
Khurana et al. (2023) augmented with gaze data.
(b) Our model, augmented with _synthetic_ scanpaths, achieves comparable
performance to the PLM-AS model augmented with _human_ scanpaths, eliminating
the need for human scanpaths.
(c) Ablation experiments (bottom two rows) show that when the Eyettention
model is frozen or not pre-trained, the performance decreases. This
demonstrates the importance of both pre-training and task-specific fine-tuning
of the scanpath generator.

Model | Scanpath (#) | F1 | AUC
---|---|---|---
BERT$\star$ | - | 82.932.26 | 92.421.62
ScanTextGAN | real | 83.34 | -
ScanTextGAN | synthetic | 84.77 | -
PLM-AS$\star$ | real (7) | 85.811.16 | 94.791.02
Ours$\star$ | synthetic (7) | 85.351.77 | 94.900.94
Eyettention (frozen)$\star$ | synthetic (7) | 84.521.79 | 94.501.03
Eyettention (scratch)$\star$ | synthetic (7) | 85.031.6 | 94.771.03
Table 1: Results for sentiment classification on ETSA, with standard errors
indicated as subscript. Results obtained from our experiments are marked with
$\star$; other results are from the respective papers for recapitulation.

#### Varying the number of scanpaths

We analyze the impact of the number of scanpaths sampled both at training and
at application time on model performance. Figure 2 shows the F1 score as a
function of the number of scanpaths used by BERT without eye gaze, PLM-AS with
human scanpaths, and our model with synthetic scanpaths. We observe that the
performance of scanpath-augmented models improves as the number of scanpaths
increases, reaching its peak at seven scanpaths.333The optimal number of
scanpaths to be used by the model is considered a hyperparameter for the
subsequent experiments. Importantly, our model outperforms BERT and, when
being augmented with five or more synthetic scanpaths, approaches the
performance of PLM-AS augmented with human scanpaths.

Figure 2: Sentiment classification performance on ETSA with varying numbers of
scanpaths at training and application time. Error bars show the standard
error.

#### Low-Resource Performance

We hypothesize that eye gaze might be most beneficial in low-resource
settings. To test this hypothesis, we sample a small subset of the training
sentences K = {200, 400, 600} from the total number of around 800 training
instances, and evaluate the performance of our model augmented with seven
synthetic scanpaths (the best-performing configuration from the previous
experiments). The performance comparison between our model and the baseline
model BERT is shown in Figure 3. Our model consistently outperforms BERT, with
larger improvements observed when using less training data.

Figure 3: Sentiment classification performance on ETSA in the low-resource
setting. Error bars represent the standard error.

###  3.3 GLUE Benchmark

|  |  | MNLI | QQP | QNLI | SST-2 | CoLA | STS-B | MRPC | RTE | Avg.
---|---|---|---|---|---|---|---|---|---|---|---
K | Model | Gaze | 392k | 363k | 108k | 67k | 8.5k | 5.7k | 3.5k | 2.5k | -
200 | BERT | $\times$ | 42.901.51 | 57.422.03 | 73.070.16 | 78.781.10 | 16.952.74 | 79.430.69 | 81.180.04 | 54.301.50 | 60.50
Ours | ✓ | 48.970.83 | 61.631.78 | 70.460.62 | 80.760.74 | 24.083.55 | 74.941.20 | 81.850.17 | 59.351.47 | 62.75
500 | BERT | $\times$ | 52.091.05 | 65.130.37 | 77.040.19 | 82.550.47 | 35.611.74 | 83.140.41 | 81.530.29 | 60.720.61 | 67.23
Ours | ✓ | 56.480.38 | 67.810.23 | 77.600.26 | 84.630.50 | 36.411.39 | 81.990.58 | 82.320.52 | 61.881.24 | 68.64
1000 | BERT | $\times$ | 58.970.58 | 67.350.49 | 78.880.36 | 85.800.55 | 39.891.64 | 85.420.21 | 84.181.00 | 63.390.99 | 70.49
Ours | ✓ | 61.280.25 | 70.650.14 | 80.740.10 | 86.060.29 | 41.190.50 | 85.130.43 | 84.610.68 | 64.551.18 | 71.78
all | BERT | $\times$ | 82.9 | 69.7 | 90.1 | 93.1 | 53.9 | 84.8 | 87.7 | 66.1 | 78.54
Ours | ✓ | 83.6 | 69.6 | 90.1 | 93.8 | 50.2 | 85.8 | 87.7 | 67.3 | 78.51
Table 2: Results on the GLUE benchmark with K = {200, 500, 1000, all} training
samples. Below each task, the total number of training samples for each
dataset is indicated. We use F1 for QQP and MRPC, Spearman correlation for
STS-B, Matthews correlation for CoLA, and accuracy for the remaining tasks.
The standard error is indicated as the subscript.

In contrast to the small and single task-specific ETSA data set, we extended
our evaluation to assess whether gaze data could enhance language models
across different tasks, including scenarios with substantial text data. To
achieve this, we evaluate our model on the GLUE benchmark, a comprehensive
collection of 8 diverse NLP tasks with a large number of text samples. As no
eye gaze data is available for GLUE, we focus on the comparison with the BERT
baseline, and investigate both, high- and low-resource settings.

#### High-Resource Performance

The results of our model on the GLUE test set using all training samples (K =
all) are reported in the bottom two rows of Table 2. The results are obtained
from the GLUE leaderboard. Our model outperforms BERT in 4 out of 8 tasks, and
achieves comparable performance in 3 tasks. However, our model’s performance
is notably poor in the CoLA task, possibly due to the model’s emphasis on gaze
sequence ordering, potentially overshadowing the importance of the original
word order, which is critical to determine linguistic acceptability of
sentences.

#### Low-Resource Performance

We present the results on the GLUE benchmark with K = {200, 500, 1000}
training samples in Table 2. We take additional 1,000 samples from the
original training set as the development set used for early stopping. The
original development set is utilized for testing. We perform 5 runs with
different random seeds to shuffle the data and report the average results.

Overall, our model consistently outperforms BERT across tasks, except for the
STS-B task. In terms of average score, our model shows performance gains of
2-4% compared to BERT.

##  4 Discussion and Conclusion

We developed a model that integrates synthetic scanpath generation into a
scanpath-augmented language model. We observe that the model achieves results
that are comparable to a language model augmented with human scanpaths, which
eliminates the need for human scanpaths during both training and testing.
Human gaze data are only available for a very limited number of NLP tasks and
data sets. At application time, under any standard use case scenario of NLP
tasks, no gaze recordings are available. Synthetic gaze data not only open the
possibility to train high-capacity gaze-augmented models across tasks, which
would otherwise require the collection of an impractical large volume of gaze
data, but also allow for the exploitation of eye gaze signals as model input
at application time.

Using the GLUE benchmark, we observe that gaze signals show benefits not only
for sentiment classification tasks (SST-2), as reported in previous research,
but also for entailment classification tasks (MNLI, RTE) and a sentence
similarity task (STS-B). This highlights the potential of integrating
cognitive signals from eye gaze into a wider range of NLP tasks in the future.
Nevertheless, it is evident that not all tasks derive equal benefits from gaze
data. It remains up to future research to explore which types of tasks benefit
most from gaze signals.

Our results further show that the potential benefit of augmenting language
models with gaze data is higher for low-resource settings. Hence, we believe
that the augmentation with gaze data might be particularly interesting for
low-resource languages. Two ongoing multi-lab efforts to collect large
multilingual eye-tracking-while-reading corpora (MECO444https://meco-read.com
and MultiplEYE555https://multipleye.eu) include a range of low-resource
languages, which will allow for training scanpath generators and augmenting
language models with synthetic eye gaze for these languages in the near
future.

## Limitations

One limitation of our work is that the scanpath generation model Eyettention
was pre-trained on eye-tracking data recorded on isolated sentences (single
sentence reading paradigm). Since the majority of tasks in the GLUE benchmark
involve two-sentence classification, future work could involve pre-training
the model on an eye-tracking data set specifically designed for two-sentence
reading tasks to enhance its performance. Additionally, scanpath augmentation
turned out to be detrimental to the language model’s performance for the task
of identifying linguistically acceptable sentences (CoLA). This finding was to
be expected as the actual word order is more relevant for linguistic
acceptability of a sentence than the order in which the words are fixated.
Pre-training the scanpath generator on an eye-tracking corpus that includes
both acceptable and unacceptable sentences may be beneficial for improving the
model’s performance.

Furthermore, in our proposed framework, the sampling process involved in
scanpath generation during training and at inference time is not conducive to
a high model efficiency. Future work could explore alternative scanpath
generation models that do not rely on auto-regressive architectures to improve
efficiency.

## Ethics Statement

It is crucial to acknowledge potential privacy risks in collecting, sharing,
and processing human gaze data. Since eye movements are highly individual, it
can be possible to extract a participant’s identity from gaze data Jäger et
al. (2020); Makowski et al. (2021). Other personal information such as gender
Sammaknejad et al. (2017) and ethnicity Blignaut and Wium (2014) that can be
detected to some degree today may turn out to be extractable accurately in the
future, which incurs a risk of leakage of personal information from gaze data.
Synthetic gaze data can reduce the need for large-scale experiments with human
subjects, even though some amount of human gaze data is still necessary to
train generative models.

## Acknowledgements

This work was partially funded by the German Federal Ministry of Education and
Research under grant 01$|$ S20043.

## References

  * Barrett et al. (2018) Maria Barrett, Joachim Bingel, Nora Hollenstein, Marek Rei, and Anders Søgaard. 2018.  Sequence classification with human attention.  In _Proceedings of the 22nd Conference on Computational Natural Language Learning (CoNLL)_ , pages 302–312, Brussels, Belgium.
  * Barrett et al. (2016) Maria Barrett, Frank Keller, and Anders Søgaard. 2016.  Cross-lingual transfer of correlations between parts of speech and gaze features.  In _Proceedings of the 26th International Conference on Computational Linguistics (COLING): Technical Papers_ , pages 1330–1339, Osaka, Japan.
  * Berzak et al. (2022) Yevgeni Berzak, Chie Nakamura, Amelia Smith, Emily Weng, Boris Katz, Suzanne Flynn, and Roger Levy. 2022.  CELER: A 365-participant corpus of eye movements in L1 and L2 English reading.  _Open Mind_ , pages 1–10.
  * Blignaut and Wium (2014) Pieter Blignaut and Daniël Wium. 2014.  Eye-tracking data quality as affected by ethnicity and experimental design.  _Behavior Research Methods_ , 46:67–80.
  * Bolliger et al. (2023) Lena S. Bolliger, David R. Reich, Patrick Haller, Deborah N. Jakobi, Paul Prasse, and Lena A. Jäger. 2023.  ScanDL: A Diffusion Model for Generating Synthetic Scanpaths on Texts.  In _Proceedings of Empirical Methods in Natural Language Processing (EMNLP)_ , Singapore, Singapore.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014.  On the properties of neural machine translation: Encoder–decoder approaches.  In _Proceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation_ , pages 103–111, Doha, Qatar.
  * Deng et al. (2023) Shuwen Deng, David R Reich, Paul Prasse, Patrick Haller, Tobias Scheffer, and Lena A Jäger. 2023.  Eyettention: An attention-based dual-sequence model for predicting human scanpaths during reading.  _Proceedings of the ACM on Human-Computer Interaction_ , 7(ETRA):1–24.
  * Devlin et al. (2019) Jacob Devlin, Ming Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_ , pages 4171–4186, Minneapolis, MN, USA.
  * González-Garduño and Søgaard (2017) Ana Valeria González-Garduño and Anders Søgaard. 2017.  Using gaze to predict text readability.  In _Proceedings of the 12th Workshop on Innovative Use of NLP for Building Educational Applications, EMNLP_ , pages 438–443, Copenhagen, Denmark.
  * Hollenstein and Zhang (2019) Nora Hollenstein and Ce Zhang. 2019.  Entity recognition at first sight: Improving NER with eye movement information.  In _Proceedings of North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_ , pages 1–10, Minneapolis, Minnesota.
  * Jäger et al. (2020) Lena A. Jäger, Silvia Makowski, Paul Prasse, Liehr Sascha, Maximilian Seidler, and Tobias Scheffer. 2020.  Deep Eyedentification: Biometric identification using micro-movements of the eye.  In _Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2019_ , volume 11907 of _Lecture Notes in Computer Science_ , pages 299–314, Cham, Switzerland. Springer International Publishing.
  * Jang et al. (2017) Eric Jang, Shixiang Gu, and Ben Poole. 2017.  Categorical reparameterization with gumbel-softmax.  In _Proceedings of the 5th International Conference on Learning Representations (ICLR)_ , Toulon, France.
  * Just and Carpenter (1980) Marcel A Just and Patricia A Carpenter. 1980.  A theory of reading: From eye fixations to comprehension.  _Psychological Review_ , 87(4):329.
  * Khurana et al. (2023) Varun Khurana, Yaman Kumar, Nora Hollenstein, Rajesh Kumar, and Balaji Krishnamurthy. 2023.  Synthesizing human gaze feedback for improved NLP performance.  In _Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics (EACL)_ , pages 1895–1908, Dubrovnik, Croatia.
  * Klerke et al. (2016) Sigrid Klerke, Yoav Goldberg, and Anders Søgaard. 2016.  Improving sentence compression by learning to predict gaze.  In _Proceedings of North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_ , pages 1528–1533, San Diego, California.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled weight decay regularization.  In _Proceedings of International Conference on Learning Representations (ICLR)_ , New Orleans, Louisiana, United States.
  * Makowski et al. (2021) Silvia Makowski, Paul Prasse, David R Reich, Daniel Krakowczyk, Lena A Jäger, and Tobias Scheffer. 2021.  Deepeyedentificationlive: Oculomotoric biometric identification and presentation-attack detection using deep neural networks.  _IEEE Transactions on Biometrics, Behavior, and Identity Science_ , 3(4):506–518.
  * Mao et al. (2022) Yuning Mao, Lambert Mathias, Rui Hou, Amjad Almahairi, Hao Ma, Jiawei Han, Scott Yih, and Madian Khabsa. 2022.  UniPELT: A unified framework for parameter-efficient language model tuning.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 6253–6264, Dublin, Ireland.
  * Mishra et al. (2018a) Abhijit Mishra, Pushpak Bhattacharyya, Abhijit Mishra, and Pushpak Bhattacharyya. 2018a.  Scanpath complexity: modeling reading/annotation effort using gaze information.  _Cognitively Inspired Natural Language Processing: An Investigation Based on Eye-tracking_ , pages 77–98.
  * Mishra et al. (2017) Abhijit Mishra, Kuntal Dey, and Pushpak Bhattacharyya. 2017.  Learning cognitive features from gaze data for sentiment and sarcasm classification using convolutional neural network.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (ACL)_ , pages 377–387, Vancouver, Canada.
  * Mishra et al. (2016) Abhijit Mishra, Diptesh Kanojia, and Pushpak Bhattacharyya. 2016.  Predicting readers’ sarcasm understandability by modeling gaze behavior.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, Phoenix, Arizona, USA.
  * Mishra et al. (2018b) Abhijit Mishra, Srikanth Tamilselvam, Riddhiman Dasgupta, Seema Nagar, and Kuntal Dey. 2018b.  Cognition-cognizant sentiment analysis with multitask subjectivity summarization based on annotators’ gaze behavior.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, New Orleans, Lousiana, USA.
  * Nilsson and Nivre (2011) Mattias Nilsson and Joakim Nivre. 2011.  Entropy-driven evaluation of models of eye movement control in reading.  In _Proceedings of the 8th International NLPCS Workshop_ , pages 201–212, Copenhagen, Denmark.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019.  Pytorch: An imperative style, high-performance deep learning library.  In _Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS)_ , pages 8024–8035, Vancouver, Canada.
  * Sammaknejad et al. (2017) Negar Sammaknejad, Hamidreza Pouretemad, Changiz Eslahchi, Alireza Salahirad, and Ashkan Alinejad. 2017.  Gender classification based on eye movements: A processing effect during passive face viewing.  _Advances in Cognitive Psychology_ , 13(3):232.
  * Sood et al. (2021) Ekta Sood, Fabian Kögel, Philipp Müller, Dominike Thomas, Mihai Bace, and Andreas Bulling. 2021.  Multimodal integration of human-like attention in visual question answering.  _Computing Research Repository_.
  * Sood et al. (2020) Ekta Sood, Simon Tannert, Philipp Müller, and Andreas Bulling. 2020.  Improving natural language processing tasks with human gaze-guided neural attention.  In _Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS)_ , pages 6327–6341, Online.
  * Takmaz et al. (2020) Ece Takmaz, Sandro Pezzelle, Lisa Beinborn, and Raquel Fernández. 2020.  Generating image descriptions via sequential cross-modal alignment guided by human gaze.  In _Proceedings of Empirical Methods in Natural Language Processing (EMNLP)_ , pages 4664–4677, Online.
  * Wang et al. (2018) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. 2018.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _Proceedings of EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 353–355, Brussels, Belgium.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of Empirical Methods in Natural Language Processing (EMNLP): System Demonstrations_ , pages 38–45, Online.
  * Yang and Hollenstein (2023) Duo Yang and Nora Hollenstein. 2023.  PLM-AS: Pre-trained language models augmented with scanpaths for sentiment classification.  In _Proceedings of the Northern Lights Deep Learning Workshop_ , Tromsø, Norway.

##  Appendix A Model Details

#### PLA-AS Framework

For the PLM-AS framework, we adhere to the design of the original paper Yang
and Hollenstein (2023). The scanpath encoder consists of a single-direction
GRU layer Cho et al. (2014) with a hidden size of 768 and a dropout rate of
0.1. We initialize the hidden state of the scanpath encoder using the [CLS]
token outputs from the final layer of BERT.

##  Appendix B Training Details

We train all neural networks using the PyTorch Paszke et al. (2019) library on
an NVIDIA A100-SXM4-40GB GPU using the NVIDIA CUDA platform. For training, we
use the AdamW optimizer Loshchilov and Hutter (2019), and a batch size of 32.
We train 20 epochs and select the model with the best validation performance
for evaluation. The training is early stopped if the validation performance
does not increase for 3 consecutive epochs. During the training of our model,
we employ the Gumbel-softmax distribution with a temperature hyperparameter
set to 0.5. We use the pre-trained checkpoints from the HuggingFace repository
Wolf et al. (2020) for the language model BERTBASE.

#### Sentiment Classification

During training, each scanpath associated with one sentence is treated as a
separate instance. However, during evaluation, the pre-softmax logits obtained
from multiple scanpaths associated with the same sentence are averaged to
generate a single prediction for this sentence. We use a learning rate of 1e-5
for training all investigated models.

#### GLUE Benchmark

Table 3: Optimal number of scanpaths used for our model in GLUE Benchmark with K = {200, 500, 1000, all} training sentences. K | MNLI | QQP | QNLI | SST-2 | CoLA | STS-B | MRPC | RTE
---|---|---|---|---|---|---|---|---
200 | 5 | 3 | 3 | 7 | 3 | 7 | 3 | 7
500 | 7 | 5 | 3 | 3 | 3 | 7 | 3 | 7
1000 | 3 | 5 | 5 | 7 | 3 | 5 | 7 | 7
all | 2 | 2 | 4 | 2 | 3 | 3 | 3 | 3

We evaluate each GLUE data set using the metric specified in the benchmark. We
use the code provided in the HuggingFace repository
666https://github.com/huggingface/transformers/tree/main/examples/pytorch/text-
classification to train the BERT model and compute the metrics.

In the high-resource setting, we fine-tune the BERT model using the
hyperparameter tuning procedure outlined in the original paper (Devlin et al.,
2019). We select the best learning rate from {5e-5, 4e-5, 3e-5, 2e-5} for each
task based on the performance on the development set. The same learning rate
is used for training our model.

Additionally, for our model, we perform a hyperparameter search on the
development set to determine the optimal number of scanpaths to be used by the
model for each task. We explore different numbers of scanpaths from {2, 3, 4}
and select the configuration that achieves the best performance on the
development set. The optimal configuration for each task can be found in Table
3.

In the low-resource setting, we use the same learning rate that was found
optimal in the high-resource setting for each task. Besides, we perform a
hyperparameter search on the development set, investigating different numbers
of scanpaths from {3, 5, 7} to be used by our model. The optimal
configurations for each task can be found in Table 3.

To reduce variance, we apply shuffling to the training data using 5 different
random seeds. We use the first K samples as the new training set, and the
subsequent 1,000 samples as the development set. The data seeds used for
shuffling are {111,222,333,444,555}, while the seed s=42 is consistently used
for model training across all models. The procedure was adapted from Mao et
al. (2022).