Application of VNS metaheuristic to a VRP with fleet sizing and composition, time windows, tiered costs and multiple compartments in the poultry industry

This paper addresses the Fleet Size and Mix Vehicle Routing Problem with Time Windows, Step Costs and Multiple Compartments (FSMVRPTWSCMC). A mathematical formulation and an approach based on the Variable Neighborhood Search (VNS) metaheuristic, integrated with the Variable Neighborhood Descent (VND), applied to feed distribution in a poultry industry, is proposed. The method combines constructive heuristics, three neighborhood structures, and post-optimization. The experiments evaluated demand levels, fleet availability and contribution from the neighborhoods. With eight vehicles, the approach reduced the average cost by 11.7%, maintaining service of 99.32%. With six vehicles, the service remained above the minimum operational of 95%, while five vehicles resulted in 92.95%. The ablation analysis showed the complementarity of the neighborhoods. The results confirm the adequacy of the fleet and potential of the approach for logistics planning.