Garrett van Ryzin
Stochastic and dynamic vehicle routing with general interarrival and service time distributions
Coauthor(s): D. J. Bertsimas.
Adobe Acrobat PDF
We analyze a class of stochastic and dynamic vehicle routing problems in which demands arrive randomly over time and the objective is minimizing waiting time. In our previous analysis ( and ) on this problem, we needed to assume uniformly distributed demand locations and Poisson arrivals. In this
paper, using quite different techniques, we are able to extend our results to the more realistic case where demand locations have an arbitrary distribution and
arrivals follow a general renewal process. Further, we improve significantly the best known lower bounds for this class of problems and construct policies which are provably within a small constant factor relative to the optimal solution. We
show that the leading behavior of the optimal system time has a particularly simple form which offers important structural insight to the behavior of the system. Moreover, by distinguishing two classes of policies our analysis shows an interesting dependence of the system performance on the demand distribution.
Source: Advances in Applied Probability
Bertsimas, D. J., and Garrett van Ryzin. "Stochastic and dynamic vehicle routing with general interarrival and service time distributions." Advances in Applied Probability 25 (1993): 947-978.