The High-Efficient Heuristic Algorithm Design For AP3 Problem

The three-index assignment problem (also known as AP3 problem) is a type of classic combinatorial optimization problem. It is the extension of the linear assignment problem. The aim of a linear assignment problem is to do assignment on two finite sets, which have the same cardinality. The linear assignment problem can be solved with the Hungarian Algorithm in polynomial time. The aim of a three-index assignment problem is to do assignment on three finite sets. However, the three-index assignment problem has been proved as a NP-hard problem, thus, there is no polynomial time algorithm to find the optimal solution of the three-index assignment problem. The three-index assignment problem has wide applications, thus there have been lots of heuristics proposed to solve the three-index assignment problem.In this paper, a new heuristic named Approximate Muscle Guided Beam Search is purposed to solve the three-index assignment problem. This heuristic is based on an effective strategy for NP-hard problem, the muscle (the union of optimal solutions). This new heuristic analyses the instance firstly, to generate the approximate muscle for the instance to reduce the search space, and then it uses beam search to find the solution on the approximate muscle. By using muscle and beam search to reduce the search space, this heuristic achieves a good trade-off between running time and solution quality. The experiment on the benchmark shows that, the new heuristic is able to obtain a solution with high quality while it can be employed on instances with large scale. This heuristic is not only an effective algorithm for the three-index assignment problem, but also a promising method for improving beam search.For the three-index assignment problem with large scale, in this paper, a new hyper-heuristic based on the common mathematical programming solver is purposed. The common mathematical programming solver is a tool specifically for solving mathematical programming problem, it is able to solve a small-scale problem within quite short time. While solving problem with large scale, the common mathematical programming solver is not able to solve it within a reasonable time limited by the memory size and the complexity of the problem. In this paper, a hyper-heuristic is purposed, solving a large-scale three-index assignment problem by dividing the problem instance into subproblems, and using the common mathematical programming solver to solve the subproblem to construct the solution of the primitive problem. By using a mathematical programming solver, less domain knowledge is needed to design a heuristic. The only thing needs to be done is to convert the problem into the right format of the common mathematical programming solver. It has a good portability. The experiment indicates that, this hyper-heuristic is able to handle large instances and able to get solution with high quality and it has good adaptability.