We study a variant of the multi-period vehicle routing problem, in which a service provider offers a discount to customer in exchange for delivery flexibility. We establish theoretical properties and empirical insights regarding the intricate and complex relation between the benefit from additional delivery flexibility, the discounts offered to customers to gain additional delivery flexibility, and the likelihood of acceptance of discount offers by customers. Computational experiments, using an exact dynamic programming algorithm show that, depending on the setting, cost savings exceeding 30% can be achieved.