Models and strategies for efficiently optimizing the vertical alignment of roads for multimaterial by Shahadat Hossain B.Sc., Bangladesh University of Engineering and Technology, 2009 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE COLLEGE OF GRADUATE STUDIES (Interdisciplinary Studies - Optimization) THE UNIVERSITY OF BRITISH COLUMBIA (Okanagan) July 2013 c Shahadat Hossain, 2013 Abstract Selecting optimal vertical alignment while satisfying safety and design constraints is an important task during road construction. The amount of earthwork operations depends on the design of a vertical alignment, so a good vertical alignment can have a profound impact on construction costs. In “Optimizing the vertical alignment under earthwork block removal constraints in road construction” M.Sc. thesis 2012, F. Rahman proposed two models for vertical alignment optimization. However, the models were limited to a single material and the volume of material needed to be a convex function of the distance from the ground profile. Consequently, these models cannot be used in commercial road design softwares. In this research, we remove the previous limitations so the models can now be used for road design software. Both models use a piecewise quadratic curve to minimize the cost for earthwork operations. The models consider several new features as well as all the features of the previous models that are described in previous research by F. Rahman. Moreover, we improve the solution time, so that it is possible to make interactive design tools. We provide numerical tests that validate our results. ii Preface Models and strategies for efficiently optimizing the vertical alignment of roads for single material part of this thesis has been adapted from a manuscript co-authored with Dr. Warren Hare, Dr. Yves Lucet, and Faisal Rahman at the University of British Columbia, Okanagan campus. The manuscript has been submitted for publication to the Journal of Computers and Operations Research [HHLR13]. The paper included models and techniques for single material only. A US provisional patent was also filed based on the results contained in the present thesis. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . ix Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x Chapter 1: Introduction . . . . . 1.1 Motivation . . . . . . . . . 1.2 Road design problem . . . . 1.2.1 Horizontal alignment 1.2.2 Vertical alignment . 1.2.3 3D alignment . . . . 1.3 Our research focus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 2 4 6 7 Chapter 2: The quadratic model for vertical alignment 2.1 Model variables and parameters . . . . . . . . . . . . . 2.2 The quadratic model . . . . . . . . . . . . . . . . . . . 2.2.1 The quadratic model for single material . . . . 2.2.2 The quadratic model for multimaterial . . . . . . . . . . . . . . . . . . . . . . . . . 10 10 16 16 16 Chapter 3: Quasi network flow model for vertical alignment . 23 3.1 Quasi network flow for single material . . . . . . . . . . . . . 23 3.2 Quasi network flow for multimaterial . . . . . . . . . . . . . . 23 iv TABLE OF CONTENTS Chapter 4: Speedup techniques . . . . . . . . . . . . . . . . 4.1 Techniques with offset levels . . . . . . . . . . . . . . . . . 4.1.1 Reducing binary variables for offset levels . . . . . 4.1.2 Modeling volume constraints with SOS2 variables . 4.2 Techniques with blocks . . . . . . . . . . . . . . . . . . . . 4.2.1 Block constraints with SOS1 variables . . . . . . . 4.2.2 Reducing the number of binary variables for blocks . . . . . . . . . . . . . . 31 31 31 33 34 34 35 Chapter 5: Numerical results . . . . . . . . . . . . . . . . . 5.1 Experimental setup . . . . . . . . . . . . . . . . . . . . . . 5.2 Performance measurement . . . . . . . . . . . . . . . . . . 5.3 Experimental results for single material . . . . . . . . . . 5.3.1 Results for problems with blocks . . . . . . . . . . 5.3.2 Results for problems with no blocks . . . . . . . . 5.3.3 Summary of experimental result for single material 5.4 Experimental results for multimaterial . . . . . . . . . . . 5.4.1 Results for problems with blocks . . . . . . . . . . 5.4.2 Results for problems without blocks . . . . . . . . 5.4.3 Summary of results for mutlimaterial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 40 42 42 43 47 47 51 51 52 54 Chapter 6: Conclusion . . . . . . . . . . . . . . . . . . . . 6.1 Future research . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Improvement in the quasi network flow model . 6.1.2 More options for selecting material . . . . . . . 6.1.3 Horizontal alignment . . . . . . . . . . . . . . . . . . . . . . . . . 55 55 55 56 56 . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Appendix A: Tables . . . . . . . . . . . . . . . . . . . . . . . . . . 63 v List of Tables Table 2.1 Cut and fill volume of material . . . . . . . . . . . . . 14 Table Table Table Table Table List of strategies for single material with blocks . . . . List of strategies for single material without blocks . . Precedence of techniques for CPLEX . . . . . . . . . . Precedence of techniques for CBC . . . . . . . . . . . . List of strategies without blocks for multimaterial test cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . List of strategies with blocks for multimaterial test cases 41 47 50 50 5.1 5.2 5.3 5.4 5.5 Table 5.6 Table A.1 Table Table Table Table Table Table Table Table Table Solution time by CPLEX for single material without blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Solution time by CBC for single material without blocks A.3 Solution time by CPLEX for single material with blocks A.4 Solution time by CBC for single material with blocks . A.5 Solution time by CPLEX for multimaterial with blocks A.6 Solution time by CPLEX for multimaterial without blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . A.7 Test road configuration . . . . . . . . . . . . . . . . . . A.8 Test configurations in terms of number . . . . . . . . . A.9 Test configuration: (pattern of blocks, access roads) . A.10 Sample input table (for multi-material) . . . . . . . . . 51 53 63 64 65 66 67 68 69 70 72 73 vi List of Figures Figure 1.1 Figure 1.2 Horizontal alignment . . . . . . . . . . . . . . . . . . Vertical alignment . . . . . . . . . . . . . . . . . . . . Figure Figure Figure Figure Figure Figure Figure Figure Side view of ground profile and road profile Spline segment of vertical alignment. . . . Cross-section of a road for a cut . . . . . . Cross-section of a road for a fill . . . . . . Approximation of side-slopes for a cut . . . Approximation of side-slopes for a fill . . . Volume approximation of side-slope . . . . Stockpiling scenario during cut and fill . . 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Figure 3.1 Figure 3.2 Figure 5.1 Figure 5.2 Figure 5.3 Figure 5.4 Figure 5.5 Figure 5.6 Figure 5.7 Figure 5.8 Figure 5.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5 . . . . . . . . 10 12 13 13 13 14 15 20 A typical section in quasi network flow model . . . . A typical section in quasi network flow model with blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Performance profile for solver CPLEX (with blocks) . Performance profile for solver CBC (with blocks) . . . Performance profile of quadratic model for CPLEX (with blocks) . . . . . . . . . . . . . . . . . . . . . . . Performance profile of quadratic model for CBC (with blocks) . . . . . . . . . . . . . . . . . . . . . . . . . . Performance profile of quasi network flow model for CPLEX (with blocks) . . . . . . . . . . . . . . . . . . Performance profile of quasi network flow model for CBC (with blocks) . . . . . . . . . . . . . . . . . . . . Performance profile for solver CPLEX (without blocks) Performance profile for solver CBC (without blocks) . Performance profile for solver CPLEX for multi-material (with blocks) . . . . . . . . . . . . . . . . . . . . . . . 25 43 44 45 45 46 46 48 48 52 vii LIST OF FIGURES Figure 5.10 Performance profile for solver CPLEX for multi-material (without blocks) . . . . . . . . . . . . . . . . . . . . . 53 viii Acknowledgements I would like to express my sincere gratitude to my two supervisors, Dr. Yves Lucet and Dr. Warren Hare, for their continuous help and support in all stages of this research. I would like to thank them for being open and encouraging to new ideas, listening to my ideas, and helping me to organize those in proper way. Their knowledge, guidance, and patience were essential for this thesis. It was a great privilege to have such friendly supervisors that helped me to overcome many challenges and enjoy my graduate life. A very special thanks goes to our industrial partner (Softree Technical Systems Inc.) for providing us all the help that we need. In particular David Mills, Craig Speirs, and Alexis Guigue were always very supportive and helpful to give technical information for this thesis. The week that I worked with them in Vancouver helped me a lot to organize my thesis. I would like to thank everyone who directly or indirectly helped me in my research, course works, and in other activities during my graduate life. I owe my deepest gratitude to my parents, and family members for their prayers and support throughout my life. Without their selfless and continuous help I would not be able to come here. I also like to thank all of my friends who helped me to pass some good times in Kelowna, took me to camping, and gave me rides to several places. This research is partially funded by an Collaborative Research and Development (CRD) Grants from the Natural Sciences and Engineering Research Council (NSERC) of Canada, MITACS, and Softree Technical Systems Inc. ix Dedication To Rusdania Bushra Asha. x Chapter 1 Introduction In this chapter, we describe our motivation for research in road design, define the road design problem, and discuss some previous works in road design. 1.1 Motivation The state of the road network system is one of the strongest indicator of a country’s level of development. So every year all countries spend a significant amount of their budget on construction and maintenance of roads and highways. For example, the Canadian government in 2011 allocated $32,000,000,000 for roadway transportation [Min12a]. A significant amount of this budget is spent on building new roads and maintaining existing roads. The cost of constructing a road without considering the cost of engineering design or property acquisition, can be in the range of $2,100,000 to $5,000,000 per kilometer for two lanes [Min12b] . As a result, the government and the companies who build and maintain roads and highways are interested to find a way to minimize the cost of road construction and maintenance. While constructing roads and highways, cost minimization is not the only issue the road and highway engineers have to deal with. Every year thousands of road collisions and casualties happen. These accidents cost a lot, not only in terms of money but also in terms of life. So it is very important to consider safety requirements, rules, and regulations while designing roads to minimize accidents. Furthermore, road engineers also need to consider the environmental impacts [Jha03] and the socioeconomic effects [DJ09]. Designing roads or highways to minimize costs during the construction process while satisfying safety requirements, rules, and regulations considering all socioeconomic and environmental impacts is a very difficult task. Thus automating the road design process to the optimal design could save a lot of money. Unfortunately there is no road design software in existence today that has an automated and interactive way for computing optimal 1 1.2. Road design problem design of roads or highways considering multiple materials and all practical design issues. In this research we work to address these issues and take a step towards building a software tool for computing a mathematically proven optimal design of a road. 1.2 Road design problem Road design refers to the problem of connecting some given end points by selecting an economical alignment while satisfying various design specifications, safety constraints, and considering environmental and socioeconomic impacts [JS03], [JSJ06]. Minimizing the cost of road construction spans a wide range of road types: from highways to mountain roads. It is a sub-problem in forest management [CMW98], and in the design of efficient highway networks [ACRV13]. The problem of designing roads can be split into three interrelated subproblems [AAS04]. First, the horizontal alignment provides the road trajectory from a satellite’s eye view considering political and social issues [KSJ07]. Then, the vertical alignment is a modification of the ground profile that minimizes the cost of construction while satisfying safety and regulation constraints [Mor09]. Finally, a solution to the earthwork problem describes how material is rearranged optimally to build the desired vertical alignment at minimal cost [HKL11]. For computational efficiency, many researchers combine the last two stages together to design optimal vertical alignments while minimizing earthwork costs. Since two given points can be connected in numerous possible ways, selecting the best alignment quickly from many potential alignments is a difficult task. Manual processes of designing roads take hours of skilled labor and there is no guarantee on the optimality of the final design. In this research we propose models and strategies to calculate the vertical alignment (incorporating the earthwork problem) that can be solved by deterministic optimization algorithms. 1.2.1 Horizontal alignment A horizontal alignment is a route from source to destination; it follows a topographical map and satisfies various design code requirements [AAS04]. It should also consider several socioeconomic and political issues [KSJ07] , e.g., passing through specific town and staying away from hospitals and schools. The cost of designing a horizontal alignment depends on several 2 1.2. Road design problem factors such as land cost, travel cost, and on the vertical alignment cost discussed next. A sample horizontal alignment is shown in Figure 1.1. Horizontal alignment optimization is usually done using one of the three techniques: calculus of variation, dynamic programming, and network optimization. Figure 1.1: Horizontal alignment as visualized in RoadEng road design software. In calculus of variation, one tries to find a curve connecting two end points in space which minimizes the integral of a cost function ([JSJ06], [Wan95]). The horizontal alignment problem is similar to the typical problem in calculus of variation to some extent. This method is used to determine horizontal alignment in [SH81], [SH82], and [HBS68]. This methods needs to determine continuous local cost function. Since the cost depends on various factors, some approximation and assumptions are required to calculate 3 1.2. Road design problem the cost function. However, this method produces a continuous road, and a global optimum is guaranteed. Dynamic programming is a well known method for optimization. Mostly this technique is used for discrete problems. Few studies ([OEC73], [Tri87b], [JSJ06]) showed the optimization of a horizontal alignment using a dynamic programming method. The problem with this approach is that it takes a long time to solve large problems and the output alignment is non-smooth. Network optimization method formulate the horizontal alignment problem as a network problem such as a shortest path problem, a min cost flow problem, etc. Some early papers [TM70], [Tur78], [Tri87a] used network optimization methods to optimize a horizontal alignment. This method is simple and easy to understand, but formulating the cost function for each edge of the network considering the cost of vertical alignment is hard and requires significant approximations. 1.2.2 Vertical alignment After computing a horizontal alignment, one can draw a curve between the two given points and get the vertical ground profile along this curve ([HKL11]). An example of a vertical alignment is shown in Figure 1.2. In vertical alignment optimization, a road profile is fitted to the ground profile minimizing the cost of construction while satisfying safety and regulation constraints. It determines which hill to cut or ravine to fill to construct a road. The costs associated with the vertical alignment are the cut and fill costs of materials. Once a vertical alignment is determined, the earthwork optimization minimizes the cost of moving materials to build the desired vertical alignment. Vertical alignment optimization [Eas88], [GCF88], [Mor96], [LC01], [FCS02], [MA04], [GLA05], [GAA09], [GLA09], [Mor09], [KL10], [HKL11] of roads has been modeled by several researchers considering many constraints. As the earthwork cost depends on the design of the vertical alignment, it is common to combine the two stages together to design a vertical alignment while considering the earthwork. Nondeterministic methods to compute a vertical alignment were considered. Lee and Cheng [LC01] proposed a three layered heuristic method for vertical alignment optimization. They used several layers to convert a nonlinear mixed integer linear program to a mixed integer linear program. Their model was nonlinear at first because of the use of crest and sag curve equations to write the constraints on slopes limit. Fwa et al. [FCS02] and Goktepe et al. [GLA09] presented genetic algorithms formulation of the ver4 Height (meter) 1.2. Road design problem Road length (meter) Figure 1.2: Vertical alignment as visualized in RoadEng road design software. The solid line is the ground profile and the dotted line is the road profile. tical alignment problem. A detailed model solved with a genetic algorithm can be found in [JSJ06]. Several deterministic algorithms were proposed that take different constraints into account. Easa [Eas88] proposed a model for vertical alignment considering earthwork costs. It enumerates all possible combinations of feasible grades, and then for each grade it calculates the cut and fill using a linear program to minimize earthwork operations. It is a trial and error procedure. Goh et al. [GCF88] modeled the optimal vertical alignment using dynamic programming considering several costs such as cut, fill, pavement, and land acquisition costs. Moreb [Mor96] proposed a model combining vertical alignment and earthwork operation together in a single linear program. However, it gives a piecewise linear segments for the vertical alignment, which is not desirable. Moreb and Aljohani [MA04] improves the previous work of Moreb [Mor96] by representing the road profile as a quadratic spline. Goktepe et al. [GLA05] proposed a dynamic programming model to solve the vertical alignment problem and later in [GAA09] they extended the previous model by combining it with the Weighted Ground Line Method for cutfill balancing and earthwork minimization. Moreb ([Mor09]) also proposed an improved linear program that solved the problem of sharp connectivity of piecewise linear segments by adding more constraints. This model generalized the technique with a piecewise polynomial of any degree. Koch 5 1.2. Road design problem and Lucet ([KL10]) improved Moreb’s model ([Mor09]) by changing two constraints to avoid unnecessary errors. They also showed that up to a quadratic spline it is possible to maintain the linear structure of the model. But they did not consider side slopes and blocks into the model. Hare, Koch, and Lucet ([HKL11]) proposed a mixed integer linear programming model for earthwork optimization considering blocks. They were the first to introduce the block concept during earthwork optimization and determined an optimal schedule for material movement. A block is an obstacle such as mountains, rivers, etc. that needs to be dealt with before materials can be moved over the location of the block. In [HLR13], Hare, Lucet, and Rahman proposed a mixed integer linear programming model for vertical alignment considering side slopes and blocks. Side slopes refer to the gradual increase or decrease of the height from the road profile to the ground profile. When blocks are not considered, Ahuja et al. [AMO93, p. 12-13] gave a network flow model for earthwork optimization. Rahman [Rah12] proposed two models for vertical alignment while minimizing the earthwork cost. He extended the work of Moreb [Mor09], Koch and Lucet [KL10], and Hare et al. [HKL11]. The two models are called the quadratic model and the quasi network flow model. The quadratic model is a mixed integer linear program, and the quasi network flow model is a modification of a minimum cost network flow problem that turns it into another mixed integer linear program with significantly less variables. These two models are the most recent and constitute the state-of-the-art for solving vertical alignment problems using deterministic optimization algorithms. Sides slopes and blocks are considered in both models but only when a single material is considered, which is not realistic and prevents the model from being able to calculate a good approximation of the real construction cost. 1.2.3 3D alignment In the ideal case, designing a three dimensional alignment of roads by considering the above mentioned horizontal, vertical alignment, and earthwork sub problems together would be the most efficient strategy. However, calculating 3D alignment of a road, considering all of these simultaneously, is a very difficult problem. Most of the researchers use heuristic based algorithms to calculate 3D alignments. Chew et al. [CGF89] proposed a three dimensional highway alignment optimization model that determines the horizontal and vertical alignments simultaneously. They applied the concept of optimal control theory and used cubic spline polynomial interpolation to build a smooth vertical align6 1.3. Our research focus ment. The model is a general constrained non-linear optimization problem and cannot guarantee global optimality. Tat and Tao [TT03] developed a model for 3D alignment using genetic algorithms. It considers horizontal and vertical curvature, and gradient constraints simultaneously using GIS data. It also uses a cost model which depends on location, volume, length, etc. Akay [Aka06] proposed a method to design 3D alignments for forest roads using a combination of simulated annealing algorithm and linear programming. This model considers various soil types along the road and takes into account the safety of the drivers. But it manually selects an initial trial route. Cheng and Lee [CL06] proposed an iterative process splitting the whole process into three stages. In each iteration, a new horizontal alignment is obtained by slightly adjusting the current alignment. A corresponding vertical alignment is determined by solving a series of mixed integer linear program. Aruga [Aru05] uses a tabu search method using a high-resolution digital elevation model and later Aruga et al. [ATSM06] improved the model using Dijkstra’s shortest path algorithm and a cubic spline function. Models of the 3D alignment of highways are subject to nonlinear constraints. They have to deal with multiple design alternatives and various design parameters [GLA05]. As a result, most researchers first determine horizontal alignment and then compute a more precise vertical alignment. 1.3 Our research focus Our research is focused on vertical alignment optimization for road design. We have already discussed above some research works for solving the vertical alignment problem. Several research works emphasized different issues and tried to model them accordingly. We worked closely with our industry partner Softree Technical Systems Inc.1 who develops road design software. We have consulted with professional road engineers and learned what needs to be considered for a practical vertical alignment problem. The following requirements were found most relevant for modeling the vertical alignment problem: − Multi-material: A typical road consists of several materials. The cost of road construction depends on these various types of materials. So we need to build a model which can consider more than one material. 1 http://www.softree.com 7 1.3. Our research focus Multi-material can be defined by both different quality of the same material and different materials. − Side slopes: Side-slopes needs to be considered to obtain an acceptable material volume approximation. Side slopes refer to the gradual increase or decrease of the height from the road profile to the ground profile. Discarding them could introduces an unacceptable error in cost calculation. − Cut and fill at the same section: Cut and fill refers to the excavation and embankment of materials to make a smooth surface for the road construction. As the earth is uneven in shape, there could be cut and fill at the same section of the same material. Section refers to the smallest unit of a road, and there is no cost for moving materials within it. − Blocks: There could be blocks such as rivers, rocky mountains that needs to be considered, because it is not possible to move materials across or in between those blocks before we deal with them. Therefore to make a practical design of a vertical alignment, one has to take all of these constraints along with other common design code constraints [AAS04] into account. In addition, the challenge is to make an interactive software tool for designing optimal vertical alignment. So the model needs to give an accurate solution with acceptable computational time. Moreb’s model ([Mor09]) can be easily extended to accomodate multimaterials. But it does not consider side slopes and blocks. Hare et al. ([HKL11]) introduces blocks for earthwork optimization only. Rahman’s models ([Rah12]) incorporate blocks, side slopes. But it is only solvable for single material. It needs the input volume to be convex with respect to the height from the ground level. It also cannot consider cut and fill at the same section: it needs strictly either a cut or a fill at a given section. In our research, we have improved and combined the works done by Moreb ([Mor09]), Koch and Lucet ([KL10]), Hare et al. ([HKL11]) and Rahman ([Rah12]). We propose two models similar to Rahman’s models. Both models incorporates multimaterial, side slopes, cut and fill, and blocks. Our models can also consider convex, and nonconvex input volumes. It can handle cut and fill of the same material at the same section. So we fulfill all requirements for computing a practical vertical alignment. Moreover, we devised some techniques to reduce the solution time in order to work towards the target of developing an interactive design tool. 8 1.3. Our research focus In Chapter 2, we define the variables for both models, and then we describe and improve the previously designed mixed integer linear programming model for vertical alignment optimization. In Chapter 3, we modify the quasi network flow model for vertical alignment optimization. We describe several techniques to improve the solution time in Chapter 4. In Chapter 5, we test the techniques from Chapter 4, show numerical results and deduce the most efficient techniques. Chapter 6 concludes with directions for future research. 9 Chapter 2 The quadratic model for vertical alignment In this chapter we describe the variables, parameters, and sets required to model the vertical alignment of roads. Then we describe the quadratic model for vertical alignment optimization for a known horizontal alignment. 2.1 Model variables and parameters The road profile is designed as a quadratic spline. The idea of approximating the road profile by a spline was described in [MA04] and [Mor09]. Later in [KL10], it was shown that up to a quadratic spline, the linearity of the model can be maintained. In Figure 2.1, a ground profile and a vertical alignment of a sample road are shown. Elevation (𝑧) cross-section 𝑢1 𝑢2 𝑢0 ℎ1 𝑑0 𝑠0 𝑑1 𝑠1 u3 𝑢5 𝑢4 ℎ2 Ground profile ℎ4 𝑑2 𝑑3 𝑠3 𝑠2 𝑑4 𝑠4 Road profile (spline) ℎ5 𝑑5 𝑠5 Station Figure 2.1: Side view of ground profile and road profile. Here, di is the effective length of a section, hi is the ground elevation, ui is the offset from the ground profile towards the road profile. Cross-section areas are given at each station si . 10 2.1. Model variables and parameters In order to model the vertical alignment, we split the road into several sections. Let S = {1, 2, ..., n} be the index set for the sections. Every section i (∈ S) has a station number si and an effective length di . The difference between a station and a section is that a station is a point, whereas a section is a piece of ground stretched by an associated effective length. At every station, a cross section area of the ground profile is taken. So we can determine the cross section area of each material at each station point. The effective length is multiplied with the cross section area to approximate the volume of materials. A section is associated with the volume of materials, whereas a station is associated with the cross section areas at a particular point. The height of the ground profile of Section i is defined as hi . The decision variable ui is the vertical offset from the ground profile at Section i. We assume that throughout the entire length of the section, the road has a fixed height and a fixed cross section. In reality the heights and cross sections vary throughout the section, so this provides only an approximate value. The approximation error can be reduced by decreasing the section length, i.e., increasing the number of sections. However, if section lengths are small, the number of section increases and the problem size becomes large. The entire road profile is represented as a quadratic spline (Figure 2.2). The sections are grouped into segments. In every segment there may be several sections, and each segment is associated with a quadratic function. Let G = {1, 2, . . . , g¯} be the index set of the segments and Sg = {1, 2, ..., ng } be the index set of ng sections in spline segment g. The function δ : G ×Sg → S maps the index in the spline segment to the actual section index, i.e., if δ(g, j) = i, then si = sδ(g,j) , for all g ∈ G, j ∈ Sg , i ∈ S. Every two consecutive segments have one common station between them (Figure 2.2). Therefore, the last station of a spline segment is equal to the first station of the next spline segment, i.e., sδ(g,ng ) = sδ(g+1,1) , ∀g ∈ {1, . . . , g¯ − 1}. The quadratic function for each segment g ∈ G is defined as Pg (s) = ag,1 + ag,2 s + ag,3 s2 , where s is the distance from the current station to the beginning of the road along the alignment. The derivative of Pg (s) is written Pg (s) = ag,2 + 2ag,3 s. 11 2.1. Model variables and parameters Slopes of two consecutive segments are equal Segment 2 Segment 3 Elevation (z) Segment 1 𝑑0 𝑠0 𝑑2 𝑑1 𝑠1 𝑑3 𝑠3 𝑠2 𝑑4 𝑠4 h5 𝑑5 𝑠5 𝑑6 𝑠6 Section Road profile (spline) Ground profile Figure 2.2: Spline segment of vertical alignment. In general, we can represent the spline function as follows P1 (s) if sδ(1,1) ≤ s ≤ sδ(1,n1 ) , P2 (s) if sδ(2,1) ≤ s ≤ sδ(2,n ) , 2 P (s) = . . . Pg¯(s) if sδ(¯g,1) ≤ s ≤ sδ(1,ng¯ ) . Similarly, we will use the notation P (s) to represent the derivative of P (s). Since every two adjacent sections have one common section between them, to get a smooth curve, the height and slope of the beginning section of one segment should be equal to the height and slope of the ending section of the previous segment. Remark 2.1. For a long road, the value of s in Pg (s) could be large. Since Pg (s) has a square term of s, numerical errors can happen for large values of s. To eliminate these numerical errors from the implementation of the models, each value of s is calculated with respect to the beginning of its segment, i.e., s − sδ(g,1) ∀g ∈ G. Since this does not change the models, for the ease of describing the models, we use s instead of s − sδ(g,1) in Pg (s). Side-slope refers to the gradual decrease and increase in height from the 12 2.1. Model variables and parameters road profile to the ground profile of a cut and fill section, respectively. Sideslopes are very important from the civil engineering point of view because they help to make the road durable. Therefore, to model the vertical alignment problem accurately, we must take side-slopes into consideration. In Figures 2.3 and 2.4 the cross-section of a road with and without side-slopes for a cut and a fill are shown, respectively. Ground profile Cut area Cut area Road profile Without side-slopes With side-slopes Figure 2.3: The cross-section of a road with and without side-slopes (for cut). Road profile Fill area Fill area Ground profile Without side-slopes With side-slopes Figure 2.4: The cross-section of a road with and without side-slopes (for fill). Li,5 Li,4 Li,3 Li,2 Cut area Li,1 Before approximation ui M1 M2 M3 After approximation Figure 2.5: Approximation of side-slopes (for a cut). Here, M1 , M2 , M3 are three kinds of arbitrary materials shown for simple illustration. To model the side slopes, the approximation can be made with trapezoid shaped cross-sections with several rectangles (Figure 2.5). We make an approximation of the volumes of material at different offset levels from the ground profile. The volumes of material for cut and fill at every section are 13 2.1. Model variables and parameters Li,1 Li,2 Li,3 Li,4 Li,5 Fill area ui M1 M2 M3 After approximation Before Figure 2.6: Approximation of side-slopes (for a fill). the input data for the model. These volumes are approximated for each offset level from the ground profile. Suppose for each section i ∈ S, Li = {1, 2, ..., nl } is the index set for the different offset levels. The parameter Li,l ∈ R represents the altitude of cut or fill for level l ∈ Li at section i. Let K = {1, 2, ..., m} be the index set of the material types. Sample + represent input for a section is shown in Table 2.1. Let the parameter Ri,l,m − the given cut volume and Ri,l,m represent the given fill volume of material, respectively, for each section i ∈ S, each level l ∈ Li , and for each material type m ∈ K. Table 2.1: Cut and fill volume of material Level l Offset Li,l Cut Volume + Ri,l,m Fill Volume − Ri,l,m 1 2 3 4 5 -4 -2 0 2 4 262.06 168.44 82.82 5.28 0 0 0 0 0.08 70.06 The relation between cut and fill volume with the height of the offset can be understood clearly from Figure 2.7. For the vertical alignment problem, we need to find out the optimal offset (ui ) from the ground profile and + the corresponding cut and fill volume for that offset. Let the variable Vi,m − (i ∈ S, m ∈ K), and Vi,m (i ∈ S, m ∈ K) represent the total cut and fill volume of material, respectively. During the construction of a road, some materials may need to be dumped, and some materials may need to be brought in. Borrow pits are the external sections from which materials can be borrowed, and waste pits are the external sections in which materials can be dumped. Suppose B = {1, 2, ..., nβ } and W = {1, 2, ..., nω } are the two sets of indices that are 14 2.1. Model variables and parameters 300 250 200 Volume 150 (Ri,l ) Cut Volume 100 Fill Volume 50 0 -4 -2 0 2 4 Height of levels (Li,l) Figure 2.7: Volume approximation of side-slope used to index borrow and waste pits, respectively. The function ϑ : B → S maps a borrow pit index to the section index to which it is attached, and the function ϕ : W → S maps the same section for a waste pit. There are also access roads from which the construction of the road can be initiated. These access roads are also attached to a section and act as a gateway to the road. Let R = {1, 2, ..., nr } be the set of indices that is used to index the access roads. We assume that there is a borrow and a waste pit attached to each access road with infinite capacity for dumping and borrowing materials. Suppose the function : R → S maps an access road index to a section index to which it is attached, and the set N = {S ∪ B ∪ W} is used to represent sections, borrow pits, and waste pits collectively. In practice, it happens that some sections of land cannot be accessed before removing the obstacles. In [HKL11], the block concept was first introduced for earthwork operation in road design. We use this concept for vertical alignment modeling of road design. The block scenario is similar to the situation where engineers have to build a bridge or tunnel before they can move across a river or through a mountain, respectively. Suppose I = {1, 2, ..., nb } is the set of indices that is used to index blocks. We define time steps t to indicate when blocks are removed. It can be shown that at most (nb + 1) number of time steps are needed to remove all the blocks [HKL11]. Let T = {0, 1, 2, ..., nb } be the set to represent nb + 1 number of time steps needed to remove nb blocks, and let the function ς : I → S map a block index to a section index. To keep track of when a block is removed, we introduce binary variables ykt for each block k ∈ I and t ∈ T . If a block 15 2.2. The quadratic model is removed at time step t, then movement across the block is possible from the next time step t + 1. 2.2 The quadratic model In this section the quadratic model is described for obtaining an optimal vertical alignment. This model is referred to as the quadratic model because the required number of material movement variables is O(n2 ), where n is the number of sections. 2.2.1 The quadratic model for single material In [Rah12], the quadratic model for single material was described. That model had several features, for example, it incorporated blocks and sides slopes into the vertical alignment optimization. However, it had several limitations. That model was not capable to incorporate more than one material. The input volumes needed to be convex with respect to the height from the ground level. It could not consider cut and fill at the same section. The reason of not being able to incorporate all of the above features into the model was the way it defined the volume constraints. It required that volume for cut and fill must be zero at the ground level, which is not the case in practice because of the uneven shape of the earth. Therefore, [Rah12] approximated the input to apply their models. In this research, we change the volume constraint to accommodate all the features into a new modified model which is described in the next section. 2.2.2 The quadratic model for multimaterial In this section we describe the quadratic model for multimaterial by modifying the volume constraint. We also incorporate all the features that are required. For ease of explanation, first we introduce variables for material movement without considering blocks. Later we will introduce movement variables considering blocks. To track material movement, we define variable xij , which represents the amount of material moved from section i to section i consists of all indices j such that x j. For each i ∈ N , the index set N→ ij is a permitted move, j ∈ S ∪ W, if i ∈ S i if i ∈ B N→ = j : j∈S . ∅ if i ∈ W 16 2.2. The quadratic model j Similarly, for each j ∈ N the index set N← such that xij is a permitted move, i ∈ S ∪ B, j N← = i : ∅ i∈S which consists of all indices i if j ∈ S if j ∈ B . if j ∈ W i if, and only if, i ∈ N j . Finally, N 2 Note that for any i, j ∈ N , j ∈ N→ ← consists of all index pairs (i, j) such that xij is a permitted move, i N 2 = {(i, j) : j ∈ N→ } Note that N 2 = N × N , as N 2 omits index pairs (i, j) that correspond to illogical moves, such as movement from a road section into a borrow pit. Now we introduce variables for material movements considering blocks. For tracking material movement at every time step, we define the variable xijt , which represents the amount of material moved from section i to section j at time step t. Let I¯ 2 = {(k1 , k2 ) ∈ I × I : k1 < k2 and k1 , k2 are two consecutive blocks with no access road in between}, I¯← = {k ∈ I : the set of blocks k before which there is no access road}, and I¯→ = {k ∈ I : the set of blocks k after which there is no access road}. For all k ∈ I, the set Nbk consists of all pairs of sections (i, j) ∈ N 2 , such that movement between section i and j requires the removal of block k. The set Nbk1,k2 , for all (k1 , k2 ) ∈ I¯ 2 , consists of all pairs of sections (i, j) ∈ N 2 , such that sections i and j are between blocks k1 and k2 . For all k ∈ I¯← , we set Nb←,k = {(i, j) ∈ N 2 : section i and j are before block k}, and for all k ∈ I¯→ , we define Nbk,→ = {(i, j) ∈ N 2 : section i and j are after block k}. The cost of a vertical alignment depends on the embankment, excavation and hauling of materials from section to section. Let pi represent the excavation cost per unit of volume and qi represent the embankment cost per unit of volume for section i(∈ N ). Let rij be the hauling cost per unit of volume from section i to section j. The objective of the model is to minimize the total excavation costs, embankment costs, and hauling costs for moving materials between sections, borrow pits, and waste pits over all time steps. The objective function can be represented as follows, min i∈S∪B m∈K − qi Vi,m + + pi Vi,m + i∈S∪W m∈K (i,j)∈N 2 t∈T rij xijt , 17 2.2. The quadratic model + − where Vi,m (for i ∈ S ∪B, m ∈ K), and Vi,m (for i ∈ S ∪W, m ∈ K) represent the total cut and fill volume of material respectively. The total volume of material moved from a section to other sections at all time steps must be equal to the cut volume of that section (Constraint (2.1) below). Similarly, the total volume of material moved to a section from other sections at all time steps must be equal to the fill volume of that section (Constraint (2.2) below). We call these the balance constraints: + xijt,m = Vi,m , ∀ i ∈ S ∪ B, m ∈ K. (2.1) − xjit = Vi,m , ∀ i ∈ S ∪ W, m ∈ K. (2.2) i j∈N→ t∈T m∈K i j∈N← t∈T m∈K The offset value ui is the difference between the road profile, which is represented by the quadratic spline P (si ), and the given ground profile (hi ) (Constraint (2.3)). P (si ) − hi = ui , ∀i ∈ S (2.3) There could be a cut and fill of the same material at the same section according to the input volume table (see Table 2.1). Usually the cut volume decreases as the height of the offset level Li,l increases (see Table 2.1); and the fill volume increases along with the height of the offset level. That means the relationship between volume and offset level is convex. In general, if we have only a convex relationship for piecewise approximation in linear programming and we need minimization, then we can model that relationship without using binary variables (Constraints (2.4) and (2.5)). + + Vi,m ≥ Ri,l,m + + + Ri,l+1 − Ri,l,m Li,l+1 − Li,l (ui − Li,l ), ∀i ∈ S, l ∈ Li \ {nl }, m ∈ K (2.4) − − Vi,m ≥ Ri,l,m + − Ri,l+1 − − Ri,l,m Li,l+1 − Li,l (ui − Li,l ), ∀i ∈ S, l ∈ Li \ {nl }, m ∈ K. (2.5) 18 2.2. The quadratic model However, in the vertical alignment model, we are not minimizing only the cut and fill cost of material, but also minimizing the movement cost of material. As a result, if the cost of movement becomes larger than the cost of cut and fill, a stockpiling pattern will appear. Therefore, at certain offset level ui , the cut and fill volume could be larger than what we expect from the input volume table (Table 2.1). These extra volume of materials would cause stockpiling on the road. For example, in Figure 2.8, a stockpiling scenario is shown. There is a waste pit attached with Road Section 3. The dead haul distance of the waste pit from Road Section 3 is 10m. Suppose the offset heights of the Road Section 1, Section 2, and Section 3 are 0, 2 and 0 m respectively. The cut volumes of these three sections are 82.82 m3 , 5.28 m3 , and 82.82 m3 , and the fill volumes are 0 m3 , 0.08 m3 and 0 m3 respectively. In this instance, Road Section 2 needs a small amount of fill. So all the cut volumes must be hauled and dumped to the waste pit. However, if the fill cost is less than the hauling cost of material to the waste pit, then instead of carrying the material to the waste pit, the material will be dumped to a nearby station. In Figure 2.8, materials are dumped from Road Section 1 to Road Section 2, and from Road Section 2 to Road Section 1, causing the fill volume to get large. These dumpings of material to nearby road sections are valid according to Constraints 2.4 and 2.5, because the constraints only ensure the lower bound of cut and fill. Therefore, we need to introduce binary variables to ensure that we get the correct cut and fill volumes at optimal offset ui for each section i ∈ S (Constraints (2.6) and (2.7)). The binary variable νi,l (∀i ∈ S, l ∈ Li \ nl ) is used to indicate which interval (between Li,l and Li,l+1 ) of the offset levels is selected. The parameter Mi is the largest volume possible to be cut or filled at Section i. But for simplicity, we use M everywhere instead of Mi . At any section, only one of the interval offsets can be selected (Constraint (2.8)). + Vi,m ≤ + Ri,l,m + + + Ri,l+1 − Ri,l,m Li,l+1 − Li,l (ui − Li,l ) + M (1 − νi,l ), ∀i ∈ S, l ∈ Li \ {nl }, m ∈ K, (2.6) − Vi,m ≤ − Ri,l,m + − − Ri,l+1 − Ri,l,m Li,l+1 − Li,l (ui − Li,l ) + M (1 − νi,l ), ∀i ∈ S, l ∈ Li \ {nl }, , m ∈ K, (2.7) 19 2.2. The quadratic model Cut material of section 2 moves to section 1 Waste pit 𝑉1− = 5.28 Cut material of section 1 moves to section 2 Section 1 10 m 𝑉2− = 82.9 Section 2 20 m 𝑢1 = 0 𝑉1+ ≥ 82.82 𝑉1− ≥ 0 Cut material of section 3 dumped at waste pit Section 3 40 m 𝑢2 =2 𝑉2+ ≥ 5.28 𝑉2− ≥ 0.08 𝑢3 = 0 𝑉3+ ≥ 82.82 𝑉3− ≥ 0 Figure 2.8: Stockpiling scenario when Constraints (2.6) and (2.7) are not considered. νi,l = 1, ∀i ∈ S. (2.8) l∈Li \{nl } If there is a block between two sections, then material movement is not possible between those two sections until the block is removed (Constraint (2.9)). If there is no access road before a block, then material cannot be moved among sections before that block until the block is removed (Constraint (2.10)). Similarly, material movement is not possible if there is no access road after a block (Constraint (2.11)). Furthermore, if there is no access road between two blocks, then material movement is not possible in between those two blocks until one of them is removed (Constraint (2.12)). xijt,m ≤ M yk,(t−1) , ∀t ∈ T \ {0}, k ∈ I, (2.9) xijt,m ≤ M yk,(t−1) , (i, j) ∈ Nbk , m ∈ K, ∀t ∈ T \ {0}, k ∈ I¯← , (2.10) xijt,m ≤ M yk,(t−1) , i, j ∈ Nb←,k , m ∈ K, ∀t ∈ T \ {0}, k ∈ I¯→ , i, j ∈ Nbk,→ , m ∈ K, (2.11) 20 2.2. The quadratic model xijt,m ≤ M yk1 ,(t−1) + M yk2 ,(t−1) , ∀t ∈ T \ {0}, (k1 , k2 ) ∈ I¯ 2 , i, j ∈ Nbk1,k2 , m ∈ K. (2.12) The block removal indicator constraints (2.13, 2.14) ensure that when the required amount of materials are cut and filled for any section containing a block, then the block is considered removed from that section. u + xς(k)jt,m + M (1 − yku ) ≥ Vς(k),m , ∀k ∈ I, u ∈ T, m ∈ K, t=0 j∈N ς(k) → (2.13) u − xjς(k)t,m + M (1 − yku ) ≥ Vς(k),m , ∀k ∈ I, u ∈ T, m ∈ K. t=0 j∈N ς(k) ← (2.14) By the end of each time step t ∈ T , we want to remove at least the number of blocks equal to the number of time steps, so that we do not need more than nb + 1 time steps. This is guaranteed with block removal enforcement constraint (2.15). The monotonicity constraint (2.16), states that once a block is removed it remains removed. u ykt ≥ t + 1, ∀u ∈ T \ {nb }, (2.15) ∀k ∈ I, t ∈ T \ {0}. (2.16) t=0 k∈I yk,t ≥ yk,t−1 , The smoothness constraints (2.17) and (2.18) ensure that the transitions from one spline segment to the next are smooth, i.e., same grade and elevation (see Figure 2.2). Pg−1 (sδ(g,1) ) = Pg (sδ(g,1) ), ∀g ∈ G \ {1}, (2.17) Pg−1 (sδ(g,1) ) = Pg (sδ(g,1) ) ∀g ∈ G \ {1}. (2.18) The maximum allowable speed depends on the grade of the road profile. The grade constraint (2.19) makes sure that the grade of the spline segments are within the allowed maximum (GU ) and the minimum (GL ) value, so that it can maintain the safety parameters. GL ≤ Pg (sδ(g,1) ) ≤ GU , ∀g ∈ G \ {1}. (2.19) 21 2.2. The quadratic model Usually, the elevation and the grade of the starting point and the ending point of a road are defined explicitly. In addition to those points, the road designer can set the elevation and grade value for some fixed control points on the road (for example at an intersection). Let H be the index set of all control points. The fixed point constraints (2.20), (2.21), (2.22) set the grade and elevation on specific control points including the starting and the ending point. The parameters yA , yB are the elevations of the starting and the ending stations. Similarly, y¯A , y¯B are the slopes of the starting and the ending spline segments. The parameters Hi is the elevation of the station i ∈ H. P (s1 ) = yA , P (sn ) = yB , (2.20) P (s1 ) = y¯A , P (sn ) = y¯B , (2.21) P (si ) = Hi , ∀i ∈ H. (2.22) Finally, Constraints (2.23), (2.24), and (2.25) are bound constraints. The parameter Mi+ , and Mi− are the largest volume possible to be cut and filled from a section. xijt,m ≥ 0, 0≤ 0≤ + Vi,m − Vi,m ≤ ≤ Mi+ , Mi− , ∀(i, j) ∈ N 2 , t ∈ T , m ∈ K (2.23) ∀i ∈ S ∪ B, m ∈ K, (2.24) ∀i ∈ S ∪ W, m ∈ K. (2.25) In this chapter we have discussed the quadratic model for calculating optimal vertical alignment of roads. We have considered several features such as multimaterials, cut and fill at the same section of the same material, blocks, slide slopes, etc. However, the problem size increases quadratically with the number of sections. Consequently it takes a long time to solve the model for long roads. Another limitation is that we still need convex relationship between volumes of materials and the offset value. In Chapter 3, we discuss the quasi network flow model that reduces the size of the problem, and the computation time. 22 Chapter 3 Quasi network flow model for vertical alignment In this chapter the quasi network flow model is described for computing an optimal vertical alignment. This model is a modification of the traditional network flow model [AMO93, p. 12-13]. It combines the ideas of network flow and scheduling models. This model schedules the movement of materials among different sections in discrete time steps because of the presence of blocks in roads. In this model, the required number of material movement variable is O(n), where n is the number of sections. 3.1 Quasi network flow for single material In [AMO93, p. 12-13], a network flow model is described for earthwork optimization. Rahman [Rah12] modeled the vertical alignment problem by modifying the network flow model and considering blocks and side slopes. Same as the quadratic model described in the previous chapter, this quasi network flow model has the same limitation. However, by modifying the volume constraint and without altering the input volume of materials we are able to use it for multimaterial. 3.2 Quasi network flow for multimaterial In the quasi network flow model, sections and pits are considered as nodes, and the feasible moves are represented as arcs. This quasi network flow model consists of a series of nodes, which are connected to their adjacent nodes (Figure 3.1). The materials can flow from section to section towards the East and West directions. In every section we have to decide whether we want to fill the section with materials or transfer it to the next section, or cut materials to add more to the flow. To represent these flows towards the East and West directions, at each section virtual nodes are introduced called transit 23 3.2. Quasi network flow for multimaterial West transit flow West transit node 𝑖−1 𝑟 𝑓𝑖,𝑖−1,𝑡,𝑚 West transit node 𝒊 Section 𝒊 𝑟 𝑓𝑖−1,𝑖,𝑡,𝑚 𝑙 𝑓𝑖,𝑖,𝑡,𝑚 𝑢 𝑓𝑖,𝑖+1,𝑡,𝑚 𝑙 𝑓𝑖−1,𝑖,𝑡,𝑚 East transit node 𝑖−1 West transit node 𝑖+1 𝑙 𝑓𝑖+1,𝑖,𝑡,𝑚 𝑢 𝑓𝑖,𝑖−1,𝑡,𝑚 𝑢 𝑓𝑖,𝑖,𝑡,𝑚 𝑟 𝑓𝑖+1,𝑖,𝑡,𝑚 East transit node 𝒊 𝑟 𝑓𝑖,𝑖+1,𝑡,𝑚 East transit node 𝑖+1 East transit flow Figure 3.1: A typical section i at time-step t. nodes for both directions (Figure 3.1). If materials moved from one section to another towards the West direction, then the material goes through the West transit nodes, and this flow of material is referred as West transit flow. Similarly, the flow towards the East direction goes through East transit r nodes, and is referred as East transit flow. Let the variables fi,i−1,t,m and r fi,i+1,t,m (∀i ∈ S, t ∈ T , m ∈ K) be the flow of materials from one transit node to the next in the West and East directions, respectively. To represent the cut and fill volume of materials at each section, unload and load flows are introduced for each section. Note that, cut and fill can happen within the same section. The cut materials can be transferred to the East and West transit nodes, and within the same section. Similarly, the fill materials can be brought from the East and West transit nodes, and l l l , fi+1,i,t,m , and fi,i,t,m within the same section. Let the variables fi−1,i,t,m (∀i ∈ S, t ∈ T , m ∈ K) represent the load (fill) flows of materials to the East and West transit nodes, and within the same section, respectively. Similarly, u u u the variables fi,i−1,t,m , fi,i+1,t,m , and fi,i,t,m (∀i ∈ S, t ∈ T , m ∈ K) represent the unload (cut) flows of materials from the West and East transit nodes, and within the same section, respectively. The borrow and waste pits are attached to their associated sections. 24 3.2. Quasi network flow for multimaterial Each borrow pit can only have unload flows to both transit nodes. These unload flows represent the cut volume from the borrow pit. The flows from borb b row pits are called borrow flows. Let the variables fj,ϑ(j)−1,t and fj,ϑ(j)+1,t,m (∀j ∈ B, t ∈ T , m ∈ K) be the flows of materials to the West and East transit nodes, respectively, from the borrow pit. Similarly, for each waste pit there are load flows from both directions. These load flows represent the fill volume of the waste pit and are called waste flows. Let the variw w ables fϕ(j)−1,j,t,m and fϕ(j)+1,j,t,m (∀j ∈ W, t ∈ T , m ∈ K) be the flows of materials from the East and West transit nodes to waste pit, respectively. West transit flow West transit node 𝑖−1 𝑟 𝑓𝑖,𝑖−1,𝑡,𝑚 West transit node 𝒊 Section 𝒊 𝑟 𝑓𝑖−1,𝑖,𝑡,𝑚 𝑙 𝑓𝑖,𝑖,𝑡,𝑚 Waste pit 𝜑(𝑘) 𝑢 𝑓𝑖,𝑖+1,𝑡,𝑚 𝑙 𝑓𝑖−1,𝑖,𝑡,𝑚 East transit node 𝑖−1 West transit node 𝑖+1 𝑙 𝑓𝑖+1,𝑖,𝑡,𝑚 𝑢 𝑓𝑖,𝑖−1,𝑡,𝑚 Borrow pit 𝑓 𝑢 𝑖,𝑖,𝑡,𝑚 𝜗(𝑗) 𝑟 𝑓𝑖+1,𝑖,𝑡,𝑚 East transit node 𝒊 𝑟 𝑓𝑖,𝑖+1,𝑡,𝑚 East transit node 𝑖+1 East transit flow Figure 3.2: A typical section i at time-step t with borrow and waste pit associated with it (where ϑ(j) = ϕ(k) = i). The function ϑ : B → S maps a borrow pit index to the section index to which it is attached, and the function ϕ : W → S maps the same section for a waste pit. The cost of hauling materials from Section i to Section i−1 (respectively i + 1) is represented by cri,i−1 = cdi,i−1 (respectively cri,i+1 = cdi,i+1 ), where c represents the cost of moving one unit volume of material per unit distance, and dij is the distance between section i and j. The objective function of the quasi network flow model is also to minimize the total cost in excavation, embankment and hauling materials, which 25 3.2. Quasi network flow for multimaterial can be represented as follows, − qi,m Vi,m + + pi,m Vi,m + min i∈S∪B m∈K i∈S∪W m∈K r r cri,i−1 fi,i−1,t,m + cri,i+1 fi,i+1,t,m i∈S t∈T m∈K b b + fj,ϑ(j)+1,t,m cd¯j fj,ϑ(j)−1,t,m + j∈B t∈T m∈K w cd¯j fϕ(j)−1,j,t,m + fϕ(j)+1,j,t,m . + j∈W t∈T m∈K Notice that the objective function in this model is more strictly defined than in the quadratic model described earlier. In particular, the hauling cost of material must be a linear function of the distance traveled. This is unrealistic for long distances, but reasonably accurate for short hauls. The transit nodes are virtual nodes that provide transits for all associated flows. Therefore, the sum of the flows (demand) coming to a transit node must be equal to the sum of the flows leaving (supply) the node. The flow constraints for the East transit node (Constraint (3.1)), and for the West transit node (Constraint (3.2)) ensure that the supply and demand at both transit nodes are equal. r u fi−1,i,t,m + fi,i+1,t,m + b r l fj,i+1,t = fi,i+1,t,m + fi−1,i,t,m + j∈B ϑ(j)=i w fi−1,j,t,m , j∈W ϑ(j)=i ∀t ∈ T , i ∈ S, m ∈ K, (3.1) r u fi+1,i,t,m +fi,i−1,t,m + b r l fj,i−1,t,m = fi,i−1,t,m +fi+1,i,t,m + j∈B ϑ(j)=i w fi+1,j,t,m , j∈W ϑ(j)=i ∀t ∈ T , i ∈ S, m ∈ K. (3.2) The balance constraints ensure that the total unload flows from a section is equal to the cut volume of that section (Constraint (3.3)), and the total load flows to a section is equal to the fill volume (Constraint (3.4)). Borrow 26 3.2. Quasi network flow for multimaterial (Constraint (3.5)) and waste (Constraint (3.6)) pits constraints are written similarly. + u u u fi,i−1,t,m + fi,i+1,t,m + fi,i,t,m = Vi,m , ∀i ∈ S, m ∈ K, (3.3) − l l l fi−1,i,t,m + fi+1,i,t,m + fi,i,t,m = Vi,m , ∀i ∈ S, m ∈ K, (3.4) + b b = Vj,m + fj,ϑ(j)+1,t,m , fj,ϑ(j)−1,t,m ∀j ∈ B, m ∈ K, (3.5) − w = Vj,m fϕ(j)−1,j,t + fϕ(j)+1,j,t,m , ∀j ∈ W, m ∈ K. (3.6) t∈T t∈T t∈T t∈T The volume constraints (2.4), (2.5), (2.6), (2.7), (2.8), smoothness constraints (2.17), (2.18), grade constraints (2.19) and fixed point constraints (2.20), (2.21), (2.22) are the same for this quasi network flow model as described in the quadratic model. r If section i is a block, then for the East transit node equations fi−1,i,t,m = l r u fi−1,i,t,m and fi,i+1,t,m = fi,i+1,t,m (∀t ∈ T , m ∈ K) ensure that no material r can transfer across section i to the East direction. Because fi−1,i,t,m = l fi−1,i,t,m implies that when materials are transferred from section i − 1 to r section i, all the materials are loaded (filled) to section i. And fi,i+1,t,m = u fi,i+1,t,m implies that when materials are transferred from section i to section i + 1, all the materials are unloaded (cut) from Section i to Section i + r l 1. Similarly, in the case of West transit nodes, fi+1,i,t,m = fi+1,i,t and r u fi,i−1,t,m = fi,i−1,t,m ensure that no material can transfer across Section i to the West direction. From the above reasoning, we can ensure that no material movement can occur over a block to the East direction, until that block is removed by Constraints (3.7), (3.8), (3.9), and (3.10). Similarly, for the West direction, Constraints (3.11), (3.12), (3.13), (3.14) ensure no movement over a block. r l −(fς(k)−1,ς(k),t,m − fς(k)−1,ς(k),t,m ) ≤ M yk,t−1 , r l fς(k)−1,ς(k),t,m − fς(k)−1,ς(k),t,m ≤ M yk,t−1 , r u −(fς(k),ς(k)+1,t,m − fς(k),ς(k+1),t,m ) ≤ M yk,t−1 , r u fς(k),ς(k)+1,t,m − fς(k),ς(k+1),t,m ≤ M yk,t−1 , ∀k ∈ I, t ∈ T , m ∈ K, (3.7) ∀k ∈ I, t ∈ T , m ∈ K, (3.8) ∀k ∈ I, t ∈ T , m ∈ K, (3.9) ∀k ∈ I, t ∈ T , m ∈ K. (3.10) 27 3.2. Quasi network flow for multimaterial l r ) ≤ M yk,t−1 , − fς(k)+1,ς(k),t,m −(fς(k)+1,ς(k),t,m l r ≤ M yk,t−1 , − fς(k)+1,ς(k),t,m fς(k)+1,ς(k),t,m u r ) ≤ M yk,t−1 , − fς(k),ς(k)−1,t,m −(fς(k),ς(k)−1,t,m u r ≤ M yk,t−1 , − fς(k),ς(k)−1,t,m fς(k),ς(k)−1,t,m ∀k ∈ I, t ∈ T , m ∈ K, (3.11) ∀k ∈ I, t ∈ T , m ∈ K, (3.12) ∀k ∈ I, t ∈ T , m ∈ K, (3.13) ∀k ∈ I, t ∈ T , m ∈ K. (3.14) The block constraints must also ensure that no earth movement can occur among sections, borrow pits, and waste pits: in between two blocks, before the first block, and after the last block with no access roads, until blocks are removed. Therefore, there is no transit flow (Constraints (3.15), (3.16)), borrow flow (Constraints (3.17), (3.18)), or waste flow (Constraints (3.19), (3.20)) between two blocks with no access roads until one of the blocks is removed. r fi,i+1,t,m ≤ M (yk1 ,t−1 + yk2 ,t−1 ), ∀t ∈ T , (k1 , k2 ) ∈ I¯ 2 , m ∈ K, r fi+1,i,t,m ς(k1 ) ≤ i, i + 1 ≤ ς(k2 ), (3.15) 2 ¯ ∀t ∈ T , (k1 , k2 ) ∈ I , m ∈ K, ≤ M (yk1 ,t−1 + yk2 ,t−1 ), b fj,ϑ(j)+1,t,m ≤ M (yk1 ,t−1 + yk2 ,t−1 ), ς(k1 ) ≤ i, i + 1 ≤ ς(k2 ), (3.16) 2 ¯ ∀t ∈ T , (k1 , k2 ) ∈ I , m ∈ K, ς(k1 ) ≤ ϑ(j) − 1, ϑ(j), ϑ(j) + 1 ≤ ς(k2 ), b fj,ϑ(j)−1,t,m ≤ M (yk1 ,t−1 + yk2 ,t−1 ), (3.17) ¯2 ∀t ∈ T , (k1 , k2 ) ∈ I , m ∈ K, ς(k1 ) ≤ ϑ(j) − 1, ϑ(j), ϑ(j) + 1 ≤ ς(k2 ), w fϕ(j)+1,j,t,m ≤ M (yk1 ,t−1 + yk2 ,t−1 ), (3.18) ¯2 ∀t ∈ T , (k1 , k2 ) ∈ I , m ∈ K, ς(k1 ) ≤ ϕ(j) − 1, ϕ(j), ϕ(j) + 1 ≤ ς(k2 ), w fϕ(j)−1,j,t,m ≤ M (yk1 ,t−1 + yk2 ,t−1 ), (3.19) ∀t ∈ T , (k1 , k2 ) ∈ I¯ 2 , m ∈ K, ς(k1 ) ≤ ϕ(j) − 1, ϕ(j), ϕ(j) + 1 ≤ ς(k2 ). (3.20) 28 3.2. Quasi network flow for multimaterial There will also be no transit flow (Constraints (3.21) and (3.22)), borrow flow (Constraints 3.23 and 3.24), or waste flow (Constraints 3.25 and 3.26) after the last block with no access road until the block is removed. r fi,i+1,t,m ≤ M yk1 ,t−1 , r fi+1,i,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , ς(k) ≤ i, i + 1 ≤ n, k ∈ I¯→ , m ∈ K, (3.21) ∀t ∈ T , ς(k) ≤ i, i + 1 ≤ n, k ∈ I¯→ , m ∈ K (3.22) b ≤ M yk1 ,t−1 , fj,ϑ(j)+1,t,m ∀t ∈ T , ς(k) ≤ ϑ(j) − 1, ϑ(j), ϑ(j) + 1 ≤ n, k ∈ I¯→ , m ∈ K, (3.23) b fj,ϑ(j)−1,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , ς(k) ≤ ϑ(j) − 1, ϑ(j), ϑ(j) + 1 ≤ n, k ∈ I¯→ , m ∈ K (3.24) w fϕ(j)+1,j,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , ς(k) ≤ ϕ(j) − 1, ϕ(j), ϕ(j) + 1 ≤ n, k ∈ I¯→ , m ∈ K, (3.25) w fϕ(j)−1,j,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , ς(k) ≤ ϕ(j) − 1, ϕ(j), ϕ(j) + 1 ≤ n, k ∈ I¯→ , m ∈ K. (3.26) Similarly, there will also be no transit flow (Constraints (3.27) and (3.28)), borrow flow (Constraints (3.29) and (3.30)), or waste flow (Constraints (3.31) and (3.32)) before the first block with no access road until the block is removed. r fi,i+1,t,m ≤ M yk1 ,t−1 , r fi+1,i,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , 1 ≤ i, i + 1 ≤ ς(k), k ∈ I¯← , m ∈ K, (3.27) ¯ ∀t ∈ T , 1 ≤ i, i + 1 ≤ ς(k), k ∈ I← , m ∈ K, (3.28) b fj,ϑ(j)+1,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , 1 ≤ ϑ(j) − 1, ϑ(j), ϑ(j) + 1 ≤ ς(k), k ∈ I¯← , m ∈ K, (3.29) b fj,ϑ(j)−1,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , 1 ≤ ϑ(j) − 1, ϑ(j), ϑ(j) + 1 ≤ ς(k), k ∈ I¯← , m ∈ K, (3.30) w fϕ(j)+1,j,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , 1 ≤ ϕ(j) − 1, ϕ(j), ϕ(j) + 1 ≤ ς(k), k ∈ I¯← , m ∈ K, (3.31) w fϕ(j)−1,j,t,m ≤ M yk1 ,t−1 , ∀t ∈ T , 1 ≤ ϕ(j) − 1, ϕ(j), ϕ(j) + 1 ≤ ς(k), k ∈ I¯← , m ∈ K. (3.32) 29 3.2. Quasi network flow for multimaterial The block removal indicator constraints ensure that when the required amount of earth is excavated from or embanked to a section with a block, then the block is considered removed (Constraints (3.33) and (3.34)). u + u u fς(k),ς(k)−1,t,m + fς(k),ς(k)+1,t,m + M (1 − yku ) ≥ Vς(k),m , t=0 ∀k ∈ I, u ∈ T, m ∈ K, (3.33) u − l l + fς(k)+1,ς(k),t,m + M (1 − yku ) ≥ Vς(k),m , fς(k)−1,ς(k),t,m t=0 ∀k ∈ I, u ∈ T, m ∈ K. (3.34) The block removal enforcement Constraint (2.15) and monotonicity Constraint (2.16) are the same for the quasi network flow model as described for the quadratic model. The extra bound constraints set the lower bounds of the variables for this model. r fi,i−1,t,m ≥ 0, r fi,i+1,t,m ≥ 0, ∀i ∈ S, t ∈ T , m ∈ K, (3.35) l fi−1,i,t,m ≥ 0, l fi+1,i,t ≥ 0, ∀i ∈ S, t ∈ T , m ∈ K, (3.36) u fi,i−1,t,m ≥ 0, b fj,ϑ(j)−1,t,m ≥ w fϕ(j)−1,j,t,m ≥ u fi,i+1,t ≥ 0, b fj,ϑ(j)+1,t,m w fϕ(j)+1,j,t,m ∀i ∈ S, t ∈ T , m ∈ K, (3.37) ≥ 0, ∀j ∈ B, t ∈ T , m ∈ K, (3.38) ≥ 0, ∀j ∈ W, t ∈ T , m ∈ K. (3.39) 0, 0, In this chapter we have discussed the quasi network flow model for the vertical alignment of roads. This model reduces the size of the problem from the quadratic model (see Chapter 2) from quadratic to linear with respect to the number of sections. However, it has one drawback: the cost function must be linear with respect to the hauling distance of materials. And we still need a convex relationship between volumes of materials and the offset value. In Chapter 4, we discuss some techniques to improve the solution time for both models and remove the dependency on the convex relationship between volume and offset levels. 30 Chapter 4 Speedup techniques One of our goals in this research is to determine methods to solve the vertical alignment problem in the most efficient manner. The models we described in the previous two chapters can solve problems according to the full specification except one limitation, i.e., the volume of each material must be convex with respect to the height of the offset level. In this chapter we also remove that limitation of not able to handle non-convexity. To make an interactive design tools it is necessary to compute the optimal solution quickly. In this chapter we describe four strategies that we used to decrease the time to find a solution. In Chapter 5 we numerically test and compare these methods. 4.1 Techniques with offset levels As input for both models (the quadratic and the quasi network flow), we get volume information at different offset levels. We select an optimal height among those input offset levels by approximating the volumes of materials as a piecewise linear function (see Constriants (2.4), (2.5), (2.6), (2.7), and (2.8)). We have binary variables for each offset levels for all sections. In total we need n(nl − 1) binary variables, where n is the number of sections and nl is the number of offset levels. This large number of binary variables increases the solution time significantly. In the next two subsection we describe two techniques to accelerate the computation by modifying the constraints involving with offset levels. These techniques are applicable for both models. However, the second technique will remove the limitation of non-convexity discussed above. 4.1.1 Reducing binary variables for offset levels In the volume constraints (Constraints (2.4), (2.5), (2.6), and (2.7)) of the quadratic and quasi network flow models, there are binary variables for all the intervals of the input offsets (Li,l ) for each section i ∈ S. This 31 4.1. Techniques with offset levels requires n(nl − 1) binary variables, where n is the number of sections and (nl − 1) is the number of intervals of the input offsets. For simplicity, we now assume that every section i ∈ S has the same number of input offsets (Li,l ) numbered from 0 to nl −1. Let L = {0, 1, ..., nl −2} be the index set for the intervals of the input offset levels of all sections. A number from 0 to nl − 2 can be represented using log2 (nl − 2) binary variables as follows: log2 (nl −2) blk · 2k , l= k=0 where blk ∈ {0, 1} for each l ∈ L. Let Bk1 = {l ∈ L : blk = 1} and Bk0 = {l ∈ L : blk = 0}. Define the set L = {0, 1, 2, ..., log2 (nl −2) } to help representing (nl −1) number of intervals of offsets in binary format. Let αi,k (∀k ∈ L , i ∈ S) be the binary variable which represents the selected interval of offsets for Section i. Note that indicator variables are still needed to write the volume constraints (2.6, 2.7). Therefore, we introduce extra continuous variables Γi,l ∈ [0, 1] (for all i ∈ S, l ∈ L) to indicate which interval of the offset levels is selected. The new constraints are written in such a way that Γi,l can only take the value 0 or 1. The variable Γi,l plays the role of the binary variable νi,l of the previous models. The new constraints (4.1) and (4.2) ensure that only one of Γi,l (∀l ∈ L) can equal 1 for each section i ∈ S. Γi,l ≤ αik , ∀i ∈ S, k ∈ L , (4.1) Γi,l ≤ (1 − αik ), ∀i ∈ S, k ∈ L . (4.2) l∈Bk1 l∈Bk0 In applying the above, we also note that Constraint (2.8) is no longer required because for a given combination of αik (∀k ∈ L ), for each section i ∈ S, only one of the Γi,l (∀l ∈ L) can be one. Example 4.1. Consider the case of 5 input offset levels. Then we have 4 intervals and the set L = {0, 1}. Thus for each section i ∈ S, we get the 32 4.1. Techniques with offset levels following inequalities: Γi,1 + Γi,3 ≤ αi0 , Γi,0 + Γi,2 ≤ 1 − αi0 , Γi,2 + Γi,3 ≤ αi1 , Γi,0 + Γi,1 ≤ 1 − αi1 . Therefore, if we choose (αi1 , αi0 ) = (1, 0) that represents interval 2 of offset levels, then we get the following concrete inequalities from where it is easily noticeable that only Γi,2 equals to 1. Γi,1 + Γi,3 ≤ 0, Γi,0 + Γi,2 ≤ 1, Γi,2 + Γi,3 ≤ 1, Γi,0 + Γi,1 ≤ 0. Now, if we replace the binary variable νi,l with the continuous indicator variable Γi,l in the volume constraints (2.6, 2.7), and add new constraints (4.1) and (4.2), then we will get the same result as the original model, but the binary variables are reduced from n(nl − 1) to n log2 (nl − 1) and n constraints (2.8) are discarded. However, the number of continuous variables is increased by n(nl − 1), and 2n log2 (nl − 1) new constraints are added. 4.1.2 Modeling volume constraints with SOS2 variables The volume constraints in the quadratic and quasi network flow models work only when the input volume maintains the convex relationship with the height. But if the convexity does not hold, as often occurs in practice, then we need to select two adjacent binary variables to indicate an interval. However, instead of writing complicated volume constraints and binary variable selection constraints, we can use SOS2 variables to model this piecewise relationship between volume and offset height. Recall that SOS2 variables, or special ordered set variables of type 2, are variables with the property that at most two variables can be nonzero and they must be adjacent to each other [KdFJN04],[KdFN06],[MMM06],[Tom81]. Using this technique we are able to handle non-convex relation of volumes with respect to the heights of offset levels. Let λi,l (∀l ∈ Li ) be the set of SOS2 variables for each section i ∈ S. These variables denote non-negative weights for all levels such that their sum is 1 (Constraint (4.3)). The offset variable ui can be any point in 33 4.2. Techniques with blocks between two input offset levels (l and l + 1) that can be calculated by the weighted sum of the two adjacent input offset heights (Constraint (4.4)). Similarly, the cut and fill volumes can be calculated using the weighted sum of input volumes of two adjacent offset levels (Constraints (4.5) and (4.6)). In this formulation, we do not have to calculate slopes for each interval. λi,l = 1, ∀i ∈ S, (4.3) λi,l Li,l = ui , ∀i ∈ S, (4.4) + = Vi+ , λi,l Ri,l ∀i ∈ S, (4.5) − λi,l Ri,l = Vi− , ∀i ∈ S. (4.6) l∈Li l∈Li l∈Li l∈Li 4.2 Techniques with blocks Considering blocks during earthwork operation is a great idea. However, blocks make the problem harder to solve. We need to find an optimal schedule for material movement during vertical alignment optimization. To indicate the removal of blocks we define binary variables in Chapter 2. We need nb (nb + 1) binary variables for blocks in both models (Quadratic and Quasi network flow), where nb is the number of blocks. Moreover, it increases the number of movement (quadratic) or flow (quasi network flow) variables by a factor of (nb + 1) to associate time steps into them. 4.2.1 Block constraints with SOS1 variables In the basic quadratic and quasi network flow models, the block constraints have monotonicity constraint (2.16). The monotonicity constraint ensures that once a block is removed it remains removed by setting 1 to the binary variables ykt , for all k ∈ I, t ∈ T , upto the last time step. However, the block k is removed when 1 is set in ykt for the first time. From this reasoning, it follows that we can model the block constraints with SOS1 variable. Recall that SOS1 variables have the property that at most one variable can be 1 from that set. The SOS1 variables can be treated very efficiently by most Mixed Integer Linear Programming (MILP) solvers. For each block k ∈ I, we introduce a set of SOS1 variables γkt for all t ∈ T . As a result, the monotonicity constraints are no longer needed. 34 4.2. Techniques with blocks However we have to rewrite all the block constraints for both basic models as a summation of γkt instead of just one ykt per constraint. In particular, the block Constraints (2.9), (2.10), (2.11),(2.12), (2.13), (2.14), and (2.15) of the quadratic model are rewritten using SOS1 variables as Constraints (4.7), (4.8), (4.9), (4.10), (4.9), and (4.10). t−1 xijt,m ≤ M ∀t ∈ T \ {0}, k ∈ I, γkw , w=0 (i, j) ∈ Nbk , m ∈ K, (4.7) t−1 xijt,m ≤ M ∀t ∈ T \ {0}, k ∈ I¯← , γkw , w=0 i, j ∈ Nb←,k , m ∈ K, (4.8) t−1 xijt,m ≤ M ∀t ∈ T \ {0}, k ∈ I¯→ , γkw , w=0 i, j ∈ Nbk,→ , m ∈ K, (4.9) t−1 xijt,m ≤ M ∀t ∈ T \ {0}, (k1 , k2 ) ∈ I¯ 2 , (γk1 ,w + γk2 ,w ) , w=0 i, j ∈ Nbk1,k2 , m ∈ K, (4.10) u u xς(k)jt,m + M 1− γkw + ≥ Vς(k) , ∀k ∈ I, u ∈ T, m ∈ K, w=0 t=0 j∈N ς(k) → m∈K (4.11) u u xjς(k)t + M t=0 j∈N ς(k) ← m∈K 1− γkw − ≥ Vς(k) , ∀k ∈ I, u ∈ T, m ∈ K. w=0 (4.12) The block constraints for the basic quasi network flow model are rewritten in an analogous manner. 4.2.2 Reducing the number of binary variables for blocks An alternative to SOS1 constraints for working with blocks, is to rewrite the block variables using log n binary variables. This modeling method uses 35 4.2. Techniques with blocks similar techniques as those discussed in Subsection 4.1.1 for offset levels. We can represent each time step t ∈ T in binary format as follows: log2 nb btj · 2j , t= j=0 where btj ∈ {0, 1}. Define Bt1 = {j : btj = 1} and Bt0 = {j : btj = 0}, for each t ∈ T . Let T = {0, 1, 2, ..., log2 nb } be a set that helps to represent (nb + 1) number of time steps in binary format. Let vkj (∀j ∈ T , k ∈ I) be the set of binary variables which represent the time step at which the block k is removed. We then introduce extra continuous variables βkt ∈ [0, 1] (for all t ∈ T , k ∈ I) to indicate time step t when the block k is removed. The new constraints (4.13) and (4.14) ensure that there will always be consecutive ones in βkt (∀t ∈ T ) for each k ∈ I upto the last time step t. This represents that once a block is removed it remains removed. t−1 βku ≤ t u=0 (1 − vkj ), ∀k ∈ I, t ∈ T \ {0, nb }, (4.13) ∀k ∈ I. (4.14) j∈Bt1 log2 nb nb 2j · vkj , βku ≥ (nb + 1) − u=0 j=0 Therefore, the monotonicity constraint (2.16) is not needed any more. The other block constraints for both (quadratic and quasi network flow) models remain the same. However, one needs to replace the binary variables ykt with the continuous variables βkt . Example 4.2. If we have I = {1, 2 . . . , 7} and T = {0, 1, 2 . . . , 7} then for each k ∈ I we get the following inequalities from the Constraint (4.13): βk0 ≤ [(1 − vk0 )] · 1, βk0 + βk1 ≤ [(1 − vk1 )] · 2, βk0 + βk1 + βk2 ≤ [(1 − vk1 ) + (1 − vk0 )] · 3, βk0 + βk1 + βk2 + βk3 ≤ [(1 − vk2 )] · 4, βk0 + βk1 + βk2 + βk3 + βk4 ≤ [(1 − vk2 ) + (1 − vk0 )] · 5, βk0 + βk1 + βk2 + βk3 + βk4 + βk5 ≤ [(1 − vk2 ) + (1 − vk1 )] · 6, βk0 + βk1 + βk2 + βk3 + βk4 + βk5 + βk6 ≤ [(1 − vk2 ) + (1 − vk1 ) + (1 − vk0 )] · 7. 36 4.2. Techniques with blocks From Constraint (4.14), for each k ∈ I we get the following inequality: βk0 + βk1 + βk2 + βk3 + βk4 + βk5 + βk6 + βk7 ≥ 8 − [22 vk2 + 2vk1 + vk0 ]. Lemma 4.3. Assume constraints (4.13) and (4.14) hold. If block k ∈ I is removed at time step t ∈ T , then i. βk0 = βk1 = ... = βk(t−1) = 0, ii. βkt = βk(t+1) = ... = βknb = 1. Proof. (Part i): We know, the binary representation of the tth time step can be given as, log2 nb btj · 2j . t= j=0 If the tth time step is selected for a block k ∈ I, then we can write t = log2 nb vkj · 2j . So, btj = vkj for all index j for the tth time step of block j=0 k. Therefore, Bt1 = {j : btj = vkj = 1}. Thus, in Constraint (4.13), the t−1 i=0 βki = 0. This proves j∈Bt1 (1 − vkj ) term becomes zero. As a result, the first part. (Part ii): If we have nb blocks, then we know we have nb + 1 time steps for each block k ∈ I. Also notice, time step starts from 0 and ends at nb . If log n the tth time step is selected for block k, then t = j=02 b vkj · 2j for that block. In the first part of this theorem, we prove that, the first t continuous indicator variables (βk0 , βk1 , ..., βk(t−1) ) are zero. From Constraint (4.14), we know, the sum of all the continuous variables should be at least (nb + 1) − t. The continuous indicator variable can have value at most 1. So, to make the sum (nb +1)−t, we need at least (nb +1)−t continuous indicator variables to be 1. If we rewrite Constraint (4.14), then we get the following expression, Sum of first t continuous indicator variables + Sum of rest of the continuous indicator variables ≥ (nb + 1) − t ⇒ [βk0 + βk1 + ... + βk(t−1) ] + [βkt + βk(t+1) + ... + βknb ] ≥ (nb + 1) − t ⇒ [0] + [sum of rest of the (nb + 1 − t) continuous indicator variables] ≥ (nb + 1) − t. To satisfy the last line, the continuous indicator variables from βkt to βknb should be one. 37 4.2. Techniques with blocks Remark 4.4. (Feasibility) If block k ∈ I is removed at time step t ∈ T , then the last (nb − t) inequalities of the first constraint (4.13) will always have at least t ∈ T , where t > t, on the right hand side. Also, on the left hand side, there are t continuous indicator variables, which makes the solution feasible to always get consecutive ones up to the end. Remark 4.5. We no longer require the monotonicity constraint βk(t+1) ≥ βkt for each t ∈ T ∩ {1, 2, ..., nb } under this formulation, because Lemma 4.3 proves that these properties will be satisfied for any selection of t using binary variables vkj , where j ∈ T . Theorem 4.6. The solution of the quadratic model is (xijtm , ykt ), where ykt is binary variable if and only if (xijtm , βkt ) is the solution to the current model, where βkt is continuous variable. Proof. Let (xijtm , ykt ) be the solution for the quadratic model. In the current model, we have the same constraint sets as the quadratic model except for the monotonicity constraints (2.16), which is not required anymore. Additionally, in the current model we have constraints (4.13) and (4.14) that ensure the monotonicity of βkt (Lemma 4.3). So, if we have monotonicity in the quadratic model, then the solution should also satisfy the extra two constraints (4.13) and (4.14) of the current model. Therefore (xijtm , βkt ) is the solution to the current model. Let (xijtm , βkt ) be the solution to the current model. In the quadratic model, ykt is a binary variable with the same constraint satisfying Constraints (2.16), but without the extra two constraints (4.13) and (4.14) of the current model. These two extra constraints (4.13) and (4.14) ensure monotonicity in the current model. So in the solution βkt will have consecutive ones till the last time step. Therefore, it should satisfy the monotonicity constraint (2.16) in the quadratic model. Hence, (xijtm , ykt ) is the solution to the quadratic model. Proposition 4.7. Representing nb + 1 time steps for each block k ∈ I in binary format, can be done using nb ( log2 nb + 1) binary variables. Proof. Let, t be an integer number. We know, t can be represented in binary format using the following formulation, log2 t b · 2j , t= j=0 where b ∈ {0, 1}. So, to represent time step nb in binary format, we can use log2 nb + 1 binary variables. For each block k ∈ I, we need to have a time 38 4.2. Techniques with blocks step which will indicate when block k is removed. There are nb number of blocks that need to be removed, and time steps are ranged from 0 to nb . Therefore, one can use nb ( log2 nb + 1) binary variables. This approach reduces the number of binary variables from nb (nb + 1) to nb ( log2 nb + 1), but increases the number of continuous variable by nb (nb + 1) and constraints by nb . 39 Chapter 5 Numerical results In this chapter we discuss the performance of the models and techniques that are described in earlier chapters. 5.1 Experimental setup The experiments were setup with 60 different test problems with various section lengths, numbers of sections, blocks, access roads, and offset levels. These 60 test problems were created with help from our industry partner. We have used 7 roads that are listed in Table A.7. The configuration of all 60 test problems is listed in Tables A.8 and A.9. A sample input file for multi-material case is shown in Table A.10. All experiments were performed on a Dell workstation with an Intel(R) Xeon(R) 3.20 GHz (4 cores) processors, a 24 GB of RAM and a 64-bit Windows 7 Enterprise operating system. We used two different MILP solvers to solve all the test problems. First, an academic edition of the IBM ILOG CPLEX Optimizer v12.4 (http://www.cplex.com) and second, an open source MILP solver CBC v2.7.7 (https://projects.coin-or.org/Cbc). The models were programmed in C++ using MS Visual Studio 2010 Professional edition. We have two basic models: a quadratic model and a quasi network flow model (see Chapters 2 and 3). In Chapter 4, we outlined several strategies to modify both models to speedup the solution time. For offset levels, in addition to the basic method, we use a reduced binary variable technique and SOS2 variable technique (see Subsections 4.1.1 and 4.1.2). For the cases of blocks, in addition to the basic way of dealing with blocks, we use SOS1 variable technique and a reduced n log n technique (see Subsections 4.2.1 and 4.2.2). In sum, we have 2 models (quadratic, quasi network flow) with 3 level modeling techniques (basic, reduced binary, SOS2) and 3 block modeling techniques (basic, n log n, SOS1), creating 18 different strategies and two solvers. These 18 strategies are shown in Table 5.1. All the test problems are solved with a 1% MIP gap tolerance and a maximum 4 minutes of CPU time. 40 5.1. Experimental setup Table 5.1: List of strategies for single material with blocks Strategy Model Level Technique Block Technique QBB QBN QBS QNB QNN QNS QSB QSN QSS NBB NBN NBS NNB NNN NNS NSB NSN NSS Quadratic Quadratic Quadratic Quadratic Quadratic Quadratic Quadratic Quadratic Quadratic Quasi network Quasi network Quasi network Quasi network Quasi network Quasi network Quasi network Quasi network Quasi network Basic Basic Basic Binary Binary Binary SOS2 SOS2 SOS2 Basic Basic Basic Binary Binary Binary SOS2 SOS2 SOS2 Basic n log n SOS1 Basic n log n SOS1 Basic n log n SOS1 Basic n log n SOS1 Basic n log n SOS1 Basic n log n SOS1 flow flow flow flow flow flow flow flow flow reduction reduction reduction reduction reduction reduction 41 5.2. Performance measurement 5.2 Performance measurement In order to compare the performance of different strategies, we use performance profiles as developed in [DM02]. Performance profiles are designed to graphically compare both speed and robustness of strategies across a test set. This is done by plotting, for each strategy, the percentage of problems that are solved within a factor of the best solve time. Let P be the set of all problems, and S be the set of strategies. We first compute the performance ratio tp,s rp,s = , min{tp,s : s ∈ S} where p ∈ P and tp,s is the solving time of strategy s for problem p. The percentage of problems that are solved within a factor τ ∈ R are computed in logarithmic scale by ρs (τ ) = |{p ∈ P : log2 (rp,s ) ≤ τ }| × 100%. |P| The percentage ρs of all problems solved by strategy s at τ gives us an overall assessment of the performance of strategy s. High values of ρs near τ = 1 represents fast solve times. High values of ρs when τ is large represents high success rates. Therefore, for a good algorithm, the plot of ρ(τ ) should be found above the other algorithms. For a more detailed description of performance profiles we refer the reader to [DM02]. 5.3 Experimental results for single material Out of the 60 test problems, 46 test problems contain blocks and 14 test problems are setup without blocks. Some of the test problems are created for stress testing. For example, Test 8 (see Table A.9) is created with 40 blocks in just 50 sections that cannot be solved by any strategies within time limits. In reality, almost all problems have at most 5 and extremely rarely 10 blocks. But we include harder problems with extreme conditions to learn the limit of the models. In Tables A.3 and A.4 the solution times required by solvers CPLEX and CBC, respectively, are listed for 18 different strategies for the 46 test problems with blocks. In Tables A.1 and A.2 the solution times are listed for the 14 test problems with no blocks for 6 different techniques (see Table 5.2) for both MIP solvers. 42 5.3. Experimental results for single material 5.3.1 Results for problems with blocks The performance profiles of 18 different strategies with solver CPLEX are shown in Figure 5.1. We have used MATLAB to draw the performance profiles. Note that when MATLAB plots vertical lines the value of the function ρs is equal to the largest values of the graph at that point. We see that the performances of Strategies NSB, NSN and NSS are very close to each other. These 3 strategies are all quasi network flow models with the SOS2 level technique and three different block techniques. These three strategies solved almost all of the problems in the problem set. Although Strategy NSB is better than the other two strategies, strategy NSN, which is the quasi network flow model with the SOS2 level technique and the n log n block technique, is very close. However, strategy NSN solves one problem less than strategy NSB. 1 QBB QBN QBS QNB QNN QNS QSB QSN QSS NBB NBN NBS NNB NNN NNS NSB NSN NSS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 2 4 6 log2(τ) 8 10 12 Figure 5.1: Performance profile for solver CPLEX (with blocks) Similarly, in the case of CBC, the performance profiles of 18 different strategies are shown in Figure 5.2. Strategy NSS, which is a quasi network flow model with the SOS2 level technique and the SOS1 block technique, outperforms all the other strategies. It solves almost 90% of the problem set. Strategy NSB comes next: it can also solve 90% of the problem set but 43 5.3. Experimental results for single material 1 QBB QBN QBS QNB QNN QNS QSB QSN QSS NBB NBN NBS NNB NNN NNS NSB NSN NSS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 7 8 9 10 log2(τ) Figure 5.2: Performance profile for solver CBC (with blocks) takes a little bit more time. From Figures 5.1 and 5.2, we observe that the quasi network flow model performs better than the quadratic model for both solvers for solving problems with blocks. However, for the block technique (Section 4.2.1 and 4.2.2), we see that the SOS1 technique works better than the other techniques for CBC, whereas the basic technique works well for CPLEX. In Figures 5.3, 5.4, 5.5, and 5.6 the performance profiles are shown with various techniques separately for the quadratic and quasi network flow models for each MIP solver. For CBC (Figures 5.4, 5.6), the SOS2 level technique and the SOS1 block technique work better than the other strategies by a slight margin. However, for CPLEX (Figures 5.3, 5.5), the SOS2 level technique combined with the basic block technique works better than other strategies. 44 5.3. Experimental results for single material 1 QBB QBN QBS QNB QNN QNS QSB QSN QSS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 7 8 9 log2(τ) Figure 5.3: Performance profile of different strategies of the quadratic model for solver CPLEX (with blocks) 1 QBB QBN QBS QNB QNN QNS QSB QSN QSS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 7 8 log2(τ) Figure 5.4: Performance profile of different strategies of the quadratic model for solver CBC (with blocks) 45 5.3. Experimental results for single material 1 NBB NBN NBS NNB NNN NNS NSB NSN NSS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 2 4 6 log2(τ) 8 10 Figure 5.5: Performance profile of different strategies of the quasi network flow model for solver CPLEX (with blocks) 1 NBB NBN NBS NNB NNN NNS NSB NSN NSS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 7 8 9 10 log2(τ) Figure 5.6: Performance profile of different strategies of the quasi network flow model for solver CBC (with blocks) 46 5.3. Experimental results for single material 5.3.2 Results for problems with no blocks For problems without blocks, the list of strategies is shown in Table 5.2. The run times for these 6 strategies in the case of both solvers are listed in Tables A.1 and A.2. The performance profiles for CPLEX and CBC for these 6 strategies are shown in Figures 5.7 and 5.8, respectively. From both performance profiles, we see that the SOS2 level technique makes a significant difference. Both quasi network flow and quadratic models with SOS2 can solve all of the problems, and as before, the quasi network flow model outperforms the quadratic model. Table 5.2: List of strategies for single material without blocks 5.3.3 Strategy Model Level Trick QB QN QS NB NN NS Quadratic Quadratic Quadratic Quasi network flow Quasi network flow Quasi network flow Basic Binary reduction SOS2 Basic Binary reduction SOS2 Summary of experimental result for single material The basic quadratic model (QBB) with the basic level and block techniques can solve 38% of the problem set with blocks using CPLEX and 20% using CBC. Using the quasi network flow model (NSB), with the SOS2 level technique and the basic block technique, we improve this to 95% for CPLEX and 88% for CBC. To compare the improvement in solution time, we consider the common problems that can be solved by all strategies. The improvement in solution time for the problems with blocks are listed below. − For the solver CPLEX, we found the following results. – The quadratic model with the basic level and block technique can solve 17 problems out of 46 test problems taking 1197 seconds. Whereas the quadratic model with the SOS2 level technique and the basic block technique can solve those 17 problems in 151 seconds. The improvement in speed is a factor of 8. 47 5.3. Experimental results for single material 1 QB QN QS NB NN NS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 2 4 6 8 10 12 log2(τ) Figure 5.7: Performance profile for solver CPLEX (without blocks) 1 QB QN QS NB NN NS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 2 4 6 log2(τ) 8 10 12 Figure 5.8: Performance profile for solver CBC (without blocks) 48 5.3. Experimental results for single material – The quasi network flow model with the basic level and block technique can solve 41 test problems taking 1755 seconds. Whereas the quasi network flow model with the SOS2 level technique and the basic block technique takes 175 seconds to solve those problems. In this case the improvement in speed is a factor of 10. – The improvement from the basic quadratic model to quasi network flow model introduced in [Rah12] with SOS2 level technique is a factor of 173. − For the solver CBC, we found the following results. – The basic strategy QBB (quadratic model with basic level and block technique) takes 785 seconds to solve 9 problems out of 46 problems. Whereas the Strategy QSB takes 50 seconds and Strategy QSS takes 205 seconds to solve those 9 problems. The performance improvement in solution time from QBB to QSB is a factor 16. – On the other hand, for the quasi network flow model, the basic strategy NBB takes 2128 seconds to solve 36 problems out of 46. Whereas the strategy NSS (quasi network flow with SOS2 level and SOS1 block technique) takes 623 seconds. The improvement is a factor of 3. The performance improvement from QBB to NSS is a factor of 142. For no blocks, the basic quadratic model (QB) with basic level technique can solve 42% of the problem set using CPLEX and 50% using CBC. Using both the quadratic (QS) and the quasi network flow model(NS) with SOS2 level technique, we improve this to 100% for both solvers. For problems without blocks, the performance improvement in solution time for different strategies are listed below. − The solution time is improved from basic quadratic model (QB) to quadratic model with SOS2 level technique (QS) by a factor of 244.2. − The solution time is improved from basic quasi network flow model (NB) to quasi network flow model with SOS2 level technique (NS) by a factor of 94.1. − The solution time is improved from basic quadratic model (QB) to quasi network flow model with SOS2 level technique (NS) by a factor of 1498.3. Similar results can be found for CBC. 49 5.3. Experimental results for single material The precedence of all techniques are shown in Tables 5.3, 5.4 for CPLEX and CBC respectively in terms of number of problems solved and solution speed. Although the performance of the quasi network flow model is better than the quadratic model, the quasi network flow model cannot have a non linear cost function with respect to hauling distance. The quadratic model is more flexible as it can handle a nonlinear cost function. Table 5.3: Precedence of techniques for CPLEX in terms of number of problems solved and solution speed. Precedence is decreasing from left to right in each row. CPLEX Model Quasi network flow Quadratic Level Technique SOS2 Basic Binary Reduction SOS2 Basic Binary Reduction Block Technique Basic SOS1 n log n Basic SOS1 n log n Table 5.4: Precedence of techniques for CBC in terms of number of problems solved and solution speed. Precedence is decreasing from left to right in each row. CBC Model Quasi network flow Quadratic Level Technique SOS2 Basic Binary Reduction SOS2 Basic Binary Reduction Block Technique SOS1 Basic n log n SOS1 Basic n log n 50 5.4. Experimental results for multimaterial 5.4 Experimental results for multimaterial In this section, we show the experimental results for the multimaterial vertical alignment optimization. We use the same 60 test problems that we have used for single material, but this time we consider four materials instead of one single material, and give ten minutes CPU time to solve a problem. We also use the same configuration for the computer and software (see Section 5.1). In multimaterial test cases, the volumes of materials are mostly nonconvex in nature with respect to the height of the offset levels. So we do not use the basic and binary reduction techniques for offset levels since they requires that the volumes are convex in nature. We apply only SOS2 techniques which can handle non-convex volumes with respect to heights. 5.4.1 Results for problems with blocks The strategies that we have used for numerical testing multimaterial models with blocks are listed in Table 5.5. In Table A.5 the solution times required by CPLEX are listed for the 46 test problems with blocks. CBC cannot solve any of the test problem of mulimaterial. Table 5.5: List of strategies without blocks for multimaterial test cases Strategy Model Level Technique Block Technique QSB QSN QSS NSB NSN NSS Quadratic Quadratic Quadratic Quasi network flow Quasi network flow Quasi network flow SOS2 SOS2 SOS2 SOS2 SOS2 SOS2 Basic n log n SOS1 Basic n log n SOS1 The performance profiles of these six strategies is shown in Figure 5.9. In this case we observe the same behavior that we have seen for single material. NSB and NSS solve almost all the problems from the test set, although NSB has better solution time. NSN solves 88 percent problem. Among the three quasi network flow strategies, NSB is the best in terms of solution speed and robustness. In the case of strategies with the quadratic model, the performance of the QSN and QSB are very close and significantly better than the other 51 5.4. Experimental results for multimaterial strategy QSS. Among the three strategy QSN is the best method in terms of number of problem solved. The reason for this kind of performance profile for the quadratic model is that the problems size grows very fast with the number of materials and blocks. Since QSN reduces the number of binary variables, the size of the problem is less than the other two strategies. Overall, the performance profile with blocks for multimaterial test is similar to the performance of single material. 1 QSB QSN QSS NSB NSN NSS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 1 2 3 4 log2(τ) 5 6 7 Figure 5.9: Performance profile for solver CPLEX for multi-material (with blocks) 5.4.2 Results for problems without blocks For the case of without blocks, we now have only two strategies that are listed in Table 5.2. The solution times required by CPLEX solver are listed in Table A.6 for the 14 test cases without blocks. The performance profile is shown in Figure 5.10. In this case, it is obvious that the quasi network flow strategy with SOS2 level technique is better than the quadratic strategy with SOS2. 52 5.4. Experimental results for multimaterial Table 5.6: List of strategies with blocks for multimaterial test cases Strategy Model Level Technique QS NS Quadratic Quasi network flow SOS2 SOS2 1 QS NS 0.9 0.8 0.7 ρs(log2(τ)) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 log2(τ) Figure 5.10: Performance profile for solver CPLEX for multi-material (without blocks) 53 5.4. Experimental results for multimaterial 5.4.3 Summary of results for mutlimaterial We observe almost the same behavior in performance for the multimaterial case as we have seen in single material in terms of number of problem solved. For the mutimaterial case, the problem size increases as the number of material increases. Solver CPLEX can cope with the increase of problem size, but solver CBC is not able to solve multimaterial problems. In the case of multimaterial, we have to consider nonconvexity in volume with respect to the height offset level. In general, all strategies with quasi network flow is significantly better than the strategies with quadratic model. In order to measure the performance in solution time explicitly, we consider the problems that are solved by both strategies. QSB can solve 27 problems with blocks out of 46 problems taking 3675 seconds in total. NSB takes 148 seconds for the same problem set. So performance increase in solution time is a factor of 25. Without block problems, the performance increase in solution time is 11 from QS to NS. This performance increase is caused mostly by the quasi network flow model, while SOS2 techniques help to increase performance for both models and accommodate the nonconvexity relation between volume and offset level. 54 Chapter 6 Conclusion We started this thesis with the practical requirements that need to be considered for vertical alignment design in Chapter 1. We also discussed the shortcomings of previous research works. We developed two models based on the previous works of [Mor09], [HKL11], [Rah12]. The quadratic and quasi network flow models are an enhancement of the previous work done in [Rah12] and are described in Chapters 2 and 3. These two models are capable of considering all requirements for optimal design of the vertical alignment. Both models incorporate features such as multimaterial, sides slopes and physical blocks. We further introduced six potential techniques to improve the solution speed that are applicable for both models in Chapter 4. Numerical tests shows that using the best combination of techniques can consistantly generate major improvements in solution time, regardless of which LP solver is used. For example, the quasi network flow model introduced in [Rah12] and further improved by the best speed techniques discussed in this research improves solution speed from the basic quadratic model by a factor of 173. The techniques developed in this research have made it possible to solve a vertical alignment design for a very long road within a reasonable amount of time. Using these improvement techniques, our industry partner (Softree Technical Systems Inc.) has developed an interactive road design software. 6.1 6.1.1 Future research Improvement in the quasi network flow model The quasi network flow model has a limitation in the structure of its cost function. The hauling cost is linear with distance traveled by the volume of materials. In practice, for hauling materials, it may be enough to consider only two kinds of haul such as short haul and long haul. Short haul refers to moving material in short distance. Long haul refers to moving materials in long distance using big trucks. There could be a fixed cost for loading materials in long haul which is much higher than hauling materials in short 55 6.1. Future research distance. However, once the materials are put in a large truck, a long traveling distance does not increase the cost significantly. To accommodate these two hauls in our quasi network flow model, we can define another pair of East and West transit flow. Then with appropriate cost values set for the short and long haul it is probably possible to have a nonlinear cost function. 6.1.2 More options for selecting material In our existing models, we cut and fill various sections of roads with the materials according to the given input volume tables (Table 2.1). We assume that materials are not replaceable by any other type of materials. But it can be modeled and implemented to have the alternate material options. However, it will increase the size of the problem, as we have to define all possible movement variables as xijt,m1 m2 , where m1 and m2 are the alternate materials pair such that low quality material m1 is replaceable with high quality material m2 . 6.1.3 Horizontal alignment The ultimate goal of automating the road design process is to calculate the horizontal alignment while considering the sub problem of vertical alignment. First, road engineers select a corridor for building a road using the topographical analysis of the ground profile. After fixing a corridor, road engineers select a route for the horizontal alignment within that corridor minimizing the cost while satisfying the safety, other design constraints, and considering other socioeconomic impacts. While computing the horizontal alignment, the cost is heavily dependent on the cost of the vertical alignment. Certainly, during the horizontal alignment optimization, our research will help to find the optimal solution. 56 Bibliography [AAS04] AASHTO, editor. A policy on geometric design of highways and streets. AASHTO, 5 edition, 2004. → pages 2, 8 [ACRV13] E. Angulo, W. Castillo, R. G. Rdenas, and J. S. Vizcano. A continuous bi-level model for the expansion of highway networks. Computers & Operations Research, 2013. → pages 2 [Aka06] A. Akay. Minimizing total costs of forest roads with computeraided design model. Sadhana, 31:621–633, 2006. → pages 7 [AMO93] R. K. Ahuja, T. L. Magnanti, and J. B. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993. → pages 6, 23 [Aru05] K. Aruga. Tabu search optimization of horizontal and vertical alignments of forest roads. Journal of Forest Research, 10:275– 284, 2005. → pages 7 [ATSM06] K. Aruga, T. Tasaka, J. Sessions, and S. Miyata. Tabu search optimization of forest road alignments combined with shortest paths and cubic splines. Croatian Journal of Forest Engineering, 27:37– 47, 2006. → pages 7 [CGF89] E. P. Chew, C. J. Goh, and T. F. Fwa. Simultaneous optimization of horizontal and vertical alignments for highways. Transportation Research Part B: Methodological, 23(5):315–329, 1989. → pages 6 [CL06] J. F. Cheng and Y. Lee. Model for three-dimensional highway alignment. Journal of Transportation Engineering, 132(12):913– 920, 2006. → pages 7 [CMW98] R. L. Church, A. T. Murray, and A. Weintraub. Locational issues in forest management. Location Science, 6(14):137 – 153, 1998. → pages 2 57 Bibliography [DJ09] C. Davis and M. K. Jha. Modeling the effects of socioeconomic factors in highway construction and expansion. Journal of Transportation Engineering, 135(12):990–998, 2009. → pages 1 [DM02] E. D. Dolan and J. J. Mor´e. Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2):201– 213, 2002. → pages 42 [Eas88] S. M. Easa. Selection of roadway grades that minimize earthwork cost using linear programming. Transportation Research Part A: General, 22(2):121 – 136, 1988. → pages 4, 5 [FCS02] T. F. Fwa, W. T. Chan, and Y. P. Sim. Optimal vertical alignment analysis for highway design. Journal of Transportation Engineering, 128(5):395–402, 2002. → pages 4 [GAA09] A. B. G¨ oktepe, S. Altun, and P. Ahmedzade. Optimization of vertical alignment of highways utilizing discrete dynamic programming and weighted ground line. Turkish Journal Of Engineering & Environmental Sciences, 10:105–116, 2009. → pages 4, 5 [GCF88] C. J. Goh, E. P. Chew, and T. F. Fwa. Discrete and continuous models for computation of optimal vertical highway alignment. Transportation Research Part B: Methodological, 22(6):399 – 409, 1988. → pages 4, 5 [GLA05] A. B. Goktepe, A. H. Lav, and S. Altun. Dynamic optimization algorithm for vertical alignment of highways. Mathematical and Computational Applications, 10(3):341–350, 2005. → pages 4, 5, 7 [GLA09] A. B. Goktepe, A. H. Lav, and S. Altun. Method for optimal vertical alignment of highways. Proceedings of The Institution of Civil Engineers-transport, 162(4):177–188, December 2009. → pages 4 [HBS68] B. E. Howard, Z. Bramnick, and J. F. Shaw. Optimum curvature principle in highway routing. Journal of the Highway Division, 94:61–82, 1968. → pages 3 [HHLR13] W. L. Hare, S. Hossain, Y. Lucet, and F. Rahman. Models and strategies for efficiently determining an optimal vertical alignment of roads. Technical report, Under submission, 2013. → pages iii 58 Bibliography [HKL11] W. L. Hare, V. R. Koch, and Y. Lucet. Models and algorithms to improve earthwork operations in road design using mixed integer linear programming. European Journal of Operational Research, 215(2):470 – 480, 2011. → pages 2, 4, 6, 8, 15, 55 [HLR13] W. Hare, Y. Lucet, and F. Rahman. A mixed-integer linear programming model to optimize the vertical alignment considering blocks and side-slopes in road construction. under submission. Technical report, Under submission, 2013. → pages 6 [Jha03] M. K. Jha. Criteria-based decision support system for selecting highway alignments. Journal of Transportation Engineering, 129(1):33–41, 2003. → pages 1 [JS03] J. C. Jong and P. Schonfeld. An evolutionary model for simultaneously optimizing three-dimensional highway alignments. Transportation Research Part B: Methodological, 37(2):107 – 128, 2003. → pages 2 [JSJ06] M. K. Jha, P. Schonfeld, and J. C. Jong. Intelligent Road Design, volume 19. WIT Press, 2006. → pages 2, 3, 4, 5 [KdFJN04] A. B. Keha, I. R. de Farias Jr., and G. L. Nemhauser. Models for representing piecewise linear cost functions. Operations Research Letters, 32(1):44 – 48, 2004. → pages 33 [KdFN06] A. B. Keha, I. R. de Farias, and G. L. Nemhauser. A branch-andcut algorithm without binary variables for nonconvex piecewise linear optimization. Operations Research, 54(5):847–858, September 2006. → pages 33 [KL10] V. R. Koch and Y. Lucet. A note on: Spline technique for modeling roadway profile to minimize earthwork cost. Journal of Industrial and Management Optimization, 6(2):393 – 400, May 2010. → pages 4, 6, 8, 10 [KSJ07] M. W. Kang, P. Schonfeld, and J. C. Jong. Highway alignment optimization through feasible gates. Journal of Advanced Transportation, 41(2):115–144, 2007. → pages 2 [LC01] Y. S. Lee and J. F. Cheng. . Journal of Transportation Engineering-ASCE, 127(4):303–310, Jul-Aug 2001. → pages 4 59 Bibliography [LV92] M.G. Lay and J.E. Vance. Ways of the World: A History of the World’s Roads and of the Vehicles That Used Them. RUTGERS University Press, 1992. → pages [MA04] A. A. Moreb and M. S. Aljohani. Quadratic representation for roadway profile that minimizes earthwork cost. Journal of Systems Science and Systems Engineering, 13(2):245–252, April 2004. → pages 4, 5, 10 [Min12a] Minister of Public Works and Government Services. Transportation in canada 2011 - comprehensive review. Transport Canada, Cat. No. T1-23A/2011E-PDF:15, 2012. → pages 1 [Min12b] Ministry of Transportation and Infrastructure. Construction and rehabilitation cost guide, July 2012. → pages 1 [MMM06] A. Martin, M. Mller, and S. Moritz. Mixed integer models for the stationary case of gas network optimization. Mathematical Programming, 105:563–582, 2006. → pages 33 [Mor96] A. A. Moreb. Linear programming model for finding optimal roadway grades that minimize earthwork cost. European Journal of Operational Research, 93(1):148 – 154, 1996. → pages 4, 5 [Mor09] A. A. Moreb. Spline technique for modeling roadway profile to minimize earthwork cost. Journal of Industrial and Management Optimization (JIMO), 5(2):275–283, 2009. → pages 2, 4, 5, 6, 8, 10, 55 [OEC73] OECD. Optimisation of road alignment by the use of computers. Technical report, Organization of Economic Co-operation and Development, Paris, 1973. → pages 4 [Rah12] F. Rahman. Optimizing the vertical alignment under earthwork block removal constraints in road construction. Master’s thesis, UBC, 2012. → pages 6, 8, 16, 23, 49, 55 [SH81] J. F. B. Shaw and B. E. Howard. Comparison of two integration methods in transportation routing. Transportation Research Record, 806:8–13, 1981. → pages 3 [SH82] J. F. B. Shaw and B. E. Howard. Expressway route optimization by ocp. Transportation Engineering Journal, 108:227–243, 1982. → pages 3 60 Bibliography [TM70] A.K. Turner and R. D. Miles. The GCARS system: a computerassisted method of regional route location. Technical Report FHWA/IN/JHRP-70/27, Purdue University, Joint Highway Research Project, 1970. → pages 4 [Tom81] J. A. Tomlin. A suggested extension of special ordered sets to nonseparable non-convex programming problems. Studies on Graphs and Discrete Programming, 11:359–370, 1981. → pages 33 [Tri87a] D. Trietsch. Comprehensive design of highway networks. Transportation Science, 21(1):26–35, 1987. → pages 4 [Tri87b] D. Trietsch. A family of methods for preliminary highway alignment. Transportation Science, 21(1):17–25, February 1987. → pages 4 [TT03] C. W. Tat and F. Tao. Using gis and genetic algorithm in highway alignment optimization. In Intelligent Transportation Systems, 2003. Proceedings. 2003 IEEE, volume 2, pages 1563 – 1567 vol.2, oct. 2003. → pages 7 [Tur78] A. K. Turner. A decade of experience in computer aided route selection. Photogrammetric Engineering and Remote Sensing, 44:1561–1576, 1978. → pages 4 [Wan95] F. Y. M. Wan. Introduction to the calculus of variations and its applications. Chapman & Hall, 1995. → pages 3 61 Appendix 62 Appendix A Tables Table A.1: Solution times for CPLEX with 6 strategies for 14 test problems without blocks Test # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 QB QN QS NB NN NS 1.485 1.134 NaN 31.377 NaN 74.593 NaN NaN 199.839 NaN NaN NaN NaN 156.044 NaN NaN NaN 136.647 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 0.032 0.027 0.028 0.06 0.065 0.128 0.122 0.125 0.176 0.155 1.605 1.312 1.322 1.479 1.181 1.119 0.647 1.005 1.474 2.514 3.144 4.97 5.671 4.062 18.932 22.998 12.813 10.17 NaN NaN NaN 203.027 NaN NaN NaN NaN NaN NaN NaN NaN NaN 86.527 0.021 0.018 0.023 0.031 0.035 0.046 0.05 0.044 0.056 0.047 0.147 0.189 0.119 0.138 63 Appendix A. Tables Table A.2: Solution times for CBC with 6 strategies for 14 test problems without blocks Test # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 QB QN QS NB NN NS 45.716 15.417 31.591 12.985 35.614 NaN NaN NaN 160.272 48.029 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 0.057 0.034 0.047 0.214 0.181 0.359 0.281 0.333 0.602 0.541 5.05 4.999 5.392 5.32 101.07 38.33 55.593 36.97 23.706 NaN 112.62 45.162 15.58 9.091 NaN NaN 161.062 8.943 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 89.347 0.04 0.03 0.043 0.084 0.091 0.115 0.123 0.149 0.192 0.164 0.664 0.8 0.61 0.564 64 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 Test # QBN QBS QNB QNN QNS QSB QSN 1.45 3.14 2.45 11.69 16.11 10.95 0.27 0.28 3.03 3.46 3.57 70.85 133.41 123.73 0.40 0.38 9.55 26.27 24.89 NaN NaN NaN 1.46 1.43 NaN NaN NaN NaN NaN NaN 20.88 34.66 43.44 23.92 49.00 NaN NaN NaN 2.53 2.42 54.05 43.39 127.68 NaN NaN NaN 4.05 3.29 89.68 175.70 NaN NaN NaN NaN 14.19 12.39 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 28.58 20.61 111.67 NaN NaN NaN NaN NaN 16.52 6.47 NaN NaN NaN NaN NaN NaN 50.46 78.99 NaN NaN NaN NaN NaN NaN 78.59 114.20 57.78 56.80 92.90 NaN NaN NaN 4.54 4.12 43.98 92.03 51.95 NaN NaN NaN 1.15 1.19 60.40 NaN NaN NaN NaN NaN 12.46 11.75 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 33.28 28.50 NaN NaN NaN NaN NaN NaN 115.21 101.36 231.87 NaN NaN NaN NaN NaN 47.39 43.10 NaN NaN NaN NaN NaN NaN 122.71 89.45 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 150.65 NaN NaN NaN NaN NaN 25.07 22.78 27.61 56.59 110.77 NaN NaN NaN 3.76 3.18 NaN NaN NaN NaN NaN NaN 14.62 10.13 NaN NaN NaN NaN NaN NaN 109.03 NaN 109.58 182.50 NaN NaN NaN NaN 6.57 6.12 NaN NaN NaN NaN NaN NaN 10.33 6.37 70.76 41.68 99.71 NaN NaN NaN 2.25 1.92 NaN NaN NaN NaN NaN NaN 40.41 27.70 54.89 127.81 70.25 NaN NaN NaN 6.99 6.77 NaN NaN NaN NaN NaN NaN 54.91 45.04 NaN NaN NaN NaN NaN NaN 36.86 21.53 NaN NaN NaN NaN NaN NaN 51.57 36.25 NaN NaN NaN NaN NaN NaN 65.12 40.16 NaN NaN NaN NaN NaN NaN 186.31 209.07 NaN NaN NaN NaN NaN NaN 212.62 NaN 76.63 76.14 71.28 NaN NaN NaN 1.44 0.59 NaN NaN NaN NaN NaN NaN 49.95 34.84 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN QBB 1.23 1.60 9.06 223.09 18.64 42.56 102.07 NaN 114.49 75.03 NaN NaN 23.42 6.17 191.66 NaN 132.78 NaN NaN NaN NaN NaN NaN 50.44 NaN NaN 68.05 200.25 24.03 NaN 33.75 NaN NaN NaN NaN NaN NaN 0.50 NaN NaN NaN NaN NaN NaN NaN NaN QSS 0.70 1.62 2.26 8.91 3.48 4.53 17.15 NaN 25.56 39.76 40.62 77.60 7.96 15.62 11.28 NaN 34.84 16.40 14.62 21.00 70.54 210.73 7.82 2.20 13.57 58.77 29.95 39.88 35.54 198.18 28.95 19.65 21.19 33.64 15.32 136.10 50.16 9.66 18.57 NaN 170.95 NaN 133.79 NaN 95.16 10.64 NBB NBS NNB NNN NNS NSB NSN NSS 0.97 0.94 4.28 12.23 4.77 0.05 0.05 0.08 1.56 1.40 11.50 19.18 9.02 0.05 0.05 0.06 2.28 1.92 33.45 63.37 52.82 0.11 0.10 0.16 14.00 52.68 102.79 NaN 207.15 0.37 0.43 0.75 2.28 4.13 83.02 78.67 240.34 0.18 0.17 0.42 8.71 4.98 48.24 64.71 41.54 0.16 0.30 0.36 25.66 52.08 NaN NaN NaN 1.41 6.28 10.40 NaN NaN NaN NaN NaN NaN NaN NaN 17.55 49.82 NaN NaN NaN 1.43 1.34 2.74 15.58 21.86 NaN NaN NaN 0.95 0.78 0.90 46.36 27.03 NaN NaN NaN 1.34 1.18 1.18 58.30 164.51 NaN NaN NaN 3.84 4.55 1.10 7.49 13.95 39.06 NaN 91.41 0.30 0.38 0.36 13.07 14.79 NaN 34.16 130.92 0.28 0.11 0.12 22.65 23.36 NaN NaN NaN 0.52 0.42 0.81 NaN NaN NaN NaN NaN NaN NaN NaN 18.33 34.44 NaN NaN NaN 2.12 1.93 2.17 22.56 28.85 NaN NaN NaN 2.87 4.89 5.68 24.40 13.07 NaN 203.81 NaN 1.36 1.33 1.37 16.15 65.18 NaN NaN NaN 1.60 1.70 6.48 100.87 206.28 NaN NaN NaN 23.45 14.16 11.26 NaN NaN NaN NaN NaN 91.53 225.44 131.60 30.89 18.62 NaN NaN NaN 0.36 0.38 1.09 3.46 3.60 15.62 33.19 37.86 0.13 0.13 0.13 15.09 45.34 NaN NaN NaN 0.22 0.22 0.41 231.60 220.83 NaN NaN NaN 0.75 0.77 2.48 26.31 40.93 NaN NaN NaN 0.16 0.24 0.20 60.48 62.07 NaN NaN NaN 0.20 0.17 0.19 25.09 35.96 NaN NaN NaN 0.11 0.11 0.20 20.70 11.30 NaN NaN NaN 0.44 0.64 0.62 11.31 11.08 NaN NaN NaN 0.16 0.14 0.17 19.08 27.24 NaN NaN NaN 0.33 0.34 1.10 26.75 26.01 NaN NaN NaN 0.28 0.29 0.45 21.29 44.98 NaN NaN NaN 0.64 0.58 2.80 17.66 20.64 NaN NaN NaN 0.48 0.41 0.58 50.84 165.77 NaN NaN NaN 1.42 1.54 5.24 155.81 22.39 NaN NaN NaN 2.59 2.50 2.01 9.27 9.16 NaN NaN NaN 0.66 0.11 0.53 24.80 27.78 NaN NaN NaN 0.36 0.45 0.76 NaN NaN NaN NaN NaN 7.39 NaN 135.91 NaN NaN NaN NaN NaN 24.57 22.40 107.02 216.44 NaN NaN NaN NaN 5.66 7.47 5.07 65.11 228.36 NaN NaN NaN 4.01 5.28 4.68 NaN NaN NaN NaN NaN 2.75 3.74 5.73 144.01 104.32 NaN NaN NaN 2.36 2.11 2.73 12.03 13.62 49.16 69.87 49.84 1.23 1.42 2.01 NBN Table A.3: Solution time for CPLEX with 18 strategies for 48 test problems with blocks Appendix A. Tables 65 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 Test # QBN QBS 7.94 14.92 12.48 84.62 29.96 30.63 106.41 89.66 108.05 NaN NaN NaN NaN NaN NaN 86.93 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 167.28 NaN 31.92 59.55 30.01 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 144.72 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 125.53 129.79 114.93 NaN NaN NaN 137.33 134.24 178.72 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 59.80 94.50 81.45 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN QBB NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN QNB NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN QNN QSB QSN QSS NaN 1.78 5.44 0.53 NaN 0.49 127.72 1.00 NaN 25.03 NaN 7.28 NaN 199.37 NaN 191.11 NaN 162.16 NaN 17.63 NaN 5.75 NaN 153.05 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 89.99 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 12.29 NaN 22.33 NaN 1.33 38.83 1.53 NaN NaN NaN NaN NaN NaN NaN NaN NaN 17.16 NaN 11.57 NaN NaN NaN NaN NaN 25.78 NaN 55.81 NaN 175.26 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 32.30 NaN 26.36 NaN 4.49 NaN 9.16 NaN NaN NaN 112.01 NaN NaN NaN NaN NaN 24.09 NaN 21.63 NaN 41.81 NaN 8.86 NaN 4.34 NaN 4.40 NaN NaN NaN NaN NaN 5.34 NaN 5.97 NaN 35.37 NaN 58.96 NaN NaN NaN 99.76 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 1.78 1.65 1.77 NaN NaN NaN 93.20 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN QNS 3.22 21.67 45.20 102.06 27.07 15.15 NaN NaN 74.79 44.77 100.17 55.86 14.79 40.16 92.78 NaN 107.00 113.88 139.14 NaN NaN NaN 46.26 8.78 56.22 102.68 37.81 18.80 23.74 114.71 34.70 44.59 29.52 216.00 65.16 122.57 147.59 11.87 20.81 NaN NaN NaN NaN NaN NaN 28.65 NBB 4.95 6.74 58.22 207.69 86.68 91.81 NaN NaN NaN 21.55 184.09 231.40 11.78 8.86 172.95 NaN 78.94 NaN 144.08 NaN NaN NaN 192.51 5.43 76.39 NaN 13.90 107.69 17.82 117.30 17.44 67.66 19.02 160.99 149.84 NaN NaN 17.77 120.71 NaN NaN NaN NaN NaN NaN 31.34 NBN NNB NNN NNS NSB NSN NSS 4.57 NaN NaN NaN 0.47 1.61 0.17 3.85 NaN NaN 217.71 0.29 10.10 0.25 4.96 NaN NaN NaN 3.70 19.47 1.99 40.13 NaN NaN NaN 20.91 NaN 2.94 59.04 NaN NaN NaN 7.68 27.18 3.84 19.47 NaN NaN NaN 1.26 21.18 0.69 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 50.99 NaN NaN NaN 22.06 24.67 38.00 28.32 NaN NaN NaN 2.32 18.69 9.74 149.99 NaN NaN NaN 36.60 59.15 22.68 87.56 NaN NaN NaN 80.08 NaN 27.12 15.24 NaN NaN NaN 2.28 9.18 1.83 47.30 NaN NaN NaN 0.74 0.70 0.36 19.83 NaN NaN NaN 26.32 30.48 24.78 NaN NaN NaN NaN NaN NaN NaN 106.88 NaN NaN NaN 1.71 32.75 0.99 NaN NaN NaN NaN 62.15 94.80 153.02 36.36 NaN NaN NaN 3.61 62.36 1.07 121.82 NaN NaN NaN 7.34 58.31 57.15 NaN NaN NaN NaN 222.24 NaN 10.72 NaN NaN NaN NaN NaN NaN NaN 86.85 NaN NaN NaN 2.78 49.74 2.46 27.27 228.01 151.99 NaN 0.59 6.39 0.67 52.62 NaN NaN NaN 17.29 37.68 5.51 89.12 NaN NaN NaN 97.88 96.15 93.68 33.54 NaN NaN NaN 1.81 11.62 1.84 22.53 NaN NaN NaN 0.84 10.58 0.89 25.01 NaN NaN NaN 0.47 1.66 0.43 25.19 NaN NaN NaN 28.48 45.83 11.26 16.66 NaN NaN NaN 0.50 0.50 0.45 41.11 NaN NaN NaN 2.64 65.39 3.54 37.11 NaN NaN NaN 14.04 23.46 7.82 135.16 NaN NaN NaN 14.73 86.14 27.83 80.59 NaN NaN NaN 27.01 56.27 9.78 NaN NaN NaN NaN 80.26 134.80 96.22 230.79 NaN NaN NaN 110.57 NaN 60.43 13.85 NaN NaN NaN 1.53 0.44 0.53 50.20 NaN NaN 157.72 20.95 35.08 5.34 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN 127.43 NaN NaN NaN 208.73 NaN 111.51 NaN NaN NaN NaN 101.28 195.48 91.70 NaN NaN NaN NaN 92.31 221.35 21.92 211.04 NaN NaN NaN 15.44 116.83 8.25 28.30 47.49 201.13 163.63 5.12 45.18 4.43 NBS Table A.4: Solution time for CBC with 18 strategies for 48 test problems with blocks Appendix A. Tables 66 Appendix A. Tables Table A.5: Solution time for CPLEX with 6 strategies for 48 test problems with blocks for multimaterial Test # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 QSB 1.611 1.733 11.101 144.51 15.376 NaN NaN NaN 32.174 16.287 208.916 509.851 10.091 8.547 77.049 NaN 21.439 318.855 NaN 265.369 NaN NaN 197.132 8.105 90.885 NaN 37.006 38.6 13.463 223.456 80.338 168.785 237.192 NaN QSN 2.551 1.729 12.924 187.665 15.218 175.466 NaN NaN 98.9 16.69 214.335 577.067 9.078 2.881 47.665 NaN 31.844 370.849 430.451 330.761 NaN NaN 220.926 6.591 126.161 NaN 52.907 88.74 13.805 282.791 108.861 162.139 278.53 NaN QSS 2.658 3.252 27.801 NaN 43.646 NaN NaN NaN 135.887 86.277 NaN NaN 29.145 8.911 238.032 NaN 143.385 NaN NaN NaN NaN NaN 596.321 61.082 469.719 NaN 106.244 240.214 36.571 NaN 106.847 565.35 NaN NaN NSB NSN NSS 0.54 0.491 0.641 0.315 0.37 0.476 1.166 1.15 1.82 7.579 21.74 10.832 1.449 1.412 2.73 7.028 5.507 6.925 42.762 NaN 113.876 125.299 NaN 241.943 3.771 3.05 11.003 1.269 1.085 1.674 4.24 6.295 4.961 5.358 10.068 6.342 0.909 0.993 1.637 0.506 0.403 0.62 2.523 3.176 3.601 19.82 202.195 17.395 1.988 1.79 2.249 20.114 29.77 45.046 4.022 6.429 5.086 18.988 25.7 60.412 28.216 40.785 45.003 26.515 92.717 74.644 12.628 19.769 32.604 0.992 0.855 0.779 3.972 4.225 6.601 23.249 46.813 37.171 3.054 2.324 3.749 2.301 2.148 2.583 1.842 1.853 2.149 4.706 6.533 5.817 7.014 7.347 10.067 10.863 11.766 18.709 7.697 9.289 11.594 20.627 19.715 54.811 Continued on next page 67 Appendix A. Tables Table A.5 – continued from previous page Test # QSB QSN QSS NSB NSN 35 248.307 418.303 NaN 7.933 9.46 36 NaN NaN NaN 34.481 44.471 37 NaN NaN NaN 25.11 54.156 38 17.273 17.247 17.38 2.749 2.817 39 100.066 130.871 NaN 3.013 4.826 40 NaN NaN NaN NaN NaN 41 NaN NaN NaN 304.881 NaN 42 NaN NaN NaN 62.56 391.583 43 NaN NaN NaN 74.586 135.362 44 NaN NaN NaN NaN NaN 45 NaN NaN NaN 28.381 36.46 46 572.097 NaN NaN 8.617 8.713 NSS 9.372 96.462 33.075 2.827 7.016 NaN 511.828 84.689 100.502 NaN 35.489 12.912 Table A.6: Solution time for CPLEX with two strategies for 16 test problems without blocks for multimaterial Test # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 QS 0.307 0.685 9.62 0.686 2.63 9.117 25.994 17.785 65.313 16.316 NaN NaN 270.647 44.071 NS 0.16 0.271 4.192 0.301 1.78 1.454 3.433 3.108 7.668 2.54 NaN NaN 15.958 1.401 68 Appendix A. Tables Table A.7: Test road configuration Road Section Length Section Count Size in kilometre A B C D E F G 20 100 20 20 100 100 20 50 50 100 150 150 200 450 1 5 2 3 15 20 9 69 Appendix A. Tables Table A.8: Test configuration of 60 test problems in terms of number of access roads, blocks, and offset levels Test # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 Road A A A A A B B B C C C C C C C C C D D D D D D D E E E E E E F F F F Access Rd 1 2 5 20 4 10 4 8 2 3 13 17 1 2 4 20 5 3 9 2 25 5 3 4 7 10 2 6 1 10 1 2 4 2 Blocks Offset Levels 3 10 5 10 10 10 25 10 12 10 15 10 20 10 40 10 7 10 8 10 19 10 22 10 5 10 3 10 12 10 30 10 10 16 12 10 10 10 7 10 30 10 20 10 8 10 5 6 9 10 21 10 5 10 8 10 3 10 15 10 2 10 5 10 8 10 10 10 Continued on next page 70 Appendix A. Tables Table A.8 – continued from previous page Test # Road Access Rd Blocks Offset Levels 35 F 8 12 10 36 F 5 15 10 37 F 10 20 10 38 F 1 1 10 39 F 4 7 6 40 G 25 40 20 41 G 15 30 10 42 G 20 22 10 43 G 10 15 10 44 G 5 10 20 45 G 7 9 10 46 G 3 4 4 47 A 10 0 40 48 A 1 0 30 49 B 1 0 40 50 C 1 0 16 51 C 1 0 24 52 D 1 0 16 53 D 1 0 22 54 E 1 0 24 55 F 1 0 16 56 F 1 0 10 57 G 1 0 16 58 G 1 0 30 59 G 1 0 10 60 G 1 0 4 71 Road A A A A A B B B C C C C C C C C C D D D D D D D E E E E E E F F F F F F F F F G G G G G G G A A B C C D D E F F G G G G Test # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 16 10 10 10 10 10 10 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 6 20 10 10 10 20 10 4 40 30 40 16 24 16 22 24 16 10 16 30 10 4 Offset Levels 1 15;40 1;10;19;30;50 1;3;5;7;9;11;15;17;20;23;26;29;33;35;38;41;43;46;48;50 15;30;40;50 1;5;10;15;20;25;30;35;40;50 1;25;30;50 4;10;15;21;28;36;42;48 1;100 30;50;80 1;10;20;25;30;40;45;50;60;70;80;90;100 1;7;14;20;25;30;35;44;50;55;60;66;70;75;80;90;100 50 20;50 10;30;50;80 1;5;10;15;20;25;30;35;45;50;55;60;65;70;75;80;85;90;95;100 5;25;45;65;80 20;80;130 1;10;25;35;45;55;89;97;123 1;150 1;10;15;20;25;30;35;40;50;55;60;70;75;80;85;90;100;105;110;120;125;130;135;140;150 20;40;70;100;120 1;80;150 10;40;90;130 1;20;30;50;70;90;120 1;25;35;45;55;65;75;95;125;135 30;90 20;50;90;120;130;150 50 1;30;45;60;70;88;101;123;130;150 1 1;200 1;50;100;150 50;100 1;24;44;58;77;98;120;150 1;50;90;140;200 10;20;40;60;80;100;120;140;160;180 1 1;50;130;200 1;13;20;33;40;55;66;77;90;100;120;130;150;160;190;220;240;260;280;290;300;330;340;350;360 1;30;70;100;130;150;170;200;230;250;270;290;330;350;370 10;25;40;55;70;85;100;115;140;155;165;175;190;220;250;280;300;330;360;380 1;30;60;90;130;160;190;250;300;350 50;100;150;250;330 1;50;90;130;160;260;350 1;100;300 1;5;10;15;20;30;35;40;45;50 1 1 1 1 1 1 1 1 1 1 1 1 1 Access Roads 10;25;37 10;20;30;43;45 2;3;7;13;17;24;25;40;41;45 2;4;6;8;10;12;13;14;16;18;19;21;22;24;27;28;30;31;32;36;40;42;44;47;49 4;5;9;10;20;21;22;23;24;35;45;46 2;3;7;13;18;23;28;33;34;38;43;44;45;46;49 4;5;6;9;12;14;15;16;19;20;21;26;27;33;34;38;40;45;46;47 1;2;3;5;6;7;8;9;11;12;13;14;16;17;18;19;20;22;23;24;25;26;27;29;30;31;32;33;34;35;37;39;40;41;43;44;45;46;47;49 20;30;40;41;55;60;70 20;25;40;60;61;70;85;90; 5;6;14;15;22;27;33;34;35;43;48;55;56;65;68;73;75;85;96 4;5;10;11;16;22;23;27;33;38;40;41;48;53;58;64;68;73;78;81;82;94 10;20;30;60;70 10;30;60 5;6;17;25;35;40;45;55;60;85;90;95 2;3;7;8;12;17;23;28;33;36;40;41;42;48;53;54;58;62;63;67;72;73;77;78;83;84;88;92;97;98 2;10;15;20;30;31;35;50;70;90 10;30;35;40;50;60;70;90;100;110;140;145 7;15;30;39;51;60;70;93;109;120 20;40;50;55;80;100;120 5;6;7;12;17;23;27;34;42;48;53;58;66;67;68;73;78;83;88;93;94;102;107;113;114;123;127;133;137;145 5;6;10;15;25;30;34;36;45;55;60;80;85;90;95;110;115;125;130;140 10;15;20;30;50;90;100;130 5;20;60;100;140 10;25;40;41;80;100;130;131;140 5;10;15;30;40;43;50;60;70;71;80;81;85;90;100;105;115;130;131;140;141 10;40;50;70;120 10;25;26;27;70;100;125;140 20;40;100 10;11;20;40;51;65;78;92;109;110;128;140;141;142;143 50;100 10;20;40;60;100 10;20;70;80;120;129;140;160 10;20;21;22;23;30;31;60;90;130 9;10;11;30;32;50;60;80;100;130;140;170 10;20;30;60;70;88;101;120;121;122;130;150;170;189;182 5;15;30;31;32;50;55;70;71;90;110;130;131;149;150;170;172;189;190;191 100 30;70;90;100;120;150;180 7;8;9;16;25;35;50;60;61;70;84;88;95;96;105;110;115;125;135;140;144;155;165;170;180;185;200;210;230;250;270;285;295;310;320;335;345;355;370;380 10;15;20;40;45;55;60;61;62;80;110;120;140;160;180;185;190;198;211;220;225;245;265;280;300;310;320;340;360;380 4;5;15;30;50;60;65;75;90;105;125;150;160;170;200;210;240;270;290;310;340;370 10;15;20;50;80;110;150;170;220;230;240;280;290;330;380 10;20;70;120;130;170;200;300;310;350 10;30;70;100;120;150;200;290;380 50;120;150;200;330 X X X X X X X X X X X X X X Blocks Table A.9: Test configuration for 60 test problems with patterns of blocks and access roads associated with sections Appendix A. Tables 72 X 392201.6 392201.6 392201.6 392201.6 392201.6 392201.6 392201.6 392201.6 392201.6 392201.6 392201.6 392203.3 392203.3 392203.3 392203.3 392203.3 392203.3 392203.3 392203.3 392203.3 392203.3 392203.3 . . . Station 0 0 0 0 0 0 0 0 0 0 0 20 20 20 20 20 20 20 20 20 20 20 . . . Y 6983092 6983092 6983092 6983092 6983092 6983092 6983092 6983092 6983092 6983092 6983092 6983112 6983112 6983112 6983112 6983112 6983112 6983112 6983112 6983112 6983112 6983112 . . . h 311.88 311.88 311.88 311.88 311.88 311.88 311.88 311.88 311.88 311.88 311.88 313.24 313.24 313.24 313.24 313.24 313.24 313.24 313.24 313.24 313.24 313.24 . . . Offset -10 -8 -6 -4 -2 0 2 4 6 8 10 -10 -8 -6 -4 -2 0 2 4 6 8 10 . . . 11.48 10.48 9.48 8.48 7.48 0 0 0 0 0 0 11.48 10.48 9.48 8.48 7.48 0 0 0 0 0 0 . . . 0 0 0 0 0 0 -32.4 -76.8 -133.2 -201.6 -282 0 0 0 0 0 0 -32.4 -76.8 -133.2 -201.6 -282 . . . M1-Cut M1-Fill GR GR GR GR GR GR GR GR GR GR GR GR GR GR GR GR GR GR GR GR GR GR . . . M1-Type 32.93 29.93 26.93 23.93 20.93 0 0 0 0 0 0 32.93 29.93 26.93 23.93 20.93 0 0 0 0 0 0 . . . M2-Cut 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . . M2-Fill HP HP HP HP HP HP HP HP HP HP HP HP HP HP HP HP HP HP HP HP HP HP . . . M2-Type 137.6 97.2 60.8 28.4 0 0 0 0 0 0 0 137.6 97.2 60.8 28.4 0 0 0 0 0 0 0 . . . M3-Cut 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . . M3-Fill Table A.10: A sample input table for multi-material SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR SR . . . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . . M3-Type M4-Cut 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . . OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR . . . M4-Fill M4-Type Appendix A. Tables 73
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Models and strategies for efficiently optimizing the...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Models and strategies for efficiently optimizing the vertical alignment of roads for multimaterial Hossain, Shahadat 2013
pdf
Page Metadata
Item Metadata
Title | Models and strategies for efficiently optimizing the vertical alignment of roads for multimaterial |
Creator |
Hossain, Shahadat |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | The full abstract for this thesis is available in the body of the thesis, and will be available when the embargo expires. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2014-01-02 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0073960 |
URI | http://hdl.handle.net/2429/44663 |
Degree |
Master of Science - MSc |
Program |
Interdisciplinary Studies |
Affiliation |
Graduate Studies, College of (Okanagan) |
Degree Grantor | University of British Columbia |
Graduation Date | 2013-11 |
Campus |
UBCO |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2013_fall_hossain_shahadat.pdf [ 2.53MB ]
- Metadata
- JSON: 24-1.0073960.json
- JSON-LD: 24-1.0073960-ld.json
- RDF/XML (Pretty): 24-1.0073960-rdf.xml
- RDF/JSON: 24-1.0073960-rdf.json
- Turtle: 24-1.0073960-turtle.txt
- N-Triples: 24-1.0073960-rdf-ntriples.txt
- Original Record: 24-1.0073960-source.json
- Full Text
- 24-1.0073960-fulltext.txt
- Citation
- 24-1.0073960.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:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0073960/manifest