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 the 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 have failed to solve this kind of problems in a reasonable time, a meta-heuristic algorithm called scatter search is proposed to nd feasible and near-optimal solutions to the formulated winner determination problem. To evaluate the performance of the proposed algorithm, several instances of the problem with dierent 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.