Stronger \(K\)-tree relaxations for the vehicle routing problem

DOI10.1016/S0377-2217(03)00353-9zbMath1061.90023MaRDI QIDQ1827647

Abilio Lucena, Nelson F. Maculan, Carlos A. Martinhon

Publication date: 6 August 2004

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

Integer programmingVehicle routing problemand cutExact solution algorithmRelax

Mathematics Subject Classification ID

Integer programming (90C10) Traffic problems in operations research (90B20)

Related Items

Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ Heuristic and exact algorithms for a min-max selective vehicle routing problem ⋮ Shape Measures of Random Increasing k-trees ⋮ A relax-and-cut algorithm for the set partitioning problem ⋮ Exact algorithms for the vertex separator problem in graphs ⋮ Decomposition and dynamic cut generation in integer linear programming ⋮ Robust branch-and-cut-and-price for the capacitated vehicle routing problem ⋮ A note on relatives to the Held and Karp 1-tree problem ⋮ Non delayed relax-and-cut algorithms

Uses Software

• TSPLIB
• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch and bound algorithm for the capacitated vehicle routing problem
• Polyhedral study of the capacitated vehicle routing problem
• A branch-and-cut algorithm for vehicle routing problems
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• Numerical optimization. Theoretical and practice aspects
• On the capacitated vehicle routing problem
• The volume algorithm: Producing primal solutions with a subgradient method
• Separating capacity constraints in the CVRP using tabu search
• Lagrangean heuristics for location problems
• A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations
• Routing problems: A bibliography
• The Truck Dispatching Problem
• The Vehicle Routing Problem
• State-space relaxation procedures for the computation of bounds to routing problems
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• TSPLIB—A Traveling Salesman Problem Library
• Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees
• A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem
• Validation of subgradient optimization
• Optimal rectangular partitions
• A Matching Based Exact Algorithm for Capacitated Vehicle Routing Problems
• Extensions of the Petal Method for Vehicle Routeing
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• A Lagrangian relaxation approach to the edge-weighted clique problem