Vehicle routing with soft time windows and Erlang travel times. (English) Zbl 1176.90108
Summary: 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.
MSC:
90B20 | Traffic problems in operations research |
90C59 | Approximation methods and heuristics in mathematical programming |