Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm

Abstract

In this paper, we are interested in the unbalanced assignment problem with constraints to agents. The modified Hungarian algorithm with dummy tasks and agents are most common methods to solve the unbalanced problem. However, it is impractical in the real scenarios sometimes since some tasks are unassigned actually using the above method. Instead, we propose a graph based twin cost matrices method with improved ant colony optimization algorithm to solve the assignment problem elegantly and uniformly. We start from the generation of the twin cost matrices, and modify the ant colony algorithm to be capable to assign tasks to agents with different numbers. Random mutation is conducted for the stable pheromones to help the ant colony keep diversity during the operation. Experiments demonstrates that using our proposed method to solve the unbalanced assignment problem can stably obtain better results than previous methods.

Keywords

• Unbalanced assignment problem
• Assignment problem
• Ant colony algorithm
• Combinatorial optimization problem
• Mutation