CS Paper Radar

Strengthening Compact Vehicle Routing Formulations through Arc-Flow Aggregation and Refinement

Julian Yarkony, Willem-Jan van Hoeve, Anthony Karahalios, Martin Karyamsetty, Soheyl Khalilpourazari, Louis-Martin Rousseau, Xiaohang Zhu

cs.DM math.OC ·submitted 2026-11-15 23:17 UTC · v1

Abstract

Arc-flow formulations can provide strong relaxations for mixed-integer program formulations of vehicle routing problems, but the associated networks may be prohibitively large. We study the setting in which multiple arc flow relaxations may be applied, and introduce a dual-guided aggregation and refinement framework that constructs substantially smaller arc-flow formulations while recovering the LP bound of the original networks. Dual information is used both to identify states that can be aggregated without weakening the bound and to guide node disaggregation. We show that the resulting procedure converges finitely to the arc-flow bound of the full arc-flow formulation. The framework retains the original decision variables, allowing cutting planes to be added directly in the original variable space. Moreover, it produces an explicit MILP formulation without relying on column generation or pricing to determine the arc-flow relaxation bound. We apply our approach to the vehicle routing problem with time windows for which we define two arc flow relaxations, as well as two families of cutting planes over the original variable space. Computational experiments show that strong bounds can be obtained using substantially aggregated networks. The resulting root bounds are competitive with those obtained by the branch-and-price solver RouteOpt, while retaining a formulation that can be solved directly by a general-purpose MILP solver.

Comment
47 pages. Submitted to Transportation Science

Closest papers

Nearest neighbours by meaning across the whole index.

Mixed-integer flow formulations for motion planning and decision-making of networked multi-agent systems

cs.MA ·2026-09-21 ·Angelo Caregnato-Neto, Paul-Louis Delacour, Raf Van de Plas, Tamás Keviczky, Janito Vaqueiro Ferreira
similarity 0.69
Abstract

This work investigates the use of flow-based connectivity maintenance constraints in mixed-integer linear programming (MILP) trajectory planning and decision-making models for networked multi-agent systems (MAS). We integrate flow-based encodings for standard and k-hop connectivity into MILP multi-vehicle maneuvering models that are widely used alongside receding horizon planning strategies. Their necessity and sufficiency is demonstrated, guaranteeing full coverage of potential network topologies. The flow formulation for standard connectivity decreases the growth of the required inequality constraints from exponential to polynomial w.r.t. the size of the MAS when compared to the state-of-the-art subtour elimination (SEC) method. The flow-based k-hop connectivity constraints decrease the number of required binary variables and decouple its growth from the number of hops. However, the impact of these formulations in performance is not straightforward due to the introduction of a substantial number of continuous flow optimization variables and, in the case of k-hop connectivity, additional inequality constraints. We investigate this trade-off through a statistical evaluation of costs and optimization times using a conventional branch-and-bound commercial solver and trials performed with randomized environments for increasingly larger MAS. The results show that the flow formulation outperforms SEC in standard connectivity problems, enabling the solutions to be computed for larger MAS considering the imposed optimization time limit. The reduction in number of binary variables enabled by the k-hop flow formulations decreases the theoretical worst-case number of iterations required by the branch-and-bound algorithm to compute the global optimal solution. Our results show that this advantage did not translate into improvements in the average performance when compared to the baseline.

0.20

Stochastic Corridor Time Network Capacity Planning for Low Altitude Airspace Systems

cs.CE ·2026-08-11 ·Yipu Yao, Li Ding, Yanlu Zhao
similarity 0.66
Abstract

Regulators in China, the United States, and the European Union now provide low-altitude airspace access as priced, time-windowed corridor authorizations, booked in advance and forfeited if unused. We ask how much capacity a UAV logistics planner should reserve on each corridor--time unit before demand is realized, to maximize expected profit net of reservation cost. Reserved capacity cannot be transferred across corridors or time windows and is consumed jointly along time-respecting paths, so reservations are coupled through the network in ways that models with exogenous airspace capacity cannot capture. We formulate a two-stage stochastic program whose recourse selects and routes accepted requests on a time-expanded network, prove its arc-based and path-packing forms equivalent, and solve it by Benders decomposition with column-generated subproblems. The decomposition operates on the LP relaxation, and all reported reservation and routing decisions are recovered as integer plans. Computational experiments achieve single-digit LP-Benders gaps on moderate-sized networks and extend to much larger instances through a truncated-path approach. A Shenzhen case study shows reservations concentrating on structurally central corridors, with demand level and reservation price having more influence on the quantity of capacity reserved than the selection of corridors.

0.04

Depot-Closed Multi-Component Construction for Neural Vehicle Routing

cs.LG ·2026-09-28 ·Shinichiro Hamada, Hisashi Kashima
similarity 0.64
Abstract

Most neural constructive solvers for the vehicle routing problem (VRP) use route-by-route construction, extending one route until completion before starting the next. This commits route membership early and hinders global coordination across routes. We propose multi-component construction, which maintains many route components simultaneously and merges them in an arbitrary order. This removes the depot-return cue that route-by-route construction obtains from the remaining capacity; to compensate, we introduce an interpretation in which every component is treated as an implicitly depot-closed route. Under this depot-closed interpretation, every intermediate state of standard CVRP construction is a complete feasible solution, and the exact cost reduction of a merge is the Clarke-Wright saving. The neural policy combines this CW-saving signal with the evolving component state to learn what to connect and when to connect. A policy trained only on CVRP100 outperforms the reported results of representative neural solvers on CVRP100-500 with greedy inference and, reused for ruin-and-reconstruct, performs strongly at all evaluated sizes up to CVRP1000. In a zero-shot Constraint Tightness evaluation with capacities from $C=10$ to $500$, it outperforms the reported neural solvers at every capacity. Controlled analyses show that robustness persists without CW grounding and point to learned route-closing behavior as a plausible contributor to the tight-regime degradation of learned route-by-route solvers.

0.26

On the Delay-Constrained Maximum Concurrent Flow Problem

cs.NI math.OC ·2026-09-04 ·Walid Ben-Ameur, Guillaume Beraud-Sudreau, Hervé Kerivin, Sebastien Martin
theory similarity 0.62
Abstract

Real-time services, such as VoIP and large-scale neural network training, require strict transmission delay guarantees. While routing under hop constraints is tractable, real-world delays increase sharply with equipment load, typically modeled using the M/M/1 queuing function where delay is inversely proportional to available bandwidth. We investigate the resulting Delay-Constrained Maximum Concurrent Flow (DCMCF) problem, which seeks to maximize the minimum throughput across all commodities. The problem's complexity stems from the conditional and non-linear nature of the delay constraints, which are active only along the specific paths used by the flow. We prove that DCMCF is strongly NP-hard, even for single-source/single-destination instances. To address the inherent non-convexity of the problem, we introduce a new convex relaxation expressed through second-order cone constraints, obtained from the convex envelope of a function representing the conditional delay associated with a single arc of a given path. The relaxation is shown to outperform existing formulations based on disjunctive programming. Leveraging this result, we develop a polynomial-time approximation algorithm with a provable performance guarantee and present numerical experiments demonstrating the effectiveness of the proposed approach.

0.31

Single-level reformulations for network pricing under Wardrop equilibrium with separable affine costs

cs.GT math.OC ·2026-10-19 ·Miguel F. Anjos, José Neto
benchmarktheory similarity 0.61
Abstract

We consider the problem of setting tolls on a subset of the arcs of a congested network so as to maximize the revenue of a network authority, anticipating that users route according to a Wardrop equilibrium. This problem is naturally cast as a bilevel program in which the leader sets tolls while the followers respond by choosing an equilibrium routing. We focus on the important special case of separable affine arc cost functions. Under this assumption, Wardrop equilibria admit Beckmann's convex characterization, from which we derive three new single-level reformulations of the bilevel problem, exploiting both Beckmann's formulation and its dual: an arc-based formulation, which we solve exactly, and two path-based formulations, solved by column-and-constraint generation. Beyond the reformulations, we further derive from Beckmann's potential an upper bound on the optimal revenue that can be used to certify optimality gaps across all formulations. An extensive computational study on instances derived from the Sioux Falls and Eastern Massachusetts networks compares our formulations with the recent mixed-integer nonlinear formulation of Beck, Labbé and Schmidt. The arc-based formulation solves substantially more instances to proven optimality (within a time limit of 1800 s) than this formulation and, unlike it, returns a feasible solution on every instance. It remains effective on the largest, 74-node network, on which the formulation of Beck et al. solves none. The magnitude of the upper bounds on the tolls proves to be a major driver of tractability: the genuinely hard core of the benchmark emerges once the regulatory cap on tolls is removed. The two path-based formulations, used as heuristics, return a solution within one percent of the optimum on every instance whose optimal value is known, often in seconds where exact formulations reach the time limit.

0.24

KAYROS: An Anytime and Exact Solver for the Time-Dependent Vehicle Routing Problem with Time Windows - Extended Version

cs.MS math.OC ·2026-09-01 ·Florian Rascoussier, Romain Billot, Lina Fahed, Christine Solnon
theorycode/data similarity 0.61
Abstract · v3: 93 pages, 4 figures, 12 tables. Updated authorship, affiliations, ORCID identifiers, acknowledgements and references. No new experiments…

The Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW) captures a central difficulty of urban logistics: travel times vary with the time of day, so the cost of a route depends on when it is driven. This paper introduces KAYROS, an open-source solver for the duration-minimization TDVRPTW that is both anytime and exact. It returns improving valid solutions throughout its time budget and can close instances with conditional computational optimality certificates through an integrated branch-price-and-cut component. We extend the composition of continuous arrival-time functions from the literature, previously described only at proof or proposition level, to the left-continuous functions that stepwise benchmarks require. We prove that the composition routine shipped in the checker computes that operation exactly. We analyze when its evaluation and breakpoint normalization are exact in IEEE-754 double-precision arithmetic, and argue that a canonical, epsilon-free checker must define the objective. The anytime layer combines greedy construction, granular time-dependent local search over balanced route trees, and iterated local search, with a fleet-aware descent for a fleet-cost objective. We further propose an anytime evaluation methodology based on a normalized signed primal integral under a pre-committed statistical design. On 212 instances from five families at a one-hour single-threaded budget, KAYROS achieves a pooled anytime score 63.3% lower than the strongest of three available contenders (Timefold, Hexaly, jsprit). All three contrasts are significant under Holm correction. KAYROS improves all 30 high-effort references of Blauth et al. and 10 literature best-known solutions, and publishes 704 such certificates. The solver, benchmarks and campaign data are openly released.

0.32

Optimizing the Steady-State Travel Time of Nash Flows over Time with Capacity Increases

cs.DS ·2026-11-09 ·Niklas Dahlmeier, Paul Paschmanns, Laura Ritter, Ruben Skorupinski
similarity 0.61
Abstract

We study budgeted capacity augmentation for single-source single-sink \NFOTs under constant inflow $u_0$. The goal is to increase capacities on arcs subject to a global budget constraint in order to minimize the steady-state travel time in the network. We show that this problem is weakly NP-hard on series-parallel networks and provide an exact pseudopolynomial algorithm as well as a fully polynomial algorithm that attains the optimum travel time for budget $B$ while spending at most $B + \varepsilon\cdot\max\{B,u_0\}$. On general networks the problem becomes strongly NP-hard. Moreover, unless $\text{P} = \text{NP}$, for every fixed $\varepsilon \in (0,1)$, no polynomial-time algorithm can achieve the optimal steady-state travel time while exceeding the budget by at most a factor of $n^{1-\varepsilon}$. Lastly, we give structural properties about steady-state travel time under varying arc capacities. We identify capacity thresholds determined by subsets of $s$-$t$-cuts and show that the travel time is constant in the interior of the cells resulting from the corresponding hyperplane arrangement.

0.24

Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization

cs.AI ·2026-09-28 ·Jiale Zhao, Sirui Mao, Zimu Chen, Wentao Yang, Zihan Wang +3 more
similarity 0.60
Abstract · 31 pages, 5 figures

Large-scale routing problems are difficult to solve efficiently as their search spaces grow rapidly with problem size. Existing approaches primarily improve the optimization procedure itself, often at increasing computational cost. We instead shift the focus to a useful initialization that can be refined into a high-quality solution with limited downstream refinement. We propose Just Initialize, a training-free and solver-agnostic initialization component for large-scale routing optimization. Just Initialize compresses a large routing instance into a compact surrogate space, optimizes its global routing structure, and recovers the resulting solution as an optimization-friendly starting point in the original space. Extensive experiments on Traveling Salesman Problems (TSPs), Capacitated Vehicle Routing Problems (CVRPs), Vehicle Routing Problems with Time Windows (VRPTWs), and Prize-Collecting Traveling Salesman Problems (PCTSPs) demonstrate that Just Initialize achieves high-quality solutions comparable to or better than state-of-the-art methods while substantially reducing computational cost across instances ranging from 1K to 100K nodes, including an average speedup of approximately 70$\times$, sub-second runtimes on 10K-node instances, and runtimes within tens of seconds on 100K-node instances.

0.19