New spatial clustering-based models for optimal urban facility location considering geographical obstacles
Tóm tắt
The problems of facility location and the allocation of demand points to facilities are crucial research issues in spatial data analysis and urban planning. It is very important for an organization or governments to best locate its resources and facilities and efficiently manage resources to ensure that all demand points are covered and all the needs are met. Most of the recent studies, which focused on solving facility location problems by performing spatial clustering, have used the Euclidean distance between two points as the dissimilarity function. Natural obstacles, such as mountains and rivers, can have drastic impacts on the distance that needs to be traveled between two geographical locations. While calculating the distance between various supply chain entities (including facilities and demand points), it is necessary to take such obstacles into account to obtain better and more realistic results regarding location-allocation. In this article, new models were presented for location of urban facilities while considering geographical obstacles at the same time. In these models, three new distance functions were proposed. The first function was based on the analysis of shortest path in linear network, which was called SPD function. The other two functions, namely PD and P2D, were based on the algorithms that deal with robot geometry and route-based robot navigation in the presence of obstacles. The models were implemented in ArcGIS Desktop 9.2 software using the visual basic programming language. These models were evaluated using synthetic and real data sets. The overall performance was evaluated based on the sum of distance from demand points to their corresponding facilities. Because of the distance between the demand points and facilities becoming more realistic in the proposed functions, results indicated desired quality of the proposed models in terms of quality of allocating points to centers and logistic cost. Obtained results show promising improvements of the allocation, the logistics costs and the response time. It can also be inferred from this study that the P2D-based model and the SPD-based model yield similar results in terms of the facility location and the demand allocation. It is noted that the P2D-based model showed better execution time than the SPD-based model. Considering logistic costs, facility location and response time, the P2D-based model was appropriate choice for urban facility location problem considering the geographical obstacles.
Tài liệu tham khảo
Anderberg M (1973) Cluster analysis for applications. Academic Press, New York
Berman O, Krass D (2002) The generalized maximal covering location problem. Comput Oper Res 29(6):563–581
Choset H, Lynch K, Hutchinson S, Kantor G, Burgard W, Kavraki L, Thrun S (2007) Principles of robot motion: theory, algorithms, and implementation (chapter 2). The MIT Press, Cambridge, MA, USA
Church R (2002) Geographical information systems and location science. Comput Oper Res 29(6):541–562
Ester M, Kriegel HP, Sander S, Xu S (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the 2nd international conference on knowledge discovery and data mining, pp 226–231
Estivill-Castro V, Houle M (2001) Robust distance-based clustering with applications to spatial data mining. Algorithmica 30(2):216–242
Galvao R, Espejo L, Boffey B (2000) A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. Eur J Oper Res 124:377–389
Geetha S, Poonthalir G, Vanathi P (2009) Improved K-means algorithm for capacitated clustering. InfoComp J 8(4):52–59
Guha S, Rastogi R, Shim K (1998) CURE: an efficient clustering algorithm for large databases. In: Proceedings of the ACM SIGMOD international conference on management of data, Seattle, pp 73–84
Kaufman L, Rousseeuw P (1990) Finding groups in data: an introduction to cluster analysis. Wiley, New York
Kaveh P, Sabzevari Zadeh A, Sahraeian R (2010) Solving capacitated p-median problem by hybrid k-means clustering and FNS algorithm. Int J Innov Manag Technol 1(4):405–410
Koperski K, Adhikary J, Han J (2001) Spatial data mining: progress and challenges. Survey paper
Liao K, Guo D (2008) A clustering-based approach to the capacitated facility location problem. Trans GIS 12(3):323–339
Likas A, Vlassis N, Verbeek J (2003) The global K-means clustering algorithm. Pattern Recognit 36(2):451–461
Ng R, Han J (1994) Efficient and effective clustering methods for spatial data mining. In: Proceedings of the 20th Conference on very large data bases, Santiago, pp 144–155
Pena J, Lozano J, Larranaga P (1999) An empirical comparison of four initialization methods for the K-means algorithm. Pattern Recognit Lett 20:1027–1040
Tung A, Ng R, Laksmanan L, Han J (2001) Constraint-based clustering in large databases. In: Proceedings of the International Conference on database theory, London, pp 405–419
Wang W, Yang J, Muntz R (1997) STING: a statistical information grid approach to partial data mining. In: Proceedings of the 23rd International Conference on very large data bases, Athens, pp 186–195
Wei G, Xin W (2010) Studies on the performance of a heuristic algorithm for static and transportation facility location allocation problem. In: Zhang W, Chen Z, Douglas CC, Tong W (eds) High performance computing applications. Lecture notes in computer science, vol 5938. Springer, Heidelberg, pp 27–37
Zarnani A, Rahgozar M, Lucas C, Taghiyareh F (2007) Spatial data mining for optimized selection of facility location s in field-based service. In: Proceedings of the IEEE International symposium of computational intelligence and data mining. IEEE Press, Hawaii, pp 734–741
Zhang J, Papadias D, Mouratidis K, Manli Z (2005) Query processing in spatial databases containing obstacles. Int J Geogr Inf Sci 19(10):1091–1111