A heuristic approach to automated forest road location

An optimization problem arising when planning forest harvesting operations is the location of new access roads. The new roads must cover several areas to be harvested at minimum cost. This problem is of economical and environmental relevance in the domain of forestry. In this study, the problem is expressed as a P-forest problem in a graph. It consists of determining a set of tree structures in a graph that covers a set of vertices corresponding to harvest areas. The objective is to minimize the sum of construction costs and harvesting costs. In addition to the location of roads, the P-forest problem has several relevant applications, including public transport, electricity transmission, roads, pipelines, and communication networks design. This paper presents a greedy randomized adaptive search procedure (GRASP) to solve this problem. The heuristic was implemented on a decision support system, and computational experiments were conducted on randomly generated and real instances to demonstrate the performance and practical efficiency of the proposed approach. A comparison with manually designed forest road networks in the real instances shows a clear advantage for the proposed method.