An Exact Algorithm for the Vehicle Routing Problem with Time Windows and Perishable Products

Maintaining the quality of temperature-controlled perishable products during distribution is essential. Several factors affect product quality and the energy cost of refrigeration during distribution, including the temperature inside delivery trucks, route duration, number of stops, and vehicle load. The existing literature on routing for perishable products considers only a limited set of these factors, and most solution methods rely on heuristics or commercial solvers. This research formulates a vehicle routing problem with time windows and quality considerations. The objective is to determine a set of vehicle routes that minimize both travel costs and refrigeration energy costs while satisfying customer quality criteria and time windows. To capture product quality decay during transportation, we propose a function that accounts for the effect of temperature, route duration, number of stops, and vehicle load, thereby extending existing quality decay models in the literature. To solve the problem, we developed a tailored exact framework with several specialized features to efficiently manage quality decay and energy cost functions. Computational experiments demonstrate that the proposed algorithm is capable of solving instances with up to 100 customers. In addition, we revisit the trade-offs in temperature-controlled routing and provide useful insights into the impact of quality decay and temperature-related coefficients on routing decisions and costs. Funding: This research was partially supported by TKI DINALOG [Grant 2017-2-131TKI]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0262 .