A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem

DOI10.1002/net.20330zbMath1205.90081MaRDI QIDQ3057116

Marcus Poggi de Aragão, Artur Alves Pessoa, Eduardo Uchoa

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20330

zbMATH Keywords

column generation; cutting planes; extended formulations

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90B20: Traffic problems in operations research

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows, An Improved Branch-Cut-and-Price Algorithm for Parallel Machine Scheduling Problems, Thirty years of heterogeneous vehicle routing, Orienteering problem: a survey of recent variants, solution approaches and applications, Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems, Exact algorithms for routing problems under vehicle capacity constraints, Improved lower bounds for the split delivery vehicle routing problem, Task assignment with start time-dependent processing times for personnel at check-in counters, Layered graph approaches for combinatorial optimization problems, Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems, Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem, A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet, Solving the team orienteering arc routing problem with a column generation approach, A hybrid algorithm for the heterogeneous fleet vehicle routing problem, The time dependent traveling salesman problem: polyhedra and algorithm, Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints, An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem, Improved branch-cut-and-price for capacitated vehicle routing, A hybrid adaptive large neighborhood search heuristic for the team orienteering problem, A POPMUSIC matheuristic for the capacitated vehicle routing problem, Branch-and-cut algorithms for the vehicle routing problem with trailers and transshipments

Uses Software

• CVRPSP

Cites Work

• A column generation approach to the heterogeneous fleet vehicle routing problem
• The fleet size and mix vehicle routing problem
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• A tabu search heuristic for the heterogeneous fleet vehicle routing problem
• A sweep-based algorithm for the fleet size and mix vehicle routing problem
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem
• Formulations and valid inequalities for the heterogeneous vehicle routing problem
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k ≥ 3
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• A heuristic column generation method for the heterogeneous fleet VRP
• Tabu search variants for the mix fleet vehicle routing problem