Abstract
Combinatorial auctions, in which trucking companies bid on contracts for bundles of lanes, rather than single ones, hold significant promise for adding efficiencies to contracts for freight transportation services. However, the problems faced by bidders (trucking companies) and auctioneers (large shippers) in order to effectively bid and select contract winners are very computationally complex â?? preventing widespread adoption of such auctions to date. In this research the authors provide heuristics for solving combinatorial auctions for freight procurement and demonstrate that complicated side constraints (favoring incumbents, creating backup assignments, and minimizing the number of winning carriers) can be considered â?? benefiting both shippers and carriers. The authors do this in a setting where carriers can bid on as many lanes or packages as they wish and in which shippers explicitly consider carrier capacities when assigning contracts. Empirical analysis shows that othe authors heuristics, based on the LP rounding technique developed by Shmoys and Tardos for the generalized assignment problem have very good performance.