CAPACITATED LOCATION PROBLEMS ON A LINE

This paper examines capacitated facility location problems on a straight line. To serve a customer, a facility must be located within a corresponding customer neighborhood. The fixed costs of locating facilities and the unit production costs of serving a customer from a facility can depend upon their locations on the line. The authors discuss the computational complexity of several capacitated location models. For capacitated problems on a line with non-nested customer intervals, and for general capacitated problems on a line with non-nested customer intervals, and for general capacitated problems that satisfy a certain "monotonicity" property, the authors develop polynomial-time dynamic programming algorithms for (i) locating minimum cost facilities to serve all customers, and (ii) maximizing the profit by locating up to q facilities that serve some or all customers with idiosyncratic returns, penalties and demands.

  • Availability:
  • Corporate Authors:

    Operations Research Society of America

    1314 Guilford Avenue
    Baltimore, MD  United States  21202
  • Authors:
    • Mirchandani, P
    • Kohli, R
    • Tamir, A
  • Publication Date: 1996-2

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 00720579
  • Record Type: Publication
  • Files: TRIS, ATRI
  • Created Date: Apr 29 1996 12:00AM