k-most suitable locations selection

Yu Chi Chung, I. Fang Su, Chiang Lee

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

Choosing the best location for starting a business or expanding an existing enterprize is an important issue. A number of location selection problems have been discussed in the literature. They often apply the Reverse Nearest Neighbor as the criterion for finding suitable locations. In this paper, we apply the Average Distance as the criterion and propose the so-called k-most suitable locations (k-MSL) selection problem. Given a positive integer k and three datasets: a set of customers, a set of existing facilities, and a set of potential locations. The k-MSL selection problem outputs k locations from the potential location set, such that the average distance between a customer and his nearest facility is minimized. In this paper, we formally define the k-MSL selection problem and show that it is NP-hard. We first propose a greedy algorithm which can quickly find an approximate result for users. Two exact algorithms are then proposed to find the optimal result. Several pruning rules are applied to increase computational efficiency. We evaluate the algorithms’ performance using both synthetic and real datasets. The results show that our algorithms are able to deal with the k-MSL selection problem efficiently.

Original languageEnglish
Pages (from-to)661-692
Number of pages32
JournalGeoInformatica
Volume22
Issue number4
DOIs
Publication statusPublished - 2018 Oct 1

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Geography, Planning and Development

Fingerprint

Dive into the research topics of 'k-most suitable locations selection'. Together they form a unique fingerprint.

Cite this