pith. sign in

arxiv: 2604.23748 · v1 · submitted 2026-04-26 · 🧮 math.OC

Enforcing TSP-Optimality in Fair Vehicle Routing by Cutting Planes

Bart van Rossum , Rui Chen , Andrea Lodi This is my paper

Pith reviewed 2026-05-08 05:53 UTC · model grok-4.3

classification 🧮 math.OC
keywords fair vehicle routingTSP-optimalitycutting planesbranch-price-and-cutcapacitated VRPrange minimizationroute dominanceexact methods
0
0 comments X

The pith

TSP-optimality cuts eliminate dominated routes and solve fair vehicle routing instances to near-optimality.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The fair capacitated vehicle routing problem aims to minimize the range between the longest and shortest routes served by a fleet. Because the range objective is non-monotonic, optimal solutions can include routes that are artificially lengthened and therefore not shortest possible for their customers. The paper develops a branch-price-and-cut framework that adds TSP-optimality cuts to forbid TSP-dominated arc sequences and uses a lifting procedure to strengthen those cuts. On benchmark sets with up to 25 customers the algorithm reaches optimality on nearly all instances and leaves an average gap of 0.27 percent on the most difficult ones. This approach matters because it prevents wasteful detours while still producing fair assignments of work across vehicles.

Core claim

The authors introduce TSP-optimality cuts inside a branch-price-and-cut algorithm for the fair capacitated vehicle routing problem. These cuts forbid any arc sequence that a traveling-salesman solution would dominate, thereby enforcing that every route in the fleet is shortest possible for the customers it serves. A dedicated lifting procedure strengthens the cuts. The resulting method solves nearly all instances with up to 25 customers to optimality and reports an average gap of 0.27 percent on the hardest configurations.

What carries the argument

TSP-optimality cuts that forbid TSP-dominated arc sequences, strengthened by a dedicated lifting procedure, embedded in a branch-price-and-cut framework.

If this is right

  • Every route in an optimal fair solution is guaranteed to be a shortest path for its assigned customers.
  • The non-monotonic range objective can be optimized without generating artificial detours.
  • Instances with up to 25 customers are solved to optimality or to an average gap of 0.27 percent on the hardest cases.
  • The lifted cuts remain valid across all pricing subproblems in the branch-price-and-cut tree.
  • Computational effort stays tractable because the cuts are added only when violated and are strengthened once per separation round.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same cut family could be applied to other non-monotonic objectives such as minimizing maximum route length or balancing load under different metrics.
  • Combining the cuts with column-generation heuristics might produce high-quality solutions for instances larger than 25 customers.
  • The lifting procedure might generalize to related dominance conditions in time-window or prize-collecting variants of the problem.
  • If the cuts prove strong enough, the framework could serve as a template for exact solution of other fairness-constrained routing models.

Load-bearing premise

The generated TSP-optimality cuts, even after lifting, remove every non-TSP-optimal route without excluding any globally optimal fair solution, and the pricing and separation routines remain fast enough on the tested sizes.

What would settle it

Discovery of a feasible fair solution with objective value strictly better than any solution produced by the algorithm that still contains a non-shortest route for its customers.

Figures

Figures reproduced from arXiv: 2604.23748 by Andrea Lodi, Bart van Rossum, Rui Chen.

Figure 1
Figure 1. Figure 1: Instance with two vehicles where TSP-suboptimality reduces the range. are compatible with any arc- or route-based formulation in which TSP-optimality must be enforced. The remainder of this paper is structured as follows. We formally define the F-CVRP(-TSP) in Section 2, and present the branch-price-and-cut framework of Van Rossum et al. [12] in Section 3. We introduce the TSP-optimality cuts and a separat… view at source ↗
Figure 2
Figure 2. Figure 2: Forward lifting of a TSP-optimality cut. Solid arrows show the TSP-violating path 𝑃 = (0, 𝑣1 , 𝑣2 , 𝑣3 ), which is longer than the path (0, 𝑣2 , 𝑣1 , 𝑣3 ). Dashed arrows are arcs lifted via route elementarity: they cannot coexist with all arcs of 𝑃 in an elementary route. The dotted arrow (𝑣2 , 𝑣4 ) is lifted via TSP￾optimality: the path (0, 𝑣1 , 𝑣2 , 𝑣4 ) is longer than (0, 𝑣2 , 𝑣1 , 𝑣4 ). 𝑥(Δ+ 𝑘 (𝑃 )) = … view at source ↗
read the original abstract

We study the fair capacitated vehicle routing problem, in which a fleet of vehicles must serve a set of customers such that the difference between the longest and shortest route, the range, is minimized. A key challenge is that the range objective is non-monotonic: it can be reduced by artificially lengthening routes, leading to solutions that violate TSP-optimality of individual routes. Existing exact methods struggle to handle this efficiently. We propose a branch-price-and-cut framework that enforces TSP-optimality through TSP-optimality cuts, which forbid TSP-dominated arc sequences. We strengthen the cuts through a dedicated lifting procedure. Computational experiments on benchmark instances with up to 25 customers show the method solves nearly all instances to optimality, achieving an average gap of 0.27% on the hardest configurations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper introduces a branch-price-and-cut algorithm for the fair capacitated vehicle routing problem that minimizes the range (difference between longest and shortest route lengths). It develops TSP-optimality cuts to forbid TSP-dominated arc sequences in routes and strengthens them with a dedicated lifting procedure. The key justification is that, for any fixed customer-to-vehicle assignment, an optimal fair solution always exists in which every route is a shortest tour; the cuts enforce this without excluding globally optimal solutions. Computational tests on benchmark instances with up to 25 customers report that nearly all instances are solved to optimality, with an average gap of 0.27% on the hardest configurations.

Significance. If the cuts correctly describe the convex hull of TSP-optimal routes and remain separable in reasonable time, the framework offers a principled exact method for non-monotonic objectives in vehicle routing. The approach exploits a structural property of the range objective to avoid artificial lengthening of routes, which is a recurring difficulty in fair optimization. The reported solution rates on instances up to 25 customers suggest the method is already practical for moderate sizes and could serve as a foundation for larger-scale fair routing applications.

major comments (1)
  1. [Computational Experiments] Computational Experiments section: the claim that the method 'solves nearly all instances to optimality' with a 0.27% average gap on the hardest configurations is difficult to evaluate because the text provides no information on cut separation times, the number of cuts generated per instance, the criteria used to designate 'hardest configurations,' or any measure of statistical variability across runs or random seeds.
minor comments (2)
  1. [Abstract] Abstract and §3: the phrase 'TSP-dominated arc sequences' is used without an explicit definition or small illustrative example in the opening paragraphs; adding one would improve accessibility.
  2. [§3.2] The lifting procedure in §3.2 is presented algorithmically, but the manuscript does not state whether the lifted inequalities are facet-defining for the TSP-optimal route polytope or merely valid.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive overall assessment and for highlighting opportunities to improve the clarity of our computational results. We address the major comment below.

read point-by-point responses

  1. Referee: Computational Experiments section: the claim that the method 'solves nearly all instances to optimality' with a 0.27% average gap on the hardest configurations is difficult to evaluate because the text provides no information on cut separation times, the number of cuts generated per instance, the criteria used to designate 'hardest configurations,' or any measure of statistical variability across runs or random seeds.

    Authors: We agree that these details are necessary for a complete evaluation. In the revised manuscript we will augment the Computational Experiments section with the following: average and maximum cut separation times (both per instance and aggregated); the number of TSP-optimality cuts generated (reported as means and ranges); an explicit definition of the 'hardest configurations' as the 25-customer instances, which were identified a priori by the largest solution times and gaps in preliminary runs; and a statement that the algorithm is deterministic with no random components, so no statistical variability across seeds exists. These additions will be presented in both text and a supplementary table. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core derivation rests on a direct mathematical argument: for any fixed customer-to-vehicle assignment, the range objective (max length minus min length) is non-decreasing when any route is artificially lengthened beyond its TSP optimum. This property is established from first principles on the objective definition itself and does not reduce to any fitted parameter, self-citation chain, or renamed empirical pattern. The TSP-optimality cuts are then motivated as a valid restriction that preserves all globally optimal solutions. Computational results report empirical gaps on benchmark instances without any 'prediction' step that tautologically reproduces input data. No load-bearing self-citation or ansatz smuggling is present in the provided text; the framework is self-contained as an algorithmic construction validated by solvability rates.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on standard polyhedral theory for the TSP and capacitated VRP; no new free parameters, invented entities, or ad-hoc axioms are introduced beyond the algorithmic construction of the cuts.

axioms (1)
  • standard math Validity of TSP subtour elimination and other standard inequalities for the traveling salesman polytope
    The TSP-optimality cuts are derived from the assumption that individual routes must be optimal TSP tours, relying on known polyhedral descriptions.

pith-pipeline@v0.9.0 · 5431 in / 1239 out tokens · 43537 ms · 2026-05-08T05:53:26.081963+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Solutionalgorithms for a vehicle routing problem with route-cost equity constraints

    Agius,M.,Absi,N.,Feillet,D.,Garaix,T.,2026. Solutionalgorithms for a vehicle routing problem with route-cost equity constraints. Annals of Operations Research , 1–41

    work page 2026

  2. [2]

    A polyhedral study of the asymmetric traveling salesman problem with time windows

    Ascheuer, N., Fischetti, M., Grötschel, M., 2000. A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks 36, 69–79

    work page 2000

  3. [3]

    Beyond efficiency: Exploringthecosteffectsofprioritizingdriversatisfactioninvehicle routing

    Bruinink, T., Berghman, L., Dollevoet, T., 2025. Beyond efficiency: Exploringthecosteffectsofprioritizingdriversatisfactioninvehicle routing. Operations Research Letters 63, 107344

    work page 2025

  4. [4]

    Exact branch-price- and-cut algorithms for vehicle routing

    Costa, L., Contardo, C., Desaulniers, G., 2019. Exact branch-price- and-cut algorithms for vehicle routing. Transportation Science 53, 946–985

    work page 2019

  5. [5]

    A dynamic programming approach to sequencing problems

    Held, M., Karp, R.M., 1962. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics 10, 196–210

    work page 1962

  6. [6]

    Path inequalities for the vehicle routing problem with time windows

    Kallehauge, B., Boland, N., Madsen, O.B., 2007. Path inequalities for the vehicle routing problem with time windows. Networks 49, 273–293

    work page 2007

  7. [7]

    Fair vehicle routing via bilevel optimization

    Ljubić, I., Puerto, J., Torrejon, A., 2026. Fair vehicle routing via bilevel optimization. URL:https://optimization-online.org/2026/ 03/fair-vehicle-routing-via-bilevel-optimization/. Preprint, sub- mitted March 5, 2026

    work page 2026

  8. [8]

    Anewbranch-and- cutalgorithmforthecapacitatedvehicleroutingproblem

    Lysgaard,J.,Letchford,A.N.,Eglese,R.W.,2004. Anewbranch-and- cutalgorithmforthecapacitatedvehicleroutingproblem. Mathemat- ical programming 100, 423–445

    work page 2004

  9. [9]

    On the Asymmetric Travelling Salesman Problem with Replenishment Arcs

    Mak, V.H., 2001. On the Asymmetric Travelling Salesman Problem with Replenishment Arcs. Ph.D. thesis. University of Melbourne, Department of Mathematics and Statistics

    work page 2001

  10. [10]

    Workload equity in vehicle routing problems: A survey and analysis

    Matl, P., Hartl, R.F., Vidal, T., 2018. Workload equity in vehicle routing problems: A survey and analysis. Transportation Science 52, 239–260. Bart van Rossum, Rui Chen and Andrea Lodi:Preprint submitted to ElsevierPage 6 of 7 Enforcing TSP-Optimality in Fair Vehicle Routing

    work page 2018

  11. [11]

    A new branching rule for rangeminimizationproblems,in:InternationalConferenceonInteger Programming and Combinatorial Optimization, Springer

    van Rossum, B., Chen, R., Lodi, A., 2024. A new branching rule for rangeminimizationproblems,in:InternationalConferenceonInteger Programming and Combinatorial Optimization, Springer. pp. 433– 445

    work page 2024

  12. [12]

    Efficient branching rules foroptimizingrangeandorder-basedobjectivefunctions

    van Rossum, B., Chen, R., Lodi, A., 2025. Efficient branching rules foroptimizingrangeandorder-basedobjectivefunctions. Mathemat- ical Programming , 1–34. Bart van Rossum, Rui Chen and Andrea Lodi:Preprint submitted to ElsevierPage 7 of 7

    work page 2025