Abstract

We introduce and solve a new multi-commodity Vehicle Routing Problem, motivated by a case study of milk collection in Chile. Different grades of raw milk are collected from a number of farms scattered over a large area and transported to a single plant, allowing milk blending at the trucks. Previous works allow blending different grades of milk in the trucks, but the resulting blend is classified as its worst grade component, even if there was a single drop of it in the blend. The novelty of our work is the use of a less conservative gradual blending rule that associates milk grades to ranges of somatic cell count per milliliter, resulting in a more accurate classification of milk. The volume and somatic cell count per milliliter of the milk produced at each farm are known before the collection, and the farms are paid accordingly. The problem is to route a heterogeneous fleet of vehicles to maximize total profit at the plant, i.e., the revenue from milk minus route cost. All the milk is collected and gradual blending is applied. We propose a mixed integer linear programming formulation and solve the problem using a branch-and-cut method for small instances, and an Iterated Local Search metaheuristic for real-size instances. Both are applied to a large set of standard instances and a real case in Chile. Our results show an increase in profit over previous milk collection strategies, of 20% and 28% for test instances and up to 30% for a real instance.