A Framework For Probabilistic Vehicle Routing

Abstract

The stochastic vehicle routing problem is a problem of considerable current importance in operations research and industrial engineering. The basic problem is to determine a fixed set of vehicle routes of minimal expected total distance. All vehicles must leave from and eventually return to a central depot, and capacity constraints and probabilistic customer demands must be satisfied. In previous work, we assumed that the demand at each node i could be modeled by a Poisson distribution with mean Λi and that demands at nodes are mutually independent. We then developed an efficient heuristic solution procedure which was quite effective in generating an excellent set of fixed vehicle routes, as evidenced by extensive computational results. With this previous work as a starting point, in this paper we investigate solution procedures for the case where other appropriate probability distributions are assumed. In addition, we present analytical results describing the various relationships between design parameters and provide a framework for performing perturbation analysis. Finally, we focus on a more flexible model in which demands are correlated.