Vehicle routing with soft time windows and Erlang travel times

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.