Woodam CHUNG, Graduate Research Assistant, John SESSIONS, Professor, Department of Forest Engineering, Oregon State University, Corvallis, OR 97331, UNITED STATES OF AMERICA, and Hans R. HEINIMANN, Professor of Forest Engineering, Swiss Federal Institute of Technology, Zurich, SWITZERLAND
This paper describes a methodology for optimizing cable logging layout using a digital terrain model (DTM). The methodology formulates a cable logging layout as a network problem. Each grid cell containing timber volume to be harvested is identified as an individual entry node of the network. Mill locations or proposed timber exit locations are identified as destinations. Then each origin will be connected to one of the destinations through alternative links representing different cableways, harvesting equipment, landing locations and truck road segments. A preliminary computerized model currently being developed is introduced as an application of the methodology. The model is intended to optimize landing, logging profile, and road location, simultaneously using information from a DTM. A heuristic method for network programming can be used as an optimization technique in this methodology.
Key words: Cable logging layout, network analysis, heuristics
Designing timber harvesting units is one of the most difficult tasks in forest operational planning. The task requires engineers to decide on logging equipment, landing site, logging profile, transportation system, and road location based on various considerations, including timber volume distribution, economic and environmental outcomes, as well as the physical feasibility of the system. Traditionally, engineers have done the task manually, but it is difficult to consider many alternatives. Thus, it is not easy to find a timber harvest layout that is not only “feasible” but also “good” by the manual method.
With the purpose of assisting engineers in designing timber harvest layout, various computerized methods have been introduced in the United States. Dykstra (1976) developed a methodology to assist in the design of timber harvest cutting units and the assignment of logging equipment. However, the methodology did not consider alternative road locations or multispan skyline systems, both of which result in limiting the flexibility of harvesting unit design and the scope of the problem. Only clear-cut treatments were considered and additional constraints (i.e. landing capacity, equipment availability) were not permitted in the model.
PLANS (Preliminary Logging Analysis System) developed by Forest Service (Twito et al., 1987) has been used for developing timber harvest and road network plans based on large-scale topographic maps. The model provides useful information, such as payload analysis, cost analysis, road layout, and terrain information. However, it does not have the ability to optimize a timber harvest operational plan.
PLANEX (Epstein et al., 1999a; Epstein et al., 1999b) is able to generate an approximately optimal allocation of equipment and road network based on a heuristic algorithm. However, the system does not have the ability to analyse cableways with their topographic profiles, and some logging cost estimations do not vary with yarding distance and other cableway variables.
This paper presents a methodology developed for optimizing cable logging layout using a DTM. The methodology combines a cable logging equipment assignment problem with a road location problem, optimizing them simultaneously while incorporating modern computer hardware languages, Geographic Information System (GIS) technologies and optimization techniques that have become available during the last decade. The methodology evaluates alternative cable layouts based on feasibility analyses of logging systems and road segments, and estimation of operation costs.
A heuristic for network programming is used as an optimization technique. The algorithm provides flexibility to consider other constraints, such as equipment availability, landing capacity and environmental considerations. The methodology is implemented in a computerized model, which is currently being developed as a decision-making support tool. On completion, the model will be able to assist forest engineers in designing cable logging units by providing “feasible and good” alternatives using cost and environmental criteria.
Methodology for optimizing cable logging layout using a DTM
Timber harvest operations can be considered as a series of operations that start from the stump and end at the mill. Each operation can be represented by a link connecting two consecutive operations with corresponding costs. Then a series of operations would be a path (a series of links) forming a part of a network system. All possible paths from each timber source would structure an entire network system consisting of multiple origins, multiple paths and multiple destinations. Then the network problem is solved using one of the network solution techniques developed by Sessions (1985) and Chung and Sessions (in press).
The methodology requires two GIS layers as input data: a DTM and a timber volume layer (see Figure 1). A DTM provides spatial and topographic information for logging feasibility analysis and estimating logging operation costs. A timber volume layer enables identification of the timber sources spatially, by which we can consider not only clear-cut treatments but also group selection cutting systems and even individual tree selection operations, which are usually used in natural forest in tropical regions.
|Digital Terrain Model||Irregular distribution of timber volume|
Figure 1. GIS layers used in the network analysis as input data.
Figure 2 shows a series of cable harvesting operations on a DTM. The timber harvesting operations using cable systems may be categorized into two different types of operations: cable logging and truck transportation. The cable logging operation planning requires decisions on the cable system, cableway, and landing location, while truck transportation planning requires selection of road locations and transportation routes.
Figure 2. Cable harvesting unit layout as a network problem on a DTM
Selecting cableways and landing locations
Alternative landing sites are located over a harvest unit by the planner. Cable equipment is placed at the proposed landing sites. Based on the cable equipment, cableways are projected from the landing location and a payload analysis is conducted to find alternative cableways that satisfy logging feasibility. Each feasible cableway would cover a portion of the harvest unit as its feasible yarding zone, depending on the lateral yarding capacity of the system. Because the yarding zones from different cableways of different systems at different landing locations could overlap, timber in a grid cell within the overlapped area may be yarded through any of the possible alternative cableways, systems and landings (see Figure 3).
Costs incurred by an individual cableway of a cable system are evaluated based on payload analysis, ground profile, cable system and harvest volume. Landing costs are estimated from construction cost and landing template. After evaluating the possible paths from each timber source to eligible destinations, each grid cell (timber source) is assigned to one of the alternative cableways. This assignment of the grid cell to the cableway simultaneously defines the cable system and landing location.
Figure 3. An example of alternative cableways and landing locations
Selecting road locations
Identifying a set of possible road segments on a DTM using a network-based algorithm has been done by Liu and Sessions (1993). It is assumed that each grid cell on the DTM has eight potential links corresponding to moves to adjacent grid cells (see Figure 4). Each link is evaluated based on the construction and transportation costs, the maximum gradients and environmental factors. The construction costs can be estimated using the sideslope from the DTM. The methodology in this study regards the road location problem as a part of a large network problem that includes cableway and landing location problems.
Figure 4. Possible road segments from a grid cell
Assembling the network
Each grid cell containing timber volume to be harvested is identified as an individual entry node of the network. Mill locations or proposed timber exit locations are identified as destinations of the network.
Then each origin will be connected to one of the destinations through alternative paths representing different cableways, harvesting equipment, landing locations and truck road segments (see Figure 5). Each path consists of links incurring variable costs (yarding and truck transport cost) and fixed costs (equipment cost, landing and road construction cost).
In order to solve cable equipment assignment and road location problems simultaneously, two different link lists are used in the network analysis: a cableway link list and a road link list. The cableway link list includes all possible links from the origins to alternative landings and is used to evaluate cable logging operation paths. A road link list consists of road links generated from the DTM and is used to evaluate truck transportation routes from each landing to the destinations.
Once the road and cableway network is set up, a network algorithm solves the problem and finds the lowest cost path from each origin (timber entry) to one of the destinations (mills) while simultaneously selecting the cableway, cable equipment, landing location and road segments to be used.
Figure 5. A network represents timber harvesting operations, including cable logging and truck transportation
Optimization algorithm - heuristics for network programming
Because of their efficiency and ability to handle large-scale optimization problems, network optimization algorithms have been used for solving a wide variety of problems, such as transportation, assignment and resource allocation (Jensen and Barnes, 1980). In forestry, a heuristic network algorithm developed by Sessions (1985) has been applied to forest transportation planning and other applications. Chung and Sessions (In press) have also applied other heuristic solution techniques, such as Simulated Annealing (Kirkpatrick et al., 1983) and Great Deluge (Dueck, 1993), to solving a network problem.
A new heuristic network algorithm currently being developed by the authors of this paper may also be appropriate to solve a large network problem. The new algorithm combining a Simulated Annealing technique with k-shortest path algorithm may be able to provide more flexibility to solve problems with multiple objectives and multiple constraints. Any of the above algorithms can be applied to solving cable logging layout problems described in this paper. Applying the problem solving algorithms and comparing results among them is not within the scope of this paper.
Developing a computerized model
In order to implement the methodology described in this paper, a computerized model is currently in development. Figure 6 presents a flow chart for the planned model. The model starts with reading network data and generates two link lists for a network analysis. Based on the link lists, the network optimization algorithm will find the best timber path from each timber source to the proposed destination.
Figure 6. A flow chart for the computerized model
Figure 7 shows a screen of the preliminary model showing several functions that have already been developed. It presents a function to generate cableways from user-defined landing sites and a payload analysis example for one of the generated cableways. This cableway model also has the ability to locate intermediate supports automatically where necessary. Payload analysis is conducted based on ground profile, ground condition and cable equipment capacity. Additional functions and details are currently being developed.
Figure 7. A screen of the preliminary model showing functions of projecting cableways and a payload analysis
This paper introduced a methodology for simultaneously optimizing cable equipment assignment and road locations on a digital terrain model using a network solution technique. This methodology is currently being implemented in a computerized model. Developing a useful model requires an accurate estimation of operation costs, therefore, detailed cableway analysis and road cost modules are included.
Grid pixel size in a DTM directly affects the problem size for the network analysis. High resolution in a DTM would provide topographic details but exponentially increases problem size resulting in increasing solution time and demand for memory capacity. Methods to reduce problem size with a high resolution DTM may need to be explored to shorten solution time and lessen memory requirements.
Reducing the number of origins by clumping several timber cells together or eliminating infeasible links from the whole network system might be alternative ways to reduce problem size.
Verification of the methodology described in this paper will be done in the future studies. The results from this methodology can be compared with a cable layout by manual methods or results from other optimization techniques. Also, further studies to improve the efficiency of the solution technique should be taken based on the preliminary results of the planned model. The computerized model implementing this methodology is expected to provide “feasible and good” alternatives for cable logging layout. It would be able to assist forest engineers in developing a better layout in an efficient way.
Chung, W. & Sessions, J. (In press). 2000. NETWORK 2000, a program for optimizing large fixed and variable cost transportation problems. In Proceedings of the 2000 Symposium on Systems Analysis in Forest Resources. Edited by Arthaud, G. J. Society of American Foresters. Aspen, Colorado.
Dueck, G. 1993. New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics. 104:86–92.
Dykstra, D.P. 1976. Timber harvest layout by mathematical and heuristic programming. (PhD dissertation). Oregon State University. Corvallis, Oregon. 299 pp.
Epstein, R., Weintraub, A., Sessions, J., Sessions, J.B., Sapunar, P., Nieto, E., Bustamante, F. & Musante, H. 1999a. In Proceedings of the international mountain logging and 10th Pacific Northwest skyline symposium. Edited by J. Sessions and W. Chung. March 28–April 1. Corvallis, Oregon.
Epstein, R., Morales, R., Seron, J. & Weintraub, A. 1999b. Use of OR systems in the Chilean forest industries. Interfaces. 29(1): 7–29.
Jensen, P.A. & Barnes, J.W. 1980. Network flow programming. John Wiley & Sons, Inc., USA.
Kirkpatrick, S., Gelatt, C. & Vecchi, M.P. 1983. Optimization by simulated annealing. Science 220:671–680.
Liu, K. & Sessions, J. 1993. Preliminary planning of road systems using digital terrain models. J. For. Eng. 4:27–32.
Sessions, J. 1985. A heuristic algorithm for the solution of the variable and fixed cost transportation. In Proceedings of the 1985 symposium on systems analysis in forest resources. Edited by Dress and Field. 1985. Society of American Foresters.
Twito, R.H., Reutebuch, S.E., Stephen, E., McGaughey, R.J. & Mann, C.N. 1987. Preliminary logging analysis system (PLANS): overview. Gen. Tech. Rep. PNW-GTR-199. Portland, OR: U.S. Department of Agriculture, Forest Service, Pacific Northwest Research Station. 24 pp.