A quadtree-based allocation method for a class of large discrete Euclidean location problems

Said Salhi, Chandra Ade Irawan

Research output: Journal PublicationArticlepeer-review

6 Citations (Scopus)

Abstract

A special data compression approach using a quadtree-based method is proposed for allocating very large demand points to their nearest facilities while eliminating aggregation error. This allocation procedure is shown to be extremely effective when solving very large facility location problems in the Euclidian space. Our method basically aggregates demand points where it eliminates aggregation-based allocation error, and disaggregates them if necessary. The method is assessed first on the allocation problems and then embedded into the search for solving a class of discrete facility location problems namely the p-median and the vertex p-center problems. We use randomly generated and TSP datasets for testing our method. The results of the experiments show that the quadtree-based approach is very effective in reducing the computing time for this class of location problems.

Original languageEnglish
Pages (from-to)23-35
Number of pages13
JournalComputers and Operations Research
Volume55
DOIs
Publication statusPublished - Mar 2015
Externally publishedYes

Keywords

  • Aggregation
  • Allocation method
  • Quadtree method
  • p-median and p-center problems

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'A quadtree-based allocation method for a class of large discrete Euclidean location problems'. Together they form a unique fingerprint.

Cite this