An exact algorithm for the capacitated shortest spanning arborescence

DOI10.1007/BF02098285MaRDI QIDQ1908299zbMATH OpenFDO

Authors Daniele Vigo, Paolo Toth

Publication date 18 March 1996

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

zbMATH Keywords

network designroutingbranch-and-boundheuristic algorithmsLagrangian relaxationcapacitated shortest spanning arborescencecomplete and loop-free digraph

Mathematics Subject Classification ID

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

Recommendations

• A branch and bound algorithm for the capacitated minimum spanning tree problem
• A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Finding minimum cost directed trees with demands and capacities
• Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 4125195 (Why is no real title available?)
• A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs
• A branch and bound algorithm for the capacitated minimum spanning tree problem
• A branch and bound algorithm for the multiple depot vehicle scheduling problem
• A heuristic algorithm for the asymmetric capacitated vehicle routing problem
• A new dominance procedure for combinatorial optimization problems
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• An Exact Algorithm for the Vehicle Routing Problem with Backhauls
• An additive bounding procedure for the asymmetric travelling salesman problem
• An exact algorithm for the asymmetrical capacitated vehicle routing problem
• Computing capacitated minimal spanning trees efficiently
• Efficient algorithms for a family of matroid intersection problems
• Finding optimum branchings
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Network flows. Theory, algorithms, and applications.
• New lower bounds for the symmetric travelling salesman problem
• Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees
• Optimum branchings
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The Capacitated Minimum Spanning Tree
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The complexity of the capacitated tree problem
• The traveling-salesman problem and minimum spanning trees: Part II

Cited in

(6)

• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• Models, relaxations and exact approaches for the capacitated vehicle routing problem
• scientific article; zbMATH DE number 1420487 (Why is no real title available?)
• The (K,k)-Capacitated Spanning Tree Problem
• A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem
• Formulations and exact algorithms for the vehicle routing problem with time windows

Describes a project that uses

Uses Software

• VRP

This page was built for publication: An exact algorithm for the capacitated shortest spanning arborescence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908299)