A Milk Collection Problem with Incompatibility Constraints

Milk collection is a well known problem in rural areas all around the world. This paper considers a real-life problem for an Italian dairy company, collecting raw milk from farmers. One of the main constraints in milk collection is that some farms are small and inaccessible by large vehicles. This suggests that the problem can be mathematically represented by using the truck and trailer routing model. However, the distinction between pure trucks and complete vehicles does not suffice, since we assume that pure trucks can have heterogeneous capacities as well as trailers, showing possible analogies with the heterogeneous vehicle routing problem. Nevertheless, there is another constraint to be taken into account, leading to a further generalization of the two aforementioned routing problems. Indeed, in the milk collection problem under study, farmers produce different milk types and tank trucks are equipped with more than one compartment, into which commodities are transferred. This generates the additional constraint that at most one milk type can be assigned to a tank compartment. The goal of this paper is to show how operations research techniques helped the company in improving its daily performance. In particular, a solution approach is presented based on two mathematical formulations and local search, all embedded in a multiple restarting mechanism. The first mathematical formulation minimizes the number of vehicles to be routed in the network, and the second one the tour length. Experiments on the real case study and a comparison with the previous situation are given.