This Article Full Text (PDF) 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 Google Scholar Articles by Kennington, J. L. Articles by Nicholson, C. D.

The Uncapacitated Time-Space Fixed-Charge Network Flow Problem: An Empirical Investigation of Procedures for Arc Capacity Assignment

Department of Engineering Management, Information, and Systems, Southern Methodist University, Dallas, Texas 75275
Department of Engineering Management, Information, and Systems, Southern Methodist University, Dallas, Texas 75275
jlk{at}lyle.smu.edu
cd.nicholson{at}sbcglobal.net

The nodes and arcs of a network configuration replicated over time is a common structure found in many applications, particularly in the area of logistics. A common cost structure for flows in arcs for such problems involves both a fixed and variable cost. Combining the two concepts results in the uncapacitated time-space fixed-charge network flow problem. These problems can be modeled as mixed binary linear programs and can be solved with commercial software. To create these models for uncapacitated arcs requires determining artificial arc capacities that are sufficiently large so that the solution space has not been altered but are small enough that the linear programming relaxations are tight. In this investigation, we present a strategy for determining these artificial arc capacities for any time-space fixed-charge network flow problem. In extensive empirical tests, we provide statistical evidence that the strategy is superior to the usual techniques applied to this class of problem. Many of the most difficult problems were solved in only 5% of the computational time required by standard techniques.

Key words: network optimization; integer programming; logistics
History: received July 2008; revised February 2009; accepted May 2009.