Abstract

This dissertation focuses on the development of optimization methods and approximation algorithms for combinatorial auctions, particularly with application to the contract procurement problem in freight transportation. Combinatorial auctions are auctions in which a set of heterogeneous items are sold simultaneously and in which bidders can bid for their preferred combinations of items. They involve many difficult optimization problems both for auction hosts and bidders and have received significant attention from computer scientists, operations researchers and economists recently. Large shippers (typically manufacturing companies or retailers) have begun to use this method to procure services from trucking companies and logistics services providers. This dissertation first analyzes the economic impact of combinatorial auction-based procurement methods both on shippers and carriers using a simulation study and reveals that both parties can benefit from this economically efficient price discovery mechanism. While the majority of prior research has been from an auctioneer’s perspective, we demonstrate that bidders have even more complicated optimization problems in combinatoiral auctions. The bid construction problem, that is, how bidders should identify and construct beneficial bids, is very hard and remains an open question. This dissertation investigates this problem and proposes an optimization based approximation method that involves solving an NP-hard problem only once, yielding significant improvements in computational efficiency. Further, the current state of trucking and third party logistics industries are examined. The trucking industry is very competitive and small carriers are operating under thin margins. This dissertation addresses these issues by proposing an auction based collaborative carrier network in which participating carriers can identify inefficient lanes from daily operations quickly and exchange them with partners under an auction protocol. This system is proved to be Pareto efficient. Further, decision problems are discussed regarding how carriers should identify inefficient operations and how to make and select bids. This represents an effort to use advanced auction mechanisms to enhance the carriers’ operational efficiencies.