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.
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.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.