The General Equal Arcs Flow in The Multicommodity Network Flow Problem

Abstract

In this paper the multicommodity network flow problem with equal flow on some predetermined arcs is considered. The equal flow constraints require that the amounts of arcs flow of some commodities on some subsets of predetermined arcs, are equal. For solving this problem, first, using the capacity allocation algorithm, we define a starting solution. Then by lagrangian relaxation technique on general constraints we find a lower bound on the objective function value. An upper bound is also found by using embedded network simplex method. Finally, The optimal or near optimal solution is found when the upper and lowers bounds are made close enough to each other.

Keywords