k-most suitable locations selection

Yu Chi Chung, I. Fang Su, Chiang Lee

研究成果: Article同行評審

4 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)661-692
出版狀態Published - 2018 10月 1

All Science Journal Classification (ASJC) codes

  • 資訊系統
  • 地理、規劃與發展


深入研究「k-most suitable locations selection」主題。共同形成了獨特的指紋。