Schedule negotiation with ADA paratransit riders under value of time uncertainty

When paratransit riders book their travels, operators have the flexibility to adjust the requested pickup time within a predetermined limit for efficiency purposes in accordance with the Americans with Disabilities Act (ADA) regulations. This practice, known as schedule negotiation, is widely adopted across the United States (U.S.). However, the existing paratransit literature lacks optimization methods to support decision-making in this context. To address this research gap, we propose a new mathematical formulation, enabling an operator to simultaneously determine how a new travel request can be accommodated and how incentives can be designed to maximize the operator’s payoff (revenues minus total costs). In addition, to enhance the realism of behavioral modeling in the paratransit literature, we explicitly consider the privately held value of time information for riders, which results in probabilistic responses. Eventually, the formulation is a nonconvex mixed-integer nonlinear program (MINLP). We thus design a decomposition-based fix-and-optimize algorithm that ensures global optimality despite the nonconvexity. We validate and evaluate our proposed method through synthetic analyses and real-world case studies, which demonstrate substantial advantages of schedule negotiation in improving paratransit operational efficiency. We also highlight the efficiency of the proposed solution approach relative to a benchmark approach based on complete enumeration. The proposed optimization method is thus expected to advance the state of the practice in pickup time negotiation in paratransit and other related mobility services.