A tutorial on column generation and branch-and-price for vehicle routing problems

DOI10.1007/s10288-010-0130-zzbMath1208.90016OpenAlexW2036969993MaRDI QIDQ633483

Dominique Feillet

Publication date: 1 April 2011

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-010-0130-z

zbMATH Keywords

column generationvehicle routing problembranch-and-price

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Transportation, logistics and supply chain management (90B06)

Related Items

Green hybrid fleets using electric vehicles: solving the heterogeneous vehicle routing problem with multiple driving ranges and loading capacities, Solving the petroleum replenishment and routing problem with variable demands and time windows, Robust Team Orienteering Problem with Decreasing Profits, Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows, A branch-and-price algorithm for stable workforce assignments with hierarchical skills, Using the primal-dual interior point algorithm within the branch-price-and-cut method, Empirical analysis for the VRPTW with a multigraph representation for the road network, The multiple Steiner TSP with order constraints: complexity and optimization algorithms, Accelerating the branch-and-price algorithm using machine learning, Exact Branch-Price-and-Cut for a Hospital Therapist Scheduling Problem with Flexible Service Locations and Time-Dependent Location Capacity, Learning-Based Branch-and-Price Algorithms for the Vehicle Routing Problem with Time Windows and Two-Dimensional Loading Constraints, Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time, An efficient and general approach for the joint order batching and picker routing problem, Configuration‐based approach for topological problems in the design of wireless sensor networks, Estimating the marginal cost to deliver to individual customers, Linear edge costs and labeling algorithms: The case of the time‐dependent vehicle routing problem with time windows, The multi-trip container drayage problem with synchronization for efficient empty containers re-usage, The robust vehicle routing problem with time windows: solution by branch and price and cut, Detecting critical node structures on graphs: A mathematical programming approach, The time-dependent vehicle routing problem with time windows and road-network information, A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration, Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies, A branch-and-price algorithm for a vehicle routing with demand allocation problem, A way to optimally solve a green time-dependent vehicle routing problem with time windows, Branch-and-price approaches for the multiperiod technician routing and scheduling problem, A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports, Minimum makespan vehicle routing problem with compatibility constraints, Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization, The Team Orienteering Pick-Up and Delivery Problem with Time Windows and its applications in fleet sizing, A relax‐and‐price heuristic for the inventory‐location‐routing problem, Robust vehicle routing under uncertainty via branch-price-and-cut, Modeling and Solving Vehicle Routing Problems with Many Available Vehicle Types, A matheuristic for the truck and trailer routing problem, A heuristic for cumulative vehicle routing using column generation

Uses Software

• VRP

Cites Work

• Unnamed Item
• Recent advances in vehicle routing exact algorithms
• Stabilized column generation
• New variants of bundle methods
• A descent method with linear programming subproblems for nondifferentiable convex optimization
• Interior point stabilization for column generation
• Comparison of bundle and classical column generation
• An exact algorithm for team orienteering problems
• Vehicle routing problem with elementary shortest path based column generation
• A generic view of Dantzig--Wolfe decomposition in mixed integer programming
• Lagrangian duality applied to the vehicle routing problem with time windows
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• 2-Path Cuts for the Vehicle Routing Problem with Time Windows
• The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k ≥ 3
• Cutting planes for branch-and-price algorithms
• The Cutting-Plane Method for Solving Convex Programs
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• The B<scp>oxstep</scp> Method for Large-Scale Optimization
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• On constrained optimization by adjoint based quasi-Newton methods
• A Branch-and-Cut Procedure for the Vehicle Routing Problem with Time Windows
• On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Generalized Bundle Methods
• Selected Topics in Column Generation
• Shortest Path Problems with Resource Constraints
• Implementing Mixed Integer Column Generation