Solving large $$p$$ p -median problems by a multistage hybrid approach using demand points aggregation and variable neighbourhood search

A hybridisation of a clustering-based technique and of a variable neighbourhood search (VNS) is designed to solve large-scale $$p$$ p -median problems. The approach is based on a multi-stage methodology where learning from previous stages is taken into account when tackling the next stage. Each stage is made up of several subproblems that are solved by a fast procedure to produce good feasible solutions. Within each stage, the solutions returned are put together to make up a new promising subset of potential facilities. This augmented $$p$$ p -median problem is then solved by VNS. As these problems used aggregation, a cost evaluation based on the original demand points instead of aggregation is computed for each of the ‘aggregation’-based solution. The one yielding the least cost is then selected and its chosen facilities included into the next stages. This multi-stage process is repeated several times until a certain criterion is met. This approach is enhanced by an efficient way to aggregate the data and a neighbourhood reduction scheme when allocating demand points to their nearest facilities. The proposed approach is tested, using various values of $$p$$ p , on the largest data sets from the literature with up to 89,600 demand points with encouraging results. Copyright Springer Science+Business Media New York 2015