Arts and Sciences, Irving K. Barber School of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Amirsadri, Shima
Master of Science - MSc
University of British Columbia
Vertical Alignment (VA) optimization refers to the problem of finding the minimum cost of earthwork while satisfying VA design constraints. Even though we have many VA methods, there is no software or program to automatically check whether their output is as expected or not. In this thesis, we introduce a software package, called ROADENTS (ROAd DEsigN Testing Software), that can validate the output of a VA technique on simple quadratic artificial roads. Here, we test the output of Quasi Network Flow (QNF), Multi-haul Quasi Network Flow (MQNF) and Softree API (V2) using ROADENTS. Moreover, generating ground profiles with different characteristics can be a painstaking task, especially when we have to build a myriad of ground profiles. To tackle this problem, we incorporate a software component in ROADENTS that can produce different types of ground profiles, ranging from single-segment to sophisticated multi-segment ground profiles. Using this, researchers can generate thousands of quadratic ground profiles in just a few seconds. ROADENTS is not only a VA model checker or a ground profile generator, but also a VA visualizer, and a .CSV area converter. In the road design world, every VA model accepts a ground profile in a different format. Utilizing ROADENTS, users can convert the format of the ground profiles into the desired format very quickly and efficiently.
ROADENTS (ROAd DEsigN Testing Software)byShima AmirsadriB.Sc., Islamic Azad University, 2008M.Sc., University of Kashan, 2014A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe College of Graduate Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)October 2019© Shima Amirsadri, 2019The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:ROADENTS (ROAd DEsigN Testing Software)submitted by Shima Amirsadri in partial fulfilment of the requirements of thedegree of Master of ScienceDr. Yves Lucet, Irving K. Barber School of Arts and ScienceSupervisorDr. Warren Hare, Irving K. Barber School of Arts and ScienceCo-supervisorDr. Solomon Tesfamariam, School of EngineeringSupervisory Committee MemberDr. Gordon Lovegrove, School of EngineeringUniversity ExamineriiAbstractVertical Alignment (VA) optimization refers to the problem of findingthe minimum cost of earthwork while satisfying VA design constraints. Eventhough we have many VA methods, there is no software or program toautomatically check whether their output is as expected or not. In thisthesis, we introduce a software package, called Roadents (ROAd DEsigNTesting Software), that can validate the output of a VA technique on simplequadratic artificial roads. Here, we test the output of Quasi Network Flow(QNF), Multi-haul Quasi Network Flow (MQNF) and Softree API (V2)using Roadents.Moreover, generating ground profiles with different characteristics canbe a painstaking task, especially when we have to build a myriad of groundprofiles. To tackle this problem, we incorporate a software component inRoadents that can produce different types of ground profiles, ranging fromsingle-segment to sophisticated multi-segment ground profiles. Using this,researchers can generate thousands of quadratic ground profiles in just a fewseconds.Roadents is not only a VA model checker or a ground profile genera-tor, but also a VA visualizer, and a .CSV area converter. In the road designworld, every VA model accepts a ground profile in a different format. Uti-lizing Roadents users can convert the format of the ground profiles intothe desired format very quickly and efficiently.iiiLay SummaryWe introduce a software package that is a ground profile generator, a ver-tical alignment checker, a vertical alignment visualizer and a .CSV area fileconverter. Using this software, researchers can generate numerous verticalalignments with different characteristics easily and efficiently. Furthermore,using the vertical alignment evaluator component of Roadents, researcherscan make sure that the output spline of their models is as expected.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Supplementary Materials . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Road design optimization . . . . . . . . . . . . . . . . . . . . 11.1.1 Earthwork optimization . . . . . . . . . . . . . . . . . 21.1.2 Horizontal alignment optimization . . . . . . . . . . . 31.1.3 Vertical alignment optimization . . . . . . . . . . . . . 31.2 The quasi-network-flow model for vertical alignment . . . . . 51.2.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . 51.2.2 The model description . . . . . . . . . . . . . . . . . . 61.3 Multi-haul quasi-network-flow (MQNF) model . . . . . . . . . 101.4 Softree API® . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5 Organization of this thesis . . . . . . . . . . . . . . . . . . . . 10Chapter 2: ROADENTS: ROAd DEsigN Testing Software . . 122.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Software Components . . . . . . . . . . . . . . . . . . . . . . 14vTABLE OF CONTENTS2.2.1 Ground Profile Generator . . . . . . . . . . . . . . . . 152.2.2 Configuration Settings . . . . . . . . . . . . . . . . . . 192.2.3 .CSV Converter . . . . . . . . . . . . . . . . . . . . . . 232.2.4 Road Visualizer . . . . . . . . . . . . . . . . . . . . . . 242.2.5 Micro-service architecture for VA evaluation . . . . . . 25Chapter 3: Linear and quadratic ground profiles . . . . . . . . 283.1 Real-world ground profiles . . . . . . . . . . . . . . . . . . . . 283.2 Linear ground profiles . . . . . . . . . . . . . . . . . . . . . . 303.2.1 Analyzing the horizontal ground profiles . . . . . . . . 313.2.2 Analyzing the slanted ground profiles . . . . . . . . . 333.3 Quadratic ground profiles . . . . . . . . . . . . . . . . . . . . 343.4 Finding the optimal vertical alignment for quadratic groundprofiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.4.1 Finding the optimal vertical alignment - simplifiedversion . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Chapter 4: Spline ground profiles . . . . . . . . . . . . . . . . . 474.1 Summary of the results for spline ground profiles . . . . . . . 57Chapter 5: Numerical Experimentation . . . . . . . . . . . . . 585.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59Chapter 6: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 60Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62viList of TablesTable 5.1 The average and standard deviations of (Diff1−Diff2) 59viiList of FiguresFigure 1.1 The high-level overview of dealing with the road de-sign problem . . . . . . . . . . . . . . . . . . . . . . . 2Figure 1.2 Different stages of Earthwork optimization . . . . . . 2Figure 1.3 A three dimensional alignment [20] . . . . . . . . . . 6Figure 1.4 A typical section i of the QNF graph at time-step t . 7Figure 1.5 The slope constraints for the gth segment . . . . . . . 9Figure 2.1 The main components of the proposed software . . . 14Figure 2.2 The main window of Roadents . . . . . . . . . . . . 14Figure 2.3 The single ground profile generator . . . . . . . . . . 16Figure 2.4 The advanced ground profile generator . . . . . . . . 17Figure 2.5 The multi ground profile generator . . . . . . . . . . . 19Figure 2.6 The configuration settings . . . . . . . . . . . . . . . 20Figure 2.7 The .CSV converter . . . . . . . . . . . . . . . . . . . 23Figure 2.8 The road visualizer . . . . . . . . . . . . . . . . . . . 24Figure 2.9 The micro-service-based design of Roadents . . . . . 25Figure 2.10 VA Evaluator components . . . . . . . . . . . . . . . 26Figure 3.1 The output of the single-haul, multi-haul models, andthe Softree API for the real-world Flat ground profile. 29Figure 3.2 The station view of the flat ground profile with ditcheson the edges obtained from Softree Location software 30Figure 3.3 The output of the single-haul, multi-haul, and Softreemodels for the horizontal ground profile . . . . . . . . 32Figure 3.4 The output of the single-haul, multi-haul, and Softreemodels for a flat ground profile with 5 segments . . . 33Figure 3.5 The output of the single-haul, multi-haul, and Softreemodels for a linear ground profile . . . . . . . . . . . 34Figure 3.6 The optimal VA for a quadratic ground profile with10 levels of vertical band . . . . . . . . . . . . . . . . 36viiiLIST OF FIGURESFigure 3.7 The quadratic equation passing the upper bound ofthe feasible region, starting, and ending control pointsfor Example 2 . . . . . . . . . . . . . . . . . . . . . . 38Figure 3.8 The output of the single-haul, multi-haul and SoftreeAPI for a quadratic ground profile with 20 levels ofvertical band . . . . . . . . . . . . . . . . . . . . . . . 39Figure 3.9 A summary of finding the minimum d . . . . . . . . . 40Figure 3.10 The output of the single-haul, multi-haul and SoftreeAPI for a quadratic ground profile with 10 levels ofvertical band . . . . . . . . . . . . . . . . . . . . . . . 43Figure 3.11 The optimal VA for a quadratic ground profile with20 levels of vertical band . . . . . . . . . . . . . . . . 45Figure 4.1 The optimal VA for a spline ground profile while splinesegments satisfy slope constraints . . . . . . . . . . . 49Figure 4.2 The optimal VA for a spline segment while the smallersegment satisfies the slope constraints . . . . . . . . . 52Figure 4.3 The optimal VA for a spline segment while the largersegment satisfies the slope constraints . . . . . . . . . 54Figure 4.4 The optimal VA for a spline segment while none ofthe segments satisfies the slope constraints . . . . . . 56Figure 5.1 Specifications for creating 10000 quadratic ground pro-files . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58ixList of Supplementary MaterialsIntroduction to Roadents . . . . . . . . . . . . . . . . . . . . . . . . 15Use of Single-ground profile generator . . . . . . . . . . . . . . . . . . 18Use of Multi-ground profile generator . . . . . . . . . . . . . . . . . . 19How to set Configuration Settings for models . . . . . . . . . . . . . . 22How to use .CSV Converter . . . . . . . . . . . . . . . . . . . . . . . . 23How to use Road Visualizer . . . . . . . . . . . . . . . . . . . . . . . . 25How to use VA Evaluator . . . . . . . . . . . . . . . . . . . . . . . . . 27xAcknowledgementsI would like to thank Dr. Yves Lucet as my main supervisor for continu-ous help and guidance for this project. He has always been very welcomingto help during the project. And, Dr. Warren Hare as my co-supervisor gaveme very helpful comments and guidance during the project.Special thanks to The University of British Columbia, Softree Techni-cal System Inc., and the federal government of Canada for providing mefinancial support. This work was supported by the Natural Sciences andEngineering Research Council of Canada (NSERC) through CollaborativeResearch and Development grant #CRDPJ 479316-15 sponsored by SoftreeTechnical Systems Inc. Additional funding was provided by the GraduateEntrance Scholarship and the University Graduate Fellowship from the Uni-versity of British Columbia. Part of the computation in this research wascarried out, using a software library provided by Softree Technical SystemInc. Part of the research was performed in the Computer-Aided ConvexAnalysis (CA2) laboratory funded by a Leaders Opportunity Fund (LOF,John R. Evans Leaders Fund Funding for research infrastructure) from theCanada Foundation for Innovation (CFI) and by a British Columbia Knowl-edge Development Fund (BCKDF).xiDedicationI would like to dedicate my work to underprivileged cats all over theworld.xiiChapter 1Introduction1.1 Road design optimizationFocusing on minimizing the cost while satisfying regulatory and safetyconstraints, road design optimization is the problem of finding an alignmentconnecting two given end-points. In road design optimization, we have fivemajor costs: construction cost; maintenance cost; planning and adminis-trative cost; user cost; and social and environmental cost [14]. The roaddesign optimization problem consists of three main sub-problems, which areEarthwork, Horizontal Alignment (HA) and Vertical Alignment (VA) op-timization problems. The solution path of the road design problem startsfrom the Earthwork optimization and continues to the vertical and then fi-nally finishes in the horizontal alignment optimization. In other words, tosolve the HA problem, we first need to tackle the VA problem and to solvethe VA problem, we should deal with the Earthwork optimization problem.Figure 1.1 shows a high-level overview of tackling the road design problem.11.1. Road design optimization Earthwork Optimization Vertical Alignment (VA) Optimization Horizontal Alignment Optimization Solve Figure 1.1: The high-level overview of dealing with the road design problem1.1.1 Earthwork optimizationThe Earthwork optimization problem refers to the problem of minimizingthe overall cost of excavating, loading, hauling and embanking of materialsin a given region. In other words, the objective of this problem is to find thecheapest way to excavate materials, move them from a section and embankthem in other sections. Figure 1.2 shows the different stages of the earthworkoptimization problem. Loading Excavating Embanking Hauling Figure 1.2: Different stages of Earthwork optimizationIn road construction, we have both fill and cut sections. The groundprofile is the level of the ground prior to optimization while the road profileis the level of the ground after the optimization. Fill sections refer to sectionsthat road profile is above the ground profile and cut sections are sections21.1. Road design optimizationof the road profile that are below the ground profile. Embankment andexcavation costs are associated to fill and cut sections while hauling costrefers to the movement of materials between cut and fill sections.Since the VA problem is the main focus of this thesis, next the HAproblem will be discussed briefly, and then the VA problem will be explainedin details.1.1.2 Horizontal alignment optimizationThe horizontal alignment optimization problem refers to the problemof finding the best piecewise linear-circular curve between two given pointswhile trying to minimize the cost of Earthwork and satisfying all horizontaland vertical alignment design constraints. In road design optimization, theprojection of curves and tangential lines on a horizontal plane is called thehorizontal alignment and the feasible horizontal region in which the hori-zontal alignment can be created is called corridor.There have been numerous studies regarding the horizontal alignmenttopic. For example, Mondal [20] presented a new optimization model forsolving the horizontal alignment problem in a specified corridor. Usingderivative-free optimization algorithms, the author guaranteed the local op-timality of the solution. In another recent study, Aziz [2] developed a multi-fidelity framework in road design to optimize the performance of the hori-zontal alignment optimization algorithms in road design. He showed thatusing this framework, the horizontal alignment can be found for a variety ofroads in a much faster pace while guaranteeing local optimality. Casal, San-tamarina, and Va´zquez-Me´ndez [4] presented a mathematical model for hor-izontal alignment comprised tangential lines and circular curves connectedwith transition curves. They showed that using this model, they can im-prove the horizontal alignment of existing roads. Pu et al. [24] proposed ameta-heuristic algorithm for dealing with horizontal alignment in complexmountainous terrains. Using this approach, they showed that the results aremore promising compared to the ones created by experienced designers.1.1.3 Vertical alignment optimizationVertical alignment optimization is the problem of finding the optimalvertical alignment, which minimizes the earthwork cost while satisfying thevertical alignment design constraints for a fixed horizontal alignment.Many researchers have presented models for optimizing the vertical align-ment problem. Some authors have applied heuristic algorithms to the prob-31.1. Road design optimizationlem. For example, Cheng and Lee [18] introduced a novel method for verticalalignment optimization problem and used a heuristic approach for solvingit. Akay [1] introduced a new model for three-dimensional alignment of for-est roads and applied a simulated annealing algorithm to solve it. Sinceheuristic-based approaches are non-deterministic and do not guarantee theoptimality of a solution, other recent approaches have been proposed forsolving the problem.Hurate [25] applied dynamic programming to the vertical alignmentproblem for the first time. They introduced a two-phase model for verticalalignment optimization. In the first phase, the author generated a verti-cal alignment using piecewise-linear segments, and in the second phase, thevertical alignment is approximated by a set of cubic functions. Goh, Chew,and Fwa [9] introduced a dynamic programming model to solve the two-dimensional highway location problem. Although dynamic programming iseasy to implement, the drawback of this method is that it explores a discretesearch space. As a result, the generated vertical alignment is non-smooth.Recent studies have applied linear, mixed-integer linear and quadraticprogramming to earthwork and vertical optimization problems. Stark andNicholls [27] used linear programming for the earthwork optimization for thefirst time. Easa [6] introduced a linear programming based model, whichminimizes the earthwork optimization cost while satisfying the geometricconstraints. Moreb [21] introduced a model, which incorporates the road-way grade selection level and earthwork transportation level using linearprogramming. Consequently, the model ensures global optimality. Easa [5]proposed the idea of non-constant unit costs using a quadratic program-ming model. Moreb and Alijohani [23] used a linear mathematical modelto overcome the issue of sharp connectivity points by presenting the roadprofile as a quadratic spline. Moreb in [22] used a univariate spline tocombine the grade selection and earthwork allocation problems in a linearprogramming problem. The presented model guarantees global optimalitywhile maintaining smoothness. Koch and Lucet [16] improved the model bymodifying the gap and slope constraints while keeping the linearity of themodel. Hare, Koch and Lucet [11] introduced a mixed-integer linear pro-gramming model that considers physical blocks such as mountains, riverswhile minimizing the earthwork optimization cost. Rahman [10] integratedthe side-slopes with the presented model by Hare, Koch and Lucet [11] usinga quasi-network-flow model (QNF). They also improved the performance ofthe model in terms of the construction cost. In another study [3], Beiran-vand improved the computational cost of the quasi-network-flow model bypresenting a multi-haul quasi-network-flow model (MQNF).41.2. The quasi-network-flow model for vertical alignmentSince in this thesis, the quasi-network-flow model is incorporated intothe interface, it will be discussed in details.1.2 The quasi-network-flow model for verticalalignmentBefore explaining the QNF model, we will briefly go over the terminologyused in vertical alignment optimization.1.2.1 TerminologyGround profile: The vertical profile of the ground prior to construc-tion.Road profile: The vertical profile of the ground after construction.Section: The ground profile is divided into several unique smaller unitscalled sections, which are indexed by the set S = {1, 2, ..., n}.Station: The starting and ending points of each section.Spline: The road profile is approximated using a spline, which is apiecewise quadratic function.Segment: The spline is split into m segments, which are indexed bythe set G = {1, 2, ...,m}. Each segment is represented using a quadraticequation, which can be formulated as,Pg(x) = ag,1 + ag,2x + ag,3x2 (1.1)where g and x are the segment number and the station number, respectively.Pits: Pits are categorized into borrow and waste pits. Borrow pits referto external sections where earth can be borrowed whereas waste pits areexternal sections where earth can be disposed.Control points: Control points are the stations where the elevation ofthe road profile is preallocated.Vertical offsets: The vertical displacements from the points along theground profile.Vertical band: The allowable region for vertical optimization.Figure 1.3 shows three sample stations of a road profile with their cor-responding vertical offsets and vertical band.51.2. The quasi-network-flow model for vertical alignmentVertical bandVertical offset1-1Figure 1.3: A three dimensional alignment [20]1.2.2 The model descriptionThe QNF model can be presented using graphs in which nodes are sec-tions and pits, and edges are feasible moves. The movements between thenodes are done using additional virtual nodes called transit nodes. Eachsection has east and west transit nodes. The volume of earth moved usingedges are called flows that are categorized into load, unload, borrow, waste,west and east transit flows. Load and unload flows refer to fill and cut vol-umes, respectively, which are considered in east and west directions. Theunload flow from a borrow pit is the cut volume for both east and west di-rections. The load flow to a waste pit is the fill amount for both directions.Figure 1.4 represents a typical section i of the QNF graph at time-step t.61.2. The quasi-network-flow model for vertical alignment Section [i] West transit node [i-1] East transit node [i+1] 𝑓𝑖,𝑖+1,𝑡𝑟 𝑓𝑖,𝑖−1,𝑡𝑟 West transit node [i] Borrow[j] 𝑓𝑖,𝑖−1,𝑡𝑢 𝑓𝑖+1,𝑖,𝑡𝑙 𝑓𝑖,𝑖+1,𝑡𝑢 𝑓𝑖−1,𝑖,𝑡𝑙 West transit node [i+1] 𝑓𝑖+1,𝑖,𝑡𝑟 East transit node [i] East transit node [i-1] 𝑓𝑖−1,𝑖,𝑡𝑟 𝑓𝑗,𝑖−1,𝑡𝑏 𝑓𝑗,𝑖+1,𝑡𝑏 Waste[k] 𝑓i+1,𝑘,𝑡𝑤 𝑓i−1,𝑘,𝑡𝑤 Figure 1.4: A typical section i of the QNF graph at time-step tObjective functionThe objective is to minimize the earthwork cost, which includes excava-tion, embankment and hauling costs. It can be formulated as,min∑i∈S(piV+i + qiV−i ) +∑t∈T∑i∈S(cri,i−1fri,i−1,t + cri,i+1fri,i+1,t)+∑j∈Bcbj∑t∈T(f bj,ϑ(j)−1,t + fbj,ϑ(j)+1,t) +∑k∈Wcwk∑t∈T(fwϕ(k)−1,k,t + fwϕ(k)+1,k,t)(1.2)where the parameters− pi and qi are the per unit volume excavation cost and per unit volumeembankment for a section i, respectively,− cri,i−1 and cri,i+1 are the per unit volume hauling cost from section i tosection i− 1 and i + 1, respectively,− and cbj and cwk are the borrow and waste costs in either directions fora borrow and a waste pit, respectively,and the variables− V +i is the volume of material excavated from any section or borrow pitand V −i is the volume of material embanked to any section or wastepit,− f ri,i−1,t and f ri,i+1,t are the flows of material from one transit node tothe next in both directions at time-step t,71.2. The quasi-network-flow model for vertical alignment− f bj,ϑ(j)−1,t and f bj,ϑ(j)+1,t are the flows of material to both east and westtransit nodes from a borrow pit,− fwϕ(k)−1,k,t and fwϕ(k)+1,k,t are the flows of material from both east andwest transit nodes to a waste pit.Some of the most important constraints are listed as follows. More detailscan be found in [26].Flow constraintsThe sum of the flows entering a transit node must be the same as theflows leaving that node. The flow constraints for the east and west transitnodes can be formulated as Equation (1.3) and Equation (1.4), respectively,f ri−1,i,t + fui,i+1,t +∑j∈Bϑ(j)=if bj,i+1,t = fri,i+1,t + fli−1,i,t +∑k∈Wδ(k)=ifwi−1,k,t, (1.3)f ri+1,i,t + fui,i−1,t +∑j∈Bϑ(j)=if bj,i−1,t = fri,i−1,t + fli+1,i,t +∑k∈Wδ(k)=ifwi+1,k,t, (1.4)where fui,i−1,t and fui,i+1,t are the flow of earth from a section to both eastand west transit nodes, f li−1,i,t and fli+1,i,t are the flow of earth from botheast and west transit nodes to a section.Balance constraintsThe total of unload flows from a section should be the same as the cutvolume at that section. ∑t∈T(fui,i+1,t + fui,i−1,t) = V+i (1.5)The total of load flows to a section should be equal to the fill volume atthat section. ∑t∈T(f li−1,i,t + fli+1,i,t) = V−i (1.6)81.2. The quasi-network-flow model for vertical alignmentSlope constraintsSlope constraints ensure that the slope of the spline segments is withinthe slope range, where U and L are the maximum and the minimum al-lowable slope values. Since the spline segments are quadratic, it suffices tocheck the slopes of the starting and ending stations for each segment. Theslope constraints for segment g can be formulated as,L ≤ ag,2 + 2ag,3sg,i ≤ U (1.7)where sg,i is the starting point of the ith station of the gth segment. Fig-ure 1.5 shows the slope constraints for the gth segment. 𝑆𝑔,1 𝑆𝑔,𝑛𝑔+1 𝐿 ≤ 𝑎𝑔,2 + 2𝑎𝑔,3𝑠𝑔,1 ≤ 𝑈 𝐿 ≤ 𝑎𝑔,2 + 2𝑎𝑔,3𝑠𝑔,𝑛𝑔+1 ≤ 𝑈 Segment g Figure 1.5: The slope constraints for the gth segmentSmoothness constraintsThe C0 continuity constraint implies the spline segments are to be con-tinuous at their connecting points. For all segments g except the first onewe have,ag,1 + ag,2sg,1 + ag,3s2g,1 = a(g−1),1 + a(g−1),2sg,1 + a(g−1),3s2g,1 (1.8)and the C1 continuity constraints ensures that the spline segments aresmooth at their connecting points. Thus, for all segments g except thefirst one we have,ag,2 + 2ag,3sg,1 = a(g−1),2 + 2a(g−1),3sg,1 (1.9)91.3. Multi-haul quasi-network-flow (MQNF) model1.3 Multi-haul quasi-network-flow (MQNF)modelIn the QNF model, we consider just one single haul to move materialsbetween sections. This single haul is considered as a single type of earth-moving equipment such as a truck. In real-world road construction, variousearthmoving equipment is used to build a more economical road. As anexample, for short distances, a bulldozer can be used whereas a truck ispreferred for long distances. In MQNF model, we consider several haulingpaths to build more realistic roads. We consider three hauling paths forMQNF model, which are free-haul, over-haul and end-haul.1.4 Softree API®Softree API is a commercial software that is developed by our industrialpartner, Softree Technical System Inc. This software is designed to tacklethe road optimization problem.In this thesis we use Softree API, a commercial road optimization toolkit,for solving the VA optimization problem, and evaluate whether the outputsof the QNF, MQNF and Softree API models are as expected.1.5 Organization of this thesisThis thesis presents a software that includes four contributions that aimto help researchers validate and check different models for VA. As we know,there exists different models for VA optimization, such as [10] and [3], butwe have not had a tool to check the output of the VA models. In orderto check the output of these models, we need to have test cases. In oursoftware package, first, a ground profile generator, which can easily gener-ate linear, quadratic or advanced ground profile test cases, is designed andimplemented. Using this software component, users can test, check and com-pare their new algorithms against existing models easily. Second, a softwarecomponent is designed to check whether the proposed models can providethe expected results. Using this, model designers can ensure that their mod-els are able to solve simple vertical alignment problems. Third, since thissoftware is designed based on the micro-service architecture, any softwarecomponent can be implemented in a different programming language. Forexample, the QNF, MQNF and Softree API models were all implementedusing the C++ language while other components are developed using the101.5. Organization of this thesisC# language. Moreover, any changes to the existing models and even in-corporating new algorithms into the software can be carried out with someminor changes. For integrating a new algorithm in Roadents, it sufficesthat the input and output of the new algorithm follow a specific format.Finally, Softree Technical System Inc., our industrial partner, possesses nu-merous ground profile files in different .CSV formats, each of which workswith a specific version of Softree API. Using our software, users are able toconvert all these versions of .CSV files into their desired format.It is worth to mention that the ground profile generator and the VAchecking tool are the cornerstones of our software package as using thesetwo components users are able to generate test cases and check their newVA algorithms. On the other hand, the least important component is the.CSV converter since this component only converts area .CSV files from oneversion to the other versions.The remainder of this thesis is structured as follows. In Chapter 2, wediscuss our proposed software, which is called Roadents, concentrating onits different components. In Chapter 3, we explain linear and quadraticground profiles. In Chapter 4, we study the spline ground profiles. The nu-merical experimentation of quadratic ground profiles are discussed in Chap-ter 5. In Chapter 6, we conclude the thesis and provide some suggestionsfor future works.11Chapter 2ROADENTS: ROAd DEsigNTesting SoftwareIt is a consensus in the software development world that software andprograms are notoriously prone to errors, run-time exceptions and bugs.To protect ourselves against such problems, we usually embrace softwaretesting such as unit testing, integration testing, system testing and regressiontesting [15]. However, there are some limitations and constraints regardingtesting such as difficulty in finding the proper test suite. It is also difficult tofind the correct output for the correct suite of test inputs. More importantly,this process is often carried out in the course of the testing stage and notin the production stage. Given this, it is essential to employ the checkingprocess to ensure the correctness of models and implementations.Program checking is different from the verification process. While theformer one is an extension to testing, the latter one is the formal proof ofcorrectness of software implementation in the production scale. There hasbeen a myriad of researches and practitioners focusing on checking software.For example, Mehlhorn et al. [19] presented a tool to check some basicgeometric tasks such as convex polygons, convex planar subdivisions andDelaunay diagrams.In this thesis we present Roadents (ROAd DEsigN Testing Software),which is implemented in the C# programming language. Roadents is notjust a ground profile generator but also a VA checking tool. It contains achecking software component to evaluate and check the output of the models.Using inequalities presented in Section 3.4, the software checks whether theresults of the models are correct and as expected. In Chapter 5, we use thischecking software component to test many quadratic ground profile testcases.The proposed software is data-driven. Data-driven means that the pa-rameters of the models are not hard-coded in the program but rather storedin a file or database. The main goal of data-driven design is to write as littlefixed code as possible [8].In Roadents the domain-driven design pattern is also followed. Nowa-122.1. Motivationdays, domain-driven design is a popular topic in the software developmentworld, especially when designing a complex, multi-functional program.Domain-driven represents the idea of breaking monolithic software into gooddomain models. In this way, it can be ensured that the software can beextended and scaled out without any major changes. More importantly,the domain designers and non-technical people can understand the softwarewithout any problem [7].When developing Roadents, we faced a few challenges. The main chal-lenge we had was that the QNF, MQNF and Softree API models were imple-mented in the C++ language while we wanted to develop Roadents usingthe C# language. To address this issue, a micro-service architecture waschosen. As a result, every component or a new model can be developed ina different programming language.2.1 MotivationSince it is an arduous and time-consuming task to derive the groundprofile with specific specifications (slope, number of stations, number of seg-ments, vertical band) from real-world roads, it is useful to be able to generateuser-defined artificial ground profiles according to the needs. Moreover, tocompare the QNF, MQNF and Softree API models and predict their behav-ior, it is required to have numerous ground profiles with particular specifi-cations to validate or invalidate an observation. For example, after carefulconsideration, users may believe that the difference between the quadraticroad and ground profiles with one segment at an arbitrary station follows aspecific formula. To validate this observation, we can study this conjectureby testing it against the myriads of ground profiles with different specifi-cations. Roadents can be utilized to create artificial single-segment ormulti-segment linear or quadratic ground profiles.Furthermore, for studying a new algorithm for the vertical alignment inroad optimization, Roadents can be used to test, compare and visualizethe results of the new model against the outputs of the existing models. Thenew model can be easily incorporated into Roadents by making sure theinputs and the outputs of the new model follow the same structures as theexisting models.132.2. Software Components2.2 Software ComponentsIn this section, the main components of the software package will bediscussed. The software consists of Ground Profile Generator, ConfigurationSettings, .CSV Converter, VA Evaluator and Road Visualizer components.Figure 2.1 shows the five pillars of the software package. VA Evaluator Road Visualizer CSV Converter Configuration Settings Ground Profile Generator Software Package Figure 2.1: The main components of the proposed softwareFigure 2.2 shows the main window of Roadents.Figure 2.2: The main window of Roadents142.2. Software ComponentsFor an introduction to Roadents please watchSupplementary Materials #1: An introduction to Roadents.2.2.1 Ground Profile GeneratorAs discussed, we desire to generate numerous grounds profiles with dif-ferent configurations. The ground profile generator is built to generate dif-ferent types of ground profiles, ranging from single-segment linear to multi-segment quadratic ground profiles. The output of this component is a .CSVfile, which can be used by all the models.The ground profile generator includes two main parts: Single groundprofile generator and Multi ground profile generator.Single ground profile generatorSingle ground profile generator is designed for generating a single groundprofile and consists of four different parts: Road options, First Station op-tions, Formula options and Process options. Figure 2.3 shows the mainwindow of the Single ground profile generator.152.2. Software ComponentsFigure 2.3: The single ground profile generatorRoad options: Using Road options, users can define the specificationsof a single ground profile such as number of stations, section length (inmeters), number of levels (vertical band), starting level, number of materialsand fill/cut cost (per meter).First Station options: In the First station options, users are able toset the attributes of the first station of the ground profile, which are stationnumber, X-coordinate, Y-coordinate and elevation.Formula options: Real-world ground profiles consist of linear, quadraticor even a combination of these types of profiles. Therefore, the main focushere is on all these types of ground profiles. The Formula options comprisesthree components: Formula, Advanced, and Free Mode Design.− Formula: In the Formula part, users can enter the desired Linear orQuadratic equation of the ground profile to be generated. Using Regexvalidation process [17], it is ensured that users enter the formula in aproper linear or quadratic format.162.2. Software Components− Advanced: Using this option, users can define multi-segment groundprofiles by entering the equations for each segment separately. Fig-ure 2.4 shows the Advanced ground profile generator.Figure 2.4: The advanced ground profile generator− Free Mode Design: This option gives users the ability to generate asingle ground profile of any shape by clicking on the mouse and drawingthe desired shape on the Elevation-Station window.For all of the above options, users can also see the graphical overview of thegenerated ground profile in the Elevation-Station window.Process options: This option is utilized to export the information of agenerated ground profile into a .CSV file. There are three different versionsof .CSV files each of which is suitable for a specific model. The .CSV version1 can be used for Softree API up to version 1, and .CSV version 2 is used inSoftree API version 2. Moreover, users can generate a .CSV version, whichis not suitable for Softree API, but rather for QNF and MQNF models. Thisone is called as the old version in Roadents.172.2. Software ComponentsFor a demonstration of the use of Single ground profile generator,please watchSupplementary Materials #2: Single ground profile generator.Multi ground profile generatorMulti ground profile generator is utilized for generating quadratic groundprofiles in large numbers. Using this software component, users can spec-ify the minimum and maximum of coefficients of quadratic ground profiles.Moreover, they can define vertical band, station range, the number of gener-ated ground profiles, fill/cut cost, initial station number, and its coordinatesand also section length range. After choosing the proper destination folder,the desired number of ground profiles within the chosen ranges will be gen-erated in the destination folder in the proper .CSV file. Figure 2.5 showsthe main window of the Multi ground profile generator.182.2. Software ComponentsFigure 2.5: The multi ground profile generatorTo gain more information about Multi ground profile generator,please watchSupplementary Materials #3: Multi ground profile generator.2.2.2 Configuration SettingsUsing this component, users can set the configurations of each modelindividually. As discussed earlier, Roadents is data-driven where userscan define or change the input parameters of all the models. In all the192.2. Software Componentsmodels studied, users can change or customize the solver, the number ofstations per segment, and many other settings related to the road design.Figure 2.6 shows the main window of the Configuration Settings.Figure 2.6: The configuration settingsIn particular, for the QNF and MQNF models, users can determine mid-dle control points, the lower and upper bounds of the spline slope, number ofstations per segment, the solver used for VA optimization (CPLEX/CBC),the model of solving the problem (QUADRATIC, NETWORK), reducedbinary (normal, type 1, SOS2), which is related to the variables of theconstraints. For the MQNF model, there is an extra setting, which is thenumber of hauls. The value of this variable is set to 3 by default. Users canchoose values 1 (only free-haul), 2 (free-haul and overhaul) and 3 (free-haul,overhaul and end haul). It should be noted that in QNF and MQNF models,the starting and ending stations are already considered as control points.On the other hand, for the Softree API, users should set starting andending stations as control points. Moreover, since the Softree API is com-mercial software, there are more options comparing to the QNF and MQNFmodels. In the Softree API, users can set the unit costs of each hauling pathsuch as load cost of free-haul, load cost of overhaul, load cost of endhaul,move cost of freehaul, move cost of overhaul and move cost of end-haul. The202.2. Software Componentsdistance for each type of hauls depends on the hauling and loading costs.So, users have the possibility to update free-haul and overhaul thresholddistances. The unit cost variable values for Softree API are by default set tothe same values as QNF and MQNF models. At the top of the Unit Costsgrid, users can set the name of the materials, embankment/excavation unitcost coefficients. Each material has a designated embankment/excavationcost. Users can also set the quality of the material of the ground where eachmaterial has a designated quality factor (Q1, Q2, Q3 and Q4) indicating theeffectiveness of material for the fill. For the time that the desired quality isrequired, any material with the same or higher quality can be used for con-struction. The quality factor Q1 has the best and Q4 has the worst quality.Users can also set the cut/fill factors used for calculating the optimizationcost.In the Constraints grid, users can set the grade and K constraints. Theseconstraints control the smoothness and steepness of an alignment. Gradeconstraints determine the maximum and minimum permissive grades de-pending on the speed limit and the traffic composition [20]. The horizontaldistance, along which a 1% change in grade occurs on the vertical crest andsag curves, is represented by the K value. Crest and sag vertical curves areconcave and convex parabolic curves, respectively. The constraints set theminimum K value for the minimum crest and sag curves.Using Optimization grid, users can set the VA or HA. Users can alsodetermine the curve type. In the Softree API, different curve types areavailable. These are− POLYLINE: This produces an alignment with straight segments only(There are no curves).− CURVE: This option generates back to back curves without tangentsbetween them.− CURVE TAN: It generates an alignment with a tangent inserted be-tween curves. Using this option, the time to solve the mixed-integerlinear programming problem can be reduced.− CURVE TAN GENERAL: This option is similar to CURVE TAN butwe can have curves and tangents with variable lengths. Using thisoption the time to solve the mixed-integer linear programming problemis slowest.− USER DEFINE: This preserves the location and the length of thecurves and tangents as defined in the Reference alignment. The speed212.2. Software Componentsof this option is similar to the CURVE option.− SETFROMOUTSIDE: This option provides a test mode, which canbe used for constraint checking.In the Optimization grid, users can also choose the solver (CPLEX, CBC)for solving the problem. In this grid, users can also select different types ofoptimization. These are− COSTOPTIMIZATION: This calculates the cost of a given verticalalignment.− FULLOPTIMIZATION: This option calculates the optimal (lowestcost) vertical alignment position and its associated cost.− FESOPTIMIZATION: It checks the feasibility of the constraints.− GENOPTIMIZATION: This option generates a best fit profile.Users can also configure the cost model,− GEN COST: This one will return the general cost. This option is setby default.− FES COST: This one is for a feasibility check with no costing involved.− NOEARTH COST: This option returns the cost of the model withoutearth movement.Like QNF and MQNF models, users can choose (QUADRATIC/NETWORK)models for finding the optimal VA. Minimum curve length is the minimumlength of a curve measured horizontally from the first station to the last one.For more information, users can visit [12].There is also an option for automating the configuration settings for thesolvers, which is called Automated model settings. This option considersthe starting and ending stations of each ground profile as control points forall of the models. Moreover, checking this option assumes that a road profilehas one segment for all of the models. Consequently, for a group of groundprofiles, there is no need to do these settings individually, which leads to agreat reduction in the processing time.For a demonstration of how to set the Configuration Settings,please watchSupplementary Materials #4: Configuration Settings.222.2. Software Components2.2.3 .CSV ConverterThe .CSV Converter is useful when users want to convert the .CSV of aground profile to the other versions. As discussed, there exist three differentversions of .CSV files for ground profiles. The .CSV area file used for Softreeapplication software up to version 6, QNF and MQNF models is called theold .CSV file. Softree API has currently two different input versions: Version1.0 and Version 2.0. Using the .CSV converter, users can convert any area.CSV file to other versions. Figure 2.6 shows the main window of the .CSVConverter.Figure 2.7: The .CSV converterMore information about how to use the .CSV Converter can befound inSupplementary Materials #5: The .CSV Converter.232.2. Software Components2.2.4 Road VisualizerThis component gives users the ability to visualize the VA generated byany VA models provided that their input is in the form of station/elevationand is stored as a .CSV file. In the Road Visualizer grid view, there existthree different options, which are Draw options, Input options and Outputoptions.− Draw options: Using this option, users can set the specifications ofeach alignment, such as line pattern, line thickness, line color. If theVA is too small/big, users can zoom in/out using the zoom slide bar.− Input options: By this option, users can choose the inputs to thevisualizer, which are station/elevation files. Users can also clear all ofthe drawn alignments.− Output options: Using this option, users can browse the destinationfor saving the output alignments. The output image is stored as aPNG file.Figure 2.8 shows the main window of the Road Visualizer.Figure 2.8: The road visualizer242.2. Software ComponentsTo gain more information about Road Visualizer, please watchSupplementary Materials #6: Road Visualizer.2.2.5 Micro-service architecture for VA evaluationRoadents follows the micro-service architecture and domain-driven de-sign pattern. The micro-service design refers to breaking of a formerlycomplicated monolithic software into small, independent units called micro-service where each micro-service is designed, implemented or even deployedin a different environment. Readers are referred to [28] to gain more infor-mation about micro-service architecture and design.Since the micro-service architecture is chosen for Roadents, the modelscan be developed, tested, evaluated, versioned and deployed independently.It means that if users want to update the Softree API from version 2.0to version 3.0, they can develop, update and test the Softree API withoutmaking any changes to any other parts of the software. In this way, users canalso add a new API without changing any other APIs. More importantly,the other APIs can be written with any language that Microsoft Windows(later than XP) supports. Figure 2.9 shows the micro-service-based designof Roadents.Figure 2.9: The micro-service-based design of RoadentsAs shown in Figure 2.9, QNF, MQNF and Softree API and VA Evaluatorare considered as micro-services and use file-based communications to sendinformation among each other. So, for example, when a ground profile isselected for evaluation, VA Evaluator first checks if the ground profile is252.2. Software Componentsin a proper format. If it is, then VA Evaluator stores the .CSV area filein the proper format for any of the micro-services and sends a notificationletting them know that a problem is ready to be solved. After solving theproblem, the micro-services send back a notification to VA Evaluator to letit know whether each one has solved the problem or not. Taking advantageof the micro-service architecture, users can easily change any of the micro-services. And by some minor changes, a new VA Evaluator can incorporatethe modified micro-service into its structure.The VA Evaluator comprises three main components: input, solve andoutput. Figure 2.10 shows the configuration of the VA Evaluator component. Ground profile (.CSV) Station/Elevation(.CSV) Cost/Time(.CSV) Solve Coefficients(.CSV) D(.CSV) Figure 2.10: VA Evaluator componentsThe input of the VA Evaluator is the .CSV file of the ground profile. Us-ing the File option, users can import the .CSV of a single ground profile andusing Folder option, they can import the .CSV of multiple ground profiles.A summary of the imported ground profiles including road name, numberof stations, number of vertical offsets, and number of materials is shown inthe Input Roads grid view.In the Process grid view, users can determine the output type of the VAEvaluator, which are,− Export to Coefficients (.CSV): By checking this checkbox, the coeffi-cients of the road profile for QNF, MQNF and Softree API are storedin a separate .CSV file.− Export to Station/Elevation (.CSV): After checking this checkbox, thestations and their related elevations of the road profile are kept in a.CSV file.262.2. Software Components− Export to Cost/Time (.CSV): This option saves the information aboutthe optimization cost and the required time of each model for solvingany problems in a separate .CSV file.− Compute difference of ground and road profiles: This is the most im-portant part of the VA Evaluator component. By checking this option,users can evaluate the optimal VA generated by the models. For thispurpose, first the difference between the ground profile and road pro-file generated by each solver at the middle station is calculated. Then,the difference between the ground and optimal expected VA at themiddle station is calculated using (3.14), (3.15) and (3.16). Finally,the results are compared and stored in a separate .CSV file. If thedifference is negligible, we can claim that the output of the models isas expected.More information about Compute difference of ground androad profiles can be found inSupplementary Materials #7: Compute difference ofground and road profiles.Since Roadents is based on the micro-service design pattern, integrat-ing a new model can be easily done with just a few small steps. First, thenew algorithm needs to be implemented as a micro-service and it shouldaccept the .CSV file as an input file. Then, by calling it from the software,the problem can be solved easily. Finally, it is required to make sure thatthe output of the new algorithm is stored as a separate .CSV file, containingthe coefficients of the road profile. Using this, Roadents can generate theElevation/station output .CSV file.27Chapter 3Linear and quadratic groundprofilesIn this chapter, we first discuss why it is difficult to use real-world groundprofiles to test optimization models and software for VA. Second, we explainthe specifications of linear and quadratic ground profiles, and then we studythe results of the single-haul, multi-haul models along with the Softree API.We finally compare their results against the expected vertical alignment.3.1 Real-world ground profilesIn Section 2.2.1, the ground profile generator for creating artificial groundprofiles was discussed. In this section, we study the shape of the real-worldground profiles and why it is difficult to use them to test optimization modelsfor VA. All the real-world ground profiles have one or multiple templates intheir structures. The template refers to the structure and the desired shapeof the finished road. For example, two templates are rural and urban. Therural template is defined with a flat center line containing ditches or spikeson the sides whereas the urban template has a smoother surface with lessnumber of ditches and spikes on edges.In order to show how much a template has an impact on the expectedresults of our models, we optimize the vertical alignment of a real-worldflat ground profile produced by the Softree Location software [13]. Theflat ground profile has 6 stations with the section length 20 meters, onesegment and the slope lower and upper bound of −0.1 and 0.1, respectively.Figure 3.1 shows the results of the single-haul, multi-haul models along withthe Softree API for the flat ground profile.283.1. Real-world ground profilesFigure 3.1: The output of the single-haul, multi-haul models, and the SoftreeAPI for the real-world Flat ground profile.As shown in Figure 3.1, none of the models produce a final optimizedcost equal to zero. The reason is that the ground profile has a rural template.Having the rural template in the area .CSV file of the flat ground profilecauses that the cut cost of the level one to be less than the cut cost of thelevel zero. As a result, level one would be reported as the best verticaloffset. Therefore, the optimal vertical alignment is one meter above theground profile. Since we set two control points at the beginning and theending of the road profile, the output of the models has an arc shape.Figure 3.2 represents the structure of the flat ground profile in detailsfrom two different points of view.293.2. Linear ground profiles Station 0 Ditch Ditch (a) The 3D view Ditch Ditch Center Line (b) The 2D viewFigure 3.2: The station view of the flat ground profile with ditches on theedges obtained from Softree Location softwareFrom Figures 3.1 and 3.2, it can be seen that having at least one typeof templates results in not having the expected optimal vertical alignment.It should be also noted that since the urban template has right and leftslopes, the optimization cost is still nonzero. Using the Softree Locationsoftware, one template can be chosen for the ground profile. Moreover, allthe ditches, spikes or crown slopes for left and right can be removed from thedesired template. In this way, a completely flat road profile can be achievedwith the total optimization cost equal to zero.Although we can filter out the templates from the real-world groundprofiles, it is a time-consuming and an arduous task. Moreover, selectingparts of real-world ground profiles with specific linear or quadratic equationsfor our analysis is a painstaking task. Finally, for a complex real-worldground profile, it might be impossible to know the actual best answer. Thatis why we do use artificial ground profiles generated by Roadents to testoptimization models and software for VA. Figure 3.3 shows the flat groundprofile generated by Roadents with the desired output.3.2 Linear ground profilesIn this section, we will assume that a blank road template is used togenerate artificial ground profiles. In the blank template, Level zero of allthe stations has very small cost. Furthermore, the cost of levels increasesas we keep cutting/filling further. It should be noted that since the SoftreeAPI only accepts non-zero cost for Level 0 of any stations of the ground, we303.2. Linear ground profilescannot choose zero cost for level zero of the ground profile .CSV files. Forthis reason, we chose very small cost (2.4 cents) for Level 0.To analyze the output of the vertical alignment models, the structure oflinear ground profiles is first discussed. The linear ground profile representsa vertical alignment in which the elevation of all stations of the ground,prior to the optimization process, follows a linear equation. The linearground profile can be categorized into horizontal and slanted ones. Theonly difference between these profiles is the feasibility. While a feasible roadprofile always exists for the horizontal ground profile, for the slanted onethere may not exist a feasible road profile. In either case, if a feasible roadprofile exists, then the optimized vertical alignment should be the same asthe initial alignment of the profile.3.2.1 Analyzing the horizontal ground profilesThe horizontal ground profile represents a road where the elevation ofall stations is the same. In order to analyze this type of ground profiles, ahorizontal ground profile with 6 sections is created where the length of eachsection is equal to 20 meters, the slope range is [−0.1, 0.1] and there is onesegment for the whole road. It is clear that the horizontal ground profilessatisfy the slope constraints as the slope of all the stations is equal to zero.Consequently, it is expected the optimal vertical alignment generated by themodels to be the same as the ground profile with the total optimization costequal to zero. Figure 3.3 shows the output of the single-haul, multi-hauland Softree models for the horizontal ground profile.313.2. Linear ground profilesFigure 3.3: The output of the single-haul, multi-haul, and Softree modelsfor the horizontal ground profileSince we chose very small cost for Level 0, the optimization cost of allof the models is not zero but rather close to zero.Since Softree API includes some other parameters, e.g., fill/cut factorsin calculating the cost that are not considered in QNF and MQNF models,we do not have the same costs. That is why we do compare the roads basedon locations not costs.It is worth noting that in any VA, each segment is approximated bya quadratic spline. In the spline interpolation as the number of points in-creases, we have a more fitting spline. As the number of segments grows, thenumber of points in each segment decreases. If we do not have enough pointsin each segment, we might not have a fitting spline. Figure 3.4 denotes theoutput of the models for the horizontal ground profile with 6 segments whereeach segment comprises two sections, the section length is 20 meters and theslope range is [−0.1, 0.1].323.2. Linear ground profilesFigure 3.4: The output of the single-haul, multi-haul, and Softree modelsfor a flat ground profile with 5 segmentsAs shown in Figure 3.4, the output of any of the models is not completelyflat. This is due to the fact that each spline is approximated using onlytwo points, which is not clearly enough for the spline interpolation. Toapproximate a segment of a road using the spline interpolation, we at leastneed three points.3.2.2 Analyzing the slanted ground profilesIn the slanted ground profile, the elevation of all stations follow a linearequation as follows:y = ax + b, (a 6= 0), (3.1)where x is the station number and y is the elevation of the correspondingstation. If the slanted ground profile satisfies the slope constraints, whichwas explained in Section 1.2.2, it is expected that the best vertical alignmentwill be the same as the ground profile with the optimization cost equalto zero. Figure 3.5 shows the road profile generated for the single-haul,multi-haul and Softree API for the slanted ground profile with the equationy = 0.05x + 100 where there exists 6 sections with the section length of 20333.3. Quadratic ground profilesmeters, the slope range is within [−0.1, 0.1] and the road profile has onesegment.Figure 3.5: The output of the single-haul, multi-haul, and Softree modelsfor a linear ground profileAs shown in Figure 3.5, the road profile is the same as the ground profile.The reason is that the slope of the ground profile is 0.05, which is withinthe slope range of [-0.1,0.1].If the slope of the slanted ground profile is outside of the slope range,we do not expect a feasible solution. For example, if the ground profileis y = 0.11x and the slope range is sr=[-0.1,0.1], there is no feasible roadprofile. This is consistent with the testing performed.3.3 Quadratic ground profilesIn this section, we study the quadratic ground profiles concentrating onthe outputs of the single-haul, multi-haul models and the Softree API. Inthe quadratic ground profile, the elevation of all stations in advance of theoptimization process follows the quadratic equation:y = a1x2 + a2x + a3, (3.2)where x is the station number and y is the elevation of that station.343.3. Quadratic ground profilesAs in Section 3.2, in this section we assume the blank template intro-duced on Page 30 is used. Before demonstrating how to find the optimal VAfor quadratic ground profiles, we consider three situations that might occur.Example 1: The optimal vertical alignment is the same as the groundprofile.As discussed, in the QNF model, the road profile is approximated usinga spline. A spline is a piecewise polynomial function, consisting of somequadratic spline segments. Depending on the number of stations in theroad, we may have one or many spline segments.Assume we have a quadratic ground profile with only one segment. If theground profile satisfies the slope constraints, then it should be the optimalvertical alignment. In other words, when the slope at the beginning and atthe end points of each segment of the ground profile is in between the lowerand upper bounds of the slope range, then the optimal vertical alignment isthe same as the ground profile with the minimum total cost.To demonstrate Example 1, we generate a road that follows the followingquadratic equationy = 0.00042x2 − 0.084x + 10.2.It has 11 sections with the section length equal to 20 meters, the slope rangeof [−0.1, 0.1] and 10 levels of vertical band. There is one segment for thewhole road.Based on the slope constraints, it suffices to check the slope at the be-ginning and at the end points of each segment. In this example, the slopeof the ground profile follows the equationm(x) = 0.00084x− 0.084,where x is the section number and m(x) is the slope of the correspondingstation. We havem(0) = −0.084 ∈ [−0.1, 0.1],m(200) = 0.084 ∈ [−0.1, 0.1].As the slope at the boundaries is within the slope range, it is expectedthat the optimized VA to be the same as the ground profile. Figure 3.6shows the optimal vertical alignment generated by the single-haul, multi-haul and Softree API for the quadratic ground profile with the equationy = 0.00042x2 − 0.084x + 10.2.353.3. Quadratic ground profilesFigure 3.6: The optimal VA for a quadratic ground profile with 10 levels ofvertical bandAs shown in Figure 3.6, the optimal vertical alignment of the single-haul,multi-haul and Softree API are the same as the ground profile with the totaloptimization cost close to zero.Example 2: There is no feasible solution for the vertical alignment.In quadratic ground profiles, the lower and the upper bounds of thefeasible region is represented using two quadratic equations. If the slopeof these two quadratic equations at the beginning and at the end controlpoints is not within the slope range, then there is no feasible solution forthe vertical alignment.To demonstrate Example 2, we generate the ground profile with thefollowing equationy = 0.0025x2 − 0.5x + 25.where there are 11 stations with the section length equal to 20 meters, theslope range of [−0.1, 0.1], and 10 levels for the vertical band. There is alsoone segment for the whole road.The slope of the ground profile follows the equationm = 0.005x− 0.5.So we have,m(0) = −0.5 /∈ [−0.1, 0.1],m(200) = 0.5 /∈ [−0.1, 0.1].363.3. Quadratic ground profilesIn this example, the ground profile does not satisfy the slope constraints.Therefore, the best VA is not the ground profile.To check whether there is a feasible VA, we check whether the quadraticequation passing the beginning, ending and the arbitrary station at theupper bound of the vertical band satisfies the slope constraints. Note thatif this fails, then there is no feasible VA. However, if it passes, it does notguarantee that there ia a feasible VA, as it might fail somewhere else.The beginning, ending and the arbitrary stations have the coordinates(0,25), (200,25) and (100,10), respectively. The quadratic passing thesethree points has the equationy = 0.0015x2 − 0.3x + 25.The aforementioned quadratic has the slope of,m(x) = 0.003x− 0.3.We havem(0) = −0.3 /∈ [−0.1, 0.1],m(200) = 0.3 /∈ [−0.1, 0.1].As can be seen, the quadratic passing the control points and the arbitrarystation at the last level of the feasible region does not satisfy the slopeconstraints. Therefore, there is not any feasible VA for the ground profiley = 0.0025x2 − 0.5x + 25 with the slope range [−0.1, 0.1] and 10 levels forthe vertical band.In Figure 3.7, the green dashed curves denote the vertical band, theblue dashed curve represents the ground profile and the red dashed curveshows the quadratic equation passing an arbitrary station (station 100) atthe upper bound of the feasible region for Example 2.373.3. Quadratic ground profiles0 50 100 150 200010203040StationElevationVertical bandQuadratic at last levelGround profileFigure 3.7: The quadratic equation passing the upper bound of the feasibleregion, starting, and ending control points for Example 2Example 3: The optimal vertical alignment is not the same as the groundprofile.In this example, we assume that the ground profile does not satisfy theslope constraints. On the other hand, the slope of the quadratic passing theupper bound of the feasible region at the beginning and end points is withinthe slope range. Given this, we have a feasible solution, which is not thesame as the ground profile.As discussed, there is no feasible VA for the ground profile with theequation of,y = 0.0025x2 − 0.5x + 25,the slope range of [−0.1, 0.1] and 10 levels for the vertical band.If we increase the number of levels to 20, the quadratic passing thecontrol points (0,25), (200,25) and (100,20) will have the equation of,y = 0.0005x2 − 0.1x + 25.The aforementioned quadratic has the slope of,m(x) = 0.001x− 0.1,383.4. Finding the optimal vertical alignment for quadratic ground profileswhere the slope at the beginning and at the ending control points will be,m(0) = −0.1 ∈ [−0.1, 0.1],m(200) = 0.1 ∈ [−0.1, 0.1].Since y = 0.0005x2−0.1x+25 is the closest quadratic to the ground profile,which satisfies the slope constraints and passes the control points, it will bethe optimal VA for the ground profile with the equation of,y = 0.0025x2 − 0.5x + 25.Figure 3.8 shows the optimal VA generated by the single-haul, multi-haulmodels and the Softree API for the ground profile y = 0.0025x2− 0.5x+ 25.Figure 3.8: The output of the single-haul, multi-haul and Softree API for aquadratic ground profile with 20 levels of vertical bandAs shown in Examples 1-3, three situations may come up in optimizingquadratic ground profiles. In Section 3.4, we will introduce a formula thatcovers these three situations.3.4 Finding the optimal vertical alignment forquadratic ground profilesHere the objective is to find the optimal vertical alignment for any typesof quadratic convex ground profiles. For this reason, it is required to mini-mize the distance between the ground profile and the road profile, which is393.4. Finding the optimal vertical alignment for quadratic ground profilescalled (d), such that the quadratic curve passing through the control pointsand an arbitrary station within the station range to be feasible. It is worthnoting that the optimal vertical alignment for the concave quadratic groundprofile can be obtained in a similar fashion.Suppose that the station range is [xs, xe], xm is an arbitrary stationwithin the station range, the slope range is [−m,m] and the number of levelsis equal to nl. The ground profile and the road profile have the equationsof,yn = ax2n + bxn + c,y′n = a′x2n + b′xn + c′,(3.3)respectively, where xn is the station number. Figure 3.9 shows a summaryof the problem.𝑐𝑝1 = (𝑥𝑠, 𝑦𝑠) 𝑐𝑝2 = (𝑥𝑒 , 𝑦𝑒) (𝑥𝑚, 𝑦𝑚′ ) min𝑑 (𝑥𝑚, 𝑦𝑚) Figure 3.9: A summary of finding the minimum dAs cp1 and cp2 are the starting and the ending control points, it isrequired that the elevation of the ground and road profiles at these twostations to be the same. This can be formulated asa′x2s + b′xs + c′ = ys,a′x2e + b′xe + c′ = ye.(3.4)The elevation of the road profile at the arbitrary station (xm) can be ob-tained from the following formulaa′x2m + b′xm + c′ = y′m. (3.5)Using 3.4 and 3.5, we find a′, b′, which are the coefficients of the quadraticroad profile asa′ =(y′m − ye)(xm − xs)− (y′m − ys)(xm − xe)(x2m − x2e)(xm − xs)− (x2m − x2s)(xm − xe), (3.6)403.4. Finding the optimal vertical alignment for quadratic ground profilesb′ =ys − yexs − xe − a′(xs + xe). (3.7)After replacing (3.6) in (3.7) we haveb′ =ys − yexs − xe −[(y′m − ye)(xm − xs)− (y′m − ys)(xm − xe)(x2m − x2e)(xm − xs)− (x2m − x2s)(xm − xe)](xs + xe)(3.8)As mentioned in section 1.2.2, every road profile needs to satisfy the slopeconstraints at the beginning control point. So we require−m ≤ 2a′xs + b′ ≤ m. (3.9)After replacing (3.6) and (3.8) in (3.9) we need−m ≤ 2[(y′m − ye)(xm − xs)− (y′m − ys)(xm − xe)(x2m − x2e)(xm − xs)− (x2m − x2s)(xm − xe)](xs)+ys − yexs − xe −[(y′m − ye)(xm − xs)− (y′m − ys)(xm − xe)(x2m − x2e)(xm − xs)− (x2m − x2s)(xm − xe)](xs + xe)≤ m.(3.10)In a similar vein, the road profile also must satisfy the slope constraints atthe end control point. Therefore, we require−m ≤ 2a′xe + b′ ≤ m. (3.11)Replacing (3.6) and (3.8) in (3.11) we get−m ≤ 2[(y′m − ye)(xm − xs)− (y′m − ys)(xm − xe)(x2m − x2e)(xm − xs)− (x2m − x2s)(xm − xe)](xe)+ys − yexs − xe −[(y′m − ye)(xm − xs)− (y′m − ys)(xm − xe)(x2m − x2e)(xm − xs)− (x2m − x2s)(xm − xe)](xs + xe)≤ m.(3.12)As shown in Figure 3.8, the elevation of the road profile at the arbitrarystation (xm) is equal to the elevation of the ground profile at this stationplus the difference (d) between the road and ground profiles at this station.So we writea′x2m + b′xm + c′ = y′m = ym + d. (3.13)413.4. Finding the optimal vertical alignment for quadratic ground profilesLet Φ1 = xm(−xm+xs+xe) and ∆ = ye(xs−xm) + ys(xm−xe), then afterreplacing (3.13) in (3.10) and trying to isolate d we have[−m−(ys−yexs−xe)][Φ1−xsxe]−∆(xe−xs) − ym ≤ d ≤[m−(ys−yexs−xe)][Φ1−xsxe]−∆(xe−xs) − ym.(3.14)Let Φ2 = xm(xm − xs − xe). After replacing (3.13) in (3.12) and tryingto isolate d we have[m−(ys−yexs−xe)][Φ2+xsxe]−∆(xe−xs) − ym ≤ d ≤[−m−(ys−yexs−xe)][Φ2+xsxe]−∆(xe−xs) − ym.(3.15)In order to have a feasible road profile, the difference of the road andground profiles at any arbitrary station needs to be within the vertical band.So we have0 ≤ d ≤ nlh. (3.16)where nl is the number of levels and h is the height of each level. In allof the examples, we assume the height of each level is equal to one meter.Since the objective is to find the minimum value of d, we should first findthe intersection of the ranges of d values from the inequalities (3.14), (3.15)and (3.16).Given the intersection of the ranges of d values from inequalities (3.14),(3.15) and (3.16), we face three different cases.Case 1: When d ∈ [0, d¯] : As the goal is to minimize d, in this case, d = 0will be the solution to the problem, which means that the ground profile isthe best VA.To study Case 1, we generate a ground profile with the following equationyn = 0.0005x2n − 0.1xn + 7, (3.17)where there are 11 stations with the section length equal to 20 meters, theslope range of [−0.1, 0.1], and 10 levels for the vertical band. There is alsoone segment for the whole road and the arbitrary station is xm = 100. Byreplacing the control points in Equation 3.17, we haveys = y(0) = 7, ye = y(200) = 7 and ym = y(100) = 2.From (3.14), we have0 ≤ d ≤ 10. (3.18)423.4. Finding the optimal vertical alignment for quadratic ground profilesFrom (3.15), we have0 ≤ d ≤ 10. (3.19)From (3.16)0 ≤ d ≤ 10. (3.20)The intersection of the intervals (3.18), (3.19) and (3.20) isd ∈ [0, 10].As we want to minimize d, so d = 0 is the solution to the problem. Thisimplies that the road profile overlays the ground profile.Figure 3.10: The output of the single-haul, multi-haul and Softree API fora quadratic ground profile with 10 levels of vertical bandAs shown in Figure 3.10, the optimal vertical alignment of the single-haul, multi-haul and Softree API are the same as the ground profile.Case 2: When there is no intersection between the the ranges of d valuesfrom the inequalities (3.14), (3.15) and (3.16), which means that the problemis infeasible.To demonstrate Case 2, we consider the ground profile with the followingequationyn = 0.0028x2n − 0.56xn + 30,433.4. Finding the optimal vertical alignment for quadratic ground profileswhere there exists 11 stations with the section length of 20 meters. Theslope range is [−0.1, 0.1] and the vertical band consists of 10 levels. Thereis a segment for the whole road and the arbitrary station is xm = 100.After replacing the control points in the ground profile equation, we haveys = y(0) = 30, ye = y(200) = 30 and ym = y(100) = 2.From (3.14) and (3.15), we have23 ≤ d ≤ 33. (3.21)From (3.16), we have0 ≤ d ≤ 10. (3.22)So there is no intersection between these two intervals, meaning that thereis no feasible VA for the ground profile with the equation of,yn = 0.0028x2n − 0.56xn + 30with 10 levels of vertical band and the slope range of [−0.1, 0.1].Case 3: When d ∈ [d, d¯] s.t. 0 < d < d¯ : In this case, d will be the solutionto the problem, which means the best VA has the distance of d with theground profile at the arbitrary station xm.To study Case 3, we consider the ground profile with the equation of,yn = 0.0025x2n − 0.5xn + 25, (3.23)where there exists 9 stations with the section length equal to 20 meters.The station range is [0, 160] and the slope range is [−0.1, 0.1]. There are20 levels for the vertical band and one segment for the whole road. Thearbitrary station is xm = 60. After replacing the values in Equation (3.23),we haveys = y(0) = 25, ye = y(160) = 9 and ym = y(60) = 4.From (3.14), we have15 ≤ d ≤ 22.5.From (3.15), we have7.5 ≤ d ≤ 15,443.4. Finding the optimal vertical alignment for quadratic ground profilesand from (3.16)0 ≤ d ≤ 20.The intersection of the above intervals is d = 15, which means that the bestVA has the distance of 15 meters with the ground profile at the arbitrarystation xm = 60.The optimal VA returned by the models has the equation of,y′n = 0x2n − 0.1xn + 25.From the above equation, the elevation of the road profile at the stationxm = 60 is y′60 = 19 and the ground elevation of the station xm = 60 isy60 = 4. Therefore, the difference between the road profile and the groundprofile at the station xm = 60 is d = 15 meters. Station No.: 60 d = 15 m Figure 3.11: The optimal VA for a quadratic ground profile with 20 levelsof vertical band3.4.1 Finding the optimal vertical alignment - simplifiedversionTo simplify (3.14) and (3.15), without loss of generality, let suppose thatthe station range is [−∆,∆] and the arbitrary station xm = 0. Consideringthis, (3.14) can be simplified as453.4. Finding the optimal vertical alignment for quadratic ground profiles3y(−∆) + y(∆)− 2m∆4− c ≤ d ≤ 3y(−∆) + y(∆) + 2m∆4− c. (3.24)Similarly, 3.15 can be written as3y(∆) + y(−∆)− 2m∆4− c ≤ d ≤ 3y(∆) + y(−∆) + 2m∆4− c. (3.25)So the problem of finding the difference between the optimal road profileand the ground profile for convex quadratic ground profiles can be writtenasmin ds.t.3y(−∆) + y(∆)− 2m∆4− c ≤ d ≤ 3y(−∆) + y(∆) + 2m∆4− c,3y(∆) + y(−∆)− 2m∆4− c ≤ d ≤ 3y(∆) + y(−∆) + 2m∆4− c,0 ≤ d ≤ nl.(3.26)If y(−∆) = y(∆), the optimization problem (3.26) can further be sim-plified tomin ds.t.4y(∆)− 2m(∆)4− c ≤ d ≤ 4y(∆) + 2m∆4− c,0 ≤ d ≤ nl.(3.27)46Chapter 4Spline ground profilesIn the previous chapter, we studied the single-segment ground profiles,focusing on flat, linear and quadratic types. In this chapter, we want tofind out whether we can extend this work and take a further step to studymulti-segment (spline) ground profiles. Since the spline ground profiles aremore complex than single-segment ones, we consider the simplest case: first,the profile consists of two consecutive quadratic ground profiles. Second, theconnecting station of two spline segments is considered as a middle controlpoint. Given these assumptions, the hypothesis is that the spline groundprofiles should be easy to analyze.In this chapter, we study four different examples of spline ground profileswith blank templates. The objective is to check whether the output ofthe single-haul, multi-haul models and the Softree API is as expected forthese examples. Despite studying the simplest case, we see some subtlecomplications can arise.Example 1: Both of the spline segments satisfy the slope constraints.Suppose that both of the spline segments satisfy the slope constraintsand C0 continuity constraint (1.8), but they do not satisfy the C1 continuityconstraint (1.9).Let the first spline segment have the equation of,y1 = 0.0004x2 − 0.04x, (4.1)where it consists of 11 stations with the section length of 10 meters. Theinitial station is 0, the slope range is [−0.1, 0.1] and the vertical band has10 levels.The slope of the first spline segment has the equation of,m(x) = 0.0008x− 0.04.Therefore, the slope of the control points is as follows,m(0) = −0.04 ∈ [−0.1, 0.1],m(100) = 0.04 ∈ [−0.1, 0.1].47Chapter 4. Spline ground profilesTherefore, the first spline segment satisfies the slope constraints.Let the second spline segment have the equation of,y2 = −0.0016x2 + 0.4x− 24, (4.2)where it has 11 stations with the section length of 5 meters and the initialstation is 100.The slope of the second spline segment has the equation of,m(x) = −0.0032x + 0.4So the slope of the control points is as follows,m(100) = 0.08 ∈ [−0.1, 0.1],m(150) = −0.08 ∈ [−0.1, 0.1].Therefore, the second spline segment satisfies the slope constraints.As discussed, we consider the connecting station of the two spline seg-ments as a control point, where both of the spline segments must satisfy bothof the slope and continuity constraints. Since the spline segments are con-secutive, the elevation of both is the same at the connecting control point.The first segment has the slope of 0.04 at the station 100, but the secondsegment has the slope of 0.08 at this station. So, the spline segments donot satisfy the C1 continuity constraint. Consequently, the ground profilecannot be the optimal VA.As the goal is to minimize the optimization cost and both of the splinesegments satisfy the slope constraints, in this example, the spline segmentwith the larger curve length will remain intact. However, the small splinesegment will change such that it reaches the same slope as the larger splinesegment at the connecting control point. In this example, the first splinesegment with the larger curve length has the slope of 0.04 at the station100. So, it will not change in the road profile but the second spline segmentwith the smaller curve length will change so as to have the slope of 0.04 atthe station 100 in the road profile. In this way, both of the spline segmentswill satisfy the slope and continuity constraints in the road profile withthe minimum optimization cost. The smaller spline segment will have thefollowing equation in the road profile,y′2 = −0.0008x2 + 0.2x− 12.Figure 4.1 represents the spline segments of the ground and road profilesfor the Example 1. As shown in Figure 4.1, the spline segment with larger48Chapter 4. Spline ground profilescurve length will remain intact whereas the spline segment with smallercurve length will change such that the road profile satisfies the C1 continuityconstraint.Figure 4.1: The optimal VA for a spline ground profile while spline segmentssatisfy slope constraintsFrom Figure 4.1, it can be seen that the VA generated by QNF, MQNFand Softree API has the expected output.Example 2: The smaller spline segment satisfies the slope constraints.In this example, the spline segment with the smaller curve length satisfiesthe slope constraints but the larger spline segment does not.Let the first spline segment have the equation of,y1 = 0.008x2 − 0.8x, (4.3)where it has 11 stations and the section length is 10 meters. The initialstation is 0, the slope range is [−0.1, 0.1] and the vertical band has 20 levels.The slope of the first spline segment has the equation of,m(x) = 0.016x− 0.8.Therefore, the slope of the control points is as follows,m(0) = −0.8 /∈ [−0.1, 0.1],m(100) = 0.8 /∈ [−0.1, 0.1].49Chapter 4. Spline ground profilesTherefore, the first spline segment does not satisfy the slope constraints.Let the second spline segment have equation,y2 = −0.0016x2 + 0.4x− 24, (4.4)where there exists 11 stations with the section length of 5 meters and theinitial station is 100.The slope of the second spline segment has equation,m(x) = −0.0032x + 0.4.Therefore, the slope of the control points is,m(100) = 0.08 ∈ [−0.1, 0.1],m(150) = −0.08 ∈ [−0.1, 0.1].Therefore, the second spline segment satisfies the slope constraints.The first segment has the slope of 0.8 at the station 100 but the secondsegment has the slope of 0.08 at this station. So, the spline segments do notsatisfy the C1 continuity constraint.For this example, there are two different scenarios that can occur. In thefirst scenario, it is supposed that the smaller spline segment that satisfiesthe slope constraints will stay the same. However, the larger spline segmentwill reach to the same slope as the smaller one at the connecting controlpoint, which is equal to 0.08 at the station 100. Therefore, the larger splinesegment will have equation,y′1 = 0.0008x2 − 0.08x,where the slope is 0.08 at Station 100.For Scenario 1, the area between the road and ground profiles is com-puted as follows,Area =∫ 1000(0.0008x2 − 0.08x− [0.008x2 − 0.8x])dx,Area =∫ 1000(−0.0072x2 + 0.72x)dx,Area = 1200.In the second scenario, we assume that both of the spline segments inthe road profile have the same slope as the value of the slope boundaries atthe control points. For this example, the first spline segment reaches to the50Chapter 4. Spline ground profilesslope of −0.1 and 0.1 and the second one reaches the slope of 0.1 and −0.1at their beginning and ending control points, respectively. Therefore, thefirst spline segment in the road profile has equation,y′1 = 0.001x2 − 0.1x,and the second spline segment in the road profile has equation,y′2 = −0.002x2 + 0.5x− 30.For this scenario, the area between the road and ground profiles is calculatedas follows,Area =∫ 1000(0.001x2 − 0.1x− [0.008x2 − 0.8x])dx,+∫ 150100(−0.002x2 + 0.5x− 30− [−0.0016x2 + 0.4x− 24])dx,Area =∫ 1000(−0.007x2 + 0.7x)dx +∫ 150100(−0.00042 + 0.1x− 6)dx,Area = 1175.In this example, the area between the road and ground profiles in the secondscenario is less than the first one. As a result, the second scenario has thelower cost.In order to check the models, we create the ground profiles with (4.3)and (4.4) using Roadents and compare the results of the models with theresults of the second scenario. Figure 4.2 shows that the models generatethe optimal VA as expected in the second scenario.51Chapter 4. Spline ground profilesFigure 4.2: The optimal VA for a spline segment while the smaller segmentsatisfies the slope constraintsExample 3: The larger spline segment satisfies the slope constraints.In this example, the spline segment with the larger curve length satisfiesthe slope constraints whereas the smaller one does not.The equation of the first spline segment is,y1 = 0.0004x2 − 0.04x (4.5)where it has of 11 stations with the section length of 10 meters. The initialstation is 0, the slope range is [−0.1, 0.1] and the vertical band has 20 levels.The slope of the first spline segment has equation,m(x) = 0.0008x− 0.04Therefore, the slope of the control points is,m(0) = −0.04 ∈ [−0.1, 0.1],m(100) = 0.04 ∈ [−0.1, 0.1].Therefore, the first spline segment satisfies the slope constraints.Let the second spline segment has equation,y2 = −0.0048x2 + 1.2x− 72, (4.6)where there exists 11 stations and the section length is 5 meters. The initialstation is 100.52Chapter 4. Spline ground profilesThe slope of the second spline segment has equation,m(x) = −0.0096x + 1.2Therefore, the slope of the control points is as follows,m(100) = 0.24 /∈ [−0.1, 0.1],m(150) = −0.24 /∈ [−0.1, 0.1].Therefore, the second spline segment does not satisfy the slope constraints.The first segment has the slope of 0.04 at the station 100 but the secondsegment has the slope of 0.24 at this station. So, the spline segments doesnot satisfy the C1 continuity constraint.Like Example 2, we will discuss two different scenarios. In the firstscenario, we suppose that the spline segment with the larger curve lengththat satisfies the slope constraints will remain the same but the smallerspline segment reaches the same slope as the larger spline segment at theconnecting control point, which is equal to 0.04 at station 100. Therefore,the smaller spline segment has equation,y′2 = −0.0008x2 + 0.2x− 12,which has the slope of 0.04 at station 100.For this scenario, we calculate the area between the road and groundprofiles.Area =∫ 150100(−0.0048x2 + 1.2x− 72− [−0.0008x2 + 0.2x− 12])dx,Area =∫ 150100(−0.004x2 + x− 60)dx,Area = 83.33For the second scenario, we assume that both of the spline segmentsreach to the same slope as the value of the slope boundaries at their controlpoints. Consequently, the first spline segment has the slope of −0.1 and 0.1at the stations 0 and 100, respectively. The slope of the second spline hasthe values of 0.1 at station 100 and −0.1 at station 150. Therefore, the firstspline segment has equation,y′1 = 0.001x2 − 0.1x,53Chapter 4. Spline ground profileswhich has the slope of 0.1 at station 100. The equation of the second splinesegment in the road profile is as follows,y′2 = −0.002x2 + 0.5x− 30The area between the road and ground profiles for the second scenariois as follows,Area =∫ 1000(0.004x2 − 0.04x− [0.001x2 − 0.1x])dx+∫ 150100(−0.0048x2 + 1.2x− 72− [−0.002x2 + 0.5x− 30])dx,Area =∫ 1000(0.003x2 + 0.06x)dx +∫ 150100(−0.0028x2 + 0.7x− 42)dx,Area = 1358.33In this example, the area between the road and ground profiles in the firstscenario is less than the second one, which means that less volume of earthneeds to be moved in the first scenario. Consequently, first scenario haslower cost compared to the second one.Using Roadents, we generate the ground profiles with (4.5) and Equa-tion (4.6) and compare the outputs of the models with the outputs of thefirst scenario to validate our models. The spline segments of the ground androad profiles for the Example 3 can be seen in Figure 4.3.Figure 4.3: The optimal VA for a spline segment while the larger segmentsatisfies the slope constraints54Chapter 4. Spline ground profilesFrom Figure 4.3, it can be shown that QNF, MQNF and Softree APIgenerate the expected VA.Example 4: None of the spline segments satisfy the slope constraints.In this example, none of the spline segments satisfy the slope constraints.Let the first spline segment have equation,y1 = 0.008x2 − 0.8x, (4.7)where there exists 11 stations with the section length of 10 meters. Theinitial station is 0, the slope range is [−0.1, 0.1] and the vertical band has20 levels.The slope of the first spline segment has equation,m(x) = 0.016x− 0.8.Therefore, the slope of the control points is,m(0) = −0.8 /∈ [−0.1, 0.1],m(100) = 0.8 /∈ [−0.1, 0.1].So the first spline segment does not satisfy the slope constraints.Let the second spline segment have equation,y2 = −0.016x2 + 4x− 240, (4.8)where it consists of 11 stations with the section length of 5 meters and theinitial station is 100.The slope of the second spline segment has equation,m(x) = −0.032x + 4.So the slope of the control points is,m(100) = 0.8 /∈ [−0.1, 0.1],m(150) = −0.8 /∈ [−0.1, 0.1].Therefore, the second spline segment does not satisfy the slope constraintstoo.Both of the spline segments have slope 0.8 at station 100. Therefore,they satisfy the C1 continuity constraint.The slope boundaries are the maximum values for the slope that sat-isfy the slope constraints. Consequently, in this example, we can have the55Chapter 4. Spline ground profilesminimum optimization cost provided that both of the spline segments havethe same slope as the value of the slope boundaries at their control points.Therefore, the first spline segment has the following equation in the roadprofile,y′1 = 0.001x2 − 0.1x,which has the slopes of −0.1 and 0.1 at the stations 0 and 100, respectively.The second spline segment will have equation,y′2 = −0.002x2 + 0.5x− 30,that has the slopes of 0.1 at station 100 and the slope of −0.1 at 150.Figure 4.4 presents the spline segments of the ground and road profilesfor Example 4.Figure 4.4: The optimal VA for a spline segment while none of the segmentssatisfies the slope constraintsFrom Figure 4.4, it can be shown that the outputs of QNF, MQNF andSoftree API are as expected.As shown in Examples 1-4, the hypothesis that two segment splineground profiles with a control point in the middle are easy to solve is notactually correct as we have to consider many different scenarios. More im-portantly, based on this fact we can also conclude that the spline segmentground profile in general is surprisingly complex to study.564.1. Summary of the results for spline ground profiles4.1 Summary of the results for spline groundprofilesThe optimal alignment for a spline ground profile is determined by look-ing at the integral of the difference between the road and ground profilesand minimizing it. We can see that this integral for each segment has 6parameters, which are the coefficients of the road and ground profiles. Thevalue of those parameters will be influenced by the width and height of eachsegment.If we relax our curve types even further, then more parameters will comeinto play and the integral will become more difficult to compute. Therefore,we conclude that analyzing these styles of curves is much more complicatedthan we expected.57Chapter 5Numerical ExperimentationIn this chapter, the optimal vertical alignments generated by QNF,MQNF, and Softree API are evaluated over 10,000 quadratic ground profileswith different specifications.For carrying out this experiment, we run Roadents on a workstationPC with Windows 10, 64 bits. It is equipped with Intel Core i7 2.8 GHzCPU with 16 GB RAM.5.1 MethodologyThe process of evaluating the VA models is as follows. First, we cre-ate 10,000 quadratic ground profiles using Roadents multi ground profilegenerator component with different specifications. Figure 5.1 shows thespecifications for building 10,000 quadratic ground profiles.Figure 5.1: Specifications for creating 10000 quadratic ground profiles585.2. ResultsThen, we select all these ground profiles in the Roadents VA evaluatorsection. We make sure that both Automated model settings and Computedifference of ground and road profiles options are checked. Next, Roadentscalls every VA model when a problem is ready to be solved, and as soon asthe problem is solved, the VA model lets Roadents know that the problemis solved.Finally, after solving the problems, Roadents runs a process that cal-culates the difference between the ground and road profiles at the middlestation for each solver. It also computes the predicated difference betweenthe ground and road profiles at the same station using the technique de-veloped in Section 3.4. Roadents also calculates the difference betweenthe outputs of these two processes. We call the former process Diff1 andthe later Diff2. We then examine (Diff1−Diff2). Theoretically this valueshould be 0 to the numerical precision of the VA solver. Note that we usethe default numerical precision of 1e-04.5.2 ResultsTable 5.1 represents the summary results of QNF, MQNF and SoftreeAPI on 10,000 quadratic ground profiles where Mean and Std are the averageand standard deviations of (Diff1−Diff2).All the quadratic ground profilesSolver Mean(Diff1−Diff2) Std(Diff1−Diff2)QNF 2.48e-05 1.37e-05MQNF 2.48e-05 1.37e-05Softree API 1.42e-14 1.53e-14Table 5.1: The average and standard deviations of (Diff1−Diff2)As shown in Table 5.1, the mean and the standard deviations of theresults of QNF, MQNF and Softree API are less than the numerical precisionof the VA solver. Consequently, we can state that the QNF, MQNF andSoftree API generate the expected optimal VA.59Chapter 6ConclusionGenerating ground profiles with different characteristics is a dauntingtask, especially when a myriad of ground profiles are needed. To handlethis problem, a software package called Roadents (ROAd DEsigN TestingSoftware) was introduced in this thesis. Using Roadents users are able togenerate numerous ground profiles with different attributes.Roadents is a VA model checker, a ground profile generator, a VAvisualizer, and a .CSV area converter. In the road design optimization,every VA model accepts a ground profile in a specific format. By employingRoadents, users can convert the format of the ground profiles into thedesired format very quickly and efficiently. To the best of our knowledge,this is the first software to automatically check whether the output splineof VA models is correct or not. With Roadents in hands, researchers cantest and check the output of their models even in the early stage of theirdevelopment.To test the output of Quasi Network Flow (QNF), Multi-haul Quasi Net-work Flow (MQNF) and Softree API (V2) using Roadents, the RoadentsVA Evaluator software component was used. The results showed that themodels generated the expected output spline segments over 10,000 differentquadratic ground profiles. This provides a strong confidence that the modelsare implemented properly.Recommendations for future researchWhile Roadents provides great features in terms of ground profile gen-eration, VA checking and VA visualizing, there is still room for further im-provement.In the Roadents multi-ground profile generator, we only consideredsingle-segment quadratic ground profile. While this assumption facilitatesthe process of generating feasible ground profiles, it may limit us to test theVA models further.Furthermore, Roadents only generates single-material ground profiles.Roadents could be advance to allow generation of VA models not just on60Chapter 6. Conclusionsingle-material ground profiles, but also on multi-material ones.Roadents does not consider templates when generating ground profiles.It means that in every section, from the rightmost vertical offset to theleftmost offset, we have a flat surface in every level. However, in real-worldground profiles, it may not be the case. As discussed in Section 3.1, a real-world ground may contain one or multiple templates, which means that weneed to consider cross-sections for calculating the cost. By taking templatesinto account, Roadents can create more realistic ground profiles.In Chapter 4, we studied two-segment spline ground profiles with a mid-dle control point. However, to allow more complete testing, we can investi-gate multi-segment segment ground profiles.Finally, to make Roadents available and easy-to-use, we can deploy iton cloud as a native cloud app, so all researchers can use it without having toinstall an array of software on their workstations. However, we should keepin mind that using Roadents on cloud brings licensing issues at least forCPLEX. To address this issue, we can consider business or network license.61Bibliography[1] Abdullah E Akay. Minimizing Total Cost of Construction, Mainte-nance, and Transportation Costs with Computer-Aided Forest Road De-sign. PhD thesis, Oregon State University, 2003. → pages 4[2] Mahdi Aziz. Multi-fidelity algorithms for the horizontal alignment prob-lem in road design. MSc Thesis, University of British Columbia, 2018.→ pages 3[3] Vahid Beiranvand, Warren Hare, Yves Lucet, and Shahadat Hossain.Multi-haul quasi network flow model for vertical alignment optimiza-tion. Engineering Optimization, 49(10):1777–1795, 2017. → pages 4,10[4] Gerardo Casal, Duarte Santamarina, and Miguel E Va´zquez-Me´ndez.Optimization of horizontal alignment geometry in road design and re-construction. Transportation Research Part C: Emerging Technologies,74:261–274, 2017. → pages 3[5] Said M Easa. Earthwork allocations with nonconstant unit costs. Jour-nal of Construction Engineering and Management, 113(1):34–50, 1987.→ pages 4[6] Said M Easa. Selection of roadway grades that minimize earthwork costusing linear programming. Transportation Research Part A: General,22(2):121–136, 1988. → pages 4[7] Eric Evans. Domain-driven design: tackling complexity in the heart ofsoftware. Addison-Wesley Professional, 2004. → pages 13[8] Richard Fabian. Data-oriented Design: Software Engineering for Lim-ited Resources and Short Schedules. Richard Fabian, 2018. → pages12[9] Chong Jin Goh, EP Chew, and TF Fwa. Discrete and continuous mod-els for computation of optimal vertical highway alignment. Transporta-62Chapter 6. Bibliographytion Research Part B: Methodological, 22(6):399–409, 1988. → pages4[10] Warren Hare, Yves Lucet, and Faisal Rahman. A mixed-integer lin-ear programming model to optimize the vertical alignment consideringblocks and side-slopes in road construction. European journal of oper-ational research, 241(3):631–641, 2015. → pages 4, 10[11] Warren L Hare, Valentin R Koch, and Yves Lucet. Models and al-gorithms to improve earthwork operations in road design using mixedinteger linear programming. European Journal of Operational Research,215(2):470–480, 2011. → pages 4[12] Softree Technical Systems Inc. API user documentation, 2019. → pages22[13] Softree Technical Systems Inc. Softree location software, 2019. → pages28[14] Manoj Kumar Jha, Manoj Kumar Jha, PM Schonfeld, and J-C Jong.Intelligent road design, volume 19. Wit Press, 2006. → pages 1[15] Paul C. Jorgensen. Software Testing: A Craftsman’s Approach. Auer-bach Publications, Boston, MA, USA, 3rd edition, 2008. → pages 12[16] Valentin R Koch and Yves Lucet. A note on: Spline technique for mod-eling roadway profile to minimize earthwork cost. Journal of Industrial& Management Optimization, 6(2):393–400, 2010. → pages 4[17] Shivprasad Koirala. Learn regular expressions (regex) with ease, 2014.→ pages 16[18] Yusin Lee and Juey-Fu Cheng. Optimizing highway grades to minimizecost and maintain traffic speed. Journal of transportation engineering,127(4):303–310, 2001. → pages 4[19] Kurt Mehlhorn, Stefan Na¨her, Michael Seel, Raimund Seidel, ThomasSchilz, Stefan Schirra, and Christian Uhrig. Checking geometric pro-grams or verification of geometric structures. Computational Geometry,12(1-2):85–103, 1999. → pages 12[20] Sukanto Mondal. Horizontal alignment optimization in road design.MSc Thesis, University of British Columbia, 2014. → pages viii, 3, 6,2163Chapter 6. Bibliography[21] Ahmad A Moreb. Linear programming model for finding optimal road-way grades that minimize earthwork cost. European Journal of Opera-tional Research, 93(1):148–154, 1996. → pages 4[22] Ahmad A Moreb. Spline technique for modeling roadway profile tominimize earthwork cost. Journal of Industrial & Management Opti-mization, 5(2):275–283, 2009. → pages 4[23] Ahmad A Moreb and Mohammad S Aljohani. Quadratic representationfor roadway profile that minimizes earthwork cost. Journal of SystemsScience and Systems Engineering, 13(2):245–252, 2004. → pages 4[24] Hao Pu, Taoran Song, Paul Schonfeld, Wei Li, Hong Zhang, JianpingHu, Xianbao Peng, and Jie Wang. Mountain railway alignment opti-mization using stepwise & hybrid particle swarm optimization incorpo-rating genetic operators. Applied Soft Computing, 78:41–57, 2019. →pages 3[25] J. Puy Huarte. Opygar. Optimization and automatic design of highwayprofiles. In 1973 In PTRC Seminar Proceedings on Cost Models andOptimization in Highways, page 9, 1973. → pages 4[26] Md. Faisal Rahman. Optimizing the vertical alignment under earthworkblock removal constraints in road construction. MSc Thesis, Universityof British Columbia, 2012. → pages 8[27] Robert M. Stark and R.L. Nicholls. Mathematical foundations for de-sign: civil engineering systems. Number v. 1. McGraw-Hill, 1971. →pages 4[28] Cesar de la Torre. .NET Microservices: Architecture for Containerized.NET Applications. Number v. 2.2.1. Microsoft Corporation, 2019. →pages 2564
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
ROADENTS (ROAd DEsigN Testing Software)
Text
Moving Image