@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix skos: . vivo:departmentOrSchool "Graduate Studies, College of (Okanagan)"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCO"@en ; dcterms:creator "Sarafrazi, Soroor"@en ; dcterms:issued "2017-03-12T00:00:00"@en, "2016"@en ; vivo:relatedDegree "Master of Science - MSc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description """Economy is one of the most important factors to develop a country and roads are vital to expedite the economy growth. Although road networks lead to social and economic development, the road construction and maintenance are expensive activities. Therefore, there is a strong interest in minimizing the construction cost, while satisfying safety and environmental constraints. Different road design models have been proposed, but the sensitivity of these models to their input parameters has not yet been analyzed. Sensitivity analysis of a road model before building the road is highly suggested because it helps to investigate the stability of the model and identify the parameters that have the most effect on the variability of the model output. In addition, sensitivity analysis helps to enhance the communication between modelers and decision makers (managers). Therefore, different sensitivity analysis methods are presented in this thesis and the sensitivity of a road model to its inputs is studied. Moreover, in a road design model, the ground is discretized into sections and the number of sections is highly correlated with the optimization time. Designing roads that consider all sections is too time consuming to be practical. Thus, different methods are presented in this thesis to reduce the number of sections while keeping the accuracy of the ground profile."""@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/59212?expand=metadata"@en ; skos:note "Sensitivity analysis and sectionpositioning for road design modelbySoroor SarafraziM.Sc., Shahid Bahonar University of Kerman, 2011A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Interdisciplinary Studies - Optimization)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)September 2016c© Soroor Sarafrazi, 2016The undersigned certify that they have read, and recommend to theCollege of Graduate Studies for acceptance, a thesis entitled: Sensitivityanalysis and section positioning for road design model submittedby Soroor Sarafrazi in partial fulfillment of the requirements of thedegree of Master of ScienceProf. Yves Lucet (Arts & Sciences, UBC Okanagan)Supervisor, Professor (please print name and faculty/school above the line)Dr. Jason Loeppky (Arts & Sciences, UBC Okanagan)Co-Supervisor, Professor (please print name and faculty/school above the line)Dr. Warren Hare (Arts & Sciences, UBC Okanagan)Supervisory Committee Member, Professor (please print name and faculty/school abovethe line)Dr. Kasun Hewage (School of Engineering, UBC Okanagan)University Examiner, Professor (please print name and faculty/school above the line)September 2016(Date Submitted to Grad Studies)iiAbstractEconomy is one of the most important factors to develop a country androads are vital to expedite the economy growth. Although road networkslead to social and economic development, the road construction and main-tenance are expensive activities. Therefore, there is a strong interest inminimizing the construction cost, while satisfying safety and environmentalconstraints. Different road design models have been proposed, but the sen-sitivity of these models to their input parameters has not yet been analyzed.Sensitivity analysis of a road model before building the road is highlysuggested because it helps to investigate the stability of the model and iden-tify the parameters that have the most effect on the variability of the modeloutput. In addition, sensitivity analysis helps to enhance the communica-tion between modelers and decision makers (managers). Therefore, differentsensitivity analysis methods are presented in this thesis and the sensitivityof a road model to its inputs is studied.Moreover, in a road design model, the ground is discretized into sec-tions and the number of sections is highly correlated with the optimizationtime. Designing roads that consider all sections is too time consuming tobe practical. Thus, different methods are presented in this thesis to reducethe number of sections while keeping the accuracy of the ground profile.iiiPrefaceA paper co-authored with Dr. Jason Loeppky and Dr. Yves Lucet isadapted from the second chapter of this thesis. This paper is submittedfor publication to the journal of Reliability Engineering & System Safety[SLL16]. In addition, a presentation, joint work with Dr. Jason Loeppkyand Dr. Yves Lucet, was adapted from the third chapter and given at the58th Canadian Operational Research Society Annual Conference in Banff,Canada.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . xDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: A Survey on the Sensitivity Analysis Methods forUnderstanding Complex Models . . . . . . . . . . 32.1 Sensitivity analysis . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Basic notation and definitions . . . . . . . . . . . . . . . . . . 62.3 Linear and monotonic Sensitivity Analysis (SA) methods . . 82.4 Nonlinear SA methods . . . . . . . . . . . . . . . . . . . . . . 92.4.1 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.2 Variance-mean . . . . . . . . . . . . . . . . . . . . . . 172.4.3 Factor screening methods . . . . . . . . . . . . . . . . 202.4.4 Derivative-based method . . . . . . . . . . . . . . . . . 212.4.5 Distance between distributions . . . . . . . . . . . . . 232.4.6 Moment independence measures . . . . . . . . . . . . 242.5 Surrogate-based methods for expensive function models . . . 252.6 Sensitivity indices for multivariate outputs . . . . . . . . . . . 262.6.1 Multivariate Sobol sensitivity analysis . . . . . . . . . 27vTABLE OF CONTENTS2.6.2 Sequential sensitivity analysis . . . . . . . . . . . . . . 272.6.3 Principal Components Analysis (PCA)-based multi-variate sensitivity analysis . . . . . . . . . . . . . . . . 282.6.4 Variance-based multivariate sensitivity analysis . . . 282.7 Numerical examples and discussion . . . . . . . . . . . . . . . 292.7.1 Study 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 292.7.2 Study 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 302.7.3 Study 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 342.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Chapter 3: Section positioning in the road design verticalalignment problem . . . . . . . . . . . . . . . . . . . 403.1 The road design problem . . . . . . . . . . . . . . . . . . . . . 403.2 The road design model . . . . . . . . . . . . . . . . . . . . . . 413.3 Section positioning methods . . . . . . . . . . . . . . . . . . . 453.3.1 Method 1: The heuristic method . . . . . . . . . . . . 453.3.2 Method 2: The regression tree . . . . . . . . . . . . . 453.3.3 Method 3: Piecewise constant approximation . . . . . 463.4 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . 483.4.1 Comparing the three methods . . . . . . . . . . . . . . 503.5 Summary of the section positioning methods . . . . . . . . . 59Chapter 4: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 60Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62viList of TablesTable 2.1 The Pearson, Spearman and the main Sobol sensitivityindices of four functions (2.27). . . . . . . . . . . . . . 30Table 2.2 The sensitivity indices of the linear and monotonicmethods for the Ishigami function. . . . . . . . . . . . 32Table 2.3 The numerical values of the Mckay and Sobol indicesobtained from symbolic integration in Maple for theIshigami function. . . . . . . . . . . . . . . . . . . . . . 32Table 2.4 The average of sensitivity indices of different nonlinearmethods for the Ishigami function. . . . . . . . . . . . 33Table 2.5 The Sobol and FAST indices for Moreb’s problem. . . 36Table 3.1 Approximation of Cut volumes using side-slopes for acut area. . . . . . . . . . . . . . . . . . . . . . . . . . . 45Table 3.2 Four different grounds. . . . . . . . . . . . . . . . . . 49Table 3.3 The performance of the heuristic method on GroundA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Table 3.4 The performance of the Regression tree on Ground A. 54Table 3.5 The performance of the piecewise constant approxima-tion method on Ground A. . . . . . . . . . . . . . . . 55Table 3.6 Comparing methods on Ground A according to twostopping criteria. . . . . . . . . . . . . . . . . . . . . . 55Table 3.7 Comparing methods on Ground B according to twostopping criteria. . . . . . . . . . . . . . . . . . . . . . 56Table 3.8 Comparing methods on Ground C according to twostopping criteria. . . . . . . . . . . . . . . . . . . . . . 56Table 3.9 Comparing methods on Ground D according to twostopping criteria. . . . . . . . . . . . . . . . . . . . . . 56Table 3.10 Comparing methods on Ground A based on the mate-rial volumes and according to two stopping criteria. . 57Table 3.11 Comparing methods on Ground B based on the mate-rial volumes and according to two stopping criteria. . 58viiLIST OF TABLESTable 3.12 Comparing methods on Ground C based on the mate-rial volumes and according to two stopping criteria. . 58Table 3.13 Comparing methods on Ground D based on the mate-rial volumes and according to two stopping criteria. . 58viiiList of FiguresFigure 2.1 The CSMXi(q) for three inputs of the Ishigami function. 18Figure 2.2 The effect of the symmetric reducing of the rangeto [q, 1 − q] on variance for the three inputs for theIshigami function. . . . . . . . . . . . . . . . . . . . . 19Figure 2.3 The scatter plot of Ishigami function with N = 1000. 31Figure 2.4 The road and ground profiles. . . . . . . . . . . . . . 34Figure 2.5 Summary of SA methods for inexpensive models. . . 38Figure 3.1 The vertical alignment of the ground profile. . . . . . 41Figure 3.2 The cross-section of a road with and without side-slopes. . . . . . . . . . . . . . . . . . . . . . . . . . . 44Figure 3.3 Approximation of side-slopes for a cut area. . . . . . 44Figure 3.4 Three iterations of the heuristic method. . . . . . . . 46Figure 3.5 Three iterations of the regression tree. . . . . . . . . . 47Figure 3.6 The piecewise constant approximation. . . . . . . . . 48Figure 3.7 Four ground profiles. . . . . . . . . . . . . . . . . . . 50Figure 3.8 An example for Algorithm 2 which approximates theside-slopes of merged sections. . . . . . . . . . . . . . 51ixAcknowledgmentsI would like to express my deep sense of gratitude to my supervisors Dr.Yves Lucet and Dr. Jason Loeppky for their updated knowledge, continuoussupport, great guidance and patience during my research.I also like to thank my committee members Dr. W. Hare, Dr. YvesLucet and Dr. Jason Loeppky for their great advice and inspiration.I truly appreciate the support of our industrial partner (Softree TechnicalSystems Inc.). In particular David Mills, Craig Speirs, and Alexis Guiguewere always very supportive and their technical information is highly appre-ciated.I owe my deepest gratitude to my parents, and family members for theirsupport and encouragement throughout my life.This research is partially funded by Natural Sciences and EngineeringResearch Council of Canada, Canada Foundation for Innovation, BritishColumbia Knowledge Development Fund, and Softree Technical SystemsInc.xDedicationTo my beloved parents and family members.xiChapter 1IntroductionA high quality road network can increase the standards of living, fa-cilitate trading and lead to social and economic development. However, aroad network has some negative effects including damaging environment,accidents, air and noise pollution [FJM+01]. Therefore, designing a roadimplies trade-offs between safety, social, environmental and economic im-pacts; it is a complicated and challenging process [JSJ06]. The road designis usually split into three interconnected stages: horizontal alignment, ver-tical alignment, and earthwork [HKL11].In the horizontal alignment, the road curve is examined from a satellite’seye view and the primary objective in this stage is minimizing environmentalissues and construction costs [EM07]. After the horizontal alignment is fixed,the starting and end points can be connected by a curve and the verticalground profile can be examined along this curve. In other words, a road’schange in elevation can be studied in the vertical alignment stage. Theprimary objective in this stage is minimizing the construction cost [HKL11].After the vertical alignment stage, the earth is rearranged with minimumcost in the earthwork optimization stage. In this stage, the ground profilechanges to a desired smooth road profile [MS81].In all stages of the road design model, there are several inputs and theiruncertainties lead to uncertainty in the model output. SA studies how themodel output uncertainty can be assigned to different sources of uncertaintyin inputs [SAA+10]. SA indicates if the model is robust to small changesin inputs and determines the robustness of the model when one or some ofthe model parameters are varied simultaneously [STCR04]. In other words,SA can help to improve the road design model and test the robustness ofa decision. Therefore, different SA methods are presented and comparedin this thesis and the most appropriate SA methods are applied to a roaddesign model.In addition to the SA of the road design model, the optimization time ofthis model should also be considered. In the road design model, the groundprofile is discretized into sections [HHLR14] and the optimization time isproportional to the number of sections. Optimizing long roads with a lot1Chapter 1. Introductionof sections is too time consuming to be practical. Therefore, the number ofsections should be reduced while considering a trade-off between time andaccuracy of approximation. Consequently, different methods are presentedand compared in this thesis for section positioning and reducing the numberof sections.This thesis is organized as follows. Chapter 2 is a survey paper on SAwhich is submitted for publication to the journal of Reliability Engineering& System Safety [SLL16]. This paper also includes SA on a road designmodel. Chapter 3 introduces and compares different methods for sectionpositioning. Finally, conclusions with directions for future research are pro-vided in Chapter 4.2Chapter 2A Survey on the SensitivityAnalysis Methods forUnderstanding ComplexModelsMathematical models representing real world situations are now ubiqui-tous across science, engineering and the humanities. One major challengewith these models is in understanding and quantifying the effect of uncertaininputs on the output of the function. In this Chapter, we review fundamen-tal sensitivity analysis methods and classify them to allow non-specialists toselect the method most appropriate for their specific problem. The classifi-cation is based on the SA method and assumption. These SA methods fornon-expensive models are summarized with a decision tree. We also considerthe sensitivity analysis of expensive models, and models with multivariateoutputs. The accuracy and computational costs of the methods are com-pared on three numerical examples and on a real-world application in roaddesign.2.1 Sensitivity analysisMathematical models widely used in natural sciences, engineering andnetwork science are subject to different sources of uncertainty, e.g., inaccu-rate parameter values, uncertain model structure, and unknown parameterranges [GMPS14]. Some of the biggest challenges for modelers are dealingwith uncertainty in the input parameters and finding the parameters thathave the largest effects on the model output. Different terms are used inter-changeably for these parameters, such as “important”, “sensitive”, “mostinfluential”, “effective”, “major contributor”, or “correlated (with output)”[Ham94, SCS+00]. Identifying the important parameters and understand-32.1. Sensitivity analysising their contributions to the output is one goal of sensitivity analysis (SA)[STCR04, OO04] and this goal is called factor prioritization [BP16].The other goals of the SA are factor fixing, model structure, direction ofchange and stability. Factor fixing is associated with finding the least im-portant inputs that can be fixed anywhere in their variability ranges. Themodel structure applies in cases where the model inputs affect the outputindividually or the interactions between inputs have an important role ininfluencing the output. Direction of change studies whether an increase (de-crease) in a model input causes an increase (decrease) in the model output.Stability determines the input space over which the optimal solution doesnot change [BP16].SA gives insight into a model’s behavior by these five goals [Alv09,Ham94]. SA also helps validating a model by factor fixing and model struc-ture goals [IL14, AIGMA05, CP02].SA has seen applications in a diverse setting. For example, it is used toassess the risk caused by the uncertainty in the parameters of a CO2 storagemodel [AON13]. Cannavo [Can12] implemented SA to validate and developa model that can best describe the state of volcano. Sellers and Crompton[SC04] implemented SA on a biomechanical model and they strongly en-courage the use of SA as a validation technique for modeling. Saint-Geourset al. [SGBG14] implemented a flood damage assessment model and thequality of the conclusions drawn from the model output are studied by SA.In [LMM14], SA is used to find the dependability of complex systems andhelps to predict failures and schedule maintenance.SA methods are based on producing a quantitative evaluation of thecontribution of each parameter in the form of sensitivity indices. Using thevalues of these indices, one can rank the input parameters from most impor-tant to least important. SA methods with different assumptions may leadto different ranking of inputs that influence the model output. Therefore,SA methods should be chosen properly to find the ranking most appropriatefor a given application [CHT00]. Using two or more methods with differentmechanisms is recommended to identify the key inputs with more confidence[CP02].SA methods are usually categorized into local and global methods. LocalSA methods concentrate on the sensitivity of the output with respect tosmall perturbations around the input values. In local SA, the values of theinput parameters of interest are perturbed, while the other parameters arefixed at their nominal values (all inputs are perturbed if the local sensitivityof output to all inputs is required). While local SA methods do not studythe whole ranges of inputs, they can capture co-dependencies using higher42.1. Sensitivity analysisorder derivatives or profile-based measures [SK11]. Global SA methods takeone or a combination of input parameters and study the model output overthe entire ranges of the input parameters [Sud08, SK11].One can classify global SA methods as mathematical, statistical or graph-ical [CP02]. However, in this paper, we choose to focus on the methodsassumptions and mechanisms. The global SA methods in this paper areclassified according to linear, monotonic and nonlinear methods.Linear SA methods assume a linear approximation of the model outputwith the variable of interest (where all others are ignored). If these methodsfind a highly important input, then the model has one active input and themodel can be approximated by a linear function of the important input.Monotonic SA methods assume modeling a monotonic relationship betweenthe model output with the variable of interest (where all others are ignored).Nonlinear SA methods do not assume any relationship between the modeloutput and inputs.In this paper, unlike the other review papers [IL14, Ham94, AIGMA05,Ham95], a wide range of global SA methods are studied and the presentedframework helps to choose an appropriate method where appropriateness isbased on the type of problems a method can solve and its computationalcost.When the evaluation of a function, provided as a black-box, is expen-sive in term of computation time, SA methods become too time consum-ing. In that situation, one needs to approximate the function using asurrogate. There are numerous methods to construct a surrogate modelsuch as moving Least-Squares [Lev98], Polynomial Chaos Expansion [Sud08,Ale13, DNM+03], Gaussian Process (GP) [OO04], Artificial Neural Network[MCLH14], linear model [PPS09], Support Vector Machine [BM08], Cheby-shev polynomials [WLZZ15], etc. In the present survey, we will focus on theGP methods since sensitivity indices are obtained while building the GPsurrogate (applying a Bayesian approach to the GP ). For other surrogatemodels, the sensitivity indices should be estimated after the surrogate isdeveloped.When a model is vector-valued (multivariate output), the model outputis time dependent (dynamic) or not (static). According to the model output,different SA methods have been presented in this chapter.For the static models with high dimensional outputs, Gamboa et al.[GJKL13] generalize the Sobol method. The sensitivity of dynamic modelscan be presented graphically or shown by indices. The sequential sensitivityanalysis method introduced in [PCS+96] and the PCA based method usedin [LMM11, LML+09, CMW06] present the sensitivity indices graphically.52.2. Basic notation and definitionsThe factor and time sensitivity indices introduced by Cao et al. [CDD13]are suggested for the sensitivity analysis of dynamic models. We discussboth static and dynamic multivariate sensitivity analysis in Section 2.6.The paper is organized as follows. Section 2.2 is devoted to basic no-tations and definitions. Section 2.3 presents the linear and monotonic SAmethods. The nonlinear SA methods are described in Section 2.4. Sec-tions 2.3 and 2.4 consider SA methods for nonexpensive models that can beevaluated quickly, while the methods for expensive models are discussed inSection 2.5. Section 2.6 presents the SA methods for models with multi-variate outputs. In Section 2.7, the SA methods are implemented on threenumerical examples and also on an engineering model with a comparisonof accuracy and computational costs. Finally, conclusions are provided inSection 2.8. These conclusions discuss how to pick a proper SA methodaccording to the SA goal, the number of model inputs and the complexitiesof the model and the SA methods.2.2 Basic notation and definitionsIn what follows a bold capital letter (X) denotes a matrix, a bold lower-case letter (x) is a vector, a regular capital letter (X) is a random variableand a scalar is denoted by a regular lower-case letter (x).The model input parameters are denoted by x = (x1, ..., xd) which hasdimension d. Let G(x) be the model function we wish to study; the possiblyvector-valued output is denoted by y = (y1, ..., yl) = G(x).The vector x−i of dimension d− 1 denotes all the inputs of x except xi.A subset of inputs is denoted by xR = (xi1 , xi2 , ..., xid′ ) with R = {i1, ..., id′}(d′ ≤ d). The complementary set for this subset is given by xRc (c denotesthe set complement) and contains the remaining inputs such that R ∪Rc ={1, ..., d} and R ∩Rc = ∅.Let fX(x) denote the joint distribution of a vector of random variables(x = (X1, ..., Xd)), then fXi(xi) =∫..∫fX(x)∏t6=i dxt is the marginal dis-tribution and FXi(xi) =∫ xi−∞ fXi(s)ds is the cumulative distribution func-tion (CDF) of Xi.The expectation, the variance, the standard deviation and the covariance62.2. Basic notation and definitionsof random variables X and Y are respectivelyE(Xi) =∫xifXi(xi)dxi,V (Xi) = E[(Xi − E[Xi])2],σXi =√V (Xi),Cov(Xi, Y ) = E[Xi − E[Xi]]E[Y − E[Y ]].When inputs are viewed as random variables, the output Y = G(X) isalso a random variable and E(Y ) =∫G(x)fX(x)dx is the output mean.The mean of G(X) conditional on knowing XR is given byE(Y |XR) =∫G(x)fXcR(x)dxRc ,where fXcR(x) is the conditional distribution of XRc .To estimate the sensitivity indices, N samples for each random variableare used. The sth sample of the input is indicated by xs = (x1,s, ..., xd,s),which leads to the output ys. Further let x¯i and σ2Xidenote the usual samplemean and variance of the ith coordinate.Remark 2.1 (Dependent inputs). Most SA methods assume the inputs areindependent. Consequently, these methods cannot be directly implementedon models with dependent inputs. For example, if x1 is dependent on x2,then the sensitivity index of x1 indicates the contributions of both x1 andx2.A procedure to define a set of independent parameters from a set ofdependent inputs is suggested by Mara and Tarantola [MT12]. These trans-formed inputs are then used to study the sensitivities using the methodsdiscussed in Sections 2.3 and 2.4. The new orthogonal input parametersx′ = (X ′1, X ′2, ..., X ′d) can be obtained from the dependent normal inputsx = (X1, X2, ..., Xd) using the following procedure [MT12]{X ′1 = X1,X ′i = Xi − E(Xi|X ′1, ..., X ′i−1), ∀i = 2, ..., d.It is assumed that the conditional expectation distinguishes the depen-dency between the inputs. The new inputs x′ = (X ′1, X ′2, ..., X ′d) are inde-pendent and orthogonal.It should be noted that this procedure produces new independent inputsand the sensitivity indices of these independent inputs do not indicate theimportance of the original inputs (the dependent inputs).72.3. Linear and monotonic SA methodsDepending on the problem, a change of variable to obtain independentinput followed by SA of output with respect to the new independent inputsmay be acceptable. Otherwise, the methods in Remark 2.4 or Subsection2.4.6 should be used.Remark 2.2 (Monte Carlo integration). Numerical integration is a particularusage of Monte Carlo methods, which were named by Ulam and Metropo-lis [MU49].Consider the integration I =∫Ω f(x)dx and let V =∫Ω dx. Monte Carlointegration uses N samples of x to estimateI ≈ I ′ ≡ VNN∑s=1f(xs).The error of Monte Carlo integration is independent of the number of di-mensions and proportional to 1/√N . Thus, the convergence of Monte Carlointegration can be slow but does not suffer from the “curse of dimension-ality”. Techniques to improve the performance of Monte Carlo integrationare discussed in [Wei00].2.3 Linear and monotonic SA methodsIn this section, SA methods that find the linear and monotonic effects ofeach input Xi on the output Y = G(x) are described. Because these meth-ods are mainstream, only a brief sketch of the methods are provided. Bothmethods assume inputs are independent. Pearson’s method is a correlation-based SA method and is a linear SA method. An example of MonotonicSA method is Spearman’s method that is also correlation-based sensitiv-ity analysis method. For finding the Pearson and Spearman coefficients, Nsamples for input x, which lead to N samples for the output Y , (y1, .., yN ),are considered.The concept of correlation was first introduced by Galton in 1888 [Gal88]and the Pearson (product-moment) correlation r was proposed by Pearsonin the 1890s [Pea95]. The correlation between the input Xi and the outputY = G(x) that shows the sensitivity of Xi is given byri =Cov(Xi, Y )σXiσY≈∑s(xi,s − x¯i)(ys − y¯)√∑s(xi,s − x¯i)2√∑s(ys − y¯)2, (2.1)where cov(X,Y ) denotes the covariance of X and Y .82.4. Nonlinear SA methodsThe positive or negative value of cov(X,Y ) shows the positive or negativeslope of Y as a function of X. The correlation coefficient (−1 ≤ ri ≤ 1)measures both the strength and direction of a linear relationship betweenXi and Y . If ri = ±1, it means input i is linearly important. If Xi andY are independent, then the covariance and the correlation are zero, butthe reverse is not always true. This method does not identify nonlinearrelationships between the input and output [Con80].The Spearman correlation is computed by replacing the data with theirranks in the Pearson correlation coefficient. In this situation, the Spearmancorrelation coefficient can be used to determine sensitivities of monotonicrelationships between the model output with the variable of interest (whereall others are ignored). SA methods that do not consider linear or mono-tonic relationships between model output and inputs are studied in the nextsection.2.4 Nonlinear SA methodsIn this section, nonlinear SA methods that do not assume any specificrelationship between model output and inputs are presented . These meth-ods are based on various mechanisms such as variance, metric distance anddifferentiation. In what follows we assume that the inputs are independent.2.4.1 VarianceIn this subsection, SA methods based on variance are introduced. Theyare classified into decomposing and classical approaches. In a decomposingapproach, such as Sobol’s method, a “decomposition” of the original modelis first computed. By this decomposition, the mapping factor between in-puts and output and all the sensitivity indices can be obtained. In theclassical family of methods, the Fourier Amplitude Sensitivity Test (FAST)estimates the variances directly to obtain the sensitivity indices [CFS+73,CLS78]. Higher order interactions can be computed using the ExtendedFAST method [STC99].Sobol’s methodSobol’s method is a global SA method for nonlinear models. It decom-poses the output variance and then analyzes the variances decomposition[Sob01]. In other words, the Sobol’s method is an analysis of variances92.4. Nonlinear SA methods(ANOVA) decomposition. The Sobol sensitivity indices are obtained fromthe ANOVA decomposition of G(x)G(x) = G0 +∑iGi(xi) +∑i x2 > x3.The Wei indices show x1 is the most important input because by re-ducing its distributions, the output variability is highly affected. The Wei322.7. Numerical examples and discussionTable 2.4: The average of sensitivity indices of different nonlinear methodsfor the Ishigami function.inputs/SI x1 x2 x3 sum Model runsBorgonovoave 0.28 0.30 0 0.58 3,000Borgonovostd 0.02 0.02 0 -Mckay ηavei 0.34 0.36 0 0.70 4,046Mckay ηstdi 0.04 0.04 0.02 -Sobol SIavei 0.34 0.35 0 0.69 4,000Sobol SIstdi 0.03 0.03 0.05 -Sobol SItot,avei 0.64 0.36 0.30 - 4,000Sobol SItot,stdi 0.05 0.02 0.02 -EFAST SIavei 0.34 0.39 0 0.73 301EFAST SItot,avei 0.64 0.37 0.30 - 903Morris µ∗,avei 9.24 7.87 7.82 - 4,000Morris µ∗,stdi 0.22 0 0.23 -Morris σavei 0.24 0.24 0.34 -Morris σstdi 0 0 0 -Wei SIavei 0.25 0.19 0.06 2,048Wei SIstdi 0 0 0Wei SItot,avei 0.72 0.53 0.56 2,048Wei SItot,stdi 0 0 0total sensitivity indices confirm that if the input distributions reduce, theinput x1 has the most interactions with others. It should be noted that thesmall number of model runs (2,048) in Wei’s method is due to the use of asurrogate.As each method gives a specific information, it can be concluded theinputs x1 and x2 have the most influences on the output sensitivity and x1has the most interactions with other inputs (the total sensitivity of x1 ishigher than the other inputs). The results match Formula (2.28): first ordersensitivity indices for x1 (resp. x2) is responsible for around 34% (resp.35%) of the variation due to the term sin(x1) (resp. a sin2(x2)). There isa nonlinear interaction since first-order interactions sum to 69%; it is thebx43 sin(x1) term that appears as a 64% total variation index for x1 so 30%is due to higher order interactions while x3 only exhibits a 30% higher order332.7. Numerical examples and discussion0 200 400 600 800 1000 1200 1400 160025303540length (m)height (m) RoadGroundSegment 2Segment 1 Segment 3Figure 2.4: The road and ground profiles.interaction.2.7.3 Study 3We consider a simple road design model [KL10, Mor96] which minimizesthe construction cost. Figure 2.4 shows the ground, and the road. The ver-tical dashed lines indicate the sections. The road is divided into 3 segments(pieces on which the road is a quadratic function) as indicated as darkerdashed vertical lines. The first, second and third segments are divided into2, 2 and 4 sections, respectively.The general parameters in this model are n the number of sections, ngthe number of sections in each segment, Ai the area of section i, hi averageground height of section i, xi the start point of section i, and tg the x-coordinate at the end of segment g.The cost parameters are qd the cost of embanking to a landfill (dump)pit, pb the cost of excavating from a borrow pit, p the cost of excavating fromeach section, q the cost of embanking to each section, Cij(or Cid) the costof transporting one cubic unit from section i to j (or to the dump pit), andCbi the cost of transporting one cubic unit from the borrow pit to section i.The decision variables are ui the height of earth removed from section i,vi the height of earth added to section i, Tij the number of units transportedfrom section i to j (AiTij is the transferred volume), and agk the coefficientof xk in the quadratic model of the road on segment g.342.7. Numerical examples and discussionThe quadratic model for each segment isPg(x) = ag0 + ag1x+ ag2x2, x ∈ [tg−1, tg], i = 1, ..., ng, g = 1, 2, 3.The objective function in this linear programming model is to minimizethe total cost of embankment, hauling and excavation, i.e.minCost =n∑i=1(pAiui + qAivi)+n∑i=1n∑j=1,i 6=jCijAiTij +n∑i=1((Cid + qd)AiTid + (Cbi + pb)AiTbi)The following constraint ensures that the transported volume to or froma section is equal to the work done at that sectionn∑j=1,i 6=jAi(Tij − Tji) = Ai(ui − vi), i = 1, 2, ..., n.which can be simplified inton∑j=1,i 6=jTij − Tji = ui − vi, i = 1, 2, ..., n.The smoothness and continuity constraints of splines arePg(tg) = Pg+1(tg), g = 1, 2,P ′g(tg) = P′g+1(tg), g = 1, 2.The gap constraint ishi(xg,i+1−xg,i)−∫ xg,i+1xg,iPg(x) = (ui−vi)(xg,i+1−xg,i); i = 1, ..., ng, g = 1, 2.The slope constraints aremaxx∈[tg−1,tg]P ′g(x) ≤ U g = 1, 2, 3,minx∈[tg−1,tg]P ′g(x) ≥ L g = 1, 2, 3,where t0 = x1 = 0. The road height at the initial point and final point shouldbe 32m and 31m, respectively. The sensitivity analysis is implemented on352.7. Numerical examples and discussionthis model to find the importance of ground height and cost parameters.The sensitivity of the ground heights at the start and end points are notstudied because changing them may make the problem infeasible, and thesevalues are usually known with much greater accuracy. The range of costparameters is (0, 5) and the height parameters range is (20, 40) (these rangesare suggested by experts).All the SA methods can be implemented on this problem but we chosethe FAST method as a nonlinear variance based SA method. This problemis not high dimensional (7 height parameters and 5 cost parameters) andthe number of inputs is smaller than the maximum number of inputs for theFAST method. In addition, when a model is not high dimensional, FAST isthe cheapest method among the other variance based SA methods.Since the FAST and Sobol’s methods provide the same information, wealso implemented Sobol’s method to increase confidence in the results. An-other verification method is to run Sobol’s method several times and verifythat the standard deviation is small enough.Table 2.5: The Sobol and FAST indices for Moreb’s problem.inputs/SISobol FASTSI ave SI sd SItot ave SItot sd SIp 0.07 0.03 0.07 0.00 0.06q 0.06 0.03 0.07 0.00 0.06pb 0.00 0.03 0.00 0.03 0qd 0.00 0.03 0.00 0.02 0C 0.26 0.02 0.33 0.01 0.25h2 0.11 0.03 0.20 0.01 0.11h3 0.03 0.03 0.13 0.01 0.03h4 0.00 0.03 0.05 0.01 0.01h5 0.01 0.03 0.09 0.01 0.01h6 0.02 0.03 0.10 0.01 0.02h7 0.02 0.03 0.11 0.01 0.03h8 0.12 0.03 0.23 0.01 0.13sum 0.70 - - - 0.71In our tests, Equation (2.3) resulted in large negative indices so we usedEquation (2.6). To verify the result, we compared Sobol’s with FAST in-dices (Sobol’s method uses 13,000 model runs and the FAST method uses5,861 model runs). In addition, Sobol’s method was run 20 times. The av-362.8. Discussionerage and standard deviation of the Sobol indices with the FAST indices areshown in Table 2.5. For expensive models, we suggest to run Sobol’s method(Formula (2.6)) once and compare the result with the FAST method.The FAST method is deterministic, so we ran it once. We could not usethe EFAST method in the SAinterface [Jac06] library since it is limited to10 inputs for finding the total sensitivity indices.As Table 2.5 shows the C parameter, which is the transportation cost, isthe most important parameter while the pb and qd are unimportant and haveno interaction with other inputs. However, we cannot simplify the modelby removing the dump and borrow pits since they are used at the optimalsolution.2.8 DiscussionFigure 2.5 summarizes the SA methods for non-expensive models with adecision tree.The SA methods have different assumptions and mechanisms and aproper method for a specific goal should be used. For the factor prioritiza-tion, factor fixing and model structure goals, the screening or the variancebased methods can be applied. The monotonic SA method and plotting theANOVA decomposition (plotting G(x) versus Gi(xi) (Equation 2.2)) can beused for the model structure goal. The Wei method can be used for thestability goal.While stability goal applies to linear programming (LP) problems [BP16],a parametric LP analysis (which is not studied in this paper) can also beused [BBM03, Fil11]. A Matlab-based toolbox for parametric LP analysiscan be found in [MPT].In addition to sensitivity analysis objectives, the complexity of eachSA method should be taken into account for choosing a proper method.The maximum numbers of inputs for FAST (in GSAT library [Can14]) andEFAST (in SAinterface library [Jac06]) are 50 and 10, respectively (in theirimplementation). However, using EFAST with 50 inputs is still expensiveand Saltelli et al [SRTC05, SRTC12] suggest to use the variance based meth-ods when the model inputs are smaller than 20 or the model requires a smallamount of CPU time (up to 1 min per run). When the model is low dimen-sional, the number of function evaluations of EFAST is smaller than thenumber of function evaluations used in the Sobol method. In this case, wesuggest to use the EFASTT method instead of the Sobol method.Saltelli et al [SRTC05, SRTC12] suggest to use the screening method372.8. DiscussionSensitivityAnalysismethodsNonlinearVariance basedWeiSobolFirst-ordervariancecoefficientEFASTFASTmomentindependencemeasuresBorgonovoDistance ChunFactorscreening RadialscreeningmeasureMorrisDerivative-based DGSMWangVariance-mean basedTarantolaMonotonicCorrelation-Ranking basedSpearmanLinearCorrelationbasedPearsonFigure 2.5: Summary of SA methods for inexpensive models.based on radial sampling (Subsection 2.4.3) when the CPU time for eachrun of the model takes up to 10 min per run or the number of inputs is upto 100.Increasing the number of samples, increases the accuracy of sensitivityindices. In this paper, the number of samples for Sobol’s method is set to1, 000. If 1, 000 samples is expensive for a model (because each run of modeltakes more than 10 min or the number of inputs is more than 100), using thesurrogate methods described in Section 2.5 is suggested for this expensivemodel. Among all the surrogate methods, we suggest the Gaussian processbecause it accounts for uncertainty.In case of multivariate output models which are specific problems, differ-ent methods are discussed in Section 2.6. If the model is static, the Gamboaet al. [GJKL13] method is suggested. The sequential SA or the PCA basedSA is recommended to graphically present the sensitivity indices of a dy-382.8. Discussionnamic model. Cao et al. [CDD13] introduce two different indices (time andfactor sensitivity indices) for dynamic models. The time index finds thesensitivity of output at time ty (y(ty)) to an input at specific time (t∗) andthe factor index finds the sensitivity of (y(ty)) to an input at all time priorto time ty.Sobol’s and FAST methods are implemented on a road design model.The importance of cost and height parameters are studied for specific inputranges. The most important parameter was found to be the transportationcost. In the future, a more thorough study of the importance of all parame-ters of this model is needed to compute a range for each input on which theoptimal solution is meaningful.39Chapter 3Section positioning in theroad design verticalalignment problemThe road design problem is usually split into horizontal alignment, ver-tical alignment, and earthwork. After the horizontal alignment is fixed, thevertical alignment problem considers a discretization of the ground into sec-tions. The number of sections is directly linked to the computation time. Alarge number of sections increases the calculation time to find the optimalvertical alignment. We study different methods to approximate the groundwith non-uniformly spaced sections. The presented methods are comparedwith a commercial road design software.3.1 The road design problemA country’s economic development is highly correlated with the qual-ity of its road network. A reliable road network connects people, markets,services and knowledge together. In other words, the road network hasa huge impact on the economic growth. However, the road constructionand its maintenance are expensive activities. Therefore, the road designmodel should be optimized by minimizing the construction cost and consid-ering safety constraint, environmental and socioeconomic impacts [HHLR14,HAMM13].In the road design problem, the ground profile is discretized into seg-ments and sections as shown in Figure 3.1. In this figure, the ith sectionis shown by Si and Segment j is presented by Segj . Considering numeroussections in optimizing the road design model is too time consuming to bepractical. Therefore, we present different methods to select a reasonablenumber of sections and position them in a way that still provide enoughaccuracy on the resulting road alignment.The inputs to these methods consist of the number of sections (N), their403.2. The road design model Height (m) x (m) 𝑆1 𝑆2 𝑆3 𝑆4 𝑆5 𝑆6 𝑆7 𝑆8 𝑆9 𝑆10 𝑆11 𝑆12 𝑆13 𝑆14 𝑆15 𝑆𝑒𝑔1 𝑆𝑒𝑔2 𝑆𝑒𝑔3 Ground profile Road profile Figure 3.1: The vertical alignment of the ground profile.distances from the starting point (x = (x0, x1, ..., xN )) and their heights(h = (h0, h1, ..., hN )). The outputs are denoted (N′,x′,h′) where N ′ < N .This paper is organized as follows. Section 3.2 presents the model. Sec-tion 3.3 is devoted to explaining the methods used for section positioningand reducing the number of sections. These methods are implemented ondifferent grounds and compared with each other in Section 3.4. Finally,conclusions are provided in Section 3.5.3.2 The road design modelFor a good accuracy, the ground profile and the construction cost shouldbe estimated well. The cost is dependent on the material volume and theground profile. A linear programming road design model which has multi-material and side slope features is presented in this section. This modelconsists of several parameters, variables and constraints, which are intro-duced as they appear.In this model, the ground profile is discretized into N sections and eachsection is presented by its height hi and the start point (xi). Sections aregrouped into segments and the number of sections in each segment is shownby ng [HHLR14, KL10, Mor96]. For example, the number of sections (ng)in segments 1, 2 and 3 of Figure 3.1 are 4, 8 and 3, respectively. The x-coordinate at the end of segment g is shown by tg and the quadratic roadmodel for each segment is defined as413.2. The road design modelPg(x) = ag0 + ag1xi + ag2x2i , xi ∈ [tg−1, tg], i = 1, ..., ng, g ∈ G .where G is the index of segments. A quadratic function is used to avoidsharp connections and have linear programming problem. If cubic or higherorder spline is used, then the constraints cannot be enforced with linearprogramming.The road should be smooth and continuous which means the height andthe slope of the ending section of a segment should be equal to the heightand slope of the beginning section of the next segment. The smoothnessand continuity constraints of splines arePg(tg) = Pg+1(tg), g ∈ G − 1,P ′g(tg) = P′g+1(tg), g ∈ G − 1.(3.1)The slope constraints, which are considered for safety, aremaxx∈[tg−1,tg]P ′g(x) ≤ U g ∈ G ,minx∈[tg−1,tg]P ′g(x) ≥ L g ∈ G .(3.2)During the road construction, not only may some material need to bemoved between sections, but also some materials may be brought from Bor-row pits to sections or dumped from sections to Waste pits. Thus, theBorrow and Waste pits are considered as the external sections in the roaddesign problem.Let the variables V +i , and V−i represent the total cut and fill materialvolumes of section i, respectively. The cost parameters areqd : the cost of embanking to a Dump pit,pb : the cost of excavating from a Borrow pit,p : the cost of excavating from each section,q : the cost of embanking to each section,Cij : the cost of transporting one cubic unit from section i to j,Ciw : the cost of transporting one cubic unit from section i to the Waste pit,andCbi : the cost of transporting one cubic unit from the Borrow pit to sectioni.The objective function in this linear programming model is to minimize423.2. The road design modelthe total cost of embankment, hauling and excavation,min Cost =n∑i=1(pV +i + qV−i )+n∑i=1n∑j=1,i 6=jCijTij +n∑i=1((Ciw + qw)Tiw + (Cbi + pb)Tbi),(3.3)where the variables Tij, Tbi and Tiw represent the transferred volume fromsection i to j, the transferred volume from Borrow pit to section i and thetransferred volume from section i to Waste pit, respectively.The material volume moved from section i to other sections or Waste pitshould be equal to the volume cut from section i. Similarly, The materialvolume brought from other sections or Borrow pit to section i should beequal to the volume filled to section i. These constraints, which are calledbalance constraint, are defined asN∑j=1,i 6=jTij + Tiw = V+i , i, j ∈ N,n∑j=1,i 6=jTji + Tbi = V−i , i, j ∈ N.(3.4)In order to make the road durable, side-slopes are used. Side-slope refersto gradual increase (decrease) in height from a fill (cut) section of the groundprofile to the height of the road profile [HHLR14]. In Figure 3.2, the cross-section of a road with and without side-slopes for a cut and a fill are shownrespectively.To model the side-slopes, trapezoid shaped cross-sections are approx-imated with several rectangles. Each rectangle is presented by an index(level), the altitude of the lth rectangle at section i is shown by the OffsetLi,l and the variable ui is the difference between the ground and road heightsat section i asP (xi)− hi = ui i ∈ N. (3.5)An example of a side-slope for a cut area is shown in Table 3.1 and Figure 3.3.Assume ui = 7m, then l should be 5 and the cut volume can be computedeasily by R+i,4 +R+i,5−R+i,4Li,5−Li,4 (Li,5 − ui) = 215.25.433.2. The road design modelFigure 3.2: The cross-section of a road with and without side-slopes. Cut area without side-slope Cut area with side-slope Ground profile Road profile 𝐿𝑖,1 𝐿𝑖,4 𝐿𝑖,3 𝐿𝑖,2 𝐿𝑖,5 𝑈𝑖 Figure 3.3: Approximation of side-slopes for a cut area.In other words, the gap constraint areV + =R+i,l +R+i,l+1 −R+i,lLi,l+1 − Li,l (Li,l+1 − ui), i ∈ N, l ∈ {l′|Li,l′ ≤ ui < Li,l′+1},V − =R−i,l +R−i,l+1 −R−i,lLi,l+1 − Li,l (Li,l+1 − ui), i ∈ N, l ∈ {l′|Li,l′ ≤ ui < Li,l′+1},(3.6)where R+i,l and R−i,l are the cut and fill volumes at section i and level l,respectively.While the shrink and swell factors and compaction are material depen-dent, the model uses banked units to compute the transportation costs andthus avoids the complexity of tracking material dependent factors withoutany loss in approximation [Koc10, Remark 1.6].443.3. Section positioning methodsTable 3.1: Approximation of Cut volumes using side-slopes for a cut area.Level l Offset Li,l Cut Volume R+i,l1 0 02 2 0.083 4 70.064 6 168.445 8 262.06The optimization time for this model is dependent on the number ofsections (the cost model is an aggregate model that does not go into thedetails of construction duration). Considering a lot of sections approximatesthe ground profile well but increases the optimization time. Keeping theapproximation accuracy while reducing the optimization time can be doneby the section positioning methods presented in the following section.3.3 Section positioning methodsThe methods used for section positioning are the heuristic method usedin the RoadEng software, the regression tree [JWH14], and the piecewiseconstant approximation method [KK88]. These methods are explained inthe following Subsections.3.3.1 Method 1: The heuristic methodIn this method, N1 uniform sections are picked from N uniform sectionsand the optimal cost is computed. If|CostN1−Cost2N1 |CostN1<  is not satisfied,then N1 is doubled until|CostN1−Cost2N1 |CostN1<  is passed and 2N1 is returnedas the number of sections. Three iterations of this method are presented inFigure 3.4.3.3.2 Method 2: The regression treeIn this method, x is the feature of sections and h is the response. First,all sections are considered as a single section (all sections are consideredin a single leaf). Afterward, h¯leaf and S presented in equation (3.7) arecalculated and two leaves are added by examining all the binary splits of allvariables value to find a value which leads to the largest decrease in S. This453.3. Section positioning methods Figure 3.4: Three iterations of the heuristic method.procedure continues until a stopping criterion is reached (Snew < δSold, δis small and defined by user) [JWH14]. The pseudo-code of this method ispresented in Algorithm 1.[ht]h¯leaf =1nleaf∑i∈leafhi,S =∑leaf∈leaves(Tree)∑i∈leaf(hi − h¯leaf )2.(3.7)Algorithm 1: The regression tree1: Consider all sections in a single leaf.2: Calculate S (3.7).3: Search over all binary splits. Take a split which can reduce S as muchas possible and add two new leaves.4: If the largest decrease in S is less than δS, go to Step 5. Otherwise, goto Step 2.5: Return the number of Sections N ′ (N ′ ≤ N).Three iterations of the regression tree are presented in Figure 3.5. Asthis figure shows, two sections (leaves) are added by binary split.3.3.3 Method 3: Piecewise constant approximationSuppose f(x), the ground profile is a piecewise constant function on aninterval x. The piecewise constant approximation approximates f(x) byg∗(x) which has the minimum number of constant pieces ((n(g∗)) or thenumber of sections). In other words, the piecewise constant approximationsolves463.3. Section positioning methods Figure 3.5: Three iterations of the regression tree.minn(g)s.t. ‖g − f‖∞ ≤ ′,(3.8)where ‖g‖∞ is the infinity norm of g [KK88]. For each section, the followingvariables are computedui = fi + ′,li = fi − ′,(3.9)and the algorithm connects section j to i if(i) min{ut|i < t ≤ j} ≥ max{lt|i < t ≤ j},(ii)ui ≥ max{lt|i < t ≤ j},(iii)li ≤ min{ut|i < t ≤ j}.(3.10)This method has linear complexity and is optimal for finding the numberof constant pieces with the constraint in Equation (3.8) [KK88]. Threeiterations of this method are shown in Figure 3.6.In this method, the best value of input ′ is unknown and can also beobtained bymin ||g − f ||2,s.t. n(g) ≤ k, (3.11)where k is the minimum value of n(g) obtained from Equation (3.8). Thecomplexity of problem (3.11) is O(kn2) [KK88] but Fulop et al. improvedthis complexity to O(n2 + kn log n) [FP92].In the road design model, the number of sections which provides a trade-off between optimization time and approximation accuracy is unknown.Therefore, Equation 3.11 cannot be used to obtain ′ since k in this Equation,473.4. Results and Discussion 2ϵ’ 2ϵ’ Figure 3.6: The piecewise constant approximation.which is the appropriate number of sections, is unknown. Consequently, thevalue of ′ for section positioning problem need to be defined by numericaltests.The values of δS and ′ are not related in this research as there aredifferent metrics to relate these values and we do not know which one is thebest. More details about these values are provided in Subsection 3.4.1.3.4 Results and DiscussionThe three methods presented in this thesis are implemented on fourdifferent grounds. The number of sections N , the number of levels nl, theoptimal cost and the time for building a road from these grounds are shownin Table 3.2 and Figure 3.1. In Table 3.2, N presents the number of sections,nl indicates the number of levels for approximation the cut and fill volumesand T Solve is the optimization time (sec). It should be noted that thesegrounds are small part of real grounds and used as case studies in the presentthesis.Optimizing road construction from these grounds were solved using aC++ code in Visual Studio 2012 that called CPLEX 12.5.1.0 on a Windows7, 64 bit computer with 4 cores hyper threading and 3.2 GHz.In order to reduce the number of sections, similar and close sections aremerged and represented as one section. The height of the new section is theheight of the first section in the merged sections. The average and medianof the merged sections heights can also be considered for the height of the483.4. Results and DiscussionTable 3.2: Four different grounds.Ground N nl Cost ($) T SolveA 2,368 22 493,306 27B 941 42 163,953 12C 2,309 62 3,780,000 26D 948 42 232,582 64new section. As the sectioning methods merge the consecutive sections thathave similar heights, all the metrics for presenting the new section heightmay lead to similar results.In order to approximate the side-slopes for this new section, Algorithm 2is used and an example for merging three sections with four levels is shownin Figure 3.8. According to this Figure, the properties of the new sectionfrom merging three sections are as described in the following paragraphs.Algorithm 2: The algorithm for approximating the side-slopes ofmerged sections1: Find the minimum (h′j,min) and the maximum (h′j,max) (j ∈ N ′) ofhi + Li,l, i ∈ the merged sections.2: Divide |h′j,max − h′j,min| to equal nl Offsets and obtain all L′j,l.3: The material volume related to the Offset L′j,l is the sum of volume ofrectangles (slabs) which satisfies the constraints h′j + L′j,l′−1 < hi + Li,land h′j +L′j,l′ ≥ hi +Li,l ( j ∈ N ′, i ∈ the merged sections and l, l′ ≥ 1).The height of the new section is equal to the height of the first section(h′ = h1) and the number of levels in the new section and the merged sectionsare equal. In addition, the maximum height of the new section slab (h′max)is equal to the maximum height of the merged sections slabs (h1 + L1,4).Similarly, the minimum height of the new section slabs (h′min = h′ + L′0) isequal to the minimum height of the merged sections slabs (h3 + L3,0).In Figure 3.8, The volumes in the slabs of the merged sections are ap-peared in the slabs of the new section based on the third step of Algorithm2. According to this Algorithm, the volume of each slab of the new sec-tion is the sum of the volumes of the slabs of the merged sections thath′j + L′j,l′−1 < hi + Li,l ≤ h′j + L′j,l′ (l, l′ ≥ 1). For example, the bot-tom slab of the new section contains V3,1 but not V2,1 and V1,1 because493.4. Results and Discussion0 200 400 600 800 1000 1200402040404060408041004120Ah (m)0 100 200 300 400 500 600 700 800 900 1000165170175180185190Bh (m)0 500 1000 1500 2000 2500115012001250Ch (m)0 100 200 300 400 500 600 700 800 900 1000350360370380390Dh (m)x(m)GroundGroundGroundGroundFigure 3.7: Four ground profiles.h′ + L′0 < h3 + L3,1 ≤ h′ + L′1 but h′ + L′0 < h2 + L2,1  h′ + L′1 andh′ + L′0 < h1 + L1,1  h′ + L′1. Consequently, V2,1 and V1,1 are in the sec-ond slab of the new section because h′ + L′1 < h1 + L1,1 ≤ h′ + L′2 andh′ + L′1 < h2 + L2,1 ≤ h′ + L′2.3.4.1 Comparing the three methodsAs δ in the regression tree and ′ in the piecewise constant approximationmethod are unknown, 20 values for them are considered (10−9 ≤ δ ≤ 10−1and 10−2 ≤ ′ ≤ 100.5). For the heuristic method, six iterations are consid-ered and in each iteration, N1 sections (N1 ≈ N/(27−iteration)) are picked (7is the number of iterations +1). We considered smaller number of iterationsfor the heuristic method than the other methods because if 20 iterationsare considered for this method, then the number of iterations +1 = 21 andN1 ≈ N/(221−iteration) returns very small number of sections in the first503.4. Results and Discussion Sec1 Sec2 Sec3 h1 h2 h3 𝑉1,1 𝑉1,2 𝑉1,3 𝑉1,4 𝑉2,4 𝑉3,4 𝑉2,3 𝑉3,3 𝑉2,2 𝑉3,2 𝑉2,1 𝑉3,1 𝑉3,1 𝑉1,1 𝑉2,1 𝑉2,2 𝑉3,2 𝑉1,2 𝑉2,3 𝑉3,3 𝑉1,3 𝑉1,4 𝑉2,4 𝑉3,4 Merged to ℎ′𝑚𝑖𝑛 = ℎ′ + 𝐿′0 ℎ′ + 𝐿′1 ℎ′ + 𝐿′2 ℎ′ + 𝐿′3 ℎ′𝑚𝑎𝑥 = ℎ′ + 𝐿′4 ℎ1 + 𝐿1,1 ℎ1 + 𝐿1,0 ℎ1 + 𝐿1,2 ℎ1 + 𝐿1,3 ℎ1 + 𝐿1,4 ℎ2 + 𝐿2,0 ℎ2 + 𝐿2,1 ℎ2 + 𝐿2,2 ℎ2 + 𝐿2,3 ℎ2 + 𝐿2,4 ℎ3 + 𝐿3,0 ℎ3 + 𝐿3,1 ℎ3 + 𝐿3,2 ℎ3 + 𝐿3,3 ℎ3 + 𝐿3,4 h’=h1 Figure 3.8: An example for Algorithm 2 which approximates the side-slopesof merged sections.iterations.As each δ in the regression tree, each ′ in the approximation method andeach iteration of the heuristic method returns a specific number of sections,comparison of these methods with a lot of numbers of sections is hard.Therefore, two stopping criteria are considered to return a specific number ofsections for each method (stopping criterion 1 is obtained from the heuristicmethod explained in Subsection 3.3.1).Stopping criterion 1: Relative cost error between two iterations of amethod ≤ 0.05 (the results which can satisfy this criterion are shown by thecyan color).Stopping criterion 2: Relative cost error between original ground andeach iteration of a method≤ 0.05. In addition, The root of mean squarederrors (RMSE) between the height of approximated ground and the originalground ≤ 0.25m (the results which can satisfy this criterion are shown bythe green color).The following tables present the methods performances on the groundsshown in Table 3.2 and in these tables, the number of sections is shown513.4. Results and Discussionby Section. MaxE and RMSE present the maximum absolute error androot mean squared error between the heights of the original and approxi-mated grounds. The relative cost error between two consecutive iterationsis indicated by RelCosti,i+1. The relative and absolute errors between thecost of an iteration and the original ground cost are shown by RelCostEand AbsCostE, respectively. Implementation time of the methods (in Mat-lab R2013b) is shown by T method and T Solve shows the solving time(optimizing the model by C++ code).The cost and the height of the original ground are respectively shown byCost and h. The height and the cost of the approximated ground at iterationi are respectively presented by h′ and Cost′i. The number of sections of theapproximated ground is smaller than the number of sections of the originalground. Therefore, the number of elements in h′ is smaller than h.In order to compute MaxE and RMSE (3.12), we need to have thesame number of elements for h and h′. For this case, assume xj′ (j′ ∈ N ′and N ′ is the number of sections of the approximated ground) is the numberof merged sections from the original ground to make the j′th section of theapproximated ground. Therefore, any section of the approximated ground isreplicated for xj′ times to have the same length for h and h′. Consequently,MaxE, RMSE, RelCosti,i+1, RelCostE and AbsCostE are defined asMaxE = max |h− h′|,RMSE =√1N(hj − h′j), j ∈ N,RelCosti,i+1 =|Cost′i+1 − Cost′i|Cost′i,RelCostE =|Cost− Cost′i|Cost,AbsCostE = |Cost− Cost′i|.(3.12)For stopping criterion 1, Total T ime is sum of T method and T Solvefrom the first iteration till the iteration that satisfies this criterion. Accord-ing to stopping criterion 1, the method that returns the smallest Section,Total T ime andRelCosti+1,i+2 is the winner. We also considerRelCosti+1,i+2since the approximation is good enough if bothRelCosti,i+1 andRelCosti+1,i+2are small.For stopping criterion 2, Total T ime is sum of T method and T Solvefrom the iteration that has RMSE ≤ 0.25 until the iteration that satisfiesthis criterion. Based on stopping criterion 2, the method that returns thesmallest Section and Total T ime is the winner.523.4. Results and DiscussionFor comparing the performances of the regression tree and the piecewiseconstant approximation method, two studies are done. In the first study,the methods are implemented as they are explained in Subsections 3.3.2 and3.3.3. In other words, the ground elevation is used as a criterion to mergesections. In the second study, the material volume is used instead of theground elevation as the criterion for merging sections.It should be noted that the heuristic method requires neither groundelevation nor material volumes and this method just picks uniform sections.Therefore, the heuristic results in both studies are the same.Study 1: Comparison based on ground elevationGround elevation is used as a criterion for merging sections and the per-formances of the heuristic method, the regression tree and the piecewiseconstant approximation method on Ground A (2,368 sections and the roadconstruction cost is $493,306) are presented in Tables 3.3, 3.4 and 3.5, re-spectively. These tables are summarized based on the two stopping criteriain Table 3.6.Table 3.3: The performance of the heuristic method on Ground A.Iteration Section MaxE RMSE RelCostE AbsCostE T_Method T_Solve1 37 3.46 1.11 0.20 0.30 149830 0.0 0.52 74 1.92 0.57 0.02 0.05 24238 0.5 1.03 148 1.16 0.28 0.01 0.02 11315 1.6 0.84 296 0.94 0.14 0.01 0.01 7249 2.4 1.25 592 0.82 0.06 0.01 0.01 3762 3.5 2.86 1184 0.68 0.03 0.00 0.00 1000 6.3 9.2The heuristic method𝐑𝐞𝐥𝐂𝐨𝐬𝐭𝐢,𝐢+𝟏 In Table 3.4, the relative cost error between δ equals to 0.0008 and0.0003 is small (RelCosti,i+1 = 0.05) but RelCosti,i+1 between δ equals to0.0003 and 0.0004 is not small (RelCosti,i+1 = 0.12). Therefore, consid-ering stopping criterion 1 is not necessarily satisfactory to obtain a goodapproximation since RelCosti,i+1 may become bigger than 0.05 in the nextiterations. In addition, the absolute cost error for this delta (0.0003) is huge.533.4. Results and DiscussionTable 3.4: The performance of the Regression tree on Ground A.Delta Section MaxE RMSE RelCostE AbsCostE T_method T_Solve0.1 3 29.65 12.87 0.39 2.76 1362194 0.0 0.14E-02 4 18.34 9.34 0.16 4.23 2086554 0.0 0.11E-02 6 16.03 6.67 0.51 5.08 2507834 0.0 0.35E-03 8 9.77 4.68 0.08 2.00 987854 0.0 0.42E-03 10 9.11 4.02 0.34 1.76 867594 0.0 0.48E-04 16 5.03 2.36 0.05 0.82 405703 0.0 0.63E-04 18 4.80 2.13 0.12 0.74 363373 0.0 0.51E-04 30 3.70 1.28 0.15 0.53 260887 0.1 0.64E-05 35 2.54 1.08 0.09 0.30 149966 0.0 0.62E-05 57 2.09 0.68 0.06 0.19 94012 0.1 0.76E-06 71 1.33 0.54 0.01 0.12 59974 0.1 0.52E-06 110 1.03 0.35 0.05 0.11 52876 0.0 0.69E-07 138 0.66 0.27 0.00 0.05 26039 0.0 1.23E-07 208 0.62 0.18 0.03 0.06 28095 0.1 1.01E-07 270 0.33 0.13 0.00 0.03 13114 0.1 1.65E-08 397 0.25 0.09 0.02 0.03 15291 0.06 1.822E-08 535 0.17 0.06 0.00 0.01 7309 0.1 3.37E-09 718 0.11 0.04 0.01 0.02 8102 0.1 3.83E-09 979 0.07 0.03 0.01 0.03 12706 0.1 5.21E-09 1288 0.04 0.02 0.02 0.02 7729 1.4 9.4The Regression Tree𝐑𝐞𝐥𝐂𝐨𝐬𝐭𝐢,𝐢+𝟏 Based on stopping criterion 1 in Table 3.6, the regression tree returnsthe smallest number of section. However, the RelCosti+1,i+2, RelCostEand RMSE of the regression tree is the worst. Consequently, there is nowinner according to stopping criterion 1 for Ground A. Based on stoppingcriterion 2 in Table 3.6, the number of sections of all methods are close toeach other but the Total T ime of the piecewise approximation method isthe biggest time. Therefore, the heuristic method and the regression treeare the winners for Ground A.The results for Ground B, C and D are presented in Tables 3.7, 3.8 and3.9, respectively.Based on stopping criterion 1, the heuristic method has the smallestRelCosti+1,i+2 and Total T ime for Ground B but returns the biggest num-ber of sections. For Ground C and D, the regression tree returns the smallestnumber of sections and Total T ime but largest RelCosti+1,i+2. Therefore,stopping criterion 1 is not good enough to find the best method for sectionpositioning problem.543.4. Results and DiscussionTable 3.5: The performance of the piecewise constant approximation methodon Ground A.Epsilon Section MaxE RMSE RelCostE AbsCostE T_method T_Solve3.1623 21 2.08 0.90 0.12 0.64 313255 1.7 12.3357 29 1.55 0.65 0.04 0.43 214204 1.7 01.7252 39 1.23 0.49 0.10 0.37 183334 1.5 11.2743 52 0.86 0.36 0.08 0.23 113097 1.4 00.9412 72 0.82 0.27 0.04 0.13 66533 1.2 10.6952 95 0.43 0.20 0.01 0.09 46664 1.2 10.5135 128 0.34 0.15 0.04 0.10 50860 1.2 10.3793 172 0.24 0.11 0.01 0.06 29256 1.1 10.2801 230 0.19 0.08 0.02 0.05 25590 1.0 20.2069 303 0.15 0.06 0.00 0.03 17189 1.0 20.1528 403 0.11 0.05 0.01 0.03 15973 1.0 20.1129 533 0.08 0.04 0.00 0.03 12537 1.0 30.0834 689 0.05 0.03 0.01 0.02 11165 1.0 40.0616 867 0.04 0.02 0.01 0.02 7673 1.0 60.0455 1101 0.03 0.02 0.01 0.01 3403 1.0 70.0336 1452 0.02 0.01 0.01 0.02 8222 1.0 120.0248 1786 0.01 0.01 0.00 0.01 4396 1.0 140.0183 2036 0.01 0.00 0.02 0.01 6637 1.0 190.0135 2237 0.01 0.00 0.00 0.00 975 1.0 230.0100 2284 0.01 0.00 0.00 0.00 610 1.0 24The Piecewise Constant Approximation Method𝐑𝐞𝐥𝐂𝐨𝐬𝐭𝐢,𝐢+𝟏 Table 3.6: Comparing methods on Ground A according to two stoppingcriteria.Stopping CriterionMethods Section RMSE RelCostE Total_TimeHeuristic 148 0.28 0.01 0.02 2.4Regresssion Tree 18 2.13 0.12 0.74 2.6Piecewise approximation 39 0.49 0.10 0.37 6.5Heuristic 296 0.14 0.01 0.01 3.5Regresssion Tree 270 0.13 0.02 0.03 2.8Piecewise approximation 230 0.08 0.00 0.05 9.0Ground A12𝑹𝒆𝒍𝑪𝒐𝒔𝒕𝒊+𝟏,𝒊+𝟐 553.4. Results and DiscussionTable 3.7: Comparing methods on Ground B according to two stoppingcriteria.Stopping CriterionMethods Section RMSE RelCostE Total_TimeHeuristic 118 0.54 0.01 0.01 3.0Regresssion Tree 9 2.89 0.01 0.25 1.1Piecewise approximation 33 0.62 0.04 0.10 3.5Heuristic 471 0.11 0.00 0.00 7.9Regresssion Tree 185 0.23 0.00 0.01 1.8Piecewise approximation 125 0.20 0.00 0.00 1.9Ground B12𝑹𝒆𝒍𝑪𝒐𝒔𝒕𝒊+𝟏,𝒊+𝟐 Table 3.8: Comparing methods on Ground C according to two stoppingcriteria.Stopping CriterionMethods Section RMSE RelCostE Total_TimeHeuristic 145 1.13 0.04 1.29 10Regresssion Tree 70 1.52 0.18 1.30 15Piecewise approximation 83 0.65 0.02 2.25 20Heuristic - - - - -Regresssion Tree - - - - -Piecewise approximation - - - - -Ground C12𝑹𝒆𝒍𝑪𝒐𝒔𝒕𝒊+𝟏,𝒊+𝟐 Table 3.9: Comparing methods on Ground D according to two stoppingcriteria.Stopping CriterionMethods Section RMSE RelCostE Total_TimeHeuristic 119 0.43 0.02 0.70 15Regresssion Tree 4 4.44 0.40 0.62 2Piecewise approximation 32 0.45 0.16 0.72 76Heuristic - - - - -Regresssion Tree - - - - -Piecewise approximation - - - - -Ground D12𝑹𝒆𝒍𝑪𝒐𝒔𝒕𝒊+𝟏,𝒊+𝟐 563.4. Results and DiscussionTable 3.7 confirms that stopping criterion 1 is not good enough to evalu-ate the methods because the regression tree and the piecewise approximationmethods return small number of sections but their ground approximationsare bad (large RMSE and RelCostE). As Table 3.7 shows, based on theStopping criterion 2, the regression tree and piecewise approximation meth-ods are winners for Ground B.Tables 3.8 and 3.9 highlight that stopping criterion 1 is not good enoughto evaluate the methods. In addition, no methods can satisfy stoppingcriterion 2, thus the rows are blank. Therefore, there is no winner based onstopping criterion 2 in these tables.As the cost approximation error should be small and cost is dependenton the material volume, the volumes of materials are used instead of groundelevation in the following study.Study 2: Material volumes instead of ground elevationIn this study, the effect of using material volumes instead of ground elevationfor the regression tree and the piecewise constant approximation method isstudied. The methods are compared and the summarized results based ontwo criteria are presented in the following Tables.Table 3.10: Comparing methods on Ground A based on the material volumesand according to two stopping criteria.Stopping CriterionMethods Section RMSE RelCostE Total_TimeHeuristic 148 0.28 0.01 0.02 2.4Regresssion Tree 213 0.22 0.00 0.00 3.3Piecewise approximation 577 0.25 0.00 0.00 28.3Heuristic 296 0.14 0.01 0.01 3.5Regresssion Tree 213 0.22 0.01 0.00 0.7Piecewise approximation 577 0.25 0.01 0.00 2.2Ground A12𝑹𝒆𝒍𝑪𝒐𝒔𝒕𝒊+𝟏,𝒊+𝟐 573.4. Results and DiscussionTable 3.11: Comparing methods on Ground B based on the material volumesand according to two stopping criteria.Stopping CriterionMethods Section RMSE RelCostE Total_TimeHeuristic 118 0.54 0.01 0.01 3.0Regresssion Tree 90 1.02 0.02 0.07 2.9Piecewise approximation 624 1.05 0.00 0.16 8.9Heuristic 471 0.11 0.00 0.00 7.9Regresssion Tree - - - - -Piecewise approximation 733 0.18 0.00 0.01 8.3Ground B12𝑹𝒆𝒍𝑪𝒐𝒔𝒕𝒊+𝟏,𝒊+𝟐 Table 3.12: Comparing methods on Ground C based on the material volumesand according to two stopping criteria.Stopping CriterionMethods Section RMSE RelCostE Total_TimeHeuristic 145 1.13 0.04 1.29 10Regresssion Tree 389 0.38 0.23 1.67 12Piecewise approximation 2090 0.04 0.21 1.90 80Heuristic - - - - -Regresssion Tree - - - - -Piecewise approximation - - - - -Ground C12𝑹𝒆𝒍𝑪𝒐𝒔𝒕𝒊+𝟏,𝒊+𝟐 Table 3.13: Comparing methods on Ground D based on the material volumesand according to two stopping criteria.Stopping CriterionMethods Section RMSE RelCostE Total_TimeHeuristic 119 0.43 0.02 0.70 15Regresssion Tree 96 1.17 0.39 0.67 10Piecewise approximation 382 0.14 0.02 0.72 399Heuristic - - - - -Regresssion Tree - - - - -Piecewise approximation - - - - -Ground D12𝑹𝒆𝒍𝑪𝒐𝒔𝒕𝒊+𝟏,𝒊+𝟐 In this study, stopping criterion 2 is not successful to evaluate meth-ods and the heuristic method is mostly the winner based on the stoppingcriterion 1.583.5. Summary of the section positioning methods3.5 Summary of the section positioning methodsThis Chapter presents heuristic method, regression tree and piecewiseconstant approximation for section positioning in road design model. Twostopping criteria are considered for these methods and the methods perfor-mances are compared in two studies.In the first study, the ground elevation is used in the regression tree andpiecewise constant approximation method and the material volumes are usedin the second study for these methods. The heuristic method results are thesame in both studies, as this method just picks uniform sections regardlessof considering ground elevation or volumes.The results show there is no specific method that is the best for allgrounds. Therefore, all methods should be implemented on a small part ofa real ground and the method which has the best performance should beimplemented on the whole of real ground.59Chapter 4ConclusionThis thesis is based on two research projects. In the first project (Chap-ter 2), an extensive survey on the sensitivity analysis methods is done whichhelps the practitioners decide the most appropriate SA method. In addition,the most appropriate methods are implemented on a road design model. Inthe second project (Chapter 3), three methods are compared to obtain atrade-off between reducing number of sections and accuracy.The contributions of this thesis are1. Sensitivity analysis (Chapter 2): Categorizing the most efficient sen-sitivity analysis methods, comparing sensitivity analysis methods ineach category, helping practitioners decide the most appropriate sen-sitivity analysis method and analyzing the sensitivity of a road designmodel.2. Section positioning (Chapter 3): proof of concept that has great poten-tial for reducing the number of variables considered and subsequentlyreducing the computation time. In this thesis, up to 90% reduction innumber of section was observed while maintaining acceptable accuracythat translate to 88% savings in computation time. This is a proof ofconcept supported by 4 use cases that show tremendous potential.The limitations of this thesis are:1. Only construction cost was considered in the road design model whilein practice, environmental, users, and other costs should be taken intoaccount.2. Only vertical alignment was considered but SA should also be appliedto horizontal alignment; similarly, section reduction was applied tovertical alignment but may also give huge savings on the horizontalalignment.3. Even with only building costs considered, several approximation as-sumption were made e.g. no details on what machine was used, wages,construction duration etc. were used to keep the model tractable.60Chapter 4. ConclusionFuture work based on Chapter 2 could consider obtaining safe ranges ofroad design model inputs such as cost parameters. The true cost parameterscannot be known until after construction, and even then it may be difficultto estimate the true cost parameters. Therefore, ranges for the unit costsshould be found such that the construction cost is not sensitive to these unitcosts ranges.Suppose UC is the actual unit cost and UC1 is the uncertain unit cost.For a given set of standards and constraints (assume constant), function Fareturns an alignment for a given set of unit costs. For a given alignment, thetotal earthwork construction cost (C) can be estimated by the cost functionFc.A = Fa(UC),C = Fc(A,UC),(4.1)where A and C are the actual alignment and construction cost, respectively.As the designers do not have the actual unit costs, they use the uncertainunit costs (UC1) and find an alignment (A1 = Fa(UC1)). The cost ofconstructing this alignment is C1T that can be calculated by estimating theactual unit costs and plugging them in the cost function C1T = Fc(A1, UC).The designers expect C1T and C to be close to each other. In otherwords, they expect C1T−CC to have a small value. Therefore, designing a costmodel that helps to find an insensitive construction cost is required.Future work based on Chapter 3 is comparing the section positioningmethods on a large number of grounds. In addition, the grounds should becategorized into flat, hilly, and etc. For each category of grounds, specificvalues for the methods parameters (δ and ′) could be defined.61Bibliography[AIGMA05] J. C. Ascough II, T. R. Green, L. Ma, and L. R. Ahjua. Keycriteria and selection of sensitivity analysis methods appliedto natural resource models. In Modsim 2005 InternationalCongress on Modeling and Simulation, pages 2463–2469, Mod-eling and Simulation Society of Australia and New Zealand,Melbourne, Australia, 2005. → pages 4, 5, 14, 15[Ale13] A. Alexanderian. On spectral methods for variance based sen-sitivity analysis. Probability Surveys, 10:51–68, 2013. → pages5[Alv09] D. A. Alvarez. Reduction of uncertainty using sensitivity analy-sis methods for infinite random sets of indexable type. Interna-tional journal of approximate reasoning, 50(5):750–762, 2009.→ pages 4[AON13] M. Ashraf, S. Oladyshkin, and W. Nowak. Geological storageof CO2: Application, feasibility and efficiency of global sensi-tivity analysis and risk assessment using the arbitrary polyno-mial chaos. International Journal of Greenhouse Gas Control,19:704–719, 2013. → pages 4[BB13] M. Baucells and E. Borgonovo. Invariant probabilistic sensitiv-ity analysis. Management Science, 59(11):2536–2549, 2013. →pages 24, 25[BBM03] F. Borrelli, A. Bemporad, and M. Morari. Geometric algorithmfor multiparametric linear programming. Journal of optimiza-tion theory and applications, 118(3):515–540, 2003. → pages37[BM08] A. Basudhar and S. Missoum. Adaptive explicit decision func-tions for probabilistic design and optimization using supportvector machines. Computers & Structures, 86(19):1904–1917,2008. → pages 562Bibliography[BO09] L. S. Bastos and A. O’Hagan. Diagnostics for Gaussian processemulators. Technometrics, 51(4):425–438, 2009. → pages 26[Bor07] E. Borgonovo. A new uncertainty importance measure. Reli-ability Engineering & System Safety, 92(6):771–784, 2007. →pages 24, 25[BP16] E. Borgonovo and E. Plischke. Sensitivity analysis: A reviewof recent advances. European Journal of Operational Research,248(3):869–887, 2016. → pages 4, 37[BTPM14] E. Borgonovo, S. Tarantola, E. Plischke, and M. D. Morris.Transformations and invariance in the sensitivity analysis ofcomputer experiments. Journal of the Royal Statistical Soci-ety: Series B (Statistical Methodology), 76(5):925–947, 2014.→ pages 24, 25[Can12] F. Cannavo´. Sensitivity analysis for volcanic source modelingquality assessment and model selection. Computers & Geo-sciences, 44:52–59, 2012. → pages 4[Can14] F. Cannavo´. GSAT: Global sensitivity analysis toolbox.http://www.mathworks.com/matlabcentral/fileexchange/40759-global-sensitivity-analysis-toolbox, 2013–2014.→ pages 30, 37[CCS07] F. Campolongo, J. Cariboni, and A. Saltelli. An effectivescreening design for sensitivity analysis of large models. En-vironmental modelling & software, 22(10):1509–1518, 2007. →pages 21[CDD13] J. Cao, F. Du, and Sh. Ding. Global sensitivity analysis fordynamic systems with stochastic input processes. ReliabilityEngineering & System Safety, 118:106–117, 2013. → pages 6,28, 39[CFS+73] R. I. Cukier, C. M. Fortuin, K. E. Shuler, A. G. Petschek, andJ. H. Schaibly. Study of the sensitivity of coupled reaction sys-tems to uncertainties in rate coefficients. I theory. The Journalof Chemical Physics, 59(8):3873–3878, 1973. → pages 9, 12[CGP+12] G. Chastaing, F. Gamboa, C. Prieur, et al. General-ized hoeffding-sobol decomposition for dependent variables-63Bibliographyapplication to sensitivity analysis. Electronic Journal of Statis-tics, 6:2420–2448, 2012. → pages 12[CHT00] M. H. Chun, S. J. Han, and N. I. Tak. An uncertainty im-portance measure using a distance metric for the change ina cumulative distribution function. Reliability Engineering &System Safety, 70(3):313–321, 2000. → pages 4, 23[CLS78] R. I. Cukier, H. B. Levine, and K. E. Shuler. Nonlinear sen-sitivity analysis of multiparameter model systems. Journal ofcomputational physics, 26(1):1–42, 1978. → pages 9, 12[CMW06] K. Campbell, M. D. McKay, and B. J. Williams. Sensitivityanalysis when model outputs are functions. Reliability Engi-neering & System Safety, 91(10):1468–1472, 2006. → pages 5,28[Con80] W. J. Conover. Practical nonparametric statistics. Wiley NewYork, 1980. → pages 9[CP02] F. H. Christopher and S. R. Patil. Identification and reviewof sensitivity analysis methods. Risk analysis, 22(3):553–578,2002. → pages 4, 5[DNM+03] B. J. Debusschere, H. N. Najm, A. Matta, O. M. Knio, R. G.Ghanem, and O. P. Le Matre. Protein labeling reactions inelectrochemical microchannel flow: Numerical simulation anduncertainty propagation. Physics of Fluids (1994-present),15(8):2238–2250, 2003. → pages 5[EM07] S. M. Easa and A. Mehmood. Establishing highway horizontalalignment to maximize design consistency. Canadian Journalof Civil Engineering, 34(9):1159–1168, 2007. → pages 1[Fil11] C. Filippi. Sensitivity analysis in linear programming. WileyEncyclopedia of Operations Research and Management Science,2011. → pages 37[FJM+01] L. Figueiredo, I. Jesus, J. A. T. Machado, J. Ferreira, andJ. L. M. De Carvalho. Towards the development of intelligenttransportation systems. In Intelligent Transportation Systems,volume 88, pages 1206–1211, 2001. → pages 164Bibliography[FK14] M. Farah and A. Kottas. Bayesian inference for sensitivityanalysis of computer simulators, with an application to radia-tive transfer models. Technometrics, 56(2):159–173, 2014. →pages 26[FP92] J. Fu¨lo¨p and M. Prill. On the minimax approximation in theclass of the univariate piecewise constant functions. Operationsresearch letters, 12(5):307–312, 1992. → pages 47[Gal88] F. Galton. Co-relations and their measurement, chiefly fromanthropometric data. Proceedings of the Royal Society of Lon-don, 45(273-279):135–145, 1888. → pages 8[GBA+15] P. Gilles, I. Bertrand, J. with contributions from S. D. VeigaAlexandre, J. Fruth, L. Gilquin, J. Guillaume, L. L. Gratiet,P. Lemaitre, B. Ramos, and T. Touati. sensitivity: SensitivityAnalysis, 2015. R package version 1.11. → pages 30[GI12] G. Glen and K. Isaacs. Estimating Sobol sensitivity indices us-ing correlations. Environmental Modelling & Software, 37:157–166, 2012. → pages 11, 12[GJKL13] F. Gamboa, A. Janon, Th. Klein, and A. Lagnoux. Sen-sitivity indices for multivariate outputs. Comptes RendusMathe´matique, 351(7):307–310, 2013. → pages 5, 27, 38[GMPS14] G. Gal, V. Makler-Pick, and N. Shachar. Dealing with uncer-tainty in ecosystem model scenarios: application of the single-model ensemble approach. Environmental Modelling & Soft-ware, 2014. → pages 3[Ham94] D. M. Hamby. A review of techniques for parameter sensitivityanalysis of environmental models. Environmental Monitoringand Assessment, 32(2):135–154, 1994. → pages 3, 4, 5[Ham95] D. M. Hamby. A comparison of sensitivity analysis techniques.Health Physics, 68(2):195–204, 1995. → pages 5[HAMM13] E. Hayati, E. Abdi, B. Majnounian, and M. Makhdom. Appli-cation of sensitivity analysis in forest road networks planningand assessment. Journal of Agricultural Science and Technol-ogy, 15(4):781–792, 2013. → pages 4065Bibliography[Her15] J. Herman. SALib: Sensitivity analysis library. http://jdherman.github.io/SALib/, 2013–2015. → pages 30[HHLR14] W. Hare, Sh. Hossain, Y. Lucet, and F. Rahman. Models andstrategies for efficiently determining an optimal vertical align-ment of roads. Computers & Operations Research, 44:161–173,2014. → pages 1, 40, 41, 43[HKL11] W. Hare, V. R. Koch, and Y. Lucet. Models and algorithmsto improve earthwork operations in road design using mixedinteger linear programming. European Journal of OperationalResearch, 215(2):470–480, 2011. → pages 1[HS96] T. Homma and A. Saltelli. Importance measures in global sen-sitivity analysis of nonlinear models. Reliability Engineering &System Safety, 52(1):1–17, 1996. → pages 11[IH90] T. Ishigami and T. Homma. An importance quantification tech-nique in uncertainty analysis for computer models. In Uncer-tainty Modeling and Analysis, 1990. Proceedings, First Inter-national Symposium on, pages 398–403. IEEE, 1990. → pages30[IL14] B. Iooss and P. Lemaˆıtre. A review on global sensitivity analysismethods. arXiv preprint arXiv:1404.2405, 2014. → pages 4, 5[Jac06] J. Jacques. SAinterface. http://eric.univ-lyon2.fr/~jjacques/soft.html, 2006. → pages 30, 31, 37[Jan99] M. J. W. Jansen. Analysis of variance designs for model out-put. Computer Physics Communications, 117(1):35–43, 1999.→ pages 11, 12[JKLN13] A. Janon, Th. Klein, A. Lagnoux, and C. Nodet, M.and Prieur.Asymptotic normality and efficiency of two Sobol index estima-tors. ESAIM: Probability and Statistics, 2013. → pages 10, 11[JSJ06] M. K. Jha, P. Schonfeld, and J. C. Jong. Intelligent road design,volume 19. WIT Press, 2006. → pages 1[JWH14] G. James, D. Witten, and T. Hastie. An introduction to sta-tistical learning: With applications in R., 2014. → pages 45,4666Bibliography[K+09] S. Kucherenko et al. Derivative based global sensitivity mea-sures and their link with global sensitivity indices. Mathemat-ics and Computers in Simulation, 79(10):3009–3017, 2009. →pages 21, 22[KK88] H. Konno and T. Kuno. Best piecewise constant approximationof a function of single variable. Operations research letters,7(4):205–210, 1988. → pages 45, 47[KL10] V. R. Koch and Y. Lucet. A note on: Spline technique for mod-eling roadway profile to minimize earthwork cost. Journal ofIndustrial and Management Optimization, 6(2):393–400, 2010.→ pages 34, 41[Koc10] Valentin Raphael Koch. Optimizing earthwork block removal inroad construction. PhD thesis, University of British Columbia,2010. → pages 44[Lev98] D. Levin. The approximation power of moving least-squares.Mathematics of Computation of the American MathematicalSociety, 67(224):1517–1531, 1998. → pages 5[LML+09] M. Lamboni, D. Makowski, S. Lehuger, B. Gabrielle, andH. Monod. Multivariate global sensitivity analysis for dynamiccrop models. Field Crops Research, 113(3):312–320, 2009. →pages 5, 28[LMM11] M. Lamboni, H. Monod, and D. Makowski. Multivariate sensi-tivity analysis to measure global contribution of input factorsin dynamic models. Reliability Engineering & System Safety,96(4):450–459, 2011. → pages 5, 28[LMM14] B. Lamoureux, N. Mechbal, and J. R. Masse´. A combined sen-sitivity analysis and kriging surrogate modeling for early vali-dation of health indicators. Reliability Engineering & SystemSafety, 130:12–26, 2014. → pages 4[LT09] L. Lilburne and S. Tarantola. Sensitivity analysis of spatialmodels. International Journal of Geographical Information Sci-ence, 23(2):151–168, 2009. → pages 11, 12[M+95] M. D. McKay et al. Evaluating prediction uncertainty. USNuclear Regulatory Commission, 1995. → pages 1567Bibliography[MCLH14] A. P. Melo, D. Co´stola, R. Lamberts, and J. L. M. Hensen.Development of surrogate models using artificial neural networkfor building shell energy labelling. Energy Policy, 69:457–466,2014. → pages 5[MMM08] M. D. Morris, L. M. Moore, and M. D. McKay. Using or-thogonal arrays in the sensitivity analysis of computer models.Technometrics, 50(2):205–215, 2008. → pages 15, 16[MNM06] H. Monod, C. Naud, and D. Makowski. Uncertainty and sen-sitivity analysis for crop models. D. Wallach, D. Makowskiand J. Jones, ed.: Working with Dynamic Crop Models, pages55–100, 2006. → pages 11[Mor91] M. D. Morris. Factorial sampling plans for preliminary compu-tational experiments. Technometrics, 33(2):pp. 161–174, 1991.→ pages 20[Mor96] A. A. Moreb. Linear programming model for finding optimalroadway grades that minimize earthwork cost. European Jour-nal of Operational Research, 93(1):148–154, 1996. → pages 34,41[MPT] MPT: The multi-parametric toolbox. http://control.ee.ethz.ch/~mpt/3/Main/HomePage. → pages 37[MS81] R. H. Mayer and R. M. Stark. Earthmoving logistics. Journalof the Construction Division, 107(2):297–312, 1981. → pages 1[MT12] Th. A. Mara and S. Tarantola. Variance-based sensitivity in-dices for models with dependent inputs. Reliability Engineering& System Safety, 107:115–121, 2012. → pages 7[MTS82] G. J. McRae, J. W. Tilden, and J. H. Seinfeld. Global sen-sitivity analysisa computational implementation of the fourieramplitude sensitivity test (fast). Computers & Chemical Engi-neering, 6(1):15–25, 1982. → pages 14[MU49] N. Metropolis and S. Ulam. The Monte Carlo method. Journalof the American statistical association, 44(247):335–341, 1949.→ pages 868Bibliography[OO04] J. E. Oakley and A. O’Hagan. Probabilistic sensitivity anal-ysis of complex models: a Bayesian approach. Journal of theRoyal Statistical Society: Series B (Statistical Methodology),66(3):751–769, 2004. → pages 4, 5, 26[PBS13] Elmar P., Emanuele B., and Curtis L. S. Global sensitivitymeasures from given data. European Journal of OperationalResearch, 226(3):536 – 550, 2013. → pages 25[PCS+96] S. W. Pacala, Ch. D. Canham, J. Saponara, J. A. Silander Jr,R. K. Kobe, and E. Ribbens. Forest models defined by fieldmeasurements: estimation, error analysis and dynamics. Eco-logical monographs, 66(1):1–43, 1996. → pages 5, 27[Pea95] K. Pearson. Note on regression and inheritance in the caseof two parents. Proceedings of the Royal Society of London,58:240–242, 1895. → pages 8[Pli12] E. Plischke. An adaptive correlation ratio method using thecumulative sum of the reordered output. Reliability Engineering& System Safety, 107:149–156, 2012. → pages 19[PPS09] L. Pichler, H. J. Pradlwarter, and G. I. Schue¨ller. A mode-basedmeta-model for the frequency response functions of uncertainstructural systems. Computers & Structures, 87(5):332–341,2009. → pages 5[SAA+10] Andrea Saltelli, Paola Annoni, Ivano Azzini, Francesca Cam-polongo, Marco Ratto, and Stefano Tarantola. Variance basedsensitivity analysis of model output. design and estimator forthe total sensitivity index. Computer Physics Communications,181(2):259–270, 2010. → pages 1, 11, 12[Sal02] A. Saltelli. Making best use of model evaluations to com-pute sensitivity indices. Computer Physics Communications,145(2):280–297, 2002. → pages 11, 12[SB98] A. Saltelli and R. Bolado. An alternative way to computefourier amplitude sensitivity test (fast). Computational Statis-tics & Data Analysis, 26(4):445–460, 1998. → pages 13[SC04] W. I. Sellers and R. H. Crompton. Using sensitivity analysisto validate the predictions of a biomechanical model of bite69Bibliographyforces. Annals of Anatomy-Anatomischer Anzeiger, 186(1):89–95, 2004. → pages 4[SCS+00] A. Saltelli, K. Chan, E. M. Scott, et al. Sensitivity analysis,volume 134. Wiley New York, 2000. → pages 3[SGBG14] N. Saint-Geours, J. S. Bailly, and Ch. Grelot, F.and Lavergne.Multi-scale spatial sensitivity analysis of a model for economicappraisal of flood risk management policies. EnvironmentalModelling & Software, 60:153–166, 2014. → pages 4[SH08] A. Saltelli and T. Homma. SimLab: Free development frame-work for sensitivity and uncertainty analysis. http://ipsc.jrc.ec.europa.eu/?id=756, 1999-2008. → pages 30[Sin93] J. Sinclair. Response to the PSACOIN level S exercise.PSACOIN level S intercomparison. Nuclear Energy Agency,OECD, 1993. → pages 17[SK11] H. Sulieman and I. Kucuk. Global derivative based sensitiv-ity method for parameter estimation. Journal of the FranklinInstitute, 348(7):1556–1573, 2011. → pages 5[SLL16] S. Sarafrazi, J. Loeppky, and Y. Lucet. A survey on the sen-sitivity analysis methods for understanding complex models.Under submission, 2016. → pages iv, 2[Sob01] I. M. Sobol. Global sensitivity indices for nonlinear mathemat-ical models and their Monte Carlo estimates. Mathematics andcomputers in simulation, 55(1-3):271–280, 2001. → pages 9, 11[SRA+08] A. Saltelli, M. Ratto, T. Andres, F. Campolongo, J. Cariboni,D. Gatelli, M. Saisana, and S. Tarantola. Global sensitivityanalysis: the primer. John Wiley & Sons, 2008. → pages 11[SRTC05] A. Saltelli, M. Ratto, S. Tarantola, and F. Campolongo.Sensitivity analysis for chemical models. Chemical reviews,105(7):2811–2828, 2005. → pages 11, 37[SRTC12] A. Saltelli, M. Ratto, S. Tarantola, and F. Campolongo. Update1 of: Sensitivity analysis for chemical models. Chemical reviews,112(5):PR1–PR21, 2012. → pages 11, 20, 3770Bibliography[STC99] A. Saltelli, S. Tarantola, and K. P. S. Chan. A quantitativemodel-independent method for global sensitivity analysis ofmodel output. Technometrics, 41(1):39–56, 1999. → pages9, 12, 14, 15[STCR04] A. Saltelli, S. Tarantola, F. Campolongo, and M. Ratto. Sensi-tivity analysis in practice: a guide to assessing scientific models.John Wiley & Sons, 2004. → pages 1, 4, 21[STG+07] I. M. Sobol, S. Tarantola, D. Gatelli, S. S. Kucherenko, andW. Mauntz. Estimating the approximation error when fixingunessential factors in global sensitivity analysis. Reliability En-gineering & System Safety, 92(7):957–960, 2007. → pages 11,12[Sud08] B. Sudret. Global sensitivity analysis using polynomialchaos expansions. Reliability Engineering & System Safety,93(7):964–979, 2008. → pages 5[SW06] M. Schonlau and W. J. Welch. Screening the input variables toa computer model via analysis of variance and visualization. InAngela Dean and Susan Lewis, editors, Screening, pages 308–327. Springer New York, 2006. → pages 26[TKBL+12] S. Tarantola, V. Kopustinskas, R. Bolado-Lavin, A. Kaliatka,E. Uspuras, and M. Vaisnoras. Sensitivity analysis using contri-bution to sample variance plot: Application to a water hammermodel. Reliability Engineering & System Safety, 99(0):62 – 73,2012. → pages 17[Wei00] S. Weinzierl. Introduction to Monte Carlo methods. arXivpreprint hep-ph/0006269, 2000. → pages 8[Wey38] H. Weyl. Mean motion. American Journal of Mathematics,60(4):889–896, 1938. → pages 13[WLHZ14] P. Wang, Zh. Lu, J. Hu, and Ch. Zhou. Sensitivity analysisof the variance contributions with respect to the distributionparameters by the kernel function. Computers & Mathematicswith Applications, 67(10):1756–1771, 2014. → pages 21, 22[WLS13] P. Wei, Zh. Lu, and J. Song. A new variance-based global sensi-tivity analysis technique. Computer Physics Communications,184(11):2540–2551, 2013. → pages 16, 17, 3171Bibliography[WLZZ15] J. Wu, Zh. Luo, N. Zhang, and Y. Zhang. A new intervaluncertain optimization method for structures using Chebyshevsurrogate models. Computers & Structures, 146:185–196, 2015.→ pages 572"@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "2016-11"@en ; edm:isShownAt "10.14288/1.0314327"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Interdisciplinary Studies"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "Attribution-NonCommercial-NoDerivatives 4.0 International"@* ; ns0:rightsURI "http://creativecommons.org/licenses/by-nc-nd/4.0/"@* ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Sensitivity analysis and section positioning for road design model"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/59212"@en .