This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ravi, R. Articles by Sinha, A. Search for Related Content

Approximation Algorithms for Problems Combining Facility Location and Network Design

David A. Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Stephen M. Ross School of Business, University of Michigan, Ann Arbor, Michigan 48109
ravi{at}cmu.edu
amitabh{at}umich.edu

We present approximation algorithms for integrated logistics problems that combine elements of facility location and transport network design. We first study the problem where opening facilities incurs opening costs and transportation from the clients to the facilities incurs buy-at-bulk costs, and provide a combinatorial approximation algorithm. We also show that the integer-programming formulation of this problem has small integrality gap. We extend the model to the version when there is a bound on the number of facilities that may be opened.

Subject classifications: facilities; location; discrete; networks/graphs; flow algorithms; transportation; models; networks.
History: Received June 2003; revision received January 2004; revision received September 2004; accepted October 2004.

This article has been cited by other articles:

				T. Yamada, B. F. Russ, J. Castro, and E. Taniguchi Designing Multimodal Freight Transport Networks: A Heuristic Approach and Applications Transportation Science, May 1, 2009; 43(2): 129 - 143. [Abstract] [PDF]