{"id":"91c6c698-dd55-423f-9b71-0c988084a86d","arxiv_id":"2411.13151","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"An enhanced fragment algorithm with dynamic discretization discovery, formulation leveraging, and column enumeration for row elimination is competitive with or outperforms state-of-the-art exact solvers on PDPTW and TDDRP instances.","lead":"This paper improves fragment-based exact algorithms for vehicle routing and shows they can beat state-of-the-art branch-and-price-cut solvers on pickup-and-delivery and truck-drone problems. A generalist should care because it offers a simpler route to exact solutions for hard routing problems, using commercial solvers instead of bespoke branch-and-bound code.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The TDDRP superiority claim rests on generated stand-in instances rather than the original Yin et al. benchmarks, so the state-of-the-art comparison is not settled.","rationale":"The reader's conditional verdict already identifies the same load-bearing concern: the TDDRP comparison is made on non-identical, generated instances rather than the original Yin et al. benchmarks. My stress-test confirms that this is the point where the central comparative claim is least secure. The PDPTW comparison is direct and on standard benchmarks, which is real independent evidence for that half of the claim. The DDD, FL, and CERE mechanisms are described in enough detail that the algorithmic contribution is plausible, and the paper's own Section 5.4 limitation statement about the need for a small route-formulation optimality gap is honestly stated. The problem is not internal inconsistency; it is that the concluding sentence 'our results are strong enough to conclude that our algorithm outperforms the BPC algorithm' goes beyond what the experimental design can establish for the TDDRP, because the baseline times were not produced on the same instances or machine. This does not warrant rejecting the paper, but it does warrant keeping the conditional verdict and requiring either access to the original instances or a more modest claim.","tokens_in":29224,"tokens_out":7545,"duration_ms":81253,"concrete_test":"Obtain the original Yin et al. (2023) TDDRP instances from the authors or from the EJOR supplementary material, and run the proposed fragment method (one thread, one-hour limit, Section 5.4 protocol) on exactly those instances. If the proposed method does not solve at least as many instances, and within comparable times, as the published BPC results on the same original instances, then the claim that it outperforms the state of the art for TDDRP should be withdrawn. If the original instances cannot be obtained, the claim should be explicitly relabeled as a proof-of-concept on instances generated under the published schema.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim requires the enhanced fragment algorithm to be competitive with or outperform state-of-the-art BPC on both PDPTW and TDDRP. For the PDPTW, Table 3 gives a direct comparison on the standard Ropke-Cordeau instances, and the claim is credible even though DD60 and CC70 are slower. For the TDDRP, however, Section 5.4 states that Yin et al.'s instances are not public, so the method is tested on instances 'generated according to their description', and the proposed solve times are compared with the BPC times reported by Yin et al. on their own, different instances. The paper explicitly concedes that comparing on differently generated instances is 'not ideal' but then concludes that the results are 'strong enough' to show outperformance. That inference is the load-bearing step: generated instances can differ in time-window tightness, depot and request geometry, route lengths, and request weights in ways that change exactly the quantity the method depends on, namely the route-formulation optimality gap and the tractability of enumeration. No evidence is given that the generated set reproduces the difficulty distribution of the original set, and the BPC times are not re-measured on the same machine or on the same instances. Thus the TDDRP half of the central comparative claim is unsupported by the experimental design, even though the algorithm may well be competitive.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an enhanced exact fragment-based algorithm for vehicle routing problems and applies it to the Pickup and Delivery Problem with Time Windows (PDPTW) and the Truck-Based Drone Delivery Routing Problem with Time Windows (TDDRP). Three enhancements are introduced: dynamic discretization discovery for the resource-expanded network, formulation leveraging that uses route-formulation reduced costs to filter fragments, and column enumeration for row elimination that concatenates fragments and removes network nodes. Sections 1–3 develop the general framework and prove that the fragment formulation is a relaxation that can represent every route (Theorems 1–4). Section 4 reports PDPTW experiments on Ropke–Cordeau instances, including a direct comparison with VRPSolver on the eight hard instances. Section 5 applies the framework to the TDDRP and compares against published BPC results by Yin et al. on instances that the authors generated because the original TDDRP instances are not public.","tokens_in":29500,"tokens_out":8598,"duration_ms":93010,"significance":"If the claims are fully supported, the paper would make a useful contribution: it gives a general route-formulation-leveraging mechanism for fragment methods, provides a plausible alternative to bespoke branch-and-price-and-cut implementations, and includes a substantial experimental study with a clear ablation of the proposed enhancements. The PDPTW part is the strongest component: it uses standard public benchmarks, a direct comparison with VRPSolver, and the variants in Table 2 isolate the contribution of each enhancement. The theoretical results are presented with proofs in the supplement, and the code and generated TDDRP instances are made available. The main weakness is the TDDRP comparison, which currently does not meet the standard needed for the state-of-the-art outperformance claim.","major_comments":[{"comment":"The TDDRP superiority claim is not supported by the experimental design. Because the original Yin et al. instances are unavailable, the authors generate instances 'according to their description' and compare their solve times with BPC times reported by Yin et al. on different instances. The paper itself concedes that this is 'not ideal', but then concludes that the results are 'strong enough' to show outperformance. No evidence is provided that the generated instances reproduce the difficulty distribution of the original benchmark, and the manuscript explicitly states that the method's efficiency depends on the route-formulation optimality gap and on enumeration tractability, both of which are sensitive to time-window tightness, request geometry, route lengths, and request weights. Moreover, the BPC times were not re-measured on the same machine or on the same instances. To support the claim, the authors should either obtain the original instances, validate that their generated instances reproduce the original difficulty distribution, or re-run an implementation of Yin et al.'s BPC on the generated instances on the same hardware.","section":"Section 5.4, Table 4"},{"comment":"The concluding sentence that the approach 'outperforms the best performing BPC algorithms for the PDPTW and the TDDRP' overstates the evidence in Tables 3 and 4. For the PDPTW, the one-thread fragment method is slower than BPC on CC70 (555.4 s vs 383.4 s) and does not solve DD60 within the 3600 s limit, while BPC solves it in 1435.3 s; the data support 'competitive with, and faster on most hard instances', not blanket outperformance. For the TDDRP, the only BPC comparison is the generated-instance setup discussed in the previous comment. The abstract and conclusion should be aligned with the level of support actually provided.","section":"Section 6 and Section 1.4"},{"comment":"The 'hard TDDRP instances' experiments do not include any BPC comparator, yet the text states that algorithms that branch before attempting route enumeration 'would also likely be outperformed by the fragment approach here'. Table 5 can support the more limited claim that the fragment approach remains viable when route enumeration is impractical, but it cannot support a state-of-the-art outperformance claim. The inference from absolute solve times on newly generated instances without a re-implemented baseline is not load-bearing evidence for the paper's central comparative claim.","section":"Section 5.4, Table 5"}],"minor_comments":[{"comment":"In the definition of drone-flight feasibility, the recurrence for s_{i_{j+1}} uses t^drone_{i_1,i_2} for all j; it should use the travel time of the edge actually traversed, t^drone_{i_j,i_{j+1}}.","section":"Section 5.1"},{"comment":"There are several wording typos: 'Truck-Based Drone Delivery Routing Problem Problem' in the abstract, 'or approach' in contribution 3, and 'we combine' beginning Section 3.1.1 with a lowercase letter. These should be corrected.","section":"Abstract and Section 1.4"},{"comment":"The description of the relaxation-size trade-off would benefit from a more explicit statement of how the longest-arc property interacts with the choice of initial discretization in the DDD setting, since the static-network intuition of a fixed delta is not directly carried over to the dynamic case.","section":"Section 3.1.7"},{"comment":"The proof of Theorem 2 is correct, but the new dual variable 'gamma' is introduced with the same symbol as the dual constraint term; a different name, such as mu, would improve readability.","section":"Supplement, Section 1.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and has a strong, well-executed PDPTW study. The TDDRP comparison is the central obstacle to accepting the paper, and the authors' own 'not ideal' statement in Section 5.4 confirms that the current experimental design cannot settle the state-of-the-art claim. I would encourage a revision that either obtains the original Yin et al. instances, validates the generated instances against the original ones, or provides a direct re-implementation of the BPC baseline on the generated instances. The theoretical development and the ablation study are otherwise solid, and I do not see a fundamental correctness issue in the main derivation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The PDPTW half is a real advance; the TDDRP half has a comparison problem that the authors half-acknowledge. If you take the TDDRP claims at face value you'll be misled; if you ignore them, there is still a strong paper.\n\nWhat's genuinely new: formulation leveraging—using the route formulation's strong lower bound to filter fragments—and column enumeration for row elimination, where surviving fragments are concatenated and re-filtered. That combination is clever and absent from the prior fragment literature. The extension of DDD from time-expanded networks to multi-resource expanded networks over fragments is also nontrivial. Theorems 3-4 check out, and the supplement proofs, while terse, are sound. The PDPTW experiments are credible: on the eight hardest Ropke-Cordeau instances, the one-threaded fragment method is faster than VRPSolver BPC on seven, DD60 being the clear exception. The ablation-style variants give useful evidence about which enhancement matters.\n\nWhere it gets soft: the TDDRP comparison. Yin et al.'s instances are not public, so the authors generate their own from the description and compare solve times against published BPC numbers. That is not a head-to-head. The paper explicitly says this is 'not ideal' but then concludes the results are 'strong enough' to claim outperformance. That is a load-bearing step, and the stress-test note is right: there is no evidence the generated instances reproduce the difficulty distribution of the original set—especially the route-formulation gap that FL and CERE depend on. Solve-time differences could arise from instance geometry rather than algorithmic strength. So the TDDRP superiority claim is not supported by the experimental design. It may be true, but this paper does not show it. Also, no code is released, which makes the computational results harder to verify. A minor point: the paper is honest about the structural limitation—FL and CERE need a small route-formulation optimality gap—stated clearly in Section 5.4 and the conclusion. It is a real limitation, but a stated one. Citation practice is fine; Boland et al. and Irnich et al. are properly credited.\n\nWho this is for: anyone working on exact VRP methods, especially pickup and delivery. The PDPTW results alone deserve referee time. The TDDRP part needs either softer claims or a proper comparison on the original instances if those become available.\n\nRecommendation: send it to peer review, with a referee asked to look hard at the TDDRP experiments. The authors should be encouraged to release code. Not desk-reject material.","headline":"Genuinely new fragment-enhancement ideas with strong PDPTW results; the TDDRP superiority claim rests on generated stand-in instances and is not proven.","tokens_in":30025,"tokens_out":3335,"would_cite":true,"duration_ms":30587,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B06","90C27","90C11"],"pacs":[],"model":"deepseek-v4-flash","headline":"A fragment-based network model, tightened by borrowing the route formulation's lower bound, solves the Pickup and Delivery Problem with Time Windows and matches or beats the leading branch-and-price-and-cut solver on both that problem and…","keywords":["vehicle routing problem","pickup and delivery problem with time windows","fragment formulation","resource expanded network","dynamic discretization discovery","formulation leveraging","column enumeration for row elimination","truck-based drone delivery routing problem with time windows"],"falsifier":"The cleanest experiment is to rerun the published branch-and-price-and-cut solver and the fragment method on identical hardware with the same time limit on the eight hardest PDPTW instances; the authors' own table already shows the boundary at DD60, so the claim's surviving version would specify where the gap-dependent failure starts. For the TDDRP half, the decisive test is the original benchmark set, which is not public: the paper compares against published results on instances it regenerates from the textual description, so if the originals were released and the competitor matched or beat the fragment method on them within the time limit, the superiority claim would fail.","tokens_in":28998,"feed_emoji":"🚚","tokens_out":24473,"duration_ms":204150,"temperature":0.7,"pith_summary":"Exact vehicle routing is normally done by branch-and-price-and-cut: generate candidate routes on the fly, cut, and branch. This paper argues that a different object—the fragment, a short enumerable segment of a route—can carry the whole solution process, provided three enhancements are added: adaptive construction of a resource-expanded network (dynamic discretization discovery, DDD), borrowing the route formulation's lower bound to delete fragments that cannot be optimal (formulation leveraging, FL), and concatenating fragments to lengthen paths and shrink the model (column enumeration for row elimination, CERE). The payoff the paper tries to establish is that, for the first time, a fragment method effectively solves the Pickup and Delivery Problem with Time Windows, solving all 40 standard benchmark instances and outperforming the leading branch-and-price-and-cut solver on most of the eight hardest (the paper flags DD60 as the one significant loss). On the Truck-Based Drone Delivery Routing Problem with Time Windows it solves more generated instances within the time limit than the published branch-and-price-and-cut results. If true, this matters because it offers a general exact-VRP recipe that delegates the search to a commercial mixed-integer solver instead of requiring a bespoke branch-and-price implementation.","feed_headline":"Fragment solver beats branch-and-price on hard pickup-delivery","feed_subtitle":"A fragment network model solves pickup-delivery and truck-drone instances faster than the state of the art.","key_machinery":"The object that carries the argument is the resource expanded network (REN), built from fragments. A fragment is an enumerable sub-path of a route together with the fixed state of the problem's non-disposable resources at its start (for the PDPTW, the set of deliveries already onboard); fragments are joined into chains that represent routes, and the network's nodes are resourced copies of locations at discrete values of the disposable resources (time, and for the TDDRP also load). The fragment formulation is a mixed-integer network flow program on this network whose only constraints are request covering and flow conservation. Three mechanisms decide which nodes and arcs exist: DDD adds resourced nodes only where an underestimating chain must be removed; FL uses the route formulation's dual solution and forward/backward labelling to compute a lower bound $\\rho_\\omega$ on the reduced cost of any route containing a given fragment, discarding fragments whose bound exceeds the optimality gap; and CERE replaces the fragments starting and ending at a node with their concatenations, absorbing the node. The network is 'relaxed' in a designed way—the early-arrival and longest-arc properties round end resource values down to the latest available node—so Theorem 1 guarantees every route is representable, and the enhancements are precisely what prevents the relaxation from being too loose to solve.","core_discovery":"On the paper's own terms, the discovery is that the weakness of fragment formulations—a loose linear relaxation and fragments too short to capture route structure—can be repaired so thoroughly that the fragment model becomes the solver of record. DDD grows the resource-expanded network adaptively, adding discretized resource states only when an 'underestimating chain' (a network path representing a resource-infeasible route) must be eliminated. FL takes the optimal dual solution of the route formulation's root master problem, obtained once by column generation, and uses reduced-cost arguments (Theorems 3 and 4) to remove every fragment that cannot appear in an optimal solution, with limited-memory rank-1 cuts tightening the gap further. CERE joins fragments end-to-end at selected nodes, strengthening the relaxation and absorbing flow-conservation constraints. Since Theorem 1 guarantees every route has a representation as a chain of resourced fragments, the fragment network is a true relaxation of the VRP; when the enhancements keep that relaxation strong and small, a commercial solver finishes the branch-and-bound search. The paper's headline result follows: the enhanced fragment algorithm 'for the first time, effectively solves the PDPTW', and on most of the eight hardest benchmark instances it is faster than the state-of-the-art branch-and-price-and-cut algorithm, with DD60 the one significant exception.","pith_inferences":["Beyond the paper: the cleanest test of the generality claim is the planned VRPTW experiment—if the same three enhancements stay competitive on a problem with a heavily optimized branch-and-price baseline, the recipe itself is doing the work; if not, pickup-delivery structure is load-bearing.","Beyond the paper: the DD60 failure mode suggests a hybrid the authors only mention in passing—branch once on the route formulation when the fragment phase stalls, using each child's tighter dual bound to restore the filtering power that FL and CERE need.","Beyond the paper: reading Section 5.4 as a design rule, the algorithm's competitiveness is governed by the ratio of master-problem cost to fragment-formulation strength rather than by instance size; applications with cheap pricing and short routes should expect little or no gain from this approach."],"forward_implications":["The fragment method becomes a workable exact approach for the PDPTW: all 40 standard benchmark instances are solved to optimality, and on the eight hardest the one-threaded fragment algorithm beats the leading branch-and-price-and-cut solver on a majority of instances, with DD60 the one significant loss.","The framework carries over to a VRP with no pickup-delivery structure: on the TDDRP it solves more of the generated instances within the time limit than the published branch-and-price-and-cut results, and it still works on harder instances where route enumeration fails at the achieved optimality gaps.","Because the fragment model is a mixed-integer network flow program, a commercial solver supplies branching, cutting and parallelism; the paper reports that DD60, which takes 3600 s on one thread, is solved in under an hour with eight threads.","The general description of fragments and the resource-expanded network is argued to apply to any VRP whose routes are elementary paths obeying problem-specific rules, with the VRPTW named as the next planned test.","The regime where the method should beat branch-and-price-and-cut is diagnostic: the paper concludes it wins when the master problem is expensive to solve and route enumeration is hard even for tiny optimality gaps—in practice, when average route lengths are large, as in the hard PDPTW and TDDRP instances."],"supporting_citations":[{"why":"Supplies dynamic discretization discovery, the adaptive mechanism the paper extends from partially time-expanded service-network models to resource expanded networks with multiple disposable resources.","marker":"Boland et al. (2017)"},{"why":"Supplies the path-reduced-cost variable fixing technique that formulation leveraging applies, through Theorems 3 and 4, to delete fragments from the model.","marker":"Irnich et al. (2010)"},{"why":"Provides the restricted-fragment definition the paper builds on, and the claim that the approach is almost directly applicable to the PDPTW, which the paper sets out to make true.","marker":"Rist and Forbes (2021)"},{"why":"Provides extended fragments, reduced-cost filtering, and the feasibility-cut treatment of underestimating chains that the new method overhauls with DDD, FL, and CERE.","marker":"Rist and Forbes (2022)"},{"why":"Provides the original fragment method and the time-expanded network idea for a pickup-and-delivery problem, plus the multi-threaded commercial-solver comparison style.","marker":"Alyasiry et al. (2019)"},{"why":"Supplies the branch-and-price-and-cut solver whose runtimes are the PDPTW benchmark to beat, and the master-problem dual solutions used for formulation leveraging.","marker":"Pessoa et al. (2020)"},{"why":"Supplies the hard PDPTW benchmark instances (classes AA, BB, CC, DD) on which the fragment method and the branch-and-price-and-cut baseline are compared.","marker":"Ropke and Cordeau (2009)"},{"why":"Defines the truck-based drone delivery routing problem and supplies the branch-and-price-and-cut results and instance-generation description used for the second comparison.","marker":"Yin et al. (2023)"},{"why":"Introduces rank-1 subset-row cuts, which the paper uses in limited-memory form to tighten the route formulation's optimality gap that FL depends on.","marker":"Jepsen et al. (2008)"},{"why":"Introduces limited-memory rank-1 cuts, the implementation variant used when strengthening the master problem in steps 1 and 2 of the algorithm.","marker":"Pecin et al. (2017)"}],"fun_headline_variants":["Fragment solver cracks pickup-delivery with time windows","Enhanced fragments outpace branch-and-price on VRP","Dynamic discretization and formulation leveraging crack VRP","First fragment algorithm to handle pickup-delivery with time windows","Fragment method now competitive on pickup-delivery and truck-drone"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method lives or dies by one premise the paper states outright in Section 5.4: after the first pricing phase, the gap between the route formulation's lower bound and the true best solution must be small enough that the filtering and fragment-lengthening steps can keep the fragment network small while still strong—instance DD60, where the fragment method stalls at 3600 seconds against 1435 for the competitor, is the paper's own example of the premise failing.","fun_headline_variants_meta":{"raw":{"variants":["Fragment solver cracks pickup-delivery with time windows","Enhanced fragments outpace branch-and-price on VRP","Dynamic discretization and formulation leveraging crack VRP","First fragment algorithm to handle pickup-delivery with time windows","Fragment method now competitive on pickup-delivery and truck-drone"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001139,"raw_usage":{"total_tokens":4766,"prompt_tokens":1021,"completion_tokens":3745,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":3668}},"tokens_in":637,"tokens_out":3745,"duration_ms":26299,"temperature":1.0,"reasoning_tokens":3668,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:46:27.898545+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The cleanest experiment is to rerun the published branch-and-price-and-cut solver and the fragment method on identical hardware with the same time limit on the eight hardest PDPTW instances; the authors' own table already shows the boundary at DD60, so the claim's surviving version would specify where the gap-dependent failure starts. For the TDDRP half, the decisive test is the original benchmark set, which is not public: the paper compares against published results on instances it regenerates from the textual description, so if the originals were released and the competitor matched or beat the fragment method on them within the time limit, the superiority claim would fail.","supporting_citations":[{"cited_title":"INFORMS journal on computing 22(2):297--313, ISSN 1091-9856, ://dx.doi.org/10.1287/ijoc.1090.0341","cited_arxiv_id":null,"evidence_quote":"Supplies the path-reduced-cost variable fixing technique that formulation leveraging applies, through Theorems 3 and 4, to delete fragments from the model."},{"cited_title":"Transportation science 55(5):1113--1135, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.2021.1044","cited_arxiv_id":null,"evidence_quote":"Provides the restricted-fragment definition the paper builds on, and the claim that the approach is almost directly applicable to the PDPTW, which the paper sets out to make true."},{"cited_title":"Transportation science 53(6):1695--1705, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.2019.0905","cited_arxiv_id":null,"evidence_quote":"Provides the original fragment method and the time-expanded network idea for a pickup-and-delivery problem, plus the multi-threaded commercial-solver comparison style."},{"cited_title":"Transportation science 43(3):267--286, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.1090.0272","cited_arxiv_id":null,"evidence_quote":"Supplies the hard PDPTW benchmark instances (classes AA, BB, CC, DD) on which the fragment method and the branch-and-price-and-cut baseline are compared."},{"cited_title":"European journal of operational research 309(3):1125--1144, ISSN 0377-2217, ://dx.doi.org/10.1016/j.ejor.2023.02.030","cited_arxiv_id":null,"evidence_quote":"Defines the truck-based drone delivery routing problem and supplies the branch-and-price-and-cut results and instance-generation description used for the second comparison."},{"cited_title":"Operations research 56(2):497--511, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.1070.0449","cited_arxiv_id":null,"evidence_quote":"Introduces rank-1 subset-row cuts, which the paper uses in limited-memory form to tighten the route formulation's optimality gap that FL depends on."},{"cited_title":"Operations research letters 45(3):206--209, ISSN 0167-6377, ://dx.doi.org/10.1016/j.orl.2017.02.006","cited_arxiv_id":null,"evidence_quote":"Introduces limited-memory rank-1 cuts, the implementation variant used when strengthening the master problem in steps 1 and 2 of the algorithm."}],"review_version":1}