Abstract
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 ([5] and [6]) 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.