{"id":"e7b37520-f4bc-4d71-9dd0-d67099c17d91","arxiv_id":"2604.23748","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A branch-price-and-cut method with lifted TSP-optimality cuts solves fair vehicle routing instances up to 25 customers with 0.27% average gap on hard cases.","lead":"The paper develops a branch-price-and-cut algorithm for the fair capacitated vehicle routing problem that adds TSP-optimality cuts to stop routes from being artificially lengthened to reduce the range between longest and shortest tours. This targets a non-monotonic fairness objective that standard methods handle poorly.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption correctly flags the validity/sufficiency of the cuts, but the monotonicity property of the range objective (any lengthening of a route cannot improve the objective) makes the 'without cutting optimal solutions' part hold unconditionally. The remaining questions (whether the specific cuts are complete and whether pricing/separation scale) are addressed by the computational results on the tested sizes; no internal inconsistency or unsupported derivation is visible from the abstract and claim description.","tokens_in":1677,"tokens_out":351,"duration_ms":27363,"concrete_test":"On the smallest benchmark instances (n=10), extract the customer subsets from the reported optimal solutions, solve the corresponding TSPs independently, and verify that every route length equals the TSP optimum; also confirm that the lifted cuts do not exclude these solutions when added to the master.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern identified. The central claim is that TSP-optimality cuts (forbidding dominated arc sequences) plus lifting, embedded in branch-price-and-cut, correctly enforce minimal-length routes for the range objective without excluding globally optimal fair solutions and remain computationally viable up to 25 customers. The key supporting fact is that, for any fixed customer-to-vehicle assignment, increasing the length of any route above its TSP minimum can only increase or preserve the range (max length non-decreasing, min length non-increasing). Hence an optimal fair solution always exists in which every route is TSP-optimal, so the cuts are safe. Sufficiency follows if the cuts plus lifting describe the convex hull of TSP-optimal route variables; tractability is evidenced by the reported solution rates and gaps.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1829,"tokens_out":512,"duration_ms":22935,"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":[{"comment":"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.","section":"Computational Experiments"}],"minor_comments":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"§3.2"}],"recommendation":"minor_revision","confidential_remarks":"The computational claims rest on post-hoc selection of 'hardest' subsets; requiring the authors to report results on the full benchmark set (with clear instance-selection protocol) would strengthen the paper without altering its core contribution."},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"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."}],"tokens_in":1279,"tokens_out":274,"duration_ms":30249,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The central move is straightforward once you see it. For any fixed customer-to-vehicle assignment the range can never get worse if you shorten every route to its TSP length, so any optimal fair solution can be assumed to use only TSP-optimal routes. The authors turn that observation into cuts that forbid TSP-dominated arc sequences and then lift them to make them tighter. That construction is the actual novelty here; it is not just a standard VRP cut recycled for a new objective. They embed the cuts in a branch-price-and-cut framework and report that it closes nearly all instances up to 25 customers with an average gap of 0.27 percent on the harder ones. The math checks out on paper and the computational claim is at least plausible given the instance sizes they test. No load-bearing circularity or self-fitting shows up in the reported results. The main soft spot is scale. Twenty-five customers is still modest for capacitated VRP, and the abstract gives little on separation times, cut counts, or run-to-run variability, so it is hard to judge how far the method will stretch without seeing the full tables. If the full paper supplies those numbers and shows the separation routine stays fast, the weakness is minor; if not, it limits how much weight the experiments can carry. This is useful reading for anyone already working on exact methods for fair or multi-objective VRP variants. A referee who knows branch-price-and-cut and routing polyhedra would find enough substance to review it seriously. I would send it out rather than desk-reject.","headline":"The paper adds TSP-optimality cuts plus a lifting step inside branch-price-and-cut to keep the range objective from rewarding artificially long routes, and the logic holds up.","tokens_in":2294,"tokens_out":388,"would_cite":false,"duration_ms":27569,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"TSP-optimality cuts eliminate dominated routes and solve fair vehicle routing instances to near-optimality.","keywords":["fair vehicle routing","TSP-optimality","cutting planes","branch-price-and-cut","capacitated VRP","range minimization","route dominance","exact methods"],"falsifier":"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.","tokens_in":2580,"feed_emoji":"🚛","tokens_out":747,"duration_ms":32520,"temperature":0.7,"pith_summary":"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.","feed_headline":"TSP cuts block artificial detours in fair routing","feed_subtitle":"Lifted cuts forbid dominated arc sequences so that minimizing route-range yields shortest individual paths on instances up to 25 customers.","key_machinery":"TSP-optimality cuts that forbid TSP-dominated arc sequences, strengthened by a dedicated lifting procedure, embedded in a branch-price-and-cut framework.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["TSP-optimality cuts eliminate dominated arcs in fair vehicle routing","Lifted TSP cuts ensure shortest routes in range-minimizing VRP","TSP cuts forbid dominated arc sequences in fair routing","Branch-price-and-cut solves fair VRP instances up to 25 customers"],"cache_read_input_tokens":64,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["TSP-optimality cuts eliminate dominated arcs in fair vehicle routing","Lifted TSP cuts ensure shortest routes in range-minimizing VRP","TSP cuts forbid dominated arc sequences in fair routing","Branch-price-and-cut solves fair VRP instances up to 25 customers"]},"model":"grok-4.3","cost_usd":0.010227,"raw_usage":{"total_tokens":4499,"prompt_tokens":601,"num_sources_used":0,"completion_tokens":70,"cost_in_usd_ticks":102274500,"prompt_tokens_details":{"text_tokens":601,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3828,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":601,"tokens_out":70,"duration_ms":69320,"temperature":1.0,"reasoning_tokens":3828,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-08T05:53:26.081963+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}