This study is the first to formally investigate the First-Segment-Then-Aggregate (FSTA) decomposition technique to accelerate iterative heuristics for solving the Vehicle Routing Problem (VRP). Specifically, we aim to reduce unnecessary computation by retaining stable solution segments and focusing only on unstable segments. To identify stable segments, we introduce a novel neural network framework called Learning-to-Segment (L2Seg). L2Seg comes in three variants (non-autoregressive, autoregressive, and synergistic), and experimental results on the CVRP and VRPTW problems demonstrate that L2Seg speeds up state-of-the-art solvers by a factor of 2 to 7.