Article contents
Stochastic and dynamic vehicle routing with general demand and interarrival time distributions
Published online by Cambridge University Press: 01 July 2016
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 work ([6], [7]), we analyzed this problem for the case of 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 continuous distribution and arrivals follow only a general renewal process. Further, we improve significantly the best known lower bounds for this class of problems and construct policies that 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 that offers important structural insight into 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.
MSC classification
- Type
- Research Article
- Information
- Copyright
- Copyright © Applied Probability Trust 1993
Footnotes
The research of D. Bertsimas was partially supported by a Presidential Young Investigator Award DDM-9158118 with matching funds from Draper Laboratory. The research of both authors was partially supported by the National Science Foundation under grant DDM-9014751 and by grants from Draper Laboratory and the UPS Foundation.
References
- 73
- Cited by