POST-PARTITION BOUNDARY RELAXATION FOR REAL-TIME CLUSTER-FIRST LARGE-SCALE VEHICLE ROUTING

Large-scale capacitated vehicle routing problems (CVRPs) can require substantially more computation than strict real-time budgets allow, motivating cluster-first decomposition into smaller routing subproblems. Yet decomposition silently fixes a modeling choice: how strongly the resulting cluster boundaries should be enforced. We introduce Post-Partition Boundary Relaxation (PBR), a learning-free mechanism that selectively relaxes these post-partition commitments. Given a fixed partition, PBR scores each customer by its assignment margin, the gap between its strongest and second-strongest cluster assignment, and uses these solver-free ambiguity scores to identify boundaries for joint reoptimization. Rather than moving individual customers directly, PBR reopens selected neighboring cluster pairs and lets the routing solver determine the resulting reassignment. We evaluate PBR on large-scale CVRP instances under strict real-time deadlines. At $N=10,000$ nodes, monolithic optimization requires approximately $18$ seconds, motivating cluster-first decomposition to substantially reduce routing latency. Across 594 instances, PBR shortens routes on 593, reducing mean and median cost by $3.3\%$ relative to strict decomposition. Matched random boundary selection is substantially weaker, showing that the improvement is not explained by additional joint reoptimization alone, but by where reoptimization is applied. The benefit, however, depends on the computational regime. It disappears when the residual time budget cannot absorb the larger merged subproblems. These results show that decomposition quality is not determined by the partitioner alone: post-partition commitment is an independent algorithmic design axis, and inexpensive ambiguity signals can identify where that commitment should be relaxed.