REVIEW 4 major objections 5 minor 19 references
Route Optimization Over Scheduled Services For Large-Scale Package Delivery Networks
T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read A pruning algorithm that keeps exactly the schedule legs lying on feasible paths reduces trailer routing over scheduled services to a tractable scale, and a stabilized column-generation heuristic solves industrial instances with up to 74…
desk verdict Useful applied OR paper with a genuinely new problem and an exact network reduction, but the real-time claims outrun the reported evidence. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key machinery is the Earliest-and-Latest-Start-Time Pruning algorithm, EALSP. It computes two labels per hub for each request: an earliest-arrival label propagated forward from the request's origin, and a latest-start label propagated backward from its destination, both by Dijkstra-like dynamic programming over the scheduled-leg network. A leg survives if its departure is no earlier than the earliest-arrival time at its origin hub and its arrival is no later than the latest-start time at its destination hub. This reduction is exact: the surviving legs are exactly those on some feasible path, so the pruned instance contains an optimal solution whenever one exists. The companion mechanism is a column-generation heuristic whose pricing subproblem is a time-dependent shortest path with waiting allowed at hubs; a stabilized variant of the decomposition keeps dual values from oscillating, and a Lagrangian relaxation provides the lower bound against which solution gaps are measured.
What would settle it
Construct a small TPOSSP instance with a handful of hubs, schedules, and requests where the true optimum is known by exhaustive enumeration over all feasible path sets, and check both that every leg on every feasible path survives the EALSP condition and that the heuristic's final solution is within the paper's claimed gap. A single leg on a feasible path that fails the condition would directly refute Theorem 1, and a single instance where the heuristic misses the claimed gap would refute the performance claims.
Extended reading notes
Core claim
The central discovery is the EALSP characterization of an optimal sub-network for each request. For a request with an earliest pickup time and a latest arrival time, the algorithm computes, for every hub, the earliest arrival time of any feasible path from the request's origin to that hub, and the latest start time of any feasible path from that hub to the destination. A scheduled leg lies on some feasible path, by the paper's Theorem 1, exactly when its departure time is no earlier than the earliest arrival time at its origin hub and its arrival time is no later than the latest start time at its destination hub. The union of such legs is therefore precisely the sub-network of legs that can appear on a feasible path, and pruning everything else is lossless. On top of this, the paper develops a path-based decomposition whose pricing problem is a time-dependent shortest path on that sub-network, and claims that the stabilized column-generation heuristic reaches the reported solution gaps at scales where the arc-based mixed-integer program is intractable.
Load-bearing premise
The load-bearing premise is that the base plan used for the 2.3% to 3.2% cost comparison is a realistic representation of what the logistics provider actually does today; the paper does not document how that base plan is generated or updated, and if it is not a realistic baseline the headline savings and the tens-of-millions-of-dollars figure would be overstated.
Editorial extensions
If this is right
- The EALSP reduction is lossless, so solving the pruned network is equivalent to solving the full network and all reported solution-quality claims apply to the original instances.
- In planning, the heuristic reaches within 3.7% to 5.7% of the Lagrangian lower bound on instances with up to 74 billion request-leg pairs, and improves on the current base plan by 2.3% to 3.2% in total cost and 8.5% to 10.3% in empty miles.
- In real-time operations, the same heuristic returns solutions within 3% of the lower bound in 75% of the test cases, all within one minute, so new requests can be inserted on the day of operations.
- Because each request's sub-network can be cached and updated only when schedules or requests change, repeated planning runs can avoid recomputing the pruning from scratch.
- The pruning step cuts runtimes by 53% to 85% for the heuristic and by 83% to 99% for the exact arc-based mixed-integer program on the small real-time instances.
Reading between the lines
- The savings percentages are only as credible as the undocumented base plan used for comparison; if that base plan is not a realistic model of the manual process, the economic claims would shrink. This is an inference because the paper does not describe how the base plan was built.
- The EALSP condition is not specific to trailers: any scheduled-service network where time feasibility is the main coupling between legs, such as rail, air, or intermodal freight, could use the same two-label pruning, provided capacity and schedule-selection constraints are handled downstream.
- Because the planning gaps are measured against a Lagrangian lower bound rather than a proven optimum, the true deviation from optimality could be smaller than the reported 3.7% to 5.7% if that bound is loose; a fair reader should treat the bound as an anchor, not as the optimum itself.
- A direct test of the approach would be to run the same pipeline on synthetic instances with known optima, or on historical data after the fact, to ground-truth both the optimality gap and the savings fractions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper formalizes the Trailer Path Optimization with Scheduled Services Problem (TPOSSP), in which each request, representing a trailer movement with a time window, must be assigned a path over existing scheduled legs subject to tractor capacity and schedule-utilization costs. The authors propose an arc-based MIP, prove that a polynomial-time pruning algorithm (EALSP) computes the optimal sub-network of legs that can appear on any feasible path for each request, and then propose a stabilized column-generation heuristic whose pricing subproblem is a time-dependent shortest path. The approach is evaluated on industrial instances: planning instances with up to 74 billion request-leg pairs are reported to be solved within 3.7%-5.7% of a Lagrangian lower bound in 1.7-10.3 hours, and real-time instances are reported to be solved within 3% of optimality in under one minute in 75% of cases, with claimed cost savings of 2.3%-3.2% over a base plan.
Significance. If the results hold, the paper contributes a new, industrially motivated problem formulation and a scalable decomposition method, with the EALSP sub-network theorem being a clean and potentially transferable theoretical contribution. The reported scale of 74 billion request-leg pairs is impressive, and the time-dependent pricing and stabilization ideas are appropriate for the problem. However, several load-bearing issues prevent the strongest claims from being accepted as stated: the final master problem is written with continuous path variables while only y variables are declared integer, the planning gaps are measured against a Lagrangian bound rather than a certified optimum, the real-time latency figures appear to exclude EALSP preprocessing, and the baseline used for the business-savings claims is undocumented. These issues need to be resolved before the empirical conclusions are reliable.
major comments (4)
- [Section 6.3 / Figure 6] The restricted master problem in Figure 6 is written with λ ∈ [0,∞), and Section 6.3 states that integer solutions are found by enforcing integrality on the y variables only. In TPOSSP, each request is a single trailer that must follow exactly one path; a fractional convex combination of two candidate paths for the same request is not a feasible route. Unless the implementation actually imposes integrality on the λ variables, or a rounding/post-processing procedure is described, the reported objective values in Section 7 are not upper bounds on the TPOSSP optimum, and the savings versus the base plan are not necessarily achievable. This issue is load-bearing for all empirical claims and must be clarified and, if λ is in fact continuous, corrected with new experiments.
- [Section 7.4 / Table 3] Figure 10 and the Section 7.4 discussion report only CG-heuristic runtimes, while Table 3 lists EALSP preprocessing times of 6-60 seconds for the real-time instances (60s for instance 2.5, 54s for 2.14, and 42s for 2.15). For newly arriving requests, the sub-network must be computed after the request arrives, so the end-to-end latency is at least the EALSP time plus the CG time. The paper does not state whether the Section 7.4 runtimes include EALSP. As written, the claim that the method meets the '1 minute or so' real-time requirement stated in Section 1.1 is unsupported for several instances. The authors should report per-instance end-to-end wall-clock times, or explicitly justify why EALSP is not on the critical path.
- [Sections 7.2, 1.3, and Abstract] The planning optimality gaps of 3.7%-5.7% are computed against a Lagrangian dual solved by the Surrogate Lagrangian Relaxation with a stopping criterion of no improvement for 50 iterations. This yields a lower-bound gap, not a proven gap to the true optimum; the contribution statement in Section 1.3 that the CG-heuristic reaches 'within 3.7%-5.7% of the true optimal solution' overstates what is measured. The abstract's phrase 'based on a MIP relaxation' is also inconsistent with the Lagrangian relaxation described in Section 6.4. The authors should present these as gaps against a lower-bound estimate, state whether the terminal multipliers were evaluated to certify a valid Lagrangian bound, and revise all 'true optimal' wording accordingly.
- [Section 7.3] The business-benefit comparison is made against an 'available base solution' described only as the current manual process. The paper does not specify how this base plan is generated, how its schedule and mile costs are computed, which requests it covers, or how it is updated for each of the six planning instances. Since the 2.3%-3.2% cost reduction and the tens-of-millions-of-dollars claim are computed as differences from this baseline, the economic claim cannot be audited or reproduced. The authors should provide a precise description of the base plan construction and cost accounting, or report the comparison in a way that does not depend on an opaque benchmark.
minor comments (5)
- [Lemma 1, Section 5.1] The lemma's stated condition eat_i ≤ ts_l ≤ lst_j appears to contain a typo: the feasibility of leg l from i to j requires te_l ≤ lst_j, not ts_l ≤ lst_j. The proof in Appendix A uses the correct condition te_l ≤ lst_j, so the theorem remains sound, but the inconsistent statement should be corrected.
- [Table 2] The verbal definition of E_r in Table 2 says legs whose 'start time is less than eat_i', which is the reverse of the correct condition eat_i ≤ ts_l used in Equation (5a). The table entry should be rewritten for consistency.
- [Introduction and Section 7.5] The reported speedup percentages are inconsistent across the abstract, Section 1.2, Section 1.3, and Section 7.5: the CG speedup is given variously as 85%, 53%-85%, and 53%-82%, while the Arc-MIP speedup is given as 85%-99% in Section 1.3 and 83%-99% in Section 7.5. These numbers should be reconciled.
- [Throughout] There are several grammatical slips, e.g., 'with translates into savings' in the abstract and 'returns solution within 3% of optimality' in Section 1.3. A careful proofread would improve the presentation.
- [Reproducibility] No data or code availability is mentioned. Given the proprietary nature of the instances, a full release may not be possible, but the authors should at least state the availability status and consider sharing anonymized or synthetic instances to allow independent verification of the algorithmic claims.
Circularity Check
No significant circularity; the EALSP correctness proof and CG lower-bound comparisons are self-contained, with only minor non-load-bearing self-citations.
full rationale
I walked the main derivation chain. The EALSP result (Section 5, Definition 5.1, Lemma 1, Theorem 1) is a genuine correctness proof: the optimal sub-network is defined as the union of legs lying on some feasible path, and Theorem 1 proves that the EALSP set Er = {l : eat_dl <= ts_l, te_l <= lstr_el} equals that union by constructing feasible prefix and suffix paths from the definitions of earliest-arrival and latest-start times. The result is not assumed by construction; it is a substantive characterization with a proof. Lemma 2's critical-leg pruning is likewise a standard dominance argument, not a restatement of the claim. The CG-heuristic's optimality claims are measured against Arc-MIP and Lagrangian lower bounds, not against a fitted parameter or against the heuristic's own output. The parameter choices (Paths, NumIterations, MaxCost, Mode) are algorithmic tuning choices, not predictions, and the comparison to the manual base plan is an external benchmark, however under-documented. The only self-citations are Mahéo et al. (2017) and Guan et al. (2024) in the literature review, and neither is load-bearing for the EALSP algorithm, the column-generation method, or the computational claims. Concerns about omitted EALSP preprocessing time in real-time runtimes and the undocumented base plan are correctness/validity issues, not circularity.
Assumptions & free parameters
free parameters (5)
- Paths (paths per request per CG iteration) =
5 to 50; 50 used for final results
- NumIterations (CG iteration limit) =
50
- MaxCost (maximum path cost in TDSPP pricing) =
0
- Mode (standard vs stabilized CG) =
Stabilized for planning, Standard for real-time
- Lagrangian stopping criterion (no improvement for 50 iterations) =
50 iterations
assumptions (6)
- domain assumption A tractor can carry up to three short trailer equivalents; trailer volumes are normalized (28'=1, 45'=1.5, 48'=1.9, 53'=2.5) and capacities are multiples of short trailers.
- domain assumption Leg start and end times include the time to attach and detach trailers.
- domain assumption Requests with no feasible path in the given schedules are removed and replaced by direct dummy schedules from origin to destination and back, with cost sigma^dummy_s, to guarantee model feasibility.
- standard math The time-dependent shortest path problem with nonnegative leg costs and waiting at nodes can be solved with a Dijkstra-like label-setting algorithm, and the critical-legs Lemma 2 ensures pruning non-critical departures is optimal.
- standard math The Lagrangian relaxation with nonnegative multipliers provides a valid lower bound on the optimal MIP value; the surrogate Lagrangian method of Bragin et al. (2015) is used to find dual values.
- ad hoc to paper The optimality gap for planning instances is measured against the Lagrangian lower bound, which the paper assumes is a meaningful proxy for the true optimum.
invented entities (1)
-
Dummy direct schedules
Cite this review
Pith. "Pith review of Route Optimization Over Scheduled Services For Large-Scale Package Delivery Networks." pith.science (2026). https://pith.science/paper/TFN6SB6P
@misc{pith2026250720844,
author = {Pith},
title = {Pith review of: Route Optimization Over Scheduled Services For Large-Scale Package Delivery Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/TFN6SB6P}},
note = {Machine review of arXiv:2507.20844}
}
read the original abstract
This paper introduces the Trailer Path Optimization with Schedule Services Problem (TPOSSP) and proposes a column-generation heuristic (CG-heuristic) to find high-quality solutions to large-scale instances. The TPOSSP aims at determining trailer routes over a time-dependent network using existing scheduled services, while considering tractor capacity constraints and time windows for trailer pickups and deliveries. The objective is to minimize both the number of schedules used and the total miles traveled. To address the large scale of industrial instances, the paper proposes a network reduction technique that identifies the set of feasible schedule-legs for each requests. Moreover, to address the resulting MIP models, that still contains hundred of millions variables, the paper proposes a stabilized column-generation, whose pricing problem is a time-dependent shortest path. The approach is evaluated on industrial instances both for tactical planning where requests for the entire network are re-optimized and for real-time operations where new requests are inserted. In the tactical planning setting, the column-generation heuristic returns solutions with a 3.7%-5.7% optimality gap (based on a MIP relaxation) in under 1.7-10.3 hours, and improves the current practice by 2.3-3.2%, with translates into savings of tens of millions of dollars a year. In the real-time setting, the column-generation heuristic returns solution within 3% of optimality in under 1 minute, which makes it adequate for real-time deployment. The results also show that the network reduction decreases run times by 85% for the column-generation heuristic.
Figures
Figures from the paper (8 more)
Reference graph
Works this paper leans on
-
[1]
An intermodal multicommodity routing problem with scheduled services, volume 53
Burak Ayar and Hande Yaman. An intermodal multicommodity routing problem with scheduled services, volume 53. 2012
work page 2012
-
[2]
Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, and Pamela H. Vance. Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46 0 (3): 0 293--432, 1998
work page 1998
-
[3]
Cynthia Barnhart, Christopher A. Hane, and Pamela H. Vance. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research, 48 0 (2): 0 318--326, 2000
work page 2000
-
[4]
The continuous-time service network design problem
Natashia Boland, Mike Hewitt, Luke Marshall, and Martin Savelsbergh. The continuous-time service network design problem. Operations Research, 65 0 (5): 0 1303--1321, 2017
work page 2017
-
[5]
Mikhail A. Bragin, Peter B. Luh, Joseph H. Yan, Nanpeng Yu, and Gary A. Stern k. Convergence of the surrogate lagrangian relaxation method. Journal of Optimization Theory and Applications, 164: 0 173--201, 2015
work page 2015
-
[6]
Package delivery statistics: Capital one research, 2024
CapitalOne. Package delivery statistics: Capital one research, 2024. URL https://capitaloneshopping.com/research/package-delivery-statistics/. [Online; accessed 14-Dec-2024]
work page 2024
-
[7]
Service network design in freight transportation
Teodor Gabriel Crainic. Service network design in freight transportation. European Journal of Operational Research, 122 0 (2): 0 272--288, 2000
work page 2000
-
[8]
Scheduled service network design with resource acquisition and management
Teodor Gabriel Crainic, Mike Hewitt, Michel Toulouse, and Duc Minh Vu. Scheduled service network design with resource acquisition and management. EURO J. Transp. Logist., 7: 0 277–309, 2017
work page 2017
Show all 19 references
-
[9]
Dantzig and Philip Wolfe
George B. Dantzig and Philip Wolfe. Decomposition principle for linear programs. Operations Research, 8 0 (1): 0 101--111, 1960
1960
-
[10]
Path-based formulations for the design of on-demand multimodal transit systems with adoption awareness
Hongzhao Guan, Beste Basciftci, and Pascal Van Hentenryck. Path-based formulations for the design of on-demand multimodal transit systems with adoption awareness. INFORMS JOURNAL ON COMPUTING, 0 0 (0), 2024
2024
-
[11]
Dynamic discretization discovery algorithms for time-dependent shortest path problems
Edward Yuhang He, Natashia Boland, George Nemhauser, and Martin Savelsbergh. Dynamic discretization discovery algorithms for time-dependent shortest path problems. INFORMS JOURNAL ON COMPUTING, 34 0 (2): 0 1086--1114, 2022
2022
-
[12]
Pardalos
Dukwon Kim and Panos M. Pardalos. A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure. Operations Research Letters, 24 0 (4): 0 195--203, 1999
1999
-
[13]
Column generation for solving large scale multi-commodity flow problems for passenger transportation
Benedikt Lienkamp and Maximilian Schiffer. Column generation for solving large scale multi-commodity flow problems for passenger transportation. European Journal of Operational Research, 314 0 (2): 0 703--717, 2024
2024
-
[14]
Lübbecke and Jacques Desrosiers
Marco E. Lübbecke and Jacques Desrosiers. Selected topics in column generation. Operations Research, 53 0 (6): 0 1007--1023, 2005
2005
-
[15]
Benders decomposition for the design of a hub and shuttle public transit system
Arthur Mahéo, Philip Kilby, and Pascal Van Hentenryck. Benders decomposition for the design of a hub and shuttle public transit system. Transportation Science, 53 0 (1): 0 77--88, 2017
2017
-
[16]
The multicommodity network flow problem: state of the art classification, applications, and solution methods
Khodakaram Salimifard and Sara Bigharaz. The multicommodity network flow problem: state of the art classification, applications, and solution methods. Operational Research, 22 0 (4): 0 1--47, 2022
2022
-
[17]
Weighted dantzig-wolfe decomposition for linear mixed-integer programming
Paul Wentges. Weighted dantzig-wolfe decomposition for linear mixed-integer programming. Int. Trans. Opl Res., 4 0 (2): 0 151--162, 1997
1997
-
[18]
Service network design for freight transportation: a review
Nicole Wieberneit. Service network design for freight transportation: a review. OR Spectrum, 30: 0 77--112, 2008
2008
-
[19]
Scheduled service network design for freight rail transportation
Endong Zhu, Teodor Gabriel Crainic, and Michel Gendreau. Scheduled service network design for freight rail transportation. Operations Research, 62 0 (2): 0 383--400, 2014
2014
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.