On Solving A One-Dimensional Space Allocation Problem With Integer Programming

Abstract

This paper considers the location of n departments on one line. These departments are of different lengths and the material ilow between each pair of departments is known. The objective is to minimize total transportation costs given by the sum of all distance-flow products. The distance between two departments is the separation between their centroids. A binary mixed integer programming formulation is presented to solve this problem. The formulation involves ½n(n – 1) binary variables. Computational results are presented.