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

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

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

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

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, 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, 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