Activated Benders Decomposition for Paratransit Workforce
Scheduling Under Cancellation Uncertainty
K. S. Cummingsa,∗ , A. Jacquillata,b , V. Vazec
a Operations Research Center, MIT, Cambridge, MA, USAb Sloan School of Management, MIT, Cambridge, MA, USAc Thayer School of Engineering, Dartmouth College, Hanover, NH, USA∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 4, 2022
Keywords: workforce scheduling, paratransit, Benders decomposition, stochastic programming1INTRODUCTION

People with disabilities face significant obstacles to mobility, including inaccessibility, lack ofassistive technology, inconvenient schedules, inadequate accommodations, and discrimination(World Health Organization, 2001). Toward provision of equitable services, transit agencies seek
to offer high-quality paratransit options to populations with limited mobility, mandated under
the U.S. Americans with Disabilities Act of 1990.
Paratransit systems entail complex, costly operations. As typical pickup-and-delivery systems,
paratransit services face spatiotemporal imbalances, strict time windows, and traffic congestion.
In addition, operators must drive accessible vehicles and accommodate passenger needs. Dueto these complexities, paratransit contributes to 2–3% of transit ridership but 8–12% of transit
costs (Meshram, 2018). In response, transit agencies are working to modernize paratransit bydeveloping new partnerships with ride-hailing operators and launching digital platforms.
The paratransit operational regime defines a middle ground between fixed-route transit and ondemand ride-hailing. Providers have visibility into rider demand because of advance requests
and a high proportion of recurring trips (e.g., commuting trips, trips to regular medical appointments). On the supply side, paratransit providers operate their own vehicle fleets with employee
drivers. Yet, paratransit faces many uncertainties like trip cancellations, driver no-shows, andtraffic congestion, requiring real-time routing adjustments. Paratransit therefore combines theplanning challenges of fixed-route transit with the operational challenges of mobility on-demand.
Paratransit systems thus require dedicated analytics capabilities to provide low-cost, high-quality
services to populations with limited mobility. Paratransit operations are a special case of the diala-ride (DAR) problem (Cordeau & Laporte, 2007). Bertsimas & Yan (2021) recently developed acluster-then-route optimization approach to support vehicle routing for paratransit. In contrast,planning and design decisions in DAR systems have received more limited research.
In response, this work optimizes paratransit workforce schedules. We partner with an anonymous
technology-based transportation provider that operates paratransit services in many US cities.
Our stochastic program generates itineraries for drivers ahead of operations that respect trip
TRISTAN XI Symposium

Paratransit Workforce Scheduling with Cancellation Uncertainty

K. Cummings, A. Jacquillat, V. Vaze

2cancellation uncertainty. Our collabor uses its digital platform to outsource trips to self-scheduled
contractors on the day of operations, lending extra flexibility when optimizing employee drivers’
shifts. From a technical standpoint, driver scheduling is complicated by the integration of two
hard combinatorial optimization problems: workforce planning and downstream DAR operations.
To tackle this challenge, we develop a new scalable approach involving an efficient formulation
and a generalizable decomposition algorithm.

2AN EFFICIENT TWO-STAGE STOCHASTIC PROGRAM

Our first contribution is to develop a formulation to optimize driver shifts in paratransit systems
that are robust to trip cancellation uncertainty. Our formulation leverages the vehicle-sharing
network from Vazifeh et al. (2018) to integrate DAR operations into a strategic workforce scheduling model. The formulation is a two-stage stochastic program with integer recourse, but thevehicle-sharing network induces a tight formulation—much tighter than canonical DAR models.
The model takes as inputs the number of available drivers W and a set of trip requests, eachcharacterized by a pickup time and pickup/drop-off locations. We construct a vehicle-sharing
network in which nodes are trip requests and directed arcs connect two requests that the samevehicle can serve. The first-stage problem determines driver itineraries, defined as ordered setsof trip requests. We generate an extensive set of candidate itineraries with the k-shortest paths
algorithm from Yen (1971) over the vehicle-sharing network. Parameter Ci captures labor costsand binary trip delay penalties for each itinerary i ∈ I. A set partitioning formulation selects
itineraries x ∈ {0, 1}I , subject to cover constraints ensuring that all requests are served andbudget constraints ensuring that at most W itineraries are selected.
After cancellations occur, the second-stage recourse problem outsources trips to contractors if
necessary. We leverage the vehicle-sharing graph over the outsourced trips to construct physicallyvalid itineraries for contractors. In each cancellation scenario ω ∈ Ω occurring with probabilitypω , we define second-stage variables y ω that capture trip outsourcing. The second-stage problem
minimizes outsourcing costs, subject to flow balance and consistency constraints. The full formulation’s objective is represented in Equation (1), where F denotes the set of feasible first-stagedecisions, and Gω (x) denotes the set of feasible second-stage decisions in scenario ω given x ∈ F.
!
XX
minCi · x i +pω · min g(y ω )(1)x∈Fi∈Iw∈Ωy ω ∈Gω (x)For conciseness, we omit the full formulation. However, we emphasize that the tight secondstage formulation comes at the cost of exponentially many coupling constraints between firstand second-stage variables, reminiscent of linking constraints in facility location, network design,and production-routing formulations. The generalized structure is shown in Equation (2).
yωi ≤ xi , ∀ω ∈ Ω, i ∈ Iω3(2)AN ACTIVATED BENDERS DECOMPOSITION ALGORITHM

The second contribution of the paper is a solution algorithm termed activated Benders decomposition (ABD). The algorithm iterates, until convergence, between a master problem and arestricted subproblem—involving activated constraints and activated variables. This approach
is motivated by the observation that only a small subset of candidate itineraries is selected in
the first stage; hence many second-stage constraints become moot and many second-stage decision variables can be fixed to zero (see Eequation (2)). In a Benders decomposition scheme, we
can thus solve the activated subproblems at each iteration by considering only the variables andTRISTAN XI Symposium

Paratransit Workforce Scheduling with Cancellation Uncertainty

K. Cummings, A. Jacquillat, V. Vaze

3

constraints corresponding to activated itineraries {i ∈ I : xi = 1}, as opposed to solving the fullsubproblems. One question remains: how to retrieve global optimality cuts for the full problem?
To tackle this challenge, we develop a primal-dual approach to reconstruct a solution to the fullsubproblem from the activated subproblem’s solution. We prove that the proposed ABD scheme
provides a valid optimality cut at each iteration and converges finitely to the optimal solution of
the two-stage stochastic program with relaxed second-stage variables. By embedding ABD into
an integer L-shaped decomposition inspired from Laporte & Louveaux (1993), we obtain a finitely
convergent algorithm for the two-stage stochastic integer program. The proposed algorithm canalso accommodate traditional acceleration strategies in Benders decomposition.
ABD is generalizable to any two-stage stochastic program with binary first-stage variables andsecond-stage activation constraints. Examples include production constraints in facility location,arc capacity constraints in network design, and delivery constraints in production-routing. ABDprovides a computationally efficient decomposition approach that restricts the subproblem toconstraints and variables relevant to the selected facilities, arcs, routes, and itineraries.

4PRELIMINARY RESULTS

Our third contribution is to demonstrate the benefits of our modeling and algorithmic approachto optimize workforce planning in paratransit systems using real-world historical data.
From a computational standpoint, ABD yields high-quality solutions, consistently outperforming
baseline algorithms. Table 1 reports the optimality gap, computational times, and expected
costs obtained with ABD, Benders decomposition (BD), and off-the-shelf implementations of thestochastic integer program (SIP) and the model with continuous recourse (SCP). ABD converges
to the SIP-optimal solution in every trial except one, which achieves a 0.01% optimality gap.
Off-the-shelf implementation leads to sub-optimal solutions, especially with many scenarios. BD
returns close-to-optimal solutions but fails to consistently converge.
From a practical standpoint, Figure 1 and Table 2 show that the optimized solution significantly
reduces costs compared to historical shifts, which induce significant buffers as compared to trip
demand. The optimized shifts are more aggressive, leading to a more balanced system in terms of
demand and supply. The optimized solution utilizes more drivers through shorter shifts and does
not serve all trip requests at their requested times, taking advantage of the time windows. Unlike
the historical solution, the optimized solution critically leverages the availability of contractors
to outsource requests as necessary and accommodates all trips with no delays, driving costs down
and level of service up. In ongoing work, we are expanding our model to incorporate additionalcomplexities, including ride-sharing, driver no-shows, and real-time itinerary adjustments.

References
Bertsimas, D., & Yan, J. 2021. The edge of optimization in large-scale vehicle routing for paratransit.
Cordeau, Jean-François, & Laporte, Gilbert. 2007. The dial-a-ride problem: models and algorithms.
Annals of Operations Research, 153(1), 29–46.
Laporte, Gilbert, & Louveaux, François V. 1993. The integer L-shaped method for stochastic integer
programs with complete recourse. Operations research letters, 13(3), 133–142.
Meshram, Aditi. 2018. Best Practices in ADA Paratransit: Cost Reduction and Service Enhancement.
University of California, Davis.
Vazifeh, Moe, Santi, Paolo, Resta, Giovanni, Strogatz, Steven, & Ratti, Carlo. 2018. Addressing theminimum fleet problem in on-demand urban mobility. Nature, 557.
World Health Organization. 2001. IFC: International Classification of Functioning, Disability and Health.
Yen, Jin. 1971. Finding the K Shortest Loopless Paths in a Network. Management Science, 17(11).

TRISTAN XI Symposium

Paratransit Workforce Scheduling with Cancellation Uncertainty

K. Cummings, A. Jacquillat, V. Vaze

4Table 1 – Computational results for each method by number of scenarios. “# solutions” and “convergence” respectively report number of instances where algorithm finds a solution and converges to provable
optimality out of six instances (corresponding to six days of the week). Computational times are given inseconds, costs in percent optimality.

MethodABDBD

SCP

SIP

Scenarios
1
1025
50
100
1
1025
50
100
1
10
25
50
100
1
102550100# solutions
6/6
6/6
6/6
6/6
6/6
6/6
6/6
6/6
6/6
6/6
6/6
6/6
5/6
5/6
5/6
6/6
6/65/6
5/6
3/6

Convergence
6/6
6/6
6/6
6/6
5/6
3/6
2/6
1/6
0/6
0/6
0/6
0/6
0/6
0/6
0/6
1/6
0/6
0/6
1/6
0/6

Avg.
SCP Gap
00
0
0
0.01%
1.66%
2.39%
2.72%
3.85%
45.3%
0.27%
0.05%
100%
33.2%
100%
-Avg.
SIP Gap
00
0
0
0.01%
1.66%
2.43%
2.72%
3.85%
45.3%
0.27%
0.06%
100%
33.2%
100%
19.7%
0.28%
0.16%
24.9%
0.35%

MinCPU
2.86
3.01
2.91
3.05
19.7
69.3
1430
2179
3600
3600
3600
3600
3600
3600
3600
20.4
3600
3600
994
3600

Max
CPU
160
143
361
1884
3600
3600
3600
3600
3600
3600
3600
3600
3600
3600
3600
3600
3600
3600
3600
3600

Avg
CPU
34.4
42.3
79.2
349
638
1982
3209
3363
3600
3600
3600
3600
3600
3600
3600
3003
3600
3600
3166
3600

Avg.
Cost
100
100
100
100
100
101
101
101
101
101
100
105
120
108
115
100
100
100
104
129

Figure 1 – Average workforce vs. requests. Confidential y-axis scale.
Table 2 – Historical vs. optimized performance. Number of workers normalized for confidentiality.

Solution
Historical
Optimized

Avg. shift length (h)5.39
1.14

TRISTAN XI Symposium

Number of workers
100149% contractors
0.00
1.67

% trips delayed
19.7
0.00

Paratransit Workforce Scheduling with Cancellation Uncertainty