The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
Abstract
This paper presents a branch-and-cut-and-price algorithm for the vehicle-routing problem with time windows. The standard Dantzig-Wolfe decomposition of the arc flow formulation leads to a set-partitioning problem as the master problem and an elementary shortest-path problem with resource constraints as the pricing problem. We introduce the subset-row inequalities, which are Chvatal-Gomory rank-1 cuts based on a subset of the constraints in the master problem. Applying a subset-row inequality in the master problem increases the complexity of the label-setting algorithm used to solve the pricing problem because an additional resource is added for each inequality. We propose a modified dominance criterion that makes it possible to dominate more labels by exploiting the step-like structure of the objective function of the pricing problem. Computational experiments have been performed on the Solomon benchmarks where we were able to close several instances. The results show that applying subset-row inequalities in the master problem significantly improves the lower bound and, in many cases, makes it possible to prove optimality in the root node.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Integer and Combinatorial Optimization
Williams, H. P., Nemhauser, G. L., & Wolsey, L. A. (1990) · Journal of the Operational Research Society · doi:10.2307/2583737 · Cited by 5,485
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
Solomon, M. M. (1987) · Operations Research · doi:10.1287/opre.35.2.254 · Cited by 4,298
(2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718515 · Cited by 4,008
Nemhauser, G. L., & Wolsey, L. A. (1972) · Cited by 3,365
Integer and Combinatorial Optimization
Nemhauser, G., & Wolsey, L. (1988) · Wiley eBooks · doi:10.1002/9781118627372 · Cited by 3,176
Branch-and-price: column generation for solving huge integer programs
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998) · Operations Research · doi:10.1287/opre.46.3.316 · Cited by 2,219
A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
Desrochers, M., Desrosiers, J., & Solomon, M. (1992) · Operations Research · doi:10.1287/opre.40.2.342 · Cited by 1,197
Selected Topics in Column Generation
Lübbecke, M. E., & Desrosiers, J. (2005) · Operations Research · doi:10.1287/opre.1050.0234 · Cited by 1,102
Feillet, D., Dejax, P., Gendreau, M., & Gueguen, C. (2004) · Networks · doi:10.1002/net.20033 · Cited by 693
Edmonds polytopes and a hierarchy of combinatorial problems
Chvátal, V. (1973) · Discrete Mathematics · doi:10.1016/0012-365x(73)90167-2 · Cited by 624
Shortest Path Problems with Resource Constraints
Irnich, S., & Desaulniers, G. (2006) · Column Generation · doi:10.1007/0-387-25486-2_2 · Cited by 597
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem
Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. D., Reis, M., Uchoa, E., & Werneck, R. F. (2006) · Mathematical Programming · doi:10.1007/s10107-005-0644-x · Cited by 539
Fleet Management and Logistics
(1998) · Springer eBooks · doi:10.1007/978-1-4615-5755-5 · Cited by 485
2-Path Cuts for the Vehicle Routing Problem with Time Windows
Kohl, N., Desrosiers, J., Madsen, O. B. G., Solomon, M. M., & Soumis, F. (1999) · Transportation Science · doi:10.1287/trsc.33.1.101 · Cited by 411
Righini, G., & Salani, M. (2006) · Discrete Optimization · doi:10.1016/j.disopt.2006.05.007 · Cited by 364
An algorithm for the resource constrained shortest path problem
Beasley, J. E., & Christofides, N. (1989) · Networks · doi:10.1002/net.3230190402 · Cited by 327
Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
Dror, M. (1994) · Operations Research · doi:10.1287/opre.42.5.977 · Cited by 325
New dynamic programming algorithms for the resource constrained elementary shortest path problem
Righini, G., & Salani, M. (2008) · Networks · doi:10.1002/net.20212 · Cited by 284
A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems
Desaulniers, G., Desrosiers, J., loachim, I., Solomon, M. M., Soumis, F., & Villeneuve, D. (1998) · Fleet Management and Logistics · doi:10.1007/978-1-4615-5755-5_3 · Cited by 238
Vehicle Routing Problem with elementary shortest path based column generation
Chabrier, A. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2005.02.029 · Cited by 232
2-Path Cuts for the Vehicle Routing Problem with Time Windows
Desrosiers, J., Solomon, M. M., Soumis, F., Kohl, N., & Madsen, O. B. G. (1997) · Les Cahiers du GERAD · Cited by 225
The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k ≥ 3
Irnich, S., & Villeneuve, D. (2006) · INFORMS Journal on Computing · doi:10.1287/ijoc.1040.0117 · Cited by 215
Accelerated label setting algorithms for the elementary resource constrained shortest path problem
Boland, N., Dethridge, J., & Dumitrescu, I. (2006) · Operations Research Letters · doi:10.1016/j.orl.2004.11.011 · Cited by 200
Resource extension functions: properties, inversion, and generalization to segments
Irnich, S. (2007) · OR Spectrum · doi:10.1007/s00291-007-0083-6 · Cited by 163
A polyhedral approach to edge coloring
Nemhauser, G. L., & Park, S. (1991) · Operations Research Letters · doi:10.1016/0167-6377(91)90003-8 · Cited by 57
Cited by
New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem
Baldacci, R., Mingozzi, A., & Roberti, R. (2011) · Operations Research · doi:10.1287/opre.1110.0975 · Cited by 506
Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows
Desaulniers, G., Errico, F., Irnich, S., & Schneider, M. (2016) · Operations Research · doi:10.1287/opre.2016.1535 · Cited by 497
Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows
Ropke, S., & Cordeau, J.-F. (2009) · Transportation Science · doi:10.1287/trsc.1090.0272 · Cited by 487
Baldacci, R., Mingozzi, A., & Roberti, R. (2012) · European Journal of Operational Research · doi:10.1016/j.ejor.2011.07.037 · Cited by 474
Heuristics for multi-attribute vehicle routing problems: A survey and synthesis
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.02.053 · Cited by 430
Metadata
- Authors
- Jepsen, M., Petersen, B., Spoorendonk, S., & Pisinger, D.
- Venue
- Operations Research
- Published
- 2008-04
- Volume
- 56
- Issue
- 2
- Pages
- 497-511
- ISSN
- 0030-364X (ISSN-L)
- 1526-5463
- OpenAlex
- W2111658959
- Cited by
- 410
- References
- 25
- FWCI
- 27.69
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.