Vol. 16, No. 2 July 2005
Abdullah E. Akay
Kahramanmaras Sutcu Imam University
Kahramanmaras, Turkey
Kevin Boston
John Sessions
Oregon State University
Oregon, USA
The authors are, respectively, Assistant Professor, Department of Forest Engineering, Faculty of Forestry; Assistant Professor, Department of Forest Engineering, College of Forestry; and Professor, Department of Forest Engineering, College of Forestry.
ABSTRACT
In order to locate a path between two known locations on a ground surface, a large number of alternative paths should be evaluated considering physical, economical, and environmental factors. Optimization techniques can be used to search for a path that minimizes the total costs while satisfying the design and environmental constraints. These techniques can result in considerable time savings in forest road design. Initially, these optimization techniques have been applied to highway design and recently, they have been applied to forest road design. This paper describes the evolution of the optimal route location systems used in both highway and forest road design based on ten criteria. The paper concludes by describing some of the unsolved problems in forest road design.
Keywords: Optimizing road alignment, minimizing road cost, earthwork allocation, forest road design.
Introduction
Route selection analysis is a time-consuming process that requires a multicriteria evaluation of alternative alignments. This will include safe operation, construction cost, transport cost, recreational use, acute environmental impacts commonly associated with road failure, and chronic environmental impacts such as sediment production from poorly designed roads. To solve such a problem at reasonable computational cost, computer-aided analysis of route selection has been applied to road design since the 1950's.
The early applications [18, 8, 21, 10, 16, 15] were not capable of making computer-aided design judgments such as automatically generating alternative grade lines, locating a best-fitting vertical alignment for minimizing earthwork, verifying curvature limitations and gradient changes, and minimizing the total cost of construction, maintenance, and transportation. They relied on the experience of the road locator in the route selection process. These systems did not allow the road manager to look at tradeoffs between various locations and construction practices at the road segment level. These initial applications considered only construction costs and have been followed by improved applications which employed modern optimization techniques to consider transport costs and environmental costs in addition to construction costs.
Forest roads differ from the more familiar highways or rural roads. They typically incur lower traffic levels than other roads, but the vehicles are large with heavy loads. In addition, forest roads can have both commercial logging and recreational traffic, which requires additional safety measures. In the process of route selection and subsequent design, forest road managers simultaneously consider multiple constraints including construction cost, maintenance cost, hauling cost, and driver safety. They also consider environmental impacts caused by road construction and use. In order to meet these multiple constraints, a number of computer-aided design systems have been developed and used by forest road managers.
This paper presents an evolution of computer-aided design systems that were first developed for highways, but have now evolved to meet the requirements for forest roads. To compare the functionality of these systems, the following criteria were used:
The paper will conclude with a discussion of future work in the area of computer-aided forest road design.
Highway Design Systems
System I: Parker [17] used a two-stage approach to determine the horizontal and vertical alignment that minimized construction costs while satisfying the vertical curvature requirements, gradient changes, and other design constraints. The method subdivides the land into square grids. The ground elevation at a grid centroid was calculated as the mean elevation. The arithmetic differences between the elevations of the selected smooth surface and the original ground were computed for each grid. If the difference is positive there is cut and if the difference is negative there is fill (Figure 1). Then, the feasible horizontal alignments were generated by connecting the grid centroids with respect to the grade constraints. The absolute values of the outputs from the surface-smoothing stage were the inputs to the second stage that minimizes the total earthwork costs using linear programming. The second stage used the multiple-path selection program ([6], [19]) to generate a user-specified number of alternative alignments and determine the optimal path with the minimum construction cost. The location of the optimal path was determined based on the criteria of the minimum sum of the deviations of the smoothed surface from the ground elevations. Results using this system indicated that it was certainly a quicker way to search for alternative route locations than the manual approaches being employed. However, this model only considers construction costs and has limited application in forest engineering.
Figure 1. Profile view of a highway section.
System II: Trypia [20] developed a model to minimize the total construction cost subject to specified design constraints such as maintaining the road grade within acceptable limits. Once a fixed horizontal alignment was determined, the alternative road grades were generated using surface grids similar to System I (Figure 2). In this model, the designer determines the density of grids to best reflect the variability of the ground. The number of grids increased where the ground characteristic showed high variation, which significantly increases the solution time. The model used mixed integer programming to determine road elevations for each section conforming to the desired road grades. At any specified ground point (i), the road elevation (ri) was equal to hi + xi1 - xi2 where hi was the ground elevation and xi2 and xi1 were the cut and fill heights, respectively. The cut and fill heights were limited by the upper (ui) and lower limits (li). A binary variable (d) was used to assign any section as either cut or fill section. The road gradient constraint was limited by a user-defined maximum acceptable road gradient. Then, the objective function of minimizing the total cost (Z) was formulated as follows:
Min Z = 
cilxil +
ci2xi2
subject to; xi1 £ uid, xi2 £ li(1-d), xi1, xi2 ³ 0, d Î (0,1) and ci1 and ci2 are the unit cost of fill and cut, respectively.
Figure 2. Schematic diagram of a terrain on a surface grid.
As in all mixed integer programming problems solved using branch-and-bound techniques, the solution time increases in a non-polynomial rate (factorial or exponential) with respect to problem size. The cost functions for excavation and embankment activities were formulated based on the terrain conditions and type of the machinery used. The effectiveness of this model was dependent on a good initial vertical alignment.
System III: A linear programming model was developed by Mayer and Stark [14] to minimize the cost of the earthmoving activities (Figure 3) using the cut and fill for each section computed from field-generated cross-sectional data. The objective function's goal was to minimize earthwork. There were 4 sets of constraints: (1) The total volume of material moved from a cut section to all fill sections and the waste area has to be equal to the available amount of cut at that cut section, (2) the total amount of fill moved to a fill section from all cut sections and the borrow area has to be equal to the amount of fill required at that fill section, (3) the total volume moved from all cut sections to the waste area has to be equal to or less than the capacity of that waste area, and (4) the total amount of material moved from the borrow area to all fill sections has to be equal to the capacity of that borrow area. The unit costs for excavation, haul, and embankment were computed based on estimated soil characteristics of each section. This model was one of the first to include shrinkage and swell factors, which is necessary to properly determine haul and fill quantities.
Figure 3. Distribution of cut and fill material considering borrow and waste areas.
In this model, it is assumed that the unit-hauling cost is linearly proportional to the hauling distance and the unit costs do not vary with the amount of material moved. This model showed that a linear programming model of earthwork allocation could be used to overcome the limitation of the mass diagram. The mass diagram has been used to determine the minimum amount of haul, direction of the haul, and distribution of earthwork. It is a continuous curve illustrating the cumulative volume of the earth from an initial station to any succeeding station. The usefulness of the mass diagram decreases where soil characteristics vary along the roadway and additional quantities of material are required to be borrowed or wasted. The terrain and soil data must be obtained from previously conducted fieldwork external to the model.
System IV: Previous studies have shown that the purchase and excavation of borrow material are the largest cost components for highway construction costs [1]. Easa [7] developed a model to minimize the cost of earthwork by including the borrow costs. This model allows for different soil types with differing unit excavation costs as well as the distance from the borrow area to construction point to be included in the model. The unit cost function for the purchase and excavation for borrow material was formulated as a three-component stepwise function using a mixed integer linear programming model. The objective function and the constraints are similar to those developed by Mayer and Stark [14]. This model is capable of minimizing earthwork costs where the unit purchase costs and excavation for a borrow area depend on the earthwork quantity needed. The terrain and soil data must be obtained from previously conducted fieldwork external to the model.
System V: Goh et al. [9] was one of the first to include transport costs into computer-aided road design. They developed a dynamic programming algorithm with a state-parameterization model to solve the three-dimensional highway location problem. The solution method divided the road into intervals (stages) and then minimized the sum of the road construction, vehicle operation, pavement, and land costs over all the intervals. The method calculates the optimal vertical profile between two given end points of known locations, after the horizontal alignment was predetermined and fixed. The dynamic programming (Version-a) and state parameterization (Version-b) models were applied to a numerical example to compare their performances:
a) In this model, the highway section was subdivided into stages that used rectangular grids to calculate the cross sections along the central axis. A given number of vertical grid lines were used to subdivide the grid into uniformly spaced rectangular elements. The highway profile was then approximated by a series of linear segments connecting points from the start point to end point of the road. Dynamic programming produced a solution to the non-linear problem by minimizing the sum of the construction costs, while subject to maximum allowable gradient control, curvature requirements, and control points with fixed levels.
b) This model was revised to express the construction costs as a continuous function y(x) formulated as a calculus of variation problem. In the calculus of variation approach, the model finds the minimum path of a function in a space where the endpoints are fixed [12]. The vertical coordinates of the ground profile are a function of x and y coordinates, f (x, y), while road elevation is represented by z in Figure 4. The road profile is approximated as a series of cubic spline functions to transform the functional optimization problem into a constrained mathematical programming problem. Since a certain degree of smoothness is necessary for satisfying the gradient constraints, the parameterization of y(x) is followed by its first and second derivatives constraints that limit the changes from one grade or horizontal alignment to another.
Figure 4. Representation of ground and road profile in the state parametrization model.
Forest Road Design Systems
System VI: To improve the efficiency of the forest road designer, Douglas and Henderson [5] developed a computer model for forest road location problems using dynamic programming. The model divided the area of interest into grid cells which were rated with respect to specified criteria including topography, stand data, land ownership, and aesthetics. The rankings of the grid cells became a proxy for construction, usage, and environmental costs. The model allowed the designer to control the grid spacing to reflect the desired accuracy of the results. The model was capable of integrating with geographic information systems (GIS). The model required significantly less computational time when compared to traditional road location methods. There were some limitations in the model; for example, diagonal moves between the grid cells were not allowed.
System VII: Ichihara et al. [11] developed a model to locate the vertical alignment of a forest road with minimum construction costs, after a horizontal alignment was determined. A Genetic Algorithm (GA) was employed to select the set of grade control points where grade changes occurred. The GA is a modern heuristic technique that can provide good solutions for problems that exceed the computational limits of traditional mathematical techniques. The analogy of the genetic algorithm is based on the mechanics of natural selection where a population adapts and improves its fitness in a specific environment. By combining solutions, especially good solutions with a random mutation factor, a population of mathematical solutions will improve over time [2]. The model used a dynamic programming method [13] to design the optimum longitudinal grade. Intersection points were adjusted to generate the road grade with minimum construction cost. The model was applied to a road section that had been designed using traditional methods. Comparison of the profiles designed by both methods indicated a high degree of correspondence. Using the Genetic Algorithm significantly reduced the calculation time. However, computation time might increase as the number of survey points and intersection points increase. Data including survey points, intersection points, and earthwork data along the roadway were needed from previously conducted field work external to the model.
System VIII: Akay [1] developed a three-dimensional (3-D) forest road alignment model to optimally locate the road alignment by minimizing the total construction, transport, and maintenance costs, while considering environmental requirements and driver safety. The model relied on a high-resolution digital elevation model (DEM) generated using LIDAR (Light Detection and Ranging) technology. A feasible trial route was determined by locating intersection points on a 3-D graphic interface, considering geometric specifications and environmental requirements. A Simulated Annealing algorithm was used to search the best vertical alignment with minimum total cost of construction, maintenance and transportation costs, considering technically feasible grades. Simulated Annealing is one of the modern heuristic techniques that relies on an analogy of metallurgy in which a solid material is heated and cooled back slowly to produce the desired characteristics [2]. As the problem is solved with Simulated Annealing, the algorithm will allow the acceptance of an inferior solution, with a decreasing probability, to avoid being trapped in a local optimum. For each change in the vertical alignment, the model calculates cross sections and earthwork, which is then minimized using the linear programming procedure developed by Mayer and Stark [14]. In order to use this procedure, a linear programming code, based on the simplex algorithm [4], was incorporated into the model. Sediment production was simulated using relationships from the GIS-based sedimentation model, SEDMODL [3] to estimate the average annual volume of sediment delivered to a stream from the road.
Horizontal alignment is determined based on the designer's judgment, while considering geometric specifications and environmental requirements. The designer can develop a number of horizontal alignment alternatives to connect the same beginning and ending points. Then, the vertical alignment with minimum total cost is determined for each alterative using the optimization procedure. The model relies upon high quality LIDAR data that could be expensive to obtain.
DISCUSSION
This paper describes the development of computer-aided road design systems used for both highways and forest roads. Each system was evaluated based on specified road design criteria (Table 1). Initial computer-aided methods focused solely on earthwork as a proxy for construction costs. The early problems were solved using linear programming with several modeling limitations (System I). Modeling refinement was provided by System II using mixed-integer programming, but ground surfaces with high variation significantly increased the solution time.
System III improved the earthwork model by considering multiple shrinkage and swell factors. System IV incorporated stepwise functions into the model to better describe and solve earthwork problems using linear programming. Neither System III or IV were intended to determine vertical or horizontal alignment.
Table 1. Capabilities of the systems based on the specified criteria.
Systems V-a and V-b were among the first to integrate road use and maintenance costs into the model. These models allow for nonlinear construction costs to be incorporated into the dynamic programming algorithms. The discrete-state model (System V-a) had to consider the number of stages carefully before solving the problem optimally while the continuous description model (System V-b) used calculus of variation techniques to solve the problem. These two models determined the optimal vertical alignment, once horizontal alignment was predetermined and fixed.
System VI was a computerized model that searched for the optimum overall route across a grid surface to solve a forest road problem. The model first assigned values to grids based on the multiple values considered in forest engineering and then located the vertical alignment with minimum total costs. The model could be integrated into a GIS, which provides access to the commonly collected data.
System VII integrated two optimization techniques; a heuristic technique (Genetic Algorithm) to solve the grade location problem and dynamic programming to solve the earthwork problem. Although these techniques could not guarantee an optimal solution, they investigated a significant portion of the solution space and usually produced good/near optimal solutions to be evaluated by the road designers.
System VIII was one of the first attempts to include overall cost components, environmental impacts, and driver safety in a computer-aided forest road design package. This system was built upon the work of Ichihara et al. [11]. The vertical alignment was located using a heuristic technique (Simulated Annealing) while earthwork allocation was determined using linear programming. In this system, horizontal alignment was not optimized, but located by a designer considering wide range of constraints. The main goal of the system was to assist a forest road designer to quickly evaluate alternative alignments in a systematic manner.
CONCLUSION
There has been substantial progress in computer-aided road design systems during the last 20 years, but additional work is still needed. The systems can be improved by including optimization of the horizontal and vertical alignments simultaneously. Akay [1] describes the computational burden of optimization of the horizontal and vertical control automatically. The recent development of modern heuristics techniques such as Tabu Search, Threshold Accepting, Simulated Annealing, the Genetic Algorithm, and their hybridization with traditional solution techniques into metaheuristic algorithms may offer opportunities for future research. It may also be possible to include a two-neighborhood search routine that would allow for changes to the horizontal and vertical alignments to be evaluated against a suite of proposed environmental impacts.
As additional remote sensing platforms become available to the commercial sector, there should be significant improvements in the cost, accuracy and precision in these data sources. This data may overwhelm many of the solution algorithms; therefore, future research will be needed to align algorithms to use the minimum data necessary.
AUTHOR CONTACT
Mr. Akay can be reached by e-mail at --
akay@ksu.edu.tr
REFERENCES
[1] Akay, A.E. 2003. Minimizing Total Cost of Construction, Maintenance, and Transportation Costs with Computer-Aided Forest Road Design. Ph.D. thesis, Oregon State University, Corvallis, Oregon. 229 p.
[2] Beasley, J., K. Dowsland, F. Glover, L. Manuel, C. Peterson, C. Reeves and B. Soderberg. 1993. Modern heuristic techniques for combinatorial problems. Halsted Press, John Wiley and Sons, Inc. New York. 320 pp.
[3] Boise Cascade Corporation, 1999. SEDMODL-Boise Cascade road erosion delivery model. Technical documentation. 19 pp.
[4] Bowman, E.H. and R.B. Fetter. 1967. Analysis for production and operations management. Irwin Series in Quantitative Analysis for Business. Yale University. 870 pp.
[5] Douglas, R.A. and B.S. Henderson. 1987. Computer assisted forest road route location. High Technology in Forest Engineering. Proceedings of the Council of Forest Engineering, 10th Annual Meeting, Syracuse, New York. pp. 201-217.
[6] Dreyfus, S.E. 1968. An appraisal of some shortest-path algorithms. Rand Corporation, Santa Monica, California.
[7] Easa, S.M. 1988b. Earthwork allocations with linear unit costs. J. Construction Eng, and Management 114(4):641-655.
[8] Gladding, D.F. 1964. Automatic selection of horizontal alignments for highway location. Unpublished M.S. Thesis, Massachusetts Institute of Technology, Boston, Mass.
[9] Goh, C.J., E.P. Chew and T.F. Fwa, 1988. Discrete and continuous models for computation of optimal vertical highway alignment. Transportation Research 22B(6):399-409.
[10] Howard, B.E., Z. Bramnick, and J.F.B. Shaw. 1968. Optimum curvature principle in Highway Routing. Proc. Am. Soc. Civil Eng. (94):61-82.
[11] Ichihara, K., T. , I. Tanaka, S. Sawaguchi , K. Umeda, and K. Toyokawa. 1996. The method for designing the profile of forest roads supported by genetic algorithm. The Japanese Forestry Society. J. Forestry Res. 1:45-49.
[12] Kamien, M.I. and N.L. Schwartz. 1981. Dynamic optimization; the calculus of variations and optimal control in economics and management. Vol 4. Elsevier North Holland, Amsterdam.
[13] Kanzaki, K. 1973. On the decision of profile line of forest road by dynamic programming. J. Japanese Forestry Society 55:144-148.
[14] Mayer, R. and R. Stark. 1981. Earthmoving logistics. J. Const. Div. 107(CO2):297- 312.
[15] Nicholson, A.J. 1974. A variational approach to optimal route location. Civil Engineering Report 74-7, University of Canterbury, N.Z.
[16] O'Brien, W.T. and D.W. Bennett. 1969. A dynamic programming approach to optimal Route Location. Proc Symposium on Cost Models and Optimization in Road Location, Design and Construction. pp.175-199.
[17] Parker, N.A. 1977. Rural highway route corridor selection. Transportation Planning Techniques. (3):247-256.
[18] Roberts, P.O. 1957. Using new methods in highway location. Photogrammetric Eng. 23(3):563-569.
[19] Sakarovitch, M. 1968. "The K shortest chains in a graph". Transportation Research. 2 (1): 2-11.
[20] Trypia, M. 1979. Minimizing cut and fill costs in road making. Computer-Aided Design. (11):337-339.
[21] Turner, A.K. 1968. Computer-assisted procedures to generate and evaluate regional highway alternatives, Joint Highway Research Project Report No.31, Purdue University, Lafayette, Indiana.