Decomposition Algorithm in Fixed Charge Time-Space Network Flow Problems

Abstract

A wide range of network flow problems primarily used in transportation is categorized as time-space fixed charge network flow (FCNF) problems. In this family of networks, each node is associated with a specific time and is replicated across all time-periods. The cost structure in these problems consists of variable and fixed costs where continuous and binary variables are required to formulate the problem as a mixed integer linear programming. FCNF problems are classified as NP-hard problems, therefore, adding another component (i.e., time) to this type of problem results in a complex problem which is time-consuming and CPU and memory intensive. Various exact and heuristic methods have been proposed and implemented to solve FCNF problems. In this work, a decomposition heuristic is proposed that subdivides the problem into various time epochs to create smaller and more manageable subproblems. These subproblems are solved sequentially to find an overall solution for the original problem. To evaluate the capability and efficiency of the decomposition method vs. exact method, a total of 1600 problems is generated and solved using Gurobi MIP solver, which runs parallel branch & bound algorithm. Statistical analysis indicates that depending on the problem specification, the average solution time in decomposition methods is improved by up to four orders of magnitude. While statistically, there is a significant difference between the mean objective value of exact method and each TPV configuration in both decomposition methods, however, the average difference (0-2.16% in decomposition and 1.55-7.85% in decomposition method with relaxation) may not be a serious concern for many practical large-scale problems. This shows great promise for decomposition method to significantly reduce the solution time which has been an outstanding issue in complicated large-scale problems.