W e consider stochastic vehicle routing problems on a network with random travel and service times. A fleet of one or more vehicles is available to be routed through the network to service each node. Two versions of the model are developed based on alternative objective functions. We provide bounds on optimal objective function values and conditions under which reductions to simpler models can be made. Our solution method embeds a branch-and-cut scheme within a Monte Carlo sampling-based procedure. We consider a stochastic vehicle routing problem (SVRP) that consists of planning optimal vehicle routes to service a number of locations in the presence of random travel and service times. The system is modeled using a network whose arcs have nonnegative random travel times and whose nodes have nonnegative random service times, with distributions assumed to be known. Vehicles are uncapacitated and routes for each vehicle begin and end at a specific depot node. A route is defined as the set of arcs followed by a vehicle and the set of nodes it services. These routes are selected before knowing the random travel and service times and so that each node will be serviced. After the routes have been planned and realizations of the random travel and service times become known, the actual time to complete each route can be computed. The vehicles must follow their a priori routes; no route reoptimizations are permitted. The time at which the final vehicle returns to the depot, after all nodes have been serviced, is called the completion time. We consider two models with different objectives: The first minimizes the expected completion time and the second maximizes the probability that the operation is complete on or before a prespecified target time, T . Applications of the SVRP occur in a variety of fields. For example, Lambert et al. (1993) design routes for vehicles to collect deposits from bank branches and deliver them to a central office. In this paper, we study properties of the SVRP and present solution methods. In the remainder of this section, we briefly review related work. Section 2 provides a formal problem statement. In §3, we study properties of the SVRP: relating the models under the alternative objective functions, developing bounds, and providing conditions under which reductions to simpler deterministic models can be made. Solution methods and computational results are discussed in §4, and the paper is summarized in §5. Jaillet (1985, 1988) considers a probabilistic traveling salesman problem (TSP) with random demand. An a priori tour is constructed that includes all potential customers, and after observing the subset that requires service, the other customers are skipped. The goal is to find a tour of minimum expected length. Bertsimas and Howell (1993) further explore this problem, and Bertsimas (1992) generalizes it to a capacitated single-vehicle routing problem with random demands. For more on a priori optimization, see Bertsimas et al. (1990) . Laporte et al. (1994) Dror et al. (1989) and Dror (1993) , but the authors indicated that computational solution of these models was not possible. The stochastic component of the models described previously lies in the customer demands. For incapacitated vehicles, random demands are modeled via random node service times. The arc travel times may also be random. Leipälä (1978) studies the expected length of posterior tours of TSPs with random arc lengths. Berman and Simchi-Levi (1989) consider a variant of the probabilistic TSP in which the location of the salesman's home is to be optimized on a network with a random subset of customers requiring service and random travel times. Kao (1978) , Sniedovich (1981), and Carraway et al. (1989) consider a stochastic TSP in which the objective is to maximize the probability of completing the tour by a deadline when the arcs have independent and normally distributed travel times. Laporte et al. (1992) introduce the SVRP with stochastic travel and service times. In their approach, the vehicles are incapacitated, and each node must be serviced. Each vehicle has a target time by which its route should be complete: A chance-constrained formulation ensures this with prespecified probability levels, whereas a stochastic program with simple recourse penalizes the expected value by which route travel times exceed the respective targets. Laporte et al. use a branch-and-cut approach to solve instances of the SVRP on networks with 10 to 20 nodes and 2 to 5 scenarios. Lambert et al. (1993) approximately optimize collection routes through bank branches in a network with stochastic travel times by adapting the heuristic due to Clarke and Wright (1964) . As in Laporte et al. (1992) , the model incorporates target route completion times. They present results for networks with 28 and 44 nodes, in which random arcs access 3 or 4 of the nodes, respectively, and can take two values (all travel times are long or all are short). We use a variant of their 28-node problem in our computational work. Like most of the work described herein, our model is static in nature (i.e., we select vehicle routes before realizing the random parameters and do not subsequently reoptimize the routes). Each node in the network must be visited by a vehicle, and arc travel times and node service times are stochastic. Even though the vehicles in the models of Laporte et al. (1992) and Lambert et al. (1993) are incapacitated, they are called SVRPs instead of stochastic multiple salesmen TSPs (perhaps to avoid confusion with probabilistic TSPs). Of the models in the literature, ours is closest to those of Laporte et al. and Lambert et al.; so, we follow their naming convention. The objective functions in most of the stochastic vehicle routing problem (VRP) and TSP models depend on the total travel costs although, as noted previously, some incorporate target completion times for each vehicle. In contrast, our models' objective functions depend on the length of the longest route. Such an objective function would be most appropriate when the goal is to minimize completion time of the project.
Another variant of the HMDMVPP-RST where the vehicles are homogeneous and modeled as point masses is the stochastic multiple vehicle routing problem with random travel times REF .
Stochastic Vehicle Routing with Random Travel Times
Transportation Science
Transportation Science
Mathematics Computer Science