GUB Flow Cover Inequalities and an Exact Algorithm for Transportation Service Procurement Problem with Total Quantity Discounts

In transportation service procurement, total quantity discounts offered by a strategic carrier are incentives to a shipper. While the shipper reduces total cost by activating discounts, the carrier can win a valuable contract as considerable freight volume is assigned. Moreover, a strategic shipper would achieve even more cost reduction by purchasing more freight volume than demand and securing more discounts. The total quantity discounts are thus important to the transportation service procurement problem, which optimizes to select carriers and allocate them freight volume with the aim of minimizing the total cost for the shipper. The transportation service procurement problem with total quantity discounts (TP-TQD) can be formulated into a multiple choice model. We introduce a new formulation based on Dantzig-Wolfe reformulation for the problem, whose lower bound from LP relaxation is proved to be tighter than that of the multiple choice model. Two sets of generalized upper bound (GUB) flow cover valid inequalities are proposed to strengthen the models and applicable to any problems with structure consisting of the "more-than-demand" constraints, capacities, and GUB constraints. Effective separation methods are developed. A branch-and-price-and-cut algorithm is developed to solve the TP-TQD. Extensive experiments on a set of test instances generated from practical data are carried out to evaluate the methods. The results indicate that the new valid inequalities are effective and the exact algorithm is competent to solve problem instances of practical sizes