A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction
The bi-objective winner determination problem (2WDP-SC) of a combinatorial procurement auction for transport contracts is characterized by a set B  of bundle bids, with each bundle bid b?B b ? B consisting of a bidding carrier cb, a bid price pb, and a set ?b ? b of transport contracts which is a subset of the set T  of tendered transport contracts. Additionally, the transport quality qt,cb q t , c b is given which is expected to be realized when a transport contract t is executed by a carrier cb. The task of the auctioneer is to find a set X  of winning bids (X?B X ? B ), such that each transport contract is part of at least one winning bid, the total procurement costs are minimized, and the total transport quality is maximized. This paper presents a metaheuristic approach for the 2WDP-SC which integrates the greedy randomized adaptive search procedure with a two-stage candidate component selection procedure, large neighborhood search, and self-adaptive parameter setting in order to find a competitive set of non-dominated solutions. The heuristic outperforms all existing approaches. For seven small benchmark instances, the heuristic is the sole approach that finds all Pareto-optimal solutions. For 28 out of 30 large instances, none of the existing approaches is able to compute a solution that dominates a solution found by the proposed heuristic.
pareto optimization multi-criteria winner determination combinatorial auction grasp alns