¹The University of Tulsa, Tulsa, Oklahoma, USA

Correspondence: TL Urban, Operations Management, The University of Tulsa, 600 South College Avenue, Tulsa, Oklahoma 74104-3187, USA. E-mail: urbantl@utulsa.edu

Received January 2006; Accepted April 2007; Published online 25 July 2007.

Abstract

This paper investigates vehicle-routing problems in which the travel times are random variables, and deliveries are made subject to soft time-window constraints. In particular, we model the travel time using a shifted gamma distribution. Penalties are incurred for deviations from the customers' time windows—early or late—and are developed using a fixed cost, a linear cost penalty, and/or a quadratic loss penalty. Alternatively, specifying a given probability of meeting the time-window constraints is considered. A tabu-search metaheuristic is developed, and computational results on test problems from the literature are reported.