The single facility location problem with minimum distance constraints |
| |
| Affiliation: | 1. Faculty of Science, Kunming University of Science and Technology, Kunming 650093, China;2. School of Nuclear Engineering and Geophysics, East China Institute of Technology, Nanchang 330013, Jiangxi, China;3. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;4. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China;5. Department of Statistics, Feng Chia University, Taichung, Taiwan;1. Section de Mathématiques, Université de Genève, 2-4 rue du Lièvre, CH-1211, Genève, Switzerland;2. Institut für Mathematik, Universität Würzburg, Campus Hubland Nord, Emil-Fischer-Straße 30, 97074 Würzburg, Germany;1. Department of e-Business, School of Information, Central University of Finance and Economics, Beijing, 100081, PR China;2. School of Statistics, Renmin University of China, Beijing, 100872, PR China;3. Center for Applied Statistics, Renmin University of China, Beijing, 100872, PR China;4. Consulting Center of Statistics, Renmin University of China, Beijing, 100872, PR China |
| |
| Abstract: | We consider the problem of locating a single facility (server) in the plane, where the location of the facility is restricted to be outside a specified forbidden region (neighborhood) around each demand point. Two models are discussed. In the restricted 1-median model, the objective is to minimize the sum of the weighted rectilinear distances from the n customers to the facility. We present an O(n log n) algorithm for this model, improving upon the O(n3) complexity bound of the algorithm by Brimberg and Wesolowsky (1995). In the restricted 1-center model the objective is to minimize the maximum of the weighted rectilinear distances between the customers and the serving facility. We present an O(n log n) algorithm for finding an optimal 1-center. We also discuss some related models, involving the Euclidean norm. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
