A sampling based FANT for the 3-Dimensional Assignment Problem

In this paper, we proposed a sampling based FANT (S-FANT) for the 3-dimensional assignment problem (AP3). The AP3 is a well-known NP-hard problem, which aims to choose n disjoint triplets with minimum cost from 3 disjoint sets of size n. Due to its intractability, many heuristics have been proposed to obtain near optimal solutions in reasonable time. Since the solution space size of the AP3 is (n!)², traditional FANT algorithms canpsilat work well for the AP3. In this paper, we showed that, those triplets frequently contained by local optimal solutions are likely to belong to global optimal solutions. Therefore, those triplets can help the ant to converge faster to global optimal solutions. Upon the observation above, the S-FANT consists of two phases. In the sampling phase, a multi-restart scheme is employed to generate local optimal solutions. After that, the pheromone is initialized according to the frequency of triplets appearing in those local optimal solutions. In the FANT phase, a standard FANT algorithm is conducted to explore for better solutions. Extensive experimental results on the standard AP3 benchmark indicated that the new algorithm outperforms the state-of-the-art heuristics in terms of solution quality. Work of this paper not only provides a new efficient heuristic for the AP3, but shows a promising way to design FANT algorithms for those NP-hard problems with large solution space.