  Staff scheduling is a well-known problem in operations research and finds its
application at hospitals, airports, supermarkets, and many others. Its goal is
to assign shifts to staff members such that a certain objective function, e.g.
revenue, is maximized. Meanwhile, various constraints of the staff members and
the organization need to be satisfied. Typically in staff scheduling problems,
there are hard constraints on the minimum number of employees that should be
available at specific points of time. Often multiple hard constraints
guaranteeing the availability of specific number of employees with different
roles need to be considered. Staff scheduling for demand-responsive services,
such as, e.g., ride-pooling and ride-hailing services, differs in a key way
from this: There are often no hard constraints on the minimum number of
employees needed at fixed points in time. Rather, the number of employees
working at different points in time should vary according to the demand at
those points in time. Having too few employees at a point in time results in
lost revenue, while having too many employees at a point in time results in not
having enough employees at other points in time, since the total
personnel-hours are limited. The objective is to maximize the total reward
generated over a planning horizon, given a monotonic relationship between the
number of shifts active at a point in time and the instantaneous reward
generated at that point in time. This key difference makes it difficult to use
existing staff scheduling algorithms for planning shifts in demand-responsive
services. In this article, we present a novel approach for modelling and
solving staff scheduling problems for demand-responsive services that optimizes
for the relevant reward function.
