Optimizing vehicle routes in a bakery company allowing flexibility in delivery dates

Abstract

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.

Keywords:

• VRP with flexibility in delivery
• metaheuristics
• GRASP
• path relinking

Acknowledgements

We wish to thank sincerely J.F. Cordeau and V. Hemmelmayr for running our instances with their algorithms, which allowed the comparisons presented in this work. This work has been done when the last three authors enjoyed the hospitality of Applied Economic Department, University of Burgos, Spain. We would like to thank all colleagues from this department. This work was partially supported by CONACYT México (grants 61903, 61343), FEDER founds and Spanish Ministry of Science (project ECO2008-06159/ECON), Regional Government of ‘Castilla y León’ (project BU008A10-2) University of Burgos and CajaBurgos (internal projects 2009) and the Universidad Autónoma de Coahuila (México). These supports are gratefully acknowledged. Finally, thanks are due to the two anonymous referees who greatly helped to improve the presentation of this work.