Solving Large 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-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-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, on

the largest data sets from the literature with up to 89,600 demand points with encouraging

results.