Local search algorithm for the problem of covering a polygon with a forest of rooted trees
Abstract
Local search algorithm for the problem of covering a polygon with a forest of rooted trees
Incoming article date: 21.09.2022The article considers the problem of optimizing the scheme of portages in a cutting area. The mathematical model of the cutting area is a polygon - a bounded closed broken part of the plane. The portage scheme corresponds to a root graph (forest, tree) of a special type. We have introduced the concept of covering a polygon with a rooted forest. The cover is interpreted as the possibility of cutting and collecting all the trees in the cutting area while moving the harvester and forwarder along the trails. The trails are laid according to the found covering root forest. Two variants of the algorithm for solving the problem are proposed, which are a modification of the local search. The first algorithm uses the greedy method we described earlier[18] to find the underlying solution. The second algorithm uses the branch and bound method to find the basic solution. Comparative experiments were carried out on polygons sized 12x12 and 18x18. Experimental results show that both modifications of the algorithm improve the basic solution. The first algorithm improves the solution by an average of 11% for a 12x12 polygon and by 24% for a 18x18 polygon.
Keywords: portage schemes, cutting area, polygon covering the root forest, local search, coverage