Biased-randomized iterated local search for a multiperiod vehicle routing problem with price discounts for delivery flexibility

The multiperiod vehicle routing problem (MPVRP) is an extension of the vehicle routing problem in which customer demands have to be delivered in one of several consecutive time periods, for example, the days of a week. We introduce and explore a variant of the MPVRP in which the carrier offers a price discount in exchange for delivery flexibility. The carrier's goal is to minimize total costs, which consist of the distribution costs and the discounts paid. A biased-randomized iterated local search algorithm is proposed for its solution. The two-stage algorithm first quickly generates a number of promising customer-to-period assignments, and then intensively explores a subset of these assignments. An extensive computational study demonstrates the efficacy of the proposed algorithm and highlights the benefit of pricing for delivery flexibility in different settings.