A Set-Partitioning-Based Model for the Stochastic Vehicle Routing Problem

Clara Novoa(cn17txstate.edu)
Rosemary Berger(rosemary.bergerverizon.net)
Jeff Linderoth(jtl3lehigh.edu)
Robert Storer(rhs2lehigh.edu)

Abstract: The objective of the Vehicle Routing Problem (VRP) is to construct a minimum cost set of vehicle routes that visits all customers and satisfies demands without violating the vehicle capacity constraints. The Stochastic Vehicle Routing Problem (SVRP) results when one or more elements of the VRP are modeled as random variables. In this paper, we present a set-partitioning-based modeling framework for the VRP with stochastic demands (VRPSD). The framework can be adapted easily for routing problems with randomness in other problem elements, such as random customers and random travel times. We formulate the VRPSD as a two-stage stochastic program and introduce an extended recourse strategy in which vehicles are allowed to serve additional customers from failed routes prior to returning to the depot or to serve customers from failed routes on a new route after returning to the depot. Computational experiments show that route plans generated using the new recourse function perform quite well, especially for problems with few customers per route, where cost savings of roughly 5% are possible.

Keywords: vehicle routing; set partitioning, stochastic programming

Category 1: Applications -- OR and Management Sciences

Category 2: Stochastic Programming

Citation: Technical Report 06T-008, Department of Industrial and Systems Engineering, Lehigh University

Download: [PDF]

Entry Submitted: 12/06/2006
Entry Accepted: 12/06/2006
Entry Last Modified: 12/06/2006

Modify/Update this entry