Rapidly converging solution for p-centers in nonconvex regions

This paper aims to locate p resources in a nonconvex demand plane having n demand points. The objective of the location problem is to find the location for these p resources so that the distance from each of n demand points to its nearest resource is minimized, thus simulating a p-center problem. We employ various geometrical structures for solving this location problem. The suggested approach is also capable of finding the optimal value of p so that all demand points have at least one resource at a distance ∆, where ∆ is the maximum permissible distance for emergency services. Finally, an implementation of the proposed approach is presented and it is observed that the suggested approach rapidly converges towards the optimal location.

PDF

___

[1] Yen WCK. The connected p-center problem on block graphs with forbidden vertices. Theor Comput Sci 2012; 426: 13-24.
[2] Frederickson G. Parametric search and locating supply centers in trees. Lect Notes Comp Sci 1991; 519: 299-319.
[3] Foul A. A 1-center problem on the plane with uniformly distributed demand points. Oper Res Lett 2006; 34: 264-268.
[4] Fowler R, Paterson M, Tanimoto S. Optimal packing and covering in the plane are NP-complete. Inform Process Lett 1981; 12: 133-137.
[5] Drezner Z. The p-centre problemheuristic and optimal algorithms. J Oper Res Soc 1984; 35: 741-748.
[6] Elshaikh A, Salhi S, Nagy G. The continuous p-centre problem: an investigation into variable neighbourhood search with memory. Eur J Oper Res 2015; 241: 606-621.
[7] Suzuki A, Drezner Z. The p-center location problem in an area. Locat Sci 1996; 4: 69-82.
[8] Davoodi M, Mohades A, Rezaei J. Solving the constrained p-center problem using heuristic algorithms. Appl Soft Comput 2011; 11: 3321-3328.
[9] Rayco M, Francis R, Tamir A. A p-center grid-positioning aggregation procedure. Comput Oper Res 1999; 26: 1113-1124.
[10] Hwang R, Lee R, Chang R. The slab dividing approach to solve the Euclidean P -center problem. Algorithmica 1993; 9: 122.
[11] Elizinga J, Hearn D. Geometrical solution for some minimax location problems. Transport Sci 1972; 6: 379-394.
[12] Cheng T, Kang L, Ng C. An improved algorithm for the p-center problem on interval graphs with unit lengths. Comput Oper Res 2007; 34: 2215-2222.
[13] Dyer M, Frieze A. A simple heuristic for the p-center problem. Oper Res Lett 1985; 3: 285-288.
[14] Drezner Z. Conditional p-center problems. Transport Sci 1989; 23: 51-53.
[15] Dantrakul S, Likasiri C, Pongvuthithum R. Applied p-median and p-center algorithms for facility location problems. Expert Syst Appl 2014; 41: 3596-3604.
[16] Pollack R, Sharir M, Rote G. Computing the geodesic center of a simple polygon. Discrete Comput Geom 1989; 4: 611-626.
[17] Zarandi MHF, Davari S, Sisakht SAH. The large scale maximal covering location problem. Sci Iran 2011; 18: 1564-1570.
[18] Rourke J. Computational Geometry in C. 2nd ed. New York, NY, USA: Cambridge University Press, 1998.
[19] Berg M, Cheong O, Kreveld M, Overmars M. Computational Geometry: Algorithms and Applications. 3rd ed. Berlin: Springer-Verlag, 2008.
[20] Fortune S. A sweepline algorithm for Voronoi diagrams. Algorithmica 1987; 2: 153-174.
[21] Suzuki A, Okabe A. Using Voronoi diagrams. In: Drezner Z, editor. Facility Location: A Survey of Applications and Methods. New York, NY, USA: Springer, 1995. pp. 103-118.
[22] Huang P, Tsai Y, Tang C. A fast algorithm for the alpha-connected two center decision problem. Inform Process Lett 2003; 85: 205-210.
[23] Huang P, Tsai Y, Tang C. A near-quadratic algorithm for the alpha connected two-center problem. J Inf Sci Eng 2006; 22: 1317-1324.
[24] Davoodi M, Mohades A. Solving the constrained coverage problem. Appl Soft Comput 2011; 11: 963-969.