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.