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

Chandra Ade Irawan, Said Salhi, Maria Paola Scaparra

Research output: Contribution to journalArticlepeer-review

142 Downloads (Pure)


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
JournalEuropean Journal of Operational Research
Issue number2
Early online date31 Jan 2014
Publication statusPublished - 1 Sept 2014


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


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