Abstract: Comparing New Heuristics for the Pure Integer Capacitated Plant Location Problem

This paper considers the Pure Integer Capacitated Plant Location Problem (PI-CPLP). It is an NP-hard integer programming problem closely related to the Mixed Integer Capacitated Plant Location Problem (MI-CPLP). The difference between the two lays in the integrality constraints on the assignment variables. As opposed to MI-CPLP, in PI-CPLP, for a given set of open plants, the assignment subproblem remains NP-hard (specifically a Generalized Assignment Problem). Several heuristics are proposed, based on the following approaches: Evolutive Algorithms (EA), Greedy Randomized Adaptive Search Procedure (GRASP), Simulated Annealing (SA) and Tabu Search (TS). All the algorithms proposed share three characteristics. First, they make direct use of the problem structure. The main problem is divided in two subproblems, one for the selection of plants and another one for the assignment of clients to plants. Second, they search for feasible solutions to the PI-CPLP using the relaxation based on the aggregation of the capacity constraints. Third, they basically explore the same neighborhood structures. These structures and the strategies used to explore them are also presented. All the proposed algorithms have been tested computationally. Their performance is reported and their results are compared.