Heuristic algorithms for solving the interval flow transshipment network

This dissertation addresses the inclusion of semi-continuous variables into network formulations for minimum cost-flow transshipment problems with and without a fixed charge. These models, termed interval-flow networks, are formulated mathematically and solution methods are proposed and tested computationally. Chapter 1 presents the mathematical model formulations for different versions of the interval-flow transshipment network including uniform and non-uniform conditional lower bounds, and models with and without a fixed charge component. Example real-world applications are presented with simple models showing the diverse areas where the interval-flow network is useful. In chapter 2, the initial heuristic for solving the interval-flow network problem is presented. This heuristic uses the tree structure of a pure network to perform simple pivots in an attempt to find an interval-flow basic feasible solution. Once found, the heuristic attempts to improve the solution through a method of strategic oscillation. The solution time and quality of sample problems is compared to state-of-the-art commercially available software. Chapter 3 presents a heuristic for solving the interval-flow network problem with the addition of a fixed charge component. This heuristic starts with the best heuristic from chapter 2 and expands it to include the fixed charge in the solution. The solution time and quality of sample problems is compared to state-of-the-art commercially available software. The test problems used in chapters 2 and 3 are randomly generated networks with randomly placed fixed charges and conditional lower bounds. In chapter 4, upper bound constraints are added to the algorithm. An example real-world scheduling problem is solved along with the well known 2-partition problem. Chapter 5 presents a summary of the results. An appendix is also presented describing the test sets that were used for this dissertation and the programs that were used to create them.