The traveling salesman. Computational solutions for RSP applications

DOI10.1007/3-540-48661-5zbMath0825.90720OpenAlexW4232657405MaRDI QIDQ1338450

Gerhard Reinelt

Publication date: 1 December 1994

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-48661-5

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (81)

Generating subtour elimination constraints for the TSP from pure integer solutions ⋮ Nagging: A scalable fault-tolerant paradigm for distributed search ⋮ Minimization and maximization versions of the quadratic travelling salesman problem ⋮ Embedded local search approaches for routing optimization ⋮ On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem ⋮ Robust optimization for routing problems on trees ⋮ Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP ⋮ A distribution-free TSP tour length estimation model for random graphs ⋮ Genetic operators for combinatorial optimization in TSP and microarray gene ordering ⋮ Dealing with time in the multiple traveling salespersons problem with moving targets ⋮ hCHAC: a family of MOACO algorithms for the resolution of the bi-criteria military unit pathfinding problem ⋮ A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem ⋮ Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: an application to fish aggregating devices ⋮ Intelligent-guided adaptive search for the maximum covering location problem ⋮ An efficient implementation of a static move descriptor-based local search heuristic ⋮ TSP ejection chains ⋮ AN INTEGER L-SHAPED ALGORITHM FOR TIME-CONSTRAINED TRAVELING SALESMAN PROBLEM WITH STOCHASTIC TRAVEL AND SERVICE TIMES ⋮ Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem ⋮ Optimal path for automated drilling operations by a new heuristic approach using particle swarm optimization ⋮ The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem ⋮ Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions ⋮ Coupling ant colony systems with strong local searches ⋮ Routing problems with loading constraints ⋮ The traveling salesman problem on grids with forbidden neighborhoods ⋮ New TSP construction heuristics and their relationships to the 2-opt ⋮ Traveling salesman problem with clustering ⋮ Computing the variance of tour costs over the solution space of the TSP in polynomial time ⋮ Probabilistic analysis of optimization problems on sparse random shortest path metrics ⋮ The multiple traveling salesmen problem with moving targets ⋮ A semidefinite optimization approach to the target visitation problem ⋮ A branch-and-bound approach for a vehicle routing problem with customer costs ⋮ The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem ⋮ Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs ⋮ Optimal Area Polygonization by Triangulation and Visibility Search ⋮ Unnamed Item ⋮ Combining probabilistic algorithms, constraint programming and Lagrangian relaxation to solve the vehicle routing problem ⋮ Improving the Hopfield model performance when applied to the traveling salesman problem. A divide-and-conquer scheme ⋮ Ant algorithms: theory and applications ⋮ Unnamed Item ⋮ Implementation of ensemble-based simulated annealing with dynamic load balancing under MPI ⋮ A column generation approach to capacitated \(p\)-median problems ⋮ Fast, efficient and accurate solutions to the Hamiltonian path problem using neural approaches ⋮ Record breaking optimization results using the ruin and recreate principle ⋮ On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances ⋮ An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem ⋮ On the neighborhood structure of the traveling salesman problem generated by local search moves ⋮ Golden ratio versus pi as random sequence sources for Monte Carlo integration ⋮ A customized genetic algorithm for bi-objective routing in a dynamic network ⋮ Computing finest mincut partitions of a graph and application to routing problems ⋮ A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions ⋮ 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem ⋮ Construction heuristics for the asymmetric TSP. ⋮ Symmetric weight constrained traveling salesman problem: Local search ⋮ Geometric and LP-based heuristics for angular travelling salesman problems in the plane ⋮ A survey of very large-scale neighborhood search techniques ⋮ Determination of the candidate arc set for the asymmetric traveling salesman problem ⋮ Monitoring and control of anytime algorithms: A dynamic programming approach ⋮ \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem ⋮ The traveling salesman problem: new polynomial approximation algorithms and domination analysis ⋮ The approximation ratio of the greedy algorithm for the metric traveling salesman problem ⋮ Path optimization with limited sensing ability ⋮ New semidefinite programming relaxations for the linear ordering and the traveling salesman problem ⋮ Search heuristics and the influence of non-perfect randomness: examining genetic algorithms and simulated annealing ⋮ Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles ⋮ Heuristic scheduling of parallel machines with sequence-dependent set-up times ⋮ Design and analysis of stochastic local search for the multiobjective traveling salesman problem ⋮ Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration ⋮ Guided local search and its application to the traveling salesman problem ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Linear programs for constraint satisfaction problems ⋮ Angular bisector insertion algorithm for solving small-scale symmetric and asymmetric traveling salesman problem ⋮ Estimating the Held-Karp lower bound for the geometric TSP ⋮ Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ Heuristics for the rural postman problem ⋮ An effective implementation of the Lin-Kernighan traveling salesman heuristic ⋮ An approximation algorithm for the facility location problem with lexicographic minimax objective ⋮ Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation ⋮ A new variant of a vehicle routing problem: Lower and upper bounds ⋮ Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems ⋮ Relaxed tours and path ejections for the traveling salesman problem

This page was built for publication: The traveling salesman. Computational solutions for RSP applications