Skip to main content

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)

PDF - Author's Accepted Manuscript
Download (475kB) Preview
[img]
Preview
Official URL
http://dx.doi.org/10.1007/s10898-013-0080-z

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: Faculties > Social Sciences > Kent Business School
Faculties > Social Sciences > Kent Business School > Management Science
Faculties > Social Sciences > Kent Business School > Centre for Logistics and Heuristic Organisation (CLHO)
Depositing User: Said Salhi
Date Deposited: 27 Jun 2013 14:12 UTC
Last Modified: 29 May 2019 10:20 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/34434 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year