Capacitated Location Problems on a Line

Prakash Mirchandani, Rajeev Kohli and Arie Tamir
Additional contact information
Prakash Mirchandani: Joseph M. Katz Graduate School of Business, University of Pittsburgh, Pittsburgh, Pennsylvania 15260
Rajeev Kohli: Graduate School of Business, Columbia University, New York 10027
Arie Tamir: Stern School of Business, New York University, and School of Mathematical Sciences, Tel Aviv University, Israel

Transportation Science, 1996, vol. 30, issue 1, 75-80

Abstract: 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. We 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 that satisfy a certain “monotonicity” property, we 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.

Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.30.1.75 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:30:y:1996:i:1:p:75-80

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().