MINIMUM CONNECTION OF GAS PIPELINES FROM TAKORADI TO ALL THE REGIONAL CAPITAL TOWNS IN GHANA By Anthony Kudjo Gborgenu B.Sc. (Mathematics and Statistics) A Thesis submitted to the Department of Mathematics, Kwame Nkrumah University of Science and Technology in Partial Fulfillment of the requirement for the degree of Master of Science (Industrial Mathematics) Institute of Distance Learning © April, 2012 CERTIFICATION 1 I hereby declare that this submission is my own work towards the M.Sc. and that, to the best of my knowledge, it contains no material previously published by another person nor material which has been accepted for the award of any other degree of the University, except where due acknowledgement has been made in the text. ANTHONY KUDJO GBORGENU PG4066210 4TH APRIL, 2012 ………………………………….. ………………… ………………… Student Name & ID Signature Date Certified by: DR. S. K. AMPONSAH …………………………….. ………………… ………………… Supervisor‟s Name Signature Date Certified by: ……………………………… ………………… ………………… Head of Dept. Name Signature Date Certified by: ……………………… …….……………… ………………….. Dean, IDL Name Signature Date DEDICATION To the King Eternal without whom I can do nothing 2 To my mother, my wife: Saviour Adzimani and all my siblings for their support. 3 ACKNOWLEDGEMENT The completion of this research represents the realization of a long awaited dream. My deepest heartfelt thanks: first of all goes to the Almighty God for granting me guidance and knowledge in coming out with this important study. I express my profound gratitude to my supervisor and mentor, Dr. S. K. Amponsah from the proposal stage to the completion stage. All these thoughtful comments were considered carefully in the final preparation of the project and they have been of invaluable help in reinforcing my own ideas as to how the findings in this text should be presented. I am also very grateful to all my lecturers in the Mathematics and Statistics Department, Kwame Nkrumah University of Science and Technology (KNUST) for being helpful and impacting knowledge in me in diverse ways. I shall forever remain indebted to the staff of the Ghana Highways Authority for providing me with all the information needed for the project. Last but not the least, I acknowledge the following people: Nixson K. Gborgenu, Saviour Adzimani and Ohene Mamucan. Ohene Mamucan helped me in typing the work and Nixson and Saviour gave me their spiritual and moral support through the entire period of this programme. 4 ABSTRACT The demand for the use of natural gas is on the increase as an energy source. Natural gas transportation requires a continuous pipeline network from the source of gas across long distance to the various destinations. The main objective involves extending gas pipelines from Takoradi to all the regional capital towns in Ghana by developing a straight forward method of locating pipeline facilities and designing pipeline networks to minimize cost and distance covered. The problem is formulated as a network of distances and the solution is presented based on Prim‟s Algorithm for minimum connections. Data on distances are obtained from the Ghana Highways Authority. In comparison, the total distance in the original network was reduced drastically by 68.79% to the new network. Solutions are provided for the environmental damages revealed by the gas pipeline network. 5 TABLE OF CONTENTS Title Page CERTIFICATION………………………..…….…………………………………………………ii DEDICATION…………………………………………………………………………………….ii ACKNOWLEDGEMENTS…………..……………………………………………………….….iii ABSTRACT……………………….…………………………………………………………..…iv TABLE OF CONTENTS….…………………..………………………………………………..…v LIST OF TABLES….………………………………………………………………………..……x LIST OF FIGURES…………………………………………………………………….………...xi CHAPTER 1 1.0 INTRODUCTION…………………………………...…………………………….………… 1 1.1 Background of the Study…………………….……………………………………….…..… 3 1.2 Statement of the Problem……………..………………………….…….……………..…..... 5 1.3 Objectives…………..………….……………………………….………………….………5 1.4 Significance of the Study……………………...…..……….………………………………6 1.5 Justification…………………..………………………………………..………………..... 6 1.6 Scope of the Study……………………………..…………………………………………7 6 1.7 Methodology…...………………….………………………………………………………7 1.8 Limitation of the Study………………………..…………………………………………..8 1.9 Organization of the Study…..……………………….…………………..…………………8 CHAPTER 2: LITERATURE REVIEW……………………...…………………………..9 2.0 Introduction………………………………………..……………………………………….9 2.1 Gas Pipeline Research…………………………………..………………………………….9 2.2 Pipeline Selection and Routing Criteria…………………………………………………..11 2.3 Optimal Networks……………………………………...…………………………………11 2.4 Review of Related Literature….…………………………..…………………………….12 2.5 Summary………………….……………………………………………………………..29 CHAPTER 3: RESEARCH METHODOLOGY……………….……………………30 3.0 Introduction ………………………………………..……………………………………..30 3.1 GENERAL PIPELINE CONSTRUCTION PROCEDURES……………………………30 3.1.1 Survey and Staking……..…………….……………………………………....………….32 3.1.2 Clearing and Grading…...……….………………………………….……………………32 3.1.3 Trenching……………………...……………………………………..…………………..32 3.1.4 Pipe Stringing, Bending, and Welding….…...………………………..…………………34 3.1.5 Lowering-In and Backfilling………….…...………………………….…………………36 3.1.6 Special Construction Procedures………...…...…………………………………………38 3.1.7 Road, Highway, and Railroad Crossings……..…………………………………………39 7 3.1.8 Steep Terrain…………………………….………………..…………………………….40 3.1.8 Water Body Crossings………………….…………………...………………………….41 3.2 ABOVEGROUND FACILITY CONSTRUCTION PROCEDURES……………………43 3.2.1 Compressor Stations……………………………………………………………………43 3.3 Physical Networks…………..……………………………...……………………………45 3.4 Network Analysis………..……………………….…………………………………......46 3.5 Network Routing…….………………………………………………………………….46 3.5.1 Metering Stations…………………………………………….…………………………47 3.5.2 The Structure and Operation Of Gas Pipeline Networks…..…..…..………..……….…48 3.5.3 General Unique Aspects of Gas Pipeline Networks………………..…………………49 3.5.4 Mode of Transportation Technology…………………...……...……………………..49 3.5.5 Continuous Transportation System……………...…………………………………….50 3.5.6 Time of Gas Transport………………………...…………….………………………..51 3.5.7 Directed Network vs. Undirected Network…...……...………………………………51 3.5.8 Advantages, Use and Transport of Natural Gas……...……….………………..……..51 3.6 Modeling the Problem……....………………...………………………………………..52 3.7 Methods of Solving Shortest Path Problems……..……………………………….……54 3.7.1 Single Source Paths (Dijkstra‟s Algorithm)………………..…………………………………………………54 3.7.2 Algorithm…………………………………...………………………………………..54 3.7.3 All-Pairs Shortest Path Problem…………...……………………..…………………….57 8 3.7.4 Floyd-Warshall Algorithm………………………………………….…………………..57 3.7.5 Minimum-Connector………………………………………….…………………………57 3.7.6 Prim‟s Algorithm………………………………………………………………………..58 3.7.6.1 Matrix Formulation of Prim‟s Algorithm…………………………………………….59 3.7.7 A Minimum Connector Problem……………………………………………………….60 3.8 Data Collection………………………………………….………………..………………61 3.9 Summary…………………………………………………………………………………61 CHAPTER 4: DATA COLLECTION AND ANALYSIS………………………..…….62 4.0 Introduction…………………………………….……………………………………......62 4.1 Computational Procedure and Analysis of Data……..…………………………….……63 4.2 Discussion…………………………...………………..……………………..…………77 4.3 Analysis……………………………………..………………..……………………….79 4.4 Environmental Value Revealed By Pipelines………………..……………………….80 4.4.1 Environmental Values as an Aid to Decision-Making…….....………….……….….80 4.4.2 Agriculture and Soils…………………………………….………………………….82 4.4.3 Water Resources and Flood Risks………….……………….………………………..82 4.4.4 Ecology……………………………………..……..…………………………………83 4.4.5 Emissions………………………..……………….…………………………………..83 4.4.6 Traffic and Transport…………………………………………………………………83 9 4.4.7 Socio-Economics……………..………………………………………………………84 4.4.8 Geology and Ground Conditions……………………………………………………..85 CHAPTER 5: CONCLUSION AND RECOMMENDATION…………...…………….86 5.0 Introduction………………………….………………………………………………86 5.1 Conclusion…………………….......………….………………………………………86 5.2 Recommendations……...…………………...………………………………………..87 REFERENCES……………………………………………………………………………….88 APPENDICES…………………...……………………………………………………………92 LIST OF TABLES Table 2.1: Results Of Objectives Function Using Prim‟s Algorithm……………………...…….13 Table 2.2: Results Of Objectives Function without Using Prim‟s Algorithm……………..……13 Table 3.1 Components of Common Physical Networks…………………………………..…….44 Table 4.1: Distance matrix of the Network………………………………...................................65 Table 4.2:Information1…………………………………………………………….…………....66 Table 4.3: Information 2…………………………………………………………..…………….67 Table 4.4: Information 3………………………………………………….……………………..68 Table 4.5: Information 4…………………………………………………..…………………….69 Table 4.6: Information 5…………………………………...……………………………………70 Table 4.7: Information 6…………………………………………………………………………71 Table 4.8: Information 7…………………………………………………………………………72 10