A tractable two-stage robust winner determination model for truckload service procurement via combinatorial auctions

Abstract

A combinatorial auction is one of the adopted mechanisms for truckload (TL) service procurement. In such an auction, the shipper faces a well-known winner determination problem (WDP): the shipper, as the auctioneer, is given bids submitted by a group of carriers. In most literature, WDP is modeled as a deterministic mixed-integer program (MIP) and is solved by standard MIP algorithms. However, in practice, the exact shipping demand is unavailable until after the auction. This shipment volume uncertainty has a significant impact on the solution to WDP. Therefore, a deterministic winner determination model with an estimate of shipment volume may not provide solutions that attain low procurement costs. This paper proposes a new tractable two-stage robust optimization (RO) approach to solve WDP for TL service procurement under shipment volume uncertainty. Assuming that only historical data is available, we propose a data-driven approach based on the central limit theorem (CLT) to construct polyhedral uncertainty sets. In particular, we consider two random cases: independent shipment volume and correlated shipment volume. A two-stage RO model with integer first-stage decision variables and continuous recourse variables is then formulated. We develop a reformulation solution method and use numerical tests to demonstrate that it is much more computationally efficient than the widely adopted Benders' type constraint generation algorithm. We demonstrate by numerical tests that real-world sized instances of TL service procurement problems can be solved by our proposed robust method. Moreover, we compare our robust approach with benchmark and show that it is more tractable and robust to uncertainty.