Science, Irving K. Barber Faculty of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Ayman, Khandoker Md
Master of Science - MSc
University of British Columbia
The vertical alignment optimization problem for road design focuses on finding the optimum vertical alignment of a single road with a minimum cost considering earthwork and satisfying all safety and design constraints. We proposed a new model named the multi-road quasi network flow model (MR-QNF) for vertical alignment optimization of the entire road network instead of just a single road. We then presented four different methods: one-at-a-time, no-flow, with-flow and divide and conquer methods to solve the vertical alignments of a road network. Here, the one-at-a-time method uses the old model named quasi network flow model (QNF) and is considered as the base model for comparison. The other three methods use the new MR-QNF model to solve this problem. We evaluated the performances of these methods on two real-world road network examples: one small road network (total road length is around 6 km) and one comparatively extensive road network (total length is around 66 km). The numerical results show that in the case of a small road network, it is possible to lower the total cost by 7.2\% by using the with-flow method and a speedup of 20 was achieved when compare to the one-at-a-time method. However, in the case of an extensive road network, the computation time of the one-at-a-time method is significantly lower than the other two methods without any notable differences in their costs.
A Multi-Road Quasi Network FlowModel for Vertical AlignmentOptimization of a Road NetworkbyKhandoker Md AymanB.Sc., American International University-Bangladesh, 2017A 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)July 2021© Khandoker Md Ayman, 2021The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis entitled:AMulti-Road Quasi Network FlowModel for Vertical Align-ment Optimization of a Road Networksubmitted by Khandoker Md Ayman in partial fulfillment of the require-ments of the degree of Master of Science.Dr. Yves Lucet, Irving K. Barber Faculty of ScienceSupervisorDr. Warren Hare, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Mohammad Khalad Hasan, Irving K. Barber Faculty of ScienceSupervisory Committee MemberDr. Gord Lovegrove, School of EngineeringUniversity ExamineriiAbstractThe vertical alignment optimization problem for road design focuses onfinding the optimum vertical alignment of a single road with a minimumcost considering earthwork and satisfying all safety and design constraints.We proposed a new model named the multi-road quasi network flow model(MR-QNF) for vertical alignment optimization of the entire road networkinstead of just a single road. We then presented four different methods: one-at-a-time, no-flow, with-flow and divide and conquer methods to solve thevertical alignments of a road network. Here, the one-at-a-time method usesthe old model named quasi network flow model (QNF) and is considered asthe base model for comparison. The other three methods use the new MR-QNF model to solve this problem. We evaluated the performances of thesemethods on two real-world road network examples: one small road network(total road length is around 6 km) and one comparatively extensive roadnetwork (total length is around 66 km). The numerical results show thatin the case of a small road network, it is possible to lower the total cost by7.2% by using the with-flow method and a speedup of 20 was achieved whencompare to the one-at-a-time method. However, in the case of an extensiveroad network, the computation time of the one-at-a-time method is signifi-cantly lower than the other two methods without any notable differences intheir costs.iiiLay SummaryWe proposed a new model to minimize the total construction cost ofbuilding an entire road network. We then presented four different methodsto solve this model. One of these methods uses the old model to solve theroad network problem and is considered as the base model for comparison.The other three methods use the new model to solve this problem. Numericalexperiments were performed on two real-world road network examples, andthe results show that in the case of a small road network, the new model wasable to lower the total cost by 7.2% compare to the old model. However,in the case of a more extensive road network, the computation time of theold model was significantly faster than the new model without any notabledifferences in their costs.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Road design optimization . . . . . . . . . . . . . . . . . . . . 11.1.1 Corridor selection . . . . . . . . . . . . . . . . . . . . 21.1.2 The horizontal alignment optimization . . . . . . . . . 21.1.3 The vertical alignment and earthwork optimization . . 31.1.4 The three dimensional alignment optimization . . . . 51.2 Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . . 6Chapter 2: Multi-road quasi network flow model . . . . . . . . 82.1 Model definitions and parameters . . . . . . . . . . . . . . . . 82.2 Multi-road quasi network flow model . . . . . . . . . . . . . . 112.2.1 Model description . . . . . . . . . . . . . . . . . . . . 122.2.2 Cost parameters . . . . . . . . . . . . . . . . . . . . . 142.2.3 Objective function . . . . . . . . . . . . . . . . . . . . 152.2.4 Constraints . . . . . . . . . . . . . . . . . . . . . . . . 152.3 Different methods to solve the road network problem . . . . . 202.3.1 One-at-a-time method . . . . . . . . . . . . . . . . . . 20vTable of Contents2.3.2 No-flow method . . . . . . . . . . . . . . . . . . . . . . 222.3.3 With-flow method . . . . . . . . . . . . . . . . . . . . 232.3.4 Divide and conquer method . . . . . . . . . . . . . . . 23Chapter 3: Numerical experiments and results . . . . . . . . . 263.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . 263.2 MR-QNF input format . . . . . . . . . . . . . . . . . . . . . . 273.3 Experimental results of the academic cases . . . . . . . . . . 313.3.1 Academic case one . . . . . . . . . . . . . . . . . . . . 313.3.2 Academic case two . . . . . . . . . . . . . . . . . . . . 323.4 Experimental results of the real-world examples . . . . . . . . 353.4.1 Example one . . . . . . . . . . . . . . . . . . . . . . . 353.4.2 Example two . . . . . . . . . . . . . . . . . . . . . . . 373.5 Discussion and Recommendation . . . . . . . . . . . . . . . . 42Chapter 4: Conclusion and future work . . . . . . . . . . . . . 434.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2 Future research . . . . . . . . . . . . . . . . . . . . . . . . . . 434.2.1 Three dimensional road network design optimization . 434.2.2 Multi-material and multi-haul extension . . . . . . . . 444.2.3 Other areas of improvement . . . . . . . . . . . . . . . 44Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Appendix A: Unit tests . . . . . . . . . . . . . . . . . . . . . . . . 50A.1 Unit test 1 (linear road) . . . . . . . . . . . . . . . . . 50A.2 Unit test 2 (single intersection) . . . . . . . . . . . . . 51A.3 Unit test 3 (multiple intersections) . . . . . . . . . . . 51A.4 Unit test 4 (single loop) . . . . . . . . . . . . . . . . . 52A.5 Unit test 5 (multiple loops) . . . . . . . . . . . . . . . 53Appendix B: Class diagram of the MR-QNF model . . . . . . . . . 54Appendix C: Design parameters of the academic cases . . . . . . . 55C.1 Academic case two . . . . . . . . . . . . . . . . . . . . 55viList of TablesTable 3.1 Cost components in $/cubic meter. . . . . . . . . . . . 27Table 3.2 Old input format. . . . . . . . . . . . . . . . . . . . . . 27Table 3.3 New input format. . . . . . . . . . . . . . . . . . . . . 28Table 3.4 Results of the one-at-a-time method (Academic caseone). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32Table 3.5 Comparison of results for different methods (Academiccase one). . . . . . . . . . . . . . . . . . . . . . . . . . 32Table 3.6 Results of the one-at-a-time method (Academic casetwo). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Table 3.7 Comparison of results for different methods (Academiccase two). . . . . . . . . . . . . . . . . . . . . . . . . . 34Table 3.8 Comparison of results for ten different random sequencesof roads in one-at-a-time method (Real case one). . . . 36Table 3.9 Comparison of results for different initial road in one-at-a-time method (Real case one). . . . . . . . . . . . 37Table 3.10 Comparison of results for different methods (Real caseone). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Table 3.11 Comparison of results for all sequences of roads in one-at-a-time method (Real case two). . . . . . . . . . . . 39Table 3.12 Comparison of results for different methods (Real casetwo). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Table 3.13 Comparison of results for using the divide and conquermethod (Real case two). . . . . . . . . . . . . . . . . . 41Table C.1 Design parameters of the academic case two. . . . . . 55viiList of FiguresFigure 1.1 An example of a corridor. . . . . . . . . . . . . . . . . 2Figure 1.2 Different horizontal alignments for a specified corridor. 3Figure 1.3 A potential vertical alignment for a ground profile. . . 4Figure 2.1 A side view of the vertical alignment of a road profile. 9Figure 2.2 The cross section area of a cut section with and with-out side-slopes. . . . . . . . . . . . . . . . . . . . . . . 10Figure 2.3 The cross section area of a fill section with and with-out side-slopes. . . . . . . . . . . . . . . . . . . . . . . 11Figure 2.4 The cross section area of a section with side-slopesafter approximation. . . . . . . . . . . . . . . . . . . . 11Figure 2.5 A typical section a of road A in MR-QNF model sameas QNF model. . . . . . . . . . . . . . . . . . . . . . . 12Figure 2.6 A typical intersection e of a road network in MR-QNFmodel. . . . . . . . . . . . . . . . . . . . . . . . . . . 13Figure 3.1 Horizontal alignments of the academic cases. . . . . . 31Figure 3.2 Optimized vertical alignments of three roads in aca-demic case one using with-flow method. . . . . . . . . 33Figure 3.3 Optimized vertical alignments of three roads in aca-demic case two using with-flow method. . . . . . . . . 34Figure 3.4 Real-world road network example 1. . . . . . . . . . . 35Figure 3.5 Real-world network example case 2. . . . . . . . . . . 39Figure A.1 Road design of unit test 1. . . . . . . . . . . . . . . . 51Figure A.2 Road network design of unit test 2. . . . . . . . . . . 51Figure A.3 Road network design of unit test 3. . . . . . . . . . . 52Figure A.4 Road network design of unit test 4. . . . . . . . . . . 52Figure A.5 Road network design of unit test 5. . . . . . . . . . . 53Figure B.1 Class diagram of the MR-QNF model . . . . . . . . . 54viiiAcknowledgementsI would like to thank my supervisor Dr. Yves Lucet and co-supervisor Dr.Warren Hare for their continuous support and help throughout the project.Their knowledge and guidance were essential to successfully complete thisthesis.I would also like to thank our industry partner (Softree Technical Sys-tems Inc.) for their support by providing technical information and valuablefeedback in this research.I am also thankful to the University of British Columbia for providingme with financial support through Graduate Deans Entrance Scholarship(GDES) and University Graduate Fellowship Award (UGF). This researchwas also partially funded by the Natural Sciences and Engineering ResearchCouncil (NSERC) of Canada through Collaborative Research and Devel-opment (CRD) Grant #CRDPJ 479316-15 sponsored by Softree TechnicalSystems Inc.Part of the computation in this research was carried out using a soft-ware library provided by Softree Technical System Inc. Part of the researchwas performed in the Computer-Aided Convex Analysis (CA2) laboratoryfunded by a Leaders Opportunity Fund (LOF, John R. Evans Leaders Fund,Funding for research infrastructure) from the Canada Foundation for In-novation (CFI) and by a British Columbia Knowledge Development Fund(BCKDF).ixDedicationTo my parents and my wife.xChapter 1IntroductionRoads are one of the significant indications of the advancement of asociety through which the economy flourishes. They connect merchantsto markets, sick to hospitals, and workers to their jobs. In 2019 alone,Canadian households spent about $205.8 billion on transportation, which isthe second-largest expense, second only to shelter [oPWS19]. That is whysince 2016, the government of Canada has been investing over $180 billionin constructing new and maintaining existing transportation infrastructures[oPWS19]. As a result, there has been significant research on finding a wayto minimize the cost of constructing roads while at the same time satisfyingthe design, safety, environmental [Jha03], and socioeconomic constraints[DJ09].1.1 Road design optimizationDue to the inherently complex nature of the optimization of a road net-work model, most researchers use heuristic techniques ([Tan99], [RHB04],[JS04], [JS03]) and dynamic programming ([LPZL13], [Tan00]) to solve thismodel. Aruga et al. [ABS+13] presented different optimization techniquesfrom various authors in designing forest roads and road networks. Neverthe-less, none of the models in [ABS+13] can optimize the vertical alignmentsof an entire road network that includes intersection.In this research, the road design optimization problem focuses on mini-mizing the total construction cost while satisfying all the roads’ safety anddesign constraints in a road network. This cost is divided into five signif-icant costs: planning and administrative costs, construction cost, mainte-nance cost, user costs, and social and environmental cost [JSJ06]. Amongall these costs, construction cost is a critical component in designing a road.Hence, in our research, we minimize the total construction costs, mainly ex-cavation costs (cutting cost), embankment costs (filling cost), loading costs,and hauling costs for materials.Optimization of road design can be divided into four sub-problems: se-lecting the initial corridor, finding the horizontal alignment, computing the11.1. Road design optimizationvertical alignment, and earthwork optimization [HKL11]. This research pri-marily focuses on optimizing the vertical alignment and optimizing earth-work while keeping the horizontal alignment of a road network fixed.1.1.1 Corridor selectionThe initial step to construct a road is selecting a corridor on which theroad will be constructed. Figure 1.1 shows an example of a corridor in agiven terrain. Pushak et al. [PHL16] presented that a bidirectional selec-tion method and a hybrid of this method with k-shortest-paths adaptationalgorithm were the fastest and the most robust algorithm among five otheralgorithms for selecting an initial corridor. After selecting the initial corri-dor, horizontal alignment optimization can determine the road path withinthat corridor.Figure 1.1: An example of a corridor.1.1.2 The horizontal alignment optimizationHorizontal alignment optimization is the problem of finding the leastcost route between two endpoints in a given corridor satisfying all horizontaland vertical alignment design constraints to build the road. The horizontalalignment design usually consists of series of tangential lines and circulararcs. Figure 1.2 shows the different possible horizontal alignments for aspecified corridor.21.1. Road design optimizationFigure 1.2: Different horizontal alignments for a specified corridor.There has been numerous research on finding the best horizontal align-ment optimization problem. For example, in [MLH15] a new optimizationmodel was presented for optimizing the horizontal alignment of a road in agiven corridor. In this optimization model, the local optima were guaranteedby using derivative-free optimization (DFO) algorithms. However, the com-putation time of DFO algorithms is quite expensive. So Aziz et al. [AHJL20]presented a model using multi-fidelity algorithms to speed up the computa-tion time. In another study [YL16], the authors proposed a mixed-integerlinear programming model to determine a horizontal alignment by fixingthe vertical alignment of a road network. However, this model generatesa continuous road network that is non-smooth and only uses straight-linesegments for horizontal alignment.1.1.3 The vertical alignment and earthwork optimizationThe vertical alignment optimization problem finds the optimum verticalalignment of a road by solving the earthwork optimization problem satis-fying all the design and safety constraints for a predetermined horizontalalignment. As earthwork optimization depends on the vertical alignment,combining both these problems is very common as a single optimizationproblem. An example of a vertical alignment for a given ground profile isshown in Figure 1.3.Many models have been researched to solve this problem using both31.1. Road design optimizationFigure 1.3: A potential vertical alignment for a ground profile.non-deterministic and deterministic methods. For example, Lee and Cheng[LC01] presented a model using a three-layered heuristic technique to solvethe vertical alignment problem. Both Fwa et al. [FCS02] and Goktepe et al.[GLA09] proposed a model using genetic algorithms. However, these modelsuse non-deterministic techniques and thus will not always produce the samesolution for the same set of inputs.Deterministic algorithms will always produce the same solution for thesame set of inputs, and hence, there has been significant research using de-terministic algorithms to solve the vertical alignment problem. For example,Easa [Eas88] proposed a linear programming model for vertical alignment.This model enumerates all possible feasible grades and minimizes the to-tal earthwork operation cost to find the required vertical alignment. LaterMoreb [Mor96] presented a model that combines these two stages into onelinear programming model, thus guaranteeing global optimality. However,this model generates piecewise linear segments, thus making the road non-smooth. Hence, Moreb and Aljohani [MA04] proposed a model where theroad profile was represented using a quadratic function, thus removing thesharp connected ends of the linear segments. Nevertheless, one of the disad-vantages of using a piecewise quadratic representation is that it may createinflection points. So, in [Mor09] they improve the model by representing theroad profile by a univariate spline segment. Later, Koch and Lucet [KL10]41.1. Road design optimizationrefined the gap, and slope constraints of the [Mor09] model for removingunnecessary errors and showed that it is possible to maintain linearity upto a quadratic spline.Hare, Koch, and Lucet [HKL11] proposed a mixed-integer linear pro-gramming model for this problem, which also considers blocks such as moun-tains or rivers but does not consider any side slopes. Later, Hare, Lucet,and Rahman [HLR15] improved this model and added constraints for bothside slopes and blocks for earthwork operations using a quasi network flowmodel (QNF). However, this model considers only one type of material forearthwork operations. So, Hossain [Hos13] proposed a model that consid-ers multimaterial for vertical alignment optimization, and then Beiranvand,Hare, and Lucet [BHLH17] improved the model [Hos13, HLR15] and pro-posed a multi-haul quasi network flow model (MH-QNF) for the verticalalignment problem.Most of the previous research on optimizing road networks includes opti-mizing earthwork costs and finding the shortest path to move the earthworkmaterials for a fixed vertical alignment. For example, Liu and Lu [LL15]proposed a linear programming model with an integrated Floyd-Warshallalgorithm to find the shortest path to move earthwork materials. However,the road network’s horizontal alignments were predetermined in this model,and the vertical alignment was fixed. Hence, this model only optimizesthe movement of earthwork materials. Later, Yi and Lu [YL16] improvedthis model and presented a mixed-integer linear programming model witha cutting plane method for generating a continuous road network but for afixed vertical alignment. Besides, because it uses the cutting plane methoditeratively, this model [YL16] does not guarantee global optimality.1.1.4 The three dimensional alignment optimizationIn three dimensional (3D) alignment optimization problem, both thehorizontal and vertical alignments are optimized simultaneously, makingthis problem very hard. Moreover, the 3D alignment optimization problemis a non-linear non-convex problem. Hence, most of the researchers usenon-deterministic algorithms.Chew et al. [CGF89] first presented a model using three-dimensionalcubic spline polynomial functions and optimal control theory to generatea smooth 3D alignment of a road. However, this model is a constrainednon-linear optimization model and thus cannot guarantee global optimal-ity. Tat and Tao [TT03] used GIS and genetic algorithm to solve the 3Dalignment problem. Akay [Aka06] proposed a model using two optimization51.2. Thesis Overviewtechniques for solving this problem, namely, simulated annealing algorithmfor finding the optimal vertical alignment and linear programming for min-imizing earthwork costs. Aruga [Aru05] proposed a model using a tabusearch algorithm to simultaneously solve both the horizontal and verticalalignments from light detection and ranging data (LiDAR). Nonetheless,manually selected initial alignments are required to solve the problem suc-cessfully. Later, Aruga et al. [ATSM06] improved this model [Aru05] by us-ing Dijkstra’s shortest path algorithm and a cubic spline function for findingthe initial alignments instead of manually selecting these alignments. Li etal. [LPZL13] proposed a two-stage dynamic programming approach to solvethe 3D alignment. They formulated this problem as a network problem bya 3D search grid in the first stage and then solved this model using dy-namic programming to find the best corridor alignment. However, there isa possibility of deviation from the global optimum due to initial alignmentsresulting from the dynamic programming.Hirpa et al. [HHL+16] proposed a bi-objective optimization approachto solve the 3D road alignment problem by minimizing both earthwork andutility costs and showed that it is possible to attain the Pareto front in a rea-sonable amount of time. Zhang et al. [ZPS+20] proposed a multi-objectiveoptimization method that includes both economic and environmental objec-tives based on particle swarm optimization (PSO) algorithm to solve boththe vertical and horizontal alignment of a railway. A model based on a3D distance transform (3D-DT) algorithm was used in [LPS+16, PSS+19]to solve this problem where the terrain is located in mountainous regions.Later the model was improved in [SPS+20a] by parallelizing the 3D-DTalgorithm to reduce the computation time significantly without compromis-ing the quality of the results. The model was further improved by addinggeological hazard factors in [SPS+20b, PXS+21].1.2 Thesis OverviewThere has not been enough research on optimizing the vertical align-ments of all the roads in a road network instead of just a single road. Oneof the reasons is that the number of variables and constraints increase dra-matically in a road network model, making the problem even harder andcomputationally expensive. Hence, in this research, we improved the pre-vious quasi network flow (QNF) model [HKL11] for vertical alignment andearthwork optimization and proposed a multi-road quasi network flow (MR-QNF) model that can solve the entire road network. This proposed model61.2. Thesis Overviewalso considers side slopes for practical reasons and assumes that there areno blocks present. In this research, materials can only move through thehorizontal and vertical alignments of the roads and will not use any otheroff-roads.We implemented the proposed MR-QNF model in MATLAB [MAT18]using YALMIP optimization toolbox [Lo¨f04] and CPLEX [Cpl09] as the op-timization solver. We also created a new input format for our MR-QNFmodel as the previous input file can only contain information about a singleroad (see appendix C). We then also generated some unit tests (see ap-pendix 4.2.3) to validate our model. Next, we generated two small artificialroad networks (academic cases) to see that if there are any benefits for us-ing the proposed MR-QNF model over the QNF model. And finally, weexperimented our model with two real-world examples.The remainder of the thesis is structured as follows. First, chapter 2 dis-cusses the proposed multi-road quasi network flow model and four methodsto solve the road network problem. Then, in Chapter 3, we experimentedwith our model in two academic and two real-world road network examples.Finally, in Chapter 4, we conclude the thesis and suggest some future works.7Chapter 2Multi-road quasi networkflow modelThis chapter describes the variables, parameters, constraints, and setsrequired to model the vertical alignments and the optimization of the earth-work of a road network for known horizontal alignments. Then we describethe multi-road quasi network flow (MR-QNF) model, which can optimizethe road network as a single optimization problem. Most of the notationsdescribed here are taken from [BHLH17], [HHLR14], [Rah12]. We color thedecision variables of the optimization problem in red to differentiate themfrom the constants in the optimization model throughout this chapter.2.1 Model definitions and parametersLet R = {1, 2, ..., r} be the index set of roads where r is the total numberof roads in a road network. In QNF model, each road is divided into severalsections to model the VA. Let Si = {1, 2, ..., ni} be the index set of sectionsfor ith road. Each section has a station number and an effective length.Effective length is defined as the interval between the midpoints of previousand next stations. The difference between a station and a section is thata station is a point on the road and the section is a horizontal piece ofground stretched by the associated effective length. A segment is the intervalbetween two or more stations (sections) and is used to represent the roadprofile as a quadratic spline (see Figure 2.1). Let the set Gi = {1, 2, 3, ...,mi}represents all the segments for the ith road. So, each segment of a road canbe formulated asPi,g(x) = ai,g,1x2 + ai,g,2x+ ai,g,3 (2.1)where, g ∈ Gi, i ∈ R, and x is the distance from the beginning of the road.Here, Pi,g is a function of x which returns the elevation at the point x. Theoptimization model computes the coefficients of Pi,g, which is why they arecolored in red. The derivative of Pi,g(x) will return the slope of the starting82.1. Model definitions and parametersFigure 2.1: A side view of the vertical alignment of a road profile.or ending stations of a segment and can be written as,P ′i,g(x) = 2ai,g,1x+ ai,g,2. (2.2)The ith road’s gth spline segment consists of ni,g sections; it is indexedby the set Si,g = {1, 2, ..., ni,g}. A particular section index from set Si,g isthen mapped to the actual section index set Si by the function ψ : (R ×Gi × Si,g) → Si. For example, if ψ(i, g, j) = s then, xs = xψ(i,g,j) for alls ∈ Si, i ∈ R, j ∈ Si,g and g ∈ G. Now, the quadratic spline of road i can beformulated asPi(x) =Pi,1(x) if xi,ψ(i,1,1) ≤ x ≤ xi,ψ(i,1,ni,1),Pi,2(x) if xi,ψ(i,2,1) ≤ x ≤ xi,ψ(i,2,ni,2),...Pi,mi(x) if xi,ψ(i,mi,1) ≤ x ≤ xi,ψ(i,mi,ni,mi ).(2.3)In a road network, multiple roads are connected to an intersection. Inthis model, we defined an intersection as a special type of section which iscommon to all the roads that are connected to it. Let I = {1, 2, ..., n} bethe index set of all intersections of a road network and Re = {1, 2, ..., nre} bethe index set of all roads connecting to the intersection e. Then the functionξ : I → Re returns the set of all the roads connected to the intersection e92.1. Model definitions and parametersand the function γ(Re×I)→ Si,e returns the set of all connected sections ofroad i to intersection e. The functions µ : (I ×Re)→ R and τ : (I ×Re)→Si returns the road index and section index to which an intersection isconnected. Similarly, the functions η : (I×Re)→ Gi and ζ : (I×Re)→ Si,gmaps the connected segment and section of an intersection to the index set Giand Si,g respectively. The function λ : (R×Si)→ I returns the intersectionindex connected to ith road’s jth section where i ∈ R and j ∈ Si.The initial vertical alignment of the ground before construction is theground profile, and the optimal vertical alignment of the ground after theconstruction is known as the road profile. The difference between the roadprofile and ground profile at a certain section is known as the offset. Now,the cut and fill volumes of materials for each offset should be calculated toget the optimal road profile. Let ui,j denote the offset and V+i,j and V−i,j bethe total cut and fill volumes respectively of ith road’s jth section for i ∈ Rand j ∈ Si. Similarly, let ze be the offset and U+e and U−e be the total cutand fill volumes respectively for every intersection e ∈ I.The road network model also considers side slopes for cutting and fillinga particular section of a road as shown in Figure 2.2 and 2.3. Each sectionis then divided into several rectangles to approximate the trapezoid shapedarea generated by the side-slopes (see Figure 2.4). The height of each rectan-gles from the ground profile is known as offset levels. Let Li,j = {1, 2, ..., ni,j}be the index set for offset levels of ith road’s jth section where, ni,j is thetotal number of offset levels of this section. The height of each offset level isthen denoted by ok ∈ R, where k ∈ Li,j . Let R+k ∈ R denote the cut volumeand R−k ∈ R denote the fill volume respectively for each offset level k ∈ Li,j .Figure 2.2: The cross section area of a cut section with and without side-slopes.Besides cut and fill, materials also need to be either borrowed or dis-carded from the site during construction of each roads. Let Bi = {1, 2, ..., ni,b}be the index set of borrow pits from where materials can be brought in to102.2. Multi-road quasi network flow modelFigure 2.3: The cross section area of a fill section with and without side-slopes.Figure 2.4: The cross section area of a section with side-slopes after approx-imation.each road i ∈ R and Wi = {1, 2, ..., ni,w} be the index set of waste pitswhere extra materials can be discarded from each road i ∈ R. The functionϑ : Bi → Si maps the borrow pit and ϕ : Wi → Si maps the waste pit to asection for each road i ∈ R.Access roads are required to move materials from a particular section ofa road to either borrow or waste pits. Let Ai = {1, 2, ..., ni,a} be the indexset of access roads and % : Ai → Si is the function that maps access roadto a particular section of each road i ∈ R. The set Ni = {Sr ∪ Bi ∪ Wi}represents all the section indexes including borrow and waste sections foreach road i ∈ R. The distance between the borrow/waste pit and the sectionconnected to it is known as the dead haul distance and is denoted by d˜k (d˜lfor waste) where k ∈ Bi (l ∈ Wi for waste) for the ith road.2.2 Multi-road quasi network flow modelIn the multi-road quasi network flow model (MR-QNF), the QNF modelfrom [HHLR14] has been modified and extended to accommodate all the112.2. Multi-road quasi network flow modelroads of a road network, including intersections. Currently, the MR-QNFmodel only assumes a single haul to move one type of materials for theconstruction of a road network as opposed to MH-QNF model [BHLH17]which assumes multiple hauls to move different types of materials for asingle road.2.2.1 Model descriptionSimilar to the QNF and MH-QNF models, we draw sections, intersec-tions, borrow and waste pits as nodes. In addition, we draw arcs as thefeasible path to move materials from one node to another in the MR-QNFmodel. Figure 2.5 shows the typical flows that a section has for a particularroad in the MR-QNF model, which is the same as the QNF model. How-ever, unlike the QNF model, the MR-QNF model can handle multiple roads,including intersections. Figure 2.6 shows the typical flows of an intersectionof four roads in the MR-QNF model.Figure 2.5: A typical section a of road A in MR-QNF model same as QNFmodel.In this model, each road of a road network is divided into sections,and each section has two virtual transit nodes, a positive node for movingmaterials left to right and a negative node for moving materials right toleft. Each positive transit node has one outgoing flow path denoted by thevariable, f t+i,j with the exception of the last section’s transit node and one122.2. Multi-road quasi network flow modelFigure 2.6: A typical intersection e of a road network in MR-QNF model.incoming flow path, f t+i,j−1 aside from the first section’s transit node (∀i ∈ Rand ∀j ∈ Si). Similarly, each negative transit node has one outgoing flowpath denoted by the variable, f t−i,j except the first section’s transit node andone incoming flow path, f t−i,j+1 aside from the last section’s transit node.Both positive and negative virtual nodes have two more flow paths forloading and unloading materials. Let f l+i,j and fl−i,j denote the two outgoingload flow paths and fu+i,j and fu−i,j indicates the two incoming unload flowpaths of positive and negative transit nodes respectively. If a particular sec-tion is associated with an access road for moving materials to either borrowor waste pit, then each transit node of this section will have two additionalflow paths. One outgoing flow path (fw+,li,j and fw−,li,j ) for discarding materi-als to a waste pit and one incoming flow path (f b+,ki,j and fb−,ki,j ) for borrowingmaterials from a borrow pit.An intersection is a common section between two or more roads. In132.2. Multi-road quasi network flow modelthis model, we assume that every road can be connected to at most twointersections. That is, a road can only connect to an intersection either at thestarting or at the ending section of that road. So, for example, if two roadsintersect each other at a common section, then the model would consider theroad network as four roads connecting to the common section/intersectionprovided each road has only one endpoint connected to the intersection andthe other endpoint is not connected. However, roads forming a loop in a 8pattern would only be counted as two roads.Each intersection in this model has one virtual transit node for movingmaterials from one road to another. This virtual node has two flow pathsfor loading and unloading materials onto the intersection. Let the variablesf le and fue denote the outgoing loading path and incoming unloading pathrespectively for the intersection virtual transit node (∀e ∈ I). The inter-section virtual node also has two additional flow paths (one incoming andone outgoing) for each road connecting to this intersection. For example,the intersection e as shown in Figure 2.6 has four roads. Thus, the virtualnode of this intersection e will have eight flow paths (four incomings andfour outgoings). Then the variables f in,ei,j and fout,ei,j denote the incoming andoutgoing flow paths respectively for each road.2.2.2 Cost parametersThe MR-QNF model considers only excavation or cutting cost, embank-ment or filling cost, hauling costs, and loading costs of materials to constructthe road network. Let pc and qc be the per unit volume of excavation andembankment cost of materials, respectively. There are two distinct direc-tions in which materials can move in each road. The hauling cost of oneunit volume of materials per unit distance is denoted as hc. The materialscan move from left to right (next section) and right to left (previous sec-tion). Then the distance between the current section and the next section isdefined as d+i,j and the distance between the current and previous section isdenoted as d−i,j where i ∈ R and j ∈ Si. Finally, the hauling cost of materialsto the next section can be defined as ht+i,j = hcd+i,j . Similarly, ht−i,j = hcd−i,jdefines the hauling cost of materials to the previous section. On a similarnote, let hei,j denote the hauling cost of materials to/from an intersection(∀i ∈ Re, ∀j ∈ Si,e and ∀e ∈ I). The loading cost is only associated withexcavating materials from a section or borrowing materials from a borrowpit. Let yc denote the loading cost of materials. This model does not con-sider any unloading cost of materials as this cost is insignificant comparedto the other costs.142.2. Multi-road quasi network flow model2.2.3 Objective functionThe objective of the MR-QNF model is to minimize the total construc-tion cost which includes all the excavation, embankment, hauling and load-ing costs of materials for constructing an entire road network. Hence, theobjective function ismin[∑i∈R∑j∈Si(pc + yc)V+i,j +∑i∈R∑j∈Si+1qcV−i,j+∑i∈R∑j∈Si(ht+i,jft+i,j + ht−i,jft−i,j)+∑e∈I(pc + yc)U+e +∑e∈Iqc U−e+∑e∈R∑i∈ξ(e)∑j∈γ(i,e)hei,j(f in,ei,j + fout,ei,j)+∑i∈R∑k∈Bi(pc + yc + hcd˜k)(f b+,ki,ϑ(k) + fb−,ki,ϑ(k))+∑i∈R∑l∈Wi(qc + hcd˜l)(fw+,li,ϕ(l) + fw−,li,ϕ(l))].(2.4)Here,∑i∈R∑j∈Si(pc + yc)V+i,j represents the total excavation/cutting andloading costs of all the sections of every road in a road network. Similarly,∑i∈R∑j∈Si+1 qcV−i,j represents the total embankment/filling costs of all thesections of every road in a road network.∑i∈R∑j∈Si(ht+i,jft+i,j +ht−i,jft−i,j ) rep-resents the total cost of moving materials or hauling costs within each road.∑e∈I(pc+ yc)U+e +∑e∈I qc U−e represents the total excavation, loading andembankment costs of all intersections. And∑e∈R∑i∈ξ(e)∑j∈γ(i,e) hei,j(fin,ei,j +fout,ei,j ) represents the total hauling costs of moving materials from one roadto another. Finally,∑i∈R∑k∈Bi(pc + yc + hcd˜k)(fb+,ki,ϑ(k) + fb−,ki,ϑ(k)) representsthe total cost of borrowing the materials and∑i∈R∑l∈Wi(qc+hcd˜l)(fw+,li,ϕ(l)+fw−,li,ϕ(l)) represents the total cost of discarding materials from all the roads.2.2.4 ConstraintsSeveral constraints must be added to the optimization model to ensureboth safety and design requirements for constructing the road network.152.2. Multi-road quasi network flow modelSmoothness constraintsThe height and slope of the first section of a segment must be equalto the height and slope of the last section of the previous segment. Theseconstraints are going to ensure that the road is smooth. Thus the smoothnessconstraints are defined asPi,g−1(xψ(i,g−1,ni,g−1))= Pi,g(xψ(i,g,1)), ∀i ∈ R, ∀g ∈ Gi \ {1}, (2.5)P ′i,g−1(xψ(i,g−1,ni,g−1))= P ′i,g(xψ(i,g,1)), ∀i ∈ R, ∀g ∈ Gi \ {1}. (2.6)In addition, the height of all the sections connecting to the same intersectionmust be equal. Then the smoothness constraints for the intersections aredefined asPµ(e,1),η(e,1)(xψ(µ(e,1),η(e,1),ζ(e,1)))= · · ·= Pµ(e,nre),η(e,nre)(xψ(µ(e,nre),η(e,nre),ζ(e,nre))) ∀e ∈ I. (2.7)Both P and P ′ are colored in red, since they are the functions of x, wherethe coefficients are considered variables (see Eqs. (2.1) and (2.2)).Road grade constraintThe road grade constraint makes sure that the road profile is constructedwithin the maximum (GU ) and minimum (GL) allowable grades for safetyconsiderations and is defined asGL ≤ P ′i,g(xψ(i,g,1)) ≤ GL, ∀i ∈ R, ∀g ∈ Gi. (2.8)Gap constraintsThe gap constraints ensure that the difference of the road profile andground profile at each section of a segment must be equal to the offset ofthat section. Then the gap constraints are formulated as,Pi,g(xψ(i,g,k))− Zi,j = ui,j , ∀i ∈ R, j ∈ Si, g ∈ Gi, k ∈ Si,g, (2.9)where Zi,j is the height of the ground profile of ith road’s jth section.162.2. Multi-road quasi network flow modelVolume constraintsThe volume constraintsV+i,j =∑k∈Li,jR+k lk, ∀i ∈ R, j ∈ Si, (2.10)V−i,j =∑k∈Li,jR−k lk, ∀i ∈ R, j ∈ Si, (2.11)ensure that the total excavation/embankment from/to a section is equal tothe total cut/fill volume for that section.The constraint ∑k∈Li,joklk = ui,j , ∀i ∈ R, j ∈ Si, (2.12)also ensures that after excavating/embankment of materials from/to a sec-tion, the new height must be equal to the offset of that section. In addition,the constraint ∑k∈Li,jlk = 1, ∀i ∈ R, j ∈ Si, (2.13)makes sure that only one level is selected from each section.Similarly, the constraintsU+e =∑k∈LeR+k lk, ∀e ∈ I, (2.14)U−e =∑k∈LeR−k lk, ∀e ∈ I, (2.15)∑k∈Leoklk = ze, ∀e ∈ I, (2.16)∑k∈Lelk = 1, ∀e ∈ I, (2.17)ensure that the total excavation/embankment from/to an intersection isequal to the total cut/fill volume for that intersection.172.2. Multi-road quasi network flow modelBalance constraintsEach section is treated as an outgoing and incoming flows of materials.Hence, the total unload flows from a section and total load flows into thissection must be equal to the total cut and fill volumes respectively of thissection. These constraints are called balance constraints and defined asfu+i,j + fu−i,j = V+i,j , ∀i ∈ R, ∀j ∈ Si, (2.18)f l+i,j + fl−i,j = V−i,j , ∀i ∈ R, ∀j ∈ Si. (2.19)Similarly, the balance constraints for an intersection are simply definedasfue = U+e , ∀e ∈ I, (2.20)f le = U−e , ∀e ∈ I. (2.21)Flow constraintsFlow constraints ensure that the total amount of materials flowing intoa particular virtual transit node of a section equals the total amount ofmaterials flowing out of that transit node. The flow constraint for virtualtransit nodes where the section is not connected to an intersection are definedasf t+i,j + fl+i,j +∑m∈Wifw+,mi,ϕ(m) = ft+i,j−1 + fu+i,j +∑k∈Bif b+,ki,ϑ(k), ∀i ∈ R,∀j ∈ Si(2.22)andf t−i,j + fl−i,j +∑m∈Wifw−,mi,ϕ(m) = ft−i,j+1 + fu−i,j +∑k∈Bif b−,ki,ϑ(k), ∀i ∈ R,∀j ∈ Si.(2.23)Now, if a particular section is connected to an intersection and is thefirst section of the road, then the flow constraints for this section’s virtualtransit nodes are defined as,f t+i,j +∑m∈Wifw+,mi,ϕ(m) = fout,λ(i,j)i,j +∑k∈Bif b+,ki,ϑ(k), ∀i ∈ R,∀j ∈ Si (2.24)andfin,λ(i,j)i,j +∑m∈Wifw−,mi,ϕ(m) = ft−i,j+1 +∑k∈Bif b−,ki,ϑ(k), ∀i ∈ R,∀j ∈ Si, . (2.25)182.2. Multi-road quasi network flow modelSimilarly, if the section is the last section of a road is connected to anintersection then the flow constraints are defined as,fin,λ(i,j)i,j +∑m∈Wifw+,mi,ϕ(m) = ft+i,j−1 +∑k∈Bif b+,ki,ϑ(k), ∀i ∈ R,∀j ∈ Si (2.26)andf t−i,j +∑m∈Wmfw−,mi,ϕ(m) = fout,λ(i,j)i,j +∑k∈Bif b−,ki,ϑ(k), ∀i ∈ R,∀j ∈ Si. (2.27)In addition, the constraint∑i∈ξ(e)f in,ei,τ(e,i) + fue =∑i∈ξ(e)fout,ei,τ(e,i) + fle, ∀e ∈ I, (2.28)conserves the flow of materials for each intersection transit node.The constraints∑i∈ξ(e)fu+i,τ(e,i) +∑i∈ξ(e)fu−i,τ(e,i) = 0, ∀e ∈ I and (2.29)∑i∈ξ(e)f l+i,τ(e,i) +∑i∈ξ(e)f l−i,τ(e,i) = 0, ∀e ∈ I, (2.30)ensure that the unloading and loading materials of sections that are con-nected to an intersection are not counted multiple times as these materialsare already included in the intersection.Bound constraintsBound constraints define the domain space of every variables. Let M+idenote the maximum amount of materials that can be excavated from asection and M−i denote the maximum amount of materials that can be em-banked to a section for road i. Again, let ui,j and ui,j denote the maximumand minimum offsets of ith road’s jth section. Similarly, let ze and ze de-note upper and lower limits of the offsets of intersection e. Then the boundconstraints can be defined as,0 ≤ fu+i,j ≤M+i , ∀i ∈ R, ∀j ∈ Si, (2.31)0 ≤ fu−i,j ≤M+i ,∀i ∈ R, ∀j ∈ Si, (2.32)0 ≤ f l+i,j ≤M−i ,∀i ∈ R,∀j ∈ Si, (2.33)192.3. Different methods to solve the road network problem0 ≤ f l−i,j ≤M−i ,∀i ∈ R,∀j ∈ Si, (2.34)0 ≤ fue ≤M+e , ∀e ∈ I, (2.35)0 ≤ fue ≤M−e , ∀e ∈ I, (2.36)ui,j ≤ ui,j ≤ ui,j , ∀i ∈ R,∀j ∈ Si, (2.37)ze ≤ ze ≤ ze, ∀e ∈ I, (2.38)lk ∈ {0, 1}, ∀i ∈ R,∀j ∈ Si, ∀k ∈ Li,j , (2.39)V+i,j ≥ 0,V−i,j ≥ 0, ∀i ∈ R, ∀j ∈ Si, (2.40)U+e ≥ 0,U−e ≥ 0, ∀e ∈ I, (2.41)f b+,ki,ϑ(k) ≥ 0, f b−,ki,ϑ(k) ≥ 0, ∀i ∈ R,∀k ∈ Bi, (2.42)fw+,li,ϕ(l) ≥ 0, fw−,li,ϕ(l) ≥ 0, ∀i ∈ R,∀l ∈ Wi, (2.43)f t+i,j ≥ 0, f t−i,j ≥ 0, ∀i ∈ R,∀j ∈ Si, (2.44)f in,ei,j ≥ 0, fout,ei,j ≥ 0, ∀i ∈ R,∀j ∈ Si, ∀e ∈ I. (2.45)2.3 Different methods to solve the road networkproblemWe propose four different methods to solve the road network problem.2.3.1 One-at-a-time methodOne way to solve the road network optimization problem is to solveeach road individually and ensure that each section’s height connecting tothe same intersection is equal. Let this method be called the one-at-a-timemethod. This method’s advantage is that it is simple and straightforwardto implement with the existing QNF/MH-QNF model. However, the draw-backs of this method are that it does not guarantee a global minimum andmay return an infeasible solution even if there is a feasible solution to theroad network problem. This is because, in this method, we are solving eachroad as a distinct optimization problem. So, there is a possibility that solv-ing any one of these optimization problems may make any one of the otheroptimization problems infeasible, thus making the entire road network in-feasible. In addition, the optimal cost of the solution also may differ forsolving the roads in different sequences.202.3. Different methods to solve the road network problemFor example, if a road network has 10 roads, then there are 10! ways tosolve this problem using the one-at-a-time method. However, it is unreal-istic to solve this problem for 10! sequences. So, instead, we will solve thisproblem by generating road sequences in a connected way. Hence, there willbe 10 different ways to solve this problem for 10 different initial roads usingthis method. Algorithm 2.1 outlines the pseudocode of the one-at-a-timemethod to solve the road network problem for a single road sequence.Algorithm 2.1: One-at-a-time methodInput : R ← array of all roads.Output: set of solutions P.Z ← empty array of heights for all common intersections.Rordered ← Select a road ordering from R.for all roads r in Rordered doobjective← from Eq. (2.4), excluding intersection parts;constraints← from Eqs. (2.5) to (2.45) excluding intersectionconstraints;for all connected intersections i in r doif Z[i] is not empty thenconstraints← constraints + [height of r at theconnected section == Z[i]];endendP[r]← solve(objective, constraints).for all connected intersections i in P[r] doif Z[i] is empty thenZ[i]← height of P[r] at the connected section;endendendIn the one-at-a-time method, we are solving each road one by one. So,after solving each road, we have to store the height of the connected in-tersection for solving all the remaining roads. This is why we are storingthe height of all the intersections in Z after solving each road which willbe then used for solving the next available road if required. The order ofroads in R will determine the road sequence for solving the problem usingthe one-at-a-time method. This order can be selected in random or in asequential way depending on the settings of the experiment. Next we build212.3. Different methods to solve the road network problemthe model using all the Eqs. from (2.4) to (2.45) excluding intersections andthen solve the problem.2.3.2 No-flow methodUsing this method, the road network optimization problem is solved asa single optimization problem rather than several individual optimizationproblems for each road. However, the materials can not move from one roadto another in this method. The new proposed MR-QNF model must beused to implement this method since all the other previous models can onlyaccommodate a single road. This method also does not guarantee the globalminimum and may require a longer computation time than the one-at-a-timemethod depending on the size of the problem. Algorithm 2.2 outlines thepseudocode of the no-flow method to solve the road network problem as asingle optimization problem.Algorithm 2.2: No-flow methodInput : N ← road network.Output: Solution P of the road network problem.objective← from Eq. (2.4);constraints← from Eqs. (2.5) to (2.45);constraints← constraints + [f in,ei,j == 0] for all intersections;constraints← constraints + [fout,ei,j == 0] for all intersections;P ← solve(objective, constraints).The no-flow method solves the road network problem as a single opti-mization model and hence will use all the Eqs. from (2.4) to (2.45). However,since materials will not move from one road to another, the associated vari-ables must be set to zero. Here, the associated variables are f in,ei,j and fout,ei,jwhich determines the amount of materials moving in and out of the inter-section e. Therefore, these variables for all intersections of the road networkhas been set to zero by a equality constraint as shown in the algorithm 2.2.Figure B in appendix B shows the class diagram for the road network objectN .The optimal cost of the no-flow method will be a lower bound for the op-timal cost of the one-at-a-time method. That is, the solution of the one-at-a-time method will never generate a lower cost than the no-flow method’s solu-tion. Hence, solving the road network problem using the no-flow method willdetermine how reasonable the solution’s cost of the one-at-a-time methodis.222.3. Different methods to solve the road network problem2.3.3 With-flow methodThe only difference between this method and the no-flow method is thatnow materials can move freely from one road to another and thus ensure aglobal minimum. This method also uses the proposed MR-QNF model tosolve the road network problem. The drawback of this method is that it mayrequire a longer computation time than the previous two methods dependingon the size of the problem. Algorithm 2.3 outlines the pseudocode of thewith-flow method to solve the road network problem as a single optimizationproblem.Algorithm 2.3: With-flow methodInput : N ← road network.Output: Solution P of the road network problem.objective← from Eq. (2.4);constraints← from Eqs. (2.5) to (2.45);P ← solve(objective, constraints).The with-flow method will also solve the road network problem as asingle optimization problem. But unlike the no-flow method, this methodwill allow materials to move from one road to another. Hence, there areno extra constraints for this method and will use all the Eqs. from (2.4) to(2.45) to build the model.The optimal cost of the with-flow method will be a lower bound forthe no-flow method’s optimal cost. Hence, the no-flow method will nevergenerate a solution with a lower cost than the with-flow method.2.3.4 Divide and conquer methodThis is not the algorithm that divides a problem into two or more sub-problems recursively that is usually found in computer science. Instead,we defined this method in this research as solving the whole road networkproblem by dividing it into two or more smaller road networks and then usethe no-flow or with-flow method to solve all these small road networks. Wewill only apply this method when we cannot solve the whole road network asa single optimization problem due to time-outs or lack of memory. Algorithm2.4 outlines the pseudocode of the divide and conquer method to solve theroad network problem.We followed a similar strategy to the one-at-a-time method to solve theroad network problem using the divide and conquer method. However, in232.3. Different methods to solve the road network problemAlgorithm 2.4: Divide and conquer methodInput : N ← road network.Output: set of solutions P.Z ← empty array of heights for all common intersections;C ← Divide N into clusters of m roads;Cordered ← Select a road network ordering from C.for all small road networks c in Cordered doobjective← from Eq. (2.4) (for with-flow method);constraints← from Eqs. (2.5) to (2.45) (for with-flow method);for all connected intersections i in c doif Z[i] is not empty thenconstraints← constraints + [height of the connectedsection == Z[i]];endendP ← solve(objective, constraints).for all connected intersections i in P doif Z[i] is empty thenZ[i]← height of the connected section;endendend242.3. Different methods to solve the road network problemthis method, instead of solving multiple single roads, we are solving multipleroad networks as distinct optimization problems. Next we can either use thewith-flow or the no-flow method to solve these optimization problems. Inaddition, we also have to keep track of the height of all the common inter-sections between the optimization problems like the one-at-a-time method.Moreover, as we are solving multiple optimization problems, the total op-timal cost of the whole road network may differ depending on the order ofthese optimization problems are solved. Hence, this method will not guar-antee a global minimum for the road network problem.25Chapter 3Numerical experiments andresultsIn this chapter, we describe and present the experimental results andperformance of the MR-QNF model that is discussed in earlier chapters. Atfirst, we compare the MR-QNF model’s performance with different methodsusing two academic case studies. Then we measure the performance of thesemethods with real-world examples.3.1 Experimental setupThe experiment was first set up with two academic examples using veryshort roads to understand the validity and benefits of using the MR-QNFmodel. Then we use two real-world road network problems generated withthe help of our industry partner.All the experiments were performed on the same workstation, an Intel(R)Xeon(R) CPU E5-1620 v4 3.50 GHz processor and 64 GB of RAM. Themathematical model was implemented on MATLAB R2020a 64-bit version[MAT18]. To model the optimization variables and parameters in MATLAB,we used YALMIP [Lo¨f04] optimization toolbox version R20200930 (https://yalmip.github.io/download). In addition, we used the academicversion of the IBM ILOG CPLEX solver V12.10.0 [Cpl09] to solve the MILPproblem (https://www.ibm.com/products/ilog-cplex-optimization-studio).The performance of the model also depends on the cost components.Table 3.1 shows the cost components for the road network model. Theupper and lower bound of each road’s grade is set between 0.1 and -0.1,respectively, for all the experiments except one, which will be discussedlater in this section. Also, the number of stations per segment is set to 2 inall the experiments. All the experiments have been run at least five times,and the minimum computation time is selected as the final computationtime for that experiment.263.2. MR-QNF input formatTable 3.1: Cost components in $/cubic meter.Cost component ValueExcavation cost 4.000Embankment cost 2.000Loading cost 1.000Hauling cost 0.005Throughout this research, we calculated the values of the diff column intables using the formula, diff = ((new value − base value)/base value) ∗100. The formula for calculating the speedup is as follows, speedup =base value/new value.3.2 MR-QNF input formatAll the previous models (QNF and MH-QNF) were designed to only solvesingle road problems considering other constraints. Hence, the input filesfor these previous models will not be applicable to the current MR-QNFmodel. Table 3.2 shows the format of the old input file.Table 3.2: Old input format.SNo X Y Z Offset Quantity0 0 0 300 -4 4500 0 0 300 -2 1500 0 0 300 0 00 0 0 300 2 -1000 0 0 300 4 -30050 50 0 304 -4 45050 50 0 304 -2 15050 50 0 304 0 050 50 0 304 2 -10050 50 0 304 4 -300100 100 0 300 -4 450100 100 0 300 -2 150100 100 0 300 0 0100 100 0 300 2 -100100 100 0 300 4 -300273.2. MR-QNF input formatHere, SNo is the station numbers of the roads, X and Y are the coor-dinates of this station, Z is the elevation/altitude of the ground profile inmeters at this station, Offset is the difference (in meters) of the groundprofile indicated by Z to the road profile and Quantity is the amount ofmaterials (cubic meters) that need to be cut (when the offset is negative)or filled (when the offset is positive) to construct the road profile. In thisexample, each station has five offsets.For example, the first row of the table 3.2 is 0, 0, 0, 300,−4, 450 means,the first station of the road is 0 and the next two numbers indicate thecoordinate of this station is (0, 0). The next 300 indicates the altitude ofthis station 0. Finally, −4 and 450 indicate that to lower the height of thisstation to 300 − 4 = 296 meters, a total of 450 m3 of materials need to becut.This old input format can only contain information of just a single road.Hence, a new input format for the MR-QNF model has to be generated,which contains information on both multiple roads and intersections. There-fore, a script is coded in MATLAB, which will combine the single road’sinput files into a new input format (CSV) that contains all the relevant in-formation of the road network. Table 3.3 shows the format of the new inputfile. This table also outlines the design parameters for academic case one.Table 3.3: New input format.RdNo INo SNo X Y Z Offset Quantity RdINo1 0 0 0 300 -4 4501 0 0 0 300 -2 1501 0 0 0 300 0 01 0 0 0 300 2 -1001 0 0 0 300 4 -3001 50 50 0 304 -4 4501 50 50 0 304 -2 1501 50 50 0 304 0 01 50 50 0 304 2 -1001 50 50 0 304 4 -3001 100 100 0 300 -4 450 11 100 100 0 300 -2 150 11 100 100 0 300 0 0 11 100 100 0 300 2 -100 1Continued on next page283.2. MR-QNF input formatTable 3.3 – continued from previous pageRdNo INo SNo X Y Z Offset Quantity RdINo1 100 100 0 300 4 -300 12 0 100 0 300 -4 450 12 0 100 0 300 -2 150 12 0 100 0 300 0 0 12 0 100 0 300 2 -100 12 0 100 0 300 4 -300 12 50 150 0 296 -4 4502 50 150 0 296 -2 1502 50 150 0 296 0 02 50 150 0 296 2 -1002 50 150 0 296 4 -3002 100 200 0 300 -4 4502 100 200 0 300 -2 1502 100 200 0 300 0 02 100 200 0 300 2 -1002 100 200 0 300 4 -3003 0 100 0 300 -4 450 13 0 100 0 300 -2 150 13 0 100 0 300 0 0 13 0 100 0 300 2 -100 13 0 100 0 300 4 -300 13 50 100 50 300 -4 4503 50 100 50 300 -2 1503 50 100 50 300 0 03 50 100 50 300 2 -1003 50 100 50 300 4 -3003 100 100 100 300 -4 4503 100 100 100 300 -2 1503 100 100 100 300 0 03 100 100 100 300 2 -1003 100 100 100 300 4 -3001 0 100 0 300 -4 4501 0 100 0 300 -2 1501 0 100 0 300 0 01 0 100 0 300 2 -100Continued on next page293.2. MR-QNF input formatTable 3.3 – continued from previous pageRdNo INo SNo X Y Z Offset Quantity RdINo1 0 100 0 300 4 -300Six columns in both the old and new input formats are precisely thesame. However, the new input format has three more additional columns tocontain the information of multiple roads and intersections. For example,the RdNo and INo columns identify each road and intersection in the roadnetwork. And the RdINo column indicates which section of the road isconnected to which intersection. All this information can not be found inthe old format required to solve the entire road network problem. The table3.3 is divided into four parts. The first three parts contain informationabout the three roads in the road network, which are differentiated by theRdNo column. The last part of this table contains information about theintersection. Hence, here the RdNo column is empty, and the INo columndifferentiates multiple intersections, if any.For example, the last row of the first part of the table 3.3 is 1, , 100, 100, 0,300, 4,−300, 1 means, for road 1, the station number is 100 and the next twonumbers indicate the coordinates of this station, (100, 0). The second col-umn here is empty as this is not an intersection. The next 300 indicates thealtitude of this station of road 1. The next two numbers, 4 and −300 indi-cate that to raise the height of this station to 300+4 = 304 meters, a total of300 m3 of materials need to be filled. The last 1 indicates that this stationis actually an intersection. Similarly, , 1, 0, 100, 0, 300,−4, 450, means thisis not a road as the first column is empty. The next number indicates thisis intersection 1 and the station number is 0 with a coordinate of (100, 0)and an altitude of 300 meters. Again, −4 and 450 indicate that to lower thealtitude of this intersection to 296, a total of 450 m3 of materials need tobe cut. Finally, the last column here is empty as this is an intersection andnot a road.The input files for all the cases, including academic and real-world ex-amples, have been generated similarly. Table C.1 in appendix C outlinesthe new input format for the academic case two. The input files for thereal-world examples are too long to be shown here. The file (CSV) sizesfor real-world examples one and two are approximately 1 MB and 6.5 MB,respectively.303.3. Experimental results of the academic cases3.3 Experimental results of the academic casesThe academic cases consist of three short roads of just three sections withvaried ground profiles. These cases were manually generated to illustratethe advantages of using the MR-QNF model compared to the existing QNFmodels in solving the road network problem. The design parameters of thesetwo academic cases can be found in Tables 3.3 and C.1. Figure 3.1 showsthe horizontal alignments of these academic cases.Figure 3.1: Horizontal alignments of the academic cases.3.3.1 Academic case oneAt first, the one-at-a-time method is used to solve the road networkproblem for this case. There are in total 3! = 6 sequences of roads and thussix different ways to solve this problem. However, as all three roads areconnected to the same intersection, the order on which road is solved nextwill not change the total cost of the problem. For example, if we chose tosolve this problem by selecting road 1 as the initial road, then after solvingthis road, the height of the common intersection will get fixed. Therefore,the height of the remaining two road’s starting points will also be equalto the height of this intersection. Furthermore, since the remaining tworoads are independent of each other, the order on which road we solvednext will not change the total cost of the problem. So, there are actuallythree different ways to solve this problem using the one-at-a-time methoddepending on three different initial roads.Table 3.4 shows the optimal costs and the computation times for thisproblem using the one-at-a-time method. Here, the results are sorted inascending order of the cost, and the minimum cost has been selected as thebase cost for comparing with other ways to solve this problem. This table313.3. Experimental results of the academic casesalso shows that depending on the order in which road is solved first, thesolution’s cost can differ significantly. Hence, it is important that, when theone-at-a-time method is used to solve the road network problem, it shouldbe solved in every possible and reasonable ways.Table 3.4: Results of the one-at-a-time method (Academic case one).Method Initial road Cost ($) Diff (%) Time (sec)One-at-a-time2 874 - 0.33 874 0.0 0.31 1,880 115.1 0.3Next, the no-flow and with-flow methods are used to solve this problemusing the proposed MR-QNF model. Table 3.5 shows the comparison ofoptimal costs and computation times for these three methods. For the one-at-a-time method, the minimum cost has been selected as the base cost forobvious reasons, and the total computation time of solving this problem inthree different ways is the base time for comparison with the other methods.Table 3.5: Comparison of results for different methods (Academic case one).Method Cost ($) Diff (%) Time (sec) SpeedupOne-at-a-time 874 - 0.9 -No-flow 874 0.0 0.1 9With-flow (best) 737 -15.7 0.1 9The optimal cost obtained from the no-flow method is the same as theoptimal cost of the one-at-a-time method but with lower computation time.However, the with-flow method’s optimal cost is 15.7% lower than the othertwo methods for this academic case. Although the computation time of bothno-flow and with-flow methods is comparatively lower than the one-at-a-timemethod, these differences are not reliable since this is an extremely smalloptimization problem. Figure 3.2 shows the resultant vertical alignmentsand earthwork optimization when the with-flow method is used to solve thisproblem.3.3.2 Academic case twoThe only distinction between academic cases one and two is in the groundprofile. Table 3.6 shows the results of using the one-at-a-time method. In323.3. Experimental results of the academic casesFigure 3.2: Optimized vertical alignments of three roads in academic caseone using with-flow method.contrast to the previous case, where different sequences of roads changed theoptimum solution only, this case example also shows that a certain sequenceof road may generate an infeasible solution even when there is a feasiblesolution to the problem.Table 3.6: Results of the one-at-a-time method (Academic case two).Method Initial road Cost ($) Diff(%) Time (sec)One-at-a-time1 14,375 - 0.32 14,375 0.0 0.33 infeasible - 0.3Table 3.7 shows the comparison of different methods to solve this prob-lem. In this case, using the with-flow method, it is possible to lower theoptimum cost by around 37% compare to the other two methods. Figure3.3 shows the resultant vertical alignments and earthwork optimization whenthe with-flow method is used to solve this problem.333.3. Experimental results of the academic casesTable 3.7: Comparison of results for different methods (Academic case two).Method Cost ($) Cost Diff (%) Time (sec) SpeedupOne-at-a-time 14,375 - 0.9 -No-flow 14,375 0.0 0.1 9With-flow (best) 9,075 -36.9 0.1 9Figure 3.3: Optimized vertical alignments of three roads in academic casetwo using with-flow method.In both the one-at-a-time and the no-flow methods, the materials cannot move from one road to another. However, the one-at-a-time methodrequires to be used three times for three different initial roads to ensureminimum cost and feasibility, which can be seen in Tables 3.4 and 3.6. Onthe other hand, the no-flow method will solve the road network problemonly once and generate the minimum cost from the one-at-a-time method.Nevertheless, in both academic cases, the with-flow method reduced thetotal cost of the problem significantly compared to both the one-at-a-timeand no-flow methods. Furthermore, since both the academic cases can besolved as a single optimization problem, the divide and conquer method hasnot been used to solve these problems. Hence, in both these academic cases,343.4. Experimental results of the real-world examplesthe with-flow method is the best method to solve the road network problem.3.4 Experimental results of the real-worldexamplesThis section describes the numerical results of all the methods on tworeal-world road network examples. Our industry partner provided theseexamples to assess the proposed model in a real-world context.3.4.1 Example oneThe first example consists of twelve roads and five intersections (seeFigure 3.4). The longest road is around 1 km in length and has 55 sections,and the shortest road is around 170 m in length and has ten stations in thisexample. The total length of the road network is around 6 km.Figure 3.4: Real-world road network example 1.Similar to the academic cases, this problem was first solved using the one-at-a-time method. There are in total 12! ways to solve this problem usingthis method. However, it is unrealistic to solve all 12! different sequences ofroads. Hence, we first solve this problem by randomly choosing ten different353.4. Experimental results of the real-world examplesTable 3.8: Comparison of results for ten different random sequences of roadsin one-at-a-time method (Real case one).Runs Cost ($) Diff (%) Time (sec) Sequences1 53,867 - 3.3 11-9-7-8-3-10-12-4-1-2-5-62 53,867 0.0 3.1 11-10-3-1-9-5-8-6-12-7-2-43 53,982 0.2 3.0 3-6-5-7-4-8-9-1-11-10-12-24 56,012 4.0 3.0 4-5-2-9-8-11-7-6-10-12-3-15 56,012 4.0 3.1 1-9-4-5-11-6-8-10-7-3-2-126 62,954 16.9 3.1 2-10-9-7-6-5-3-11-4-8-1-127 63,069 17.1 3.2 2-7-10-9-6-5-4-1-12-3-8-118 71,477 32.7 3.0 8-12-6-9-10-2-5-4-11-1-3-79 71,477 32.7 3.1 6-5-8-7-10-9-4-12-11-3-1-210 73,357 36.2 3.3 8-1-9-3-10-7-6-11-4-2-12-5sequences of roads and then compared the results. The results in this tablehave been sorted by ascending order of the cost, and the minimum cost hasbeen selected as the base cost for comparison.However, if we sequentially solve the problem, there are genuinely 12ways to solve this problem depending on which of the 12 roads is solvedfirst, as there are no loops present in this road network. For example, theinitial road can be selected randomly, and after solving this road first, theheight of the intersection to which this road is connected will be fixed. Hence,all the other roads connected to this intersection can be selected to solve inany order but will always generate the same solution. Similarly, the heightof the following road’s intersection will be fixed, and so on. Therefore, ifthe road network is solved sequentially using this method, the final solutiononly depends on which road is solved first when there are no loops in theroad network.Table 3.9 shows the comparison of these results depending on which ofthe 12 roads is solved first. The results of this table are sorted in ascendingorder of the total cost of the solution. Among the twelve runs, six runshad significantly higher costs, which warrants the need to run this problemmultiple times. The minimum cost and the total time of all runs from Table3.9 was chosen as the base to compare with the other two methods.Although by choosing random sequences of roads (table 3.8), we wereable to reduce the cost further compare to sequentially solving the problem(table 3.9), the difference is not significant enough (only by 0.2%). Hence,it is reasonable to assume that we will get a solution closer to the minimum363.4. Experimental results of the real-world examplesTable 3.9: Comparison of results for different initial road in one-at-a-timemethod (Real case one).Initial Road Cost ($) Diff (%) Time (sec)11 53,983 - 3.410 54,064 0.2 3.312 54,064 0.2 3.41 54,064 0.2 3.02 54,064 0.2 3.03 54,064 0.2 3.14 61,859 14.6 3.19 65,748 22.0 3.45 65,864 22.0 3.16 65,864 22.0 3.27 65,864 22.0 3.48 96,424 78.6 3.3in most cases, even if we sequentially solve the problem.Next, both the no-flow and with-flow methods are used to solve thisproblem. Table 3.10 shows the comparison of the results for these threemethods. In this case, the no-flow method reduced the cost by 2.0%, andthe with-flow method reduced the total cost by 7.2% compare to the one-at-a-time method. The one-at-a-time method took a longer computation timethan the other two methods because it had to solve the same problem intwelve different ways with twelve different initial roads to get the optimalcost. On the other hand, the no-flow and with-flow methods only solvedthe road network problem once and reduced the cost with less computationtime. Hence, in this case, the with-flow method is the best method to solvethe road network problem.We also did not use the divide and conquer method in this examplesince we can solve this problem as a single optimization problem within areasonable amount of time.3.4.2 Example twoThe second example of the real-world road network is located in a moun-tainous region and much more extensive than the first example (see Figure3.5). This case example has 32 roads and 16 intersections, and the longestroad is around 10 km with 600 stations. Thus, the total length of the road373.4. Experimental results of the real-world examplesTable 3.10: Comparison of results for different methods (Real case one).Method Cost ($) Diff (%) Time (sec) SpeedupOne-at-a-time 53,983 - 38.7 -No-flow 52,928 -2.0 2.0 19With-flow (best) 50,071 -7.2 1.9 20network is around 66 km. Besides, each road’s grade for this case is setbetween -0.2 to 0.2. This is because, when we first solved this problem bysetting the road grade between -0.1 to 0.1, the road network became infea-sible as the terrain in this example is mountainous. Hence, to get a feasiblesolution, we had to increase the road grade. Therefore, although the verti-cal alignments of these roads will not be practical, the conclusion would besimilar in most cases for both the road grades.Unlike the previous case, the real case example 2 has one loop in it,which makes determining the total number of sequences of roads a littlemore complicated. If there had been no loops, then the total number ofways it can be solved sequentially using the one-at-a-time method wouldbe 32 for 32 roads. However, as there is one loop in this example, each ofthe 32 sequences of roads would have three more sequences of roads makingthe total number of sequence of roads to be 32 × 3 = 96. For example, letroad 22 be the common road making the loop. The first sequence can besolving road 23 or 24 first, making the height of this intersection fixed, andthen solving road 22. The second sequence can either solve the road 20 or21 first, thus making the height of this common intersection fixed and thensolving the road 22 problem. And the third or final sequence can be solvingroad 23 or 24 and 20 or 21 first, making the height of these two intersectionsfixed, and then solving road 22. Hence, each of the 32 sequences of roadswill have three more sequences to consider. Note that to keep it simple, weassumed that only one road is responsible for making each loop in the roadnetwork, and also, one road can only connect to at most two intersections.Table 3.11 shows the results of using the one-at-a-time method for 32sequences of the road without considering the loops. The results of thistable are sorted by ascending order of the cost. The minimum cost of these32 sequences is selected as the base cost for comparison. The reason for notsolving it in 96 ways is because most of the roads are comparatively long, andthus, a significant amount of materials will only move within each road, andbarely any materials will move to another road through the intersection.Therefore, we hardly see any changes in the optimal cost among all the383.4. Experimental results of the real-world examplesFigure 3.5: Real-world network example case 2.sequences of roads. This is also the reason for not including the sequencesrelated to the loop in the road network since it is reasonable enough toassume that they will not provide a significantly lower cost than table 3.11.Table 3.11: Comparison of results for all sequences of roadsin one-at-a-time method (Real case two).Initial Road Cost ($) Diff (%) Time (sec)9 189,154 - 35.911 189,154 0.0 36.810 189,155 0.0 36.4Continued on next page393.4. Experimental results of the real-world examplesTable 3.11 – continued from previous pageInitial Road Cost ($) Diff (%) Time (sec)7 189,262 0.1 35.223 189,321 0.1 32.324 189,321 0.1 32.925 189,321 0.1 33.126 189,321 0.1 33.228 189,321 0.1 34.127 189,323 0.1 34.618 189,324 0.1 34.519 189,324 0.1 35.120 189,324 0.1 35.121 189,324 0.1 35.822 189,324 0.1 34.716 189,325 0.1 33.617 189,328 0.1 34.515 189,329 0.1 33.11 189,334 0.1 32.62 189,334 0.1 33.13 189,334 0.1 33.44 189,334 0.1 34.25 189,334 0.1 34.48 189,334 0.1 35.512 189,334 0.1 37.513 189,334 0.1 38.914 189,334 0.1 33.86 189,335 0.1 34.630 189,697 0.3 35.231 189,697 0.3 35.632 189,697 0.3 37.529 189,716 0.3 34.7Next, we applied both no-flow and with-flow methods to solve this roadnetwork problem. For the one-at-a-time method, the minimum cost and thetotal computation time are selected as the base for comparison like previousexamples. However, since this problem is quite extensive, the CPLEX solvercould not solve this problem as a single optimization problem and ran outof memory. Table 3.12 shows the results for these three methods.So, in this case, we used the divide and conquer method to solve the road403.4. Experimental results of the real-world examplesTable 3.12: Comparison of results for different methods (Real case two).Method Cost ($) Diff (%) Time (hr) SpeedupOne-at-a-time (best) 189,154 - 0.3 -No-flow out of memoryWith-flow out of memorynetwork problem. First, we divided the entire road network into two smallroad networks, each with sixteen roads and eight intersections. Next, theno-flow method and the with-flow method are used to solve these problems.Finally, the two small road network’s results were combined to get the resultsof the entire road network. Similarly, we also further divided the entireroad network into four and eight small road networks. Table 3.13 showsthe comparison of these results. Here, for the one-at-a-time method, theminimum cost and the average computation time of solving all the roads onceis selected as the base for better comparison with the divide and conquermethod.Table 3.13: Comparison of results for using the divide and conquer method(Real case two).Method Cost ($) Diff (%) TimeOne-at-a-time (32 roads) 189,154 - 34.7 secDivide and conquer(2 clusters)No-flow 189,046 -0.1 6.4 hrWith-flow 188,446 -0.4 5.6 hrDivide and conquer(4 clusters)No-flow 189,234 0.0 3.4 minWith-flow 188,716 -0.2 3.5 minDivide and conquer(8 clusters)No-flow 189,235 0.0 1.2 minWith-flow 188,834 -0.2 1.5 minIn the case of the one-at-a-time method, it was able to solve the problemwithin 0.3 hours for 32 different initial roads. However, when we used thedivide and conquer method in the case of 2 clusters, it took a significantlyhigher computation time compare to the one-at-a-time. Because even afterdividing the entire road network into two small road networks, these twosub-problems were still too big. However, if we use the divide and con-quer method in the case of 4 or 8 clusters, we can significantly lower the413.5. Discussion and Recommendationcomputation time of the total solution.3.5 Discussion and RecommendationOne disadvantage of using the divide and conquer method is that once wedivide the road network into two or more clusters, we can no longer guaranteethe global minimum unless we consider all the possible ways to make two ormore clusters. This is also true for the one-at-a-time method. Since boththe one-at-a-time and divide and conquer methods do not guarantee globalminimum and require exhaustive iterations, we can choose to solve the roadnetwork problem only once by using the one-at-a-time method with anysequences of roads in this case. Then in this example, the one-at-a-timemethod can solve all the roads within 34.7 seconds on average for any singlesequence of roads. So, in this example, where the roads are comparativelylong, the one-at-a-time method is the best method to solve the road networkproblem. However, we need to further experiment on more road networkexamples of different lengths and terrains to see that if this conclusion holdsfor every long road networks or not.In summary, when the road network is comparatively small such as theacademic cases and the real-world road network example one, it is better touse the with-flow method to solve the vertical alignments of all the roadsconsidering earthwork costs. However, if the road network is extensive likethe real-world road network example two, we are better off using the one-at-a-time method as it is significantly faster than the other three methodswith minimal changes to the optimal cost.42Chapter 4Conclusion and future work4.1 ConclusionIn this research, we extended the previous quasi network flow model[HHLR14] and presented a multi-road quasi network flow model for thevertical alignment optimization of the entire road network instead of a singleroad considering earthwork cost. This model also considers side-slopes and asingle material to move but assumes no blocks present in the terrain. We alsopresented and compared four different methods to solve the road networkproblem. Among these four methods, only the one-at-a-time method usesthe quasi network flow model, and the other three methods use the multi-road quasi network flow model to optimize the entire road network. Theproposed model can also be applied in the construction of railways, highways,pipelines, etc. but needs further validation.We then applied these methods on two different real-world road networkexamples: one comparatively small with 12 roads and 5 intersections andone more extensive road network with 32 roads and 16 intersections. Theexperimental results from these examples show that using the with-flowmethod in small road networks reduces the optimal cost by 7.2% withoutany significant changes to the computation time. However, the with-flowmethod’s computation time in an extensive road network is exceptionallylong compared to the one-at-a-time method’s computation time withoutany significant changes to the optimal cost.4.2 Future research4.2.1 Three dimensional road network design optimizationCurrently, the proposed MR-QNF model assumes that the corridors andthe horizontal alignments of the roads in a road network are predetermined.However, in the three-dimensional alignment optimization problem, the hor-izontal and vertical alignments of the road are optimized simultaneously andoften involve optimizing the vertical alignments multiple times to optimize434.2. Future researchthe horizontal alignments of the roads. Moreover, as this MR-QNF modelcan accurately optimize the vertical alignments of the roads in a road net-work, future research can be done using this model to get a more precisesolution to the road network design optimization problem.4.2.2 Multi-material and multi-haul extensionThe MR-QNF model is an extended model of the QNF model, whichconsiders a single haul and a single material to move in a road network.Nevertheless, in reality, multiple types of materials can be found on theearth, which has to be taken into account for the vertical alignment opti-mization of a road. So, Hossain [Hos13] proposed a model that considersmulti-material and then Beiranvand, Hare, and Lucet [BHLH17] improvedthe model [Hos13] and proposed a multi-haul quasi network flow model(MH-QNF) for the vertical alignment problem, which considers both multi-material and multi-haul. However, these models [Hos13, BHLH17] are onlyapplicable for vertical alignment optimization of a single road. Hence, infuture research, the proposed MR-QNF model can be extended so that bothmulti-material and multi-haul are taken into account for optimizing the ver-tical alignments of the roads in a road network considering earthwork cost.4.2.3 Other areas of improvementDifferent values of excavation, embankment, hauling, or loading costsmay impact the computation time of the MR-QNF model. In this research,we assumed only a fixed set of costs for all the experiments. However,different terrains may have different values for these costs. Hence, in futureresearch, a sensitivity model can be generated to determine the stabilityregions of these cost parameters for a given road network.In this research, we only assumed four types of construction costs forbuilding the road network and did not take into account other costs such asuser costs, reducing fuel cost of vehicles, [Akh21], reducing greenhouse gas(GHG) emissions, etc. So, in the future, further research could be exploredto incorporate one or more of these costs in constructing the roads.44Bibliography[ABS+13] K. Aruga, P. Bettinger, J. Sessions, et al. Using optimizationtechniques in designing forest roads and road networks. BartınOrman Faku¨ltesi Dergisi, 15(1):49–62, 2013. → pages 1[AHJL20] M. Aziz, W. Hare, M. Jaberipour, and Y. Lucet. Multi-fidelityalgorithms for the horizontal alignment problem in road design.Engineering Optimization, 52(11):1848–1867, 2020. → pages 3[Aka06] A. E. Akay. Minimizing total costs of forest roads with computer-aided design model. Sadhana, 31(5):621–633, 2006. → pages 5[Akh21] A. Akhmet. Multiobjective Optimization for Road Vertical Align-ment Design. PhD thesis, University of British Columbia, 2021.→ pages 44[Aru05] K. Aruga. Tabu search optimization of horizontal and ver-tical alignments of forest roads. Journal of Forest Research,10(4):275–284, 2005. → pages 6[ATSM06] K. Aruga, T. Tasaka, J. Sessions, and E. S. Miyata. Tabu searchoptimization of forest road alignments combined with shortestpaths and cubic splines. Croatian Journal of Forest Engineer-ing: Journal for Theory and Application of Forestry Engineer-ing, 27(1):37–47, 2006. → pages 6[BHLH17] V. Beiranvand, W. Hare, Y. Lucet, and S. Hossain. Multi-haulquasi network flow model for vertical alignment optimization.Engineering Optimization, 49(10):1777–1795, 2017. → pages 5,8, 12, 44[CGF89] E. P. Chew, C. J. Goh, and T. F. Fwa. Simultaneous optimiza-tion of horizontal and vertical alignments for highways. Trans-portation Research Part B: Methodological, 23(5):315–329, 1989.→ pages 545Bibliography[Cpl09] IBM ILOG Cplex. V12. 1: User’s Manual for CPLEX. Inter-national Business Machines Corporation, 46(53):157, 2009. →pages 7, 26[DJ09] C. Davis and M. K. Jha. Modeling the effects of socioeconomicfactors in highway construction and expansion. Journal of Trans-portation Engineering, 135(12):990–998, 2009. → pages 1[Eas88] S. M. Easa. Selection of roadway grades that minimize earthworkcost using linear programming. Transportation Research Part A:General, 22(2):121–136, 1988. → pages 4[FCS02] T. F. Fwa, W. T. Chan, and Y. P. Sim. Optimal vertical align-ment analysis for highway design. Journal of TransportationEngineering, 128(5):395–402, 2002. → pages 4[GLA09] A. B. Goktepe, A. H. Lav, and S. Altun. Method for optimalvertical alignment of highways. In Proceedings of the Institu-tion of Civil Engineers-Transport, volume 162, pages 177–188.Thomas Telford Ltd, 2009. → pages 4[HHL+16] D. Hirpa, W. Hare, Y. Lucet, Y. Pushak, and S. Tesfamariam. Abi-objective optimization framework for three-dimensional roadalignment design. Transportation Research Part C: EmergingTechnologies, 65:61–78, 2016. → pages 6[HHLR14] W. Hare, S. Hossain, Y. Lucet, and F. Rahman. Models andstrategies for efficiently determining an optimal vertical align-ment of roads. Computers & Operations Research, 44:161–173,2014. → pages 8, 11, 43[HKL11] W. L. Hare, V. R. Koch, and Y. Lucet. Models and algorithms toimprove earthwork operations in road design using mixed integerlinear programming. European Journal of Operational Research,215(2):470–480, 2011. → pages 2, 5, 6[HLR15] W. Hare, Y. Lucet, and F. Rahman. A mixed-integer linear pro-gramming model to optimize the vertical alignment consideringblocks and side-slopes in road construction. European Journalof Operational Research, 241(3):631–641, 2015. → pages 5[Hos13] S. Hossain. Models and strategies for efficiently optimizing thevertical alignment of roads for multimaterial. PhD thesis, Uni-versity of British Columbia, 2013. → pages 5, 4446Bibliography[Jha03] M. K. Jha. Criteria-based decision support system for select-ing highway alignments. Journal of Transportation Engineering,129(1):33–41, 2003. → pages 1[JS03] J. Jong and P. Schonfeld. An evolutionary model for simultane-ously optimizing three-dimensional highway alignments. Trans-portation Research Part B: Methodological, 37(2):107–128, 2003.→ pages 1[JS04] M. K. Jha and P. Schonfeld. A highway alignment optimiza-tion model using geographic information systems. Transporta-tion Research Part A: Policy and Practice, 38(6):455–481, 2004.→ pages 1[JSJ06] M. K. Jha, P. Schonfeld, and J. C. Jong. Intelligent road design,volume 19. WIT press, 2006. → pages 1[KL10] V. R. Koch and Y. Lucet. A note on: Spline technique formodeling roadway profile to minimize earthwork cost. Journalof Industrial & Management Optimization, 6(2):393, 2010. →pages 4[LC01] Y. Lee and J. Cheng. Optimizing highway grades to minimizecost and maintain traffic speed. Journal of Transportation En-gineering, 127(4):303–310, 2001. → pages 4[LL15] C. Liu and M. Lu. Optimizing earthmoving job planning basedon evaluation of temporary haul road networks design for massearthworks projects. Journal of Construction Engineering andManagement, 141(3):04014082, 2015. → pages 5[Lo¨f04] J. Lo¨fberg. YALMIP : A Toolbox for Modeling and Optimiza-tion in MATLAB. In In Proceedings of the CACSD Conference,Taipei, Taiwan, 2004. → pages 7, 26[LPS+16] W. Li, H. Pu, P. Schonfeld, H. Zhang, and X. Zheng. Methodol-ogy for optimizing constrained 3-dimensional railway alignmentsin mountainous terrain. Transportation Research Part C: Emerg-ing Technologies, 68:549–565, 2016. → pages 6[LPZL13] W. Li, H. Pu, H. Zhao, and W. Liu. Approach for Optimizing3D Highway Alignments Based on Two-stage Dynamic Program-ming. JSW, 8(11):2967–2973, 2013. → pages 1, 647Bibliography[MA04] A. A. Moreb and M. S. Aljohani. Quadratic representation forroadway profile that minimizes earthwork cost. Journal of Sys-tems Science and Systems Engineering, 13(2):245–252, 2004. →pages 4[MAT18] MATLAB. 9.7.0.1190202 (R2019b). The MathWorks Inc., Nat-ick, Massachusetts, 2018. → pages 7, 26[MLH15] S. Mondal, Y. Lucet, and W. Hare. Optimizing horizontal align-ment of roads in a specified corridor. Computers & OperationsResearch, 64:130–138, 2015. → pages 3[Mor96] A. A. Moreb. Linear programming model for finding optimalroadway grades that minimize earthwork cost. European Journalof Operational Research, 93(1):148–154, 1996. → pages 4[Mor09] A. A. Moreb. Spline technique for modeling roadway profile tominimize earthwork cost. Journal of Industrial & ManagementOptimization, 5(2):275, 2009. → pages 4, 5[oPWS19] Minister of Public Works and Government Services. Transporta-tion in Canada 2019. Catalogue No. T1-21E-PDF, 2019.→ pages1[PHL16] Y. Pushak, W. Hare, and Y. Lucet. Multiple-path selectionfor new highway alignments using discrete algorithms. EuropeanJournal of Operational Research, 248(2):415–427, 2016. → pages2[PSS+19] H. Pu, T. Song, P. Schonfeld, W. Li, H. Zhang, J. Wang, J. Hu,and X. Peng. A three-dimensional distance transform for op-timizing constrained mountain railway alignments. Computer-Aided Civil and Infrastructure Engineering, 34(11):972–990,2019. → pages 6[PXS+21] H. Pu, J. Xie, P. Schonfeld, T. Song, W. Li, J. Wang, and J. Hu.Railway alignment optimization in mountainous regions consid-ering spatial geological hazards: A sustainable safety perspec-tive. Sustainability, 13(4):1661, 2021. → pages 6[Rah12] M. Rahman. Optimizing the vertical alignment under earthworkblock removal constraints in road construction. PhD thesis, Uni-versity of British Columbia, 2012. → pages 848Bibliography[RHB04] M. J. Richard, M. Z. Huang, and M. Bouazara. Computeraided analysis and optimal design of mechanical systems usingvector-network techniques. Applied Mathematics and Computa-tion, 157(1):175–200, 2004. → pages 1[SPS+20a] T. Song, H. Pu, P. Schonfeld, W. Li, H. Zhang, Y. Ren,J. Wang, J. Hu, and X. Peng. Parallel three-dimensionaldistance transform for railway alignment optimization usingopenmp. Journal of Transportation Engineering, Part A: Sys-tems, 146(5):04020029, 2020. → pages 6[SPS+20b] T. Song, H. Pu, P. Schonfeld, H. Zhang, W. Li, J. Hu,and J. Wang. Mountain railway alignment optimizationconsidering geological impacts: A cost-hazard bi-objectivemodel. Computer-Aided Civil and Infrastructure Engineering,35(12):1365–1386, 2020. → pages 6[Tan99] J. Tan. Locating forest roads by a spatial and heuristic procedureusing microcomputers. Journal of Forest Engineering, 10(2):91–100, 1999. → pages 1[Tan00] J. Tan. Application of dynamic programming to optimum loca-tion of a forest road. Journal of Forest Engineering, 11(2):33–42,2000. → pages 1[TT03] C. W. Tat and F. Tao. Using GIS and genetic algorithm in high-way alignment optimization. In Proceedings of the 2003 IEEEInternational Conference on Intelligent Transportation Systems,volume 2, pages 1563–1567. IEEE, 2003. → pages 5[YL16] C. Yi and M. Lu. A mixed-integer linear programming approachfor temporary haul road design in rough-grading projects. Au-tomation in Construction, 71:314–324, 2016. → pages 3, 5[ZPS+20] H. Zhang, H. Pu, P. Schonfeld, T. Song, W. Li, J. Wang, X. Peng,and J. Hu. Multi-objective railway alignment optimization con-sidering costs and environmental impacts. Applied Soft Comput-ing, 89:106105, 2020. → pages 649AppendicesAppendix AUnit testsUnit testing is a technique that is used to determine if there are anycomplications or defects within each component of the software code. Itis usually executed after a new component is added to the existing codeand validates that all the previous components and the new component isperforming as expected. A good unit test will significantly reduce both timeand cost by detecting defects at the beginning of the software developmentphase. The key to a good unit test is to make a proper test plan. In ourresearch, we made six different unit tests of varying designs to ensure thatthe code for the MR-QNF model is functioning as required.Our research assumes that a road can be connected to an intersectionat two endpoints only. No intersection can be found in the middle or anyother part of the road except at the beginning or end of the road. Theroads are designed in this way so that the proposed model can handle anycomplex pattern that can be found in the road network. The unit tests arealso designed in this way.A.1 Unit test 1 (linear road)The first unit test is the simplest one with one road and linear groundprofile. In this case, the MR-QNF model should return a zero-cost solutionas no materials are required to move. Figure A.1 shows the road design forthe case of unit test 1.50A.2. Unit test 2 (single intersection)Figure A.1: Road design of unit test 1.A.2 Unit test 2 (single intersection)The second unit test consists of three roads and one intersection to verifythat the model works as expected when an intersection is introduced to themodel. Figure A.2 shows the road network design for the case of unit test2. This unit test consists of three roads instead of two roads because anintersection can not be in the middle of the road in this model.Figure A.2: Road network design of unit test 2.A.3 Unit test 3 (multiple intersections)The third unit test is consists of five roads and two intersections to verifythat the model can manage more than one intersections. Figure A.3 showsthe road network design for the case of unit test 3.51A.4. Unit test 4 (single loop)Figure A.3: Road network design of unit test 3.A.4 Unit test 4 (single loop)A road network can sometimes have a loop in its design. Figure A.4shows such an example of a road network design to ensure that each newcomponent added to the model is compatible even when it has a loop. Thisunit test consist of two roads and one intersection. Here, both end of oneof the road is connected to the same intersection and only one end of theother road in connected to this intersection.Figure A.4: Road network design of unit test 4.52A.5. Unit test 5 (multiple loops)A.5 Unit test 5 (multiple loops)Figure A.5 shows an example of a road network design for unit test 5of three roads and two intersections that has multiple loops. Here, one endof all the three roads are connected to one of the intersection and the otherends are connected to the other intersection.Figure A.5: Road network design of unit test 5.53Appendix BClass diagram of theMR-QNF modelFigure B.1: Class diagram of the MR-QNF model54Appendix CDesign parameters of theacademic casesC.1 Academic case twoTable C.1: Design parameters of the academic case two.RdNo INo SNo X Y Z Offset Quantity RdINo1 0 0 0 298 -4 4501 0 0 0 298 -2 1501 0 0 0 298 0 01 0 0 0 298 2 -1001 0 0 0 298 4 -3001 50 50 0 311 -4 4501 50 50 0 311 -2 1501 50 50 0 311 0 01 50 50 0 311 2 -1001 50 50 0 311 4 -3001 100 100 0 315 -4 450 11 100 100 0 315 -2 150 11 100 100 0 315 0 0 11 100 100 0 315 2 -100 11 100 100 0 315 4 -300 12 0 100 0 315 -4 450 12 0 100 0 315 -2 150 12 0 100 0 315 0 0 12 0 100 0 315 2 -100 12 0 100 0 315 4 -300 12 50 150 0 311 -4 4502 50 150 0 311 -2 150Continued on next page55C.1. Academic case twoTable C.1 – continued from previous pageRdNo INo SNo X Y Z Offset Quantity RdINo2 50 150 0 311 0 02 50 150 0 311 2 -1002 50 150 0 311 4 -3002 100 200 0 298 -4 4502 100 200 0 298 -2 1502 100 200 0 298 0 02 100 200 0 298 2 -1002 100 200 0 298 4 -3003 0 100 0 315 -4 450 13 0 100 0 315 -2 150 13 0 100 0 315 0 0 13 0 100 0 315 2 -100 13 0 100 0 315 4 -300 13 50 100 50 315 -4 4503 50 100 50 315 -2 1503 50 100 50 315 0 03 50 100 50 315 2 -1003 50 100 50 315 4 -3003 100 100 100 315 -4 4503 100 100 100 315 -2 1503 100 100 100 315 0 03 100 100 100 315 2 -1003 100 100 100 315 4 -3001 0 100 0 315 -4 4501 0 100 0 315 -2 1501 0 100 0 315 0 01 0 100 0 315 2 -1001 0 100 0 315 4 -30056
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Lucet, Yves
A multi-road quasi network flow model for vertical alignment optimization of a road network
Text