INTEGRATION OF CLUSTERING SEARCH AND PATH RELINKING ALGORITHMS TO SOLVE THE VEHICLE ROUTING PROBLEM IN A FOREST INVENTORY

The planted tree sector plays a strategic role in the Brazilian economy, requiring constant monitoring of forest areas. This monitoring is carried out through the forest inventory, an activity that requires the displacement of measurement teams from the company's headquarters to the fields. Proper planning of this process makes it possible to reduce routes and, consequently, operating costs. Forest Inventory Planning (PIF) can be modeled as a variant of the Vehicle Routing Problem (PRV), more specifically the Periodic Vehicle Routing Problem with Time Window (PRPVJT).
This work proposes a hybrid approach to the resolution of PRV-PIF. It is the integration between the Clustering Search (CS) meta-heuristic and the Path Relinking (PR) intensification strategy. The proposed method is called CS+PR and uses Simulated Annealing (SA) as a solution generator algorithm and the Hamming distance to measure similarity in the clustering phase. The methodology was evaluated in a set of nine instances with varying dimensions, including small, medium and large scenarios, with a limit of up to 2016 plots, 252 days of time horizon and three work teams.
The computational experiments demonstrated the robustness and consistency of the CS+PR algorithm, which obtained viable solutions for all instances