Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty

DOI10.1287/opre.2020.2035zbMath1472.90079OpenAlexW2946283300MaRDI QIDQ5003707

Artur Alves Pessoa, François Vanderbeck, Ruslan Sadykov, Michael Poss

Publication date: 29 July 2021

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01958184

zbMATH Keywords

vehicle routinglocal searchrobust optimizationbranch-cut-and-pricecapacity inequalities

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Robustness in mathematical programming (90C17)

Related Items (7)

Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty ⋮ Constant-Ratio Approximation for Robust Bin Packing with Budgeted Uncertainty ⋮ A concise guide to existing and emerging vehicle routing problem variants ⋮ Approximating the chance-constrained capacitated vehicle routing problem with robust optimization ⋮ Recent advances in vehicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price-and-cut ⋮ An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands ⋮ Robust vehicle routing under uncertainty via branch-price-and-cut

Uses Software

• BaPCod
• CVRPSP

Cites Work

• Unnamed Item
• Robust combinatorial optimization with variable cost uncertainty
• An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Stochastic vehicle routing
• Robust discrete optimization and network flows
• Adjustable robust solutions of uncertain linear programs
• A branch-and-price algorithm for the minimum latency problem
• Robust combinatorial optimization with knapsack uncertainty
• Limited memory rank-1 cuts for vehicle routing problems
• The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach
• Exact algorithms for the chance-constrained vehicle routing problem
• A heuristic for moment-matching scenario generation
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• Robust combinatorial optimization with variable budgeted uncertainty
• Complexity results and exact algorithms for robust knapsack problems
• A short note on the robust combinatorial optimization problems with cardinality constrained uncertainty
• Heuristics for multi-attribute vehicle routing problems: a survey and synthesis
• A unified exact method for solving different classes of vehicle routing problems
• Improved branch-cut-and-price for capacitated vehicle routing
• A note on the Bertsimas \& Sim algorithm for robust combinatorial optimization problems
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Robust Convex Optimization
• The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty
• New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem
• Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling
• Distributionally Robust Convex Optimization
• Introduction to Stochastic Programming
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• The Price of Robustness
• Technical Note—Branch-and-Price-and-Cut Approach to the Robust Network Design Problem Without Flow Bifurcations
• The Distributionally Robust Chance-Constrained Vehicle Routing Problem
• Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation
• Shortest Path Problems with Resource Constraints
• Lower bounds and algorithms for the 2-dimensional vector packing problem

This page was built for publication: Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty