An adaptive multiphase approach for large unconditional and conditional p-median problems

Chandra Ade Irawan, Said Salhi, Maria Paola Scaparra

Research output: Journal PublicationArticlepeer-review

31 Citations (Scopus)

Abstract

A multiphase approach that incorporates demand points aggregation, Variable Neighbourhood Search (VNS) and an exact method is proposed for the solution of large-scale unconditional and conditional p-median problems. The method consists of four phases. In the first phase several aggregated problems are solved with a "Local Search with Shaking" procedure to generate promising facility sites which are then used to solve a reduced problem in Phase 2 using VNS or an exact method. The new solution is then fed into an iterative learning process which tackles the aggregated problem (Phase 3). Phase 4 is a post optimisation phase applied to the original (disaggregated) problem. For the p-median problem, the method is tested on three types of datasets which consist of up to 89,600 demand points. The first two datasets are the BIRCH and the TSP datasets whereas the third is our newly geometrically constructed dataset that has guaranteed optimal solutions. The computational experiments show that the proposed approach produces very competitive results. The proposed approach is also adapted to cater for the conditional p-median problem with interesting results.

Original languageEnglish
Pages (from-to)590-605
Number of pages16
JournalEuropean Journal of Operational Research
Volume237
Issue number2
DOIs
Publication statusPublished - 1 Sept 2014
Externally publishedYes

Keywords

  • Adaptive learning
  • Aggregation
  • Exact method
  • Large p-median problems
  • Variable neighbourhood search

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'An adaptive multiphase approach for large unconditional and conditional p-median problems'. Together they form a unique fingerprint.

Cite this