ANT COLONY ALGORITHM FOR SOLVING WINNER DETERMINATION PROBLEM IN REVERSE COMBINATORIAL AUCTION

摘要

A common model is formulated for solving the winner determination problem of reverse combinatorial auction. A PRIM (Preprocessing Rules-Based Improved MMAS) algorithm is adopted for the problem. Three preprocessing rules was proved to be feasibility. By applying two of the preprocessing rules before serching begins, noncompetitive bids can be removed efficiently and the bid scale was decreased. By using the other preprocessing rule in every round of serch, unnecessary trials will be avoid early. Simulation results show that the PRIM algorithm achieves good performance than MMAS in different size problems. Meanwhile PRIM performs more steadly than MMAS as the number of bidders increase.