Finding feasible solutions for multi-commodity flow problems

Many transportation, communications, and logistics problems can be formulated as large multi-commodity flow problems, which are often solved using the traditional column generation method. During the application of the column generation, one needs to find initial solutions, so-called feasible columns in a first step. In order to determine these feasible columns and also solve dependent price problems within an acceptable time, this paper proposes several novel methods: Two methods by solving the global problem and two methods by finding the shortest and widest paths are proposed to compute the initial columns. Furthermore, we propose two methods by finding the shortest paths with commodities and sources (SPC and SPS) for solving price problems. Several well-known network instances are used as case studies in our evaluation to test the efficiency of each method. It is shown that the widest-path method is the best for finding initial columns. For solving the price problems, the preference of the two path-finding methods depend on the network structure.