An improved branch-and-Benders-cut algorithm for two-stage scenario-based robust winner determination problem

This paper investigates a winner determination problem in transportation service procurement, where a shipper uses a combinatorial auction mechanism to procure transportation services from carriers. To mitigate the shipper demand uncertainty and carrier capacity disruptions, we propose a two-stage scenario-based robust winner determination model. The proposed model integrates robust optimization based on budget uncertainty sets and stochastic optimization based on probabilistic scenarios to deal with both typical operational uncertainties and potential disruptions in transportation capacity, as well as their impact on demand uncertainty. To efficiently solve large-scale problems, we develop an improved branch-and-Benders-cut (IBBC) algorithm. The IBBC algorithm features two major innovations: (1) a polynomial-time cut-lifting procedure that generates tight integrated lifted cuts by exploiting both generalized upper bound and cardinality constraints, producing facet-defining inequalities for the convex hull of mixed 0–1 knapsack sets under a mild condition; and (2) an extension of closest Benders cuts to the two-stage robust optimization framework, enabling effective cut generation for challenging max-min subproblems. Furthermore, we enhance the algorithm with a tailored warm-start procedure and a constructive local search heuristic. Numerical experiments show that the proposed 2SRWD model achieves procurement cost reductions ranging from 1.76% to 22.88% compared with stochastic programming approaches, and from 0.89% to 2.37% compared with traditional robust optimization using budget uncertainty sets. Compared with existing Benders decomposition and branch-and-check algorithms, the proposed IBBC algorithm improves computational efficiency by fivefold and threefold, respectively, while reducing solution gaps by 90% and 80%, respectively.