The uncapacitated time-space fixed-charge network flow problem: An empirical investigation of procedures for arc capacity assignment

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.