Distribution product packaging to maximize net revenue

This paper studies a problem in which a distribution center of a chain store packages a small subset of a large number of available products (e.g. DVDs) to distribute to its local stores. Only a limited number of different packages are allowed. We determine what products are in each package and what package to distribute to each store for revenue maximization. A column generation method is developed in which the sub-problem generates candidate packages and corresponding stores to serve while the master problem determines the final packages on the production lines. Two heuristic methods are proposed to generate the candidate packages for the sub-problem. Bounds are derived for both the optimal number of packages and the total revenue in order to expedite the solution. The algorithm shows great promise with operational data from a chain store that serves several thousand retail locations.