ROW-COLUMN AGGREGATION FOR RECTILINEAR DISTANCE P-MEDIAN PROBLEMS

For large-scale p-median problems, it is common to aggregate the demand points. This size reduction via aggregation makes the problem easier to solve, but introduces error. Doing this aggregation well is difficult to prove. This paper presents a median-row-column aggregation algorithm, MRC, with provable properties including an error bound, an (attainable) upper bound on the maximum objective function error. MRC adjusts spacing of individual rows and columns to exploit problem structure. For e demand points, r rows, and c columns, the algorithm has computational order e(c + r + log e), and order e storage requirements. The authors report encouraging computational experience.

  • Availability:
  • Corporate Authors:

    Institute for Operations Research and the Management Sciences

    901 Elkridge Landing Road, Suite 400
    Linthicum, MD  United States  21090-2909
  • Authors:
    • Francis, R L
    • Lowe, T J
    • Rayco, M B
  • Publication Date: 1996-5

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 00721944
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jun 26 1996 12:00AM