Stochastic and dynamic vehicle routing with general demand and interarrival time distributions
Authors:
- Dimitris J. BertsimasDBDimitris J. Bertsimas
- Garrett Van RyzinGRGarrett Van Ryzin
- 1 December 1993
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 25 (4) , 947-978
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated VehiclesOperations Research, 1993
- An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probabilityOperations Research Letters, 1990
- Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean SpaceManagement Science, 1988
- Bounds and Heuristics for Capacitated Routing ProblemsMathematics of Operations Research, 1985
- An O(N log N) planar travelling salesman heuristic based on spacefilling curvesOperations Research Letters, 1982
- Poisson Arrivals See Time AveragesOperations Research, 1982
- Subadditive Euclidean Functionals and Nonlinear Growth in Geometric ProbabilityThe Annals of Probability, 1981
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the PlaneMathematics of Operations Research, 1977
- Multiple channel queues in heavy traffic. IAdvances in Applied Probability, 1970
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959