Abstract :
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 di erent 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.
