Solving the medium newspaper production/distribution problem

It is becoming increasingly important that the production and distribution of products be carefully coordinated. In this paper we study a problem from the newspaper industry where production and distribution are especially closely coupled since there can be no finished goods inventories. We describe the problem, give a mathematical formulation, and develop a solution strategy using heuristic search algorithms. Using data from a particular newspaper and extensive computational experiments, we find that re-using trucks that have completed earlier routes is the most important way to achieve low-cost solutions. We also compare and contrast various heuristic search algorithms.