A robust winner determination problem for combinatorial transportation auctions under uncertain shipment volumes

• A robust winner determination problem for the procurement of transportation services with uncertain shipment volumes is proposed.
• A 2-stage robust formulation is proposed and solved using a constraint generation algorithm.
• The proposed approach shows good computational performances.
• Considerable monetary losses could be avoided when robust solutions are chosen rather than deterministic ones.

Combinatorial auctions are widely used for the procurement of transportation services. In these auctions, shippers act as auctioneers who need to outsource a number of transportation services to external carriers. Carriers compete by submitting bids on packages of shippers’ requests. After receiving all carriers’ bids, the shipper solves the well-known winner determination problem (WDP) in order to determine winning bids. This paper considers the WDP in a context where shipment volumes are not known with certainty. Based on the bi-level characteristic of the problem, a 2-stage robust formulation is proposed and solved using a constraint generation algorithm. Experimental results show a good performance of the proposed approach. We also evaluate, through an experimental analysis, the benefits of considering a robust rather than a deterministic WDP.