Large routing problems are usually solved by cutting them into pieces: split a 5,000-customer instance into small sub-routes, solve each piece with a fast learned solver, and glue the pieces back together. The glue is where things break. When a route has time windows (each customer must be visited within a given interval), a small change near one seam shifts every arrival time downstream. A piece that looked fine locally can make a distant piece infeasible. Geometric modeling met the same problem decades ago with surface patches. Matching only positions at a patch boundary leaves visible creases. The fix was to also match derivatives, and to do it with constraints that involve only the data next to the boundary, so a local edit does not spread across the whole mesh.
This note proposes to bring that fix to combinatorial routing. At each seam, the solver for one piece receives more than where and when the neighboring piece starts. It also receives how fast the rest of the route's cost rises if that start is delayed, plus the latest start that keeps the rest feasible. That signal is the analogue of a first-derivative ($C^1$) boundary condition. It is computable in closed form from the neighbor's current solution. Its form is the same across problem types: a resource level, the marginal cost of that resource, and a hard limit. The resource is time for time-window problems, remaining capacity for capacitated vehicle routing, and remaining travel budget for orienteering. So a single interface design could serve many routing variants, which is where the cross-problem question comes in.
Core Claim
Divide-and-conquer neural solvers fail on tightly coupled constraints because their seams carry only zeroth-order information, meaning which node connects to which. The piece being solved cannot see how its exit state is priced by the rest of the route. We claim that conditioning each local solver on a first-order seam condition and iterating recovers most of the feasibility and quality lost at seams on time-window routing. The condition consists of the incoming resource level, the slope of the downstream cost-to-go with respect to that level, and the latest feasible level. We further claim that this gain grows with constraint tightness and disappears on unconstrained TSP, where the slope is identically zero. That second claim is what separates a real mechanism from extra tuning.
Stated formally, let $V_j(t)$ be the cost of the remainder of the route after seam $j$, given that the route crosses seam $j$ at resource level $t$ (for example, departure time). The local solver for the piece ending at seam $j$ minimizes its own cost plus a Hermite-style local model of $V_j$:
$$ \min_{\pi}\; c(\pi) + V_j(\bar t_j) + V_j'(\bar t_j)\,\big(t_j(\pi)-\bar t_j\big) \quad \text{subject to}\quad t_j(\pi)\le T_j^{\max}, $$
In this objective, $\pi$ is the local sub-route, $c(\pi)$ is its cost, $t_j(\pi)$ is the resource level it produces at the seam, $\bar t_j$ is the level in the current global solution, $V_j'$ is the slope, and $T_j^{\max}$ is the latest feasible level. For time windows with soft lateness penalties, $V_j$ is piecewise linear in $t$. Its slope is zero while downstream waiting slack absorbs the delay. After that, the slope equals the penalty rate times the number of downstream customers that would become late. It can therefore be computed by one forward pass over the neighbor's route.
We deliberately stop at first order. A characterization of connecting maps as nonlinear roots of the identity shows that curvature-level continuity at a junction of many patches forces a large jump in polynomial degree. We read that result as a constraint on this design: higher-order seam conditions cost far more than they buy. In our setting, the kink structure of piecewise-linear cost-to-go is better captured by the explicit hard limit $T_j^{\max}$ than by a curvature term.
Relation to Prior Work
The closest existing work is UDC. It uses a graph network to split instances across ten problem classes, solves pieces with small constructive models, and repairs seams by rolling the cut points so that old seams become piece centers in the next pass. It reports a gap of roughly 2.5% relative to LKH3 on 2,000-node TSP and 4.05% on 100,000-node TSP. According to the research file, the UDC authors also note that this discrete rolling does not handle time-window coupling. UDC motivates this proposal and supplies the backbone. We keep its divider and its reunion schedule and change only what information crosses a seam. Imitation Improvement Learning for Large-Scale CVRP decomposes very large capacitated routing instances by clockwise clustering, reaching up to 30,000 customers. Its pieces likewise see no priced boundary state.
The geometric side supplies the method rather than the domain. In Adaptive Reconstruction of Surfaces and Scalar Fields from Dense Scattered Trivariate Data, cross-boundary derivatives depend only on control points adjacent to the shared face, so imposing local collinearity guarantees $C^1$ continuity without global propagation. Our seam slope plays the same role: it is computed only from the neighbor route and is enforced only in the adjacent piece. Ellipse-preserving Hermite interpolation and subdivision shows that joint value-and-derivative data at knots, in a well-chosen basis, gives high accuracy with very small support. This motivates passing exactly the (value, slope) pair per seam. Learning Residual Elastic Warps for Image Stitching under Dirichlet Boundary Condition is the learned-model precedent: neural thin-plate-spline warps tear at patch edges unless boundary control points are constrained. The authors report 24.84 dB mPSNR and a 0% failure rate on UDIS-D once the constraint is added. We borrow the lesson that a learned local model needs explicit boundary data to behave at seams. Their boundary condition fixes only the value, and ours adds the derivative. The PDE blending works, Real-time surface manipulation with C1 continuity and Analytical C2 Continuous Surface Blending, enforce continuity through closed-form solutions of high-order equations. We do not use PDEs, because routing seams have no continuous domain to blend over. We keep only the principle of a boundary condition on value plus derivative.
On the cross-problem side, CaDA solves 16 routing variants with one model by adding a 5-dimensional constraint indicator vector to the input. It reports a 3.32% average gap on CVRPLib at 16 to 200 nodes. CaDA is our local solver, and its prompt vector tells the solver which constraints exist. Our seam tokens tell it what those constraints cost at the boundary, which a prompt cannot express. DIFU-Ada transfers a TSP-trained diffusion solver to prize-collecting TSP and orienteering by adding penalty gradients during sampling. It lowers the PCTSP-20 gap from 19.21% to 4.20%. That is the natural "just add a penalty" alternative, and it operates on whole instances rather than seams. EFLOCO and Geometric Algorithms for Neural Combinatorial Optimization with Constraints both relate continuous representations to discrete solutions, but globally per instance. Neither addresses partition interfaces. Portfolio Optimization with Translation of Representation connects different search representations through abrupt projections, a different kind of interface from ours. Finally, Beyond the Heatmap is a constraining result. It shows that a parameter-free nearest-neighbor prior with tuned tree search matches learned priors on TSP-10000, with a 2.14% gap versus 2.37% for DIFUSCO. Any learned addition must therefore beat well-tuned plain search, and we design the baselines accordingly.
Research Program
The system has three parts. The first is UDC's divider and reunion schedule, used unchanged. The second is a seam oracle. Given the current global route, it computes for each seam the resource level, the downstream slope, and the latest feasible level in one linear-time pass. Time windows use waiting-slack propagation, capacitated routing uses remaining load against cheapest refill detours, and orienteering uses remaining budget against the prize lost per unit of budget. The third is a CaDA local solver extended with two seam tokens, one per end of the piece. Each token embeds the triple (level, slope, limit). The solver is trained on sub-instances cut from larger generated instances, with seam triples computed from the reference solutions of the surrounding pieces. The training reward is local cost plus the linearized downstream term above, with infeasibility against $T^{\max}$ masked.
At inference, pieces are solved, seams are recomputed, and pieces are re-solved on UDC's rolled schedule. This is effectively a block-coordinate scheme where each block sees a first-order model of its neighbors. The analysis question is when this loop converges. We expect convergence when slopes change slowly between passes, and we will measure how much the seam triples move per pass.
Cross-problem applicability is tested by one trained model with shared seam tokens across time-window routing, capacitated routing, and team orienteering with time windows. The constraint prompt selects the variant, and the seam semantics change with the resource.
Baselines
The naive reference is independent pieces with no reunion. Each piece is solved by the same CaDA solver and concatenated. This measures the raw seam penalty.
The strongest existing method is UDC with its rolled reunion. We run it with the same divider, the same number of reunion passes, and a CaDA local solver that has the time-window prompt but no seam tokens. The solver is trained on the same generated data for the same number of steps. As a result, the only difference from our method is the seam information. On TSP, UDC reports about 2.5% gap to LKH3 at 2,000 nodes and 4.05% at 100,000 nodes. For time-window routing, no reported result found on Lacuna for UDC on TSPTW or any large time-window benchmark. We therefore run it ourselves. Beating it means a lower infeasibility rate and a lower gap to a long-run classical solver at equal wall-clock time, on instances with 1,000 to 5,000 customers.
The key ablation is value-only seams. The seam tokens carry the resource level and latest limit but set the slope to zero. This is the zeroth-order analogue, and it isolates whether the derivative matters or whether simply exposing the boundary state does all the work. A second ablation replaces the computed slope with a learned scalar predicted from the neighbor's embedding. This tests whether the closed-form computation matters.
The search-strength baseline is a tuned classical repair applied to every variant's stitched output under an identical time budget. We use the HGS-style local search used by the IIL line, with its parameters tuned by the same automated configuration budget for all methods. This follows the lesson of Beyond the Heatmap. Improvements must survive the repair step, not just appear before it. Finally, CaDA run directly on whole instances gives the monolithic reference at the sizes where it fits. Its reported CVRPLib average gap is 3.32%.
Why not just…?
Why not just run more reunion passes, as UDC does? Rolling cut points moves seams, but every piece still sees only node connectivity. A delay pushed across a seam is invisible until the next pass, which can push it back, so the loop can oscillate rather than converge. We will run UDC with up to four times our pass count at matched wall-clock time. If extra passes close the gap on tight time windows, the proposal's claim is wrong, and the experiment reports that honestly.
Why not just add a lateness penalty to each piece's objective, in the spirit of DIFU-Ada's energy guidance? A penalty on the piece's own customers does not price the delay it causes downstream. That price is exactly the slope, and it is zero when slack absorbs the delay and steep when slack is exhausted. A uniform penalty is either too weak or too strong across seams. The fixed-penalty variant is run as a baseline with its weight tuned on validation data. Since it is a real threat on loose windows, the tightness sweep below decides where each wins.
Why not just repair the stitched route with strong classical local search? This is the most serious alternative. On TSP, tuned plain search already rivals learned components, as Beyond the Heatmap shows. We apply the same repair to every method under the same budget. The proposal succeeds only if first-order seams still help after repair, for example by starting repair from a feasible route more often, which on tight windows is where local search tends to struggle. If repair erases the difference, we will conclude that the contribution is at most a speed gain, and report it that way.
Why not just rely on CaDA's constraint prompt? The prompt tells a solver that time windows exist, not how much a minute of delay costs at a specific boundary. It also has no way to see state outside the piece. The value-only ablation already covers the richest prompt-like boundary input, so this alternative is subsumed by that comparison.
Proposed Experiments
The main benchmark is large generated time-window routing, meaning TSPTW and routing with capacity plus time windows. Instances are built by tiling CaDA-style time-window generators to 1,000, 2,000, and 5,000 customers. We use a tightness parameter that scales window width from loose to very tight. The metrics are the fraction of instances returned feasible, the gap to a long-run HGS or LKH3 reference, and wall-clock time.
The first decisive check is the tightness sweep. The advantage over value-only seams and over UDC should be near zero on loose windows and grow monotonically as windows tighten. Any other pattern means the slope is not the operative ingredient.
The second check is a negative control on plain TSP from TSPLIB and on generated instances up to 2,000 nodes. There the slope is identically zero, so our method should match UDC's reported quality and not exceed it. An improvement there would signal an unfair comparison, for example extra training, rather than a real mechanism.
The third check is cross-problem. One model is trained on time-window routing and capacitated routing and evaluated on the CVRPLib instances CaDA uses and on the uniform-random datasets from the IIL work. It is then evaluated zero-shot on the Montemanni–Gambardella and Righini–Salani team orienteering instances (48 to 288 nodes) used by ADOPT. For those instances ADOPT reports 11 new best-known solutions but no aggregate gap, so no reported result found on Lacuna for a gap baseline there. We compare against the best-known scores directly. Transfer counts as supported if shared seam tokens help on the held-out resource type relative to the value-only ablation.
We will also report the per-pass movement of seam triples. This shows whether the coordination loop settles, and whether its failures concentrate at seams where the downstream cost-to-go has a kink near the current level. The first-order model predicts that such seams are the hardest.
References
- A characterization of connecting maps as nonlinear roots of the identity
- UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems
- Imitation Improvement Learning for Large-Scale Capacitated Vehicle Routing Problems
- Adaptive Reconstruction of Surfaces and Scalar Fields from Dense Scattered Trivariate Data
- Ellipse-preserving Hermite interpolation and subdivision
- Learning Residual Elastic Warps for Image Stitching under Dirichlet Boundary Condition
- Real-time surface manipulation with $$C^{1}$$ continuity through simple and efficient physics-based deformations
- Analytical C2 Continuous Surface Blending
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
- Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation
- Efficient Few-Step Solution Generation via Discrete Flow Matching for Combinatorial Optimization
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints
- Portfolio Optimization with Translation of Representation for Transport Problems
- Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solvers
- ADOPT: Combining parameter tuning and Adaptive Operator Ordering for solving a class of Orienteering Problems