A variation of the generalized assignment problem arising in the New Zealand dairy industry

Within the New Zealand dairy industry, milk is collected from farms by road tanker vehicles and delivered to the factories of a dairy company for processing. Before the tankers can be scheduled to pick up the milk, each company must decide to which factory the output of each of its client farms is to be sent. We present a mathematical model of this allocation problem and solution procedures for it. The model is a variation on the generalized assignment problem. The problem is NP-hard, which reinforces the search for efficient heuristics for it. We present heuristics which yield solutions close to optimality in a reasonable amount of computing time for problems of the size commonly encountered in the dairy industry.