ABSTRACT Title of Thesis: OPTIMIZATION MODELS FOR RUNWAY LOCATION, ORIENTATION AND LONGITUDINAL-GRADE DESIGN Tong Zhou, Master of Science, 2014 Directed By: Professor Paul Schonfeld Department of Civil Engineering Airfield design is challenging for several reasons. It is limited by various constraints, such as airport usability, airspace clearance standards and geometric specifications. In addition, many factors must be considered, such as environmental issues, construction cost, obstructions, winds, runway exits and airport accessibility. The conventional runway design process relies on trial-and-error. It is laborious and usually suboptimal. Thus a mathematical model can help reduce the design time and improve the design quality. In this thesis, three models are developed for runway design optimization. The first model identifies feasible runway orientations based on crosswind limitations, the second optimizes runway location and orientation, and the third optimizes runway longitudinal-grade design. Various constraints and cost components are considered in the models. Genetic algorithms (GAs) are adopted in order to solve this problem, while a “Feasible Gates” method is used to reduce the search space and enhance computation efficiency. OPTIMIZATION MODELS FOR RUNWAY LOCATION, ORIENTATION AND LONGDITUDINAL-GRADE DESIGN By Tong Zhou Thesis submitted to the Faculty of the Graduate School of the University of Maryland, College Park, in partial fulfillment of the requirements for the degree of Master of Science 2014 Advisory Committee: Professor Paul Schonfeld, Chair/Advisor Professor Ali Haghani Associate Professor Lei Zhang © Copyright by Tong Zhou 2014 ii ACKNOWLEDGMENTS First and foremost I would like to thank my parents for their encouragement and support. They urged me to apply for a graduate school in the U.S and have unconditionally supported me over the years. This opportunity would not have been possible without them, and I truly appreciate all the effort they have done to me. My graduate studies would not have succeeded without the help of my adviser Dr. Paul Schonfeld. I would like to thank him for all the time and dedication he has put in to edit and refine my thesis. He has always been there for me with an answer when I stumble across something I do not understand. I have learned so much from him and his expertise in my field of study has never failed to astound me. He has not only helped me further my studies but also shows me the attitude I should have for academic study, and I believe this attitude will affect me for the rest of my life. I could not have asked for a better adviser. I also wish to thanks Dr. Lei Zhang and Dr. Haghani for their valuable advice, for reviewing my thesis, and for helping me improve it. I have made many new friends since coming to Maryland, and each one of them has helped me with the transition to a new country easier. I would like to thanks them for their helps and supports. I would not be where I am today without them. iii CONTENTS Acknowledgements .......................................................................................................................... i Contents ......................................................................................................................................... iii Chapter 1 Introduction .................................................................................................................... 1 1.1 Background and Motivation ............................................................................................. 1 1.2 Problem Statement ............................................................................................................ 2 1.3 Research Objective and Scope .......................................................................................... 8 1.4 Research Approach ........................................................................................................... 9 Chapter 2 Literature Review ......................................................................................................... 10 2.1 Optimization of Runway Location and Orientation........................................................ 10 2.3 Optimization of Runway Longitudinal-Grade Design .................................................... 13 Chapter 3 Optimization of Runway Location and Orientation .................................................... 16 3.1 Monte Carlo Method ....................................................................................................... 16 3.2 Model of Wind Rose ....................................................................................................... 17 3.3 Optimization Model ........................................................................................................ 21 3.4 Genetic Algorithm .......................................................................................................... 31 Chapter 4 Optimization of Runway Longitudinal-Grade Design ................................................. 36 iv 4.1 Formulation ..................................................................................................................... 38 4.2 Genetic Algorithm Modifications ................................................................................... 43 4.3 Feasible Gates ................................................................................................................. 45 Chapter 5 Case Study .................................................................................................................... 56 5.1 The Region of Feasible Runway Orientation.................................................................. 59 5.2 Runway Location and Orientation Optimization ............................................................ 60 5.3 Runway Longitudinal-Grade Design Optimization ........................................................ 64 5.4 Sensitivity Analyses ........................................................................................................ 67 Chapter 6 Contributions and Future Work ................................................................................... 70 6.1 Contributions................................................................................................................... 70 6.2 Future Work .................................................................................................................... 71 Appendix ....................................................................................................................................... 73 References ..................................................................................................................................... 92 1 CHAPTER 1 INTRODUCTION 1.1 Background and Motivation The design of an airport runway that only aims to satisfy the most basic requirements is quite challenging, and optimizing the design is even more difficult. There are various factors associated with building an airport runway, such as environmental impacts, construction cost, existing obstructions, winds, runway exits, airport accessibility, land use and auxiliary areas for facility construction. In addition, geometric specifications, airspace clearance standards and environmental issues are all essential constraints to the project. Conventional runway design is conducted with a “trial-and-error” process (Ashford et al. 2011). Engineers attempt different combinations of runway location, orientation and longitudinal-grade design, test the feasibility of geometry and crosswind components, and evaluate total cost with the considerations of the features of runway. This manual process is generally laborious and complicated. Moreover, it is difficult to find the optimal solution. Therefore, developing a mathematical model and algorithm is an efficient way to reduce design time and explore better solutions. Previous studies on runway orientation optimization mainly focused on critical crosswind component, without a comprehensive consideration of runway construction costs. On the other hand, no previous study on the optimization of runway longitudinal-grade design has been found, but some methods and models for highway and railroad alignment design are somewhat analogous and may be partly transferable to runways. 2 The runway design problem is divided here into two steps. The first step focuses on runway location and orientation while the second step focuses on runway longitudinal-grade design optimization. This method can reduce the number of decision variables in each problem and improve overall computation efficiency. In this thesis, three new models are proposed. The first model identifies the region of feasible runway orientations, the second model optimizes the runway location and orientation and the third model optimizes runway longitudinal-grade design. 1.2 Problem Statement Generally, statewide-integrated airport system planning first identifies the area of new airports, and then the specific design of an airport is prepared in airport master planning. The construction of runways is very important for airport planning, since it affects the entire layout of airport facilities, such as terminal configuration (Bandara and Wirasinghe 1992), taxiway, parking lot (Jia 2005) and airport access. In runway design optimization, three important basic factors are runway location, orientation and longitudinal grade. The goal is to find a solution that satisfies numerous constraints using minimum construction cost. The runway design constraints are shown in the table 1.1. 3 Table 1.1 Runway design constraints Name Constraint Location 1. Airspace clearance standards. 2. Area of interest. Orientation 1. Airspace clearance standards. 2. Usability factor of the airport. Longitudinal-grade design 1. Airspace clearance standards. 2. Runway longitudinal-grade design specifications. Not all factors affecting runway design are considered in this thesis. For example, noise is a major factor, especially when the area of interest is near residential zones (Espey et al. 2000 and Prats et al. 2011). In addition, airport accessibility, cost of land and interference with other airports or sensitive areas are some other important factors to be considered in determining runway location and orientation. These factors should be considered in the future studies. The standards of FAA approach categories C and D are used in this thesis as an example. The considered requirements and cost components are described as below. Area of Interest As stated early in this section, statewide integrated airport system planning specifies a general area for future airport building. Thus, the search area should be limited in this designated area. 4 Airspace Clearance Standards Airports must be free from obstructions that could be potentially hazardous to landings and takeoffs. Airspace clearance standards define several imaginary surfaces surrounding each runway. Any natural or artificial objects penetrating these surfaces are considered as obstacles for air navigation. In this thesis, the layout of imaginary surfaces is based on Federal Aviation Administration (FAA) regulations in FAR Part 77 (1975). The imaginary surfaces include primary surface, approach surface, horizontal surface, transition surface and conical surface, as shown in Figure 1.1. Under these constraints, the runway must be located precisely in a site without any imaginary surfaces penetration, or all obstructions must be removed. (a) (b) 5 (c) (d) Figure 1.1 Imaginary surfaces (a) Approach and transition surfaces; (b) Primary, horizontal and conical surfaces; (c) Combined imaginary surfaces; (d) Aerial view of imaginary surfaces Usability Factor of the Airport Due to the advantage of headwind and the disadvantage of crosswind for both takeoffs and landings, it is desirable to orient main runways along the direction of the prevailing winds. FAA and International Civil Aviation Organization (ICAO) have developed a series of standards for maximum permissible crosswind components. When the crosswind component exceeds the maximum allowable value, the runway should not be used. In addition, the ICAP (Aerodromes 2009) and FAA (FAA 2012), require that the usability of an airport should not be less than 95%. According to Ashford (2011), the usability factor is defined as the percentage of time during which the use of the runway is not restricted because of an excessive crosswind component. Thus the crosswind component should be under the maximum value at least 95% of the time. If a 6 single runway orientation fails to meet the requirement, more runway orientations must be provided. However, only a single-runway situation is considered in this thesis. Runway longitudinal-grade design specifications Runways are relatively flat, but an absolutely level runway may result in excessive earthwork costs. According to the ICAO and the FAA, runway longitudinal-grade design criteria include maximum longitudinal grade, maximum grade for first and last quarter, maximum effective grade, maximum grade change, distance between points of intersection, and length of vertical curve. In addition, FAA (2012) specifies the runway line-of-sight standards. For runways without full parallel taxiways, any point 5 feet above the runway centerline must be mutually visible with any other point 5 feet above the runway centerline. FAA (2012) also requires the runway safety area (RSA) to be graded for reducing the risk of damage to aircraft in the event of an undershoot, overshoot, or excursion from the runway. The part of the RSA between the runway ends must be longitudinally parallel to the runway centerline. For the first 200 of the runway safety area beyond the runway ends, the slope is downward from the ends and not steeper than 3%. For the remainder of the safety area, the longitudinal slope should be such that no part of the runway safety area penetrates the approach surface. The maximum negative grade is 5% for that part of the safety area. Runway Cross Section Except for runway, shoulders and RSA should also be graded. The cross-section Template is shown as in Figure 1.2. For approach categories C and D of FAA, the cross-section slope of runway is between 1% and 1.5%, and for RSA it is between 1.5% and 3.0%. Since shoulder 7 width is relatively small (10 ft to 25 ft), the grade range for shoulders is assumed to be the same as that for runways. Figure 1.2 Transverse-grade Limitations for Approach Categories C and D (modified from Ashford et al. 2011) Cost Components Earthwork cost and earthwork transportation cost are embedded in the models. Earthwork cost is defined as the cost of embankment and excavation. It includes the earthwork generated from grading runway, runway safety area, the areas taxiway and facilities construction and removing natural obstructions. Earthwork transportation cost represents the cost of hauling earth from one site to another. For runway longitudinal-grade design optimization model, pavement cost is also included. For runway location and orientation optimization model, facility connection cost is considered. The facility connection cost represents the taxiing delay cost of aircraft and taxiway construction cost. 8 1.3 Research Objective and Scope The runway optimization problem is divided into two parts in this thesis. The first part deals with runway location and orientation optimization, while the second focuses on runway longitudinal- grade design optimization. The goals of these two problems are stated as follows. 1. Different orientation and location of runway result in different location for clearance area and the areas for taxiway and facility construction. The earthwork is highly sensitive to the runway location and orientation. The objective is to find the optimal solution that minimizes the construction cost. 2. Runway length varies linearly with the gradient and pavement cost is proportional to runway length. The clearance area increases when runway length increases. Therefore, optimized longitudinal-grade design that follows the ground profile results in less earthwork cost for the runway and runway safety area, while a longer runway means more pavement cost, and probably more earthwork cost from removing obstructions. The goal is to achieve a minimum total cost based on these trade-offs. Thus, the problem of this thesis is defined as: Given an area of interest, optimize runway orientation, location and longitudinal-grade design. In order to achieve this objective, several goals must be pursued: 1) Propose a model for identifying the region of feasible runway orientation. 2) Develop a model for optimizing the location and orientation. 3) Develop a model for optimizing the runway longitudinal-grade design. 4) Find the feasible gates of runway longitudinal-grade design in order to improve the computation efficiency of the proposed genetic algorithm. 9 The design of an airport runway is a result of compromises among many factors and costs, such as land use, noise, obstruction clearance cost, flight path and construction cost. However, only the important and sensitive factors are considered in developing a reasonable mathematical model. 1.4 Research Approach Each chapter of this thesis has different approaches. 1) Optimization of runway location and orientation First, the Monte Carlo method is applied to determine the region of feasible runway orientations. Then a model considering construction costs is developed for comprehensively optimizing runway location and orientation. Finally genetic algorithm (GA), that only includes simple crossover and mutation operators, is applied to optimize the location and orientation. 2) Optimization of runway longitudinal-grade design An optimization model is developed that considers earthwork cost and transportation cost. A GA with specially designed operators is developed for searching the optimal solution. The “feasible gate” approach is applied here to enhance the computation efficiency. 10 CHAPTER 2 LITERATURE REVIEW The literature review for this thesis covers two main aspects. The first part reviews the scopes and methods of runway location and orientation optimization. The second part reviews the optimization of runway longitudinal-grade design. Since no previous study about the second part has been found, the literature review focuses on some pertinent highway and railroad alignment optimization models, and discusses how similar ideas can be applied to runways. 2.1 Optimization of Runway Location and Orientation In aviation, crosswind is the component of prevailing wind that is perpendicular to runway center line. With the increment of crosswind, the difficulty of landings and takeoffs increases. Especially in inclement weather, runways are affected by standing water and snow, so the maximum acceptable crosswind decreases. Since crosswinds are hazardous to aviation safety, the airport is forbidden to be used when the speed of crosswind is higher than the allowable value. Thus, orientation of runway should be designed to ensure aircraft land or takeoff into the wind to improve the usability of an airport. According to the standards of FAA and ICAO, runway orientation should be well designed so that the usability factor of the airport is not less than 95%. The conventional method for determining runway orientation is the wind rose method (Ashford and Wright 1998). This method defines wind directions and speeds in a polar coordinate system. The angle denotes the direction of wind, and the radius denotes the wind speed. Circles and radial lines divide the wind rose into many cells. The number in each cell is the probability for wind to blow in that particular range of directions and speeds, as shown in Figure 2.1. A template 11 is placed on the wind rose. The width of template is the allowable crosswind component. The usability is calculated by the coverage of the template. The wind rose method is based on a spreadsheet. Manual calculation is time-consuming. Besides, it is inaccurate for the cells that are only partially covered by template. A computer model called WNDROS was developed by Mousa (2000) to automate the process of wind rose analysis. This model adopted the geometric method to calculate the adjustment factor of cells that are partially covered, and acquires the optimal solution through an exhaustive search. In addition, Mousa (2001) also proposed a similar method for two-runway orientation optimization. The WNDROS model can precisely calculate the usability through the geometry. Nevertheless, very high accuracy seems meaningless in this problem, since the wind data is quite rough. Moreover, the geometric method was very complicated since many cases must be considered. A GIS-based wind rose method was presented by Jia et al. (2005). This model took advantage of ArcGIS to avoid the intensive geometric computation. However, it cannot handle multiple runway systems. Chang (2013) also presented a model for optimizing multiple runway orientations. This model can find not only the optimal solution, but also the feasible region of runway orientation. Thus it was useful for developing comprehensive optimization models in the future studies. Moreover, this model adopted an approximation method to calculate the adjustment factors for partially covered sectors. It reduced the computation time and avoids geometric calculation. However, in comparison with other models, this approximation method impaired the accuracy of the usability factor. Oktal and Yildirim (2013) presented a new model for optimizing the runway orientation. They tested every observation of wind data to determine if it is within the template. The usability was calculated by the percentage of observations that meet the crosswind requirements. This method avoided the calculation of partially covered sectors. 12 Figure 2.1 Wind Rose and Template (Ashford et al. 2011) All the studies mentioned above focused on maximizing airport usability factor. However, as Chang (2013) stated, “the actual runway orientation is the result of compromises between the airport usability and additional factors”. A comprehensive model is desirable for practical use. In this thesis, the Monte Carlo Method is adopted for calculating the usability factors of runway systems. As discussed above, the biggest difficulty with the wind rose method is the computation of the adjustment factors for partially covered cells. The proposed modified Monte Carlo Method avoids this step and efficiently and accurately calculates usability factors. The optimal 13 orientation can be identified through an exhaustive search. Besides, a model is developed for comprehensively optimizing runway location and orientation. 2.3 Optimization of Runway Longitudinal-Grade Design Similarly to highway alignment design, the conventional method for runway longitudinal-grade design is laborious and it could hardly achieve a near-optimal design. The runway longitudinal- grade design (RLD) is analogous to that for highway and road transit. Although some factors are different, the formulation of highway vertical alignment and road transit alignment could be applied to runway problems with additional considerations. There are several existing optimization methods for HVA. Easa (1988a) formulated an enumeration model for acquiring minimum earthwork embankment, excavation and allocation cost of highway construction while satisfying the geometric constraints. In another paper Easa (1988b) added more detailed considerations of the cost of borrow pit and landfill in the model. The first stage in Easa’s model is the selection of highway vertical alignment, while the second stage is for earthwork allocation optimization. The model integrated these two stages together. However, one disadvantage of Easa’s proposed model was that it was based on an enumeration method, so it can find the global optimal solution only after trying all combinations, and the solutions are discrete. Linear programming models were also adopted for optimizing highway alignment, such as Moreb et al. (1996). With some well-developed algorithms, such simplex, this method can guarantee the global optimal solution and comparatively short computation time. However, this method cannot cope with non-linear cost functions and constraints, which are necessary in 14 runway longitudinal-grade design. Besides, it is not clear that runway alignment can be specified well enough by a polynomial function (Jong 1998). Dynamic programming (Goh, Chew and Fwa 1988, Puy Huarte 1973 and Murchland 1973) is another method in the highway alignment optimization. In this method, each station is treated as a stage of in a dynamic model. Each sub-problem is iteratively optimized in these successive phases. This method has three disadvantages. First, the search space is not continuous. Second, the vertical alignments generated from dynamic programming are usually piecewise segments (Jong 1998). Thus, it is too rough to be used without a refinement by engineers. Third, the effectiveness of dynamic programming model is low, so the quality of solution is limited by computer capacity. Heuristic algorithms are also adopted for solving highway alignment optimization problems. The series of papers by Jong, Jha and Schonfeld (2000), Jong and Schonfeld (2003), Jha and Schonfeld (2004), provided an evolutionary formulation for optimizing three-dimension alignment simultaneously. They showed that a genetic algorithm is an efficient way to search for an optimized solution for highway alignment problem because it was comprehensive and the search space could be continuous. Jong and Schonfeld (2003) also verified the effectiveness of their proposed model and algorithms with a statistical test. Jong, Jha and Schonfeld (2000) and Jha and Schonfeld (2004) also adopted GIS into their model, which made the model more practical. Kang and Schonfeld (2007) proposed a method called feasible gates to enhance the effectiveness of GA. The feasible gate method improves efficiency by identifying the feasible region of each variable in advance, so that each offspring in GA is guaranteed to be feasible. Kang (2009) presented a prescreening and repairing method for improving the efficiency of GAs. This method identified and repaired infeasible solutions whose violations are small. However, 15 infeasible alignments whose violations of constraint are too severe were discarded before explicit evaluation. Fwa (2002) chose GAs as the optimization technique for highway vertical alignment since it did not require information on differentiability, convexity, or other auxiliary properties. In addition, Fwa verified the validity of GA in a simple example, by comparing the solution calculated by GA to the one obtained from dynamic programming. Kim and Schonfeld (1997) first analyzed the benefit of applying dipped vertical alignment between rail transit stations. They used a numerical example to demonstrate that dipped track profiles can significantly reduce propulsive energy, braking energy, and travel times. Kim and Schonfeld (2012) used a deterministic simulation model to verify the benefit of dipped rail transit alignment. Jha et al. (2007) proposed a comprehensive model integrated GAs and GIS system for optimizing three-dimensional rail transit route between two stations. This study was based on their previous highway vertical optimization research, but with different design criteria and cost components. Lai and Schonfeld (2010) presented a practical rail transit optimization methodology that can track alignment connecting several stations. This model can comprehensively optimize rail transit alignment considering various cost components. Lai and Schonfeld (2012) extended their model to analyze vehicle dynamics through a simulation process. The highway alignment optimization problem has been extensively studied over the past decades. Some of these studies were successfully applied to solve rail transit alignment optimization problems. The airport runway vertical alignment problem is analogous to vertical highway alignment problem. This study utilizes and modifies existing methodologies and genetic algorithms of highway alignment optimization for the runway vertical alignment optimization problem. 16 CHAPTER 3 OPTIMIZATION OF RUNWAY LOCATION AND ORIENTATION The search region of an optimization of runway location and orientation is limited by two constraints. The location must be bounded in the area of interest. The constraint for runway orientation is that the usability of the airport must be no less than 95%. In this chapter, the Monte Carlo method is applied to determine the feasible region of runway orientation based on standard wind data. With the feasible region of location and orientation, a comprehensive model is developed for minimizing the runway construction cost. 3.1 Monte Carlo Method The Monte Carlo method is a probabilistic model for calculating approximate solutions for problems that are difficult to solve by other explicit methods. It is widely used in optimization and numerical integration problems. Calculating the area of an irregular shape is a very basic application of the Monte Carlo method. There are generally several steps to follow. First, define a regular domain which contains the irregular area. Second, generate random points within the domain. Third, count the number of points in the irregular area and out of it. Fourth, determine the ratio of two counts. Fifth, the area of the irregular shape is the product of the ratio and the regular area. 17 Figure 3.1 Using the Monte Carlo Method to Compute the Area of a Semicircle As shown in Figure 3.1, to calculate the area of a circle, we draw a larger square that contains the circle. Then, we generate a certain number of random points in the whole domain. Let denote the number of points located in the circle, denote the total number of random points, and denote the area of the square. Then the area of the circle is: (3-1) Note that the points in this example are uniformly distributed. However, in other problems random points may follow other probabilistic distributions. As in the wind rose method, locations of points are also related to wind data. The details will be presented in the next section. 3.2 Model of Wind Rose In the models of previous studies, the wind rose is built in the Cartesian coordinate system. However, due to the feature of wind rose, it would be easier to build it in the polar coordinate system. Angle is denoted as the direction of wind, and radius is denoted as the wind speed. In order to calculate the feasible region of orientation, five steps should be followed. 18 Step 1: Set up the boundary for each cell. As shown in Figure 3.1, angle denotes the direction of wind, and radius denotes the wind speed. Thus, cell is the region within boundary ( ) and ( ). Note that, for cells connected to the origin, the boundary of wind speed is ( ). Step 2: Place random points. As shown in Figure 3.1, each cell has a percentage number. They represent the probability for wind blowing within those ranges of direction and speed. Use to denote the probability of cell . When randomly placing the points, we take the probability into consideration. Let be the possibility that points will be located within one particular cell. Thus, inside the cells, the distribution of random points is uniform; however, on the whole template, the distribution is weighted by the possibilities. With the increment of the number of points, the total number of points located in cell is, (3-2) where is the total number of points; is the total percentage of wind, whose value is always 1. There will be points randomly placed in the cell , as shown in Figure 3.1. The angle of each point is a random value in the range of , and the radius of each point is a random value in the range of . Use to denote a random value in a given range. We thus obtain equations (3) and (4). (3-3) 19 (3-4) Figure 3.1 Random Points on Wind Rose Therefore, with the definitions above, the usability of a runway is equal to the percentage of points that is covered by the template. Step 3: Count the points located in the template Since it is difficult to determine the position of a point relative to a line in the polar coordinate system, we convert all the points to the Cartesian coordinates system by using the following equations: 20 (3-5) (3-6) Assume the angle of the runway centerline is , and . Thus, (3-7) in which, (3-8) Two lines of the template intersect with the line that is perpendicular to the centerline and passes through the origin. The two intersection points’ coordinates are as follows: √( ) and √( ) (3-9) √ ( ) and √ ( ) (3-10) For , a point is in the template if the equation (3-11) is true. ( ) ( ) (3-11) For , a point is in the template if the equation (3-12) is true. ( ) ( ) (3-12) For , a point is in the template if the inequality (3-13) is true. (3-13) 21 For , a point is in the template if the equation (3-14) is true. (3-14) Step 4: Calculate the usability Let denote the number of points located in the template. The usability can be calculated using equation (3-15). (3-15) Step 5: Convert Note that angles in polar coordinate system start from east counterclockwise, but the conventional wind rose method measures from north clockwise. Convert the angles from , which is measured from the east counterclockwise, into , which is measured from the north clockwise. ( ) (3-16) This equation is adopted from Mousa (2000). 3.3 Optimization Model The optimization model is set to search for the runway location and orientation that generates minimum cost within the area of interest and the feasible region of orientation. Runway location and orientation optimization are related to various costs, but only earthwork cost, earthwork transportation cost and facility connection cost are considered in this model since these costs are highly sensitive to the change of runway location and orientation. A basic genetic algorithm with only simple crossover and mutation operators is applied here to search for the optimal solution. 22 Methodology To build a runway, obstructions above the imaginary surfaces must be removed. The area of runway must be graded to satisfy the geometric specifications. The area around the runway must be graded for taxiway construction. This area will be referred to as “taxiway area” for convenience. Moreover, designers must also designate at least one area for facility construction, such as terminal, cargo warehouse and control tower. Thus the goal is to find the runway location and orientation with minimum earthwork cost for runway, taxiway and facility construction. In this model, several assumptions are made as follows: 1. Obstructions above the imaginary surfaces must be removed. 2. There must be a rectangular area surrounding runway, namely taxiway area. It includes runway area, runway safety area and the area for taxiway construction. The amount of taxiway area is predefined by designer, but the length and width could vary in a range. 3. There must be at least one rectangular area near the runway for future facilities construction. The elevation difference between the areas for facility construction and runway should be in an allowable range. The shape of the areas for facility construction is variable, but the required amount of area is a given constant. 4. Facility connection costs are assumed to increase linearly with the distances between the facilities and the runway. Longer distance between facilities and runway results in higher taxiway construction cost and aircraft taxiing delay cost. 5. Taxiway area and the areas for facility construction must be graded to be nearly flat with some allowable gradient. 23 With these assumptions, there are three kinds of area, namely taxiway area, area for facility construction and clearance area. Clearance area is the region where imaginary surfaces stand. The treatments of earthwork for each kind of area are different, as summarized in table 3.1. Table 3.1 Treatments of Earthwork for Different Areas Name Treatment Taxiway area Grading to be nearly flat with some allowable gradient Areas for facility construction Grading to be nearly flat with some allowable gradient Clearance area Excavation is necessary to remove obstructions; Embankment is acceptable as long as it is under imaginary surfaces. Formulation Denote the taxiway area as area zero. Let the areas for facility construction as area . Use ( ) to represent the 3-dimentional location of the starting point of the runway. The starting point is one of the ends of the runway. Let to denote the orientation of runway. For each area of facility, we use ( ) to denote the 3-dimentional locations and to denote the orientations. Let be the gradient of area for . In addition, the length of area is denoted as for . Consequently the cost function is defined as in equation (3- 17). 24 Total cost includes earthwork cost , facility connection cost and earthwork transportation cost . The goal is to minimize total construction cost. The objective function is defined as in (3-18). The amount of earthwork embankment and excavation are calculated according to the ground profile and treatments in Table 3.1. Earthwork cost is assumed to vary linearly with the amount of earth to be cut and filled, as shown in equation (3-19). As defined in equation (3-20), the facility connection cost is related to distances between the runway and the facilities. is the average Euclidean distance from the centroids of facility to runway starting and ending point. The unit of coefficient is defined as . In addition, for any given solution, earthwork transportation cost is relevant to the allocation plan. The earthwork transportation cost resulting from the optimal allocation plan will be adopted in the objective function. A linear program is applied to obtain the minimum transportation cost, and the details are discussed in the next section. Moreover, is a penalty cost corresponding to the set of constraints (3-28) to (3- 32) whose details will be presented later. ( ) (3-17) ( ( )) (3-18) (3-19) ∑ ( ) (3-20) Subject to: 25 (3-20) (3-21) ̅ ̅ (3-22) (3-23) (3-24) (3-25) (3-26) where, is the volume of earthwork for fill, ; is the volume of earthwork for cut, ; is the unit cost of embankment, ; is the unit cost of excavation, ; and are the lower and upper bound of the area of interest on the y-axis; and are the lower and upper bound of the area of interest on the x-axis; ̅ is the allowable elevation difference between runway and facilities; and are the lower and upper bound of the region of feasible runway orientation; and are the lower and upper bound of length of each area. is the upper bound of gradient of each area; 26 is the height of facility ; is the lowest height of imaginary surfaces at a particular location; is the number of areas for facility construction. The set of constraints (3-20) and (3-21) defines the x-axis and y-axis bounds of the area of interest. There is no bound for since the cost function can automatically force to a reasonable value. The set of constraints (3-22) limits the elevation differences between facilities and runway to less than ̅. Constraint (3-23) requires that the orientation of runway must be in the feasible region. The set of constraints (3-24) defines the upper and lower bound of the length of the areas for taxiway and facilities construction. Note that we define the width , where is the area. Thus the areas do not vary with the change of length. The set of constraints (3-25) limits the gradient of each area in a predefined range. The set of constraints (3-26) prevents facilities from penetrating the imaginary surfaces. In addition, the overlaps of taxiway area and areas for facility construction must be excluded. This constraint is hard to be explicitly defined since the search region of one area is related to all others. However, determining if there is any overlap is easy. Thus, a simple method is to add a penalty cost in the objective function. If there is any overlap in these areas, equals to a huge number, namely big M. Otherwise, equals to zero. To determine if two rectangles overlap, we can check if any vertex of one rectangle is inside of the other. The following method is adopted to determine if a point is inside a rectangle. Let as a vertex of the rectangle, and as the adjacent vertices of point . Thus, is inside the rectangle if and only if 27 (3-27) Denote as four vertices of area , for . Therefore, the penalty function is defined below. (3-28) (3-29) (3-30) (3-31) { ( ) ( ) (3-32) Linear programming for earthwork transportation Transportation cost is related to the allocation plan of earthwork. A poor plan can result in the waste of resources, such labor and time, while transportation cost can be decreased with a optimized allocation plan. Only the optimal allocation with the minimum transportation cost should be adopted in the objective function. This problem can be solved by linear programming. This linear programming model adopts the method of Easa (1988) and Mayer and Stark (1981) with some modifications. For a runway the formulation is more complex than for a highway since a broader are must be considered. First we divide all areas into squares with same length , as shown in Figure 3.2. Then we calculate the amount of fill or cut earthwork in each cell. For cells that only contain 28 embankment or excavation, the amount is simply the sum of earthwork. Besides, for cells that contain both embankment and excavation, the amount of earthwork is the absolute value of their sum. We classify these cells as cut cell or fill cell based on whether the cell needs net embankment or net excavation. Assume the earthwork transportation cost is zero for earth transported inside the cell due to the short distance. The calculation error resulting from this assumption decreases with the size of cells into which the area is divided. The outside of taxiway area, facility area and clearance area is assumed as borrow pit and landfill. Earth can be excavated from the outside to cells or filled from cells to the outside without limitation. Figure 3.2 Cells in Taxiway Area and Clearance Area We compute the distances between each cut cells to fills cell by the coordinates of centroids. Assume that the distance from each cell to landfill and borrow pit is the shortest Euclidean distance from the cell to the nearest boarder. Suppose that the cost to transport one cubic foot of earth among cells varies linearly with the distance between their centers as in equation (3-33). Let denote the unit cost. Different values denote different origin-destination pairs. means that the transportation is between different cells. or denotes that the transportation is from borrow pit to cells or from cells to landfill. 29 ( ) (3-33) ( ) √ ( ) ( ) (3-34) Note that the number of variables in the sub-problem is ( ) . When dividing each area into more cells, the number of variables increases greatly. This may greatly increase computation time, or even make the problem unsolvable for some software because of limitation of computer memory. However, it is obvious that if two cells are too far apart, there is literally no earthwork transportation between them. That is because the objective function prevents this expensive allocation plan. Thus it is reasonable to assume that transportation occurs only if two cells are within an acceptable distance , so that unnecessary variables could be eliminated without losing much accuracy. Users could also set the value of to control the accuracy. The variables from cells to landfill or borrow pit should always be retained. The objective function is shown in equation (3-35). Constraints (3-36) to (3-39) are based on the Table 3.1. ∑ ∑ ( ) ( ) ∑ ( ) ( ) ∑ ( ) ( ) (3-35) Constraints: ∑ ( ) ( ) ( ) (3-36) ∑ ( ) ( ) ( ) (3-37) ∑ ( ) ( ) (3-38) ( ) ( ) ( ) (3-39) Where: 30 ( ) denotes the amount of earthwork of cut cell ; ( ) denotes the amount of earthwork of fill cell ; ( ) denotes the maximum amount of earthwork that could be filled in cell in clearance area; denotes the shrinkage (or swell) factor of earthwork excavated from cut cell , and to be compacted in fill cell ; denotes the shrinkage (or swell) factor of earthwork excavated from borrow pit, and to be compacted in fill cell ; ( ) is the amount of earthwork to be transported from cut cell to fill cell ; ( ) is the amount of earthwork to be disposed from cut cell to landfill; ( ) denote the amount of earthwork to be transported from borrow pit to fill cell ; ( ) is the cost to haul one cubic foot earthwork from cut cell to fill cell ; ( ) denote the cost to haul one cubic foot earthwork from cut cell to landfill; ( ) is the cost to haul one cubic foot earthwork form borrow pit to fill cell ; is the number of cut cells; is the number of fill cells; is the number of fill cells in clearance area, but exclude the cells in taxiway area; is the set of fill cells that are less than away from cut cell ; 31 is the set of cut cells that are less than away from fill cell ; is the set of cut cells less than away from imaginary surfaces fill cell . 3.4 Genetic Algorithm Recall that the decision variables in the proposed model includes the three-dimensional coordinates of runway starting point and the areas for facility construction , orientations, and lengths of the areas for taxiway and facilities construction. Total cost is a complex nonlinear function of all the variables. Although the problem is based on a three-dimensional space, the search space is a hyperspace. In this case, GAs are chosen for several reasons. First, at any step in the search GAs deal with a population of candidate solutions rather than on solution. These are spread throughout the solution space, so the chance of reaching the global optimum is increased significantly (Goldberg, 1989). Second, the search is processing in several directions and approaching to the optimum simultaneously (Haupt et al. 2004). Third, objective function itself does not need to be linear, and no gradient information is required (Goldberg, 1989). These properties of GAs make them practical for the proposed model and, for complicated and noisy objective functions, they are more likely to achieve good solutions than conventional techniques. The process of basic GAs can be simply described by the following pseudo code: Begin: 1. Generate initial population. 2. Prune the population based on the fitness value. 3. Repeat until meet the termination rule. 32 a. Select pairs from the older generation to mate. b. Refill population by crossover and mutation. c. Eliminate the individuals with less fitness value. d. Group the remaining individuals for next round. End; 4. Output Encoding In genetic algorithms, solutions, constraints and objective functions are analogous to population, environment, and the measure to evaluate the fitness of each individual candidate solution. Each solution is encoded into a chromosome such as in equation (3-31), which contains a set of genes. ( ) (3-40) Variables in this model should be floating-point number rather than integer in order to search a continuous space. For notational convenience, we denote as a uniformly distributed random number in the closed interval . The domain of each variable is defined as follows:. (3-41) (3-42) (3-43) (3-44) (3-45) 33 [ ] (3-46) (3-47) and define the area of interest and the range of elevation. and limit the runway orientation to the feasible region that we obtain from the model in section 3.2. For the facility construction areas, the orientation can be any value between and . and are the length limitations for each area. is the gradient upper bound for each area. Fitness function For genetic algorithms, fitness represents the performance of a chromosome in the environment. Fitness is the value returned by the proposed fitness function (3-17). Since the goal is to minimize the total cost, a lower fitness value indicates a higher probability of survival. For constraint (3-24), penalty functions are adopted. By adding penalties in the fitness function, violation of constraints will increase the total cost, so that the infeasible solutions are prohibited from being selected for the next generation. Selection Two ways are commonly used to select chromosomes for reproduction of the next generation. One, based on proportionate selection, determines the probability of choosing each chromosome. Thus, even the genes with very low fitness will be possibly chosen. The other one is ordinal- based section. In this case, we first rank the chromosomes according to their fitness values and only the ones with highest rankings may be chosen. 34 Operators Crossover and mutation are two basic way to reproduce offspring. Crossover is the process of randomly choosing genes from two parents. With this operator, offspring can retain the good genetic information that result in higher fitness and abandon the bad ones. A crossover operator allows the search process to focus on local optimal solutions. On the other hand, concentration on local optima may keep the search away from the global optimal solution. The process of crossover does not generate new genes. Therefore mutation is included in the algorithm to provide the offspring with some new genes that they cannot inherit from their parents. It helps maintain the diversity of genetic information. In this model, we only include the uniform crossover and simple mutation. (1) Uniform crossover Suppose two chromosomes, and , are chosen to reproduce. For the resulting offspring, each gene comes either from or . One possible offspring is . Note that inherits gene and from , and all others genes from . ( ) (3-48) ( ) (3-49) ( ) (3-50) (2) Simple mutation 35 Let ( ) be the chromosome chosen to mutate. Randomly pick one or more variables to mutate in a given range. For example, variable is chosen. Then new value of and new chromosome are as follows: = (3-51) ( ) (3-52) Termination rule The search process repeats until a termination rule has been activated. In this model, the search stops if there is no improvement within a given number of generations, or it reaches a pre-set number of generations. 36 CHAPTER 4 OPTIMIZATION OF RUNWAY LONGITUDINAL-GRADE DESIGN Since the limitations of runway longitudinal-grade design are very strict, designers usually only consider how to satisfy the geometric specifications; however, designs which closely follow the ground profile while still meeting the requirements, can reduce construction cost. In this chapter, a runway longitudinal-grade optimization model considering pavement cost, earthwork cost and earthwork transportation cost, is proposed for minimizing runway construction cost. Earthwork generated from grading runway and runway safety area (RSA) and removing natural obstructions are considered in the model. Pavement cost varies linearly with the length of runway, and earthwork cost is assumed to vary linearly with the amount of earth that must be cut and filled. For earthwork transportation, a linear program is adopted to secure the optimal allocation plan, and the corresponding cost is adopted as earthwork transportation cost in the objective function. A genetic algorithm with specified operators is applied to solve this problem. In addition, as mentioned previously, constraints of runway longitudinal-grade design are strict. Many randomly generated offspring are infeasible. Thus, a “feasible gates” method (Kang, Schonfeld and Jong 2007) is applied to narrow search space to enhance the computation speed. The flow chart of the model is shown in Figure 4.1. 37 Figure 4.1 Flow Chart of the Runway Longitudinal-Grade Design Optimization Model 38 4.1 Formulation Five factors strongly influence required runway length (Ashford et al. 2011): performance characteristics of aircraft using the airport, landing and takeoff gross weights of the aircraft using this airport, temperature, elevation of the airport and runway gradient. As the goal is to optimize runway longitudinal-grade design, only runway gradient varies with solutions in the proposed model. Here, basic runway length is defined as the runway length considering all factors except for runway gradient. Therefore, the design runway length is the product of gradient factor and basic runway length . The gradient factor is defined in equation (4-1). The effective gradient is the maximum difference in runway elevations divided by the runway length. (4-1) Assume the runway is evenly divided by stations into sections. Thus the length of each section ( ), as shown in Figure 4.2. The elevation of the first station is assumed to be the same as the elevation obtained from the runway location and orientation optimization model. Let the starting point to be the reference point. The distance from the starting station to station is . The elevation of each station is . The slope of each section is calculated as: (4-2) The longitudinal grades of RSA between the runway ends are assumed to be parallel to runway centerline. Let and denote the slopes of the first 200 feet of the RSA beyond the runway ends, while and denote the slopes of the remainder of RSV. 39 Figure 4.2 Elements of the Model Objective function The objective function is set to minimize construction cost, which includes pavement cost, earthwork cost and earthwork transportation cost. Variables are the elevations of stations of the runway and the slopes of the RSA beyond the runway ends . Thus the cost function is defined in (4-3) and the objective function is specified in equation (4-4). The pavement cost varies linearly with the pavement area, as in equation (4-5). Earthwork cost is assumed to vary linearly with the amount of earth to be cut and filled, as in equation (4-6). For a given solution of elevation of stations, different allocation plan results in different earthwork transportation cost, and the optimal one will be adopted in the objective function. A subroutine linear program, similar to section 3.3, is applied to obtain the minimum transportation cost. The only difference is that the earthwork in the runway area should be considered separately. In addition, runway and RSA cross-section designs also affect earthwork cost. A simple method is applied in this model. If the ground profile is higher than the upper bound of cross-section profile in that part of runway or RSA, then the largest allowable grade is chosen. If the ground profile is lower than the lower bound of cross-section profile, then the smallest allowable grade 40 is chosen. Otherwise, we choose the grade that connects the cross-section profile to the ground profile. ( ) (4-3) ∑( ( ) ) (4-4) (4-5) (4-6) In the above equations: is the elevation of station , ; is the station of RSA beyond the runway ends, ; is the runway pavement cost; is the earthwork cost, including embankment and excavation cost; is the earthwork transportation cost; is unit cost of pavement, ; is the runway width; is the volume of earthwork for fill; is the volume of earthwork for cut; is the unit cost of embankment, ; 41 is the unit cost of excavation, . Constraints According to FAA runway longitudinal-grade design Criteria, six geometric requirements and the runway sight distance requirements must be satisfied. Besides, there are requirements for the part of the RSA extending the runway ends. The following constraints are based on FAA approach categories C and D. a. Maximum longitudinal grade Maximum longitudinal grade within the second and third quarter of runway must be less than 1.5%. In equation (4-7), is index of sections within the second quarter and third quarter of the runway. ( ) ( ) (4-7) b. Maximum grade first and last quarter ( ) ( ) (4-8) In equation (4-8), is index of sections within the first quarter and last quarter of the runway. c. Maximum effective grade (4-9) and are the elevations of the highest and lowest point of the crest of runway centerline. 42 d. Maximum change ̇ | | % (4-10) e. Distance between points of intersection ( ̇ ̇ ) (4-11) f. Length of vertical curve ̇ ̇ (4-12) g. Sight distance requirement For runways without full parallel taxiways, any point 5 feet above the runway centerline must be mutually visible with any other point 5 feet above the runway centerline. Set as the line connecting points ( ) and ( ). Let denote the x-axis coordinate of line when y-axis coordinate equals . Thus the constraint is as follows:. (4-13) h. For the first 200 feet of the RSA beyond the runway ends (4-13) i. For the remainder of the RSA (4-14) j. Grade change limitation in RSA (4-15) 43 4.2 Genetic Algorithm Modifications In this model each solution is encoded as a chromosome, which contains a set of genes as shown in equation (4-16): ( ) (4-16) As Jong and Schonfeld (2003) suggested, the values of stations should be floating-point numbers rather than discrete number in order to search through a continuous space. and are the lower bound and upper bound of gene , as in equation (4-17): (4-17) The search space of is determined by the elevations of surrounding stations. The method for calculating the bounds of search space will be discussed in the section 4.3. The search space of is constant as shown in equations (4-13) to (4-15). To improve the computation efficiency in this certain case, several specifically designed operators and initialization methods are added in the basic GA. Initial population a. Randomly generated runway profile Only initialization and mutation could introduce new genetic information. The comprehensiveness of first generation is very important to the performance of GAs. Thus, it is necessary to have some random individuals in the first generation. b. Flat runway profile 44 Considering the high cost of runway pavement, the solutions that generate shorter runway length might be good guesses. It is recommended that the chromosome containing the same elevation as starting point should be included in the initial population. Thus, one of chromosomes in the first generation is: ( ) (4-18) c. Runway profile closely following the terrain If runway longitudinal-grade design is closer to ground profile, it can result in less earthworks volume in the runway area. However, it might not be feasible if we put all intersection points on the existing ground. Consequently, points that are close to ground profile but are still within the feasible range would be included in the first generation. Operators Crossover and mutation are two kinds of common operator in GAs. The process of crossovers makes the search converge on good solutions. Nevertheless, a search process without mutation may fall into local optimum. That is why mutation must be added to keep the search more diverse. Well-defined operators can improve the performance of proposed GA. a. Uniform mutation Let only one gene on chromosome ( ) mutate. Generate a random number to denote which gene is mutated. Thus the gene of mutates in its feasible region. b. Flat mutation 45 This operator is designed to flatten the runway longitudinal grade. As discussed before, a flatter longitudinal-grade design leads to a shorter runway, which may result in less total cost. For ( ) , let ( ) , and ( ) . Then, and . c. Single Crossover Assume that ( ) and ( ) crossover. Generate a random number to denote which gene to crossover. Then we obtain two new chromosomes. Equations (4-19) and (4-20) illustrate a possible outcome of single crossover. ( ) (4-19) ( ) (4-20) d. Uniform crossover Suppose that chromosome ( ) and ( ) ) crossover to produce . Generate random numbers . If then the gene of is inherited from ; otherwise gene is inherited from . 4.3 Feasible Gates In highway alignment optimization models, the feasible gates method (FG) developed by Kang et al (2007) is an approach to enhance the computation efficiency and solution quality by avoiding infeasible solutions from the process of initial generation and mutations. FG predefines the feasible region for proposed GAs so that infeasible solutions are avoided to be generated. 46 Even though this concept was originally proposed for highway design, it is also very useful in runway longitudinal-grade design optimization. Since the runway geometric specifications are much more restricted compared to highways, the feasible domain is usually very small. Many solutions must be eliminated for violating constraints. Without predefined FGs to narrow the search space down to feasible region, it would be difficult to generate the initial generation. Besides, almost all of the mutations will be invalid. It is time-consuming to generate too many infeasible solutions, and it even affects the quality of the model. Consequently, determining the feasible gates of runway longitudinal-grade design is desirable. Constraints discussion Recall the geometric constraints presented in section 4.1. We do not discuss the FGs for RSA slopes since these constraints are constant. Constraints and are actually the same but with different parameters in different sections. It would be easy to obtain the FG of Constraint in the model. We just need to restrict the elevations of other stations according to the distance from them to the current lowest and highest station. Constraints , and are the strictest. Constraints and can be eliminated since constraint is a subset of constraints and in this model. Let’s transform equation (4-11) to equation (4-21) as follows. ( ̇ ̇ ) (4-21) Basically, in order to achieve an accurate solution, the length of section should not exceed 1000 feet. Thus if we set to be 1000, equation (4-21) is as follows: ( ̇ ) (4-22) 47 Thus constraint is included in constraint . In addition, constraint can be transformed as: ( ̇ ̇ ) (4-23) Constraint is included in . Therefore constraints can be eliminated. Before discussing the feasible gates in different situations, we define the symbols that will be used next section as follows. Let denote the lower bound ; denote the upper bound ; denote the provisional lower bound of subject to constraints ; denote the provisional upper bound of subject to constraints ; denote the provisional lower bound of subject to constraints based on station , where ; denote the provisional upper bound of subject to constraints based on station , where ; Note that denotes constraint and , constraint ,constraint and constraint respectively. According to the discussion above, the feasible gates are defined as follow. 48 FG in generation process In the generation process, feasible gates are easier to calculate than in mutation process since the feasible regions of undefined stations are only limited by previous stations. The following steps are designed to find the bounds of station ( ). a. Constraint and Figure 4.3 Bounds of Constraints and ( ) (4-24) ( ) (4-25) is the length of that part of section ( ) located in the first or last quarter of the runway. b. For constraint ( ) (4-28) ( ) (4-29) c. For constraint Case 1, if , no bounds. Case 2, if : 49 As shown in Figure 4.4, is defined as the grade change at station . B is is the maximum allowable grade change at station . It is defined as in equation (4-30). ( ) (4-30) Thus, ( ) (4-31) ( ) (4-32) Figure 4.4 The Bounds of Constraint d. For constraint Figure 4.5 The Bounds of Constraints In generation process, there is no upper bound for constraint . We must check the sight distance of all previous stations in order to calculate the lower bounds of station . Denote as the 50 points on the runway at station , while as the points 5 feet above the runway at station . Use to denote the intersect of line and the vertical line at station , where . Let denote the elevation of point . The lower bound of constraint is defined below. ( ) (4-25) where ( ) and . All in all, lower bound for is ( ) ; upper bound for is ( ). FG in mutation process During mutation process, it becomes relatively harder to determine the upper and lower bound for one particular station, since points on both sides will limit the variation of the variable that is chosen for mutation. a. Constraint and Figure 4.5 The Bounds Resulting From Constraint and ( ) (4-33) ( ) (4-34) 51 ( ) (4-33) ( ) (4-34) is the length of that part of section located in the first or last quarter of the runway. Thus ( ); ( ). b. Constraint ( ) for all (4-45) ( ) for all (4-46) c. Constraint There are four limitations when changes. As shown in Figure 4.6, in order to obtain the feasible gate of station , we need to consider station , , and . Figure 4.6 The Bounds Resulting From Constraint First, the FG based on . Consider that changes with , and it is limited by . ( ) (4-47) ( ) (4-48) Second, the FG based on . Consider that changes with , and it is limited by . 52 ( ) (4-49) ( ) (4-50) Third, the FG based on Consider that E and B change with , and they limit each other. For lower bound: If ( ⁄ ) Then set ( ) ( ⁄ ) (4-51) (4-52) So, ( ) (4-53) Else, Then set ( ) ( ⁄ ) (4-54) (4-55) So, ( ) (4-56) 53 For upper bound: If ( ⁄ ) Then set ( ) ( ⁄ ) (4-57) (4-58) So, ( ) (4-59) Else: Let ( ) ( ⁄ ) (4-60) (4-61) So, ( ) (4-62) Fourth, for FG based on The similar method for calculating FG based on could be applied to obtain and . Thus, 54 ( ) (4-63) ( ) (4-64) Specially, for , there is no and for , there is no ; for , there is no and ; for , there is no . d. Constraint Figure 4.5 The Bounds of Constraints We must check the sight distance of all other stations in order to calculate the lower bound of station , as shown in Figure 4.5. Denote as the points on the runway at station , while as the points 5 feet above the runway at station . Use to denote the intersection of line and the vertical line at station . Let denote the elevation of point . The lower bound of constraint is defined below. ( ) (4-25) where, if ( ) then ; else if then . 55 For upper bound, we just need to make sure that station does not block the sight line among other stations. Denote as the intersection of line and the vertical line at station Let denote the elevation of . Thus the upper bound of constraint is as follows. ( ) (4-25) where, ( ) then ; All in all, lower bound for is ( ); upper bound for is ( ). 56 CHAPTER 5 CASE STUDY In order to test the accuracy and efficiency of the proposed models and genetic algorithms, a numerical example is presented in this chapter. Wind data and topographic data are from two different real projects, so they are collected from different sites. The standard wind data, as shown in Table A1 in the appendix, are adopted from FAA Advisory Circular (FAA 1989). The topographic data, from US 220 project, are shown as maps in Figures 5.1 and 5.2. We assume it is reasonable to combine them as the data set for the case study. As can be seen, the northwestern part of the area of interest is mountainous. There is a canyon from southwest to northeast. Comparing to other parts of the map, the southeast is more flat and the elevation in this area is lower. Therefore, after optimization, the runway is expected to be located and oriented on the southeastern part. In addition, if crosswind allows, the optimal solution may also be in the canyon area. The design parameters of the proposed case are summarized in Table 5.1. 57 Figure 5.1 Contours of the Terrain 58 Figure 5.2 3-D view of the Terrain 59 Table 5.1 Design Parameters for Case Study Parameter Design Value First Model – Runway Feasible Orientation Allowable crosswind 13 knots Increment of angle Second Model – Runway Location and Orientation Optimization Basic runway length 10000 Runway width 200 Transportation cost $8,000 per thousand cubic yards per mile; Excavation cost $7,200 per thousand cubic yards; Embankment cost $9,600 per thousand cubic yards; Landfill earthwork cost Same as regular cost Borrow pit earthwork cost Same as regular cost Shrinkage factor and 1.0 Number of areas for facility construction One Facility connection cost coefficient 50,000 Facility area 48,000,000 Facility length lower and upper bound 6000 , 15000 Maximum allowable gradient for facility area 3.0% Design facility height 1,000 Taxiway area 80,000,000 Taxiway length lower and upper bound 16,000 , 20,000 Maximum allowable gradient for taxiway area 2.0% Earthwork transportation acceptable distance 6,000 Allowable elevation difference ̅ 100 Third Model – Runway Longitudinal-Grade Design Optimization Basic runway length and width Same as in the second model Transportation, excavation and embankment cost Same as in the second model Shrinkage factor and 1.0 Longitudinal-grade and Cross-section design criteria FAA approach categories C and D Runway pavement cost 312.5 Number of longitudinal-grade design stations 20 5.1 The Region of Feasible Runway Orientation We transfer the data in Table A1 to percentages through dividing the total number of observations by each count. After calculations, the acceptable orientation is found to range from 60 ( ) to ( ) , as shown in Figure 5.2. The optimal orientation is ( ) with 96.94% usability. The minimum usability is 93.64%, which is oriented at ( ). Calculation time is 202.5s. Figure 5.3 Feasible Region of Runway Orientation 5.2 Runway Location and Orientation Optimization The the output is shown in Table 5.3 and Figure 5.5. The earthwork distribution is shown in Figure 5.6. The allocation plan of earthwork is shown in Figure 5.7 and 5.8. Note that the arrows line from each point to borrowpit and landfill mean that there are earthwork tranported bewteen them, but it does not represent the distance between them. The distance is assume to be measured from the centroid of cells to the nearest bound. 61 Table 5.3 Output of Optimization Model Output Value runway orientation runway x-coordinate 125470.99 runway y-coordinate 160287.25 runway elevation 844.16 length of taxiway area 17782.18 width of taxiway area 4498.88 gradient of taxiway area 0. 663% facility orientation 112.19 facility x-coordinate 129042.20 facility y-coordinate 180739.76 facility elevation 844.90 length of facility area 12789.01 width of facility area 3753.22 gradient of facility area 2.043% Earthwork transportation cost $224,950,000 Earthwork excavation cost $803,300,000 Earthwork embankment cost $602,480,000 Facility connection cost $1,038,100,000 Total cost $2,668,800,000 As shown in Table 5.2 and Figure 5.3, the runway is located in the southeastern part of the area of interest. There is no earthwork in the clearance area, but a large amount of eathwork is in the areas for facility contruction and taxiway area, as shown in Figure 5.8. As shown in Figure 5.9, the allocation of earthwork of this optimal solution. Surplus earth in taxiway area is mainly transported to clearance area as long as it is still under the maximum allowable amount. The earthwork in the area for facility contruction needs the balance of landfill and borrow pit. 62 Figure 5.5 Optimal Location and Orientation for Runway and Facility 63 Figure 5.6 Optimal Location and Orientation for Runway and Facility (Enlarged) Figure 5.7 Earthwork Distribution 64 Figure 5.8 Earthwork Allocation 5.3 Runway Longitudinal-Grade Design Optimization According to the last section, optimal orientation is s, and the location is (125470.99, 160287.26). With these inputs, runway alignment optimization model is applied. The outputs are shown in Figure 5.9 and Table 5.4. As we can see, the optimized alignment follows the ground profile so that the earthwork cost could be reduced. In addition, the cross-section design of the first station of the runway is shown in Figure 5.10. More cross-section design may be found in the appendix. 65 Figure 5.9 Optimized Runway Longitudinal-Grade Design Figure 5.10 Cross-Section Design of the First Station 66 Table 5.4 Output of Runway Longitudinal Grades station X-coordinate(ft) Elevation(ft) 1 -5000.0 844.2 2 -4473.7 840.6 3 -3947.4 839.1 4 -3421.1 838.3 5 -2894.7 839.0 6 -2368.4 840.4 7 -1842.1 840.2 8 -1315.8 839.5 9 -789.5 840.4 10 -263.2 842.1 11 263.2 845.7 12 789.5 850.1 13 1315.8 856.3 14 1842.1 861.7 15 2368.4 865.3 16 2894.7 869.1 17 3421.1 872.8 18 3947.4 875.9 19 4473.7 878.4 20 5000.0 878.8 Table 5.5 Output of Runway RSA Slope X-coordinate(ft) Slope -6000 to -5200 -0.048 -5200 to 5000 -0.028 5000 to 5200 0.000 5200 to 6000 0.014 The total cost of the optimal solution is . If we set the longitudinal grades to be flat (elevations are the same as the starting point), then the total cost would be . The improvement rate is 11.0%. Considering the expense of a runway, even though the improvement rate is not high, the saving is still considerable. 67 5.4 Sensitivity Analyses In this section, two sensitivity analyses of two parameters are conducted to examine the influence of their value on the solution. Pavement cost The gradients of runway are highly constrained by pavement cost. Since gradients have the effect of increasing the required runway length, runway longitudinal-grade design is expected to be more level when pavement cost increases. We define 8 scenarios with different pavement costs but keep other parameters unchanged. Table 5.6 Results with Different Pavement Costs Scenario Pavement Cost ( ) Effective Grade Runway Length ( ) Total Cost ( ) 1 312.5 0.404% 10403.6 8.117E+08 2 625.0 0.393% 10393.1 1.462E+09 3 937.5 0.286% 10285.6 2.106E+09 4 1250.0 0.165% 10164.6 2.741E+09 5 1562.5 0.165% 10164.7 3.381E+09 6 1875.0 0.126% 10125.9 4.011E+09 7 2187.5 0.107% 10106.7 4.644E+09 8 2500.0 0.045% 10045.0 5.275E+09 As can be seen in Table 5.5, the effective grade and runway length decreases while pavement cost increases. When we set pavement cost to be 8 times that of the scenario 1, the effective 68 grade is only 0.045%, which means the runway is almost level. Figure 5.10 illustrates the optimal runway longitudinal designs in different scenarios. Figure 5.11 Longitudinal Designs in Different Scenarios Earthwork cost and earthwork transportation cost Earthwork cost and earthwork transportation cost are highly related to the gradients of runway. If we keep the pavement cost unchanged and decrease the earthwork cost and earthwork transportation cost, the benefit from making the runway longitudinal-grade design follows ground profile would be less. Thus, it is expected that cheaper earthwork cost and earthwork transportation costs will result in flatter runway profiles. Ten scenarios are defined with different earthwork cost and earthwork transportation cost, as shown in Table 5.7. The results in different scenarios verified the expectation. Effective gradient decreases as the earthwork cost and earthwork transportation cost increase. 69 Table 5.7 Results with Different Earthwork Cost and Earthwork Transportation Cost Scenario Transportation cost $/(1000yd³*mile) Excavation cost $/(1000yd³) Embankment cost $/(1000yd³) Effective Gradient Runway Length ft Total Cost $ 1 8000 7200 9600 0.404% 10421.2 8.1E+08 2 7200 6480 8640 0.393% 10392.7 7.9E+08 3 6400 5760 7680 0.393% 10392.8 7.8E+08 4 5600 5040 6720 0.393% 10392.7 7.6E+08 5 4800 4320 5760 0.393% 10392.7 7.4E+08 6 4000 3600 4800 0.306% 10305.9 7.3E+08 7 3200 2880 3840 0.306% 10306.0 7.1E+08 8 2400 2160 2880 0.259% 10259.4 6.9E+08 9 1600 1440 1920 0.150% 10149.5 6.7E+08 10 800 720 960 0.000% 10000.0 6.5E+08 70 CHAPTER 6 CONTRIBUTIONS AND FUTURE WORK 6.1 Contributions 1. A new method is developed for searching the feasible runway orientation region with standard wind data. This method takes advantage of the Monte Carlo method, uses weighted distribution of random point to represent the wind distribution, and constructs the wind rose mathematically in polar coordinates. It avoids the intensive geometric calculation for partially covered cells and also guarantees the accuracy of usability calculation. 2. A model is proposed for optimizing the construction cost of runway location and orientation. To practically solve this problem, taxiway area and the areas for facility construction are also considered in the model with several assumptions. Earthwork cost, earthwork transportation cost and facility connection cost are included in this model since they are sensitive to runway location and orientation. A linear program is adopted to determine the optimal allocation of earthwork and corresponding earthwork transportation cost. A basic genetic algorithm, as discussed in section 3.4, can efficiently optimize the runway location and orientation. Compared to previous studies, the proposed model includes more factors and constraints that affect the runway location and orientation optimization problem. Thus, this model can comprehensively solve this problem. 3. A runway longitudinal-grade design optimization model is presented in chapter 4. Based on known location and orientation, this model can optimize the runway longitudinal- 71 grade design. FAA and ICAO runway design geometric specifications are satisfied. A genetic algorithm is adopted to search for the optimal solution. Some self-defined operators of GA are also developed for improving the performance of the GA. 4. Since the geometric constraints of runways are very strict, many randomly generated offspring are infeasible. To avoid generating infeasible offspring and to improve the computation efficiency, the feasible gate method is adopted here. As discussed in the section 4.3, feasible gates can be achieved after a series of calculations. 5. In the chapter 5, a case study is presented to test the performance of proposed models. The first model can efficiently obtain feasible runway orientations relatively quickly. The second model can find an optimized solution for runway location and orientation as expected. The third model optimizes the runway longitudinal-grade design. The optimized runway profile follows ground profile. 6. The sensitivity analysis shows that runway longitudinal-grade design is highly related to runway pavement cost, earthwork cost and earthwork transportation cost. The runway profile tends to be flatter when runway pavement cost increases. Similarly, the effective gradient of runway declines as the unit cost of earthwork and earthwork transportation decreases. 6.2 Future Work 1. Some validation of the proposed solution methods should be pursued in future studies. One possible method is a statistical test such as that presented in Jong and Schonfeld (2003). They fit a distribution to the fitness value of a randomly generated large sample of solutions. Based on the distribution, the probability of obtaining solutions better than optimized solution found by the genetic algorithm could be estimated. Hopefully, that 72 probability would be extremely small. Another possible way to validate the models is by comparing the outputs of the proposed models with the designs of other experienced airport engineers. 2. In future studies, additional factors should be considered in the model. For example, noise and land-use cost are two significant factors when the airport is close to residential areas. Airport accessibility also affects the location and orientation of a runway. 3. A model for optimizing multiple runway orientations and locations could be extended from the proposed model. For multiple runway systems, more details must be considered. Besides, the feasible regions of runway orientation should be determined based on multiple-runway cases. 4. Integrated models that simultaneously consider runway location, orientation and longitudinal-grade design may be developed in the future. 73 APPENDIX Table A1 Wind Data Speed Direction Number of observations 0-3 (knot) 4-6 (knot) 7-10 (knot) 11-16 (knot) 17-21 (knot) 22-27 (knot) 28-33 (knot) 34-40 (knot) Total 06 to 15 469 842 568 212 0 0 0 0 2091 16 to 25 568 1,263 820 169 0 0 0 0 2820 26 to 35 294 775 519 73 9 0 0 0 1670 36 to 45 317 872 509 62 11 0 0 0 1771 46 to 55 268 861 437 106 0 0 0 0 1672 56 to 65 357 534 151 42 8 0 0 0 1092 66 to 75 369 403 273 84 36 10 0 0 1175 76 to 85 158 261 138 69 73 52 41 22 814 86 to 95 167 352 176 128 68 59 21 0 971 96 to 105 119 303 127 180 98 41 9 0 877 106 to 115 323 586 268 312 111 23 28 0 1651 116 to 125 618 1,397 624 779 271 69 21 0 3779 126 to 135 472 1,375 674 531 452 67 0 0 3571 136 to 145 647 1,377 574 281 129 0 0 0 3008 146 to 155 338 1,093 348 135 27 0 0 0 1941 156 to 165 560 1,399 523 121 19 0 0 0 2622 166 to 175 587 883 469 128 12 0 0 0 2079 74 176 to 185 1,046 1,984 1,068 297 83 18 0 0 4496 186 to 195 499 793 586 241 92 0 0 0 2211 196 to 205 371 946 615 243 64 0 0 0 2239 206 to 215 340 732 528 323 147 8 0 0 2078 216 to 225 479 768 603 231 115 38 19 2253 226 to 235 187 1,008 915 413 192 0 0 0 2715 236 to 245 458 943 800 453 96 11 18 0 2779 246 to 255 351 899 752 297 102 21 9 0 2431 256 to 265 368 731 379 208 53 0 0 0 1739 266 to 275 411 748 469 232 118 19 0 0 1997 276 to 285 191 554 276 287 118 0 0 0 1426 286 to 295 271 642 548 479 143 17 0 0 2100 296 to 305 379 873 526 543 208 34 0 0 2563 306 to 315 299 643 597 618 222 19 0 0 2398 316 to 325 397 852 521 559 158 23 0 0 2510 326 to 335 236 721 324 238 48 0 0 0 1567 336 to 345 280 916 845 307 24 0 0 0 2372 346 to 355 252 931 918 487 23 0 0 0 2611 356 to 05 501 1,568 1,381 569 27 0 0 0 4046 Calm 7729 7729 Total 21676 31828 19849 10437 3357 529 166 22 87864 75 Figure A1 Index of Cross-Section Designs 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 REFERENCES [1] Ashford, N. J., Mumayiz, S., & Wright, P. H. (2011). Airport Engineering: Planning, Design and Development of 21st Century Airports. Wiley. [2] Aerodromes Design Manual, Part I (2006). 3rd Ed., Vol. 1, International Civil Aviation Organization (ICAO). [3] FAA. (2012). Airport design. FAA Advisory Circular. AC 150/5300-13A. Federal Aviation Administration, Washington, D.C. [4] Objects Affecting Navigable Airspace, 14-CFR-Part 77, Federal Aviation Administration Regulations, FAR Part 77, July 21,1975. [5] Bandara, S., & Wirasinghe, S. C. (1992). Optimum geometries for pier-type airport terminals. Journal of transportation engineering, 118(2), 187-206. [6] Espey, M., & Lopez, H. (2000). The impact of airport noise and proximity on residential property values. Growth and Change, 31(3), 408-419. [7] Prats, X., Puig, V., & Quevedo, J. (2011). A multi-objective optimization strategy for designing aircraft noise abatement procedures. Case study at Girona airport. Transportation Research Part D: Transport and Environment, 16(1), 31-41. [8] Chang, S. W. (2013). Crosswind based optimization of multiple runway orientations. Journal of Advanced Transportation. [9] Mousa, R. M., & Mumayiz, S. A. (2000). Optimization of runway orientation. Journal of transportation engineering, 126(3), 228-236. [10] Mousa, R. M. (2001). Integrated model for optimizing orientation of two-runway configurations. Journal of transportation engineering, 127(4), 342-351. [11] Jia, X., Chung, D., Huang, J., Petrilli, M., & The, L. (2004). ARO: Geographic information 93 systems-based system for optimizing airport runway orientation. Journal of transportation engineering, 130(5), 555-559. [12] Oktal, H., & Yildirim, N. (2013). New Model for the Optimization of Runway Orientation. Journal of Transportation Engineering. [13] Easa, S. M. (1988). Selection of roadway grades that minimize earthwork cost using linear programming. Transportation Research Part A: General, 22(2), 121-136. [14] Easa, S. M. (1988). Earthwork allocations with linear unit costs. Journal of Construction Engineering and Management, 114(4), 641-655. [15] Moreb, A. A. (1996). Linear programming model for finding optimal roadway grades that minimize earthwork cost. European Journal of Operational Research, 93(1), 148-154. [16] Jong, J. C., Jha, M. K., & Schonfeld, P. (2000). Preliminary highway design with genetic algorithms and geographic information systems. Computer‐Aided Civil and Infrastructure Engineering, 15(4), 261-271. [17] Jong, Jyh-Cherng, and Paul Schonfeld. (2003). "An evolutionary model for simultaneously optimizing three-dimensional highway alignments." Transportation Research Part B: Methodological 37.2: 107-128. [18] Jha, M. K., & Schonfeld, P. (2004). A highway alignment optimization model using geographic information systems. Transportation Research Part A: Policy and Practice, 38(6), 455-481. [19] Goh, C. J., Chew, E. P., & Fwa, T. F. (1988). Discrete and continuous models for computation of optimal vertical highway alignment. Transportation Research Part B: Methodological, 22(6), 399-409. [20] Puy Huarte, J. (1973), “OPYGAR: Optimisation and Automatic Design of Highway 94 Profiles”, PTRC Seminar Proceedings on Cost Models and Optimisation in Highways (Session L13), London. [21] Jong, Jyh-Cherng (1998). Optimizing highway alignment with genetic algorithm . PHD Disertation, University of Maryland , College Park. [22] Murchland, J. D. (1973), “Methods of Vertical Profile Optimisation for an Improvement to an Existing Road”, PTRC Seminar Proceedings on Cost Models and Optimisation in Highways (Session L12), London. [23] Kang, M. W., Schonfeld, P., & Jong, J. C. (2007). Highway alignment optimization through feasible gates. Journal of advanced transportation, 41(2), 115-144. [24] Kang, M. W., Schonfeld, P., & Yang, N. (2009). Prescreening and repairing in a genetic algorithm for highway alignment optimization. Computer‐Aided Civil and Infrastructure Engineering, 24(2), 109-119. [25] Fwa, T. F., Chan, W. T., & Sim, Y. P. (2002). Optimal vertical alignment analysis for highway design. Journal of transportation engineering, 128(5), 395-402. [26] Kim, D. N. and Schonfeld, P. M. (1997). “Benefits of Dipped Vertical Alignments for Rail Transit Routes“, Journal of Transportation Engineering 123, 20-27 [27] Laporte, G., Mesa, J.A., Ortega, F.A., 2002. Locating stations on rapid transit lines. Computers and Operation Research 29, 741–759 [28] Spasovic, L., Schonfeld, P., 1993. Method for optimizing transit service coverage. Transportation Research Record 1402, 28–39 [29] Kim, M., Schonfeld, P., & Kim, E. (2012). Comparison of Vertical Alignments for Rail Transit. Journal of Transportation Engineering, 139(2), 230-238. [30] Jha, M. K., Schonfeld, P., & Samanta, S. (2007). Optimizing rail transit routes with genetic 95 algorithms and geographic information system. Journal of Urban Planning and Development, 133(3), 161-171. [31] Lai, X., & Schonfeld, P. (2010). Optimizing Rail Transit Alignments Connecting Several Major Stations. In Transportation Research Board 89th Annual Meeting (No. 10-2837). [32] Lai, X., & Schonfeld, P. (2012). Optimization of Rail Transit Alignments Considering Vehicle Dynamics. Transportation Research Record: Journal of the Transportation Research Board, 2275(1), 77-87. [33] Mayer, R. H., & Stark, R. M. (1981). Earthmoving logistics. Journal of the Construction Division, 107(2), 297-312. [34] Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, Inc., Massachusetts. Haupt, R. L., & Haupt, S. E. (2004). Practical genetic algorithms. John Wiley & Sons.