BEAMR: an exact and approximate model for the p-median problem. The p-median problem is perhaps one of the most well-known location-allocation models in the location science literature. It was originally defined by Hakimi in 1964 and 1965 and involves the location of p facilities on a network in such a manner that the total weighted distance of serving all demand is minimized. This problem has since been the subject of considerable research involving the development of specialized solution approaches as well as the development of many different types of extended model formats. One element of past research that has remained almost constant is the original ReVelle-Swain formulation [C. S. ReVelle and R. Swain [Central facilities location. Geographical Anal. 2, 30–42 (1970)]. With few exceptions as detailed in the paper, virtually no new formulations have been proposed for general use in solving the classic p-median problem. This paper proposes a new model formulation for the p-median problem that contains both exact and approximate features. This new p-median formulation is called Both Exact and Approximate Model Representation (BEAMR). We show that BEAMR can result in a substantially smaller integer-linear formulation for a given application of the p-median problem and can be used to solve for either an exact optimum or a bounded, close to optimal solution. We also present a methodological framework in which the BEAMR model can be used. Computational results for problems found in the OR_library of J. E. Beasley [Eur. J. Oper. Res. 21, 270–273 (1985; Zbl 0569.90021)] indicate that BEAMR not only extends the application frontier for the p-median problem using general-purpose software, but for many problems represents an efficient, competitive solution approach.

References in zbMATH (referenced in 10 articles )

Showing results 1 to 10 of 10.
Sorted by year (citations)

  1. Drezner, Zvi; Salhi, Said: Incorporating neighborhood reduction for the solution of the planar $p$-median problem (2017)
  2. Nickel, Stefan; Velten, Sebastian: Optimization problems with flexible objectives: a general modeling approach and applications (2017)
  3. Bont, Leo Gallus; Heinimann, Hans Rudolf; Church, Richard L.: Concurrent optimization of harvesting and road network layouts under steep terrain (2015)
  4. Irawan, Chandra Ade; Salhi, Said; Scaparra, Maria Paola: An adaptive multiphase approach for large unconditional and conditional $p$-median problems (2014)
  5. Park, Gigyoung; Lee, Youngho; Han, Junghee: A two-level location-allocation problem in designing local access fiber optic networks (2014)
  6. Xi, Menghao; Ye, Feng; Yao, Zhong; Zhao, Qiuhong: A modified $p$-median model for the emergency facilities location problem and its variable neighbourhood search-based algorithm (2013)
  7. Goldengorin, Boris; Krushinsky, Dmitry: A computational study of the pseudo-Boolean approach to the $p$-median problem applied to cell formation (2011)
  8. Kaveh, A.; Shahrouzi, M.; Naserifar, Y.: Tuned genetic algorithms for finding $p$-medians of a weighted graph (2010)
  9. Matisziw, Timothy C.; Murray, Alan T.: Modeling $s-t$ path availability to support disaster vulnerability assessment of network infrastructure (2009)
  10. Church, Richard L.: BEAMR: an exact and approximate model for the $p$-median problem (2008)