Traveling Salesman Tardiness

Haoyue Liu; Sheng Liu

REVIEW 3 major objections 5 minor 31 references

Traveling Salesman Tardiness

T0 review · 3 major / 5 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read TSP route-time targets grow fragile linearly with demand volume under spatial uncertainty, not with the classic square-root law.

desk verdict Clean matching bounds and a usable SOCP for a new TSP tardiness index; the Θ claim is real but conditional on interior dispersion, which the abstract understates. read the letter →

arxiv 2607.05730 v1 pith:TR43JGWT submitted 2026-07-07 math.OC

Haoyue Liu , Sheng Liu This is my paper · ORCID

classification math.OC MSC 90C2790B0690C17

keywords travelingsalesmanproblemrobustsatisficingtardinessindexWassersteindistancecontinuousapproximationlast-miledeliveryregionpartitioning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Delivery routes that solve the Traveling Salesman Problem are routinely held to a fixed service deadline. This paper asks how fragile that deadline becomes when the locations of customers can shift relative to the historical sample. It defines a TSP tardiness index that measures the worst-case excess routing time per unit of distributional distance from the empirical locations. Under mild geometric regularity, the index scales as n times the square root of region area times sample size, divided by the target. That linear growth in realized demand is fundamentally different from the classic Beardwood–Halton–Hammersley square-root scaling of tour length itself. The same law extends to multi-vehicle makespan and yields simple closed-form rules for partitioning a service region so that fleet size and target jointly control overtime risk. Synthetic and Amazon last-mile experiments show that the index tracks out-of-sample overtime severity and that the resulting partitions improve both average and tail overtime relative to length-based or violation-based benchmarks.

What carries the argument

The TSP tardiness index ρ_τ(L), defined via the robust-satisficing fragility measure as the smallest k such that excess tour length above τ never exceeds k times the Wasserstein-1 distance from the empirical measure. It is evaluated by reducing the infinite-dimensional worst-case problem to a one-dimensional envelope E_D(t) of the BHH factor inside a Wasserstein ball of radius t, then bounding that envelope geometrically.

What would settle it

Generate many empirical supports that deliberately violate interior dispersion (all mass near the boundary or heavily clustered), recompute the index for a tight target, and check whether the observed growth in n remains linear or collapses toward a lower order.

Watch

Extended reading notes

Core claim

Under non-boundary conditions the TSP tardiness index satisfies ρ_τ(L) = Θ(β² n √(|D| m) / τ) for n realized stops, m historical support points, region area |D| and routing-time target τ. The multi-vehicle makespan version scales as Θ(β² n √(|D| m) / (K² τ)). The matching upper and lower bounds therefore establish a new scaling law for target fragility that is linear in demand volume rather than square-root.

Load-bearing premise

A positive fraction of the historical customer locations must sit well inside the service region and stay separated from one another at the natural planar spacing; severe clustering or boundary pile-up would break the matching lower bound.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The new piece is the first closed-form characterization of target-fragility for BHH tour length under Wasserstein location uncertainty: they define a robust-satisficing tardiness index ρ_τ(L) and prove it is Θ(β^{2} n √(|D|m)/τ) in the interior regime, with a clean 1/K^{2} multi-vehicle extension and simple aggregate/minimax partition ratios. That scaling is not in the BHH, Carlsson–Behroozi–Mihic, or Long–Sim–Zhou lines; it is derived here.

What works: the upper bound (Prop. 3 + Cor. 1) is distribution-free and short—Kantorovich–Rubinstein, Cauchy–Schwarz, Voronoi rearrangement. The SOCP (Props. 1–2) is correctly dualized and, from their timing table, dramatically faster than the earlier cutting-plane DRO. The lower-bound construction (Prop. 4) is explicit and matches order once Assumption 1 holds. Numerics are honest: synthetic correlations with overtime are high; Amazon data are noisier until service time is controlled, which they report. Partition rules are simple enough to use and beat the natural length/violation benchmarks on the metrics they care about.

Soft spots, in proportion. The matching Θ (and therefore the abstract claim) needs Assumption 1: a positive fraction of the m atoms must pack into disjoint interior balls of the natural planar scale. Without it the lower constant can vanish while the O side remains; the paper flags “non-boundary conditions” but the abstract and §3.3 state Θ more flatly than the proofs support. BHH is asymptotic and they use it at finite n; that is standard in continuous approximation but remains an approximation error, not a theorem. No code is shipped. None of these kill the contribution; they bound its scope.

This is for people who do last-mile districting or continuous-approximation routing and want a risk index they can actually compute and design with. Math and citation pattern look solid; free parameters are the usual ones (β, quadrature, target quantiles). I would send it to referees. Worth engaging if you work in the area; the scaling and the SOCP are the parts I would keep.

Referee Report

3 major / 5 minor

Summary. The paper introduces a TSP tardiness index ρ_τ(L) based on the robust-satisficing fragility measure of Long, Sim, and Zhou (2023), which quantifies the worst-case excess of the BHH routing length L(f) above a target τ per unit Wasserstein-1 deviation from an empirical measure with m support points. It derives an exact finite-dimensional dual (Proposition 1) and an SOCP quadrature reformulation (Proposition 2) for computing the index, then proves matching upper and lower bounds on the radius-constrained envelope E_D(t) that yield the interior-regime scaling ρ_τ(L)=Θ(β^{2} n √(|D|m)/τ) under Assumption 1 (Corollaries 1–2, §3.3). The same order is extended to the K-vehicle makespan setting (Corollary 3) and used to obtain closed-form two-zone partition rules (Proposition 5). Synthetic and Amazon last-mile experiments show that the index correlates with out-of-sample overtime metrics and that the partition rules control aggregate and worst-zone overtime better than nominal benchmarks.

Significance. If the scaling law holds under the stated geometric conditions, the paper supplies a new, target-oriented risk measure for spatial routing that is distinct from classical BHH √n growth and from existing distributionally robust TSP formulations. The SOCP reformulation is a concrete computational contribution that improves on the cutting-plane method of Carlsson, Behroozi, and Mihic (2018) by roughly two orders of magnitude (EC.1.2). The closed-form partition ratios in Proposition 5 give immediately usable tactical guidelines. Strengths include an explicit dual derivation, a constructive lower-bound density, and empirical validation on both synthetic families and real Amazon station data. The result is therefore of genuine interest to continuous-approximation and robust-logistics communities, provided the dependence on Assumption 1 is stated with equal prominence in the abstract and main claims.

major comments (3)

Abstract and §3.3 state the Θ scaling as the main result under “non-boundary conditions,” yet the matching Ω side rests entirely on Assumption 1 (interior support dispersion). Proposition 3 and Corollary 1 give a distribution-free O(n √(|D|m)/τ) upper bound; the lower bound of Proposition 4 / Corollary 2 requires a positive fraction η of the m atoms to sit in pairwise-disjoint balls of radius ζ|D|^{1/2}m^{-1/2}. If atoms cluster or concentrate near ∂D, the constant ηζ can vanish while the upper bound remains. The abstract and the Θ claim in §3.3 should therefore be rewritten to make the geometric hypothesis explicit (e.g., “under Assumption 1 the index is Θ(·)”), and a short discussion of what happens when the packing fails should be added.
The analysis throughout uses the asymptotic BHH formula L(f)=β√n ∫√f as an exact routing-time functional (Theorem 1, Eq. (1), and all subsequent envelopes). Finite-n boundary and shape effects are acknowledged only briefly (§2.1) and absorbed into a calibrated β. Because the tardiness index is defined for finite n and the numerical experiments use n in the range 30–100, the paper should either (i) quantify the approximation error of the BHH surrogate relative to exact TSP lengths inside the Wasserstein ball, or (ii) state clearly that all analytic claims are for the continuous-approximation model rather than for the combinatorial TSP. Without this clarification the claimed “new scaling law that extends beyond existing deterministic and probabilistic TSP bounds” is overstated.
Corollary 3 and Proposition 5 invoke the balanced multi-vehicle makespan approximation L_K(f)≈(β√n/K)∫√f. While this is standard in continuous approximation, the paper cites only Carlsson et al. (2025, 2026) without restating the precise conditions under which the makespan is evenly split. A short lemma or reference to the required regularity (identical vehicles, no capacity constraints, etc.) is needed before the 1/K^{2} scaling and the partition ratios |D1|/|D2|=K_i^{2}τ_i (or K_i√τ_i) can be treated as rigorous design rules.

minor comments (5)

Notation: the empirical measure is written both bP_b and bPb; the fixed-k value function appears as V_D(k) and later as V_D. Unify throughout.
Figure EC.1.1 panels are labeled EC.1.1(a)–(f) but the caption refers to “Figures EC.1.1(a)–EC.1.1(f)”; a single multi-panel figure with sub-captions would be clearer.
Table 1 reports p-values with asterisks; the footnote uses both “***p<0.01” and “**p<0.05”, yet the table header already contains the significance markers. Streamline.
In the Amazon experiment (EC.2.2) the global 8-hour target is translated into zone-specific travel-time targets after subtracting service time; the precise subtraction formula is not written. Adding one equation would aid reproducibility.
The constant β is treated as known in the analytic sections but is re-estimated per zone in the experiments. A sentence clarifying that the scaling statements treat β as a fixed geometric constant would avoid confusion.

Circularity Check

1 steps flagged · score 1.0 of 10

Core Θ scaling is a genuine first-principles bound match; only a secondary multi-vehicle step rests on concurrent self-citation.

self citation load bearing [§3.3, Corollary 3 and preceding paragraph]
"as shown in Carlsson et al. (2025, 2026), the minimax routing solution (that also minimizes the makespan) for K identical vehicles would split the total routing time evenly, so the routing time of each vehicle is approximated by L_K(f)≈ β√n/K ∫_D √f(x) dx. ... ρ^K_τ(L)=Θ(β² n √(|D|m)/(K² τ))."

The 1/K² fleet-size factor in the multi-vehicle tardiness scaling is not re-derived; it is imported from concurrent papers coauthored by Liu that supply the balanced-makespan continuous approximation. The single-vehicle Θ claim (Corollaries 1–2, §3.3 main text) does not depend on this citation, so the circularity is secondary rather than load-bearing for the paper’s strongest result.

full rationale

The TSP tardiness index is defined from the external robust-satisficing template (Long–Sim–Zhou) applied to the classical BHH length functional; it is not defined in terms of the claimed scaling. The upper envelope bound (Prop. 3) follows from the Kantorovich–Rubinstein dual, Cauchy–Schwarz, and Voronoi rearrangement and is distribution-free. The matching lower order (Prop. 4 / Cor. 2) is obtained by an explicit feasible density construction under the stated interior-dispersion Assumption 1; the Θ statement in §3.3 is simply the order match of those two independent bounds in the interior regime. β enters as the classical BHH constant (calibrated only in numerics). No fitted parameter is renamed a prediction, no uniqueness theorem is imported, and no known empirical law is merely re-labeled. The sole mild self-citation is the balanced-makespan continuous-approximation claim used for the multi-vehicle Corollary 3 (Carlsson–Liu concurrent zoning papers); that extension is secondary and does not force the paper’s central single-vehicle scaling. Score 1 reflects that minor secondary dependence only.

Assumptions & free parameters 3 free parameters · 6 assumptions · 1 invented entities

The analytic claim rests on classical BHH asymptotics, the Kantorovich–Rubinstein dual of W1, the Long–Sim–Zhou robust-satisficing template, and the paper’s own interior-dispersion Assumption 1. Computational claims add quadrature and a positivity tolerance. β is treated as a known constant analytically and calibrated numerically. No new physical entities are postulated; the tardiness index is a defined functional.

free parameters (3)

BHH constant β
Appears as a multiplicative factor in all analytic bounds; in experiments it is zone-calibrated from finite-sample TSP lengths rather than taken as the universal continuum constant.
quadrature tolerance ε and grid resolution C
Chosen for numerical stability of the SOCP denominator (Proposition 2); affect computed index values but not the asymptotic Θ statement.
target construction parameters c,q in synthetic experiments
τ is set as c times the empirical q-quantile of realized lengths (c=0.95, q=0.45); these choices shape the reported correlations but not the theory.

assumptions (6)

standard math Beardwood–Halton–Hammersley theorem: L(f)/√n → β ∫√f as n→∞ for continuous densities on D
Used as the routing-length model throughout §§2–3; finite-n error is acknowledged but not bounded.
standard math Semidiscrete Kantorovich–Rubinstein dual: W1(f,P̂)=max_λ∈Λ ∫ a_λ(x)f(x)dx
Invoked to obtain the finite-dimensional dual form (5) and the fixed-k program (7).
domain assumption Robust satisficing fragility measure ρ(Ψ) of Long, Sim, Zhou (2023)
Definition (2)–(3) is taken as the risk measure; properties (i)–(iv) are cited rather than re-proved.
ad hoc to paper Assumption 1: positive fraction of empirical atoms are interior-dispersed at scale |D|^{1/2}m^{-1/2}
Required for the matching lower bound on E_D(t) and thus for the Θ claim; rules out severe clustering/boundary concentration.
domain assumption Constant unit vehicle speed; only locational uncertainty is modeled
Stated in §2.1 and footnote 2; service-time and travel-time noise are excluded from the index by construction.
domain assumption Balanced K-vehicle makespan ≈ (β√n/K)∫√f (Carlsson et al. concurrent work)
Used in Corollary 3 to replace β√n by β√n/K; not re-derived here.

invented entities (1)

TSP tardiness index ρ_τ(L) independent evidence
purpose: Scalar fragility measure of a routing-time target under Wasserstein spatial uncertainty
Defined via the robust-satisficing template specialized to Ψ_τ=L−τ; it is a constructed functional, not an independent physical object. Independent evidence is the out-of-sample correlation with overtime metrics in §4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Traveling Salesman Tardiness." pith.science (2026). https://pith.science/paper/TR43JGWT

@misc{pith2026260705730,
  author       = {Pith},
  title        = {Pith review of: Traveling Salesman Tardiness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TR43JGWT}},
  note         = {Machine review of arXiv:2607.05730}
}

read the original abstract

How fragile is the routing time window of delivery systems against spatial distributional uncertainty? We study the tardiness risk of Traveling Salesman Problem (TSP) solutions with respect to a service deadline (target) over the routing time. Using the robust satisficing model, we introduce the TSP tardiness index to quantify the target's fragility under distributional uncertainty in customer locations. Assuming there are m potential customer locations from historical samples on a service region D (of area |D|), we prove that the TSP tardiness index is {\Theta}(n * sqrt(|D|m) / {\tau}) for n realized locations with respect to the routing time target {\tau}, under non-boundary conditions. This result establishes a new scaling law that extends beyond the existing deterministic and probabilistic TSP bounds. We further extend it to a multi-vehicle case and derive simple partition rules for managing delivery systems. Our numerical experiments using synthetic and real-world routing data validate the value of the TSP tardiness index in characterizing and managing the overtime risk of routing systems.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

[1]

Operations Research , volume=

Provably good region partitioning for on-time last-mile delivery , author=. Operations Research , volume=. 2024 , publisher=

work page 2024
[2]

INFORMS Journal on Applied Analytics , volume=

Redesigning Zoning Systems for Equitable and Efficient Last-Mile Delivery at Ninja Van , author=. INFORMS Journal on Applied Analytics , volume=. 2025 , publisher=

work page 2025
[3]

Transportation science , volume=

The distance traveled to visit N points with a maximum of C stops per vehicle: An analytic model and an application , author=. Transportation science , volume=. 1984 , publisher=

work page 1984
[4]

Computers & operations research , volume=

Estimating the length of the optimal TSP tour: An empirical study using regression and neural networks , author=. Computers & operations research , volume=. 1995 , publisher=

work page 1995
[5]

Computers & Operations Research , volume=

Optimal-transport satisficing with applications to capacitated hub location , author=. Computers & Operations Research , volume=. 2024 , publisher=

work page 2024
[6]

Available at SSRN 5769803 , year=

Analytics for On-Demand Food Delivery: A Hurwicz Satisficing Perspective , author=. Available at SSRN 5769803 , year=

work page
[7]

Transportation Research Part E: Logistics and Transportation Review , volume=

A robust satisficing multi-objective optimization approach for bike-sharing systems with heterogeneous user types , author=. Transportation Research Part E: Logistics and Transportation Review , volume=. 2025 , publisher=

work page 2025
[8]

Transportation Research Part C: Emerging Technologies , volume=

Data-driven robust optimization for contextual vehicle rebalancing in on-demand ride services under demand uncertainty , author=. Transportation Research Part C: Emerging Technologies , volume=. 2023 , publisher=

work page 2023

Show all 31 references

[9]

Operations Research , volume=

Robust workforce management with crowdsourced delivery , author=. Operations Research , volume=. 2025 , publisher=

2025
[10]

IISE Transactions , volume=

Robust inventory routing problem considering budget violation under demand uncertainty , author=. IISE Transactions , volume=. 2026 , publisher=

2026
[11]

Management Science , year=

Service-Oriented Considerate Routing: Data, Predictions, and Robust Decisions , author=. Management Science , year=
[12]

Transportation Science , volume=

2021 Amazon last mile routing research challenge: Data set , author=. Transportation Science , volume=. 2024 , publisher=

2021
[13]

Management Science , volume=

Satisficing measures for analysis of risky positions , author=. Management Science , volume=. 2009 , publisher=

2009
[14]

2021 , publisher=

Topics in optimal transportation , author=. 2021 , publisher=

2021
[15]

Operations Research , volume=

Wasserstein distance and the distributionally robust TSP , author=. Operations Research , volume=. 2018 , publisher=

2018
[16]

Operations Research , volume=

Robust satisficing , author=. Operations Research , volume=. 2023 , publisher=

2023
[17]

Mathematical proceedings of the Cambridge philosophical society , volume=

The shortest path through many points , author=. Mathematical proceedings of the Cambridge philosophical society , volume=. 1959 , organization=

1959
[18]

Transportation science , volume=

The vehicle routing problem with stochastic travel times , author=. Transportation science , volume=. 1992 , publisher=

1992
[19]

Transportation Science , volume=

Models and algorithms for stochastic and robust vehicle routing with deadlines , author=. Transportation Science , volume=. 2016 , publisher=

2016
[20]

Operations research , volume=

Routing optimization under uncertainty , author=. Operations research , volume=. 2016 , publisher=

2016
[21]

Operations Research , volume=

Robust data-driven vehicle routing with time windows , author=. Operations Research , volume=. 2021 , publisher=

2021
[22]

Transportation Science , volume=

Probabilistic traveling salesman problem with deadlines , author=. Transportation Science , volume=. 2008 , publisher=

2008
[23]

1985 , school=

Probabilistic traveling salesman problems , author=. 1985 , school=

1985
[24]

Operations research , volume=

Robust partitioning for stochastic multivehicle routing , author=. Operations research , volume=. 2013 , publisher=

2013
[25]

Manufacturing & Service Operations Management , year=

Equitable delivery zoning for last-mile logistics: A framework validated with implementation , author=. Manufacturing & Service Operations Management , year=
[26]

Transportation Science , volume=

Fleet sizing and service region partitioning for same-day delivery systems , author=. Transportation Science , volume=. 2022 , publisher=

2022
[27]

Management Science , volume=

Tactical design of same-day delivery systems , author=. Management Science , volume=. 2022 , publisher=

2022
[28]

European journal of operational research , volume=

Incorporating inventory and routing costs in strategic location models , author=. European journal of operational research , volume=. 2007 , publisher=

2007
[29]

Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages=

Towards equitable assignment: Data-driven delivery zone partition at last-mile logistics , author=. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages=
[30]

Operations Research 66(6):1603--1624

Carlsson JG, Behroozi M, Mihic K, 2018 Wasserstein distance and the distributionally robust tsp. Operations Research 66(6):1603--1624

2018
[31]

Transportation Science 58(1):8--11

Merch \'a n D, Arora J, Pachon J, Konduri K, Winkenbach M, Parks S, Noszek J, 2024 2021 amazon last mile routing research challenge: Data set. Transportation Science 58(1):8--11

2024

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.

[1] [1]

Operations Research , volume=

Provably good region partitioning for on-time last-mile delivery , author=. Operations Research , volume=. 2024 , publisher=

work page 2024

[2] [2]

INFORMS Journal on Applied Analytics , volume=

Redesigning Zoning Systems for Equitable and Efficient Last-Mile Delivery at Ninja Van , author=. INFORMS Journal on Applied Analytics , volume=. 2025 , publisher=

work page 2025

[3] [3]

Transportation science , volume=

The distance traveled to visit N points with a maximum of C stops per vehicle: An analytic model and an application , author=. Transportation science , volume=. 1984 , publisher=

work page 1984

[4] [4]

Computers & operations research , volume=

Estimating the length of the optimal TSP tour: An empirical study using regression and neural networks , author=. Computers & operations research , volume=. 1995 , publisher=

work page 1995

[5] [5]

Computers & Operations Research , volume=

Optimal-transport satisficing with applications to capacitated hub location , author=. Computers & Operations Research , volume=. 2024 , publisher=

work page 2024

[6] [6]

Available at SSRN 5769803 , year=

Analytics for On-Demand Food Delivery: A Hurwicz Satisficing Perspective , author=. Available at SSRN 5769803 , year=

work page

[7] [7]

Transportation Research Part E: Logistics and Transportation Review , volume=

A robust satisficing multi-objective optimization approach for bike-sharing systems with heterogeneous user types , author=. Transportation Research Part E: Logistics and Transportation Review , volume=. 2025 , publisher=

work page 2025

[8] [8]

Transportation Research Part C: Emerging Technologies , volume=

Data-driven robust optimization for contextual vehicle rebalancing in on-demand ride services under demand uncertainty , author=. Transportation Research Part C: Emerging Technologies , volume=. 2023 , publisher=

work page 2023