{"id":"cad14104-a671-425f-a0fe-b22cb5728f85","arxiv_id":"2411.17080","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A two-stage neural solver for multi-depot vehicle routing, combining a tour-assignment transformer with a per-tour TSP router, reports near-optimal results on instances up to 1,000 customers.","lead":"This paper introduces DeepMDV, a two-stage deep learning method that assigns customers to depots and tours, then optimizes the route inside each tour, for the multi-depot vehicle routing problem. Tests on synthetic and real-world data report better or comparable travel distance than existing learning-based solvers on instances up to 1,000 customers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"HGS comparison on MDVRP1K is likely the load-bearing weakness: HGS gets only ~72 s/instance, no time-quality curve is shown, and Table 2 already contradicts 'outperforms all baselines' in skewed settings.","rationale":"The reader's weakest_assumption focuses on Section 3.1's 'one active tour per depot' rule, but that rule does not by itself prevent representing a final solution with multiple tours from the same depot: construction can close an active tour and open a standby tour from the same depot, so a two-tour-per-depot solution is representable. The actual restriction is the cap lmax = ceil(sum of demands / C) + |D| and the deactivation threshold T_t in Equations (1)-(2), which prevent closing a tour before its used capacity exceeds T_t; in clustered instances with many low-demand remote groups, an optimal solution can require more underfull tours than this cap allows. That is a heuristic bias, not a proven optimality bound, and it likely explains HGS's wins in Table 2. However, the headline '3.25% improvement on MDVRP1K' survives or fails on the HGS time budget. HGS gets 2 hours for 100 instances, or about 72 seconds per 1,000-customer instance, while DeepMDV is allowed a learned partitioner plus LKH3; no HGS time-quality curve is reported. Because HGS/PyVRP is known to improve with more runtime, the claimed superiority may be an artifact of an unduly short HGS budget. This is directly load-bearing for the abstract and Section 5.2 claims, and it is checkable by retiming HGS. I therefore recommend keeping the conditional verdict, adding a condition that the HGS comparison be re-run with several per-instance budgets or explicitly scoped to the 72-second budget.","tokens_in":115,"tokens_out":11808,"duration_ms":236676,"concrete_test":"Take the MDVRP1K benchmark from Table 1 (same 100 instances and seeds) and rerun HGS/PyVRP with per-instance time limits of 1, 5, 15, and 30 minutes, keeping all other settings fixed. Record the mean objective at each budget. If any budget produces a mean no larger than DeepMDV's reported values (38.67 for |D|=2, 36.29 for |D|=3, 35.13 for |D|=4) and the improvement over the 72-second HGS result is at least 3.25%, the headline 'surpasses HGS' is a time-budget artifact and must be rescoped to the stated 72-second limit. Also report variance across at least 5 seeds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim in Section 5.2 ('DeepMDV surpasses even HGS... at least a 3.25% improvement on MDVRP1K') rests on Table 1, where HGS is run for 2 hours total across 100 instances: about 72 seconds per 1,000-customer instance. HGS/PyVRP is a strong metaheuristic whose solution quality improves steeply with runtime, and the paper provides no time-quality curve and no evidence that 72 seconds is a fair budget for instances of this size. If HGS is allowed a few minutes per instance, its objective may fall below DeepMDV's reported values (38.67, 36.29, and 35.13 for 2, 3, and 4 depots respectively), which would turn the headline 'improvement' into an artifact of an unequal time budget. The abstract's 'outperforms all baselines' is additionally already contradicted by Table 2, where HGS remains best in skewed distributions, so the empirical claim must be scoped to uniform instances and to the stated runtime limit. The reader's candidate weakness, the one-active-tour-per-depot rule in Section 3.1, is not the main risk: multiple tours from one depot can be constructed sequentially, and the real representational restriction is the hard cap lmax and the deactivation threshold in Equations (1)-(2), which can exclude underfull tours in clustered instances; that is evident in HGS's wins in the skewed experiments.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DeepMDV, a two-stage deep reinforcement learning framework for the Multi-Depot Vehicle Routing Problem (MDVRP). A transformer-based partitioner assigns customers to depots and tours through a global spatial matching mechanism, and an independent router (AM or LKH3) solves the resulting TSP subproblems. The method uses a three-step training procedure and a proposed formula for an upper bound on the number of tours. Experiments on synthetic uniform, skewed, and real-world datasets report that DeepMDV outperforms learning-based baselines at all scales and, for 1,000-customer instances, surpasses HGS by 3.25% or more, while also generalizing to varying depot counts and to single-depot VRP.","tokens_in":25332,"tokens_out":5277,"duration_ms":47327,"significance":"If the empirical claims hold under fair comparison, this is a strong practical contribution: it is among the first learning-based MDVRP methods to scale to 1,000 customers, runs in seconds per instance, and shows robustness across depot counts and spatial distributions. The paper's strengths include extensive experiments across multiple datasets, a real-world case study with Gurobi as reference, a sensitivity analysis of the key hyperparameter k, and an ablation study isolating the main components. At the same time, the central comparative claims rest on a small number of tables and on the choice of runtime budgets for the metaheuristic baseline; the current presentation overstates the results relative to what the tables actually show. If the HGS comparison is made fair and scoped, the contribution would be solid; as written, the headline superiority claims are not yet fully supported.","major_comments":[{"comment":"The headline claim that DeepMDV surpasses HGS by at least 3.25% on MDVRP1K is computed against HGS run for 2 hours total per 100 instances, i.e., about 72 seconds per 1,000-customer instance. HGS/PyVRP is known to improve steeply with additional runtime, yet no time-quality curve is provided, and the text's statement that HGS 'becomes computationally expensive and infeasible for larger problems' is not supported by a 72-second budget. Please report HGS with substantially longer per-instance budgets (e.g., 5–30 minutes) and include time-quality curves, or qualify the 'surpasses HGS' claim as being specific to the stated short budget.","section":"Section 5.2, Table 1"},{"comment":"The (LKH3, G, P) variant reports, for each instance, the best result obtained over four different values of k (30%, 40%, 50%, and 60% of the customer count) using multiple GPUs, while all other methods are reported as single runs. The 3.25% improvement is therefore a best-of-four-k result, and no mean, standard deviation, or training-seed variance is provided. Please report results for fixed-k variants and include error bars or variance information, and clearly disclose the multiple-trial selection procedure. Without this, the margin that drives the central claim is not a fair single-configuration comparison.","section":"Section 5.2, Table 1, DeepMDV (LKH3, G, P) variant"},{"comment":"The abstract's claim that 'our method outperforms all baselines across varying problem sizes' is internally contradicted by Table 2, where HGS achieves the best objective in every skewed-distribution setting, and by Table 1, where HGS is the best method for all instances with up to 400 customers. The empirical claims should be scoped to learning-based baselines and to the uniform-distribution, large-instance regime. As written, the abstract's sweeping wording overstates the results and should be corrected.","section":"Section 5.2 and abstract; Table 2"},{"comment":"The paper asserts that restricting the search to at most one active tour per depot, and the related upper bound l_max = ceil(sum(demands)/C) + |D| with the deactivation threshold T_t, do not exclude optimal solutions. This is not proven. The threshold in Equations (1)-(2) forces tours to be filled beyond T_t before deactivation, which can exclude optimal solutions that contain many underfull tours from the same depot; the HGS wins in the skewed experiments of Table 2 are consistent with this risk. Please either provide a proof of optimality preservation or add an ablation that compares against unconstrained tour counts on small instances where exact solutions are available.","section":"Section 3.1 and Section 4.1, Equations (1)-(2) and (10)"}],"minor_comments":[{"comment":"Equation (16) as written requires every vehicle v to depart from and return to every depot d, which is not the MDVRP; the formulation should select a unique depot for each vehicle.","section":"Appendix A, Equation (16)"},{"comment":"The TAM-AM entry for CVRP7k reports an objective of 10.1 with a 24.9% gap relative to HGS = 212; this is numerically inconsistent and appears to be a typo (the objective should be around 264.7). Please correct it.","section":"Table 7 (Appendix C)"},{"comment":"The text states HGS runtimes were increased to 60 minutes for small and 6 hours for large instances, while the Table 2 caption says 40M, 100M, and 5H for 100, 400, and 1,000 customers, respectively. Please clarify whether these are per-instance or total-for-100-instances budgets and reconcile the two statements.","section":"Section 5.3 and Table 2 caption"},{"comment":"Reference [26] is cited as 'Berman et al.' but the bibliography entry is Ombuki-Berman and Hanshar; the ACM Reference Format line contains '2018' while the conference year is 2025; and Figure 3's caption should clarify whether 'Obj' is the normalized Euclidean objective or the raw distance, since the text describes both.","section":"References and front matter"},{"comment":"The training description says that tours are padded by repeating the depot node, but it is not stated how this padding is masked during loss computation; please clarify to avoid the router being trained on repeated depot tokens.","section":"Section 4.4"}],"recommendation":"major_revision","confidential_remarks":"The core idea is interesting and the scale of experiments is a strength, but the central 'surpasses HGS' claim currently rests on a short HGS budget and a best-of-multiple-k selection procedure. This is likely to be the main issue raised by other reviewers. A major revision that adds time-quality curves, error bars, fixed-k results, and scoped claims would make the paper acceptable. I would also encourage the authors to include a code/data availability statement, since reproducibility is important for a learning-based systems paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: DeepMDV is a well-built, incremental neural architecture for multi-depot VRP that scales to 1000 customers and claims an edge over HGS on uniform instances. The headline result is real only under a tight HGS time budget, and the paper overstates it in the abstract.\n\nWhat's new: the task-decoupled partitioner/router with the TSLCGL local-context layer, polar coordinate encoding, and three-step fine-tuning of the router on partitioner tours. None of these are large leaps individually, but the combination is novel for MDVRP, and the cross-scale results (100 to 1000 customers, 1-4 depots) go considerably beyond earlier learned MDVRP solvers, which stall around 100 customers. The experiments are extensive: many baselines, uniform and skewed synthetic data, a real-world set, ablations, sensitivity analysis, and a memory comparison on 20k-customer instances. The Melbourne case study with Gurobi is a nice sanity check.\n\nWhere it's soft: the 'outperforms HGS' claim rests on a runtime budget of about 72 seconds per 1000-customer instance. HGS is a strong metaheuristic whose quality improves steeply with time; the paper shows no time-quality curve and even contradicts itself (Appendix B says 60s max per instance, Table 1 implies 72s average). With a few minutes per instance, HGS may close or reverse the gap. Also, the (G,P) variant selects the best of several k values per instance, which inflates results; there are no error bars or multiple seeds, and Table 7 has an obvious numerical typo (TAM-AM CVRP7k Obj=10.1). The abstract's 'outperforms all baselines' is already false on Table 2's skewed data, where HGS remains best.\n\nThe one-active-tour-per-depot restriction (Section 3.1) is not the main risk; tours from the same depot can be built sequentially, and the stronger limitation is the hard tour cap and deactivation threshold, which hurt on clustered instances—consistent with HGS's wins on skewed data.\n\nWho this is for: researchers building learned solvers for large-scale VRP/MDVRP. The architecture is a reasonable starting point and the evaluation methodology is a useful cautionary example. It deserves a serious referee, but acceptance should be conditional on code/data release, a fair HGS budget with time-quality curves, variance reporting, and corrected claims.","headline":"Solid, incremental neural MDVRP solver with a strong but over-scoped HGS comparison; deserves conditional acceptance after code release and fairer baselines.","tokens_in":25812,"tokens_out":3449,"would_cite":false,"duration_ms":30101,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90B06","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"DeepMDV claims a learned multi-depot routing solver that scales to 1,000 customers and beats a strong classical heuristic on large instances.","keywords":["Spatial data management","Vehicle Routing Problem","Deep reinforcement learning","Multi-depot VRP","Transformer decoder","Neural combinatorial optimization","Scalability","Generalization"],"falsifier":"Build a benchmark instance whose proven optimum needs a single depot to run two partially loaded tours concurrently (for example, two dense clusters near the same depot, total demand just over one vehicle capacity, and the other depots far away), then compare DeepMDV's total distance with HGS or an exact solver. If DeepMDV's objective falls well behind HGS on such instances, the one-active-tour-per-depot restriction is the limiting factor.","tokens_in":24783,"feed_emoji":"🚚","tokens_out":10247,"duration_ms":81054,"temperature":0.7,"pith_summary":"The paper presents DeepMDV, a deep-reinforcement-learning solver for the Multi-Depot Vehicle Routing Problem (MDVRP), and claims it is the first learning-based method that scales to 1,000 customers while generalizing to depot counts it never saw during training. The central idea is to split the problem into two decoupled tasks: an interdependent partitioner that globally matches customers to depot-tours, and an independent router that sequences visits within each tour with a TSP solver. On synthetic, skewed, and real-world benchmarks, DeepMDV reports better distances than every learning-based baseline, and on 700- to 1,000-customer instances it reports improvements over HGS, a strong classical metaheuristic, while producing each solution in seconds. If these results hold, near-optimal multi-depot delivery planning becomes practical at urban scale without retraining for new depot configurations.","feed_headline":"Neural routing beats classical heuristic at 1,000 customers","feed_subtitle":"Two-stage design gives near-optimal routes in seconds and transfers to unseen depot counts","key_machinery":"The load-bearing object is the decoder made of the Tour Selection and Local Context Generation Layer (TSLCGL) paired with the Node Selection Layer (NSL). TSLCGL looks at the $k$ nearest unvisited customers around each active tour's last node, computes a local context by multi-head attention over every active tour's state (depot embedding, last node, remaining capacity), and produces a compatibility score for choosing the next tour; NSL then picks the next customer for that tour using the enriched embeddings. A second load-bearing component is the closed-form estimate of the maximum number of tours, $\\lceil \\sum_i \\delta_i / C \\rceil + |D|$, which masks when new tours can start and when active tours can return to the depot. The three-step training procedure, in which the router is first trained on uniform TSP instances, the partitioner is then trained using that router's tour lengths as reward, and the router is finally fine-tuned on the partitioner's tours, is what lets the router cope with the non-uniform spatial distributions found inside large tours.","core_discovery":"DeepMDV's claim is that customer-to-depot assignment and tour formation in the MDVRP can be learned as a global spatial matching problem, decoupled from intra-tour sequencing, without sacrificing solution quality. The partitioner is a transformer-based policy that, at each decoding step, first selects the most compatible active tour and then the best unvisited customer for it; a local-context layer evaluates each candidate customer against all active tours instead of only the selected one, so the assignment reflects the whole system state. The independent router then solves a TSP per tour, so any TSP solver can be plugged in, with AM used during training and LKH3 at inference. The paper reports that this architecture outperforms all learning-based baselines across 2 to 4 depots and 100 to 1,000 customers, and that on 1,000-customer instances it improves on HGS by at least 3.25%, with each instance solved in about 5 seconds; it also reports that the same model, trained on two depots, transfers to one, three, or four depots and to single-depot VRP without retraining.","pith_inferences":["A natural test of the paper's central mechanism is whether the one-active-tour-per-depot restriction ever costs optimality: on instances whose optimum requires a depot to run two partially filled tours simultaneously, DeepMDV cannot represent that solution, and its measured edge over HGS could shrink.","The polar-coordinate input encoding, which makes representations invariant to shifts, rotations, and scaling, suggests the model might transfer across different map scales or coordinate systems without fine-tuning, though the paper does not isolate this effect.","The tour-count formula $\\lceil \\sum_i \\delta_i / C \\rceil + |D|$ generalizes a known VRP bound and could be adapted to time windows or heterogeneous fleets as a cheap feasibility mask for other learned solvers.","If the claimed scaling is robust, the partitioner could be stacked with a portfolio of TSP solvers selected by instance geometry, turning DeepMDV into a meta-solver whose quality tracks the best available router."],"forward_implications":["If the reported results hold, logistics operators can get near-optimal multi-depot routes for 1,000-customer instances in seconds, where classical metaheuristics take hours or run out of memory.","A single model trained with two depots transfers to one, three, or four depots with small gaps, so deployments with changing depot counts do not need retraining.","Because routing is a separate TSP subproblem, any future improvement in TSP solving translates directly into better DeepMDV solutions without changing the partitioner.","DeepMDV retains most of its advantage on skewed customer distributions and real-world instances, where distance-based clustering baselines degrade, suggesting it is suited to heterogeneous urban logistics.","A model trained for MDVRP also beats VRP-specific learned solvers on large single-depot instances, so the same method can serve both multi-depot and single-depot routing."],"supporting_citations":[{"why":"Supplies the attention-model encoder architecture and the AM TSP solver used during training as the router and reward estimator.","marker":"[17]"},{"why":"Provides the HGS metaheuristic baseline that DeepMDV claims to beat on 700- and 1,000-customer instances.","marker":"[34]"},{"why":"RouteFinder is the strongest learning-based MDVRP baseline, used as a primary comparison in the experiments.","marker":"[4]"},{"why":"POMO is a single-depot learned solver adapted via clustering, serving as a baseline that scales poorly beyond small instances.","marker":"[18]"},{"why":"MADRL is the prior learning-based MDVRP method used on real-world instances for gap comparison.","marker":"[2]"},{"why":"GLOP is a large-scale learned VRP baseline used with LKH3, included in both MDVRP and single-depot VRP comparisons.","marker":"[39]"},{"why":"UDC is a large-scale neural divide-and-conquer baseline used for VRP and MDVRP comparisons.","marker":"[41]"},{"why":"Supplies the inspiration for the optimal tour-count constraint and the three-step training approach for non-uniform tour distributions.","marker":"[15]"},{"why":"LKH3 is the TSP solver used at inference as the router, producing the best DeepMDV results.","marker":"[14]"},{"why":"Provides real-world MDVRP instances used to evaluate performance against best-known solutions.","marker":"[7]"}],"fun_headline_variants":["Global matching cracks multi-depot routing at scale","Two-stage neural router trumps HGS on 1,000 stops","Learn to match depots, then route: new MDVRP solver","Neural MDVRP: 3.25% better than HGS, 5s per instance","Trained on 2 depots, works on 4: transferable routing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"DeepMDV assumes only one active tour per depot at a time, so it cannot represent optimal solutions in which a depot runs two partially filled tours simultaneously.","fun_headline_variants_meta":{"raw":{"variants":["Global matching cracks multi-depot routing at scale","Two-stage neural router trumps HGS on 1,000 stops","Learn to match depots, then route: new MDVRP solver","Neural MDVRP: 3.25% better than HGS, 5s per instance","Trained on 2 depots, works on 4: transferable routing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000147,"raw_usage":{"total_tokens":1220,"prompt_tokens":1015,"completion_tokens":205,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":631,"completion_tokens_details":{"reasoning_tokens":105}},"tokens_in":631,"tokens_out":205,"duration_ms":2827,"temperature":1.0,"reasoning_tokens":105,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:32:20.866003+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a benchmark instance whose proven optimum needs a single depot to run two partially loaded tours concurrently (for example, two dense clusters near the same depot, total demand just over one vehicle capacity, and the other depots far away), then compare DeepMDV's total distance with HGS or an exact solver. If DeepMDV's objective falls well behind HGS on such instances, the one-active-tour-per-depot restriction is the limiting factor.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the attention-model encoder architecture and the AM TSP solver used during training as the router and reward estimator."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"POMO is a single-depot learned solver adapted via clustering, serving as a baseline that scales poorly beyond small instances."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"MADRL is the prior learning-based MDVRP method used on real-world instances for gap comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GLOP is a large-scale learned VRP baseline used with LKH3, included in both MDVRP and single-depot VRP comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"UDC is a large-scale neural divide-and-conquer baseline used for VRP and MDVRP comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides real-world MDVRP instances used to evaluate performance against best-known solutions."}],"review_version":1}