本研究問題在於考慮結合服務者與顧客之觀點並假設顧客會選擇最易進入（the most accessible）之廠址接受服務條件下的廠址設立問題（facility location problem）。另外，本研究亦修正Wang、Batta和Rump[19]的顧客到達率不因顧客距離服務設施遠近不同而改變之假設，以使問題能更符合實際情形。在建立數學規劃模式後，發現本研究問題在數學規劃模式上類似無產能限制下廠址設立問題（uncapacitated facility location problem, UFLP）之數學規劃模式，但本研究問題之數學規劃模式比無產能限制下廠址設立問題之數學規劃模式更加廣泛化且更能合理應用於網路溝通設施、自動提款機、便利商店…等具服務鄰近顧客之固定服務設施的設置問題上。接著，我們嘗試發展有效率之演算法求解本研究之數學規劃模式，並以隨機方式產生例題比較本研究之演算法之所得解與其最佳解之情形。求解72,000筆例題中，利用本研究演算法求得最佳解的比率為97.99%；而其中最差的例題，所得值與最佳值之差距為該題最佳值的0.0652倍。

　　In this paper, we mainly discuss a facility location problem that is combining perspectives of customers and service providers, and we suppose customers should be served by the most accessible facilities from themselves. We also revise the assumption of Wang, Batta and Rump [19] that the arrival rates of customers never change in different distances between customers and facilities and then make the assumption closer to the real circumstance. After constructing our mathematical programming model, we find that it is similar to the mathematical programming model of uncapacitated facility location problem (UFLP), yet our model is more reasonable applications to select locations of communication networks, automatic teller machines, convenience stores, and etc. on which immobile service facilities are used by nearby customers and more elaborate than UFLP’s. In following steps, we attempt to create an efficient algorithm to solve our model and compare the solutions obtained by our algorithm and optimal solutions to the same randomly generating examples. In total 72,000 examples, the proportion that the solutions obtained by our algorithm are the same as optimal solutions is 97.99% .In the worst case, the difference between the optimal value and the objective value obtained by our algorithm is 0.0652 times the first one.

[1] M.E. Aydin, V. Yigit, and T.C. Fogarty, Two approaches to simulated annealing for uncapacitated facility location problem, submitted to European Journal of Operational Research, (2002).
[2] M.L. Balinksi, On finding integer solutions to linear programs, In Proceedings of the IBM Scientific Computing, pp.225-248, IBM, (1966).
[3] G. Cornuejols, G.L. Nemhauser, and L.A. Wolsey, The uncapacitated facility location problem, in: P.B. Mirchandani, and R.L. Francis (editors), Discrete Location Theory, pp.119-171, John Wiley an Sons, New York, (1990).
[4] D. Ghosh, Neighborhood search heuristics for the uncapacitated facility location problem, European Journal of Operation Research, Vol.150, pp.150-162(2003).
[5] S. Guha, and S. Khuller, Greedy strikes back: Improve facility location algorithm, Journal of Algorithms, Vol.31, pp.228-248(1999).
[6] K. Jain, M. Mahdian, and A. Saberi, A new greedy approach for facility location problems, In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), (2002).
[7] K. Jain, and V.V. Vazirani, Primal-dual approximation algorithms for metric facility location and k-median problems, In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp.2-13(1999).
[8] K. Jain, and V.V. Vazirani, Approximation algorithms for metric facility location and k-media problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, Vol.48, pp.274-296(2001).
[9] J.H. Jaramillo, J. Bhadury, R. Batta, On the use of genetic algorithms to solve location problems, Computers & Operations Research, Vol.29(202), pp.761-779(2002).
[10] M. Körkel, on the exact solution of large-scale simple plant location problems, European Journal of Operation Research, Vol.39, pp. 157-173(1989).
[11] A.A. Kuehn, and M.J. Hamburger, A heuristic program for locating warehouses, Management Science, Vol.9, pp.643-666(1963).
[12] M. Mahdian, E. Markakis, A. Saberi, and V.V. Vazirani, A greedy facility location algorithm analyzed using dual fitting, In Proceedings of the 5th International Workshop on Randomization and Approximation Techniques in Computer Science, Vol.2129 of Lecture Notes in Computer Science, pp.127-137(2001).
[13] M. Mahdian, Y. Ye, and J. Zhang, Improved approximation algorithms for metric facility location problems, In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), (2002).
[14] A.S. Manne, Plant location under economies-of-scale-decentralization and computation, Management Science, Vol.11, pp213-235(1964).
[15] P.B. Mirchandani, and R.L. France (editors), Discrete Location Theory, John Wiley and Sons, New York, (1990).
[16] J.F. Stollsteimer, The effect of technical change and out put expansion on the optimum number, size and location of pear marketing facilities in a California pear producing region, Ph.D. thesis, University California at Berkeley, (1961).
[17] M. Sviridenko, An improved approximation algorithm for the metric uncapacitated facility location problem, In Proceedings of the 9th conference on Integer Programming and Combinatorial Optimization (IPCO), pp.240-257(2002).
[18] M. Thorup, Quick and good facility location, In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms, (2003).
[19] Q. Wang, R. Batta, and C. M. Rump, Facility location models for immobile servers with stochastic demand, Naval Research Logistics, Vol.51, pp.137-152(2004).