An exact algorithm for the capacitated shortest spanning arborescence

DOI10.1007/BF02098285zbMath0844.90104MaRDI QIDQ1908299

Daniele Vigo, Paolo Toth

Publication date: 18 March 1996

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

zbMATH Keywords

Lagrangian relaxationbranch-and-boundheuristic algorithmsnetwork designroutingcapacitated shortest spanning arborescencecomplete and loop-free digraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonlinear systems in control theory (93C10)

Related Items

Unnamed Item, A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem, Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, Formulations and exact algorithms for the vehicle routing problem with time windows, Models, relaxations and exact approaches for the capacitated vehicle routing problem

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new dominance procedure for combinatorial optimization problems
• An additive bounding procedure for the asymmetric travelling salesman problem
• A heuristic algorithm for the asymmetric capacitated vehicle routing problem
• New lower bounds for the symmetric travelling salesman problem
• A branch and bound algorithm for the capacitated minimum spanning tree problem
• Efficient algorithms for a family of matroid intersection problems
• An exact algorithm for the asymmetrical capacitated vehicle routing problem
• A branch and bound algorithm for the multiple depot vehicle scheduling problem
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• The complexity of the capacitated tree problem
• Computing capacitated minimal spanning trees efficiently
• Finding optimum branchings
• An Exact Algorithm for the Vehicle Routing Problem with Backhauls
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees
• A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Optimum branchings
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• The Capacitated Minimum Spanning Tree