Construction heuristics for the asymmetric TSP.

DOI10.1016/S0377-2217(99)00468-3zbMath1125.90402OpenAlexW2080461238MaRDI QIDQ5928379

Gregory Gutin, Anders Yeo, Alexey Zverovich, Fred Glover

Publication date: 28 March 2001

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(99)00468-3

zbMATH Keywords

Construction heuristicsHeuristicsTraveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem, Towards auction algorithms for large dense assignment problems, Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP, Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics, A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem, A generalized constructive algorithm using insertion-based heuristics, A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness, A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness, A column generation-based heuristic for a rehabilitation patient scheduling and routing problem, Transformations of generalized ATSP into ATSP., Combinação de abordagens GLSP e ATSP para o problema de dimensionamento e sequenciamento de lotes de produção de suplementos para nutrição animal, Dominance rules for single machine schedule with sequence dependent setup and due date, Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching, Solution of real-world postman problems, Determination of the candidate arc set for the asymmetric traveling salesman problem, Extended neighborhood: Definition and characterization, TSP tour domination and Hamilton cycle decompositions of regular digraphs, Iterative patching and the asymmetric traveling salesman problem, Preemptive stacker crane problem: extending tree-based properties and construction heuristics, Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems, Some dominance properties for single-machine tardiness problems with sequence-dependent setup, Variable neighborhood search-based solution methods for the pollution location-inventory-routing problem, Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential neighbourhood local search for the traveling salesman problem
• Small diameter neighbourhood graphs for the traveling salesman problem: At most four moves from tour to tour
• The traveling salesman. Computational solutions for RSP applications
• A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• Implementation of a linear time algorithm for certain generalized traveling salesman problems
• A new heuristic for the traveling salesman problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II