A network-based primal-dual heuristic for the solution of multicommodity network flow problems

In this paper, the authors present a primal-dual, heuristic solution approach for large-scale multicommodity network flow problems. The original problem is solved indirectly by repeatedly solving restated feasibility problems. Restrictions on problem size imposed by exact methods are overcome by solving the restated problems with a pure network-based heuristic procedure. To control the heuristic solution process, the network-based procedure is embedded within an iterative primal-dual framework. At each iteration, feasible dual solutions are generated, the dual objective function value strictly ascends, and primal solutions that are measurably closer to feasibility are determined. The algorithm terminates when the heuristic network-based procedure cannot determine an improved primal solution or when optimality is achieved. To demonstrate the effectiveness of the network-based solution strategy, a large-scale freight assignment problem encountered in the trucking industry is formulated as a multicommodity network flow problem. Two linear programming based, exact solution strategies (a primal-dual algorithm and a price-directive algorithm) are unable to achieve even an initial solution for this problem due to excessive memory requirements. The network-based heuristic, however, determines an optimal solution. The authors compare the performance of the new heuristic with that of the exact procedures using a set of smaller test problems. The effects of problem formulation and congestion are evaluated for each of the alternative solution strategies.