Abstract
Manufacturers are increasingly relying on third-party logistics service providers to distribute their products to retail stores. Fee tables, specifying how much to pay for each delivery based on weight and distance, are commonly used as the basis for compensating distributors for their delivery services. This paper proposes and applies an optimization model and methodology to help a large building-products manufacturer design an appropriate fee table for payments to its distributors for delivering products from regional distribution centers to retail stores. The model selects the weight and distance ranges and sets the fees for each combination of ranges, taking into account the distances and distribution of shipment weights to each store, so as to ensure adequate total compensation for each distributor while satisfying fee monotonicity and other requirements. Since our mixed integer programming model is difficult to solve using commercial solvers, we develop a tailored approach to obtain near-optimal solutions quickly. Specifically, we identify valid inequalities based on the problem's special structure to strengthen the model formulation, and develop an optimization-based procedure, that solves related network flow problems, to generate a heuristic solution. When applied to actual data from the building products manufacturer, our composite solution method, combining cutting planes and heuristic, proved to be effective (yielding heuristic solutions that are within 1% of optimality) and generated substantial savings (of nearly 10%) over the current fee table