The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm

DOI10.1016/0166-218X(86)90087-9zbMath0603.90132MaRDI QIDQ1083379

Jeffrey L. Kennington, Agha Iqbal Ali

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

Lagrangean relaxationgreedy algorithmcomputational experienceminimum spanning treesmultiple travelling salesman problemsubgradient procedure

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (11)

Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ Transformation of multidepot multisalesmen problem to the standard travelling salesman problem ⋮ A generalization of Polyak's convergence result for subgradient optimization ⋮ A simple model for the multiple traveling salesmen problem with single depot and multiple sink ⋮ Experimental study of a hybrid genetic algorithm for the multiple travelling salesman problem ⋮ Graphical-structure-based models for routing problems ⋮ The multiagent planning problem ⋮ An algorithm for mapping the asymmetric multiple traveling salesman problem onto colored Petri nets ⋮ On the shortest path problem with negative cost cycles ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ A new variant of a vehicle routing problem: Lower and upper bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Integer Programming Formulation of Traveling Salesman Problems
• A polynomially bounded algorithm for a singly constrained quadratic program
• The traveling salesman problem: A duality approach
• Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
• Validation of subgradient optimization
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Duality in Nonlinear Programming: A Simplified Applications-Oriented Development
• Integer Programming Algorithms: A Framework and State-of-the-Art Survey
• Matroids and the greedy algorithm
• Computational Experience with an M-Salesman Traveling Salesman Algorithm

This page was built for publication: The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm