Rajeev Kohli

Capacitated Location Problems on a Line

Coauthor(s): Prakash Mirchandani, Arie Tamir.


Adobe Acrobat PDF

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.

Source: Transportation Science
Exact Citation:
Mirchandani, Prakash, Rajeev Kohli, and Arie Tamir. "Capacitated Location Problems on a Line." Transportation Science 30, no. 1 (February 1996): 75-80.
Volume: 30
Number: 1
Pages: 75-80
Date: 2 1996