The work addressed in this paper is motivated from a real problem proposed to the authors by a bakery company in Northern Spain. The objective is to minimize the total distance travelled for the daily routes over the week. In order to reduce this total distance, some flexibility in the dates of delivery is introduced. A mixed-integer linear model for the problem is formulated. In addition, a two-phase method based in GRASP and path-relinking metaheuristic strategies is proposed. Computational experiments show that the method performs very well, obtaining high-quality solutions in short computational times. Moreover, when it is applied to real-data-based instances, the obtained solutions considerably reduce transportation costs over the planning horizon.
