Voronoi-Based Roadmap Generation for Multi-Criteria Off-Road Vehicle Routing in Forest Stands: A Case Study from Kampinos Forest, Poland

Route planning through forested terrain is an important problem in military operations and crisis management, since it requires accounting not only for terrain morphology but also for the spatial distribution of individual trees and the characteristics of the moving vehicle. Existing trafficability models typically represent forest as a generalized land-cover class, which cannot capture the specific tree gaps and local slopes that determine whether a given vehicle can actually pass. This study proposes a routing method based on a Voronoi graph constructed from individual tree locations, in which each edge is characterized by length, terrain slope, clearance between neighboring trees, and canopy concealment, combined into a multi-criteria cost function that also penalizes vehicle turning. The graph is adapted to a specific vehicle by removing edges that violate its width or maximum slope constraints. The method was tested on four plots in Kampinos Forest, Poland, and five vehicle types. Feasible routes were obtained for all 20 area–vehicle combinations, with Dijkstra’s and A* algorithms returning identical solution costs, and route length exceeding the straight-line distance by a modest margin in most cases. Graph size scaled near-linearly with tree count. Vehicle width and slope tolerance affected feasibility and route length through separate mechanisms, while terrain scale governed computational cost. A sensitivity analysis showed that cost-function weights influence routes differently depending on terrain, and that the slope and concealment criteria interact rather than acting independently. The proposed approach enables vehicle-specific route modelling in forested terrain at the resolution of individual trees, rather than generalized land cover.