A hybrid ant colony algorithm for the winner determination problem

Author(s): Jun Wu , Mingjie Fan , Yang Liu , Yupeng Zhou , Nan Yang , Minghao Yin , Information Science and Technology, Northeast Normal University, Changchun, China, School of Science, Beijing University of Posts and Telecommunications, Bejing, China, CHEARI Certification & Testing Co., Ltd., Beijing, China, Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Changchun, China

Publication date Created: 2022

Publication date (Print): 2022

Journal: Mathematical Biosciences and Engineering

Publisher: American Institute of Mathematical Sciences (AIMS)

Read this article at

ScienceOpenPublisher

Bookmark

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

<abstract><p>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.</p></abstract>