Multi-Haul Quasi Network FlowModel for Vertical AlignmentOptimizationbyVahid BeiranvandB.Sc. Hons., Islamic Azad University, Iran, 2008M.Sc., National University of Malaysia, 2012A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Interdisciplinary Studies)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)January 2016c© Vahid Beiranvand, 2016AbstractThe vertical alignment optimization problem for road design aims togenerate a vertical alignment of a new road with a minimum cost, whilesatisfying safety and design constraints. We present a new model calledmulti-haul quasi network flow (MH-QNF) for vertical alignment optimiza-tion that improves the accuracy and reliability of previous mixed integerlinear programming models. We evaluate the performance of the new modelcompared to two state-of-the-art models in the field: the complete trans-portation graph (CTG) and quasi network flow (QNF) models. The numer-ical results show that, within 1% relative error, the proposed model is robustand solves more than 93% of test problems. Whereas, the CTG only solvesabout 82% of test problems and QNF fails to solve any problem within 1%relative error. Moreover, in terms of computational time, on average theMH-QNF model solves the problems approximately 8 times faster than theCTG model.iiPrefaceThis research is based on work conducted in the Centre for Optimiza-tion, Convex Analysis & Nonsmooth Analysis (COCANA) by Dr. W. Hare,Dr. Y. Lucet, and V. Beiranvand. I was responsible for developing themodel, implementing it, and evaluating its performance by designing andperforming experiments.A version of this thesis has been submitted to a journal for publication asV. Beiranvand, W. Hare, Y. Lucet and S. Hossain (2015). Multi-Haul QuasiNetwork Flow Model for Vertical Alignment Optimization. I conducted allthe testing and wrote the manuscript. Shahadat Hossain contributed byproviding ideas.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . viiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Horizontal alignment optimization . . . . . . . . . . . . . . . 21.2 Vertical alignment optimization . . . . . . . . . . . . . . . . . 21.3 Three dimensional alignment optimization . . . . . . . . . . . 41.4 Research overview . . . . . . . . . . . . . . . . . . . . . . . . 5Chapter 2: Multi-haul quasi network flow model . . . . . . . . 62.1 Model variables and parameters . . . . . . . . . . . . . . . . . 62.2 Multi-haul quasi network flow model . . . . . . . . . . . . . . 82.2.1 Cost components . . . . . . . . . . . . . . . . . . . . . 132.2.2 Objective function and constraints . . . . . . . . . . . 132.3 The CTG and QNF Models . . . . . . . . . . . . . . . . . . . 20Chapter 3: Numerical results . . . . . . . . . . . . . . . . . . . 243.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . . . 243.2 Reporting the results . . . . . . . . . . . . . . . . . . . . . . . 28Chapter 4: Conclusions . . . . . . . . . . . . . . . . . . . . . . . 334.1 Future research . . . . . . . . . . . . . . . . . . . . . . . . . . 34ivTABLE OF CONTENTS4.1.1 Three dimensional road design optimization . . . . . . 344.1.2 Model uncertainty . . . . . . . . . . . . . . . . . . . . 344.1.3 Human-based experiment . . . . . . . . . . . . . . . . 34Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35vList of TablesTable 3.1 Basic roads used to assemble the test collection. . . . . 25Table 3.2 Cost components in $/cu.m. . . . . . . . . . . . . . . . 25Table 3.3 Summary of model accuracy for each model. . . . . . . 28Table 3.4 Solution times (in second) for 1% relative error. . . . . 30viList of FiguresFigure 1.1 Some potential horizontal alignments in a corridor. . 2Figure 1.2 Some potential vertical alignments for a ground profile. 3Figure 2.1 A typical section in MH-QNF model . . . . . . . . . . 9Figure 2.2 Load and unload flows in the MH-QNF model . . . . 10Figure 2.3 Borrow flows in the MH-QNF model . . . . . . . . . . 11Figure 2.4 Waste flows in the MH-QNF model . . . . . . . . . . 12Figure 2.5 CTG model for a three-sections-long road. . . . . . . 20Figure 2.6 QNF model for a three-sections-long road. . . . . . . 22Figure 2.7 MH-QNF model for a three-sections-long road. . . . . 23Figure 3.1 Cost configuration. . . . . . . . . . . . . . . . . . . . 27Figure 3.2 Performance profiles with up to 1% relative error. . . 32viiAcknowledgmentsI would like to express my sincere gratitude to all the individuals whowere involved directly or indirectly with this work. Specially, I would like tothank my supervisors Dr. Warren Hare and Dr. Yves Lucet for their contin-uous support during the research, their patience, motivation, and knowledge.I am thankful to our industrial partner (Softree Technical Systems Inc.)for supporting the research. In particular, David Mills, Craig Speirs, andAlexis Guigue for providing technical information and valuable feedbackthroughout this thesis.This research is funded by a Collaborative Research and Development(CRD) Grant from the Natural Sciences and Engineering Research Council(NSERC) of Canada, and Softree Technical Systems Inc.viiiChapter 1IntroductionTransportation infrastructures are an important sign of development andwelfare in a given country [CCGC15, HL07]. While planners normally tryto balance and coordinate among various transportation methods, roadsand highways are considered the leading component of transportation in-frastructures. Due to the fast increase of traffic volume, the high cost ofroad construction projects, and the environmental and safety impacts ofthese projects, road projects require continuing innovation to minimize thecosts while satisfying environmental and safety constraints. Road design isone of the early and significant steps in road construction projects. Roaddesign influences the construction cost and other contributing constraintsremarkably. From the optimization point of view, the main objective inroad design problems is to minimize the road construction costs (primar-ily excavation, embankment, and hauling costs), subject to road safety andquality constraints.Road design starts by determining the corridor where the road is to beconstructed. From here, a so called horizontal alignment is fixed. Next, ver-tical alignment and earthwork movement problems must be solved. In theliterature, these last two steps are often combined for the sake of efficiency[MA04, HKL11]. To calculate horizontal alignment, the vertical alignmentand earthwork movement problems should be solved accurately. If the ver-tical alignment and earthwork problems can be solved faster, then we canevaluate more possible horizontal alignments. Therefore by solving the ver-tical alignment and earth work movement problems accurately with a lowcomputational cost, we can obtain a more precise horizontal alignment.It should be noted that there are some studies that consider simultane-ous optimization of horizontal alignment, vertical alignment, and earthworkmovement [CGF89, HEAEH98, ESHS02, CL06]. However, by necessity,these approaches all use some heuristic(s), and the resulting roads gener-ally still require a final detailed optimization of the vertical alignment andearthwork movement problems. In this research we focus on solving thecombined vertical alignment and earthwork movement problem.Considering the combined vertical alignment and earthwork movement11.1. Horizontal alignment optimizationproblem, we note that the final solution must satisfy various constrain-ing factors, such as safety standards, economical limitations, environmen-tal constraints, engineering requirements, and socioeconomic requirements[Fwa06, AAS11]. In addition to these considerations, inclusion of a set of de-sign constraints and operational requirements makes the vertical alignmentand earthwork movement problem complicated.1.1 Horizontal alignment optimizationIn a given corridor there are a lot of possible routes that can connect thesource point to the destination point by building a road (see Figure 1.1).In horizontal alignment design, the objective is to identify the best routeamong all possible routes between the given points to build the road. Thebest route is the one with the lowest cost while satisfying all the designrequirements. For the detailed understanding of the horizontal alignmentoptimization we refer to [MLH15].Y X Corridor Horizontal Alignments Figure 1.1: Some potential horizontal alignments in a corridor.1.2 Vertical alignment optimizationIn the vertical alignment optimization the horizontal alignment is fixed.The vertical alignment is a modification of the ground profile elevation re-quired to build a road that minimizes the cost of road construction whilesatisfying safety and regulation constraints [HHLR14]. An example of a21.2. Vertical alignment optimizationvertical alignment is shown in Figure 1.2. In other words, the vertical align-ment optimization seeks the minimum earthwork allocation cost satisfyingthe vertical alignment design constraints.Elevation XY plane Ground profile Potential vertical alignments Figure 1.2: Some potential vertical alignments for a ground profile.Past research on the vertical alignment problem has introduced a numberof interesting techniques. Heuristic optimization methods, such as GeneticAlgorithms (GAs), have been used by a number of authors. For example,Lee and Cheng [LC01] developed a mathematical model for vertical align-ment and proposed a heuristic method to solve it. Jha et al. [JSJK06]present a comprehensive review of the road design problem and the relatedchallenges. They also present solution algorithms based on GAs to optimizehighway alignments by adapting operators and encoding schemes. Otherheuristic based optimization methods for highway alignment optimizationinclude [JS03, Aru05, KJS05, GLA09, KJS12]. Since the genetic algorithmsand other heuristic based methods are non-deterministic they do not guar-antee finding the optimum solution. Moreover, the results obtained by thesemethods are subject to change in different runs of the same algorithm onthe same test problem. Therefore, we focus our research on mixed integerlinear programming methods (discussed below).Another early approach relied on dynamic programming. Dynamic pro-gramming was first employed by Goh et al. [GCF88] to develop two modelsfor vertical alignment. They use piecewise-linear segments to represent thealignment. In general, compared to optimizing the horizontal alignment, thedynamic programming approach has a better performance in vertical align-ment optimization; however, the resulting alignment is limited to a finite set31.3. Three dimensional alignment optimizationof points at each station. It means that only a portion of the problem searchspace is explored [Jon98]. Other models can be found in the literature whichuse dynamic programming [NEW75, Tri87, LPZL13].The current state-of-the-art on the vertical alignment and earthworkmovement problem relies on linear programming, or mixed integer linearprogramming. Easa [Eas88] proposed a two-steps linear programming modelto optimize vertical alignment and earthwork movement. In the first step,by enumerating all technically feasible grades, a feasible road grade is chosenand for each grade the amount of cut and fill is calculated. In the secondstep, the earthwork transportation cost is minimized using linear program-ming. This trial and error approach does not guarantee finding the globalsolution. Moreb [Mor96] proposed a linear programming model for verticalalignment which incorporates the grade selection and earthwork allocationstages. In [MA04], Moreb and Aljohani extended the work of Easa [Eas88]to handle the sharp connectivity points problem in piecewise linear mod-els by representing the road profile as a continuous quadratic curve. In[Mor09], Moreb proposed a model in which the road profile is represented asa one-dimensional spline. This model improves the computational efficiencyand guarantees the global optimality by solving a single linear programmingproblem. Koch and Lucet [KL10] improved the Moreb model by introducingnew gap and slope constraints that reduce errors in the model.Hare et al. [HKL11] developed a mixed integer linear program (MILP)model for earthwork operations in which blocks are also taken into account.In [HLR15], the vertical alignment problem is dealt with and road sideslopes are added to the previous MILP model proposed in [HKL11], andhence, a more accurate earthwork cost calculation is obtained. In anotherupdate [HHLR14], Hare et al. improved the performance of the MILP model(called complete transportation graph or CTG) and studied a novel quasinetwork flow (QNF) model for vertical alignment optimization consideringthe earthwork allocations. The QNF model presented significant improve-ments in computational time, but at a cost of decreased accuracy in the finalsolution. The CTG and QNF models play a key role in this thesis; furtherdetails on these models can be found in Section 2.3.1.3 Three dimensional alignment optimizationIn three dimensional alignment optimization, the above-mentioned roaddesign phases (i.e., the vertical and horizontal alignments optimization) areoptimized, simultaneously. For a detailed discussion on three dimensional41.4. Research overviewalignment optimization we refer to [MLH15].1.4 Research overviewIn this research, we improve the quasi network flow model of [HHLR14],by presenting a new model called the multi-haul quasi network flow (MH-QNF) model. The MH-QNF model balances the accuracy of the CTG modelin approximating the earthwork cost with the low computational cost of theQNF model. The main idea behind the new model is to differentiate betweenhauls of different distances in earthwork allocation.5Chapter 2Multi-haul quasi networkflow modelIn this chapter we describe the variables, parameters, and sets requiredto model the vertical alignment of roads. We first provide extensive detailson the multi-haul quasi network flow (MH-QNF) model. Then we describethe quasi network flow (QNF) and complete transportation graph (CTG)models. All models are designed to optimize vertical alignment for a knownhorizontal alignment.2.1 Model variables and parametersThe road is approximated as a quadratic spline. It is split into m seg-ments indexed by G = {1, 2, ...,m}. For all g ∈ G, each segment is repre-sented using the following equationPg(s) = ag,1 + ag,2s+ ag,3s2 (2.1)in which s is the distance from the beginning of the segment.Each segment is further split into sections so that the gth spline segmentis made of ng sections indexed by the set Sg = {1, 2, ..., ng}. The totalnumber of sections in a road is n =∑g∈G ng and these sections are indexedby the set S = {1, 2, ..., n}. The section indexes of a specific spline segmentg are mapped to the actual section index set S using the function ϕ : (G ×Sg)→ S. For example, if ϕ(g, j) = i then si = sϕ(g,j) for all i ∈ S, g ∈ G, j ∈Sg. So the spline function representing the road profile is as followsP (s) =P1(s) if sϕ(1,1) ≤ s ≤ sϕ(1,n1),P2(s) if sϕ(2,1) ≤ s ≤ sϕ(2,n2),...Png(s) if sϕ(ng ,1) ≤ s ≤ sϕ(2,nng ).62.1. Model variables and parametersIn the vertical alignment problem, one goal is to obtain the optimaloffset between the ground profile and the road profile. In addition, therequired cut and fill volumes should be calculated for each offset. The offsetis denoted by ui, i ∈ S, and the cut and fill volumes of a section i aredenoted by V +i and V−i , i ∈ S respectively. When constructing a road weneed to consider borrow pits to bring in material and waste pits to dumpextra materials. They are modeled as external sections and indexed by thesets B = {1, 2, ..., nβ} and W = {1, 2, ..., nw} in which nβ is the number ofborrow pit sections and nw is the number of waste pit sections. A borrow pitindex is mapped to the section index to which it is attached by the functionϑ : B → S. Similarly, the function δ : W → S maps the waste pit index tothe section index to which it is attached.Access roads are required in road construction and they are used asgateways to the road being constructed. Access roads are linked to a sectionof the road and are indexed by the set R = {1, 2, ..., nr} in which nr is thenumber of access roads in the construction site. The function % : R → Smaps an access road index to the section index to which it is linked. Thecapacity of the ith borrow pit (respectively waste pit) is denoted by Cbi(respectively Cwi ). The set N = S∪B∪W = {1, 2, ..., n+nβ+nw} representsall the indexes for sections, borrow pits, and waste pits. The dead hauldistance is the distance between a borrow/waste pit and the section to whichit is linked. The dead haul distance of the ith borrow or waste pit is denotedby d˜i.The side slope is defined as the steady decrease/increase of height whenmoving orthogonally from the road profile to the ground profile in a cut/fillsection. Side slopes are represented as trapezoid shaped cross-sections andare approximated using stacked rectangles to preserve the linearity of themodel, see [HHLR14].Another important consideration in vertical alignment optimization areblocks [HKL11]. Blocks are obstacles that need to be removed to access someparts of the corridor. For example, they could indicate a river or mountain,and require building a bridge or a tunnel. We define nb as the number ofblocks in the corridor and the blocks are indexed by the set I = {1, 2, ..., nb}.The function γ : I → S maps a block index to the section index to whichit is linked. To model the block removal process we use a time step t whichspecifies the time at which a block is removed. In [HKL11], it is shown thatto remove nb blocks we need at most nb + 1 time steps. So we define the setT = {0, 1, 2, ..., nb} to model the required time steps and we use the binaryvariables yk,t for each block k ∈ I and time step t ∈ T to determine whethera block is removed or not. After a block is removed we can move material72.2. Multi-haul quasi network flow modelover its section.2.2 Multi-haul quasi network flow modelIn the MH-QNF model, similar to the QNF model [HHLR14], we drawsections and pits as nodes while arcs show feasible movements between them.In the QNF model the authors use a single haul to move materials. Youcan think of this single haul as a single type of earthmoving equipment suchas a bulldozer. In real roadway construction sites, different equipments arerequired for earthmoving tasks. For example, for the short distances usinga bulldozer may be more economical, while for a long distance movementa truck may be preferred. Therefore, to obtain a more realistic model, weextend the previous QNF model [HHLR14] by using multiple hauling paths.Figure 2.1 shows the typical flows for a section in the proposed MH-QNFmodel. In Figure 2.1, there are three hauling paths at each side. At eachside, you can think of each hauling path as a specific type of constructionmachinery with known hauling and loading costs. Depending on the haulingdistance we can determine which machinery is more efficient to be used. Inthis model, the material can be moved from the current section i to the nextsection (i + 1) or the previous one (i − 1). Depending on the distance ofa hauling task, the material movement can be performed through one of anumber of hauling paths indexed by H = {1, 2, ..., nh}. (In our figures andnumerical tests we shall apply nh = 3, which is based on consultation withour industry partner, whose standard software includes free-haul, over-haul,and end-haul.)When the flow of material reaches a section, materials can be unloadedto fill the section, or a cut from the section can be performed with thenew materials added to the flow, or the section remains unchanged and thematerial is transferred to the next section. To transfer material to the leftor right we use virtual transit nodes for both left and right directions. Sincewe have nh different hauls, nh groups of transit nodes are denoted in themodel, see Figure 2.2 (which represents three hauls for consistency withnumerical experiments). If material is moved to the next section, the left-side transit nodes are employed, otherwise if the material is moved to theprevious section the right-hand side transit nodes are used. In Figure 2.2,we define f r,si,i+1,t and fr,si,i−1,t (for all i ∈ S, t ∈ T ) as the flow of materialfrom the left (right) short haul transit node i to the left (right) short haultransit node i + 1 (or i − 1) at time step t, respectively. Similarly, we usethe variables f r,mi,i+1,t and fr,mi,i−1,t (for all i ∈ S, t ∈ T ) for the middle hauling82.2. Multi-haul quasi network flow modelBorrow pit transits Waste pit transits Inter-nodes transits Load & unload transits Transit node [i-1] ,, 1,r si i tf −,1, ,r si i tf +Transit node [i] Transit node [i+1] Right Short Haul ,1, ,r si i tf −,, 1,r si i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Short Haul Transit node [i-1] ,, 1,r mi i tf −,1, ,r mi i tf +Transit node [i] Transit node [i+1] Right Middle Haul ,1, ,r mi i tf −,, 1,r mi i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Middle Haul Transit node [i-1] ,, 1,r li i tf −,1, ,r li i tf +Transit node [i] Transit node [i+1] Right Long Haul ,1, ,r li i tf −,, 1,r li i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Long Haul Section [i] Borrow [j] Waste [k] Figure 2.1: A typical section in MH-QNF modelpath, and the variables f r,li,i+1,t and fr,li,i−1,t (for all i ∈ S, t ∈ T ) for the longhauling path.Figure 2.2 shows the load and unload flows that model the fill and cutvolumes of materials for each section. Whenever we want to move materialfrom a section i to the section j we need to cut material from section i.Then, the cut material should be loaded to the suitable machinery (i.e.,the material is unloaded from section) depending on the hauling distance.This loading task is modeled by the loading flows f l,hi−1,i,t and fl,hi+1,i,t (for alli ∈ S, t ∈ T , h ∈ H) depicted in Figure 2.2. Similarly, at the destinationsection j the unloading of material into the section is modeled using theunloading flows fu,hi,i+1,t and fu,hi,i−1,t (for all i ∈ S, t ∈ T , h ∈ H). Aftercutting the materials we can transfer it to the left or right using any ofthe three hauling options (short, middle, or long). Similarly, a section can92.2. Multi-haul quasi network flow modelSection [i] Transit node [i-1] ,, 1,r si i tf −,1, ,r si i tf +Transit node [i] Transit node [i+1] Right Short Haul ,1, ,r si i tf −,, 1,r si i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Short Haul Transit node [i-1] ,, 1,r mi i tf −,1, ,r mi i tf +Transit node [i] Transit node [i+1] Right Middle Haul ,1, ,r mi i tf −,, 1,r mi i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Middle Haul Transit node [i-1] ,, 1,r li i tf −,1, ,r li i tf +Transit node [i] Transit node [i+1] Right Long Haul ,1, ,r li i tf −,, 1,r li i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Long Haul ,, 1,u si i tf −,, 1,u si i tf +,1, ,l si i tf − , 1, ,l si i tf +,, 1,u mi i tf −,, 1,u mi i tf +,1, ,l mi i tf +, 1, ,l mi i tf −,, 1,u li i tf −,1, ,l li i tf +,, 1,u li i tf +,1, ,l li i tf −Figure 2.2: Load and unload flows in the MH-QNF modelbe filled using the materials taken from left or right transit nodes. Tomodel these possibilities, we introduce the variables f l,si−1,i,t and fl,si+1,i,t (forall i ∈ S, t ∈ T ) as the load (fill) flows of materials from the left and righttransit nodes for the short hauling path. The variables f l,mi−1,i,t, fl,mi+1,i,t; andf l,li−1,i,t and fl,li+1,i,t (for all i ∈ S, t ∈ T ) are used as the load flows of materialsfor the middle and long hauling paths, respectively. Similarly, the variablesfu,si,i+1,t and fu,si,i−1,t (for all i ∈ S, t ∈ T ) are the unload (cut) flows of materialsto the left and right transit nodes for the short hauling path. In the sameway, the variables fu,mi,i+1,t, fu,mi,i−1,t; and fu,li,i+1,t, fu,li,i−1,t (for all i ∈ S, t ∈ T )are the unload flows for the middle and long hauling paths, respectively.Figure 2.3 shows the borrow flows which are the flow of materials froma borrow pit to a section. In some cases, some extra material is required forthe construction project which is borrowed from a borrow pit. This meansthat the material should be cut from the borrow pit. Then, depending onthe distance between the borrow pit and destination section, the material isloaded to the appropriate machinery (or hauling path) to be transfered tothe destination section. Finally, at the destination section, the material is102.2. Multi-haul quasi network flow modelunloaded into the section. The borrow flows f b,hj,ϑ(j)+1,t and fb,hj,ϑ(j)−1,t (for allj ∈ B, t ∈ T , h ∈ H) in Figure 2.3, model this process.,, 1,b sj i tf −,, 1,b sj i tf +,, 1,b mj i tf −,, 1,b mj i tf +,, 1,b lj i tf + ,, 1,b lj i tf −Borrow [j] Transit node [i-1] ,, 1,r si i tf −,1, ,r si i tf +Transit node [i] Transit node [i+1] Right Short Haul ,1, ,r si i tf −,, 1,r si i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Short Haul Transit node [i-1] ,, 1,r mi i tf −,1, ,r mi i tf +Transit node [i] Transit node [i+1] Right Middle Haul ,1, ,r mi i tf −,, 1,r mi i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Middle Haul Transit node [i-1] ,, 1,r li i tf −,1, ,r li i tf +Transit node [i] Transit node [i+1] Right Long Haul ,1, ,r li i tf −,, 1,r li i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Long Haul Figure 2.3: Borrow flows in the MH-QNF modelEach borrow pit is attached to a section. In fact, a borrow flow denotes acut or unload flow from a borrow pit. The variables f b,sj,ϑ(j)+1,t and fb,sj,ϑ(j)−1,t(for all j ∈ B, t ∈ T ) can be used to transfer materials from a borrowpit to the next or the previous section via the short haul path. Similarly,to represent the borrow flows for the middle and long hauling paths wedefine the variables f b,mj,ϑ(j)+1,t, fb,mj,ϑ(j)−1,t; and fb,lj,ϑ(j)+1,t and fb,lj,ϑ(j)−1,t (forall j ∈ B, t ∈ T ), respectively. Waste flows are handled similarly, see Figure2.4.In Figure 2.4 the waste flows are shown. In some cases, in the construc-tion site we have some unused material at a section that cannot be usedin other sections of the road. In such conditions we can dump the unusedmaterial to a waste pit. To do so, we need to move material to the waste pitusing the appropriate hauling path (or construction machinery) and thenunload and fill the waste pit by the transferred material. Similar to bor-112.2. Multi-haul quasi network flow modelWaste [k] ,1, ,w mi k tf − ,1, ,w mi k tf +,1, ,w li k tf − ,1, ,w li k tf +,1, ,w si k tf − ,1, ,w si k tf +Transit node [i-1] ,, 1,r si i tf −,1, ,r si i tf +Transit node [i] Transit node [i+1] Right Short Haul ,1, ,r si i tf −,, 1,r si i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Short Haul Transit node [i-1] ,, 1,r mi i tf −,1, ,r mi i tf +Transit node [i] Transit node [i+1] Right Middle Haul ,1, ,r mi i tf −,, 1,r mi i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Middle Haul Transit node [i-1] ,, 1,r li i tf −,1, ,r li i tf +Transit node [i] Transit node [i+1] Right Long Haul ,1, ,r li i tf −,, 1,r li i tf +Transit node [i-1] Transit node [i] Transit node [i+1] Left Long Haul Figure 2.4: Waste flows in the MH-QNF modelrow flows, waste flows show the flow of material from a section to a wastepit. Waste pits are attached to specific sections. Material can be movedto a waste pit in both left and right directions via different hauling paths.The variables fw,sδ(k)−1,k,t and fw,sδ(k)+1,k,t (for all k ∈ W, t ∈ T ) represent thewaste flows to the waste pit k from both left and right directions throughthe short hauling path. Similarly, for the middle and long hauling paths thewaste flow variables fw,mδ(k)−1,k,t, fw,mδ(k)+1,k,t; and fw,lδ(k)−1,k,t, fw,lδ(k)+1,k,t (for allk ∈ W, t ∈ T ) are defined, respectively.A typical real-world road construction project involves several types ofmaterials with different excavation, embankment, and hauling costs. Theproposed model is able to handle more than one material. We define theindex set M = {1, 2, ..., nm} corresponding to the indexes of the differenttypes of materials. Different types of material can be excavated using dif-ferent types of construction machinery. On the other hand, the excavationand embankment costs depend on the material types. Therefore, by addingmore material types or changing the excavation costs associated with a spe-cific material type, in our model we are able to model different construction122.2. Multi-haul quasi network flow modelmachineries used to cut the earth. In this research, we chose nm = 4 basedon consultation with our industry partner.2.2.1 Cost componentsThe cost components of a vertical alignment problem consist of the em-bankment, excavation, and hauling costs of materials in the constructionsite. The per unit of volume excavation (cut or unload from a section) costof material is represented by p1, p2, ... pnm for different types of materials,respectively. Similarly, q1, q2, ... qnm denote the per unit volume of em-bankment (fill or load to a section) cost of material for the different typesof materials. Finally, for the short hauling path, the hauling cost of mate-rials from the section i to the section i − 1 (respectively i + 1) is definedas cr,si,i−1 = csdi,i−1 (respectively, cr,si,i+1 = csdi,i+1) in which cs is the cost ofmoving one unit volume of materials per unit distance for the short haulingpath, and di,j is the distance between sections i and j. Similarly, for themiddle hauling path we define the hauling cost components cr,mi,i−1 = cmdi,i−1and cr,mi,i+1 = cmdi,i+1; and for the long hauling path we have cr,li,i−1 = cldi,i−1and cr,li,i+1 = cldi,i+1. There is another cost when cutting materials from asection or a borrow pit and it is the loading cost. In the real world theloading cost of different construction equipments is different. Therefore, wedefine the loading cost components ys, ym, and yl as the cost of loading dif-ferent types of construction equipments which use short, middle, and longhauling paths, respectively. We do not consider the unloading cost of mate-rial from construction equipments because based on consultation with ourindustrial partner, it is cheap enough to be ignored.2.2.2 Objective function and constraintsIn the MH-QNF model the objective is to minimize the total cost of ex-cavation, embankment, and hauling tasks. Therefore, the objective functionis defined as follows.132.2. Multi-haul quasi network flow modelmin[ ∑i∈Sm∈Mh∈H(pm + yh)V+i +∑i∈Sm∈MqmV−i+∑i∈Sh∈Ht∈T(cr,hi,i−1fr,hi,i−1,t + cr,hi,i+1fr,hi,i+1,t)+∑j∈Bm∈Mh∈Ht∈T(pm + yh + chd˜j)(fb,hj,ϑ(j)−1,t + fb,hj,ϑ(j)+1,t)+∑k∈Wm∈Mh∈Ht∈T(qm + chd˜k)(fw,hδ(k)−1,k,t + fw,hδ(k)+1,k,t)].(2.2)Since the transit nodes are only intermediate virtual points that providetransits for the flows of materials, the sum of the input flows to a transitnode must be equal to the sum of the output flows from the node. Therefore,for all i ∈ S, h ∈ H, t ∈ T the flow constraints are defined asf r,hi−1,i,t + fu,hi,i+1,t +∑j∈Bϑ(j)=if b,hj,i+1,t = fr,hi,i+1,t + fl,hi−1,i,t +∑k∈Wδ(k)=ifw,hi−1,k,t, (2.3)f r,hi+1,i,t + fu,hi,i−1,t +∑j∈Bϑ(j)=if b,hj,i−1,t = fr,hi,i−1,t + fl,hi+1,i,t +∑k∈Wδ(k)=ifw,hi+1,k,t. (2.4)The section nodes are treated as the source and destination of the flows.Therefore, the total sum of load flows to a section or a waste pit shouldbe equal to the total fill volume of materials from that section or waste pit.Similarly, the total sum of unload flows from a section or a borrow pit shouldbe equal to the total cut volume of materials from that section or borrowpit. These constraints are called balance constraints and defined as∑t∈T(fu,hi,i+1,t + fu,hi,i−1,t) = V+i , i ∈ S, h ∈ H, (2.5)∑t∈T(f b,hj,ϑ(j)+1,t + fb,hj,ϑ(j)−1,t) = V+j , j ∈ B, h ∈ H, (2.6)142.2. Multi-haul quasi network flow model∑t∈T(f l,hi−1,i,t + fl,hi+1,i,t) = V−i , i ∈ S, h ∈ H, (2.7)∑t∈T(fw,hδ(k)−1,k,t + fw,hδ(k)+1,k,t) = V−k , k ∈ W, h ∈ H. (2.8)The borrow and waste pit constraints ensure that the total sum of bor-row/waste flows from/to a borrow/waste pit must not exceed the capacityof that borrow/waste, i.e.,∑t∈T(f b,hj,ϑ(j)+1,t + fb,hj,ϑ(j)−1,t) ≤ Cbj , j ∈ B, h ∈ H, (2.9)∑t∈T(fw,hδ(k)−1,k,t + fw,hδ(k)+1,k,t) ≤ Cwk , k ∈ W, h ∈ H. (2.10)Before introducing block constraints we require some additional nota-tions. Let I¯2 = {(k1, k2) ∈ I × I : k1 < k2, and k1, k2 are two consecutiveblocks with no access road in between them}, I¯← = {k ∈ I : the set ofblocks k before which there is no access road}, and I¯→ = {k ∈ I : the setof blocks k after which there is no access road}. To keep track of when ablock is removed, we introduce binary variables yk,t (i.e., it can be either 0or 1) for each block k ∈ I and t ∈ T . We also use the parameter Mi as thelargest possible cut or fill volume at a section i. For the sake of simplicity,we use M instead of Mi.Earth movement is not allowed between two sections when there is ablock between them. This means that for each hauling path h ∈ H, if asection i is a block then material cannot be moved over that block or section.In other words, the whole material moved to the section i from the sectioni − 1 must be loaded to section i; i.e., for the left transit nodes ∀h ∈ H,f r,hi−1,i,t = fl,hi−1,i,t. Moreover, if the section i is a block the only material thatcan move from this section to the next section (i + 1) is the material thathas been excavated from section i, i.e., for the left transit nodes ∀h ∈ H,f r,hi,i+1,t = fu,hi,i+1,t. In the case of the right transit nodes, fr,hi+1,i,t = fl,hi+1,i,t andf r,hi,i−1,t = fu,hi,i−1,t ensure that no material can move across section i to theprevious section. Therefore, for the left transit nodes, the constraints− (f r,hγ(i)−1,γ(i),t − f l,hγ(i)−1,γ(i),t) ≤Myi,t−1, ∀i ∈ I, h ∈ H, t ∈ T , (2.11)f r,hγ(i)−1,γ(i),t − f l,hγ(i)−1,γ(i),t ≤Myi,t−1, ∀i ∈ I, h ∈ H, t ∈ T , (2.12)152.2. Multi-haul quasi network flow model− (f r,hγ(i),γ(i)+1,t − fu,hγ(i),γ(i)+1,t) ≤Myi,t−1, ∀i ∈ I, h ∈ H, t ∈ T , (2.13)f r,hγ(i),γ(i)+1,t − fu,hγ(i),γ(i)+1,t) ≤Myi,t−1, ∀i ∈ I, h ∈ H, t ∈ T , (2.14)ensure that no material movement is allowed across a block. In the sameway, for the right transit nodes the constraints− (f r,hγ(i)+1,γ(i),t − f l,hγ(i)+1,γ(i),t) ≤Myi,t−1, ∀i ∈ I, h ∈ H, t ∈ T , (2.15)f r,hγ(i)+1,γ(i),t − f l,hγ(i)+1,γ(i),t ≤Myi,t−1, ∀i ∈ I, h ∈ H, t ∈ T , (2.16)− (f r,hγ(i),γ(i)−1,t − fu,hγ(i),γ(i)−1,t) ≤Myi,t−1, ∀i ∈ I, h ∈ H, t ∈ T , (2.17)f r,hγ(i),γ(i)−1,t − fu,hγ(i),γ(i)−1,t ≤Myi,t−1, ∀i ∈ I, h ∈ H, t ∈ T , (2.18)ensure no material movement across a block.The other scenario which should be ensured by the block constraints isthat material movement is not allowed between two blocks, before the firstblock, and after the last block with no access roads, until the blocks areremoved. Thus, for all h ∈ H, the transit, borrow, and waste flows areforbidden between two blocks with no access roads, until one of the blocksis removed, i.e.,f r,hi,i+1,t ≤M(yk1,t−1 + yk2,t−1),∀i ∈ S, (k1, k2) ∈ I¯2, h ∈ H, t ∈ T , γ(k1) ≤ i, i+ 1 ≤ γ(k2), (2.19)f r,hi+1,i,t ≤M(yk1,t−1 + yk2,t−1),∀i ∈ S, (k1, k2) ∈ I¯2, h ∈ H, t ∈ T , γ(k1) ≤ i, i+ 1 ≤ γ(k2), (2.20)f b,hj,ϑ(j)+1,t ≤M(yk1,t−1 + yk2,t−1),∀j ∈ B, (k1, k2) ∈ I¯2, h ∈ H, t ∈ T , γ(k1) ≤ ϑ(j)− 1, ϑ(j) + 1 ≤ γ(k2),(2.21)f b,hj,ϑ(j)−1,t ≤M(yk1,t−1 + yk2,t−1),∀j ∈ B, (k1, k2) ∈ I¯2, h ∈ H, t ∈ T , γ(k1) ≤ ϑ(j)− 1, ϑ(j) + 1 ≤ γ(k2),(2.22)162.2. Multi-haul quasi network flow modelfw,hδ(j)−1,j,t ≤M(yk1,t−1 + yk2,t−1),∀j ∈ W, (k1, k2) ∈ I¯2, h ∈ H, t ∈ T , γ(k1) ≤ δ(j)− 1, δ(j) + 1 ≤ γ(k2),(2.23)fw,hδ(j)+1,j,t ≤M(yk1,t−1 + yk2,t−1),∀j ∈ W, (k1, k2) ∈ I¯2, h ∈ H, t ∈ T , γ(k1) ≤ δ(j)− 1, δ(j) + 1 ≤ γ(k2).(2.24)After the last block with no access road, the transit, borrow, and wasteflows are not allowed until the block is removed:f r,hi,i+1,t ≤Myk,t−1, ∀i ∈ S, k ∈ I¯→, h ∈ H, t ∈ T , γ(k) ≤ i, i+ 1 ≤ n,(2.25)f r,hi+1,i,t ≤Myk,t−1, ∀i ∈ S, k ∈ I¯→, h ∈ H, t ∈ T , γ(k) ≤ i, i+ 1 ≤ n,(2.26)f b,hj,ϑ(j)+1,t ≤Myk,t−1,∀j ∈ B, k ∈ I¯→, h ∈ H, t ∈ T , γ(k) ≤ ϑ(j)− 1, ϑ(j) + 1 ≤ n, (2.27)f b,hj,ϑ(j)−1,t ≤Myk,t−1,∀j ∈ B, k ∈ I¯→, h ∈ H, t ∈ T , γ(k) ≤ ϑ(j)− 1, ϑ(j) + 1 ≤ n, (2.28)fw,hδ(j)−1,j,t ≤Myk,t−1,∀j ∈ W, k ∈ I¯→, h ∈ H, t ∈ T , γ(k) ≤ δ(j)− 1, δ(j) + 1 ≤ n, (2.29)fw,hδ(j)+1,j,t ≤Myk,t−1,∀j ∈ W, k ∈ I¯→, h ∈ H, t ∈ T , γ(k) ≤ δ(j)− 1, δ(j) + 1 ≤ n. (2.30)In the same way, before the first block with no access road, the transit,borrow, and waste flows are not allowed until the block is removed:f r,hi,i+1,t ≤Myk,t−1, ∀i ∈ S, k ∈ I¯←, h ∈ H, t ∈ T , 1 ≤ i, i+ 1 ≤ γ(k),(2.31)172.2. Multi-haul quasi network flow modelf r,hi+1,i,t ≤Myk,t−1, ∀i ∈ S, k ∈ I¯←, h ∈ H, t ∈ T , 1 ≤ i, i+ 1 ≤ γ(k),(2.32)f b,hj,ϑ(j)+1,t ≤Myk,t−1,∀j ∈ B, k ∈ I¯←, h ∈ H, t ∈ T , 1 ≤ ϑ(j)− 1, ϑ(j) + 1 ≤ γ(k), (2.33)f b,hj,ϑ(j)−1,t ≤Myk,t−1,∀j ∈ B, k ∈ I¯←, h ∈ H, t ∈ T , 1 ≤ ϑ(j)− 1, ϑ(j) + 1 ≤ γ(k), (2.34)fw,hδ(j)−1,j,t ≤Myk,t−1,∀j ∈ W, k ∈ I¯←, h ∈ H, t ∈ T , 1 ≤ δ(j)− 1, δ(j) + 1 ≤ γ(k), (2.35)fw,hδ(j)+1,j,t ≤Myk,t−1,∀j ∈ W, k ∈ I¯←, h ∈ H, t ∈ T , 1 ≤ δ(j)− 1, δ(j) + 1 ≤ γ(k). (2.36)After excavating/embanking the required amount of earth from/to asection with a block, we should consider that block as a removed blockwhich does not exist anymore. The block removal indicator constraints areused to satisfy this expectation as followsnb∑t=0(fu,hγ(k),γ(k)+1,t + fu,hγ(k),γ(k)−1,t) +M(1− yk,t) ≥ V +γ(k),∀k ∈ I, h ∈ H, t ∈ T , (2.37)nb∑t=0(f l,hγ(k)−1,γ(k),t + fl,hγ(k)+1,γ(k),t) +M(1− yk,t) ≥ V −γ(k),∀k ∈ I, h ∈ H, t ∈ T . (2.38)At the end of each time step t ∈ T , at least one block should be removedso that removing all the blocks does not take more than nb + 1 time steps.The block removal enforcement constraint guarantees this,u∑t=0∑k∈Iyk,t ≥ t+ 1 ∀t ∈ T \ {nb}. (2.39)182.2. Multi-haul quasi network flow modelIn addition, when a block is removed it should remain removed. This isdone by the monotonicity constraint as followsyk,t ≥ yk,t−1, ∀k ∈ I, t ∈ T \ {0}. (2.40)The continuity constraints,Pg−1(sϕ(g,1)) = Pg(sϕ(g,1)) ∀g ∈ G \ {1}, (2.41)P ′g−1(sϕ(g,1)) = P′g(sϕ(g,1)) ∀g ∈ G \ {1}, (2.42)are used to ensure that the height and the slope of the first section of asegment is equal to the height and the slope of the last section of the previoussegment.The volume constraintsV +i − V −i = Aiui, (2.43)in which Ai is the area of section i, guarantee that the total excavated/embanked volume of material from/to a section equals the volume differencebetween the road profile and the ground profile for that section.There are restrictions on the grade of the road profile to satisfy safetyconsiderations. Slope constraintsGL ≤ P ′g(sϕ(g,1)) ≤ GU ∀g ∈ G \ {1}, (2.44)are used to constrain the spline segments within a closed interval [GL, GU ],in which GL and GU are the minimum and the maximum valid grades,respectively.Finally, We need bound constraints to restrict the domain of variables as0 ≤ V +i ≤M, ∀i ∈ S ∪ B, (2.45)0 ≤ V −i ≤M, ∀i ∈ S ∪W, (2.46)f r,hi,i+1,t ≥ 0, f r,hi,i−1,t ≥ 0 ∀i ∈ S, h ∈ H, t ∈ T , (2.47)f l,hi−1,i,t ≥ 0, f l,hi+1,i,t ≥ 0 ∀i ∈ S, h ∈ H, t ∈ T , (2.48)fu,hi,i+1,t ≥ 0, fu,hi,i−1,t ≥ 0 ∀i ∈ S, h ∈ H, t ∈ T , (2.49)f b,hj,ϑ(j)+1,t ≥ 0, f b,hj,ϑ(j)−1,t ≥ 0 ∀j ∈ B, h ∈ H, t ∈ T , (2.50)fw,hδ(j)−1,j,t ≥ 0, fw,hδ(j)+1,j,t ≥ 0 ∀j ∈ W, h ∈ H, t ∈ T . (2.51)192.3. The CTG and QNF Models2.3 The CTG and QNF ModelsIn this section we describe two models that solve the vertical alignmentproblem for a known horizontal alignment. In the next chapter, we will usethese models to evaluate the performance of MH-QNF model.The Complete Transportation Graph model (henceforth CTG model) isa mixed integer linear programming model which was first developed byHare et al. in [HLR15]. This model is based on the spline technique pro-posed by Moreb [Mor09] in which the road profile is modeled using piecewisepolynomials and the vertical alignment problem is solved as a single linearprogram. The CTG model was improved in [HHLR14] by adding somespeedup techniques to improve the computational time.We use the CTG model as a benchmark model in our experiments. Wedo not refer to the details of this model in our research. Full details of theCTG model, which appear in [HHLR14, HLR15], are technical. Therefore, inthis discussion, we aim to provide only a broad stroke overview. In essence,instead of hauling paths, for every pair of nodes (i, j), the CTG model placesan arc moving from i to j. The flow through the arc is a continuous variableand the arc cost is computed based on i and j. Figure 2.5 demonstrates anexample of CTG model., ,, , ,i j tx i j S t T∈ ∈Sec. 1 Sec. 2 Sec. 3Sec. 1 Sec. 2 Sec. 3Figure 2.5: CTG model for a three-sections-long road.A complete transportation graph for a road with n sections, is a graphthat includes n source nodes, n destination nodes, and an edge between eachpair of source/destination nodes. The CTG model allocates a variable foreach edge so the required number of material movement variables is O(n2s) in202.3. The CTG and QNF Modelswhich ns is the number of sections. This model was extended in [HHLR14]by adding blocks and side slopes to the mixed integer linear programmingmodel proposed by Hare et al. [HLR15].For ease of explanation, we introduce variables for material movementwithout considering blocks, which can be introduced via time steps, similarto their use in MH-QNF. The full description of the model can be found in[HHLR14, HLR15]. To track material movement, we use the variable xij ,which shows the amount of material moved from section i to section j. Foreach i ∈ N , we use the index set N i→ which contains all indices j so that xijis a valid move:N i→ =j :j ∈ S ∪W if i ∈ Sj ∈ S if i ∈ B∅ if i ∈ W(2.52)Similarly, for each i ∈ N , we use the index set N i← which contains allindices j so that xij is a valid move:N i← =j :j ∈ S ∪W if i ∈ S∅ if i ∈ Bj ∈ S if i ∈ W(2.53)Note that for any i, j ∈ N , j ∈ N i→ if and only if i ∈ N j←. Finally, N 2consists of all index pairs (i, j) such that xij is a valid move:N 2 = {(i, j) : j ∈ N i→}. (2.54)Note that N 2 6= N ×N , as N 2 omits index pairs (i, j) that correspond toillogical moves, such as movement from a road section into a borrow pit.Similar to the other two models, the cost of vertical alignment dependson the embankment, excavation and hauling of materials from section tosection. Let pi represents the excavation cost per unit of volume and qirepresents the embankment cost per unit of volume for section i ∈ N . Letrij be the hauling cost per unit of volume from section i to section j.The objective function of the CTG model is to minimize the total ex-cavation, embankment, and hauling costs when moving materials betweensections, borrow pits, and waste pits over all time steps. The objectivefunction can be represented as follows:212.3. The CTG and QNF Modelsmin( ∑i∈S∪BpiV+i +∑i∈S∪WqiV−i +∑(i,j)∈N 2t∈Trijxijt), (2.55)where V +i (for i ∈ S ∪ B), and V −i (for i ∈ S ∪W) represent the total cutand fill volumes of material respectively.The constraints are similar to the constraints explained for MH-QNFmodel, which are adapted based on CTG model idea.The Quasi Network Flow model (henceforth QNF model) is studiedin [HHLR14]. It reduces the number of variable in the CTG model fromquadratic to linear, but at the cost of a more restrictive objective function.The QNF model is quite easy to describe at this stage – the QNF model is aspecial case of the MH-QNF model, where the number of haul types is one:nh = 1. Figure 2.6 illustrates a sample QNF model.Sec. 1 Sec. 2 Sec. 3Load & Unload flowsLeft transit flowRight transit flowFigure 2.6: QNF model for a three-sections-long road.For comparison, in Figure 2.7, the MH-QNF version of the road shownin Figures 2.5 and 2.6 is presented, where multiple hauling paths are em-ployed to move materials. This figure seems more reasonable for longer roadswhere we can differentiate short, middle, and long distances. The examplespresented here are only to show differences between three types of modelsintroduced earlier.222.3. The CTG and QNF ModelsShort haul Middle haul Long haul Sec. 1 Sec. 2 Sec. 3Figure 2.7: MH-QNF model for a three-sections-long road.23Chapter 3Numerical resultsIn this chapter, we present our experimental data and discuss the modelperformance on real-world problems. To evaluate the performance of theMH-QNF model, we compare the efficiency, robustness and accuracy of theproposed model with both CTG and QNF models in terms of timing andoptimal cost. The efficiency refers to the computational effort required toobtain a solution. We compare the efficiency of models using solving time.Robustness of an optimization method is defined as the ability of the methodto perform well over a wide range of problems. We compare the robustnessof the models using the success rate measure as will be discussed later.Finally, the accuracy is the quality of the solution obtained by solving amodel. We evaluate the accuracy by comparing the relative errors in costvalues obtained by all the models.3.1 Experimental setupIn a fair comparison of optimization methods, the first step is to as-semble or choose a proper problem test set [Bei15]. The selected problemtest collection consists of 60 problems. These problems are generated bychanging various parameters (i.e., number of sections, blocks, access roads,offset levels and section lengths) in 7 distinct road samples, provided byour industrial partner (see Table 3.1). All tests represent realistic road de-sign problems. In the test collection, the section length and the number ofsections in a road remain unchanged in all the problems.We consider 5 hours timeout for to solve each individual test problem.Because of limitations on the computational power, 5 hours was the highestcomputational time we could spend on solving each problem to finish allthe experiments in a reasonable time. If a test cannot be solved within thistime limitation, then it is reported as unsuccessful. Linear programmingfeasibility tolerance and relative mixed integer programming gap toleranceparameters are set to 10−06 and 1%, respectively. The upper bound andlower bound for slope constraints are 0.1 and -0.1. We use the defaultsettings for the other parameters for solver and models.243.1. Experimental setupTable 3.1: Basic roads used to assemble the test collection.Road Length (km) Section Length (m) Number of sectionsA 1 20 50B 5 100 50C 2 20 100D 3 20 150E 15 100 150F 20 100 200G 9 20 450After selection of the test collection, we solved the problems by differentmodels using the same computational environment. The workstation usedfor experiments has an Intel(R)Xeon(R) CPU W3565 3.20GHz (4 cores and8 threads) processor and 24.0 GB of RAM. To solve the developed math-ematical models we use the academic version of the IBM ILOG CPLEXoptimizer 12.51 edition http://www.cplex.com.Table 3.2: Cost components in $/cu.m.Cost component Cost Type Value Avg ValueExcavation cost M1 4.000M2 4.000M3 20.000M4 4.000Embankment cost M1 2.000M2 2.000M3 1.800M4 2.000Loading cost Short 0.000 1.067Middle 0.600Long 2.600Hauling cost Short 0.008 0.005Middle 0.004Long 0.002One of the influencing factors on our experiments is the cost compo-nents used in the MH-QNF model. Table 3.2 shows the cost components253.1. Experimental setupinvolved in a vertical alignment problem and the associated values selectedin consultation with our industry partner. Excavation and embankmentcost components depend on the different types of materials. Loading andhauling cost components depend on the type of hauling path. The AvgValue column is the average of the cost values for a cost component. Allthe three models are adapted and parametrized using the same cost com-ponents. Both MH-QNF model and the CTG model use multiple haulingpaths with different hauling and loading costs. Therefore, in the case of theQNF model which has a single hauling path, for the loading and haulingcost components we need to test the model with different pairs of haulingand loading cost components.Since the MH-QNF model is an extension of the QNF model, to get abetter understanding of the importance of loading and hauling cost compo-nents, in addition to the average values of loading and hauling costs (1.067,0.005, respectively), we test the QNF model with the other three pairs ofcost values for loading and hauling cost components reported for differenthauls (Table 3.2); i.e., we run the QNF model four times with different load-ing and hauling costs: average case (1.067, 0.005), short haul (0.000, 0.008),middle haul (0.600, 0.004), and long haul (2.600, 0.002). Thus, we have 4different setups for QNF model as follows.− QNF-S: the model QNF configured with short hauling and loadingcost values.− QNF-M: the model QNF configured with middle hauling and loadingcost values.− QNF-L: the model QNF configured with long hauling and loadingcost values.− QNF-A: the model QNF configured with average hauling and loadingcost values.As shown in Figure 3.1, to evaluate the efficiency of using a variety ofhauling paths over a single path in a road construction site, the loading andhauling cost components are selected such that− if hauling distance < 150m then short hauling path will be pickedas the optimum method of transferring material;− if 150m ≤ hauling distance < 1000m then middle hauling path willbe picked;263.1. Experimental setup− and finally, if hauling distance ≥ 1000m then the long hauling pathwill be selected.024681012141618201 251 501 751 1001 1251 1501Cost ($/cu.m.) Hauling distance (m) Short HaulMiddle HaulLong HaulLong HaulMiddle HaulShortHaulFigure 3.1: Cost configuration.In [HHLR14] the authors proposed six potential techniques to improvethe speed of solution search. They extensively tested all the techniques withtwo models and identified the setup which works the best for both mod-els. Their results highlighted two techniques as the most efficient methods.Therefore, we test all models using two different configurations. In the firstconfiguration, we use SOS2 variables for the volume constraints and SOS1variables for modeling the block constraints in all the models. In the secondconfiguration, again we use SOS2 variables for the volume constraints butfor the block constraints the basic technique is employed.In general, in our experiments we use 12 model configurations. To in-crease the readability of the report on the results we use the following namingconvention.1. Models that use the basic technique for blocks:− MH-QNF-B: The MH-QNF model.− CTG-B: The CTG model with multi haul cost components.− QNF-SB: The QNF-S model.− QNF-MB: The QNF-M model.− QNF-LB: The QNF-L model.− QNF-AB: The QNF-A model.2. Models that use the SOS1 techniques for blocks:273.2. Reporting the results− MH-QNF-S: The MH-QNF model.− CTG-S: The CTG model with multi haul cost components.− QNF-SS: The QNF-S model.− QNF-MS: The QNF-M model.− QNF-LS: The QNF-L model.− QNF-AS: The QNF-A model.3.2 Reporting the resultsAs a first pass at examining model accuracy, we summarize the relativeerrors in cost values obtained by all models in Table 3.3. The column “opt.found” is the number of problems where the model optimum value wasfound before timeout occurred (regardless of relative error). The columns“min./mean/max. error” are the minimum/mean/maximum relative errorover all problems solved when compared to CTG configurations (CTG-B orCTG-S), based on only problems solved by both CTG configuration and themodel examined.Table 3.3: Summary of model accuracy for each model.# Model opt. found min. error (%) mean error (%) max. error (%)1 CTG-B 51 – – –2 MH-QNF-B 56 0.00 0.47 2.203 QNF-SB 56 27.15 57.10 100.924 QNF-MB 56 12.33 25.65 40.745 QNF-LB 56 18.93 25.81 37.956 QNF-AB 56 22.19 40.22 62.987 CTG-S 45 – – –8 MH-QNF-S 57 0.00 0.37 1.439 QNF-SS 56 27.15 57.56 100.9210 QNF-MS 56 12.45 25.78 40.7411 QNF-LS 56 18.93 25.81 37.3912 QNF-AS 56 22.36 40.44 62.98As we expected, among the above 12 model configurations, none of theQNF model configurations are able to solve a single problem satisfactorily.The reason is that the QNF model considers a linear relation between the283.2. Reporting the resultshauling (and loading) cost and the hauling distance. In other words, QNFassumes that only one type of machinery is used to transfer materials in theconstruction site, regardless of the hauling distance. We therefore discardthese methods as they are inaccurate.Table 3.4 shows the solution times for the remaining 4 configurationsapplied to 60 test problems when only 1% relative error is allowed. “NaN”values indicate that the solver exceeded the 5 hours timeout.The reliability and robustness of an optimization method is defined asthe ability of the method to perform well over a wide range of optimizationproblems. To evaluate the reliability of the model we use two measures:success rate and computational accuracy. The success rate is defined as thenumber of problems in the given problem set that are successfully solved tooptimality by the optimization method. We use performance profiles [DM02]to evaluate the reliability and robustness of the models. While performanceprofiles are now prevalent in optimization benchmarking, we provide a briefreview for completeness. The performance profile of a solver s is defined asfollowsρs(α) =1|P|size{p ∈ P : rp,s ≤ α}, (3.1)where |P| represents the cardinality of the problem set P and rp,s is theperformance ratio defined asrp,s ={tp,smin{tp,s:s∈S} if the convergence test passed∞ if the convergence test failed (3.2)in which tp,s is the performance measure which is the computational timein our case. In this equation, for a specific problem and the best solver interms of tp,s we will have rp,s = 1.One of the advantages of performance profiles, is that they implicitlyincludes the performance ratio success rate as a reliability factor. The valueof ρs(α) gives a sense of how promising the solutions found by an optimiza-tion algorithm are relative to the best solution found by all the optimizationalgorithms that are compared together.293.2. Reporting the resultsTable3.4:Solutiontimes(insecond)for1%relativeerror.Test#MH-QNF-BCTG-BMH-QNF-SCTG-STest#MH-QNF-BCTG-BMH-QNF-SCTG-S123.8419.0215.2133.71319.89179.339.8335.04211.0027.1815.2835.413218.15619.5078.73241.43326.51190.6420.51237.693311.031361.1625.27675.144168.627214.67172.484848.313430.082385.4391.46NaN542.07434.3952.39452.033522.712463.6435.742543.56613.05232.8428.261014.8036120.08NaN273.139350.417874.97603.49581.461928.963757.231702.7490.71NaN8NaN12605.202409.50NaN383.124.964.954.98919.93169.5178.17309.463917.09230.5036.15623.731013.40297.7517.13141.414018020.00NaNNaNNaN1166.342348.9360.28NaN413361.52NaN9224.50NaN12146.363929.18124.019853.7442392.59NaN455.71NaN134.9686.7011.3833.6343308.46NaN313.39NaN142.1539.364.9717.2444NaNNaNNaNNaN1518.75392.6735.29451.634570.472014.47168.04NaN16319.90NaN366.57NaN4650.751289.76122.843528.951713.8181.6123.76174.21478.857.4417.437.7818238.371369.81383.954559.33485.709.0210.619.761930.17799.5568.351657.61493.221.876.721.892081.99632.691175.494146.94501.360.942.460.9921455.83NaN2743.00NaN514.836.117.726.1422223.278901.201426.83NaN528.9728.7414.4228.872365.001306.09553.652437.765314.3740.8923.7641.09243.6591.197.8755.345413.5827.0221.9027.86259.64750.8625.49314.505513.6830.4423.0131.262676.045486.19158.04NaN563.784.746.344.68276.87353.5014.6457.915773.501373.6894.701361.67286.16493.6014.19248.4358NaNNaNNaNNaN295.5267.069.2019.165915.24122.7515.90128.763030.442454.9351.142432.61606.9914.098.5816.29303.2. Reporting the resultsFor each solution obtained for problem s using the model m the percentrelative error is calculated using the following formula:Es,m =Objs −ObjbObjb, (3.3)in which Objs is the optimal objective value obtained for the problem s bythe model m and Objb is the objective value obtained by the benchmarkmodel b. In our experiments, a solution found by model m is consideredsuccessful if |Es,m| ≤ 1.0%.When available, we consider the CTG model as the benchmark and wecalculate the relative error for the solutions obtained using the MH-QNFmodel. When the CTG model does not provide a solution but the MH-QNF does, we consider the MH-QNF relative error to be 0.0%. This is donesince only 5 problems out of 60 have such condition (solved by MH-QNFbut not CTG). Adding or removing these 5 problems does not change thefinal conclusions of the experiments. Moreover, as discussed previously, theaccuracy of MH-QNF model is pretty close to CTG in all the problems solvedby both models. Therefore, we decided to trust MH-QNF model in the caseof these 5 test problems. Figure 3.2 provides the resulting performanceprofile.313.2. Reporting the results0 1 2 3 4 5 6 700.10.20.30.40.50.60.70.80.91log2(τ)ρ s( l og 2( τ )) MH-QNF-BCTG-BMH-QNF-SCTG-SFigure 3.2: Performance profiles with up to 1% relative error.Examining Figure 3.2, it is clear that MH-QNF greatly outperformsCTG. In terms of the block technique, the CTG model has a relatively betterperformance when it uses the basic technique for blocks by solving almost82% of the problems compared to the SOS1 version (CTG-S) which endsup with solving 75%. Similarly, in the case of MH-QNF model, the modelusing the basic technique (MH-QNF-B) is considerably faster than whenit uses the SOS1 technique (MH-QNF-S). Except on one test, MH-QNF-Bsolves most of the problems faster than MH-QNF-S. In general, among allthe configurations, MH-QNF-B is the winner and has a better performancethan the CTG configurations.32Chapter 4ConclusionsIn this research, we extended a model based on a previous quasi networkflow model by Hare et al. [HHLR14] for the vertical alignment problemconsidering the earthwork cost. In particular, we added multiple haulingflows to the model in order to improve the accuracy of the model and providemore modeling flexibility for the users. The model considers features suchas blocks and side-slopes. We compared the model with two state-of-the-artmodels in the field: CTG and QNF models.The CTG model allows a great deal of flexibility in arc-costs, but the re-sulting number of variables is very large. The total number of variables growsquadratically with the number of sections: O((ns)2nhnm), where ns, nh andnm are the number of sections, hauling paths, and material types, respec-tively [HHLR14]. As the number of sections is typically the dominatingfactor in these models, the CTG model is typically much larger than theQNF and MH-QNF models.In particular, in the MH-QNF model (and hence the QNF model) thetotal number of variables grows linearly with the number of sections: O(ns)[HLR15]. The number of variables in MH-QNF model is O(nh ∗ ns), whichis still linear in ns. (Note that nh is typically 3, so have little impact onproblem size.) However, in QNF model there is a linear relation betweenthe hauling cost and the distance traveled by the volume of materials (e.g.,the cost of moving 1 unit of earth for 100m equals to 100 times the costof moving 1 unit for 1m), which is not true in real world. Therefore, weproposed the MH-QNF model to integrate the low computational cost ofQNF model with the accuracy of CTG in solving the vertical alignmentproblem. The experimental results confirm that the new model is bothhighly accurate and considerably faster than the CTG model.334.1. Future research4.1 Future research4.1.1 Three dimensional road design optimizationIn three dimensional alignment optimization, the vertical and horizontalalignments are optimized, simultaneously. The horizontal alignment opti-mization problem is related to the vertical alignment optimization problem.Often, three dimensional optimization involves repeatedly solving the ver-tical alignment problem. As discussed in previous chapters, the proposedmodel in this thesis (i.e., MH-QNF model) accurately solves the verticalalignment optimization problem and is computationally cheaper than CTGmodel. Therefore, as a future work MH-QNF model can be used in threedimensional optimization process to get a precise final solution.4.1.2 Model uncertaintyIn the proposed model there are some parameter values (such as thelength of segments, the number of sections in a segment, and the number ofblocks in a road) that we have not studied with respect to their importancein the final solution provided by the model. These parameters are subject tochange and error. As a future work we can use model uncertainty, to investi-gate these potential changes and errors and their impacts on the conclusionsto be drawn from the model.4.1.3 Human-based experimentThe models developed for road design optimization problems are prac-tically used by civil engineers. The sophisticated nature of road designproblem imposes a lot of constraints that need to be dealt with in order toprovide a practical solution to engineers who use the model. In this regard,for the sake of providing a quality solution, it is required to design new ex-periments in order to reveal potential unknown constraints in the real-worldroad design problem which is not handled by the model proposed in thisresearch. As a future experiment it is suggested to design a test and solvethe test set by both automated optimization tool and an experienced engi-neer. Then we can evaluate the results obtained in both cases, which mightprovide more insight on the strength and quality of the developed model.34Bibliography[AAS11] AASHTO, editor. A Policy on Geometric Design of Highwaysand Streets. American Association of State Highway and Trans-portation Officials (AASHTO), 6th edition, 2011. → pages 2[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 3[Bei15] V. Beiranvand. A survey on benchmarking of optimizationalgorithms. Technical report, University of British Columbia,2015. → pages 24[CCGC15] C. Celauro, F. Corriere, M. Guerrieri, and B. L. Casto. En-vironmentally appraising different pavement and constructionscenarios: A comparative analysis for a typical local road.Transportation Research Part D: Transport and Environment,34(0):41 – 51, 2015. → pages 1[CGF89] E. P. Chew, C. J. Goh, and T. F. Fwa. Simultaneous opti-mization of horizontal and vertical alignments for highways.Transportation Research Part B: Methodological, 23(5):315 –329, 1989. → pages 1[CL06] J. Cheng and Y. Lee. Model for three-dimensional high-way alignment. Journal of Transportation Engineering,132(12):913–920, 2006. → pages 1[DM02] E. D. Dolan and J. J. More´. Benchmarking optimization soft-ware with performance profiles. Mathematical Programming,91:201–213, 2002. → pages 29[Eas88] S. M. Easa. Selection of roadway grades that minimize earth-work cost using linear programming. Transportation ResearchPart A: General, 22(2):121 – 136, 1988. → pages 435Bibliography[ESHS02] S. M. Easa, T. R. Strauss, Y. Hassan, and R. R. Souleyrette.Three-dimensional transportation analysis: Planning and de-sign. Journal of Transportation Engineering, 128(3):250–258,2002. → pages 1[Fwa06] T. F. Fwa. The Handbook of Highway Engineering. CRC Press,1st edition, 2006. → pages 2[GCF88] C. J. Goh, E. P. Chew, and T. F. Fwa. Discrete and continuousmodels for computation of optimal vertical highway alignment.Transportation Research Part B: Methodological, 22(6):399 –409, 1988. → pages 3[GLA09] A. B. Goktepe, A. H. Lav, and S. Altun. Method for opti-mal vertical alignment of highways. Proceedings of the ICE -Transport, 162(4):177–188, 2009. → pages 3[HEAEH98] Y. Hassan, S. Easa, and A. Abd El Halim. Highway align-ment: Three-dimensional problem and three-dimensional solu-tion. Transportation Research Record: Journal of the Trans-portation Research Board, 1612(1):17–25, 1998. → pages 1[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 2, 4, 5, 7, 8, 20, 21, 22, 27, 33[HKL11] W. L. Hare, V. R. Koch, and Y. Lucet. Models and algorithmsto improve earthwork operations in road design using mixedinteger linear programming. European Journal of OperationalResearch, 215(2):470 – 480, 2011. → pages 1, 4, 7[HL07] A. Herranz-Lonca´n. Infrastructure investment and spanish eco-nomic growth, 1850-1935. Explorations in Economic History,44(3):452 – 468, 2007. → pages 1[HLR15] W. Hare, Y. Lucet, and F. Rahman. A mixed-integer linearprogramming model to optimize the vertical alignment consid-ering blocks and side-slopes in road construction. EuropeanJournal of Operational Research, 241(3):631 – 641, 2015. →pages 4, 20, 21, 3336Bibliography[Jon98] J. C. Jong. Optimizing highway alignments with genetic al-gorithms. PhD thesis, University of Maryland College Park,United States - Maryland, 1998. → pages 4[JS03] J. C. Jong and P. Schonfeld. An evolutionary model for simul-taneously optimizing three-dimensional highway alignments.Transportation Research Part B: Methodological, 37(2):107 –128, 2003. → pages 3[JSJK06] M.K. Jha, P. Schonfeld, J.-C Jong, and E. Kim. Intelligentroad design, volume 19. WIT Press, 2006. → pages 3[KJS05] E. Kim, M. K. Jha, and B. Son. Improving the computationalefficiency of highway alignment optimization models through astepwise genetic algorithms approach. Transportation ResearchPart B: Methodological, 39(4):339 – 360, 2005. → pages 3[KJS12] M. W. Kang, M. K. Jha, and P. Schonfeld. Applicability ofhighway alignment optimization models. Transportation Re-search Part C: Emerging Technologies, 21(1):257 – 286, 2012.→ pages 3[KL10] V. R. Koch and Y. Lucet. A note on: Spline technique formodeling roadway profile to minimize earthwork cost. Journalof Industrial and Management Optimization, 6(2):393 – 400,2010. → pages 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 3[LPZL13] W. Li, H. Pu, H. Zhao, and W. Liu. Bidirectional DynamicProgramming Approach for Highway Alignment Optimization,volume 779-780 of Advanced Materials Research, chapter Chap-ter 2: Traffic and Transportation Engineering, Civil and Me-chanical Engineering, pages 700–704. 2013. → pages 4[MA04] A. A. Moreb and M. S. Aljohani. Quadratic representationfor roadway profile that minimizes earthwork cost. Journalof Systems Science and Systems Engineering, 13(2):245 – 252,2004. → pages 1, 437Bibliography[MLH15] S. Mondal, Y. Lucet, and W. Hare. Optimizing horizontalalignment of roads in a specified corridor. Computers & Oper-ations Research, 64:130 – 138, 2015. → pages 2, 5[Mor96] A. A. Moreb. Linear programming model for finding optimalroadway grades that minimize earthwork cost. European Jour-nal of Operational Research, 93(1):148 – 154, 1996. → pages4[Mor09] A. A. Moreb. Spline technique for modeling roadway profile tominimize earthwork cost. Journal of Industrial and Manage-ment Optimization, 5(2):275 – 283, 2009. → pages 4, 20[NEW75] A. J. Nicholson, D. G. Elms, and A. Williman. Optimal high-way route location. Computer-Aided Design, 7(4):255 – 261,1975. → pages 4[Tri87] D. Trietsch. Comprehensive design of highway networks. Trans-portation Science, 21(1):26–35, 1987. → pages 438
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Multi-haul quasi network flow model for vertical alignment...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Multi-haul quasi network flow model for vertical alignment optimization Beiranvand, Vahid 2016
pdf
Page Metadata
Item Metadata
Title | Multi-haul quasi network flow model for vertical alignment optimization |
Creator |
Beiranvand, Vahid |
Publisher | University of British Columbia |
Date Issued | 2016 |
Description | The vertical alignment optimization problem for road design aims to generate a vertical alignment of a new road with a minimum cost, while satisfying safety and design constraints. We present a new model called multi-haul quasi network flow (MH-QNF) for vertical alignment optimization that improves the accuracy and reliability of previous mixed integer linear programming models. We evaluate the performance of the new model compared to two state-of-the-art models in the field: the complete transportation graph (CTG) and quasi network flow (QNF) models. The numerical results show that, within 1% relative error, the proposed model is robust and solves more than 93% of test problems. Whereas, the CTG only solves about 82% of test problems and QNF fails to solve any problem within 1% relative error. Moreover, in terms of computational time, on average the MH-QNF model solves the problems approximately 8 times faster than the CTG model. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2016-07-15 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0228128 |
URI | http://hdl.handle.net/2429/56673 |
Degree |
Master of Science - MSc |
Program |
Interdisciplinary Studies |
Affiliation |
Graduate Studies, College of (Okanagan) |
Degree Grantor | University of British Columbia |
GraduationDate | 2016-02 |
Campus |
UBCO |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2016_february_Beiranvand_Vahid.pdf [ 498.28kB ]
- Metadata
- JSON: 24-1.0228128.json
- JSON-LD: 24-1.0228128-ld.json
- RDF/XML (Pretty): 24-1.0228128-rdf.xml
- RDF/JSON: 24-1.0228128-rdf.json
- Turtle: 24-1.0228128-turtle.txt
- N-Triples: 24-1.0228128-rdf-ntriples.txt
- Original Record: 24-1.0228128-source.json
- Full Text
- 24-1.0228128-fulltext.txt
- Citation
- 24-1.0228128.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0228128/manifest