A hybrid ant colony algorithm for the winner determination problem

Abstract

Combinatorial auction is an important type of market mechanism, which can help bidders to bid on the combination of items more efficiently. The winner determination problem (WDP) is one of the most challenging research topics on the combinatorial auction, which has been proven to be NP-hard. It has more attention from researchers in recent years and has a wide range of real-world applications. To solve the winner determination problem effectively, this paper proposes a hybrid ant colony algorithm called DHS-ACO, which combines an effective local search for exploitation and an ant colony algorithm for exploration, with two effective strategies. One is a hash tabu search strategy adopted to reduce the cycling problem in the local search procedure. Another is a deep scoring strategy which is introduced to consider the profound effects of the local operators. The experimental results on a broad range of benchmarks show that DHS-ACO outperforms the existing algorithms.

Keywords

• ant colony algorithm
• local search
• combinatorial auction
• winner determination problem
• tabu search