کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
482280 | 1446130 | 2010 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Worst-case analysis of demand point aggregation for the Euclidean p-median problem Worst-case analysis of demand point aggregation for the Euclidean p-median problem](/preview/png/482280.png)
Solving large-scale p-median problems is usually time consuming. People often aggregate the demand points in a large-scale p-median problem to reduce its problem size and make it easier to solve. Most traditional research on demand point aggregation is either experimental or assuming uniformly distributed demand points in analytical studies. In this paper, we study demand point aggregation for planar p-median problem when demand points are arbitrarily distributed. Efficient demand aggregation approaches are proposed with the corresponding attainable worst-case aggregation error bounds measured. We demonstrate that these demand aggregation approaches introduce smaller worst-case aggregation error bounds than that of the honeycomb heuristic [Papadimitriou, C.H., 1981. Worst-case and probabilistic analysis of a geometric location problem. SIAM Journal on Computing 10, 542–557] when demand points are arbitrarily distributed. We also conduct numerical experiments to show their effectiveness.
Journal: European Journal of Operational Research - Volume 202, Issue 2, 16 April 2010, Pages 434–443