{"id":"a91dec0c-f1ee-4041-b82c-be230da8f919","arxiv_id":"1908.08494","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The paper formalizes the Double Traveling Salesman Problem with Partial Last-In-First-Out Loading, proposes two ILP models and a biased random-key genetic algorithm, and evaluates them on 1,080 instances.","lead":"This paper introduces a new truck-routing problem where a single vehicle picks up items in one city and delivers them in another, and may move only a limited number of items on its stack at a cost. The authors give two exact mathematical formulations and a genetic algorithm, and test them on 1,080 benchmark instances.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Constraint (16) omits ℓ=k, so ILP1/ILP2 never charge for rearrangements that move only the current top item; the claimed valid formulations undercount cost.","rationale":"The reader's weakest assumption concerned whether constraints (12), (13), (16), and (17) fully capture the partial LIFO policy and its cost. My stress-test found a concrete indexing bug in constraint (16): the domain ℓ ∈ [1, k−1] excludes the current top slot ℓ = k. Whenever the deepest changed slot between consecutive pickup configurations is the top slot, the constraint cannot fire, so the number of rearranged items is undercounted. This is not a boundary case: it happens whenever a new item is loaded below the current top item, which is exactly the kind of rearrangement the partial LIFO policy is introduced to allow. The paper's own Figure 1 example contains such a move, so the flaw is visible even in the authors' illustration. Because both ILP1 and ILP2 use constraint (16), the claimed formal descriptions of the DTSPPL are not correct as written: the objective can assign zero handling cost to solutions that require positive handling cost. This also undermines the reported optimality results and the comparison between the ILPs and the BRKGA. The issue is localized and easily fixed by extending the domain to ℓ ∈ [1, k]; after that fix, the formulations may be correct, but the experiments and conclusions would need to be re-run. Therefore I recommend keeping a conditional verdict rather than accepting the paper as is, and I partially agree with the reader's identification of the reloading-count constraints as the fragile point.","tokens_in":56,"tokens_out":36223,"duration_ms":475812,"concrete_test":"Run ILP1 on an n = 2, L = 1, h = 1 instance whose true optimum uses pickup route 0→1→2→0 and delivery route 0→2→1→0, so item 2 must be loaded underneath item 1. The true cost includes exactly one rearrangement (item 1 is unloaded and reloaded). Inspect the ILP solution: with constraint (16) as written, z_1^P is forced to 0 and the reported total is distance only, whereas the true total is distance + h. Re-running the same model with the domain corrected to ℓ ∈ [1, k] should yield z_1^P = 1 and the correct total cost.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In both ILP formulations, the rearrangement count in the pickup area is imposed by constraint (16): z_k^P ≥ (y_kP_jℓ − y_{k+1,P}_jℓ)·(k−ℓ+1) for ℓ ∈ [1, k−1]. The upper limit should be ℓ = k. A transition that moves only the current top item changes exactly the slot ℓ = k. For example, after loading item 1 the stack is [1]; to load item 2 underneath, item 1 must be removed and reloaded, giving [2,1]. That is one rearrangement, but with k = 1 the domain is empty, and for general k the term ℓ = k is absent, so z_k^P can remain 0. The same gap occurs in the paper's own illustrative solution in Figure 1: when item 5 is removed, item 4 is inserted, and item 5 is replaced, the deepest changed slot in the old configuration is ℓ = k = 2, which is outside [1, k−1]. The freeze constraints (12) and (13) do not repair this; they only bound where items may move, and they permit this configuration change. Consequently, both ILPs understate the rearrangement cost and can declare solutions optimal that are not optimal for the stated objective. Because the central claim is that these are valid ILP formulations of the DTSPPL, this is a load-bearing correctness flaw.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Double Traveling Salesman Problem with Partial Last-In-First-Out Loading Constraints (DTSPPL), a single-vehicle pickup-and-delivery problem in which all pickup operations occur before deliveries, the container is a single horizontal stack, and at any time at most L top items may be rearranged. The total cost combines travel distance and a cost h per rearranged item. The authors propose two compact ILP formulations, ILP1 and ILP2, which differ in how the routes are modeled (position-indexed arc variables versus standard Miller-Tucker-Zemlin subtour-elimination variables), and a Biased Random-Key Genetic Algorithm (BRKGA) with a three-part chromosome encoding and a deterministic decoder. Computational experiments on 1080 instances derived from DTSPMS benchmark areas show that both ILPs solve only the smallest instances within one hour and that the BRKGA is competitive with the ILPs on some instance classes but clearly worse on others. The paper also provides a public repository with code and detailed results.","tokens_in":26213,"tokens_out":9310,"duration_ms":100374,"significance":"If the formulation issue discussed below is corrected, the paper would be a useful contribution: it names and studies a natural variant of the DTSPMS that has apparently not been treated before, it gives two concrete compact models that can serve as a starting point for exact methods, and it provides a reproducible heuristic with code and results. The motivating trade-off between routing cost and handling cost is clearly explained. The strength of the experimental section is the systematic coverage of n, L, and h combinations and the use of standard DTSPMS benchmark areas. However, the central claim that the ILP formulations exactly describe the DTSPPL is currently undermined by an error in the rearrangement-counting constraints, and the heuristic-quality claim is stronger than the evidence in the paper supports.","major_comments":[{"comment":"Constraint (16) bounds z_k^P only for positions l in [1, k-1], omitting the top position l = k. This omission means that a transition in which only the current top item is displaced is never charged a rearrangement. For example, the transition from configuration [1] to [2,1] requires removing item 1, loading item 2, and replacing item 1, which is exactly one rearrangement, but for k=1 the index range [1,k-1] is empty. For general k the same situation has its deepest changed old-configuration slot at l = k, which is also outside the range. This is not a hypothetical corner case: the paper's own illustrative solution in Figures 1-2 contains this operation when customer 4 is picked up and item 5 is removed, so the text's count of one rearrangement is not enforced by the model. Because z_k^P understates the objective, both ILP1 with objective (19) and ILP2 with objective (28) can certify as optimal solutions that are not optimal for the stated DTSPPL objective, contradicting the assertion in Section 2.2.4 that constraints (1)-(18) represent all feasible solutions. The fix is to extend the range in (16) to l in [1,k]; after doing so the authors should re-examine the analogous delivery constraint (17) and rerun the computational experiments, since the reported optimality results for small instances may change.","section":"Section 2.2.3, constraint (16)"},{"comment":"The abstract and the conclusions state that the BRKGA obtained good quality solutions for almost all instances, but the evidence in Figure 13 does not support this for deeper reloading depths. For L = 4, L = 5, and L = n with small h, many cells show the BRKGA average be substantially worse than the ILP upper bound, with the text reporting differences that can exceed 50 percent. Since the ILP upper bound is not an optimality certificate for instances with n >= 10, the comparison establishes relative performance against the ILPs rather than solution quality in an absolute sense. The claim would be calibrated by reporting BRKGA gaps against the best lower bounds max(ILP1_LB, ILP2_LB), by comparing with the no-rearrangement baseline used in Figure 15, or by testing against known optimal solutions for the small instances. As written, the conclusion that the BRKGA found good quality solutions for all instances is an overstatement of the reported data.","section":"Section 4.4 and Figure 13"}],"minor_comments":[{"comment":"Figure 14 contains unrelated chart text reading 'Temperature (°C) Monthly Average Temperature Source: WorldClimate.com', which appears to be a chart-generation artifact that should be removed.","section":"Figure 14"},{"comment":"The I/F-Race tuning uses a 10 percent sample of the same 1080 instances that are later used in the final evaluation; the paper should state explicitly that the reported BRKGA results are tuned rather than out-of-sample, or use a separate test set.","section":"Section 4.2"},{"comment":"The right-hand sides of constraints (26) and (27) appear to contain fractions, but the rendering is ambiguous; explicit parentheses and display formatting would make the intended expressions clear.","section":"Equations (26)-(27)"},{"comment":"The text describing constraints (16) and (17) would be clearer if it stated explicitly that each constraint gives a lower bound on z_k^r and that minimization forces z_k^r to equal the largest positive such bound rather than merely being bounded below.","section":"Section 2.2.3"},{"comment":"The attribution of the DTSPMSPL idea to Petersen's thesis would benefit from a more specific citation, since the reloading-depth definition is load-bearing for the whole paper; a page or section reference would help the reader verify the modeling choice.","section":"Section 1"}],"recommendation":"major_revision","confidential_remarks":"The omission of l = k in constraint (16) is a genuine correctness flaw in the central contribution, but it is localized and fixable; I do not see a reason to reject the paper outright. The computational results will need to be regenerated after the fix, because the optimality claims for small instances and the ILP/BRKGA comparisons may change. I would also suggest the editors ask the authors to substantiate or soften the heuristic-quality claims, since the current text overstates what Figure 13 shows."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the DTSPPL is a real new variant, and the paper is worth a serious look, but the two ILP formulations have a load-bearing bug. Constraints (16) and (17) range over ℓ∈[1,k−1] and ℓ∈[1,n−k], which omits the top position (ℓ=k in pickup, ℓ=n−k in delivery). Any transition that rearranges only the current top item therefore gets a z value of zero. Example: after loading item 1, to load item 2 underneath you remove item 1 and replace it—one rearrangement—but for k=1 the domain is empty, so z_1^P stays 0. The same thing happens in your own Figure 1 example: at the third pickup, item 5 is removed and replaced, deepest changed slot is ℓ=k=2, outside [1,k−1], so that rearrangement is not counted. The freeze constraints (12)/(13) do not repair this; they only allow the move, not charge for it. So both models understate rearrangement cost and can declare solutions optimal that are not optimal for the stated objective. This is not a minor indexing nit; the validity claim for the formulations is the core of the paper.\n\nWhat is good: the problem itself is new and well motivated—single stack, bounded reloading depth, per-rearrangement cost—and the distinction from DTSPMS/PDTSPH is clear. The BRKGA decoding is coherent, and the benchmark with code and instances is a real service. The computational study is extensive, though not cleanly reported.\n\nOther soft spots: the tuned BRKGA parameters are not actually given in the text (the bold in Table 1 doesn't survive), results are averages without variance, and the text has figure artifacts (Figure 14 contains a temperature chart) and cross-reference errors. These are secondary and fixable.\n\nBottom line: the problem is interesting enough that the paper deserves a serious referee, but as written the ILP claims don't hold. The fix is simple—extend the ℓ range to include the top position—and then the experiments should be rerun, since the 'optimal' small-instance values are likely understated. Who gets value: anyone working on routing with reloading constraints; the variant is worth having even if this version needs major revision.","headline":"The DTSPPL is a genuinely new and well-motivated routing variant, but both ILP formulations undercount rearrangement costs by omitting the top stack position, so the claimed 'valid' formulations and the resulting optimal values do not match the stated problem.","tokens_in":26780,"tokens_out":6689,"would_cite":false,"duration_ms":62390,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C35","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces the Double Traveling Salesman Problem with Partial Last-In-First-Out loading constraints and provides two ILP formulations plus a biased random-key genetic algorithm that finds high-quality solutions on almost all…","keywords":["double traveling salesman problem","partial LIFO loading","pickup and delivery","integer linear programming","biased random-key genetic algorithm","reloading depth","single stack container","routing with loading constraints"],"falsifier":"For an instance with three items and L=1, the models require the bottom-position item to stay frozen in constraints (12)-(13); observing a feasible real-world handling process in which that bottom item is removed and replaced without touching the item above it would directly contradict the models. A computational check on the same instance class, comparing the ILP optimum against exhaustive enumeration of all valid reloading sequences, would settle whether the depth-based cost formula counts rearrangements correctly.","tokens_in":25709,"feed_emoji":"🚚","tokens_out":5016,"duration_ms":45660,"temperature":0.7,"pith_summary":"The paper introduces the Double Traveling Salesman Problem with Partial LIFO Loading Constraints (DTSPPL), a single-vehicle pickup-and-delivery problem in which all pickups happen before all deliveries and the container is one horizontal stack. Its defining feature is a reloading depth L: at any moment, only the top L items may be taken out and put back in a different order, while deeper items must stay put. The paper's central claim is that this partial-LIFO relaxation can be captured exactly by two compact integer linear programming formulations, and that a biased random-key genetic algorithm can find high-quality solutions in short time on a broad benchmark set. The computational results show the exact models solve only smaller instances within an hour, while the heuristic performs well on almost all instances and is especially strong when the reloading depth is small. The practical interest is the trade-off the problem quantifies: paying a handling cost per reshuffled item versus saving travel distance.","feed_headline":"Reshuffling the top L items can shorten pickup-delivery routes","feed_subtitle":"Two exact ILP models and a genetic heuristic show when paying to re-stack cargo beats strict LIFO ordering.","key_machinery":"The central object is the reloading-depth mechanism: in a single horizontal stack of n items, positions 1 through L from the top can be permuted freely between two consecutive loading or unloading operations, but every item in a deeper position must stay exactly where it is. The paper encodes this with constraints (12) and (13), which equate the occupant of each frozen position across adjacent container configurations, and constraints (16) and (17), which define the rearrangement count as the depth of the deepest position whose occupant changes. This depth-based counting is what makes the objective function combine travel distance and handling cost in a single linear expression. The heuristic's corresponding machinery is a random-key chromosome whose three partitions encode the pickup route, the loading plan, and the combined unloading plan and delivery route; decoding the keys into sorted item orders produces feasible loading plans without any repair mechanism.","core_discovery":"On its own terms, the paper's discovery is that a routing problem with partial LIFO reloading can be stated as an ILP in two different compact ways, and that a random-key genetic algorithm is a workable way to solve the larger cases. The first ILP indexes every arc by its position in the tour; the second uses standard MTZ-style subtour elimination constraints. Both share the same loading-plan variables, which record, for each container configuration during pickups and during deliveries, which item occupies which stack position. The partial LIFO policy is imposed by constraints that freeze every position below the top L, while the number of rearrangements is counted through constraints that charge for the deepest position whose occupant changes between consecutive configurations. The paper reports that these formulations prove optimality for all tested 6-customer instances and almost all 8-customer instances, while larger instances remain open; the BRKGA outperforms the exact methods on most instances with reloading depth up to 3, and the exact models do better when L is large and rearrangement is cheap.","pith_inferences":["If the depth-based rearrangement count faithfully models real handling costs, the same counting principle could transfer to multi-stack containers, giving a DTSPMSPL formulation in which each stack has its own reloading depth.","A testable extension is a local-search heuristic that swaps the order of the top L items at a single pickup or delivery visit, since the decoding already reduces route construction to sorting small blocks and might reach similar quality with far less memory.","The benchmark instances are all Euclidean and symmetric, so the paper's conclusions about when rearrangement pays might shift on asymmetric or clustered networks, where the delivery route cannot simply mirror the pickup route."],"forward_implications":["If the models are right, then DTSPPL is a well-defined optimization problem whose optimal cost can be approached by two compact ILP models, giving future exact methods a clear benchmark.","The reported experiments show that even a small reloading depth yields measurable improvements over the strict-LIFO baseline, such as roughly 10 percent cost improvement for L=2, n=8, and h=5, so the handling-versus-routing trade-off is worth modeling in practice.","The BRKGA's decoding of the delivery route from the unloading plan means that a single feasible loading and unloading plan determines the delivery tour, a structural simplification that helps heuristics navigate the feasible space.","The observation that exact models solve only small instances quickly, while the heuristic handles almost all instances, suggests that a hybrid exact-heuristic pipeline with an initial incumbent plus branch-and-bound is a natural next step."],"supporting_citations":[{"why":"Introduces the DTSPMS, the multiple-stack predecessor of this problem, and supplies the benchmark areas R05-R09 used in the experiments.","marker":"[Petersen and Madsen, 2009]"},{"why":"Proposes the partial-LIFO idea and the reloading-depth motivation in a thesis, which this paper names DTSPMSPL and then specializes to a single stack as DTSPPL.","marker":"[Petersen, 2009]"},{"why":"Provides the strategy of building an initial no-rearrangement solution by solving a TSP with combined pickup and delivery arc costs, used to seed the ILPs and the BRKGA.","marker":"[Felipe et al., 2009]"},{"why":"Supplies the biased random-key genetic algorithm framework that the decoding and evolutionary operators are based on.","marker":"[Gonçalves and Resende, 2011]"},{"why":"Provides the C++ API implementation used to code the BRKGA.","marker":"[Toso and Resende, 2015]"},{"why":"Shows the branch-and-cut approach and precedence-graph property for DTSPMS that the paper cites to explain why those techniques do not carry over when rearrangements are allowed.","marker":"[Alba Martínez et al., 2013]"},{"why":"Is the earlier single-vehicle problem with full reshuffling that motivates the handling-cost trade-off studied here.","marker":"[Ladany and Mehrez, 1984]"},{"why":"Is the pickup-and-delivery TSP with handling costs whose reloading policies are compared with the partial-LIFO setting.","marker":"[Veenstra et al., 2017]"}],"fun_headline_variants":["Partial LIFO reloading can cut pickup-delivery route cost","Two ILP models and a BRKGA for the partial-LIFO double TSP","Genetic algorithm excels on larger partial-LIFO routing instances","Optimal restacking depth: balancing route length and reloads","New double TSP variant allows limited LIFO violations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the partial LIFO operating rule is completely described by 'only the top L items may move, and every movement is charged once according to the deepest changed position'; if a real handling process allows moving an item below the top L without first removing the items above it, or charges rearrangements differently, then both ILP models describe a different problem.","fun_headline_variants_meta":{"raw":{"variants":["Partial LIFO reloading can cut pickup-delivery route cost","Two ILP models and a BRKGA for the partial-LIFO double TSP","Genetic algorithm excels on larger partial-LIFO routing instances","Optimal restacking depth: balancing route length and reloads","New double TSP variant allows limited LIFO violations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000792,"raw_usage":{"total_tokens":3527,"prompt_tokens":1017,"completion_tokens":2510,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":2419}},"tokens_in":633,"tokens_out":2510,"duration_ms":19770,"temperature":1.0,"reasoning_tokens":2419,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:39:10.208785+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For an instance with three items and L=1, the models require the bottom-position item to stay frozen in constraints (12)-(13); observing a feasible real-world handling process in which that bottom item is removed and replaced without touching the item above it would directly contradict the models. A computational check on the same instance class, comparing the ILP optimum against exhaustive enumeration of all valid reloading sequences, would settle whether the depth-based cost formula counts rearrangements correctly.","supporting_citations":[],"review_version":1}