STOCHASTIC AND DYNAMIC VEHICLE-ROUTING WITH GENERAL DEMAND AND INTERARRIVAL TIME DISTRIBUTIONS

We analyze a class of stochastic and dynamic vehicle routing problems in which demands arrive randomly over time and the objective is minimi zing waiting time. In our previous work ([6], [7]), we analyzed this p roblem for the case of uniformly distributed demand locations and Pois son arrivals. In this paper, using quite different techniques, we are able to extend our results to the more realistic case where demand loc ations have an arbitrary continuous distribution and arrivals follow o nly a general renewal process. Further, we improve significantly the b est known lower bounds for this class of problems and construct polici es that arc provable within a small constant factor relative to the op timal solution. We show that the leading behavior of the optimal syste m 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 o f the system performance on the demand distribution.