Selecting unique suppliers through winner determination in combinatorial reverse auction: scatter search algorithm

In this paper, a combinatorial reverse auction mechanism is proposed to select suppliers for required items of a company. As a contribution, it is assumed that the task of supplying each required item is indivisible to multiple suppliers or the company prefers to select only one supplier for supplying each required item. So, the winner determination process is done in such a way that supplying each tendered item is assigned to only one potential supplier. The corresponding winner determination problem is formulated as a binary integer program which is an NP-complete combinatorial optimization problem. Since exact methods are failed in solving this kind of problems in a reasonable time, a meta-heuristic algorithm called scatter search is proposed for finding feasible and near-optimal solutions of the formulated winner determination problem. For evaluating the performance of the proposed algorithm, several instances of the problem with different real-world sizes are randomly generated and solved using the proposed algorithm with tuned parameters. Computational results show that the proposed scatter search method performs well in solving the problem instances.