An Iterated Local Search Approach to Solve the Milk Collection Problem with Blending

In this work, we face the vehicle routing problem for the milk collection considering different qualities of milk and blending. This problem can be considered as a multi-product vehicle routing problem with blending. In this version, different products can be mixed, generating an important reduction in traveling costs but a reduced deterioration of milk quality related to milk incoming. To solve this problem, we propose an iterated local search approach. This approach works with unfeasible solutions that are penalized in the evaluation function. Moreover, it uses two movements that allow a strong intensification of the search space during the search process. We test our approach using two sets of problem instances. The first set considers well-known vehicle routing instances in the literature. The second one considers a real case in southern Chile with 500 nodes. From the results, we can demonstrate the abilities of our local search approach to solve small problem instances in reduced times and to find high-quality solutions for real-world problem instances.