TY - JOUR ID - 880 TI - Winner Determination in Combinatorial Auctions using Hybrid Ant Colony Optimization and Multi-Neighborhood Local Search JO - Journal of AI and Data Mining JA - JADM LA - en SN - 2322-5211 AU - Dowlatshahi, M. B. AU - Derhami, V. AD - Computer Engineering Department, Yazd University, Yazd, Iran. Y1 - 2017 PY - 2017 VL - 5 IS - 2 SP - 169 EP - 181 KW - Winner Determination Problem KW - Combinatorial Auctions KW - Ant Colony Optimization KW - Multi-Neighborhood Search KW - Combinatorial Optimization DO - 10.22044/jadm.2017.880 N2 - A combinatorial auction is an auction where the bidders have the choice to bid on bundles of items. The WDP in combinatorial auctions is the problem of finding winning bids that maximize the auctioneer’s revenue under the constraint that each item can be allocated to at most one bidder. The WDP is known as an NP-hard problem with practical applications like electronic commerce, production management, games theory, and resources allocation in multi-agent systems. This has motivated the quest for efficient approximate algorithms both in terms of solution quality and computational time. This paper proposes a hybrid Ant Colony Optimization with a novel Multi-Neighborhood Local Search (ACO-MNLS) algorithm for solving Winner Determination Problem (WDP) in combinatorial auctions. Our proposed MNLS algorithm uses the fact that using various neighborhoods in local search can generate different local optima for WDP and that the global optima of WDP is a local optima for a given its neighborhood. Therefore, proposed MNLS algorithm simultaneously explores a set of three different neighborhoods to get different local optima and to escape from local optima. The comparisons between ACO-MNLS, Genetic Algorithm (GA), Memetic Algorithm (MA), Stochastic Local Search (SLS), and Tabu Search (TS) on various benchmark problems confirm the efficiency of ACO-MNLS in the terms of solution quality and computational time. UR - https://jad.shahroodut.ac.ir/article_880.html L1 - https://jad.shahroodut.ac.ir/article_880_fa4a4182279cdf654e64ae5d275c387b.pdf ER -