An optimization approach for winner determination problem considering transportation cost discounts

This study proposes a mixed-integer nonconvex programming (MINP) model for the winner determination problem (WDP) considering two discount functions in a combinatorial auction to save shipper’s transportation cost. For the WDP, the shipper allows carriers to submit bids for a bundle of lanes. Then the winning carries are selected by solving the WDP. Specifically, this study considers the shipment distance-based and volume-based discounts for transportation cost, simultaneously. The state-of-the-art linearization technique is available to convert the MINP model into a mixed-integer linear program (MILP) to obtain a global optimum, but the solution time becomes inefficient when the problem size becomes large. To find efficient and effective linearization techniques for large-scale WDP, this study (1) proposes a novel WDP model with discount policies, (2) utilizes superior encoding formulation to avoid the unbalanced branch-and-bound trees in solving MILP, and (3) reduces big-M constraints to speed up the solving time. The proposed method leads to significant savings in computational efforts. Numerical experiments with real-world-sized truckload service procurement problems are solved by the proposed method and further confirmed the drastic reduction in computational time for solving the large-size WDP.