A food network design problem: a case study

In this work, we deal with a food distribution problem that can be considered as a generalization of the asymmetric capacitated vehicle routing problem with split delivery. In particular, we are involved with a real application related to an Italian company that holds food markets along the national highway network and has to determine the distribution plan of two types of products, namely, fresh/dry and frozen food. Given a depot, a set of customers and a fleet of vehicles, the goal is to minimize the total travelling costs, which include fixed costs of the vehicles and the travelling costs proportional to the distance travelled, while satisfying operative and customer requirement constraints. We first present a mixed-integer programming model for the problem, then a two-step heuristic procedure that is particularly suitable for the network structure under consideration. More precisely, we initially determine clusters of customers on the basis of the specifications derived from perishable goods together with the routes of vehicles in each cluster and successively we use a local-search improvement algorithm for reducing the routing costs by changing customers among routes and splitting customers' demand. In our computational experimentation, we use both instances derived from the real operative scenario and random instances and validate the proposed approach using other classical ones. Moreover, a work bench is reported for validating the effectiveness of the execution of the proposed first phase for guaranteeing good initial solutions and evaluating the impact of the initial solution on the final one.