Highlights 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.

    Abstract 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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:


    Erscheinungsdatum :

    2017-04-29


    Format / Umfang :

    16 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Departure time modelling applicability and travel time uncertainty

    Borjesson, M. | British Library Conference Proceedings | 2007


    Airport access and travel time uncertainty

    Taylor, Robin / Ashford, Norman J. / Ndoh, Ngoe | TIBKAT | 1995



    Managing uncertainty in on-demand air travel

    Yang, Wei | Online Contents | 2010


    Managing uncertainty in on-demand air travel

    Yang, Wei / Karaesmen, Itır Z. / Keskinocak, Pınar | Elsevier | 2010