{"id":"0fbe49ab-f113-4e7c-9d87-0d27ada10cee","arxiv_id":"2607.13789","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"DVOP, a second-order dynamics extension of the orienteering problem for multi-rotor UAVs, is solved by an LTD-based LNS heuristic and a MILP-primitive BnB that improves KOP rewards by up to 37%.","lead":"This paper introduces the Dynamical Vehicle Orienteering Problem, a drone route-planning task that combines collecting rewards from targets with time-optimal flight under gravity and acceleration limits. It offers a fast heuristic and a branch-and-bound solver, reporting up to 37% better rewards than prior kinematic orienteering methods and validating the trajectories on a real quadrotor.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'exact BnB' claim is unsupported: IPOPT local solutions and n_sub=5 cap can invalidate the reward upper bound and prune the optimum.","rationale":"The reader's weakest_assumption exactly identifies the load-bearing concern: the BnB's exactness relies on global optimality of nonconvex trajectory NLPs, but IPOPT is only locally convergent and n_sub=5 is an empirical cap. This is not a minor implementation detail; it directly breaks the chain of inequalities used for pruning. The paper's own wording in Sec. 5.4, admitting that increasing switches beyond 5 did not improve quality in their experiments, provides only anecdotal evidence, not a proof. Independent support such as real-world flight tests and strong heuristic results does not repair this gap because the 'exact' claim is a mathematical statement about global optimality. My recommendation therefore keeps the reader's CONDITIONAL verdict: the heuristic and bounding framework may be valuable, but the central exactness claim must either be proven or explicitly downgraded to a high-quality heuristic/bounding method.","tokens_in":119,"tokens_out":2743,"duration_ms":43064,"concrete_test":"Take the smallest instance where BnB runs to completion (e.g., n=4 targets). Enumerate every feasible sequence, and for each sequence solve eq. (48) with a certified global optimizer (e.g., BARON or MAiNGO) using n_sub=10 and also n_sub=20, and compare these globally optimal costs to the IPOPT/n_sub=5 values used inside the BnB. If any C_NLP value used by the BnB exceeds the corresponding global minimum, or if increasing n_sub changes any sequence's feasibility/reward bound, then the BnB can prune the true optimum and the 'exact' claim fails. Repeating on several instances would settle whether the issue actually occurs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The BnB is called exact, but its optimality certificate depends on computing the true minimum travel time in eq. (4) and its relaxations eqs. (22) and (24). The paper itself states in Sec. 5 that 'no exact time-optimal point-mass planner exists' and that the NLP implementations (48)-(51) are solved with IPOPT, a local solver, with the number of control switches empirically capped at n_sub=5. If IPOPT returns a local minimum, then C_NLP(S) and C_NLP_rel(S) overestimate the true minimal travel times. Consequently, the remaining budget in eq. (21) is underestimated, the MILP bound in eq. (36) may understate the reward still reachable, and the BnB in Alg. 4 can prune the globally optimal sequence. Similarly, if a true time-optimal trajectory requires more than five switches (e.g., due to velocity-limit singular arcs), the discrete trajectory model (47) cannot represent it, so even a globally solved NLP over this restricted family is not the exact continuous-time cost. The paper even labels C_NLP as 'locally optimal' in Sec. 5, which directly contradicts the 'exact' label. No argument or certificate is provided to show these local solutions coincide with global minima on the instances tested.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Dynamical Vehicle Orienteering Problem (DVOP), a generalization of the Orienteering Problem in which travel costs are minimum-time trajectories of a three-dimensional point-mass model with velocity and acceleration magnitude constraints under gravity. The authors propose two solvers: an LNS metaheuristic that optimizes target order and entry velocities via limited-thrust-decomposition trajectory planning, and a Branch-and-Bound (BnB) procedure that combines NLP trajectory optimization with a MILP relaxation based on trajectory primitives through target triplets. The BnB is claimed to be exact, returning the globally optimal DVOP target sequence. The paper reports KOP benchmark improvements up to 37% over prior work, evaluates the LNS/BnB gap on randomized 3D instances, and validates the planned trajectories on a real multirotor UAV.","tokens_in":22920,"tokens_out":8675,"duration_ms":121503,"significance":"The DVOP is a natural and useful extension of the KOP/OP family, and the proposed two-level solution architecture is sensible. If the exactness of the BnB could be certified, the paper would be a substantial methodological contribution to the orienteering/VRP literature, since it couples combinatorial selection with continuous time-optimal control. The heuristic LNS with LTD-based insertion and refinement appears credible and is supported by reproducible experiments, a public code repository, and real-flight validation. The MILP primitive-based bounding idea is novel, but its validity as a rigorous reward upper bound is not established. The reported KOP improvements and the real-world tracking demonstration are valuable independent of the exactness claim.","major_comments":[{"comment":"The central claim 'We propose an exact Branch-and-Bound (BnB) procedure' is not supported. The optimality certificate depends on solving eq. (4) and its relaxations (22), (24) exactly, but Sec. 5.4 states that C_NLP is 'locally optimal', is solved with IPOPT, and that n_sub is set to 5 empirically because 'increasing the switches beyond 5 did not improve quality'. If IPOPT returns a local minimum, or if the true time-optimal trajectory needs more than five input switches per pair, then C_NLP(S) and C_NLP_rel(S) overestimate the true minimal travel times. Eq. (21) then underestimates the remaining budget, and the MILP constraint (37) can exclude rewards still reachable, so Alg. 4 can prune the globally optimal sequence. Consequently, the LNS-BnB gaps in Table 3 are not certified distances to the true optimum. This needs either a global-optimality certificate for the NLPs on the tested ins","section":"Sec. 5.2, Alg. 4 and Sec. 5.4, eqs. (48)-(51)"},{"comment":"The assertion that the averaged primitive cost C_hat(X) is a valid lower bound on C_hat_rel is not proved. The text says the cost is valid 'as the travel cost incurred for each consecutive pair of targets in S_hat is bounded by an average value of two elements of C, which themselves are lower-bounds on time-optimal travel costs.' Averaging lower bounds does not in general produce a lower bound on the quantity being relaxed; the 1/2 factor and the overlapping triplet primitives require a formal inequality proof. If C_hat(X) ever exceeds the true C_hat_rel(S_hat), the reward upper bound in eqs. (36)-(37) is invalid and the BnB can prune the optimum even when the trajectory NLPs are solved exactly. Please provide a rigorous derivation or a concrete counterexample.","section":"Sec. 5.3, eq. (35)"},{"comment":"Even if the NLPs were solved to global optimality, the discrete model (47) with at most n_sub input-switching steps per target pair is a restricted trajectory family. The paper itself notes that the velocity bound (2a) can produce singular arcs requiring infinitely many input switches, yet n_sub=5 is chosen empirically. No theorem is given showing that five switches per pair is sufficient for the full 3D model with magnitude constraints and target sequences. Therefore the computed C_NLP and its relaxations are not necessarily the exact continuous-time costs C(S) of eq. (4). The exactness claim requires a representation theorem for the trajectory model, not an empirical cap.","section":"Sec. 5.4, eq. (47)"}],"minor_comments":[{"comment":"The conclusion states a '3D RMS tracking error below 0.5 m' during agile flight at 21 m/s, but Table 5 reports RMSE = 0.671 m at that speed. The number or the wording should be corrected.","section":"Sec. 7 vs Sec. 6.5, Table 5"},{"comment":"The paper calls the BnB 'exact' in the introduction while Sec. 5 says C_NLP is 'locally optimal' and that 'no exact time-optimal point-mass planner exists'. This terminological contradiction should be resolved.","section":"Sec. 1 and Sec. 5"},{"comment":"The indexing in eq. (35) is difficult to follow: the ranges of j and k, the meaning of x_{i,j,k}, and the factor 1/2 deserve a clearer derivation or a small worked example.","section":"Sec. 5.3, eq. (35)"},{"comment":"Many rows at high Tmax report reward equal to the total available reward (15.00) with PDB=0.0, indicating instance saturation. This should be stated explicitly when discussing the PDB trend.","section":"Sec. 6.2, Table 3"}],"recommendation":"major_revision","confidential_remarks":"The exactness claim is load-bearing for the paper's positioning, and the current manuscript does not support it: the local NLP solver, the empirical n_sub cap, and the unproved MILP lower-bound property all undermine the BnB's optimality certificate. However, the heuristic contribution, the KOP benchmark improvements, and the real-flight validation are credible and useful. I would not reject; a major revision that either supplies the missing global-optimality arguments or honestly repositions the BnB as a high-quality heuristic would be appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth your time for two reasons: it cleanly formulates a second-order, gravity-explicit generalization of the orienteering problem (DVOP) for multi-rotors, and it ships a fast local-search heuristic that clearly improves on KOP results and flies on a real UAV. The MILP bound built on time-optimal triplet primitives is genuinely new, and the experimental results suggest it is reasonably tight. Credit where due: the problem definition is clear, the LNS is well-engineered, and the real-world validation is a nice touch.\n\nThe soft spot is the repeated claim that the Branch-and-Bound is exact. Sec. 5 itself says no exact time-optimal point-mass planner exists and that the NLPs are solved with IPOPT, a local solver, with the number of switches capped at n_sub=5 because more did not help in their instances. That means C_NLP and its relaxations can overestimate true minimal travel times, the residual budget in eq. (21) can be underestimated, and the MILP upper bound in eq. (36) can understate the reward still reachable. The BnB can then prune the optimal sequence. The paper even labels C_NLP \"locally optimal\" in Sec. 5, which contradicts the exactness label. Unless the authors can prove global optimality of the NLP solves or restrict to a class where the bang-zero-bang structure with five switches is provably sufficient, the exactness claim is unsupported. This is not a minor technicality; it is the load-bearing wall for the BnB. The heuristic and bounding framework would still stand as a high-quality practical solver, but not as an exact one.\n\nMinor points: benchmark tables report averages without variance across runs, and the code repository is given without a commit hash, so reproducibility is harder to verify. Both are easy to fix.\n\nWho is this for? Anyone working on UAV routing, orienteering variants, or time-optimal trajectory planning. The paper deserves a serious referee: the problem formulation and heuristic are strong enough that the exactness issue should be confronted in review, not dismissed. I would send it to peer review, with the clear expectation that the authors either reframe the BnB as a heuristic/bounding framework or prove the global-optimality requirements.","headline":"A solid new problem formulation and heuristic with a clever MILP bound, but the 'exact BnB' label doesn't survive contact with IPOPT's local solutions and the n_sub=5 cap.","tokens_in":23419,"tokens_out":1882,"would_cite":true,"duration_ms":17794,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A new drone-routing problem that respects acceleration and gravity can be solved exactly by branch-and-bound, with a fast heuristic that stays within 18% of optimal and beats prior methods by up to 37%.","keywords":["Dynamical Vehicle Orienteering Problem","Orienteering Problem","Point-Mass Model","Branch-and-Bound","Mixed-Integer Linear Programming","Large Neighborhood Search","Multi-rotor UAV planning","Time-optimal trajectory"],"falsifier":"Take any DVOP instance and compare the primitive costs $C_{NLP}(q_A,q_B,q_C)$ from eq. (51) against a certified global solution—for example, a dense grid over switch times and axis-wise bang-bang structures, or a rigorous global NLP solver. If even one primitive cost exceeds the certified global minimum, the BnB's upper bound is invalid for that instance. A simpler empirical test: run the authors' implementation with the number of switches raised to 6, 8, and 10, and check whether any best-known solution's reward increases; if it does, the fixed cap of five switches was cutting off time-optimal traje","tokens_in":22412,"feed_emoji":"🚁","tokens_out":6226,"duration_ms":65677,"temperature":0.7,"texified_at":"2026-08-05T21:21:38.103611+00:00","pith_summary":"The paper introduces the Dynamical Vehicle Orienteering Problem (DVOP), in which a multi-rotor drone must visit targets to collect rewards within a flight-time budget while obeying point-mass dynamics with velocity, acceleration, and gravity constraints. The authors aim to solve this problem exactly, and they claim a branch-and-bound procedure that combines nonlinear trajectory optimisation with a novel mixed-integer linear relaxation can return the globally optimal visit sequence. They also present a large-neighbourhood-search heuristic that produces near-optimal solutions in seconds and, on benchmark instances, improves over existing Kinematic Orienteering Problem methods by up to 37%. A sympathetic reader should care because the DVOP removes the velocity-sampling and under-actuation simplifications of prior work, and the exact solver, if correct, provides a reference against which future planning methods can be measured.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":2941,"prompt_tokens":827,"completion_tokens":2114,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":827,"completion_tokens_details":{"reasoning_tokens":1386}},"feed_headline":"Exact solver finds optimal drone routes under real dynamics","feed_subtitle":"Branch-and-bound plus a heuristic within 18% of optimal, verified in real flight.","key_machinery":"The load-bearing mechanism is the MILP relaxation of the vehicle dynamics, built from time-optimal trajectory primitives through target triplets (eq. 32). A primitive is the minimum flight time from one target to another while passing through a third, computed offline by solving a small NLP; these precomputed costs become coefficients of binary decision variables in the MILP. Because three targets are the minimum that forces a velocity change, triplet primitives encode the acceleration constraint (2b) that a graph with pairwise distances would miss. The MILP cost function $\\hat{C}(X)$ is a valid lower bound on the true relaxed travel cost—each consecutive-target edge cost is taken as an averag","core_discovery":"The central claim is that the DVOP—maximise reward collected by a point-mass quadrotor under velocity, acceleration and gravity constraints within a flight-time budget—can be solved exactly by a branch-and-bound procedure whose upper bounds are computed by a novel MILP relaxation. The relaxation represents travel cost through triples of targets using precomputed time-optimal trajectory primitives, so the acceleration constraint enters the combinatorial model through the primitive costs rather than through edge distances. The paper shows experimentally that the MILP upper bound is tight (mean reward gap under 8% over all valid solution-tree nodes in the evaluated scenarios) and that the BnB c","pith_inferences":["A natural extension would be to replace the local NLP solves with a certified global solver (or a fine grid of switch times) to remove the gap between 'claimed exact' and 'numerically global'—the authors do not prove the NLP subproblems reach the true global minimum.","The LNS's removal of velocity sampling suggests a cheap improvement for other Dubins-style orienteering solvers: maintain continuous heading/speed optimisation at targets instead of discretising them.","The gap between LNS and BnB (up to 17.3%) could be closed online by using the MILP bound as a certificate: run LNS, compute the bound for its sequence, and only degrade to speculation when the bound is loose.","The triplet-primitive idea might scale to higher-order dynamics or to multi-vehicle versions, though the precomputation cost grows cubically with the number of targets."],"forward_implications":["If correct, the BnB returns the globally optimal visit sequence on instances it can terminate, giving a reference standard for the DVOP and for the Kinematic Orienteering Problem under magnitude constraints.","The LNS heuristic yields near-optimal solutions within seconds and therefore a practical anytime planner for larger instances, where the exact method requires hours.","The MILP relaxation based on trajectory primitives can be transferred to other second-order vehicle routing settings, replacing pairwise graph costs wherever acceleration matters.","The reported 37% improvement over prior KOP solutions indicates that modelling full thrust and gravity changes which targets a drone can visit, not just the path between them.","The real-world flight tests show the planned point-mass trajectories are trackable within about 0.3 m horizontally, so the improved plans are executable, not just theoretical."],"fun_headline_variants":["Exact drone routing under real flight dynamics","New exact method for drone orienteering under physics","Exact solver beats prior drone routing by up to 37%","Real-flight verified exact drone routing with acceleration caps"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The branch-and-bound's claim to exactness rests on the nonlinear trajectory optimisations (eqs. 48–51) being solved to global optimality, but they are solved with a local NLP solver and the control parameterisation is capped at five input switches; if a true time-optimal trajectory needs more switches or the solver stops at a local minimum, the planned travel times are overestimated, the remaining budget is understated, and the BnB can prune the optimal sequence.","fun_headline_variants_meta":{"raw":{"variants":["Exact drone routing under real flight dynamics","New exact method for drone orienteering under physics","Exact solver beats prior drone routing by up to 37%","Real-flight verified exact drone routing with acceleration caps"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001498,"raw_usage":{"total_tokens":5887,"prompt_tokens":821,"completion_tokens":5066,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":565,"completion_tokens_details":{"reasoning_tokens":5015}},"tokens_in":565,"tokens_out":5066,"duration_ms":36463,"temperature":1.0,"reasoning_tokens":5015,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T03:42:03.155775+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any DVOP instance and compare the primitive costs $C_{NLP}(q_A,q_B,q_C)$ from eq. (51) against a certified global solution—for example, a dense grid over switch times and axis-wise bang-bang structures, or a rigorous global NLP solver. If even one primitive cost exceeds the certified global minimum, the BnB's upper bound is invalid for that instance. A simpler empirical test: run the authors' implementation with the number of switches raised to 6, 8, and 10, and check whether any best-known solution's reward increases; if it does, the fixed cap of five switches was cutting off time-optimal traje","supporting_citations":[],"review_version":1}