Finding the Vertical Alignment of Forest Roads Using Several

2004 Council on Forest Engineering (COFE) Conference Proceedings: “Machines and People, The Interface”
Hot Springs, April 27-30, 2004
Finding the Vertical Alignment of Forest Roads Using Several Heuristic Techniques
Abdullah E. Akay, Department of Forest Engineering, Faculty of Forestry, Kahramanmaras Sutcu Imam
University, 46100 Kahramanmaras, Turkey. (Tel: +90 (344) 223-7666, Fax: +90 (344) 221-7244, (E-mail:
[email protected])
John Sessions, Department of Forest Engineering, College of Forestry, Oregon State University, Corvallis, Oregon
97331, USA. (E-mail: [email protected])
Pete Bettinger, Warnell School of Forest Resources, University of Georgia, Georgia 30602, USA. (E-mail:
[email protected])
Orhan Erdas, Department of Forest Engineering, Faculty of Forestry, Kahramanmaras Sutcu Imam University,
46100 Kahramanmaras, Turkey. (E-mail: [email protected])
ABSTRACT
Once the horizontal alignment of a forest road section between two known locations has been determined by
establishing a series of intersection points, the most economic vertical alignment can be identified using heuristic
techniques. In a previous research work, Simulated Annealing (SA) was used to locate the optimal vertical
alignment for a preselected horizontal alignment, while subject to the geometric design specifications,
environmental requirements, and driver safety. The feasible vertical alignments were generated by adjusting the
intersection points using a neighborhood search procedure and acceptance criterion. For each alignment, the
earthwork cost was minimized using linear programming. This study is a sequel to this earlier study. It employs
various heuristic techniques for optimizing vertical alignment of a forest road section and compares their
performances in a simple application. The results indicated that heuristic techniques may be useful tools for
identifying the optimum vertical alignment at acceptable computational time.
Key Words: forest roads, vertical alignment, optimization, heuristics
INTRODUCTION
In order to locate the lowest total cost path subject to
environmental requirements and driver safety, forest
road designers should examine a sufficient number of
alternative alignments to assure that they have
identified a good one. Evaluating a large number of
alternative paths considering the specified constraints
is too complex a problem to solve with traditional
road design methods (Akay 2003). Heuristic
techniques can be used to solve such a problem with
many solutions. These techniques systematically
search for the optimal solution among feasible
solutions at acceptable computational cost (Beasley
et al. 1993).
In recent years, heuristic techniques have been
applied to forest road design problems. To optimize
vertical alignment for a forest road, Ichihara et al.
(1996) developed an optimization model using a
heuristic technique (Genetic Algorithm) for
identifying the optimum combinations of intersection
points and dynamic programming for locating the
optimum longitudinal slope with minimum
construction cost. The model was applied to a road
section that had been located using traditional road
design methods. The results indicated that the
optimization model took significantly less calculation
time compared to an existing road designed using
traditional methods.
Suzuki et al. (1998) also applied a Genetic Algorithm
(GA) to a forest road design problem for recreation.
In this study, scenic values, road slope, distance
between roads, variation of the ground elevation,
road length, and longitudinal slope were the
evaluation factors. First, two intermediate points per
one route were located to search between four points
including the beginning point, two intermediate
points, and the end point. Then, GA was employed
to find an optimal solution by altering coordinates of
the intermediate points. Comparison of the forest
road profiles designed using GA and traditional
method indicated that GA significantly reduced the
calculation time.
Akay (2003) developed a forest road alignment
model, TRACER. An initial alignment was located
on a 3D view of the terrain generated based on a
high-resolution DEM, considering the specified
constraints. The constraints included geometric
specifications, environmental requirements, and
2004 Council on Forest Engineering (COFE) Conference Proceedings: “Machines and People, The Interface”
Hot Springs, April 27-30, 2004
driver safety. A heuristic technique, Simulated
Annealing, was used to search for the best vertical
alignment with minimum total cost of construction,
maintenance, and transportation costs. For each
alignment alternative, a linear programming method
(Mayer and Stark 1981) was used to determine the
economic distribution of cut and fill quantities. The
model application indicated that development of a
road design that incorporates computer graphics
capability, advanced remote sensing technologies,
and optimization techniques could significantly
improve the design process for forest roads.
Aruga et al. (2004) developed a model to compare
capabilities of two heuristic techniques, GA and Tabu
Search (TS), in planning of a forest road profile. In
the model, alternative profiles were generated by
adjusting the heights and the location of the
intersection points. The method of Akay (2003) was
used to calculate total cost of construction and
maintenance activities. Earthwork allocation was
determined by using linear programming (Mayer and
Stark 1981). The results indicated that the model
using TS usually found a good quality solution in less
time than using GA. However, both heuristic
techniques found a near optimum/good quality
solution in a reasonable computational time.
This study is a sequel to an earlier study conducted
by Akay (2003) in which SA was used for optimizing
vertical alignment of a forest road section. In this
study, various other heuristic techniques were
employed and their performances were compared in a
simple application. The opportunities of using
heuristic techniques for finding the optimal vertical
alignment are presented to encourage other
researchers to apply them in road design problems.
HEURISTIC TECHNIQUES
Four types of heuristic techniques were used to solve
a vertical alignment optimization problem. The
techniques include Simulated Annealing, Threshold
Accepting, Record-to-Record Travel, and Great
Deluge Algorithm. In this section these techniques
were briefly described and the logic behind each
technique was presented. In the optimization process,
the initial vertical alignment (initial solution) was
generated by manually establishing the intersection
points on 3-D view of the terrain. The alternative
vertical alignment (new solution) was automatically
generated by changing the elevation at a randomly
selected intersection point within the specified
elevation range. For each feasible solution, the model
calculates its “quality”, which is the unit cost of sum
of the construction, maintenance, and transportation
costs. Then, heuristic techniques were used to
systematically search for the good quality/near
optimal solution among the acceptable solutions.
Simulated Annealing
The idea of Simulated Annealing (SA) is based on a
simulation of a metallurgical process known as
annealing. In order to produce a good quality
product, a solid material should be heated past its
melting point and then gradually cooled back into an
optimal state, subject to a reheating and cooling
schedule. Kirkpatrick et al. (1983) suggested that this
process could be basis of a heuristic technique for
combinatorial problems. SA uses a local search
where alternative solutions are generated by moving
from one solution to a neighborhood solution. There
are number of generic decisions to be made for
implementing the algorithm. These decisions include
the initial temperature (t), the temperature reduction
factor, and the stopping condition (maximum number
of iterations). In most of the combinatorial
optimization problems, they are determined based on
several trial and error runs of the search process.
After an initial solution (old solution) is determined,
the model generates a feasible random solution (new
solution) and calculates its quality. If the new
solution is feasible and better than the old solution, it
becomes the old solution for the next step. If the
proposed new solution violates any of the constraints,
it is rejected by the model and another random
solution is generated. To avoid being trapped in a
local optimum, the algorithm will allow the
acceptance of an inferior solution, with a decreasing
probability. After a user defined number of iteration,
the temperature is reduced by using temperature
reduction factor. Therefore, the probability of
accepting a worse solution is slowly lowered. The
model records the “best” solution among the
acceptable solutions during the running time. The
algorithm stops once the stopping conditions is
reached. The algorithm of SA runs as follow for
minimization:
select an initial solution (old solution)
select an initial temperature t>0
select a new solution
compute E = quality of new solution –
quality of old solution
IF E < 0
THEN old solution = new solution
ELSE with probability exp(E/t)
old solution = new solution
IF too many iterations with the same t
THEN reduce temperature t
IF stopping condition is reached
THEN stop
2004 Council on Forest Engineering (COFE) Conference Proceedings: “Machines and People, The Interface”
Hot Springs, April 27-30, 2004
Threshold Accepting
Dueck and Scheuer (1990) first proposed the idea of
Threshold Accepting (TA), which is very similar to
SA. It has a slightly different set of acceptance rules
than that of SA. TA accepts every feasible solution
which is not much worse than the old solution, while
SA accepts worse solutions only with rather small
probability. Once an initial solution (old solution) is
generated, the difference (E) between the quality of
proposed new solution and the old solution is
compared to a user defined initial threshold level (T).
If the new solution is feasible and E is less than the
threshold level, the new solution becomes the old
solution. If the proposed new solution is not feasible
with respect to the constraints, the model rejects it
and generates another random solution. The best
solution among the acceptable solutions is recorded
by the model. If there has been no improvement in
the quality of the best solution for a specified number
of iteration, the threshold is reduced by threshold
reduction factor. If the threshold level reaches the
minimum threshold level or total number of process
iterations exceeds the maximum number of iterations,
the algorithm stops. The initial threshold, threshold
reduction factor, minimum threshold level, and
maximum number of iterations are determined by the
user after a few experiments. If the quality of the best
solution has not improved for a user-defined number
of iteration, the search process also ends. The
algorithm of TA runs as follow for minimization:
the initial solution (old solution) and the model
records its quality (R). Then, the model generates a
proposed new solution. If the new solution is
feasible, its quality (Q) is compared to the quality of
the old solution plus a user defined value of some
deviation (D). If the quality of the new solution is
less than R + D, the proposed new solution becomes
the old solution. Moreover, if Q is less than R, R
becomes Q for the next steps. If there has been no
improvement in the quality of the best solution for a
specified number of iteration or maximum number of
iterations is reached, the algorithm stops. The user
determines D and the maximum number of iterations
based on several trial and error runs of the search
process. The algorithm of RRT runs as follow for
minimization:
select an initial solution (old solution)
select a deviation value D>0
set R = quality of the initial solution
select a new solution
compute Q = quality of new solution
IF Q < R + D
THEN old solution = new solution
IF Q < R
THEN R = Q
IF no improvement in quality for too
many iterations or maximum
number of iteration is reached
THEN stop
Great Deluge Algorithm
select an initial solution (old solution)
select an initial threshold level T>0
select a new solution
compute E = quality of new solution –
quality of old solution
IF E < T
THEN old solution = new solution
IF no improvement in quality for
many iterations with the same T
THEN reduce threshold level T
IF no improvement in quality for too
many iterations or maximum
number of iteration is reached
THEN stop
Record-to-Record Travel
The idea of Record-to-Record Travel (RRT)
resembles the algorithms of SA and TA (Dueck
1993). The difference relies on their acceptance rules.
In RRT, if the quality of any proposed new solution
is not much worse than the quality of the best
solution recorded so far, the new solution is accepted.
In the search process, the designer first determines
The Great Deluge Algorithm (GDA) is similar to SA
with a slight change in deciding whether or not the
proposed solution is acceptable as a new solution.
GDA was introduced by Dueck (1993) and in a
maximization process it searches for the highest
elevation in a fictitious surface by simply walking
around the surface, while it rains without end. Once
an initial solution (old solution) is generated by the
designer and its quality is computed by the model,
the initial water level (WL) is determined by adding
(subtracting in a maximization process) a user
defined “rain speed” (RS) from the quality of the
initial solution. Then, a feasible new solution is
generated by the model, considering the specified
constraints. If the quality of the new solution (Q) is
less than the initial water level, the old solution
becomes the new solution and water level becomes
WL – RS. If the quality of the best solution has not
improved for a user-defined number of iterations or
maximum number of iterations is reached, the
algorithm stops. Rain speed and the maximum
number of iterations are determined by the user after
2004 Council on Forest Engineering (COFE) Conference Proceedings: “Machines and People, The Interface”
Hot Springs, April 27-30, 2004
a few experiments. The algorithm of GDA runs as
follow for minimization:
select an initial solution (old solution)
select a rain speed RS>0
set the initial water level WL>0
select a new solution
compute Q = quality of new solution
IF Q < WL
THEN old solution = new solution
WL =WL - RS
IF no improvement in quality for too
many iterations or maximum
number of iteration is reached
THEN stop
was located by using six intersection points (Figure
1). The unit cost of the initial solution was $32.05/m.
Then, the model generated the optimal vertical
alignment using heuristic techniques.
The solution quality and computational times are
presented in Table 1. The results from the example
indicated that GDA and SA were better techniques
than TA and RTR in terms of solution time. GDA
was the fastest algorithm, while RTR was the slowest
algorithm among the heuristic techniques. The good
quality/near optimum solution ($28.61/m) for the
problem was reached by each of the four heuristic
techniques. Using the heuristic techniques, the unit
cost of sum of the construction, maintenance, and
transportation costs was reduced approximately 11%.
RESULTS AND DISCUSSION
The solutions generated by the four heuristic
techniques and their performance are compared in a
simple application. The study area of 55 hectares was
located in the Capitol State Forest, Washington. Soil,
hydrology, and geology data were provided by
Washington Department of Natural Resources. Road
design specifications and economic data were
obtained from the local sources (Kramer, 2001 and
USDA Forest Service, 1999). The initial road path
was located by establishing the intersection points on
the 3D image of the terrain based on DEM data from
LIDAR (Aerotec, 1999), while considering the
specified constraints. Some of these constraints
include minimum curve radius (18 m), minimum
vertical curve length (15 m), minimum gradient ( 2
%), maximum gradient (16%), minimum distance
from a stream (10 m), and maximum cut and fill
height (2 m). A sample forest road section (625 m)
Intersection
Points
Initial Road
Path
Figure 1. The initial solution generated by locating
the intersection points on 3D image of the terrain.
The heuristics were also compared in terms of
complexity of the programming. GDA and RRT were
very easy to implement because the success of these
algorithms depends on a single parameter. However,
in SA and TA, the quality of the solutions depends on
two parameters; therefore, they are relatively difficult
to implement into the computer programming.
In SA, when the initial temperature was too high,
worse solutions were usually accepted in the process.
Choosing the appropriate initial temperature and
temperature reduction factor influence the success of
the algorithm. In TA, the initial threshold and
threshold reduction factor were the main parameters
that reflected the quality of the results and
computational time. When the initial threshold was
too high, the algorithm produced low quality
solutions. In RRT, when the value of deviation was
too small, the algorithm ran very fast and produced
low quality results. Therefore, a large value was
chosen for deviation to generate excellent results. In
GDA, when the rain speed was too high, the
algorithm ran very fast and produced poor solutions.
To produce high quality solutions, the rain speed was
needed to be very low in this problem.
Table 1. The solution quality and times for the four
heuristic techniques, using Pentium III 750 MHz
processor.
Heuristic
Techniques
Solutions
($/m)
Computational
Times (min)
SA
28.61
5.6
TA
28.61
9.2
RTR
28.61
10.5
GDA
28.61
5.1
2004 Council on Forest Engineering (COFE) Conference Proceedings: “Machines and People, The Interface”
Hot Springs, April 27-30, 2004
CONCLUSION
Finding an optimal vertical alignment of a forest road
by evaluating all the feasible alternatives, considering
economical and environmental constraints, is too
large a problem to be solved by using the traditional
road location methods. In recent years, heuristic
techniques have been used to solve such complex
problems at reasonable computational cost. In this
study, four heuristic techniques (SA, TA, RTR, and
GDA) were applied to a forest road location problem,
where the objective function was to minimize the
sum of the construction, maintenance, and
transportation costs, subject to specific constraints.
The performance differences of these heuristic
techniques in terms of solution quality, computational
time, and complexity of programming were
investigated. The results indicated here can not be
generalized; however, this research can provide other
researchers with insight information into using
heuristic techniques for road design problems.
Besides, it can be a guide to assist road designers in
selecting the technique that is most appropriate for
their specific problem.
REFERENCES
Aerotec, 1999. Airborne laser-scan and digital
imagery. 560 Mitchell Field Road, Bessemer, AL
35022.
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.
Aruga, K., J. Sessions, and A. Akay. 2004. Heuristic
techniques applied to forest road profile. Submitted
to the Japanese Forestry Society, Journal of Forest
Research.
Beasley, J., K. Dowsland, F. Glover, L. Manuel, C.
Peterson, C. Reeves, and B. Soderberg. 1993.
Modern heuristic techniques for combinatorial
problems. New York. 320 p.
Dueck, G and T. Scheuer. 1990. Threshold accepting:
A general purpose optimization algorithm. Journal of
Comput.Phys. 90:161-175.
Dueck, G. 1993. New optimization heuristics: The
great deluge algorithm and the record-to-record
travel. Journal of Comput.Phys. 104:86-92.
Ichihara, K., T. Tanaka, I. Sawaguchi, S. Umeda, and
K. Toyokawa. 1996. The method for designing the
profile of forest roads supported by genetic
algorithm. The Jap. Forestry Society, Journal of
Forest Research. 1: 45-49.
Kirkpatrick, S., C.D. Gerlatt, and M.P. Vecchi. 1983.
Optimization by simulated annealing, Science. 220:
671-680.
Kramer, B.W. 2001. Forest road contracting,
construction, and maintenance for small forest
woodland owners. Oregon State University, Forest
Research Laboratory, Research Contribution 35. 79
p.
Mayer, R. and R. Stark. 1981. Earthmoving logistics.
Journal of Const. Div. 107(CO2):297-312.
Suzuki H, K. Ichihara, and I. Noda. 1998. Road
planning in forest for recreation. Journal of the Japan
Forest Engineering Society. 13(3): 151-160.
USDA Forest Service, 1999. Cost estimate guide for
road construction Region 6. Cost Guide Zone 5,
Davis-Bacon Area 5, Oregon. 98 p.