An optimal stopping approach to managing travel-time uncertainty for time-sensitive customer pickup

- Conceptualizes on-line vehicle routing decision as optimal stopping problem.
- Considers if and when recourse should be taken under stochastic travel times.
- Proposes optimal recourse policy that accounts for the value of waiting for additional travel-time information when considering the timing of a recourse action.
- Formulates optimal stopping problem as continuous-time stochastic dynamic program and approximates its solution using numerical options-pricing method.
- Framework is demonstrated for a dial-a-ride application in which taxis serve as backup to ridesharing vehicles.

In dynamic vehicle routing, it is common to respond to real-time information with immediate updates to routes and fleet management. However, even if routes are updated continuously, in practice, some decisions once made are difficult to reverse. At times, it may thus be valuable to wait for additional information before acting on a decision. We use the theory of optimal stopping to determine the optimal timing of a recourse action when vehicles are likely to miss customer deadlines due to travel-time stochasticities and backup services are available. The factors involved in making this decision - that is, the likelihood that the primary vehicle will arrive late, the location of the backup vehicle, and value of waiting for additional travel-time information - each change dynamically over time. We develop a recourse model that accounts for this complexity. We formulate the optimal recourse policy as a stochastic dynamic program. Properties of the optimal policy are derived analytically, and its solution is approximated with a binomial lattice method used in the pricing of American options. Finally, we develop a two-stage stochastic optimization approach to show how the opportunity to take recourse dynamically might be integrated into a priori scheduling and routing. The framework is demonstrated for a stochastic dial-a-ride application in which taxis serve as backup to ridesharing vehicles.