A linear-time crystal-growth algorithm for discretization of continuum approximation

Hongqiang Fan, Lifen Yun and Xiaopeng Li

Transportation Research Part E: Logistics and Transportation Review, 2022, vol. 161, issue C

Abstract: Continuous approximation is regarded as a scalable and insightful method for acquiring near-optimum solutions to various location problems. A continuous approximation solution is nonetheless only a continuous density function and a further discretization procedure is needed to obtain a discrete location solution for engineering practice. Inspired by the process of “crystal growth”, this paper proposes a constructive heuristic algorithm as an alternative to the classic meta-heuristic disk algorithm (Ouyang and Daganzo, 2006) in discretizing a continuous solution from a continuum approximation location model. The main idea of this algorithm is to rasterize the space into a set of small cells (either regular triangles or squares) and repeatedly grow a core cell into a full-service area according to a certain visiting sequence. Thus, it has only linear time complexity proportional to the number of cells in the space. Numerical examples are conducted to test the performance of the proposed algorithm. The results indicate that this algorithm can solve discrete facility locations more efficiently and exhibits robust performance compared with the disk algorithm.

Keywords: Continuum approximation; Discretization; Facility location; Spatial searching (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554522001065
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:161:y:2022:i:c:s1366554522001065

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2022.102715

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().