There are many practical decision problems that fall into the category of network flow problems: numerous examples of applications can be found in areas such as telecommunications, logistics, distributions, engineering, computer science and so on. One of the most popular and valuable tools to solve network flow problems of a topological nature is the use of linear programming models. An important extension of these models is that of integer programming models that deal with problems where some, or all, of the variables are required to assume integer variables. A significant application in this class of problems is the knapsack problem that arises in different contexts such as loading containers in aircraft or satisfying the demand for various lengths of cloth which must be cut from fixed length bolts of fabric.
In this study, the feasibility of representing a network flow model in a tree network model and subsequently solving it using a tree knapsack approach is investigated. To compare and validate the proposed technique, a specific case study was chosen from the literature that can be used as a basis for the research project. The said study was an oil pipeline design problem, addressed by Brimberg et al. (2003). This focuses on the optimal design of an oil pipeline network for the South Gabon oil field in Africa. The objective was to reduce oil transportation costs to a major port. Following an overview of different network flow and knapsack models, an overview of the said matter is presented. A description of the proposed tree knapsack approach and the application of this approach to the given problem is given. Results have indicated that it is feasible to apply a tree knapsack approach to solve network flow problems. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2011.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:nwu/oai:dspace.nwu.ac.za:10394/4434 |
| Date | January 2010 |
| Creators | Baitshenyetsi, Tumo |
| Publisher | North-West University |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0015 seconds