**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:

- Does it provide reasonable solution time?
- Does it require reasonable time for data input?
- Does it provide an optimal vertical alignment?
- Does it provide an optimal earthwork allocation?
- Does it consider construction cost?
- Does it consider maintenance cost?
- Does it consider transportation cost?
- Does it consider environmental requirements?
- Does it consider driver safety?

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
(*r _{i}*) was equal to

*Min Z = c _{il}x_{il} +
c_{i2}x_{i2}*

subject to;
*x _{i1}* £

**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, 10^{th} 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.