| The deterministic vehicle routing problem (VRP) is well studied in the operations research literature. A set of customers, located on the nodes of a network, each asking a given amount of demand, has to be served by a vehicle of limited capacity. The objective is to route the vehicle such that all customers' demands are satisfied and the distance traveled is minimized. A variation of the problem where customers' demands are assumed to follow a given probability distribution is considered. The problem of finding a tour through the customers that minimizes expected distance traveled is defined as the stochastic vehicle routing problem (SVRP).; In a deterministic setting, it is assumed that the vehicle always has enough capacity to satisfy all customers' demands. In a stochastic environment, this is not necessarily the case. A route failure is said to occur when the vehicle capacity becomes attained or exceeded at some customer location. In such a situation, different alternatives or recourse actions are available to the decision maker: the remaining customers may be served by a different vehicle, may be skipped, their service may be rescheduled for another day, or one may have the vehicle return to the depot, replenish, and resume its tour.; Previous work in the literature has focused on computing a fixed order of customers' visitation, eventually supplemented by decision rules on when to return to the depot to replenish, in anticipation of route failures. Recourse actions are taken when a route failure occurs. This approach to SVRP treats the problem as a static one, whereby the order of customers' visitation is not changed during its real-time execution. Recomputing routes based on the information that becomes available during the execution of the tour, although more costly from a computational standpoint, should decrease the expected distance traveled.; In this framework, the goal of this work is to develop computationally viable ways of computing in real-time a routing policy for SVRP. The problem is modeled as a stochastic shortest path, and different dynamic programming formulations are developed and analyzed. They are shown to be well behaved. State space decompositions, that allow to solve to optimality small size instances, are derived. For larger sizes, different heuristics are developed in order to compute sub-optimal policies.; The significance of this work relies on its novelty, especially on the impact that its findings may have on the field of vehicle routing: the thesis proposes computationally viable ways of coming up with good solutions for a version of the problem that has so far been considered intractable. (Abstract shortened by UMI.)... |
