UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Horizontal alignment optimization in road design Mondal, Sukanto 2014

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2014_september_mondal_sukanto.pdf [ 2.63MB ]
JSON: 24-1.0074351.json
JSON-LD: 24-1.0074351-ld.json
RDF/XML (Pretty): 24-1.0074351-rdf.xml
RDF/JSON: 24-1.0074351-rdf.json
Turtle: 24-1.0074351-turtle.txt
N-Triples: 24-1.0074351-rdf-ntriples.txt
Original Record: 24-1.0074351-source.json
Full Text

Full Text

Horizontal Alignment Optimization inRoad DesignbySukanto MondalB.Sc., Rajshahi University of Engineering & Technology, 2010A 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)July 2014c© Sukanto Mondal, 2014AbstractThe horizontal alignment optimization problem in road design is a com-plex problem. Usually, classic optimization techniques cannot be used toaddress the problem. A few studies investigated the problem mainly us-ing heuristics. Unfortunately, all of the previously studied heuristic basedmethods do not guarantee optimality. In this study, we develop a novel opti-mization model to solve the horizontal alignment optimization problem in aspecified corridor. The cost of a horizontal alignment is significantly affectedby the associated vertical alignment cost. So in order to formulate the costfunction of the model, we consider both the vertical alignment and earth-work allocation associated with a horizontal alignment. The representationof a horizontal alignment in our model satisfies all of the geometrical spec-ifications used by engineers. Our model is suitable for both backtrackingand non-backtracking horizontal alignments. Derivative-free optimizationalgorithms are used to solve the problem and guarantee the local optimal-ity of our solution. The numerical experiment results of a set of practicalproblems are reported.iiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . viiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Road design optimization . . . . . . . . . . . . . . . . . . . . 21.2.1 Earthwork optimization . . . . . . . . . . . . . . . . . 41.2.2 Vertical alignment optimization . . . . . . . . . . . . . 51.2.3 Horizontal alignment optimization . . . . . . . . . . . 51.3 Background and literature review . . . . . . . . . . . . . . . 71.3.1 Earthwork and vertical alignment optimization model 71.3.2 Horizontal alignment optimization model . . . . . . . 81.3.3 Three dimensional alignment optimization model . . . 101.4 Our research approach . . . . . . . . . . . . . . . . . . . . . . 111.5 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . 11Chapter 2: A basic approach to solve the horizontal align-ment optimization problem . . . . . . . . . . . . . . 132.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 142.3 Solution Approach . . . . . . . . . . . . . . . . . . . . . . . . 162.4 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . 18iiiTABLE OF CONTENTS2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19Chapter 3: Horizontal alignment optimization model . . . . . 203.1 Geometric representation of horizontal alignment . . . . . . . 203.2 Model description . . . . . . . . . . . . . . . . . . . . . . . . . 243.2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 243.2.2 The optimization model . . . . . . . . . . . . . . . . . 273.3 Model Summary . . . . . . . . . . . . . . . . . . . . . . . . . 40Chapter 4: Numerical results . . . . . . . . . . . . . . . . . . . 414.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . 414.2 The NOMAD and HOPSPACK solvers . . . . . . . . . . . . . 424.3 Results for the test problems . . . . . . . . . . . . . . . . . . 424.4 Summary of the result . . . . . . . . . . . . . . . . . . . . . . 49Chapter 5: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 505.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.2 Recommendations for future research . . . . . . . . . . . . . . 51Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Appendix A: Tables . . . . . . . . . . . . . . . . . . . . . . . . . . 60A.1 Results for basic model . . . . . . . . . . . . . . . . . . . . . 60A.2 Optimized alignments of the test problems . . . . . . . . . . . 62Appendix B: Figures . . . . . . . . . . . . . . . . . . . . . . . . . . 69ivList of TablesTable 1.1 Classification of the construction costs. . . . . . . . . . 4Table 4.1 Specifications of the test problems . . . . . . . . . . . 41Table 4.2 Cost improvement, no. of black-box evaluations andwall-clock time required to solve the test problems us-ing the NOMAD solver. . . . . . . . . . . . . . . . . . 43Table 4.3 Comparison of optimum objective function values ob-tained by the HOPSPACK and NOMAD solvers tosolve the test problems. . . . . . . . . . . . . . . . . . 46Table 4.4 Overall comparison of the HOPSPACK solver and theNOMAD solver with the optimum objective functionvalues. . . . . . . . . . . . . . . . . . . . . . . . . . . . 47Table 4.5 Comparison of the no. of black-box evaluations re-quired for the HOPSPACK and NOMAD solvers tosolve the test problems. . . . . . . . . . . . . . . . . . 48Table A.1 Computational Experience (Hart Rd Small.csv) . . . . 60Table A.2 Computational Experience (Diamond Road align-1.csv) 61Table A.3 Computational Experience (Diamond Road align-2.csv) 61Table A.4 Computational Experience (bluff road.csv) . . . . . . . 62Table A.5 Computational Experience (spur 3 demo.csv) . . . . . 62Table A.6 The optimal alignments of the Road A obtained bythe NOMAD and HOPSPACK solvers. . . . . . . . . . 63Table A.7 The optimal alignments of the Road B obtained by theNOMAD and HOPSPACK solvers. . . . . . . . . . . . 64Table A.8 The optimal alignments of the Road C obtained by theNOMAD and HOPSPACK solvers. . . . . . . . . . . . 65Table A.9 The optimal alignments of the Road D obtained bythe NOMAD and HOPSPACK solvers. . . . . . . . . . 66Table A.10 The optimal alignments of the Road E obtained by theNOMAD and HOPSPACK solvers. . . . . . . . . . . . 68vList of FiguresFigure 1.1 A three dimensional alignment (blue curve) showingits projection onto the XY -plane. The projected redcurve is the horizontal alignment. . . . . . . . . . . . 3Figure 1.2 Example of cut and fill in road construction. . . . . . 5Figure 1.3 Two potential vertical alignments of a fixed horizontalalignment. . . . . . . . . . . . . . . . . . . . . . . . . 6Figure 1.4 Some potential horizontal alignments in a specifiedcorridor. . . . . . . . . . . . . . . . . . . . . . . . . . 6Figure 2.1 Corridor of a horizontal alignment. Base data pointsare in red, offset data points are in black. Points cir-cled in green constitute an example of a station. Theorange and purple curves are two potential horizontalalignments in the corridor. . . . . . . . . . . . . . . . 14Figure 2.2 Three dimensional alignment. . . . . . . . . . . . . . 15Figure 2.3 Blackbox optimization in horizontal alignment opti-mization problem. . . . . . . . . . . . . . . . . . . . . 16Figure 2.4 Flowchart of the solution approach. . . . . . . . . . . 17Figure 2.5 Required time with respect to number of stations forsolved problem only. . . . . . . . . . . . . . . . . . . . 18Figure 2.6 Growth of no. of function calls with respect to num-ber of stations. . . . . . . . . . . . . . . . . . . . . . . 19Figure 3.1 Geometric representation of horizontal alignment. Thealignment displayed is represented as ((S, 0), (P1, r1),(P2, r2), (P2, r2), (E, 0)). . . . . . . . . . . . . . . . . 21Figure 3.2 Geometric specifications of a circular curve. . . . . . . 21Figure 3.3 Road segment representation in a specified corridor. . 26viLIST OF FIGURESFigure 3.4 Horizontal alignment in a specified corridor. The redcurve is an example horizontal alignment. The bluestars are the intersection points (IP) and the dottedblue rectangular boxes are feasible region (for mov-ing) associated with the intersection points. . . . . . . 26Figure 3.5 Piece-wise linear representation of horizontal align-ment segment considering all of the cross-section lines. 28Figure 3.6 An example road of four segments showing the asso-ciated variables of the optimization model. The greencross-section lines separate the road segments. Thestarting point and the end point of the alignment are(px1,1 , py1,1) and (px4,3 , py4,3), respectively, which arefixed. . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Figure 3.7 A segment of a road showing an associated horizontalalignment. . . . . . . . . . . . . . . . . . . . . . . . . 31Figure 3.8 An example of the quadrants issue in generation of acircular arc. . . . . . . . . . . . . . . . . . . . . . . . 34Figure 3.9 Discontinuity in a horizontal alignment. . . . . . . . . 38Figure 4.1 A non-backtracking alignment (the test problem as-sociated with Road A) showing the initial alignmentand the optimized alignments obtained by the NO-MAD and HOPSPACK solvers. . . . . . . . . . . . . 44Figure 4.2 A backtracking alignment (the test problem associ-ated with Road D) showing the initial alignment andthe optimized alignments obtained by the NOMADand HOPSPACK solvers. . . . . . . . . . . . . . . . . 45Figure B.1 Optimum alignments of the Road B obtained by theNOMAD solver and the HOPSPACK solver. . . . . . 69Figure B.2 Optimum alignments of the Road C obtained by theNOMAD solver and the HOPSPACK solver. . . . . . 70Figure B.3 Optimum alignments of the Road E obtained by theNOMAD solver and the HOPSPACK solver. . . . . . 71viiAcknowledgementsFirst and foremost, I would like to thank my supervisors, Dr. YvesLucet and Dr. Solomon Tesfamariam, for their continuous help and en-couragement. This thesis would not have become a reality without theirguidance and advice. More importantly, thank you to my supervisors forallowing me to knock on their door at any time.I would like to thank Dr. Warren Hare, who actively advised me duringmy research. His insightful comments on my research work helped me todevelop better ideas.A big thank you goes out to our industrial partner, Softree Technical Sys-tems Inc., for providing engineering details and practical datasets. It mustbe mentioned, in the weekly meetings, we had many productive discussionswith David Mills, Craig Speirs, and Alexis Guigue on different engineeringaspects of the problem. More specifically, during the development of theoptimization model, their valuable comments helped me a lot to build abetter model.I would also like to thank my colleagues from different parts of the world,affiliated with the Center for Optimization and Convex Analysis and Non-smooth Analysis, for our off topics discussions to know their diverse nativecultures and lifestyles. My dear colleagues, I really enjoyed your compan-ionship.This research is partially funded by a Collaborative Research and De-velopment (CRD) Grants from the Natural Sciences and Engineering Re-search Council (NSERC) sponsored by Softree Technical Systems Inc. Theresearch was performed in the Computer-Aided Convex Analysis (CA2) lab-oratory funded by a Leaders Opportunity Fund (LOF) from the CanadianFoundation for Innovation (CFI) and by a British Columbia Knowledge De-velopment Fund (BCKDF).viiiDedicationDedicated to underprivileged talents of the world.ixChapter 1IntroductionIn this chapter, we briefly describe the background of the road designoptimization research and our motivation to solve the horizontal alignmentoptimization problem.1.1 MotivationSince the early days of human civilization, the transportation system isconsidered an integral part of sustainable socioeconomic development. Thegradual development of human civilization has led us to invent differentmodes of transportation, such as land transportation, sea transportation,and air transportation. The invention of the wheel revolutionized the landtransportation system and accelerated the economic development manyfold.As of today, the transportation system is continuously contributing to oureconomy significantly. For example, the transportation sector of Canadacontributed about 4.2% of Canada’s gross domestic product (GDP) in 2005[DAAMP06]. In particular, more than one third (about 35%) of the GDPgenerated by the transportation sector in 2005 came from the truck trans-portation industry [DAAMP06]. The truck transportation system uses atotal of 1,042,300 km of roads in Canada.The alignment of a road is the route connecting two given end-points.An alignment consists of the vertical and horizontal alignments. Intuitively,a good alignment is one which minimizes the construction costs satisfyingthe design constraints. In the traditional road design process, engineers usetheir professional judgment to determine several selected candidate align-ments and then manually try to find the best one. In fact, a large number ofalternative alignments exist that should be considered in the design process.In the conventional design process, finding the best alignment requires repet-itive manual iterations. So it is almost impossible for engineers to considerall of the possible alternative alignments. Hence, engineers cannot ensurethat the chosen alignment is (even locally) optimal.In order to overcome the difficulties in the road design process, it is im-perative to develop a computer-aided process to find the optimal alignment.11.2. Road design optimizationIn the literature, many studies proposed computerized models to find theoptimal horizontal alignment. Unfortunately, all of the models have somedrawbacks that prevent them to be used effectively in practice (for furtherdiscussion see Section 1.3.2). In our research, we solve the horizontal align-ment optimization problem and provide a practical model that guarantees(local) optimality. Our approach is validated by computing several real-world alignments.1.2 Road design optimizationRoad design optimization is the problem of finding a curve connect-ing two given end-points that minimizes the cost while satisfying all of thedesired design specifications. The problem is usually divided into three in-terrelated sub-problems, namely, horizontal alignment optimization, verticalalignment optimization, and earthwork optimization.In the three dimensional space, a curve can be projected on the horizontalplane (i.e., XY -plane). In road design literature, the curve is called thealignment, and the horizontal projection is called the horizontal alignment.In Figure 1.1, for a three dimensional alignment, the associated horizontalalignment is depicted.Along the horizontal alignment shown in Figure 1.1, we can measure thedistance from the starting point to the end point. Corresponding to anymeasured distance (using the x-values and the y-values of a three dimen-sional alignment), we have a z-value (ground elevation). If we draw thez-values with respect to the distance from the starting point in two dimen-sional space, then the resulting curve is called the vertical alignment.Finding the optimal alignment connecting the two end-points is hardbecause of the complex cost structure associated with an alignment and therequirement for satisfying design constraints [JSJ06]. Moreover, the con-tinuous search space of the problem gives an infinite number of alternativealignments. Since the terrain might have an irregular surface, a small changein an alignment may result in a significant change in the total cost.In order to find a good alignment, an engineer considers five major costs[JSJ06] as follows– planning and administrative cost,– construction cost,– maintenance cost,21.2. Road design optimizationFigure 1.1: A three dimensional alignment (blue curve) showing its projec-tion onto theXY -plane. The projected red curve is the horizontal alignment.– user cost, and– social and environment cost.Planning and administrative costs are not considered in the alignmentoptimization because these costs are insensitive to alignment alternatives[JSJ06]. In the study of Chew et al. [CGF89], construction costs are clas-sified into six categories. Table 1.1 lists the cost components of the con-struction costs and the associate approximate contributions toward the totalconstruction cost.The percentage of each cost component in the total construction cost isnot fixed [JSJ06]. Depending on the road location, it could be significantlydifferent. For example, the land acquisition cost might be higher in urbanareas, whereas in mountainous areas, the earthwork cost is substantiallyhigher than other costs.Maintenance costs have many classifications (at least eight) such as road-way surface, bridges, tunnels, roadside features, drainage, shoulders and ap-proaches maintenance, snow and ice control, and traffic control devices. Thenet maintenance cost over 30 years is about 5% of the total construction cost[OEC73].User costs (vehicle operating costs) consist of the cost of vehicle main-tenance, the value of travel time and the cost of traffic accidents. The netuser cost over 30 years varies approximately from 300% to 1000% of thetotal construction cost [OEC73].31.2. Road design optimizationTable 1.1: Classification of the construction costs.Cost components Contributions ( %)Land 5%Miscellaneous items 10 %Drainage 10 %Bridges 20 %Earthwork 25%Pavement 30%Social and environment costs are the negative impacts of the road on theenvironmental and social features of a particular region. In some extremecases, environmental and social issues might be very critical and even dom-inates other cost. In practice, social and environment costs are very hard toquantify. Typically, social and environment costs are carefully considered inthe planning stage when the preliminary corridor is selected.However, among the five major cost components of the total cost, ina selected corridor, constructions costs form an important component ofthe total cost function. In particular, construction costs (excluding landacquisition costs), mainly consist of excavation costs, embankment costs, andhauling costs for the construction materials. In our research, we minimizethe total excavation costs, embankment costs, and hauling costs satisfying alldesign constraints for the road. Note that the design constraints contributeto the user costs and the maintenance costs [BDE10]. For instance, a longand gentle vertical alignment provides a great sight distance which minimizesroad accidents.In a traditional engineering approach, finding a good alignment is arepetitive and complex process. It involves a series of phases, starting fromfeasibility studies followed by planning, then narrowing down to the selectionof several possible corridors, and finally focusing on the details of an align-ment including earthwork minimization, and horizontal and vertical designconstraints.1.2.1 Earthwork optimizationEarthwork optimization is the problem of minimizing the total excava-tion cost, embankment cost, and hauling cost for a fixed alignment. In roadconstruction, earthwork is the major task which involves excavation, em-bankment and hauling of large quantities of earth materials. The cut and41.2. Road design optimizationCut area Fill area Ground profile Road profile Figure 1.2: Example of cut and fill in road construction.fill areas are determined by the intersection of the ground profile and theroad profile (see Figure 1.2). If the ground profile is below the road profile,then more material is needed to fill. On the other hand, if the ground pro-file is above the road profile, then additional material has to be cut. Theexcavation and embankment costs are incurred in the cut and fill areas re-spectively. The hauling cost is the cost associated with moving the materialfrom the cut areas to fill areas. The earthwork allocation cost is defined asthe combination of the excavation, embankment, and hauling costs.1.2.2 Vertical alignment optimizationA large number of vertical alignments can be built for a fixed horizontalalignment (see Figure 1.3). For each vertical alignment, the earthwork al-location cost (which is the minimum cost corresponding to that fixed align-ment) can be calculated by solving the earthwork optimization problem.Thus the vertical alignment optimization problem is to find the verticalalignment which has the minimum earthwork allocation cost satisfying thevertical alignment design constraints for a fixed horizontal alignment. Themajor design criteria for a vertical alignment are the allowable grades and therate of curvature [AAS04]. The maximum and minimum allowable gradesdepend on the design speed (i.e., maximum speed limit) and the trafficcomposition. The rate of curvature is the length of the vertical curve perpercent algebraic difference between the grade at the two end-points of thecurve [AAS04].1.2.3 Horizontal alignment optimizationIn a specified corridor, a large number of horizontal alignments can bebuilt (see Figure 1.4). As we described earlier, in the vertical alignment51.2. Road design optimizationElevation XY plane  Ground elevation  Vertical alignment  Figure 1.3: Two potential vertical alignments of a fixed horizontal alignment.optimization process the horizontal alignment is fixed. Thus, for each fea-sible horizontal alignment, the vertical alignment optimization problem canbe solved to get the optimal vertical alignment. The vertical alignmentoptimization yields the minimum earthwork allocation cost satisfying thevertical alignment design constraints. From the previous two assertions,immediately it follows that each horizontal alignment has a cost (in partic-ular, the minimum earthwork allocation cost) which is computed by solvingthe corresponding vertical alignment optimization problem. Therefore, thehorizontal alignment optimization problem can be defined as the problemof finding the horizontal alignment which has the minimum earthwork al-location cost satisfying the horizontal alignment design constraints and theassociated vertical alignment design constraints.Y x  Corridor Horizontal alignments  Figure 1.4: Some potential horizontal alignments in a specified corridor.A horizontal alignment consists of some tangential line segments followedby some circular arcs. The most important design constraint of the hori-zontal alignment is the minimum radius of curvature of the circular arcs for61.3. Background and literature reviewthe safety requirement.1.3 Background and literature reviewComputer-aided road design optimization started during the 1960’s and1970’s. Due to the limited computational power, it was hard to solve op-timization problems precisely. The advent of the modern computer andGIS technology has helped us to solve the problem accurately. The roadconstruction cost can be minimized substantially by solving the mathemat-ical models using modern computer programs. Many optimization modelshave been developed to address the problem from different perspectives.Although existing models work well in certain aspects, they still have somedrawbacks that prevent them to be used in practice.1.3.1 Earthwork and vertical alignment optimization modelMany different approaches have been considered to model the verticalalignment optimization problem. Numerical search [Hay70, Pea73, Rob73,GCF88], and dynamic programming [Hua73, Mur73, Fwa89, GLA05] arenotably used to solve the problem.Numerical search models are the earliest techniques to deal with the ver-tical alignment optimization problem. Usually, a resulting numerical searchmodel of the vertical optimization problem becomes a non-linear non-convexoptimization problem which is hard to solve [JSJ06, page 28, section 2.5.4].The dynamic programming approach yields a piece-wise linear alignmentrather than a smooth alignment. Rahman [Rah12, page 9, section 1.2.3]noted that the dynamic programming approach is not suitable to solve thevertical alignment optimization problem.In traditional engineering, a mass haul diagram is used to minimize theearthwork allocation. The mass haul diagram cannot be used in practicalsituations [MS81]. The mass diagram has mainly the following limitations, itcannot handle nonlinear hauling costs and the costs associated with borrowand waste pits. To overcome the previous limitations, a linear programmingmodel was developed by Mayer and Stark [MS81]. Later, the earthworkallocation and the vertical road profile are modelled together by the Trans-portation and Road Research Laboratory in the United Kingdom and themodel was further modified by the Ontario Ministry of Transportation andCommunications. This model is the first attempt to integrate the earthworkand vertical alignment optimization together. Unfortunately, the model doesnot guarantee optimality.71.3. Background and literature reviewEasa [Eas88] developed a linear programming model considering theearthwork allocation and the vertical alignment. His approach works inthree steps: parameterizing all technically feasible vertical alignments, cal-culating the cut and fill requirements for each vertical alignment, and thenusing linear programming to optimize the earthwork allocation. The modelgives the global optimum through an exhaustive enumeration of possiblevertical profile.Moreb [Mor96] developed the earthwork allocation and vertical road pro-file in a single linear programming model. Both Easa’s model and Moreb’smodel output a piecewise linear vertical curve. But a smooth alignment isdesired. In order to remove the sharp connectivity of the piecewise linearvertical alignment, the optimum result might be tempered. Engineers usequadratic spline for the vertical alignment. Moreb and Aljohani [MA04]modified the model developed in [Mor96] considering the vertical alignmentas a quadratic spline. Moreb [Mor09] further improved the previous modelby adding some additional constraints to ensure the smoothness with anydegree of polynomial spline. However, Koch and Lucet [KL10] proved thatthe linearity of the model can only be maintained up to quadratic splines.Recently, Hare, Koch, and Lucet [HKL11] developed a mixed integer lin-ear programming model for the earthwork optimization considering blocks.Rahman [Rah12] extended several models: [Mor09], [KL10], [HKL11] (un-published manuscript [HHLM11] is also mentioned in [Rah12] but I couldnot access it) to formulate the vertical alignment optimization problem as amixed integer linear program model. Hare et al. [HHLR14] further improvedthe model to reduce the solution time. In our research, we use the modeldeveloped in [HHLR14] as the objective function to solve the horizontalalignment optimization problem.1.3.2 Horizontal alignment optimization modelThe horizontal alignment optimization problem is more complicated thanthe vertical alignment optimization problem [JSJ06]. The main reasons arethat the horizontal alignment requires more data, and the cost of the hori-zontal alignment is dependent on the vertical alignment cost, political, so-cioeconomic, and environmental issues. In the literature, mainly three basicapproaches have been studied: calculus of variation, network optimization,and dynamic programming.Calculus of variation tries to find a curve connecting two end points inspace which minimizes the integral of a function [Wan95]. The nature of thealignment optimization problem allows us to use the concept of calculus of81.3. Background and literature reviewvariation to find the optimal alignment. Howard et al. [HBS68] used the ideaof calculus of variation to develop the Optimum Curvature Principle (OCP),which specifies the optimal vertical and horizontal curvatures at any point.In order to apply the OCP, Shaw and Howard [SH81] proposed two numericalintegration methods, namely, the arc of circle algorithm and the intrinsicequation procedure. The OCP was applied by Shaw and Howard to find theoptimal alignment of an expressway in South Florida [SH82]. Two majorrequirements to use the OCP are the followings: first, the cost function hasto be continuous and second, the cost function has to be twice continuouslydifferentiable. In practice, the cost function might not be continuous [JSJ06,page 8, section 2.4.1]. Although the OCP guarantees global optimality, itrequires some assumptions that make it impractical.Another well-known approach to model the horizontal alignment opti-mization problem is network optimization. In the network optimizationapproach, a network is designed to represent a region through which a roadcould pass. The region is divided into small cells to make a grid. Each cell inthe grid represents a node of the network. The nodes are connected throughthe arcs. Each arc in the network is assigned a weight considering the costassociated with the two connecting cells. An alignment is defined as a setof connecting arcs from the starting node to the ending node.In the early 1970’s, the idea of network optimization was used by Turnerand Miles [TM71] to model the route selection problem. This model [TM71]considered the square grid to define the network. Considering all of the costfactors, for each cell in the grid, a smooth surface was constructed. They[TM71] developed the Generalized Computer Aid Route Selection (GCARS)system to generate a set of ranked alignments. Turner [Tur78] further im-proved the GCARS system by incorporating the environmental impacts asa cost factor.Athanassoulis and Calogero [AC73] formulated the route selection prob-lem as a modified transportation problem. Note that both Turner’s andAthanassoulis’s models did not consider the vertical profile. In practice, itis highly expected to incorporate the vertical alignment cost in the horizontalalignment optimization process.Parker [Par77] and Trietsch [Tri87b, Tri87a] developed the two stages ap-proach considering the vertical profile and used network optimization to findthe optimal alignment. While Parker studied only the square search grid,Trietsch studied four different types of search grids: rectangular, square,ellipse, and honeycomb. However, the resulting horizontal alignments ofthe models ([Par77, Tri87b, Tri87a]) are piece-wise linear curves which areunrealistic.91.3. Background and literature reviewA basic shortcoming of the network optimization models is that theoptimal alignment is a piecewise linear trajectory. In practice, a nonsmoothalignment is to be avoided for safety reasons. Moreover, in order to get amore precise alignment, more nodes are needed which increases the problemsize and eventually the problem becomes hard to solve in a reasonable time.A few studies [OEC73, Hog73, NEW76] applied the dynamic program-ming approach to optimize the alignment. Similar to the network opti-mization approach, the dynamic programming approach yields a nonsmoothalignment. Moreover, in the dynamic programming approach, the backwardbending feature of the roads (backtracking road) introduces difficulties tohandle the alignment [Nic73, page 123, Chapter 5], [JSJ06, page 21, Section2.4.3], [Par77].Jong et al. [Jon98, JJS00] developed a horizontal alignment optimizationmodel which was solved by a genetic algorithm. The horizontal alignmentsrepresented in [Jon98, JJS00] are very different from a practical alignment[LTL09].Lee et al. [LTL09] presented a heuristic based method to optimize thehorizontal alignment that works in two stages. In the first stage, the heuris-tic tries to approximate a piecewise linear alignment and then in the secondstage, it refines the solution to make the previously generated piecewiselinear alignment compatible to a real road alignment. The solution align-ment of the model ([LTL09]) yields a practical alignment. Since a heuristicalgorithm was used to solve the model, optimality is not guaranteed.1.3.3 Three dimensional alignment optimization modelIn three dimensional alignment optimization, the vertical and horizon-tal alignments are optimized simultaneously. Modeling three dimensionalproblem is a complex problem [JSJ06] and most of the studies use heuristicbased algorithms.Chew et al. [CGF89] developed a model to solve the three dimensionalalignment using the concept of optimal control theory. Chew’s model is thefirst model that yields a smooth three dimensional alignment. The objectivefunction of Chew’s model involves integrals which are hard to compute.Tat and Tao [TT03] proposed a three dimensional alignment optimiza-tion model and used genetic algorithm to solve it. This model [TT03] consid-ers all of the major constraints of the road design. Akay [Aka06] developeda model for three dimensional alignment optimization for forest roads. Asimulated annealing algorithm was used to solve the model. A tabu searchmethod was presented by [Aru05] for optimizing the three dimensional align-101.4. Our research approachment of forest roads.A criteria-based decision support system for three dimensional alignmentoptimization was developed by Jha [Jha03] considering the environmentalcosts. Jong et al. [JS03] presented an evolutionary model for optimizing thevertical and horizontal alignment simultaneously. The previous two models[Jha03, JS03] were further improved in [JK06] by considering accessibility,proximity, and land-use changes in the road alignment planning process.Recently, Cheng and Lee [CL06] also proposed a heuristic based modelfor three dimensional alignment optimization. The heuristic solves the mod-els in three steps: first, it generates a good general horizontal alignment byadding, deleting, or moving the intersection points one by one, then it deter-mines an improved horizontal alignment by adjusting the intersection pointsbased on the previously generated horizontal alignment, and finally, it findsa better three dimensional alignment by tuning the vertical alignment cor-responding to the previously obtained horizontal alignment.All of the above mentioned three dimensional alignment optimizationmodels excluding the model in [CGF89] use a heuristic based algorithmwhich does not guarantee optimality. Unfortunately, the heuristic basedalgorithms do not ensure any mathematical proof of convergence.1.4 Our research approachIn this research, we formulate the horizontal alignment optimizationproblem as a bi-level optimization problem. Since the horizontal alignmentoptimization problem is interrelated to the vertical alignment optimizationproblem, in the inner level, the optimization model solves a vertical align-ment optimization problem corresponding to a given horizontal alignment(which comes from the outer level). The outer level of the problem opti-mizes the horizontal alignment. An alignment in our model considers allof the geometric specifications used by engineers. We used two derivativefree optimization algorithms to solve the problem. Our approach requiresan initial alignment to start a derivative free optimization algorithm. Theresulting solution alignment of our model is locally optimum.1.5 Organization of the ThesisThe rest of the thesis is organized as follows. In Chapter 2, we describea basic formulation of the horizontal alignment optimization problem. Wealso discuss the solution approach to solve the problem. Some numerical111.5. Organization of the Thesisexperiment results are reported for the basic model. It is shown that, for aroad of reasonable length, the basic model cannot be solved in a reasonabletime.In Chapter 3, we develop a model using the concept of the basic modeldeveloped in Chapter 2. This model considers all of the geometric spec-ifications used by engineers in practice. The resulting model is a bi-leveloptimization problem, in which the vertical alignment optimization prob-lem is considered as an inner problem.In Chapter 4, we report the numerical results obtained by solving themodel developed in Chapter 3. The model was solved by two derivative-freeoptimization solvers. The performance of the two solvers are reported. Fi-nally, in Chapter 5 we summarize the contribution of the thesis and highlightsome future works.12Chapter 2A basic approach to solvethe horizontal alignmentoptimization problemIn this chapter, we describe a basic optimization problem formulationfor the horizontal alignment optimization. We report numerical experimentsthat lead to the improved model described in Chapter 3.2.1 TerminologyHorizontal alignment optimization consists of finding an optimal curvewithin a designated corridor. Each corridor has a baseline, which defines thehorizontal and vertical alignment. There are two given end-points within aspecified corridor. The curve connecting the two end-points is the baselineof the corridor. The ground profile data is given for some discrete pointswithin the corridor, which are called data points.There are two types of data points, namely, base data points and offsetdata points. The base data points are the points along the baseline, i.e., theengineer’s original horizontal alignment. The offset data points represent thehorizontal displacement from the base data points. The base data points areselected a few units apart between the two end-points along the baseline.Each of the base data points has some associated offset data points in boththe left and the right directions. The red points and the black points inFigure 2.1 are the base data points and offset data points, respectively.The baseline of a corridor is a piece-wise linear curve connecting thebase data points. A base data point together with the associated offset datapoints is defined as a station.132.2. Problem Formulation1  Base  Base -  offset  Base + offset  - 2  - 1   0   1   2  Figure 2.1: Corridor of a horizontal alignment. Base data points are in red,offset data points are in black. Points circled in green constitute an exampleof a station. The orange and purple curves are two potential horizontalalignments in the corridor.2.2 Problem FormulationEach data point within the corridor, either a base data point or an off-set data point, has some associated ground profile data. Therefore, for thevertical road profile, we can move vertically up and down for each hori-zontal offset data point. Altogether a three dimensional alignment datais visualized as shown in Figure 2.2. Thus the horizontal and the verticaldisplacements from the baseline make a discrete grid for each station (seeFigure 2.2). The horizontal displacement allows to move along the x and yaxes of the grid points and the vertical displacement allows to move alongthe z axis. Our goal is to find, for each station, a horizontal offset thatgenerates a horizontal alignment and a vertical alignment which is (locally)optimal.Since every point in the designated corridor has the ground profile data,we can make an alignment by taking a point from each station and optimiz-ing it as a vertical alignment optimization problem by fixing a horizontalalignment. For instance, the orange curve and the purple curve in Figure 2.1could make a horizontal alignment and by fixing that particular alignmentwe get a vertical alignment optimization problem. Each station has somehorizontal offset values associated with the offset data points. Note thatat the base data point of each station the offset value is zero and at theleft and right sides of base data points the offset is positive and negative,respectively. To formulate the horizontal alignment optimization problem,we can now consider the vertical alignment and the horizontal alignment142.2. Problem FormulationStation i Station i+1  Station i+2  0  1  2  - 1  - 2  Vertical offset Data point  z  Figure 2.2: Three dimensional alignment.together in a way that optimizes the vertical alignment cost by varying thehorizontal offset value.Let S = {1, 2, 3, . . . , n} be the index set for the stations. The decisionvariable xi is the horizontal offset value at station i ∈ S. The lower boundand the upper bound of the horizontal offset value of station i ∈ S aredefined as li and ui, respectively. In vector form, the horizontal offset X,the lower bound L, and the upper bound U can be written asX = (x1, x2, x3, · · · , xn)ᵀ,L = (l1, l2, l3, · · · , ln)ᵀ, andU = (u1, u2, u3, · · · , un)ᵀ.(2.1)The dimension of the vector X is the number of stations. Now the problemcan be written mathematically as follows:min f(X) = CVA(X)s.tL ≤ X ≤ U,X ∈ Rn.(2.2)where CVA(X) is a function that returns the cost of an optimal vertical152.3. Solution Approachalignment for a horizontal offset X. So the objective function of the pro-posed formulation is a vertical alignment optimization problem that can becalculated by the method proposed in [HHLR14].2.3 Solution ApproachThe objective function of the problem is an optimization problem itselfthat is a large scale mixed integer program. So it is very hard to access thederivative information of the objective function (if it exists). We applied aderivative-free optimization (DFO) approach to deal with the problem. InDFO approach, we can put the objective function and the bound constraintsin a blackbox (see Figure 2.3) and optimize the problem without knowingmuch information on the objective function. Only a vector X is given as aninput in the blackbox and an output value is obtained without knowing howthe output is computed. To solve our problem we used the NOMAD [LD11](see http://www.gerad.ca/nomad) solver that implements a mesh adaptivedirect search (MADS) algorithm developed in [AD06]. The NOMAD solveris an open source solver that is proven to be competitive in solving DFOproblems [RS13]. We can integrate it as a static library. The flowchart ofthe solving technique is illustrated in Figure 2.4.Solution Approach HA Obj = VAOptimization   X DFO Technique NOMAD Solver     value   Black Box HAOptimization Problem HA Constraints 1 Figure 2.3: Blackbox optimization in horizontal alignment optimizationproblem.The algorithm takes a three dimensional alignment data as the inputdata. The VAOptimization block makes the blackbox for the MADS algo-rithm. The MADS algorithm is an iterative algorithm that continues untilthe optimal solution (i.e. the mesh is small enough) is found. Every iter-ation of the MADS algorithm needs to evaluate the blackbox. So we aresolving a vertical alignment optimization problem at each iteration. There-fore the optimal solution of the defined problem in Equation (2.2) gives usthe optimal vertical and the horizontal alignment.162.3. Solution ApproachStart  Input Data  H A  Optimal ?  VAOptimization   Extract VA data Exceed terminating parameters limit  Y ES  Optimal VA & HA  End  Optimal VA for a HA  YES  NO  NO  Figure 2.4: Flowchart of the solution approach.The NOMAD solver has some terminating parameters to stop the MADSalgorithm. For instance, we can set the maximum number of iterations forthe MADS algorithm. So if the limit of the terminating parameters is ex-ceeded, the algorithm terminates and eventually ends up with a non-optimalhorizontal alignment but the optimal vertical alignment is guaranteed to be(globally) optimal for the given horizontal alignment.The horizontal offsets given by the input data are discrete values butour formulation has continuous offset variables. The lowest and highesthorizontal offsets are the lower and higher bounds, respectively. To get theground profile data for any offset within the bound, linear interpolation isused. Let ya and yb be the ground profile data for the horizontal offset xaand xb, respectively. For any offset x within xa and xb the ground profiledata is interpolated using the following equation:y = ya + (yb − ya)x− xaxb − xa. (2.3)172.4. Numerical Results2.4 Numerical ResultsThe experiments were setup with 50 test problems with a different num-ber of stations. We used the derivative free optimization solver NOMAD(version 3.5, available in http://www.gerad.ca/nomad) to solve the opti-mization problems. All of the numerical experiments were performed on aDell workstation with an Intel(R) Xenon(R) 2.40 GHz (2 cores) processor,24 GB of RAM and a 64-bit Windows 7 Enterprise operating system.We performed numerical experiments on five different roads. For eachroad, we created ten different test problems by varying the number of sta-tions. To analyze the performance, we consider the number of function calls(blackbox evaluations) and the wall-clock time for each test problem. Thefull set of numerical data is included in Appendix A.1.0204060801001201401601802000 10 20 30 40 50 60Time (in minute)No. of StationsFigure 2.5: Required time with respect to number of stations for solvedproblem only.Figures 2.5 and 2.6 shows the wall-clock time and the number of functioncalls required to solve the test problems. Since the numerical experimentswere performed on five different roads, for every number of stations, we havefive different test problems. As a terminating condition of the algorithm,we set timeout to 3 hours. When the number of stations is up to 30, allof the five test problems can be solved in 3 hours. From Figures 2.5, wecan see that when the number of stations increased to 45 and 50 then onlyone problem can be solve within the time-limit. From Figure 2.6, we can182.5. Summary05000100001500020000250000 10 20 30 40 50 60No. of Function CallsNo. of StationsFigure 2.6: Growth of no. of function calls with respect to number ofstations.also observe that for a road of 45 or 50 stations, the solver required around17250 function calls, which is a large number of function calls to solve aproblem corresponding to a small road of 45 or 50 stations. It would beworth mentioning that a typical road is closer to 200 stations.2.5 SummaryWe have discussed a very straight-forward formulation of the horizontalalignment optimization problem. We introduced a derivative-free optimiza-tion approach to solve the problem. In this basic optimization model, theproblem size increases as the number of stations increases. Usually, theNOMAD solver can only effectively handle a problem of a small numberof variables; i.e., the problem size is less than 50 [LD11]. In Addition, themodel yields a piece-wise linear curve, which is not used by engineers inpractice. Considering all of the engineering specifications of a horizontalalignment, a more precise formulation could be developed for a road of alarge number of stations (i.e., more than 100 stations). In the next chapter,we explain how to build a practical model.19Chapter 3Horizontal alignmentoptimization modelIn this chapter, we describe a horizontal alignment optimization modelthat produces a piece-wise linear-circular curve instead of the piecewise lin-ear curve outputed by the basic model introduced in Chapter 2. We alsodescribe in detail the geometric specifications of the model.3.1 Geometric representation of horizontalalignmentIn this model, a horizontal alignment consists of a sequence of circularcurves and tangential lines. The circular curves and tangential lines aredefined by some intersection points and the radius of curvature associatedwith each intersection point. In Figure 3.1, S and E are the start and endpoints of the alignment, respectively. The intersection points of the align-ment are P1, P2, and P3. Each intersection point has a radius of curvaturethat defines the circular curve. The radius of curvature associated with theintersection points P1, P2, and P3 are r1, r2, and r3. The purple and redportions of the alignment in Figure 3.1 are the circular curve and tangentialline segments, respectively.Let i be the index of the intersection points and np be the number ofintersection points. Since the intersection point Pi has an associated radiusof curvature ri, we define an intersection point with radius of curvature as(Pi, ri), where Pi ∈ R2 and ri ∈ R. Without loss of generality, we can saythat the start and end points are a point in R2 with zero radius of curvature.The starting and end points are denoted as (P0, 0) and (Pnp+1, 0). So werepresent a horizontal alignment HA as the sequenceHA = ((P0, 0), (P1, r1), (P2, r2), . . . (Pnp , rnp), (Pnp+1, 0)). (3.1)To determine the actual horizontal alignment, we need to calculate thecircular curves and tangential line segments from the given intersection203.1. Geometric representation of horizontal alignmentX Y Figure 3.1: Geometric representation of horizontal alignment. The align-ment displayed is represented as ((S, 0), (P1, r1), (P2, r2), (P2, r2), (E, 0)).𝑃𝑖−1 𝑃𝑖+1 𝑃𝑖  𝐸𝑖 𝐹𝑖 𝐶𝑖  𝑄𝑖 Figure 3.2: Geometric specifications of a circular curve.213.1. Geometric representation of horizontal alignmentpoints and the associated radius of curvatures. So for each intersectionpoint Pi, we need to find out the two tangential points and the center ofcurvature. Let Ei and Fi be the left and right tangential point, respectively.In Figure 3.2 the green points are the two tangential points. Let Ci (redpoint in Figure 3.2) be the center of curvature that corresponds to the inter-section point Pi. We can calculate Ei, Fi, and Ci for each intersection pointPi using the radius of curvature ri and the three consecutive intersectingpoints Pi−1, Pi, and Pi+1.Tangential point calculationWe define the following variables:– θi is the angle at Pi using three consecutive intersection point Pi−1,Pi, and Pi+1.– Ui is the vector from the point Pi to Pi−1.– Vi is the vector from the point Pi to Pi+1.– Wi is the vector from the point Pi−1 to Pi+1.– Qi is the intersection point of the angle bisector of θi and the linejoining Pi−1 and Pi+1.By definition, we haveUi = Pi−1 − Pi,Vi = Pi+1 − Pi,Wi = Pi+1 − Pi−1.(3.2)We can calculate the angle θi by using the dot product of the vector Ui andVi.Ui ·Vi = ‖Ui‖‖Vi‖ cos θi. (3.3)Using Equation (3.3) we haveθi = arccos(Ui ·Vi‖Ui‖‖Vi‖). (3.4)Since the angle bisector PiQi bisects the angle θi, we have∠Pi−1PiQi =θi2= ∠Pi+1PiQi. (3.5)223.1. Geometric representation of horizontal alignmentPiPi−1 and PiPi+1 are the tangent to the circle at the tangential point Ei andFi. Thus we have CiEi⊥PiPi−1 and CiFi⊥PiPi+1. The triangle 4PiEiCiand 4PiFiCi are right angle triangles. The segment PiCi is the commonside of 4PiEiCi and 4PiFiCi. Since EiCi=FiCi, we have PiEi = PiFi. Letlt be the length of PiEi. In the triangle 4PiEiCi, we havetanθi2=EiCiPiEi=rilt. (3.6)Solt =ritan θi2. (3.7)Let eˆUi and eˆVi be the two unit vector of Ui and Vi. The tangential pointEi and Fi can be calculated as follows:Ei = Pi + lteˆUi , (3.8)Fi = Pi + lteˆVi . (3.9)Center point calculationFact 3.1 ([Byr47, Book VI Proposition III]). The angle bisector of an anglein a triangle divides the opposite side in the same ratio as the sides adjacentto the angle.Let lb be the length of the QiPi−1. The length of PiPi−1, PiPi+1 andPi−1Pi+1 are ‖Ui‖, ‖Vi‖, and ‖Wi‖, respectively. PiQi is the angle bisectorof θi in 4Pi−1PiPi+1. So using Fact 3.1 we have‖Ui‖‖Vi‖=lb‖Wi‖ − lb. (3.10)Solb =‖Ui‖‖Wi‖‖Ui‖+ ‖Vi‖. (3.11)Let eˆWi be the unit vector of Wi. The point Qi can be calculated as follows:Qi = Pi−1 + lbeˆWi . (3.12)Define Xi asXi = Qi − Pi. (3.13)233.2. Model descriptionLet lx be the length of PiCi. In the triangle 4PiEiCi, we havecosθi2=PiEiPiCi=ltlx. (3.14)Solx =ltcos θi2. (3.15)Let eˆXi be the unit vector of Xi. So the center point Ci can be calculatedas follows:Ci = Pi + lxeˆXi . (3.16)3.2 Model description3.2.1 DefinitionsIn order to model the horizontal alignment, we group a set of consecutivestations to make a segment. We divide the entire corridor into m segments,which are indexed by a set IG = {1, 2, 3 . . . ,m}. Every segment consistsof a set of stations. The gth segment has ng stations. For all g ∈ IG ,the stations associated with the gth segment are indexed by the set ISG ={1, 2, 3, . . . , ng}. So the total number of stations is n =∑g∈IGng. The gthsegment (g ∈ IG) jth station (j ∈ ISG) is denoted by Sg,j . The stations ofthe corridor are indexed by the set IS = {1, 2, 3, . . . n}. The ith (i ∈ IS)station of the corridor is denoted by si. The set of all stations is S ={s1, s2, s3, . . . sn}. We define a function to map a station index of a segmentto the actual station index (i.e. station index of the corridor) as follows:δ : (IG , ISG) 7→ IS . (3.17)Clearly, for all g ∈ IG , j ∈ ISG , i = δ (g, j) =∑g−1p=1 np + j ∈ IS . Therefore,at station si ∈ S, we have Sg,j = si for all g ∈ IG , j ∈ IGS . Each stationhas nd data points, which are indexed by the set ID = {1, 2, 3 . . . , nd}. Theith station kth (k ∈ ID) data point is denoted by Di,k. The set of nd datapoints at station si is Di = {Di,1, Di,2, Di,3 . . . Di,nd}. Corresponding toeach data point, we have vertical road profile data which is defined by avector VAi,k. The vector VAi,k consists of the cut-fill areas of a material atdifferent heights. For example, the data point (x, y) has cut-fill areas of amaterial at different heights (i.e., at some different z-values). The cut-fillareas constitute the vectorVAi,k corresponding to the data point Di,k. At243.2. Model descriptioneach station si ∈ S, we have the leftmost and rightmost offset data pointsthat define the boundary of the corridor. The leftmost and the rightmostdata points of the ith station are denoted by ui and vi and defined as follows:ui = Di,1 ∀i ∈ IS ,vi = Di,nd ∀i ∈ IS .(3.18)The set of the leftmost offset data points is U = {u1, u2, u3, . . . , un}. Theset of the rightmost offset data points is V = {v1, v2, v3, . . . , vn}. At the gthsegment jth station, the leftmost and the rightmost data points are denotedby Ug,j and Vg,j , respectively. So when δ (g, j) = i, we haveUg,j = ui,Vg,j = vi.(3.19)Every two consecutive segments share a common station. The last stationof a segment is the first station of the next segment (see Figure 3.3). Thefollowing equations are satisfied for g = 1, 2, 3, . . . ,m− 1.Sg,ng = Sg+1,1,Ug,ng = Ug+1,1,Vg,ng = Vg+1,1,Dδ(g,ng),k = Dδ(g+1,1),k.(3.20)At each station, the line passing through the leftmost offset data pointand the rightmost offset data point is defined as a cross-section line of thestation, see Figure 2.1. The parametric equation of the cross-section lineLi(t) of the ith station si ∈ S with the leftmost offset data point ui and therightmost offset data point vi isLi(t) = (1− t)ui + tvi for t ∈ R. (3.21)Using the mapping in Equation (3.17), for the gth segment jth station, thecross-section line Lg,j(tlg,j) isLg,j(t) = (1− t)Ug,j + tVg,j for t ∈ R. (3.22)In Equation (3.22), if the parameter t is restricted to [0, 1], we obtain asegment. The equation of the cross-section segment with end-points Ug,jand Vg,j isL¯g,j(t) = (1− t)Ug,j + tVg,j for t ∈ [0, 1] . (3.23)253.2. Model descriptionFigure 3.3: Road segment representation in a specified corridor.Figure 3.4: Horizontal alignment in a specified corridor. The red curve isan example horizontal alignment. The blue stars are the intersection points(IP) and the dotted blue rectangular boxes are feasible region (for moving)associated with the intersection points.We assume that each segment has exactly three intersection points (ex-cept for the last segment which may have two) named Pg,1, Pg,2, and Pg,3263.2. Model descriptionfor the gth segment. Each intersection point of a segment has a radius ofcurvature. For the gth segment rg,1, rg,2, and rg,3 are defined as the radiusof curvatures corresponding to the intersection points Pg,1,Pg,1, and Pg,3, re-spectively. In Figure 3.4, the blue points are the intersection points and thered curve is the associated horizontal alignment. By moving the intersectionpoints, we can build a wide variety of horizontal alignments.Each intersection point has a feasible region. We define the feasibleregion of each intersection point by a rectangular box. The dotted bluerectangles in Figure 3.4, are the feasible region of the intersection points.A rectangular box is defined by the leftmost bottom corner point and therightmost top corner point. Let Bg,1 and Bg,1 be the leftmost bottom cornerpoint and the rightmost top corner point of the rectangular box associatedwith the intersection point Pg,1. So the rectangular box associated with Pg,1is defined as (Bg,1, Bg,1). Similarly, the rectangular boxes associated withPg,2 and Pg,2 are defined as (Bg,2, Bg,2) and (Bg,3, Bg,3), respectively.3.2.2 The optimization modelThe road design problem is formulated as a bi-level optimization prob-lem. We can solve a vertical alignment optimization problem for a fixedhorizontal alignment. So the main idea is to move the horizontal alignmentand then minimize the vertical alignment.Basic approach: one variable per stationAt each station si ∈ S we are given the data points Di,k and correspond-ing vertical road profile data VAi,k (∀k ∈ ID) as input. At a station si, foran arbitrary data point Di,a the vertical road profile data VAi,a between twoconsecutive data points Di,k and Di,k+1 along the cross-section line segmentL¯i(t) is interpolated using the following equationVAi,a = VAi,k + (VAi,k+1 −VAi,k)‖Di,a −Di,k‖‖Di,k+1 −Di,k‖. (3.24)Therefore, we have the vertical road profile data along every cross-sectionline segment (L¯g,j(t) ∀g ∈ IG , ∀j ∈ ISG). We can build a horizontal align-ment by taking a point from each cross-section line segment. For instance,the red and purple piecewise linear curve in Figure 3.5 shows two differenthorizontal alignments for a road segment. For a fixed horizontal alignment,the optimal vertical alignment cost can be calculated by solving the verticalalignment optimization problem formulated in [HHLR14]. So the cost of a273.2. Model descriptionhorizontal alignment is the optimal vertical alignment cost corresponding tothat horizontal alignment. Since we are given Di,k and VAi,k for all stations,we could build the cross-section line Lg,j(t). Thus, by changing t between0 to 1 of the Lg,j(t), we can obtain any point Di,a on Lg,j(t) and the as-sociated VAi,a using Equation (3.24). Let tlg,j be the parameter of the gthsegment jth station. We can obtain all possible horizontal alignments bymoving the parameter tlg,j along the line Lg,j(tlg,j). The parameter valuesof the Lg,j(tlg,j) defines a horizontal alignment. So the parameters of thecross-section line can be used as variables. Let Tl be the variable vectordefining the horizontal alignment as a piecewise linear function. We defineTl = 〈tl1,1, tl1,2, . . . , tl1,n1︸ ︷︷ ︸Segment 1, tl2,1, tl2,2, . . . , tl2,n2︸ ︷︷ ︸Segment 2, . . . . . . , tlm,1, tlm,2, . . . , tlm,nm︸ ︷︷ ︸Segment m〉.Figure 3.5: Piece-wise linear representation of horizontal alignment segmentconsidering all of the cross-section lines.The cost function of a horizontal alignment optimization problem asso-ciated with variable Tl is defined as CVA(Tl). The function CVA(Tl) givesthe optimal vertical alignment cost for Tl. So the horizontal alignment op-timization problem becomesmin0≤Tl≤1CVA(Tl). (3.25)In practice, if we consider all cross-section lines (i.e., all of the stations),we have ng variables for each segment. So the total number of variables is∑mg=1 ng = n, which can be large. We can reduce the number of variablesby defining the horizontal alignment geometrically.283.2. Model descriptionAdvanced approach: three variables per intersection pointObjective function and variablesWe define a horizontal alignment using the intersection points and asso-ciated radius of curvatures. We have three intersecting points Pg,1,Pg,2, andPg,3 for the gth segment. By moving the intersection points and with differ-ent associated radius of curvatures, a wide variety of horizontal alignmentscan be built. So we can have the intersection points and the associatedradius of curvature as the variables.All of the intersection points are on the XY -plane. We define the inter-section points Pg,1, Pg,2, and Pg,3 in Cartesian coordinate as follows:Pg,1 = (pxg,1 , pyg,1),Pg,2 = (pxg,2 , pyg,2),Pg,3 = (pxg,3 , pyg,3).(3.26)Thus pxg,1 , pyg,1 , pxg,2 , pyg,2 , pxg,3 , pyg,3 , rg,1,rg,2, and rg,3 are the variablefor the gth segment. We assume that the starting and end points of thealignment are fixed.Two adjacent segments share an intersection point. Let Pˆg,g+1 =(pˆxg,g+1 , pˆyg,g+1) be the common intersection point between the gth and(g + 1)th segments. So for two consecutive segments we havePg,3 = Pg+1,1,Pˆg,g+1 = Pg,3,Pˆg,g+1 = Pg+1,1.(3.27)Let rˆg,g+1 be the radius of curvature corresponding to the point Pˆg,g+1. Sofor two consecutive segments we haverg,3 = rg+1,1,rˆg,g+1 = rg,3,rˆg,g+1 = rg+1,1.(3.28)Let X be the variable vector of the optimization problem. We haveX = 〈px1,2 , py1,2 , pˆx1,2 , pˆy1,2 , r1,2, rˆ1,2︸ ︷︷ ︸Segment 1, px2,2 , py2,2 , pˆx2,3 , pˆy2,3 , r2,2, rˆ2,3︸ ︷︷ ︸Segment 2. . . . . .pxm−1,2 , pym−1,2 , pˆxm,m−1 , pˆym−1,m , rm−1,2, rˆm−1,m︸ ︷︷ ︸Segment m-1, pxm,2 , pym,2 , rm,2︸ ︷︷ ︸Segment m〉.293.2. Model descriptionሺ݌Ƹ௫మǡయǡ݌Ƹ௬మǡయሻ ሺ݌Ƹ௫యǡరǡ݌Ƹ௬యǡరሻ ሺ݌௫యǡమǡ݌௬యǡమሻ Figure 3.6: An example road of four segments showing the associated vari-ables of the optimization model. The green cross-section lines separate theroad segments. The starting point and the end point of the alignment are(px1,1 , py1,1) and (px4,3 , py4,3), respectively, which are fixed.In Figure 3.6, for a road of four segments, the associated variables aredepicted. Note that the last segment might have two intersection points(when the number of intersection points (IP) is not divisible by 3). Inthat case, the last segment has only variables corresponding to the commonintersection point. For instance, if we assume Figure 3.6 does not have theintersection point (py4,2 , py4,2); i.e., the number of intersection points is 8,then the last segment has only the variables (pˆx3,4 , pˆy3,4) and rˆ3,4, which arealso considered in the previous (third) segment.A horizontal alignment for a road segment consists of some circularcurves and tangential lines. For each segment the horizontal alignmentcurve has three circular curves and two tangential lines (see Figure 3.7).The purple portions and the red portions of the horizontal alignment curvein Figure 3.7 are circular curves and tangential lines, respectively. Let Eg,1,Eg,2, and Eg,3 be the left tangential points; and Fg,1, Fg,2, and Fg,3 be theright tangential points correspond to the intersection points Pg,1, Pg,2, and303.2. Model descriptionFigure 3.7: A segment of a road showing an associated horizontal alignment.Pg,3. The left and right tangential points can be calculated using Equa-tion (3.8) and Equation (3.9) . Let Cg,1, Cg,2, and Cg,3 be the center ofcurvature corresponds to the intersection point Pg,1,Pg,2, and Pg,2. The cen-ter of curvature can be calculated using Equation (3.16). Since all pointsare in XY -plane, we defineCg,1 = (cxg,1 , cyg,1), Cg,2 = (cxg,2 , cyg,2), Cg,3 = (cxg,3 , cyg,3),Eg,1 = (exg,1 , eyg,1), Eg,2 = (exg,2 , eyg,2), Eg,3 = (exg,3 , eyg,3),Fg,1 = (fxg,1 , fyg,1), Fg,2 = (fxg,2 , fyg,2), Fg,3 = (fxg,3 , fyg,3).(3.29)Let Hg,1 Hg,2, Hg,3, Hg,4, and Hg,5 be five parametric pieces of the horizontalalignment curve for the gth segment. Hg,1, Hg,2, and Hg,3 are the circulararc corresponding to the intersection points Pg,1, Pg,2, and Pg,3. Hg,4 is thetangential lines connecting the two arcs Hg,1 and Hg,2. Hg,5 is the tangentiallines connecting the two arcs Hg,2 and Hg,3. Let tcg,1, tcg,2, tcg,3, tcg,4, and tcg,5be the parameters of Hg,1 Hg,2, Hg,3, Hg,4, and Hg,5, respectively.The parametric equation of the circle corresponding to the intersectionpoint Pg,1 can be written as follows:[x(tcg,1)y(tcg,1)]=[rg,1 cos(tcg,1) + cxg,1rg,1 sin(tcg,1) + cyg,1]for tcg,1 ∈ [0, 2pi] . (3.30)Equation (3.30) gives the full circle but we need a circular arc with twoendpoints. So we need to calculate the bounds of tcg,1 in Equation (3.30) toget the endpoints of a circular arc. The tangential point Eg,1 and Fg,1 arethe two endpoints of the circular arc associated with the intersection point313.2. Model descriptionPg,1. Since Eg,1 and Fg,1 are on the circle, we have[rg,1 cos(tcg,1) + cxg,1rg,1 sin(tcg,1) + cyg,1]=[exg,1eyg,1], (3.31)and [rg,1 cos(tcg,1) + cxg,1rg,1 sin(tcg,1) + cyg,1]=[fxg,1fyg,1]. (3.32)Equation (3.31) and Equation (3.32) give the two values of t that makethe bounds for the circular arc with two end points Eg,1 and Fg,1. FromEquation (3.31) we deducetcg,1 = arccosexg,1 − cxg,1rg,1or arcsineyg,1 − cyg,1rg,1. (3.33)Similarly, from Equation (3.32) we havetcg,1 = arccosfxg,1 − cxg,1rg,1or arcsinfyg,1 − cyg,1rg,1. (3.34)The ranges of arccos and arcsin are [0, pi] and[−pi2 ,pi2], respectively. But theparameter tcg,1 of the full circle in Equation (3.30) varies from 0 to 2pi. Inorder to handle this issue, first we need to identify the quadrant of the circlein which the two endpoints Eg,1 and Fg,1 lie on, and then adjust the valueof tcg,1 to calculate the actual value with respect to the full circle. Let teg,1and tfg,1 be the two parameter values corresponding to the two endpointsEg,1 and Fg,1, respectively. The value of the parameter associated with theendpoint Eg,1 can be written as follows:teg,1 =arcsinexg,1−cxg,1rg,1ifexg,1−cxg,1rg,1≥ 0 andeyg,1−cyg,1rg,1≥ 0,pi − arcsinexg,1−cxg,1rg,1ifexg,1−cxg,1rg,1< 0 andeyg,1−cyg,1rg,1≥ 0,pi − arcsinexg,1−cxg,1rg,1ifexg,1−cxg,1rg,1< 0 andeyg,1−cyg,1rg,1< 0,2pi + arcsinexg,1−cxg,1rg,1ifexg,1−cxg,1rg,1≥ 0 andeyg,1−cyg,1rg,1< 0.(3.35)323.2. Model descriptionSimilarly, associated with the endpoint Fg,1, the value of the parameter istfg,1 =arcsinfxg,1−cxg,1rg,1iffxg,1−cxg,1rg,1≥ 0 andfyg,1−cyg,1rg,1≥ 0,pi − arcsinfxg,1−cxg,1rg,1iffxg,1−cxg,1rg,1< 0 andfyg,1−cyg,1rg,1≥ 0,pi − arcsinfxg,1−cxg,1rg,1iffxg,1−cxg,1rg,1< 0 andfyg,1−cyg,1rg,1< 0,2pi + arcsinfxg,1−cxg,1rg,1iffxg,1−cxg,1rg,1≥ 0 andfyg,1−cyg,1rg,1< 0.(3.36)Note that the four cases in Equation (3.35) and Equation (3.36) representthe first, second, third and fourth quadrants of the circle, respectively.In Equation (3.35) and Equation (3.36), we do not know which valueis the upper bound or lower bound of the circular arc connecting the twoendpoints Eg,1 and Fg,1. So the lowest and highest of the two values arethe lower bound and the upper bound, respectively. Let tg,1 and tg,1 be theupper bound and the lower bound for the circular arc Hg,1. We havetg,1 = min{teg,1, tfg,1},tg,1 = max{teg,1, tfg,1}.(3.37)Note that if any of the two endpoints lies on the fourth quadrant andthe other endpoint lies on the first quadrant then the value of the parametercorresponding to the first quadrant has to be added by 2pi, otherwise a wrongarc will be generated. In Figure 3.8 an example of this issue is illustrated.For the example shown in Figure 3.8, using the formulas in Equations (3.35),(3.36), and (3.37), we can calculate the lower bound and upper bound of thearc as pi4 and7pi4 which generates the red arc. In Figure 3.8, we can observethat the correct arc is the green arc rather than the red arc. So in orderto generate the green arc, we have to add 2pi to the associated parametervalue of the endpoint Eg,1 (which lies on the first quadrant). After adding2pi to pi4 (the value associated with Eg,1), we get the new lower bound andupper bound as 7pi4 and9pi4 , respectively, which generates the green arc inFigure 3.8.Let tg,2, tg,3 be the lower bounds and tg,2, tg,3 be the upper bounds forthe circular arcs Hg,2 and Hg,3, respectively. The lower and upper boundfor Hg,2 and Hg,3 can be calculated similarly as in Equation (3.37). So theparametric equation of the circular arcs Hg,1, Hg,2, and Hg,3 areHg,1(tcg,1) =[rg,1 cos(tcg,1) + cxg,1rg,1 sin(tcg,1) + cyg,1]for tcg,1 ∈[tg,1, tg,1], (3.38)333.2. Model descriptionݐ௚ǡ1௖ ൌߨȀͶ ݐ௚ǡ1௖ ൌ͹ߨȀͶ 𝑃௚ǡ1 𝑃௚ǡଶ 𝑃௚ǡଷ 𝐸௚ǡ1 𝐹௚ǡ1 Figure 3.8: An example of the quadrants issue in generation of a circulararc.Hg,2(tcg,2) =[rg,2 cos(tcg,2) + cxg,2rg,2 sin(tcg,2) + cyg,2]for tcg,2 ∈[tg,2, tg,2], (3.39)andHg,3(tcg,2) =[rg,3 cos(tcg,3) + cxg,3rg,3 sin(tcg,3) + cyg,3]for tcg,3 ∈[tg,3, tg,3]. (3.40)The tangential line segments Hg,4 connects the endpoints Fg,1 and Eg,2.The parametric equation of Hg,4 isHg,4(tcg,4) = (1− tcg,4)Fg,1 + tcg,4Eg,2 for tcg,4 ∈ [0, 1] . (3.41)343.2. Model descriptionSimilarly, the tangential line segments Hg,5 connects the endpoints Fg,2 andEg,3. The parametric equation of Hg,5 isHg,5(tcg,5) = (1− tcg,5)Fg,2 + tcg,5Eg,3 for tcg,5 ∈ [0, 1] . (3.42)In order to calculate the cost of the horizontal alignment, we need tocompute parameter tlg,j of the cross-section lines. We have two differentcases: finding the intersection parameters for a circular arc and a line seg-ment and finding the intersection parameters for two line segments (i.e., across section line segment and a tangential line segment).For each segment, we have a set of cross-section lines{Lg,1, . . . , Lg,ng}.A cross-section line Lg,j(tlg,j), j ∈ ISG of the gth segment isLg,j(tlg,j) = (1− tlg,j)Ug,j + tlg,jVg,j for tlg,j ∈ R. (3.43)Since Ug,j and Vg,j are in the XY -plane, we define Ug,j = (uxg,j , uyg,j ) andVg,j = (vxg,j , vyg,j ). Equation (3.43) can be written as follows:x = uxg,j + (vxg,j − uxg,j )tlg,j ,y = uyg,j + (vyg,j − uyg,j )tlg,j .(3.44)The equation of the circle that corresponds to the intersection point Pg,1 inimplicit form is(x− cxg,1)2 + (y − cyg,1)2 − rg,12 = 0. (3.45)Substituting for x and y from Equation (3.44) into the Equation (3.45) givesa quadratic equation of tlg,j :(uxg,j +(vxg,j−uxg,j )tlg,j−cxg,1)2+(uyg,j +(vyg,j−uyg,j )tlg,j−cyg,1)2−rg,12 = 0.(3.46)The two roots of Equation (3.46) give the points on the line that cuts thecircle. We deducetlg,j =a±√∆b, (3.47)wherea =(vxg,j − uxg,j )(cxg,1 − uxg,j ) + (vyg,j − uyg,j )(cyg,1 − uyg,j ),∆ =rg,12((vxg,j − uxg,j )2 + (vyg,j − uyg,j )2)− ((vxg,j − uxg,j )(cyg,1 − uyg,j )− (vyg,j − uyg,j )(cxg,1 − uxg,j ))2, andb =(vxg,j − uxg,j )2 + (vyg,j − uyg,j )2.353.2. Model descriptionThe two different values of tlg,j give the two intersection points of Equa-tion (3.44) and Equation (3.45) on the line Lg,j(tlg,j). The roots maybesimilar, in that case, the line intersect only in a single point. If the rootsare imaginary then there is no intersection. Let Sg,j = (sxg,j , syg,j ) be anintersection point obtained by tlg,j . To calculate the parameter of the circlein Equation (3.30) corresponding to the point Sg,j , we deduce[rg,1 cos(tcg,1) + cxg,1rg,1 sin(tcg,1) + cyg,1]=[sxg,1syg,1]. (3.48)Sotcg,1 = arccossxg,1 − cxg,1rg,1or arcsinsyg,1 − cyg,1rg,1. (3.49)As we described earlier, due to the quadrant issue of the circle, the valueof the parameter tcg,1 has to be adjusted. Let tsg,1 be the parameter valuecorresponding to the point Sg,j . We havetsg,1 =arcsinsxg,1−cxg,1rg,1ifsxg,1−cxg,1rg,1≥ 0 andsyg,1−cyg,1rg,1≥ 0,pi − arcsinfxg,1−cxg,1rg,1ifsxg,1−cxg,1rg,1< 0 andsyg,1−cyg,1rg,1≥ 0,pi − arcsinfxg,1−cxg,1rg,1ifsxg,1−cxg,1rg,1< 0 andsyg,1−cyg,1rg,1< 0,2pi + arcsinfxg,1−cxg,1rg,1ifsxg,1−cxg,1rg,1≥ 0 andsyg,1−cyg,1rg,1< 0.(3.50)If tlg,j ∈ [0, 1] and tsg,1 ∈[tg,1, tg,1]then the intersection point is in thecorridor. In this case, we accept the value of the parameter tlg,j , otherwisewe reject the value. Similarly, for all other circular arcs we can calculate thevalue of the parameter tlg,j .Now we need to calculate the intersection point between the cross-sectional line and the tangential line segment. The equation of the tangentialline segment in Equation (3.41) can be written as follows:x = fxg,1 + (exg,2 − fxg,1)tcg,4,y = fyg,1 + (eyg,2 − fyg,1)tcg,4.(3.51)To calculate the intersection parameter of a cross-section line and a tan-gential line, from Equation (3.51) and Equation (3.44) we have the followinglinear system of equations:uxg,j + (vxg,j − uxg,j )tlg,j = fxg,1 + (exg,2 − fxg,1)tcg,4,uyg,j + (vyg,j − uyg,j )tlg,j = fyg,1 + (eyg,2 − fyg,1)tcg,4.(3.52)363.2. Model descriptionEquations (3.52) in matrix form are[vxg,j − uxg,j exg,2 − fxg,1vyg,j − uyg,j eyg,2 − fyg,1] [tlg,jtcg,4]=[fxg,1 − uxg,jfyg,1 − uyg,j]. (3.53)The solution for tlg,j and tcg,4 is[tlg,jtcg,4]=[vxg,j − uxg,j exg,2 − fxg,1vyg,j − uyg,j eyg,2 − fyg,1]−1 [fxg,1 − uxg,jfyg,1 − uyg,j]. (3.54)In order to calculate the solution defined in Equation (3.54), the coefficientmatrix has to be invertible. Thus in Equation (3.52), if the coefficient matrixis not full-rank, the system has no solution (i.e. the two lines are parallel). Ifthe value of both tlg,j and tcg,4 are in [0, 1], we accept the solution. Otherwise,the solution point is outside of the corridor.If all tlg,j ∈ [0, 1] we can compute the optimal vertical alignment cost fora horizontal alignment defined by X. On the other hand, if any tlg,j /∈ [0, 1],the alignment is outside of the corridor. In this case, we set the optimalvertical alignment cost to infinity. Finally, the objective function of thehorizontal alignment optimization can be written asf(X) ={CVA(X) if tlg,j ∈ [0, 1] ∀g ∈ IG , j ∈ ISG ,∞ otherwise. (3.55)ConstraintsA horizontal curve consists of the tangential line segments followed bythe circular arcs. Two consecutive circular arcs are connected by a tangentialline. The horizontal alignment will be discontinuous when two circular arcsoverlap along the tangential line (see Figure 3.9).For the gth segment, we have two tangential lines. The line passingthrough the intersection points Pg,1 and Pg,2 and the line passing throughthe intersection points Pg,2 and Pg,3 are the two tangential lines. In orderto maintain continuity on the line passing through the intersection pointsPg,1 and Pg,2, the length of Pg,1Pg,2 must be greater than or equal to thesummation of the length of Pg,1Fg,1 and the length of Pg,2Eg,2. So we canwrite the continuity constraints as follows:‖Pg,2 − Pg,1‖ ≥ ‖Pg,1 − Fg,1‖+ ‖Pg,2 − Eg,2‖. (3.56)373.2. Model description𝑃௚ǡଶ 𝑃௚ǡଷ Figure 3.9: Discontinuity in a horizontal alignment.Similarly, on the line passing through the intersection points Pg,3 and Pg,2,the continuity constraint becomes‖Pg,2 − Pg,3‖ ≥ ‖Pg,3 − Eg,3‖+ ‖Pg,2 − Fg,2‖. (3.57)Each intersection point has a feasible region. The feasible region is de-fined by a rectangular box. We define the box corner points in Cartesiancoordinate as follows:Bg,1 = (bxg,1 , byg,1), Bg,1 = (bxg,1 , byg,1);Bg,2 = (bxg,2 , byg,2), Bg,2 = (bxg,2 , byg,2);Bg,3 = (bxg,3 , byg,3), Bg,3 = (bxg,3 , byg,3).(3.58)So, in order to bound the intersection points inside of the rectangular boxeswe have the following constraints for the gth segment:bxg,1 ≤ pxg,1 ≤ bxg,1 ,byg,1 ≤ pyg,1 ≤ byg,1 ,bxg,2 ≤ pxg,2 ≤ bxg,2 ,byg,2 ≤ pyg,2 ≤ byg,2 ,bxg,3 ≤ pxg,3 ≤ bxg,3 ,byg,3 ≤ pyg,3 ≤ byg,3 .(3.59)383.2. Model descriptionTwo adjacent segments have a common intersection point Pˆg,g+1. Let(Bˆg,g+1, Bˆg,g+1) be the rectangular box corresponding to the common inter-section point Pˆg,g+1. So for two consecutive segments we have(Bˆg,g+1, Bˆg,g+1) = (Bg,1, Bg,1),(Bˆg,g+1, Bˆg,g+1) = (Bg,3, Bg,3).(3.60)We define the rectangular box corner points Bˆg,g+1 and Bˆg,g+1 in Cartesiancoordinate as follows:Bˆg,g+1 = (bˆxg,g+1 , bˆyg,g+1),Bˆg,g+1 = (bˆxg,g+1 , bˆyg,g+1).(3.61)Since the starting and end points are fixed the constraints (3.59) for thegth segment can be rewritten as follows:bxg,2 ≤ pxg,2 ≤ bxg,2 ∀g ∈ {1, 2, .....m} ,byg,2 ≤ pyg,2 ≤ byg,2 ∀g ∈ {1, 2, .....m} ,bˆxg,g+1 ≤ pˆxg,g+1 ≤ bˆxg,g+1 ∀g ∈ {1, 2, .....m− 1} ,bˆyg,g+1 ≤ pˆyg,g+1 ≤ bˆyg,g+1 ∀g ∈ {1, 2, .....m− 1} .(3.62)The radius of curvature associated with each intersection point has aminimum value. If the radius of curvature is too small (or zero) then ahorizontal alignment might get a sharp turn. Let Rmin be the minimumradius of curvature. For the radius of curvatures rg,1, rg,2, and rg,3 of thegth segment, we have the following constraints:rg,1 ≥ Rmin,rg,2 ≥ Rmin,rg,3 ≥ Rmin.(3.63)For the starting and end points of the alignment, the radius of curvaturesare zero (i.e. r1,1 = 0 and rm,3 = 0). Since for two adjacent segmentsrˆg,g+1 = rg,3 = rg+1,1, we can rewrite the radius of curvature constraints asfollows:rˆg,g+1 ≥ Rmin ∀g ∈ {1, 2, .....m− 1} ,rg,2 ≥ Rmin ∀g ∈ {1, 2, .....m} .(3.64)393.3. Model Summary3.3 Model SummaryThe summary of the optimization model considering all of the geometricspecifications is stated as follows.Objective functionf(X) ={CVA(X) if tlg,j ∈ [0, 1] ∀g ∈ IG , j ∈ ISG ,∞ otherwise. (3.65)Continuity constraints‖Pg,2 − Pg,1‖ ≥ ‖Pg,1 − Fg,1‖+ ‖Pg,2 − Eg,2‖ ∀g ∈ {1, 2, .....m} , (3.66)‖Pg,2 − Pg,3‖ ≥ ‖Pg,3 − Eg,3‖+ ‖Pg,2 − Fg,2‖ ∀g ∈ {1, 2, .....m} , (3.67)IP bound constraintsbxg,2 ≤ pxg,2 ≤ bxg,2 ∀g ∈ {1, 2, .....m} ,byg,2 ≤ pyg,2 ≤ byg,2 ∀g ∈ {1, 2, .....m} ,bˆxg,g+1 ≤ pˆxg,g+1 ≤ bˆxg,g+1 ∀g ∈ {1, 2, .....m− 1} ,bˆyg,g+1 ≤ pˆyg,g+1 ≤ bˆyg,g+1 ∀g ∈ {1, 2, .....m− 1} ,(3.68)Minimum radius of curvature constraintsrˆg,g+1 ≥ Rmin ∀g ∈ {1, 2, .....m− 1} ,rg,2 ≥ Rmin. ∀g ∈ {1, 2, .....m} .(3.69)40Chapter 4Numerical resultsIn this chapter, we present our experimental data and discuss the modelperformance to solve the real-world problems. We solve the test problemset using the two different derivative free optimization solvers: NOMAD[ALT09] and HOPSPACK [Pla09]. Finally, we compare the results of thetwo solvers.4.1 Experimental setupWe performed numerical experiments on five different roads listed inTable 4.1. The road profile data are given by our industry partner Soft-ree Technical System Inc. Note that Road D is a backtracking road andthe other four roads i.e., Road A, Road B, Road C, and Road E are non-backtracking roads.Table 4.1: Specifications of the test problemsRoad Name No. of stations No. of IPsRoad A 73 8Road B 361 5Road C 258 14Road D 118 22Road E 74 9All of the experiments were carried out in a Dell workstation with anIntel(R) Xenon(R) 2.40 GHz (2 cores) processor, 24 GB of RAM and a64-bit Windows 7 Enterprise operating system. We used two derivativefree optimization solvers, NOMAD [ALT09] (version 3.5, available at http://www.gerad.ca/nomad) and HOPSPACK [Pla09] (version 2.0.2, availableat http://www.sandia.gov/hopspack) to solve the test problems. Theoptimization model was implemented in C++ using Microsoft Visual Studio2010 Professional Edition.414.2. The NOMAD and HOPSPACK solvers4.2 The NOMAD and HOPSPACK solversThe NOMAD and HOPSPACK solvers use two different derivative freeoptimization algorithms of the same category. Both of the solvers use thepattern search to find an optimal solution. The NOMAD and HOPSPACKsolvers use the Mesh Adaptive Direct Search (MADS) algorithm [AD06]and the Asynchronous Parallel Pattern Search (APPS) algorithm [Kol05,GK06], respectively. Both algorithms convergence to a locally optimal point[AD06], [Kol05]. When the mesh size of the MADS algorithm goes to zero,it converges to a local minimum [AD06]. Similarly, if the step length ofthe APPS algorithm goes to zero, it converges to a local minimum [Kol05].It is worth mentioning that both MADS and APPS algorithm are globallyconvergent to a locally optimum point and a solution (i.e., a minimizer)obtained by the algorithms depends on the starting point.As a stopping condition of the algorithms, we use minimum mesh sizeand minimum step length for the MADS and APPS algorithms, respectively.Since we are interested in a solution close to a local minimum, we set boththe minimum mesh size and minimum step length to 0.1. The input data ofour model are given in meters. The final scaling (see [ALT09] and [Pla09])of the variables of our model goes down below 10 cm, which means a localminimum should exist in less than 10 cm distance. However, we can setthese parameter values of the algorithms to a value less than 0.1 for a bet-ter precision, but most of the agents (including our industry partner) onlyrequire a 10 cm precision in the optimal solution.Both solvers, NOMAD and HOPSPACK need an initial starting pointto run the algorithm. We used the baseline alignment of a corridor as aninitial starting point for both solvers. However, the NOMAD solver gives adeterministic solution (i.e., different independent runs of the algorithm yieldthe same solution), while the HOPSPACK solver gives a non-deterministicsolution (i.e., different independent runs of the algorithm might yield dif-ferent solutions). So first, we solved the test problems using the NOMADsolver and then compare with the HOPSPACK solver solutions obtained bydifferent independent runs.4.3 Results for the test problemsOur model works well for both backtracking and non-backtracking align-ments. Figure 4.1 and Figure 4.2 illustrate an initial alignment and anoptimum alignment for a non-backtracking road and a backtracking road,424.3. Results for the test problemsrespectively.Table 4.2 shows the cost improvement of the objective functions, thenumber of black-box evaluation and wall-clock time required to solve thetest problems using the NOMAD solver.Table 4.2: Cost improvement, no. of black-box evaluations and wall-clocktime required to solve the test problems using the NOMAD solver.RoadNameInitialalignmentcostOptimizedalignmentcostCostImprov-ement(%)No. ofBlack-boxevalua-tionsWall-clocktime(sec-onds)Road A 1,897 1,361 28% 2,073 1,445Road B 17,036 15,198 11% 2,528 1,770Road C 87,829 69,621 21% 37,165 45,647Road D 31,031 14,418 54% 90,535 47,613Road E 8,054 6,498 19% 11,101 5,588Now we compare the HOPSPACK solver results with the results ob-tained by the NOMAD solver. We solved each test problem five times inde-pendently using the HOPSPACK solver. Table 4.3 lists the optimum valuesof the objective functions obtained by five independent executions of theHOPSPACK solver for each test problem. The differences in the optimumobjective function values are calculated with respect to the value obtainedby the NOMAD solver. So in Table 4.3, a “ + ” value in the Difference inthe optimum costs column indicates the HOPSPACK solver yields a bettersolution than the NOMAD solver and a “− ” value indicates the opposite.Combining the results obtained for the different roads listed in Table 4.3,we make an overall comparison between the two solvers. We observed thatthe HOPSPACK solver might yield a better or a worse solution than thesolution obtained by the NOMAD solver. Thus, considering the toleranceof the difference in the optimum objective values obtained by two solver, wecount the number of times a solver wins with respect to the other solver.Table 4.4 shows the comparison of the solvers for different tolerance val-ues of the difference in the optimum objective values. The x% tolerance ofthe difference in optimum objective values means if the optimum objectivevalues obtained by the two solvers are in between −x% to +x%, then thesolvers yield the same solution (i.e., the two solvers tie), otherwise a posi-tive percentage value indicates the HOPSPACK solver wins and a negative434.3. Results for the test problems950095509600965097009750980098509900470047504800485049004950XY  Initial Alignment (Cost: $ 1898.09)Optimized Alignment: NOMAD (Cost: $ 1361.77)Optimized Alignment: HOPSPACK (Cost: $ 1278.5)Figure 4.1: A non-backtracking alignment (the test problem associated withRoad A) showing the initial alignment and the optimized alignments ob-tained by the NOMAD and HOPSPACK solvers.percentage value indicates the NOMAD solver wins.In Table 4.4, we see that if the tolerance of difference in the optimumobjective value is ±3% or above, then the two solver tie for more than 50%test runs (i.e., more than 13 test runs among 25 test runs). We can alsoobserve that for any case of the tolerance change in the optimum objectivefunction value, the difference in the number of times the NOMAD solverwins and the number of times the HOPSPACK solver wins is at most 2.So in terms of optimum objective values obtained by the two solvers, theperformance of both solvers are roughly equivalent.We also recorded the number of black-box evaluations required for theHOPSPACK and NOMAD solvers to get the optimum solutions. We cal-culated the difference in number of black-box evaluations with respect tothe number of black-box evaluations required by the NOMAD solver. Soin Table 4.5, a “ + ” value the Difference in no. of black-box evaluationscolumn indicates the HOPSPACK solver required less black-box evaluationsthan the NOMAD solver and a “− ” value indicates the opposite.444.3. Results for the test problems8.5928.5938.5948.5958.5968.5978.5988.5998.6x 1056.2856.28556.2866.28656.2876.28756.2886.28856.289x 105XY  Initial Alignment (Cost: $ 31253)Optimized Alignment−NOMAD (Cost: $ 14418)Optimized Alignment−HOPSPACK (Cost: $ 13190.9)Figure 4.2: A backtracking alignment (the test problem associated withRoad D) showing the initial alignment and the optimized alignments ob-tained by the NOMAD and HOPSPACK solvers.In Table 4.5, we can see that for all of the 25 test runs, the HOPSPACKsolver required less black-box evaluation than the NOMAD solver. For thisparticular problem set, on average, the HOPSPACKS solver took 78% lessblackbox evaluation than the NOMAD solver. So the HOPSPACK solver isroughly five time faster than the NOMAD solver to compute the optimumsolution.454.3. Results for the test problemsTable 4.3: Comparison of optimum objective function values obtained bythe HOPSPACK and NOMAD solvers to solve the test problems.RoadNameExecutionNo.Optimumcostfunctionvalue-NOMADOptimumcostfunctionvalue-HOPSPACKDifferencein theoptimumcosts (%)Test run 1 1,361 1,291 +5.2%Test run 2 1,361 1,423 -4.6%Road A Test run 3 1,361 1,418 -4.2%Test run 4 1,361 1,278 +6.1%Test run 5 1,361 1,486 -9.2%Test run 1 15,198 15,510 -2.1%Test run 2 15,198 15,141 +0.4%Road B Test run 3 15,198 15,128 +0.5%Test run 4 15,198 15,172 +0.2%Test run 5 15,198 15,529 -2.2%Test run 1 69,621 70,161 -0.8%Test run 2 69,621 70,378 -1.1%Road C Test run 3 69,621 69,995 -0.5%Test run 4 69,621 67,301 +3.3%Test run 5 69,621 67,045 +3.7%Test run 1 14,418 13,190 +8.5%Test run 2 14,418 15,154 -7.6%Road D Test run 3 14,418 14,155 +1.8%Test run 4 14,418 14,016 +2.8%Test run 5 14,418 15,384 -6.7%Test run 1 6,497 6,524 -0.4%Test run 2 6,497 6,475 +0.3%Road E Test run 3 6,497 6,497 0.0%Test run 4 6,497 6,502 -0.1%Test run 5 6,497 6,476 +0.3%464.3. Results for the test problemsTable 4.4: Overall comparison of the HOPSPACK solver and the NOMADsolver with the optimum objective function values.Tolerance ofthe differencein theoptimum costsNo. oftimes theNOMADsolver winsNo. oftimes theHOPSPACKsolver winsNo. oftimes thetwo solversties± 1% 8 7 10± 2% 7 6 12± 3% 5 5 15± 4% 5 3 17± 5% 3 3 19± 6% 3 2 20± 7% 2 1 22± 8% 1 1 23± 9% 1 0 24± 10% 0 0 25474.3. Results for the test problemsTable 4.5: Comparison of the no. of black-box evaluations required for theHOPSPACK and NOMAD solvers to solve the test problems.RoadNameExecutionNo.No. ofblack-boxevaluations-NOMADNo. ofBlack-boxevaluations-HOPSPACKDifferencein no. ofblack-boxevaluations(%)Test run 1 2,073 325 +84.3%Test run 2 2,073 336 +83.8%Road A Test run 3 2,073 697 +66.4%Test run 4 2,073 486 +76.6%Test run 5 2,073 665 +67.9%Test run 1 2,528 316 +87.5%Test run 2 2,528 309 +87.8%Road B Test run 3 2,528 286 +88.8%Test run 4 2,528 392 +88.5%Test run 5 2,528 485 +80.8%Test run 1 37,165 7,547 +79.7%Test run 2 37,165 31,418 +15.5%Road C Test run 3 37,165 3,392 +90.9%Test run 4 37,165 3,213 +91.4%Test run 5 37,165 4,661 +87.5%Test run 1 90,535 15,852 +82.5%Test run 2 90,535 19,997 +77.9%Road D Test run 3 90,535 21,194 +76.6%Test run 4 90,535 17,816 +80.3%Test run 5 90,535 21,339 +76.4%Test run 1 11,101 2,019 +81.8%Test run 2 11,101 4,332 +60.1%Road E Test run 3 11,101 1,996 +82.0%Test run 4 11,101 2,501 +77.5%Test run 5 11,101 3,120 +71.9%484.4. Summary of the result4.4 Summary of the resultUsing our advanced model developed in Chapter 3, the NOMAD solverand the HOPSPACK solver can solve all of the test problems. In our ad-vanced model, the number of variables in the optimization problem dependson the number of intersection points rather than the number of stations. Fora small non-backtracking road of 73 stations with 8 intersection points, theNOMAD solver and the HOPSPACK solver required 2,073 and 325 functioncalls, respectively. In the meanwhile, for a backtracking road of 118 stationswith 22 intersection points, the NOMAD solver and the HOPSPACK solverrequired 90535 and 15852 function calls, respectively, to solve the problem.So our advanced model can solve a reasonably large problem in a reasonablenumber of function calls.49Chapter 5Conclusion5.1 ContributionsGeometric specifications of a horizontal alignment is one of the most im-portant considerations in the road design process. In our model, a horizontalalignment is represented using the geometric specifications which are usedby engineers in practice. Thus the solution of the optimization model yieldsa practical horizontal alignment which satisfies geometric specifications andengineering requirements.In this research, we pursued a new approach to address the horizontalalignment optimization problem. While most of the studies in the liter-ature used heuristic based methods, we used derivative-free optimizationapproach. The rationale to use the derivative-free optimization approach is,it converges to a locally optimum solution. Thus our model always gives usa mathematically proven local optimum solution.It is well known that the backward bends of a horizontal alignment (i.e.,in the case of backtracking roads) might give rise to some difficulties inthe optimization process [Nic73, page 123, Chapter 5], [JSJ06, page 21,Section 2.4.3], [Par77]. Our model effectively handles backward bends ina horizontal alignment. So our model can generate both backtracking andnon-backtracking alignments.Our optimization model is a bi-level optimization problem. Our modelintegrates the vertical alignment optimization problem and the horizontalalignment optimization problem together. In our model, the cost of a hori-zontal alignment is the cost of the optimized vertical alignment which corre-sponds to that specific horizontal alignment. So our model yields a solutionwhich has not only a locally optimum horizontal alignment, but also thecorresponding optimum vertical alignment.505.2. Recommendations for future research5.2 Recommendations for future researchAlthough our proposed model works well for solving practical horizon-tal alignment optimization problems, it can be improved further for betterprecision and performance.In our model formulation, we considered that the cross sections in acorridor are fixed, which are taken corresponding to the baseline alignment.However, cross sections should be always perpendicular to a horizontal align-ment. When a horizontal alignment is significantly different from the base-line alignment, a set of new cross sections should be generated to increasethe precision before calculating the corresponding vertical road profile.A surrogate cost function is an approximation of the original cost func-tion which is cheaper to compute. Two types of surrogates can be developed:adaptive and non-adaptive surrogates. The surrogate function of an originalcost function might reduce the solution time required to get a solution. Forthe development of an adaptive surrogate cost function for our original costfunction, we are motivated by the research work done in [BDF+99]. Theydeveloped an adaptive surrogate for solving the helicopter rotor blade designproblem. The framework for optimization of expensive functions proposed in[BDF+99] can be applied to our problem effectively. We could also develop anon-adaptive surrogate cost function to accelerate the optimization process.The NOMAD solver can exploit the usage of a non-adaptive surrogate.In our model, we only consider the construction costs to formulate ourcost function. In the future, land acquisition costs could be incorporatedby considering the unit cost of a piece of land corresponding to two consec-utive cross sections in a corridor. We can also include pavement costs byconsidering the unit pavement cost between two consecutive stations.We mentioned in Chapter 4 that both solvers need an initial startingpoint. Since solutions obtained by both solvers are locally optimum, wecan use multiple starting points (i.e.; multiple initial alignments) to startthe algorithms to obtain a better solution quickly. How to choose multiplealternative good alignments in a specified corridor can be a potential futureresearch direction.The HOPSPACK solver can use a parallel computing environment ef-fectively. The resulting optimization model can be solved using the parallelversion of the HOPSPACK solver to reduce the solution time.During the optimization process, at each iteration, both of the deriva-tive free optimization solvers solve a large number of vertical alignmentoptimization problems (i.e., a large scale mixed linear programming (MILP)problem). At the earlier stage of the optimization process (i.e., when the515.2. Recommendations for future researchmesh size is coarse) we can relax some of the parameters of the vertical align-ment optimization problem to get an approximation cost to go forward andthen at the later stage (i.e., when the mesh size becomes relatively small) wecan again tight the parameters to get the accurate costs. This policy mightreduce the solution time significantly. We can also use a warm start of thevertical alignment optimization problem when the horizontal alignments areclose to each other to accelerate the vertical alignment optimization process.So the interconnection between the derivative free optimization solver andthe MILP solver can be a potential way to reduce the solution time.52Bibliography[AAS04] AASHTO. A policy on geometric design of highways andstreets, 2004. American Association of State Highway andTransportation Officials. → pages 5[AC73] G. C. Athanassoulis and V. Calogero. Optimal location of anew highway from A to B: a computer technique for routeplanning. In PTRC Seminar Proceedings on Cost Models &Optimization in Highway, 1973. → pages 9[AD06] C. Audet and J. E. Dennis, Jr. Mesh adaptive direct searchalgorithms for constrained optimization. SIAM Journal onOptimization, 17(1):188–217, 2006. → pages 16, 42[Aka06] A. Akay. Minimizing total costs of forest roads with comput-eraided design model. Sadhana, 31(5):621–633, 2006. → pages10[ALT09] C. Audet, S. Le Digabel, and C. Tribes. NOMAD user guide.Technical Report G-2009-37, Les cahiers du GERAD, 2009. →pages 41, 42[Aru05] K. Aruga. Tabu search optimization of horizontal and verticalalignments of forest roads. Journal of Forest Research, 10:275–284, 2005. → pages 10[BDE10] BDE. Bureau of design and environment manual, 2010. IllinoisDepartment of Transportation, USA. → pages 4[BDF+99] A. J. Booker, Jr. Dennis, J. E., P. D. Frank, D. B. Serafini,V. Torczon, and M. W. Trosset. A rigorous framework foroptimization of expensive functions by surrogates. Structuraloptimization, 17(1):1–13, 1999. → pages 51[Byr47] O. Byrne. The First Six Books of the Elements of Euclid.William Pickering, London,UK, 1847. → pages 2353Bibliography[CGF89] E. P. Chew, C. J. Goh, and T. F. Fwa. Simultaneous opti-mization of horizontal and vertical alignments for highways.Transportation Research Part B: Methodological, 23(5):315–329, 1989. → pages 3, 10, 11[CL06] J. Cheng and Y. Lee. Model for three-dimensional high-way alignment. Journal of Transportation Engineering,132(12):913–920, 2006. → pages 11[DAAMP06] J. Dunlavy, A. Akuoko-Asibey, R. Masse, and D. Pilon. Ananalysis of the transportation industry in 2005. Technical re-port, Statistics Canada, 2006. → pages 1[Eas88] S. M. Easa. Selection of roadway grades that minimize earth-work cost using linear programming. Transportation ResearchPart A: General, 22(2):121 – 136, 1988. → pages 8[Fwa89] T. F. Fwa. Highway vertical alignment analysis by dy-namic programming. Transportation Research Record, 1239:1–9, 1989. → pages 7[GCF88] C. J. Goh, E. P. Chew, and T. F. Fwa. Discrete and con-tinuous models for computation of optimal vertical highwayalignment. Transportation Research Part B: Methodological,22(6):399–409, 1988. → pages 7[GK06] G. A. Gray and T. G. Kolda. Algorithm 856: APPSPACK4.0: Asynchronous parallel pattern search for derivative-freeoptimization. ACM Transactions on Mathematical Software,32(3):485–507, September 2006. → pages 42[GLA05] A. B. Goktepe, A. H. Lav, and S. Altun. Dynamic optimizationalgorithm for vertical alignment of highways. Mathematicaland Computational Applications, 10:341–350, 2005. → pages7[Hay70] R. W. Hayman. Optimization of vertical alignment for high-ways through mathematical programming. Highway ResearchRecord, pages 1–9, 1970. → pages 7[HBS68] B. E. Howard, Z. Bramnick, and J. F. Shaw. Optimum curva-ture principle in highway routing. In Proceeding of the Amer-ican Society of Civil Engineers, volume 94, pages 61–82, 1968.→ pages 954Bibliography[HHLM11] D. Hare, W. Hare, Y. Lucet, and S. Mehrotra. An arc-flowmodel for earthwork operations. Technical report, (undis-closed), 2011. → pages 8[HHLR14] W. Hare, S. 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 8, 16, 27[HKL11] W. L. 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 8[Hog73] J. D. Hogan. Exprience with OPTLOC - optimum locationof highways by computer. In PTRC Seminer Proceddings onCost Models and Optimisation in Highways, 1973. → pages 10[Hua73] J. P. Huarte. Opygar: Optimization and automatic designof highway profiles. In PTRC Seminar Proceedings on CostModels and Optimization in Highways, 1973. → pages 7[Jha03] M. K. Jha. Criteria-based decision support system for selectinghighway alignments. Journal of Transportation Engineering,129(1):33–41, 2003. → pages 11[JJS00] J.-C. Jong, M. K. Jha, and P. Schonfeld. Preliminary high-way design with genetic algorithms and geographic informa-tion system. Computer Aided Civil Infrastructure Engineering,15(4):261–271, 2000. → pages 10[JK06] M. K. Jha and E. Kim. Highway route optimization basedon accessibility, proximity, and land-use changes. Journal ofTransportation Engineering, 132:435–439, 2006. → pages 11[Jon98] J.-C. Jong. Optimizing highway alignments with genetic al-gorithms. PhD thesis, University of Maryland, College Park,1998. → pages 10[JS03] J.-C. Jong and P. Schonfeld. An evolutionary model for si-multaneously optimizing 3d highway alignments. Tranporta-tion Research, Part B: Methodology, 37B(2):107–128, 2003. →pages 1155Bibliography[JSJ06] M. K. Jha, P. Schonfeld, and J.-C. Jong. Intelligent RoadDesign, volume 19. WIT Press, 2006. → pages 2, 3, 7, 8, 9,10, 50[KL10] V. R. Koch and Y. Lucet. A note on: Spline technique formodeling roadway profile to minimize earthwork cost. Journalof Industrial and Management Optimization, 6(2):393 – 400,2010. → pages 8[Kol05] T. G. Kolda. Revisiting asynchronous parallel pattern searchfor nonlinear optimization. SIAM Journal on Optimization,16(2):563–586, 2005. → pages 42[LD11] S. Le Digabel. Algorithm 909: Nomad: Nonlinear optimizationwith the mads algorithm. ACM Transactions on MathematicalSoftware, 37(4):44:1–44:15, 2011. → pages 16, 19[LTL09] Y. Lee, Y. Tsou, and H. Liu. Optimization method for high-way horizontal alignment design. Journal of TransportationEngineering, 135(4):217–224, 2009. → pages 10[MA04] A. A. Moreb and M. S. Aljohani. Quadratic representationfor roadway profile that minimizes earthwork cost. Journalof Systems Science and Systems Engineering, 13(2):245–252,2004. → pages 8[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. → pages8[Mor09] A. A. Moreb. Spline technique for modeling roadway profileto minimize earthwork cost. Journal of Industrial and Man-agement Optimization (JIMO), 5(2):275–283, 2009. → pages8[MS81] R. H. Mayer and R. M. Stark. Earthmoving logistics. Journalof the Construction Division, 107(2):297–312, 1981. → pages7[Mur73] J. D. Murchland. Methods of vertical profile optimisation foran improvement to an existing road. In PTRC Seminar Pro-ceedings on Cost Models and Optimisation in Highways, 1973.→ pages 756Bibliography[NEW76] A. J. Nicholson, D.G. Elms, and A. Williman. A variationalapproach to optimal route location. Highway Engineers, 23:22–25, 1976. → pages 10[Nic73] A. J. Nicholson. A variational approch to optimal route loca-tion. PhD thesis, University of Canterbury, 1973. → pages 10,50[OEC73] OECD. Optimisation of road alignment by the use of com-puters, 1973. Organisation for Economic Co-operation andDevelopment (Road Research Group), Paris. → pages 3, 10[Par77] N. A. Parker. Rural highway route corridor selection. Trans-portation Planning and Technology, 3(4):247–256, 1977. →pages 9, 10, 50[Pea73] A. D. Pearman. Investigation of the objective function in prob-lems of optimising highway vertical alignment. In PTRC Sem-inar Proceedings Cost Models and Optimisation in Highways,1973. → pages 7[Pla09] T. D. Plantenga. HOPSPACK 2.0 user manual. TechnicalReport SAND2009-6265, Sandia National Laboratories, Al-buqerque, NM and Livermore, CA, October 2009. → pages41, 42[Rah12] F. Rahman. Optimizing the vertical alignment under earth-work block removal constraints in road construction. Master’sthesis, The University of British Columbia, 2012. → pages 7,8[Rob73] R. Robinson. Automatic design of the road vertical alignment.In PTRC Seminar Proceedings on Cost Models and Optimiza-tion in Highways, 1973. → pages 7[RS13] L. M. Rios and N. V. Sahinidis. Derivative-free optimization: areview of algorithms and comparison of software implementa-tions. Journal of Global Optimization, 56(3):1247–1293, 2013.→ pages 16[SH81] J. F. B. Shaw and B. E. Howard. Comparison of two integra-tion methods in transportation routing. Transportation Re-search Record, pages 8–3, 1981. → pages 957Bibliography[SH82] J. F. B. Shaw and B. E. Howard. Expressway route optimiza-tion by OCP. Transportation Engineering Journal, 108:227–243, 1982. → pages 9[TM71] A. K. Turner and R. D. Miles. The gcars system: A computerassisted method of regional route location. Highway ResearchRecord, pages 1–15, 1971. → pages 9[Tri87a] D. Trietsch. Comprehensive design of highway networks. Tran-portation Science, 21(1):1, 1987. → pages 9[Tri87b] D. Trietsch. A family of methods for preliminary highwayalignment. Transportation Science, 21(1):17–25, 1987. →pages 9[TT03] C. W. Tat and F. Tao. Using GIS and genetic algorithm inhighway alignment optimization. In Intelligent TransportationSystems, volume 2, pages 1563–1567, 2003. → pages 10[Tur78] A. K. Turner. A decade of experience in computer aided routeselection. Photogrammetric Engineering and Remote Sensing,pages 1561–1576, 1978. → pages 9[Wan95] F. Y. M. Wan. Introduction to the calculus of variations andits applications. Chapman & Hal, 1995. → pages 858Appendix59Appendix ATablesA.1 Results for basic modelThe numerical experiments were performed on the five different roads.Tables A.1, A.2, A.3, A.4, and A.5 list the computational data for fivedifferent input files (i.e., different roads). “ * ” indicates the problem cannotbe solved in 3 hours.Table A.1: Computational Experience (Hart Rd Small.csv)# of sta-tion# ofFun. call# of itr. Wall-clockTimeMemory(in Min) (in Mb)5 509 53 1.8 0.1010 1,256 70 5.6 0.3515 1,998 81 11.9 0.7320 3,517 1,119 21.0 1.5625 4,734 131 29.7 2.4830 6,702 175 53.4 4.0935 8,011 173 57.3 5.5640 11,213 211 91.7 8.5745 16,413 285 137.9 13.8650 16,182 257 149.8 14.7860A.1. Results for basic modelTable A.2: Computational Experience (Diamond Road align-1.csv)# of sta-tion# ofFun. call# of itr. Wall-clockTimeMemory(in Min) (in Mb)5 600 73 2.5 0.1110 1,318 81 6.4 0.3715 2,169 89 12.4 0.7920 3,119 105 20.4 1.3925 4,286 111 34.5 2.2430 13,391 307 111.5 8.2935 7,329 147 63.3 5.0240 * * * *45 * * * *50 * * * *Table A.3: Computational Experience (Diamond Road align-2.csv)# of sta-tion# ofFun. call# of itr. Wall-clockTimeMemory(in Min) (in Mb)5 2,810 359 13.8 0.5710 1,787 107 7.7 0.5015 2,715 117 16.0 0.9820 3,690 115 28.0 1.6025 5,424 147 42.6 2.8730 20,032 447 177.3 12.6035 * * * *40 10,146 100.7 6,047 7.7045 * * * *50 * * * *61A.2. Optimized alignments of the test problemsTable A.4: Computational Experience (bluff road.csv)# of sta-tion# ofFun. call# of itr. Wall-clockTimeMemory(in Min) (in Mb)5 718 359 3.4 0.1410 10,980 107 66.2 3.1715 * * * *20 6,207 207 38.9 2.7425 9,281 275 66.6 4.8730 17,141 407 146.3 10.6035 * * * *40 * * * *45 * * * *50 * * * *Table A.5: Computational Experience (spur 3 demo.csv)# of sta-tion# ofFun. call# of itr. Wall-clockTimeMemory(in Min) (in Mb)5 728 83 3.4 0.1410 1,727 101 8.2 0.4815 3,099 127 19.3 1.1220 19,268 627 144.1 8.7925 6,987 189 50.0 3.6130 10,609 245 85.5 6.4135 13,625 285 121.21 9.3440 * * * *45 * * * *50 * * * *A.2 Optimized alignments of the test problemsThe minimizer of the optimization problems ( developed using the modeldescribed in Chapter 3) are listed in Tables A.6, A.7, A.8, A.9, and A.10.62A.2. Optimized alignments of the test problemsTableA.6:TheoptimalalignmentsoftheRoadAobtainedbytheNOMADandHOPSPACKsolvers.Spec.InitialalignmentOpt.align.-NOMADOpt.align.-HOPSPACK(run1)Opt.align.-HOPSPACK(run2)Opt.align.-HOPSPACK(run3)Opt.align.-HOPSPACK(run4)Opt.align.-HOPSPACK(run5)IP1-x9,747.369,747.369,747.369,747.369,747.369,747.369,747.36IP1-y4,737.744,737.744,737.744,737.744,737.744,737.744,737.74IP1-r0.,552.889,564.899,558.899,557.249,562.799,555.899,557.09IP2-y4,739.694,742.694,738.194,739.694,739.694,738.194,738.49IP2-r50.0050.0062.5050.00150.0062.5055.00IP3-x9,578.339,578.429,587.339,578.339,584.339,579.839,583.13IP3-y4,747.114,747.114,747.114,744.114,741.864,741.864,745.91IP3-r75.0075.0075.0050.0050.0050.0087.50IP4-x9,644.029,644.039,650.039,644.039,638.639,634.439,647.03IP4-y4,797.374,797.474,803.384,803.384,803.384,809.384,806.23IP4-r100.00100.0050.0050.0050.0050.0062.50IP5-x9,712.349,706.349,712.349,712.349,706.349,706.349,703.34IP5-y4,804.994,808.004,805.004,803.384,802.004,796.004,805.60IP5-r60.0060.0050.0050.0050.0050.0050.00IP6-x9,770.369,758.469,764.379,764.379,770.379,764.379,764.37IP6-y4,890.324,884.324,905.324,905.324,908.924,894.824,899.32IP6-r100.00100.00100.0050.0050.0050.0050.00IP7-x9,822.999,793.009,823.009,820.009,811.009,811.009,821.20IP7-y4,918.134,924.134,930.134,915.134,918.134,936.134,915.13IP7-r75.0075.0050.0050.00135.0050.0050.00IP8-x9,835.239,835.239,835.239,835.239,835.239,835.239,835.23IP8-y4,931.894,931.894,931.894,931.894,931.894,931.894,931.89IP8-r0. Optimized alignments of the test problemsTableA.7:TheoptimalalignmentsoftheRoadBobtainedbytheNOMADandHOPSPACKsolvers.Spec.InitialalignmentOpt.align.-NOMADOpt.align.-HOPSPACK(run1)Opt.align.-HOPSPACK(run2)Opt.align.-HOPSPACK(run3)Opt.align.-HOPSPACK(run4)Opt.align.-HOPSPACK(run5)IP1-x392,201.60392,201.60392,201.60392,201.60392,201.60392,201.60392,201.60IP1-y6,983,091.876,983,091.876,983,091.876,983,091.876,983,091.876,983,091.876,983,091.87IP1-r0.,282.65392,314.00392,313.00392,325.00392,313.00392,283.00392,313.00IP2-y6,983,568.996,983,620.006,983,680.006,983,630.006,983,610.006,983,530.006,983,680.00IP2-r200.004,751.103,800.002,800.004,650.003,200.003,800.00IP3-x392,923.43392,891.00392,923.00392,890.00392,893.00392,893.00392,923.00IP3-y6,984,840.696,984,860.006,984,840.006,984,860.006,984,860.006,984,870.006,984,840.00IP3-r2,000.00583.741,700.00900.001,200.00500.002,500.00IP4-x393,378.71393,370.00393,409.00393,409.00393,409.00393,379.00393,379.00IP4-y6,985,977.546,985,840.006,986,010.006,985,960.006,985,960.006,985,870.006,985,940.00IP4-r2,000.004,967.774,500.003,600.003,500.004,650.004,450.00IP5-x393,495.89393,495.89393,495.89393,495.89393,495.89393,495.89393,495.89IP5-y6,986,433.996,986,433.996,986,433.996,986,433.996,986,433.996,986,433.996,986,433.99IP5-r0. Optimized alignments of the test problemsTableA.8:TheoptimalalignmentsoftheRoadCobtainedbytheNOMADandHOPSPACKsolvers.Spec.InitialalignmentOpt.align.-NOMADOpt.align.-HOPSPACK(run1)Opt.align.-HOPSPACK(run2)Opt.align.-HOPSPACK(run3)Opt.align.-HOPSPACK(run4)Opt.align.-HOPSPACK(run5)IP1-x405,181.86405,181.86405,181.86405,181.86405,181.86405,181.86405,181.86IP1-y7,016,733.127,016,733.127,016,733.127,016,733.127,016,733.127,016,733.127,016,733.12IP1-r0.,446.69405,494.00405,484.00405,466.00405,447.00405,454.00405,472.00IP2-y7,016,896.667,016,930.007,016,930.007,016,910.007,016,90.007,016,900.007,016,920.00IP2-r500.00200.00200.00200.00200.00200.00200.00IP3-x405,721.39405,716.00405,723.00405,751.00405,706.00405,706.00405,714.00IP3-y7,017,215.307,017,190.007,017,200.007,017,250.007,017,200.007,017,160.007,017,170.00IP3-r500.00200.006,680.0024,130.0011,600.003,355.003,895.00IP4-x405,941.14405,939.00405,977.00405,949.00405,956.00405,971.00405,956.00IP4-y7,017,573.027,017,510.007,017,540.007,017,480.007,017,480.007,017,550.007,017,530.00IP4-r500.00200.00200.001,915.001,840.00200.00700.00IP5-x406,182.87406,194.00406,153.00406,147.00406,150.00406,153.00406,153.00IP5-y7,017,925.857,017,890.007,017,910.007,017,890.007,017,910.007,017,900.007,017,900.00IP5-r500.00200.00480.00380.00455.00450.00450.00IP6-x406,363.56406,354.00406,358.00406,361.00406,358.00406,364.00406,364.00IP6-y7,018,063.807,018,020.007,018,020.007,018,030.007,018,020.007,018,030.007,018,030.00IP6-r500.00200.00200.00200.00200.00200.00200.00IP7-x406,498.87406,470.00406,466.00406,469.00406,469.00406,466.00406,469.00IP7-y7,018,292.857,018,310.007,018,310.007,018,320.007,018,320.007,018,310.007,018,320.00IP7-r200.00200.00200.00200.00200.00200.00200.00IP8-x406,356.24406,362.00406,359.00406,359.00406,359.00406,359.00406,362.00IP8-y7,018,576.577,018,550.007,018,550.007,018,550.007,018,550.007,018,550.007,018,540.00IP8-r500.00200.00200.00200.00200.00200.00200.00IP9-x406,282.98406,325.00406,328.00406,326.00406,328.00406,326.00406,326.00IP9-y7,018,963.587,018,970.007,018,970.007,018,970.007,018,970.007,018,980.007,018,970.00IP9-r200.00200.00200.00200.00200.00200.00200.00IP10-x406,390.42406,383.00406,383.00406,387.00406,383.00406,360.00406,371.00IP10-y7,019,157.707,019,170.007,019,170.007,019,180.007,019,160.007,019,070.007,019,120.00IP10-r500.00200.00250.00240.00200.00320.00200.00IP11-x406,407.51406,351.00406,390.00406,379.00406,348.00406,376.00406,364.00IP11-y7,019,372.577,019,390.007,019,370.007,019,290.007,019,380.007,019,460.007,019,450.00IP11-r500.00200.00780.00310.00400.00260.00330.00IP12-x406,639.48406,700.00406,687.00406,678.00406,669.00406,719.00406,719.00IP12-y7,020,074.577,020,020.007,020,090.007,020,100.007,020,140.007,019,940.007,019,920.00IP12-r500.00500.00200.00200.00200.001,100.001,075.00IP13-x406,581.99406,582.00406,582.00406,582.00406,582.00406,582.00406,582.00IP13-y7,020,629.057,020,620.007,020,620.007,020,620.007,020,620.007,020,630.007,020,620.00IP13-r200.00200.00200.00200.00200.00200.00200.00IP14-x406,997.27406,997.27406,997.27406,997.27406,997.27406,997.27406,997.27IP14-y7,021,135.647,021,135.647,021,135.647,021,135.647,021,135.647,021,135.647,021,135.64IP14-r0. Optimized alignments of the test problemsTableA.9:TheoptimalalignmentsoftheRoadDobtainedbytheNOMADandHOPSPACKsolvers.Spec.InitialalignmentOpt.align.-NOMADOpt.align.-HOPSPACK(run1)Opt.align.-HOPSPACK(run2)Opt.align.-HOPSPACK(run3)Opt.align.-HOPSPACK(run4)Opt.align.-HOPSPACK(run5)IP1-x859,962.73859,962.73859,962.73405,181.86405,181.86405,181.86405,181.86IP1-y628,627.91628,627.91628,627.917,016,733.127,016,733.127,016,733.127,016,733.12IP1-r0.,930.76859,937.00859,937.00859,961.00859,918.00859,927.00859,961.00IP2-y628,612.74628,643.00628,643.00628,605.00628,633.00628,637.00628,604.00IP2-r25.0025.0025.0025.0025.0025.0025.00IP3-x859,874.81859,866.00859,867.00859,858.00859,872.00859,868.00859,849.00IP3-y628,605.96628,576.00628,578.00628,599.00628,576.00628,576.00628,601.00IP3-r90.0025.0025.0025.0025.0025.0045.00IP4-x859,822.25859,831.00859,822.00859,820.00859,827.00859,826.00859,822.00IP4-y628,629.40628,638.00628,649.00628,641.00628,637.00628,641.00628,642.00IP4-r60.0025.0025.0025.0025.0025.0025.00IP5-x859,773.55859,782.00859,787.00859,789.00859,790.00859,780.00859,788.00IP5-y628,618.10628,636.00628,625.00628,624.00628,630.00628,633.00628,625.00IP5-r60.0060.0025.0025.0048.0025.0025.00IP6-x859,696.78859,676.00859,698.00859,702.00859,699.00859,674.00859,701.00IP6-y628,659.71628,650.00628,681.00628,690.00628,681.00628,651.00628,690.00IP6-r90.0025.0092.5099.00115.0025.00101.50IP7-x859,627.65859,631.00859,632.00859,629.00859,629.00859,629.00859,629.00IP7-y628,620.61628,612.00628,613.00628,614.00628,612.00628,612.00628,613.00IP7-r25.0025.0025.0025.0025.0025.0025.00IP8-x859,505.79859,503.00859,500.00859,499.00859,500.00859,499.00859,499.00IP8-y628,614.11628,607.00628,608.00628,609.00628,608.00628,608.00628,609.00IP8-r25.0025.0025.0025.0025.0025.0025.00IP9-x859,466.24859,463.00859,468.00859,470.00859,468.00859,470.00859,471.00IP9-y628579.36628,574.00628,574.00628,576.00628,573.00628,575.00628,577.00IP9-r25.0025.0096.2593.7597.5090.0090.00IP10-x859,404.57859,412.00859,414.00859,412.00859,414.00859,414.00859,412.00IP10-y628,565.11628,563.00628,565.00628,565.00628,565.00628,565.00628,565.00IP10-r25.0025.0025.0025.0027.5027.5025.00IP11-x859,343.95859,346.00859,351.00859,360.00859,347.00859,348.00859,359.00IP11-y628553.75628,534.00628,537.00628,543.00628,535.00628,535.00628,543.00IP11-r25.0025.0025.0025.0025.0025.0025.00IP12-x859,305.28859,315.00859,312.00859,277.00859,316.00859,313.00859,281.00IP12-y628,557.69628,556.00628,556.00628,560.00628,556.00628,558.00628,559.00IP12-r25.0025.0025.0025.0025.0028.7525.00IP13-x859,273.63859,267.00859,270.00859,265.00859,269.00859,268.00859,266.00IP13-y628573.70628,550.00628,550.00628,571.00628,551.00628,548.00628,566.00IP13-r25.0025.0025.0025.0025.0025.0025.00IP14-x859,255.50859,263.00859,262.00859,262.00859,262.00859,263.00859,263.00IP14-y628,585.89628,598.00628,590.00628,601.00628,595.00628,590.00628,587.00IP14-r25.0025.0055.0025.0038.7525.0042.50continuetonextpage66A.2. Optimized alignments of the test problemscontinuefrompreviouspageSpec.InitialalignmentOpt.align.-NOMADOpt.align.-HOPSPACK(run1)Opt.align.-HOPSPACK(run2)Opt.align.-HOPSPACK(run3)Opt.align.-HOPSPACK(run4)Opt.align.-HOPSPACK(run5)IP15-x859,258.87859272.00859,277.00859,271.00859,271.00859,271.00859,266.00IP15-y628,622.27628,613.00628,634.00628,612.00628,610.00628,624.00628,604.00IP15-r25.0025.0062.5068.7525.0025.0032.50IP16-x859,312.40859,292.00859,300.00859,294.00859,289.00859,294.00859,295.00IP16-y628,630.18628,648.00628,649.00628,650.00628,648.00628,648.00628,650.00IP16-r25.0025.0025.0037.5037.5038.7535.00IP17-x859,370.11859,368.00859,361.00859,358.00859,362.00859,371.00859,361.00IP17-y628,640.65628,656.00628,655.00628,653.00628,655.00628,657.00628,653.00IP17-r90.0025.0025.0025.0025.0025.0025.00IP18-x859,400.45859,405.00859,392.00859,391.00859,393.00859,397.00859,396.00IP18-y628,690.04628,720.00628,694.00628,695.00628,699.00628,720.00628,697.00IP18-r25.0025.0056.2536.2525.00203.12561.25IP19-x859,440.98859,469.00859,429.00859,430.00859,425.00859,452.00859,429.00IP19-y628,757.15628,772.00628,757.00628,759.00628,758.00628,763.00628,756.00IP19-r25.0025.0025.0025.0025.0025.0025.00IP20-x859,472.96859,449.00859,489.00859,496.00859,461.00859,473.00859,488.00IP20-y628,811.20628,799.00628,782.00628,781.00628,800.00628,807.00628,781.00IP20-r50.0025.0025.0025.0050.0032.5025.00IP21-x859,418.43859,410.00859,414.00859,404.00859,412.00859,415.00859,415.00IP21-y628,848.14628,832.00628,827.00628,830.00628,837.00628,822.00628,826.00IP21-r25.0025.0025.0063.7525.0025.0025.00IP22-x859,404.20859,404.20859,404.20859,404.20859,404.20859,404.20859,404.20IP22-y628,868.81628,868.81628,868.81628,868.81628,868.81628,868.81628,868.81IP22-r0. Optimized alignments of the test problemsTableA.10:TheoptimalalignmentsoftheRoadEobtainedbytheNOMADandHOPSPACKsolvers.Spec.InitialalignmentOpt.align.-NOMADOpt.align.-HOPSPACK(run1)Opt.align.-HOPSPACK(run2)Opt.align.-HOPSPACK(run3)Opt.align.-HOPSPACK(run4)Opt.align.-HOPSPACK(run5)IP1-x860,254.98859,962.73859,962.73859,962.73859,962.73859,962.73859,962.73IP1-y628,612.83628,627.91628,627.91628,627.91628,627.91628,627.91628,627.91IP1-r0.,219.54860,207.00860,202.00860,203.00860,202.00860,202.00860,202.00IP2-y628,747.01628,777.00628,788.00628,788.00628,788.00628,788.00628,788.00IP2-r50.0050.0050.0050.0050.0050.0050.00IP3-x860,179.37860,179.00859,866.00860,179.00860,179.00860,179.00860,179.00IP3-y628,809.75628,817.00628,811.00628,813.00628,812.00628,811.00628,812.00IP3-r50.0050.0050.0050.0050.0050.0050.00IP4-x860177.93860,180.00860,178.00860,178.00860,178.00860,178.00860,178.00IP4-y628,861.00628,856.00628,849.00628,858.00628,854.00628,849.00628,865.00IP4-r50.0050.00117.50170.00100.00102.50110.0IP5-x860,181.57860,190.00860,182.00860,188.00860,188.00860,182.00860,188.00IP5-y628,896.38628,897.00628,878.00628,893.00628,896.00628,878.00628,892.00IP5-r50.0050.00220.00112.5050.00235.00122.50IP6-x860199.29860,204.00860,199.00860,205.00860,199.00860,199.00860,205.00IP6-y628,959.03628,967.00628,935.00628,971.00628,935.00628,935.00628,973.00IP6-r50.0050.00330.00198.75320.00312.50205.0IP7-x860,181.57860,203.00860,206.00860,202.00860206.00860206.00860203.00IP7-y629059.67629,050.00629,030.00629,028.00629,036.00629,039.00629,029.00IP7-r50.0050.00665.00237.50412.50340.0247.50IP8-x860,225.87860,230.00860,226.00860,227.00860,227.00860,227.00860,227.00IP8-y629,164.10629,159.00629,164.00629,163.00629,163.00629,163.00629,163.00IP8-r50.0050.0050.0050.0050.0050.0050.00IP9-x860,146.12860,146.12860,146.12860,146.12860,146.12860,146.12860,146.12IP9-y629,280.56629,280.56629,280.56629,280.56629,280.56629,280.56629,280.56IP9-r0. BFigures3.923.9223.9243.9263.9283.933.9323.9343.936x 1056.9836.98356.9846.98456.9856.98556.9866.9865x 106XY  Initial Alignment (Cost: $ 17036.2)Optimized Alignment−NOMAD (Cost: $ 15198.8)Optimized Alignment−HOPSPACK (Cost: $ 15128)Figure B.1: Optimum alignments of the Road B obtained by the NOMADsolver and the HOPSPACK solver.69Appendix B. Figures4.054.0554.064.0654.074.075x 1057.01657.0177.01757.0187.01857.0197.01957.027.02057.0217.0215x 106XY  Initial Alignment (Cost: $ 87856.6)Optimized Alignment−NOMAD (Cost: $ 69621)Optimized Alignment−HOPSPACK (Cost: $ 67045.6)Figure B.2: Optimum alignments of the Road C obtained by the NOMADsolver and the HOPSPACK solver.70Appendix B. Figures8.6018.60158.6028.60258.6038.6035x 1056.2866.2876.2886.2896.296.2916.2926.2936.294x 105XY  Initial Alignment (Cost: $ 8288.11)Optimized Alignment−NOMAD (Cost: $ 6497.96)Optimized Alignment−HOPSPACK (Cost: $ 6475.84)Figure B.3: Optimum alignments of the Road E obtained by the NOMADsolver and the HOPSPACK solver.71


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items