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

Said Salhi; Chandra Ade Irawan

doi:10.1016/j.cor.2014.10.002

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

Said Salhi, Chandra Ade Irawan

Research output: Contribution to journal › Article › peer-review

160 Downloads (Pure)

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-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 language	English
Pages (from-to)	23-35
Journal	Computers & Operations Research
Volume	55
DOIs	https://doi.org/10.1016/j.cor.2014.10.002
Publication status	Published - Mar 2015

Keywords

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

Access to Document

10.1016/j.cor.2014.10.002

A quadtree-based allocation method for a class of large discrete Euclidean location problems
“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

Cite this

@article{ac285087d6764b5493dc4baa859f21d8,

title = "A quadtree-based allocation method for a class of large discrete Euclidean location problems",

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-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.",

keywords = "Allocation method, Quadtree method, p-median and p-center problems, Aggregation",

author = "Said Salhi and Irawan, {Chandra Ade}",

note = "“NOTICE: this is the author{\textquoteright}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",

year = "2015",

month = mar,

doi = "10.1016/j.cor.2014.10.002",

language = "English",

volume = "55",

pages = "23--35",

journal = "Computers & Operations Research",

issn = "0305-0548",

publisher = "Elsevier Limited",

}

TY - JOUR

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

AU - Salhi, Said

AU - Irawan, Chandra Ade

N1 - “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

PY - 2015/3

Y1 - 2015/3

N2 - 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.

AB - 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.

KW - Allocation method

KW - Quadtree method

KW - p-median and p-center problems

KW - Aggregation

U2 - 10.1016/j.cor.2014.10.002

DO - 10.1016/j.cor.2014.10.002

M3 - Article

SN - 0305-0548

VL - 55

SP - 23

EP - 35

JO - Computers & Operations Research

JF - Computers & Operations Research

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this