Skip to content

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

Research output: Contribution to journalArticlepeer-review

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-centre 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
JournalComputers & Operations Research
Publication statusPublished - Mar 2015


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

    Rights statement: “NOTICE: this is the author’s version of a work that was accepted for publication in 'Computers & operations research'. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in 'Computers & operations research', VOL. 55, March 2015 DOI: 10.1016/j.cor.2014.10.002

    Accepted author manuscript (Post-print), 1.02 MB, PDF document

Related information

Relations Get citation (various referencing formats)

ID: 1850865