Dual search procedures for the exact formulation of the simple plant location problem with spatial interaction

This paper presents an exact formulation of the simple plant location problem with spatial interaction. The formulation is based on the derivation of the spatially interactive travel behavior, often described through a spatial ‘gravity’ model. Using techniques from separable programming, the paper derives an exact formulation of the problem, i.e. without using any approximation of the function that describes the spatially interactive travel behavior. The resulting model is a pure zero-one location model. The paper also presents a dual ascent and adjustment procedure for the linear programming relaxation of the exact formulation of the simple plant location problem with spatial interaction. Furthermore, it presents a solution method based on Lagrangean relaxation and subgradient optimization. The two dual search procedures are computationally tested on problems with a maximal size of 50×100.