Skip to main content
Kent Academic Repository

Solving Large p-median Problems by a Multistage Hybrid Approach Using Demand Points Aggregation and Variable Neighbourhood Search

Irawan, Chandra A., Salhi, Said (2015) Solving Large p-median Problems by a Multistage Hybrid Approach Using Demand Points Aggregation and Variable Neighbourhood Search. Journal of Global Optimization, 63 . pp. 537-554. ISSN 0925-5001. (doi:10.1007/s10898-013-0080-z) (KAR id:34434)

Abstract

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.

Item Type: Article
DOI/Identification number: 10.1007/s10898-013-0080-z
Uncontrolled keywords: Variable neighbourhood search · Location problem · Aggregation · p-median
Subjects: H Social Sciences
H Social Sciences > HA Statistics > HA33 Management Science
Divisions: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User: Said Salhi
Date Deposited: 27 Jun 2013 14:12 UTC
Last Modified: 19 Sep 2023 15:04 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/34434 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.