Finding the Vertical Alignment of Forest Roads Using Several
Transkript
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: akay@ksu.edu.tr) John Sessions, Department of Forest Engineering, College of Forestry, Oregon State University, Corvallis, Oregon 97331, USA. (E-mail: john.sessions@oregonstate.edu) Pete Bettinger, Warnell School of Forest Resources, University of Georgia, Georgia 30602, USA. (E-mail: pbettinger@smokey.forestry.uga.edu) Orhan Erdas, Department of Forest Engineering, Faculty of Forestry, Kahramanmaras Sutcu Imam University, 46100 Kahramanmaras, Turkey. (E-mail: erdas@ksu.edu.tr) 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.