Solving a real-world wheat blending problem using a hybrid evolutionary algorithm

Abstract

A novel hybrid algorithm is proposed to solve the Australian wheat blending problem. The major part of the problem can be modeled with a linear programming model but the unique constraints make many existing algorithms fail. The algorithm starts with a heuristic that follows pre-defined rules to reduce the search space. Then the linear-relaxed problem is solved using a standard linear programming algorithm, and the result is used to guide an evolutionary-based algorithm while exploring the infeasible regions. Constraint violations are de-penalised if the same choice is made in the linear-relaxed solution. In fact, a hybrid of an evolutionary algorithm, a heuristic method and a linear programming solver is used in the main loop to improve the solution while maintaining the feasibility. A heuristic based initialization method and a local search based post-tuning method are also incorporated into the algorithm. The proposed algorithm has been tested on real data from past years, from small to large cases. Results show that the algorithm is able to find quality results in all cases and outperforms the existing method in use in terms of both quality and speed.