An Ant Colony Optimization Approach to the Multiple-Choice Multidimensional Knapsack Problem

摘要

In this paper, we present an ant colony optimization (ACO) approach to solve the multiple-choice multidimensional knapsack problem (MMKP). This problem concerns many real life problems, and is hard to solve due to its strong constraints and NP-hard property. The ACO approach given in this paper follows the algorithmic scheme of max-min ant system, but has some new features with respect to the characteristics of the MMKP. First, a single-group-oriented solution construction method is proposed, which allows ants to generate solutions efficiently. Second, some Lagrangian dual information obtained from a Lagrangian relaxation of MMKP is integrated into ACO. In addition, we develop a novel repair operator, with which the possible infeasible solutions generated by ants can be fixed. The proposed approach has been tested on a number of MMKP instances. Computational results show that it is able to produce competitive solutions in comparison with existing algorithms.