Pith. sign in

REVIEW 3 major objections 4 minor 40 references

Enhancements of Fragment Based Algorithms for Vehicle Routing Problems

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict Genuinely new fragment-enhancement ideas with strong PDPTW results; the TDDRP superiority claim rests on generated stand-in instances and is not proven. read the letter →

arxiv 2411.13151 v1 pith:LZF5HNBH submitted 2024-11-20 math.OC

Lucas Sippel , Michael Forbes This is my paper · ORCID
classification math.OC MSC 90B0690C2790C11
keywords vehicleroutingproblempickupanddeliverywithtimewindowsfragmentformulationresourceexpandednetworkdynamicdiscretizationdiscoveryleveragingcolumnenumerationforroweliminationtruck-baseddrone
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 5.4, Table 4] 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.
  2. [Section 6 and Section 1.4] 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.
  3. [Section 5.4, Table 5] 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.
minor comments (4)
  1. [Section 5.1] 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}}.
  2. [Abstract and Section 1.4] 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.
  3. [Section 3.1.7] 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.
  4. [Supplement, Section 1.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: FL uses route-formulation dual bounds as legitimate filtering inputs, DDD and CERE preserve exactness by construction, and the TDDRP benchmark caveat is a validity concern rather than a circular argument.

full rationale

The paper's central claims are empirical and algorithmic, not derivations whose conclusions are contained in their premises. In Section 3.3, formulation leveraging computes reduced-cost lower bounds for fragments from optimal dual values of the route-formulation master problem (Theorems 3 and 4); this is standard LP-duality-based variable fixing applied to a new object type, not a fitted input renamed as a prediction. In Section 3.2, DDD adds resourced nodes only to eliminate underestimating chains and terminates only when all chains correspond to feasible routes, so optimality is not assumed by the network construction. In Section 3.4, CERE concatenates fragments while preserving the invariant that every route still has a representation, and its MaxIncrease parameter is an algorithmic control, not a parameter fit to the reported outcomes. The paper builds on the authors' earlier fragment work (Alyasiry et al. 2019; Rist and Forbes 2021, 2022), but those citations provide baseline algorithms and fragment definitions; they are not invoked as an unverified authority to exclude alternatives, so they are not load-bearing circularity. The notable weakness is Section 5.4, where Yin et al.'s TDDRP instances are unavailable and the paper compares its method on instances 'generated according to their description' against BPC times reported on the original instances, conceding that this is 'not ideal'. That is a benchmarking-validity and fair-comparison limitation, not circularity: no claimed quantity is defined in terms of the compared BPC results. I found no equation or construction by which a claimed result reduces to its own input.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard LP duality, fragment rule completeness, DDD property preservation, drone-flight enumerability, and the representativeness of generated TDDRP instances. The main free parameters are algorithmic hyperparameters (MaxIncrease, time discretization, gap slack, initial node spacing, cut rounds) that are tuned per instance set and could affect the reported performance.

free parameters (5)
  • MaxIncrease (CERE aggressiveness) = 500 (phase 1) and 6000 (phase 2) for PDPTW; 500/infinity for TDDRP; 2500 for hard TDDRP instances
    Controls how many fragments are merged at each node during CERE. Larger values strengthen the relaxation but increase the number of variables. Tuned per instance set without a sensitivity analysis.
  • Time discretization delta for static networks = 5 time units
    When DDD is not used, resourced copies of nodes are placed every 5 time units. Finer deltas strengthen the relaxation but enlarge the network. Chosen by hand.
  • Optimality gap slack psi for upper bound guess = 20 if heuristic solution has target vehicle count, else 30
    Used to set z_c^ub = min(z_heuristic, z_c^lb + psi). This slack affects how aggressively FL filters fragments. Chosen ad hoc.
  • Initial resourced node spacing for TDDRP = 10*delta with delta in {d_i/10, (d_i+10)/10, ..., (Q_truck-10)/10, Q_truck/10}
    Initializes the resource-expanded network in the TDDRP. The spacing choice affects early DDD behaviour and is set manually.
  • Cut separation rounds for hard TDDRP instances = 0, 1, or 2, chosen per instance as the fastest solve
    The number of lm-R1C separation rounds in step 2 is tuned per instance. More rounds increase CG time but may reduce optimality gap. The paper reports the fastest choice.
assumptions (5)
  • domain assumption Every route has at least one representation as a chain of fragments satisfying the fragment rules (Definition 2 and Theorem 1).
    The fragment rules are designed so that any route can be partitioned into fragments. This is the foundation of the fragment formulation, stated without a proof of rule completeness.
  • domain assumption The early arrival property and longest arc property can be maintained while adding resourced nodes in DDD.
    Properties 1-5 in Section 3.1.5 guarantee that the network is a relaxation of the VRP. The DDD updates must preserve these properties; the paper asserts this but does not prove termination or that all underestimating chains are eliminated in finite steps.
  • standard math LP duality and reduced-cost variable fixing (Theorem 2) justify fragment filtering via the route-formulation bound.
    A standard result from integer programming. The paper provides a proof in the supplement, and this is the backbone of formulation leveraging.
  • domain assumption For the TDDRP, drone flights can be fully enumerated because battery capacity and drone capacity are small (Section 5.1).
    The algorithm's tractability relies on the number of feasible drone flights being manageable. This holds on the generated instances but is not guaranteed for all TDDRP settings.
  • domain assumption The generated TDDRP instances are representative of Yin et al.'s benchmark difficulty.
    Because the original instances are not public, the authors generate instances 'according to their description'. Comparability of solve times across different instances is assumed, which weakens the performance comparison.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Enhancements of Fragment Based Algorithms for Vehicle Routing Problems." pith.science (2026). https://pith.science/paper/LZF5HNBH

@misc{pith2026241113151,
  author       = {Pith},
  title        = {Pith review of: Enhancements of Fragment Based Algorithms for Vehicle Routing Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LZF5HNBH}},
  note         = {Machine review of arXiv:2411.13151}
}
read the original abstract

The method of fragments was recently proposed, and its effectiveness has been empirically shown for three specialised pickup and delivery problems. We propose an enhanced fragment algorithm that for the first time, effectively solves the Pickup and Delivery Problem with Time Windows. Additionally, we describe the approach in general terms to exemplify its theoretical applicability to vehicle routing problems without pickup and delivery requirements. We then apply it to the Truck-Based Drone Delivery Routing Problem Problem with Time Windows. The algorithm uses a fragment formulation rather than a route one. The definition of a fragment is problem specific, but generally, they can be thought of as enumerable segments of routes with a particular structure. A resource expanded network is constructed from the fragments and is iteratively updated via dynamic discretization discovery. Additionally, we introduce two new concepts called formulation leveraging and column enumeration for row elimination that are crucial for solving difficult problems. These use the strong linear relaxation of the route formulation to strengthen the fragment formulation. We test our algorithm on instances of the Pickup and Delivery Problem with Time Windows and the Truck-Based Drone Delivery Routing Problem with Time Windows. Our approach is competitive with, or outperforms the state-of-the-art algorithm for both.

Figures

Figures reproduced from arXiv: 2411.13151 by the authors.

Figure 1
Figure 1. Two RFN solutions for the small PDPTW instance. [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. Number of timed nodes and fragments in the final network across the PDPTW instances. [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
Figure 3
Figure 3. Number of instances solved to optimality within a given amount of time. [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 22 canonical work pages

  1. [1]

    Transportation science 53(6):1695--1705, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.2019.0905

    Alyasiry AM, Forbes M, Bulmer M (2019) An exact algorithm for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation science 53(6):1695--1705, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.2019.0905

    work page arXiv 2019

  2. [2]

    Operations research 59(2):414--426, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.1100.0881

    Baldacci R, Bartolini E, Mingozzi A (2011 a ) An exact algorithm for the pickup and delivery problem with time windows. Operations research 59(2):414--426, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.1100.0881

    work page arXiv 2011

  3. [3]

    Operations research 59(5):1269--1283, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.1110.0975

    Baldacci R, Mingozzi A, Roberti R (2011 b ) New route relaxation and pricing strategies for the vehicle routing problem. Operations research 59(5):1269--1283, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.1110.0975

    arXiv 2011

  4. [4]

    Operations research 12(2):300--304, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.12.2.300

    Balinski ML, Quandt RE (1964) On an integer program for a delivery problem. Operations research 12(2):300--304, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.12.2.300

    work page doi:10.1287/opre.12.2.300 1964

  5. [5]

    Operations research 46(3):316--329, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.46.3.316

    Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Operations research 46(3):316--329, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.46.3.316

    doi:10.1287/opre.46.3.316 1998

  6. [6]

    Operations research 65(5):1303--1321, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.2017.1624

    Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Operations research 65(5):1303--1321, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.2017.1624

    arXiv 2017

  7. [7]

    Computers and industrial engineering 99:300--313, ISSN 0360-8352, ://dx.doi.org/10.1016/j.cie.2015.12.007

    Braekers K, Ramaekers K, Van Nieuwenhuyse I (2016) The vehicle routing problem: State of the art classification and review. Computers and industrial engineering 99:300--313, ISSN 0360-8352, ://dx.doi.org/10.1016/j.cie.2015.12.007

    doi:10.1016/j.cie.2015.12.007 2016

  8. [8]

    Networks 11(2):145--164, ISSN 0028-3045, ://dx.doi.org/10.1002/net.3230110207

    Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145--164, ISSN 0028-3045, ://dx.doi.org/10.1002/net.3230110207

    work page doi:10.1002/net.3230110207 1981

Show all 40 references
  1. [9]

    Transportation science 53(4):946--985, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.2018.0878

    Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation science 53(4):946--985, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.2018.0878

    2019

  2. [10]

    Management science 6(1):80--91, ISSN 0025-1909, ://dx.doi.org/10.1287/mnsc.6.1.80

    Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management science 6(1):80--91, ISSN 0025-1909, ://dx.doi.org/10.1287/mnsc.6.1.80

    1959 doi

  3. [11]

    Operations research 8(1):101--111, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.8.1.101

    Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Operations research 8(1):101--111, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.8.1.101

    1960 doi

  4. [12]

    ://hdl.handle.net/1765/123411

    Dollevoet T, Munari P, Spliet R (2020) A p-step formulation for the capacitated vehicle routing problem. ://hdl.handle.net/1765/123411

    2020

  5. [13]

    Computers and industrial engineering 57(4):1472--1483, ISSN 0360-8352, ://dx.doi.org/10.1016/j.cie.2009.05.009

    Eksioglu B, Vural AV, Reisman A (2009) The vehicle routing problem: A taxonomic review. Computers and industrial engineering 57(4):1472--1483, ISSN 0360-8352, ://dx.doi.org/10.1016/j.cie.2009.05.009

    2009 doi

  6. [14]

    4OR 8(4):407--424, ISSN 1619-4500, ://dx.doi.org/10.1007/s10288-010-0130-z

    Feillet D (2010) A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR 8(4):407--424, ISSN 1619-4500, ://dx.doi.org/10.1007/s10288-010-0130-z

    2010 doi

  7. [15]

    Networks 44(3):216--229, ISSN 0028-3045, ://dx.doi.org/10.1002/net.20033

    Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44(3):216--229, ISSN 0028-3045, ://dx.doi.org/10.1002/net.20033

    2004 doi

  8. [16]

    Mathematical programming 106(3):491--511, ISSN 0025-5610 1436-4646, ://dx.doi.org/10.1007/s10107-005-0644-x

    Fukasawa R, Longo H, Lysgaard J, De Aragão MP, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical programming 106(3):491--511, ISSN 0025-5610 1436-4646, ://dx.doi.org/10.1007/s10107-005-0644-x

    2006 doi

  9. [17]

    OR Spectrum 30(1):113--148, ISSN 0171-6468, ://dx.doi.org/10.1007/s00291-007-0083-6

    Irnich S (2008) Resource extension functions: properties, inversion, and generalization to segments. OR Spectrum 30(1):113--148, ISSN 0171-6468, ://dx.doi.org/10.1007/s00291-007-0083-6

    2008 doi

  10. [18]

    Irnich S, Desaulniers G (2005) Column Generation, 33--65 (Boston, MA: Springer US), ISBN 03872548549780387254852, ://dx.doi.org/10.1007/0-387-25486-2\_2

    2005 doi

  11. [19]

    INFORMS journal on computing 22(2):297--313, ISSN 1091-9856, ://dx.doi.org/10.1287/ijoc.1090.0341

    Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS journal on computing 22(2):297--313, ISSN 1091-9856, ://dx.doi.org/10.1287/ijoc.1090.0341

    2010

  12. [20]

    MOS-SIAM Series on Optimization (Society for Industrial and Applied Mathematics), 2nd edition, ISBN 9781611973587, ://dx.doi.org/10.1137/1.9781611973594.ch1

    Irnich S, Toth P, Vigo D (2014) The Family of Vehicle Routing Problems, chapter 1, 1--33. MOS-SIAM Series on Optimization (Society for Industrial and Applied Mathematics), 2nd edition, ISBN 9781611973587, ://dx.doi.org/10.1137/1.9781611973594.ch1

    2014 doi

  13. [21]

    Operations research 56(2):497--511, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.1070.0449

    Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Operations research 56(2):497--511, ISSN 0030-364X, ://dx.doi.org/10.1287/opre.1070.0449

    2008

  14. [22]

    International journal on artificial intelligence tools 12(2):173--186, ISSN 0218-2130, ://dx.doi.org/10.1142/S0218213003001186

    Li H, Lim A (2003) A metaheuristic for the pickup and delivery problem with time windows. International journal on artificial intelligence tools 12(2):173--186, ISSN 0218-2130, ://dx.doi.org/10.1142/S0218213003001186

    2003 doi

  15. [23]

    European journal of operational research 162(1):122--125, ISSN 0377-2217 1872-6860, ://dx.doi.org/10.1016/j.ejor.2003.05.006

    Lubbecke ME (2005) Dual variable based fathoming in dynamic programs for column generation. European journal of operational research 162(1):122--125, ISSN 0377-2217 1872-6860, ://dx.doi.org/10.1016/j.ejor.2003.05.006

    2005 doi

  16. [24]

    Operations research letters 45(3):206--209, ISSN 0167-6377, ://dx.doi.org/10.1016/j.orl.2017.02.006

    Pecin D, Pessoa A, Poggi M, Uchoa E, Santos H (2017) Limited memory rank-1 cuts for vehicle routing problems. Operations research letters 45(3):206--209, ISSN 0167-6377, ://dx.doi.org/10.1016/j.orl.2017.02.006

    2017 doi

  17. [25]

    INFORMS journal on computing 30(2):339--360, ISSN 1091-9856, ://dx.doi.org/10.1287/ijoc.2017.0784

    Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS journal on computing 30(2):339--360, ISSN 1091-9856, ://dx.doi.org/10.1287/ijoc.2017.0784

    2018

  18. [27]

    Discrete optimization 3(3):255--273, ISSN 1572-5286, ://dx.doi.org/10.1016/j.disopt.2006.05.007

    Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete optimization 3(3):255--273, ISSN 1572-5286, ://dx.doi.org/10.1016/j.disopt.2006.05.007

    2006 doi

  19. [28]

    Computers & operations research 140:105649, ISSN 0305-0548, ://dx.doi.org/10.1016/j.cor.2021.105649

    Rist Y, Forbes M (2022) A column generation and combinatorial benders decomposition algorithm for the selective dial-a-ride-problem. Computers & operations research 140:105649, ISSN 0305-0548, ://dx.doi.org/10.1016/j.cor.2021.105649

    2022

  20. [29]

    Transportation science 55(5):1113--1135, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.2021.1044

    Rist Y, Forbes MA (2021) A new formulation for the dial-a-ride problem. Transportation science 55(5):1113--1135, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.2021.1044

    2021

  21. [30]

    Transportation science 43(3):267--286, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.1090.0272

    Ropke S, Cordeau JF (2009) Branch and cut and price for the pickup and delivery problem with time windows. Transportation science 43(3):267--286, ISSN 0041-1655, ://dx.doi.org/10.1287/trsc.1090.0272

    2009

  22. [31]

    EURO journal on computational optimization 1(1-2):81--115, ISSN 2192-4406, ://dx.doi.org/10.1007/s13675-013-0009-9

    Sadykov R, Vanderbeck F (2013) Column generation for extended formulations. EURO journal on computational optimization 1(1-2):81--115, ISSN 2192-4406, ://dx.doi.org/10.1007/s13675-013-0009-9

    2013 doi

  23. [32]

    Technical report, Inria Bordeaux Sud-Ouest , ://inria.hal.science/hal-03340548

    Sadykov R, Vanderbeck F (2021) BaPCod - a generic branch-and-price code . Technical report, Inria Bordeaux Sud-Ouest , ://inria.hal.science/hal-03340548

    2021

  24. [33]

    INFORMS journal on computing 31(2):251--267, ISSN 1091-9856 1526-5528, ://dx.doi.org/10.1287/ijoc.2018.0822

    Sadykov R, Vanderbeck F, Pessoa A, Tahiri I, Uchoa E (2019) Primal heuristics for branch and price: The assets of diving methods. INFORMS journal on computing 31(2):251--267, ISSN 1091-9856 1526-5528, ://dx.doi.org/10.1287/ijoc.2018.0822

    2019

  25. [34]

    Applied sciences 11(21):10295, ISSN 2076-3417, ://dx.doi.org/10.3390/app112110295

    Tan SY, Yeh WC (2021) The vehicle routing problem: State‐of‐the‐art classification and review. Applied sciences 11(21):10295, ISSN 2076-3417, ://dx.doi.org/10.3390/app112110295

    2021 doi

  26. [35]

    European journal of operational research 309(3):1125--1144, ISSN 0377-2217, ://dx.doi.org/10.1016/j.ejor.2023.02.030

    Yin Y, Li D, Wang D, Ignatius J, Cheng TCE, Wang S (2023) A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows. European journal of operational research 309(3):1125--1144, ISSN 0377-2217, ://dx.doi.org/10.1016/j.ejor.2023.02.030

    2023 doi

  27. [36]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution isbn issn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sen...

  28. [37]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

  29. [38]

    Nemhauser GL, Wolsey LA, 1988 Integer and combinatorial optimization (John Wiley and Sons)

    1988

  30. [39]

    Mathematical programming 183(1-2):483--523, ://dx.doi.org/10.1007/s10107-020-01523-z

    Pessoa A, Sadykov R, Uchoa E, Vanderbeck F, 2020 A generic exact solver for vehicle routing and related problems. Mathematical programming 183(1-2):483--523, ://dx.doi.org/10.1007/s10107-020-01523-z

    2020 doi

  31. [40]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution isbn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence...

  32. [41]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.