Fix-and-Optimize with Arc Reduction for the VRPTW: An Approach to Mitigate Tailing-Off in MILP Formulations

The Vehicle Routing Problem with Time Windows (VRPTW) is a logistics cornerstone traditionally focused on strict fleet minimization. This paper proposes a two-phase tactical matheuristic prioritizing operational efficiency (distance) and computational robustness. The method integrates structural pre-processing for spatiotemporal arc elimination and a Fix-and-Optimize strategy guided by the Gurobi solver. Experiments on the 56 classical Solomon instances (100 customers) compared this approach against the monolithic MILP model. Results indicate the matheuristic mitigates the tailing-off phenomenon, decreasing timeout interruptions by 78% while producing solutions with a 1.56% average distance reduction for the most challenging instances. Topological analysis revealed that instances with loose time windows (Type 2) exhibit greater elasticity for reoptimization (1.62%) compared to highly constrained instances (Type 1, 0.99%). The results suggest that solutions with greater flexibility in fleet utilization may lead to relevant reductions in total distance, highlighting a potential trade-off between fixed and variable costs in logistical scenarios.