TY - JOUR
T1 - A tractable two-stage robust winner determination model for truckload service procurement via combinatorial auctions
AU - Zhang, Bo
AU - Yao, Tao
AU - Friesz, Terry L.
AU - Sun, Yuqi
N1 - Funding Information:
The authors gratefully appreciate the insightful comments from the three anonymous reviewers. This research was partially supported by the grant award CMMI-0900040 from the National Science Foundation (NSF) and the grant awards from the Mid-Atlantic Universities Transportation Center (MAUTC).
Publisher Copyright:
© 2015 Elsevier Ltd.
PY - 2015/8/1
Y1 - 2015/8/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84928668989&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84928668989&partnerID=8YFLogxK
U2 - 10.1016/j.trb.2015.03.019
DO - 10.1016/j.trb.2015.03.019
M3 - Article
AN - SCOPUS:84928668989
SN - 0191-2615
VL - 78
SP - 16
EP - 31
JO - Transportation Research Part B: Methodological
JF - Transportation Research Part B: Methodological
ER -