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.
Stochastic and dynamic vehicle routing with general demand and interarrival time distributions
Published 1993 in Advances in Applied Probability
ABSTRACT
PUBLICATION RECORD
- Publication year
1993
- Venue
Advances in Applied Probability
- Publication date
1993-12-01
- Fields of study
Mathematics, Computer Science, Engineering
- Identifiers
- External record
- Source metadata
Semantic Scholar
CITATION MAP
EXTRACTION MAP
CLAIMS
- No claims are published for this paper.
CONCEPTS
- No concepts are published for this paper.
REFERENCES
Showing 1-17 of 17 references · Page 1 of 1