An additive bounding procedure for the asymmetric travelling salesman problem

DOI10.1007/BF01585701zbMath0773.90082MaRDI QIDQ1184344

Matteo Fischetti, Paolo Toth

Publication date: 28 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

branch and boundlower boundsspanning arborescencesasymmetric travelling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A lift-and-project cutting plane algorithm for mixed 0-1 programs, A capacitated general routing problem on mixed networks, Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, SelfSplit parallelization for mixed-integer linear programming, An exact algorithm for the capacitated shortest spanning arborescence, Routing problems: A bibliography, A branch‐and‐bound algorithm for the double travelling salesman problem with two stacks, A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls, Self-organizing feature maps for the vehicle routing problem with backhauls, Minimax regret spanning arborescences under uncertain costs, Matheuristics: survey and synthesis, An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading, Unnamed Item, Heuristics from Nature for Hard Combinatorial Optimization Problems, A Stochastic Integer Programming Approach to Air Traffic Scheduling and Operations, Improved filtering for weighted circuit constraints, A Column Generation Model for a Scheduling Problem with Maintenance Constraints, An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation, Models, relaxations and exact approaches for the capacitated vehicle routing problem, The weighted arborescence constraint, The Rural Postman Problem on mixed graphs with turn penalties, Cluster based branching for the asymmetric traveling salesman problem, A heuristic algorithm for the asymmetric capacitated vehicle routing problem, New lower bounds for the symmetric travelling salesman problem, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Heuristics for the flow line problem with setup costs

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On dual solutions of the linear assignment problem
• New lower bounds for the symmetric travelling salesman problem
• An Algorithm for the Bottleneck Traveling Salesman Problem
• A branch and bound algorithm for the multiple depot vehicle scheduling problem
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• A note on finding optimum branchings
• Thek best spanning arborescences of a network
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• A restricted Lagrangean approach to the traveling salesman problem
• Finding optimum branchings
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Packing rooted directed cuts in a weighted directed graph
• Optimum branchings
• A man-machine approach toward solving the traveling salesman problem
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The traveling-salesman problem and minimum spanning trees: Part II
• Depth-First Search and Linear Graph Algorithms
• Technical Note—Bounds for the Travelling-Salesman Problem