A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
From MaRDI portal
Publication:1575073
DOI10.1007/s101070050010zbMath1043.90075OpenAlexW2027764232MaRDI QIDQ1575073
Gerhard J. Woeginger, Vladimir G. Deǐneko
Publication date: 2000
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s101070050010
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (32)
Multiobjective traveling salesperson problem on Halin graphs ⋮ The bipartite quadratic assignment problem and extensions ⋮ A survey for the quadratic assignment problem ⋮ The stable set problem and the thinness of a graph ⋮ Split-merge: using exponential neighborhood search for scheduling a batching machine ⋮ A new asymmetric pyramidally solvable class of the traveling salesman problem ⋮ The exponential multi-insertion neighborhood for the vehicle routing problem with unit demands ⋮ The parameterized complexity of local search for TSP, more refined ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems ⋮ An exponential (matching based) neighborhood for the vehicle routing problem ⋮ Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems ⋮ Upper bounds on ATSP neighborhood size. ⋮ Heuristics for vehicle routing problems: sequence or set optimization? ⋮ Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ Dominance guarantees for above-average solutions ⋮ Polynomially solvable cases of the bipartite traveling salesman problem ⋮ Construction heuristics for the asymmetric TSP. ⋮ A survey of very large-scale neighborhood search techniques ⋮ Extended neighborhood: Definition and characterization ⋮ Further extension of the TSP assign neighborhood ⋮ Creating very large scale neighborhoods out of smaller ones by compounding moves ⋮ A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem ⋮ A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem ⋮ Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ Fast local search algorithms for the handicapped persons transportation problem ⋮ Four-point conditions for the TSP: the complete complexity classification ⋮ A new ILP-based refinement heuristic for vehicle routing problems ⋮ New exponential neighbourhood for polynomially solvable TSPs ⋮ Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
This page was built for publication: A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
