The real-time deadheading problem in transit operations control

In high frequency transit operations, randomness and incidents often result in highly irregular headways which can significantly decrease service quality. Deadheading is one commonly used real-time operations control strategy that can improve service quality in such situations. When a vehicle is deadheaded, it runs empty from a terminal skipping a number of stations, typically in order to reduce expected large headways at later stations. The real-time deadheading problem is to determine at dispatching time which vehicles to deadhead and how many stations to skip in order to minimize the total passenger cost in the system. This paper formulates this problem, optimally solves a simplified version of the general formulation, and demonstrates that the solutions of the simpler problem are good approximations to the solutions of the more general problem.