We present solution methodologies for vehicle routing problems (VRPs) with stochastic demand, with a specific focus on the vehicle routing problem with stochastic demand (VRPSD) and the vehicle routing problem with stochastic demand and duration limits (VRPSDL). The VRPSD and the VRPSDL are fundamental problems underlying many operational challenges in the fields of logistics and supply chain management. We model the VRPSD and the VRPSDL as large-scale Markov decision processes. We develop cyclic-order neighborhoods, a general methodology for solving a broad class of VRPs, and use this technique to obtain static, fixed route policies for the VRPSD. We develop pre-decision, post-decision, and hybrid rollout policies for approximate dynamic programming (ADP). These policies lay a methodological foundation for solving large-scale sequential decision problems and provide a framework for developing dynamic routing policies. Our dynamic rollout policies for the VRPSDL significantly improve upon a method frequently implemented in practice. We also identify circumstances in which our rollout policies appear to offer little or no benefit compared to this benchmark. These observations can guide managerial decision making regarding when the use of our procedures is justifiable. We also demonstrate that our methodology lends itself to real-time implementation, thereby providing a mechanism to make high-quality, dynamic routing decisions for large-scale operations. Finally, we consider a more traditional ADP approach to the VRPSDL by developing a parameterized linear function to approximate the value functions corresponding to our problem formulation. We estimate parameters via a simulation-based algorithm and show that initializing parameter values via our rollout policies leads to significant improvements. However, we conclude that additional research is required to develop a parametric ADP methodology comparable or superior to our rollout policies.

In this thesis, we study two stochastic vehicle routing problems. In the first part, we investigate a routing problem where the distributor wants to construct a set of delivery routes each day to serve a set of geographically dispersed customers, but wants to send the same driver to the same set of customers as much as possible due to business requirements. The stochastic nature of customer demands and the existence of hard delivery time windows make this fixed routes problem much harder. We introduce a new recourse policy based on limited vehicle sharing and develop heuristic approaches for constructing fixed routes respecting the new policy for large real-life instances. Among the key contributions is the introduction of sampling-based techniques to handle the feasibility issues arising from hard delivery windows. An extensive computational study based on real-life data demonstrates the efficacy of the proposed fixed routing system and route construction techniques. In the second part, we investigate the new policy in an abstract setting to understand its properties. We characterize the optimal traditional fixed routes solution in terms of total expected cost for simple instances of the problem. Next we present a series of results for the new policy. For example, we show that operational feasibility of a set of fixed routes can be checked in polynomial time, but identifying the optimal use of fixed routes is NP-complete. In the final part, we focus on a dynamic and stochastic routing problem, which arises when there are service level agreements in place between a distributor and its customers. Specifically, the distributor has to serve customer orders within two days after the order is received, but has the flexibility to choose the actual delivery day. However, future customer orders are unknown and are revealed dynamically through time. We develop heuristic and optimal policies for simple instances of the problem that use the stochastic information about future orders. We empirically compare the performance of the various policies with the performance of policies that do not use future information and with an offline optimal policy which has perfect information about future orders.