Approximate Dynamic Programming for Real-time Assignment of Extraboard Transit Operators
Abstract
This study investigates real-time assignment decisions for extraboard transit operators, who are responsible for covering open work due to unexpected events such as driver absenteeism. Efficient usage of extraboard operators is critical as open work negatively affects service reliability. The problem is formulated as a Markov decision process, designed to capture its stochastic and sequential nature. Due to the problem's very large state space, an approximate policy is proposed in the form of an integer program, which maps a system state to assignment decisions such that the sum of immediate and expected future rewards is maximized. As part of off-line training, future value functions for individual operators are computed using a backward dynamic program. Then, the overestimation in the aggregate value obtained by summing individual values is corrected to account for the interaction among operators. Case studies are conducted based on the operations at a real-world transit agency. Key performance metrics including uncovered open work and extraboard utilization rates are examined for varying absenteeism rates and extraboard roster sizes. The approximate policy is shown to outperform benchmark decision rules mirroring real-world assignment strategies. Further numerical experiments are conducted to analyze different operational policies: (1) inclusion of overtime drivers in the reserve operator roster; (2) reward weights for work tasks that consider passenger wait time saved. Observations from these computational analyses provide actionable insights into extraboard sizing, overtime usage, and real-time dispatch practices at transit agencies.
Related
- Computing Approximate Solutions of Inconsistent Max-Min Fuzzy Relational Equations by Mixed-Integer Programming
- Agmon estimates for the difference of exact and approximate Dirichlet eigenfunctions for difference operators
- Neural operators approximate strongly continuous convex monotone semigroups
- On approximate support versions of Donoho--Stark uncertainty principles for k-Hadamard operators
- Approximate Inversion of Discrete Fourier Integral Operators via Hierarchically Semiseparable Matrices
BibTeX
@misc{song2026approximate,
title = {{Approximate Dynamic Programming for Real-time Assignment of Extraboard Transit Operators}},
author = {Jilin Song and Amer Shalaby and Merve Bodur},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.04511},
eprint = {2605.04511},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.04511},
}
RIS
TY - UNPB
TI - Approximate Dynamic Programming for Real-time Assignment of Extraboard Transit Operators
AU - Jilin Song
AU - Amer Shalaby
AU - Merve Bodur
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2605.04511
UR - https://arxiv.org/abs/2605.04511
AB - This study investigates real-time assignment decisions for extraboard transit operators, who are responsible for covering open work due to unexpected events such as driver absenteeism. Efficient usage of extraboard operators is critical as open work negatively affects service reliability. The problem is formulated as a Markov decision process, designed to capture its stochastic and sequential nature. Due to the problem's very large state space, an approximate policy is proposed in the form of an integer program, which maps a system state to assignment decisions such that the sum of immediate and expected future rewards is maximized. As part of off-line training, future value functions for individual operators are computed using a backward dynamic program. Then, the overestimation in the aggregate value obtained by summing individual values is corrected to account for the interaction among operators. Case studies are conducted based on the operations at a real-world transit agency. Key performance metrics including uncovered open work and extraboard utilization rates are examined for varying absenteeism rates and extraboard roster sizes. The approximate policy is shown to outperform benchmark decision rules mirroring real-world assignment strategies. Further numerical experiments are conducted to analyze different operational policies: (1) inclusion of overtime drivers in the reserve operator roster; (2) reward weights for work tasks that consider passenger wait time saved. Observations from these computational analyses provide actionable insights into extraboard sizing, overtime usage, and real-time dispatch practices at transit agencies.
ER -