Fast Algorithms for Geometric Traveling Salesman Problems
From MaRDI portal
Publication:4024311
DOI10.1287/IJOC.4.4.387zbMath0758.90071OpenAlexW2102076751MaRDI QIDQ4024311
Publication date: 25 February 1993
Published in: ORSA Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.4.4.387
approximate traveling salesman toursmultidimensional point setsstarting heuristicsuniform planar million-city traveling salesman
Programming involving graphs or networks (90C35) Large-scale problems in mathematical programming (90C06) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items (71)
A guided local search heuristic for the capacitated arc routing problem ⋮ Embedded local search approaches for routing optimization ⋮ Genetically improved presequences for Euclidean traveling salesman problems ⋮ A new adaptive multi-start technique for combinatorial global optimizations ⋮ Multiple phase neighborhood search---GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP ⋮ Genetic operators for combinatorial optimization in TSP and microarray gene ordering ⋮ The traveling group problem ⋮ TRAVELING SALESMAN PROBLEM OF SEGMENTS ⋮ Perturbed decomposition algorithm applied to the multi-objective traveling salesman problem ⋮ An improved ant colony system for the sequential ordering problem ⋮ Fast local search and guided local search and their application to British Telecom's workforce scheduling problem ⋮ Technical note: Split algorithm in \(O(n)\) for the capacitated vehicle routing problem ⋮ Routing problems: A bibliography ⋮ Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts ⋮ Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem ⋮ Variable neighborhood search ⋮ Solving large-scale TSP using a fast wedging insertion partitioning approach ⋮ The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem ⋮ Divide and conquer strategies for parallel TSP heuristics ⋮ Genetic algorithms for the traveling salesman problem ⋮ A multi-space sampling heuristic for the vehicle routing problem with stochastic demands ⋮ Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep ⋮ Neighborhood decomposition-driven variable neighborhood search for capacitated clustering ⋮ Coupling ant colony systems with strong local searches ⋮ New TSP construction heuristics and their relationships to the 2-opt ⋮ A hybrid particle swarm optimization approach for the sequential ordering problem ⋮ Heuristics for a cash-collection routing problem with a cluster-first route-second approach ⋮ New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem ⋮ The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem ⋮ Traveling salesman problem heuristics: leading methods, implementations and latest advances ⋮ Inter-depot moves and dynamic-radius search for multi-depot vehicle routing problems ⋮ Unnamed Item ⋮ Assigning real-time tasks to heterogeneous processors by applying ant colony optimization ⋮ Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand ⋮ Instance-specific multi-objective parameter tuning based on fuzzy logic ⋮ Memetic algorithm based on improved inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem ⋮ A discrete gravitational search algorithm for solving combinatorial optimization problems ⋮ On the solving strategy in composite heuristics ⋮ Variable neighborhood search: Principles and applications ⋮ Match twice and stitch: a new TSP tour construction heuristic. ⋮ Sequential search and its application to vehicle-routing problems ⋮ First vs. best improvement: an empirical study ⋮ Expanding neighborhood GRASP for the traveling salesman problem ⋮ Minimizing labor requirements in a periodic vehicle loading problem ⋮ A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands ⋮ Estimation-based metaheuristics for the probabilistic traveling salesman problem ⋮ On the benefits of co-collection: experiments with a multi-compartment vehicle routing algorithm ⋮ Exact solution of the soft-clustered vehicle-routing problem ⋮ A cooperative parallel meta-heuristic for the vehicle routing problem with time windows ⋮ Iterated local search for the quadratic assignment problem ⋮ A hybrid metaheuristic for the quadratic assignment problem ⋮ Bounded-degree plane geometric spanners in practice ⋮ Provably good solutions for the traveling salesman problem ⋮ An interactive simulation and analysis software for solving TSP using ant colony optimization algorithms ⋮ Design and analysis of stochastic local search for the multiobjective traveling salesman problem ⋮ Lasso solution strategies for the vehicle routing problem with pickups and deliveries ⋮ Guided local search and its application to the traveling salesman problem ⋮ Continuous reformulations and heuristics for the Euclidean travelling salesperson problem ⋮ Speed-up techniques for solving large-scale biobjective TSP ⋮ Transgenetic algorithm for the traveling purchaser problem ⋮ Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem ⋮ New edges not used in shortest tours of TSP ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ An effective implementation of the Lin-Kernighan traveling salesman heuristic ⋮ A note on single alternating cycle neighborhoods for the TSP ⋮ Fast local search algorithms for the handicapped persons transportation problem ⋮ IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem ⋮ Method to solve the travelling salesman problem using the inverse of diffusion process ⋮ A hybrid genetic-GRASP algorithm using Lagrangean relaxation for the traveling salesman problem ⋮ Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers ⋮ Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care
This page was built for publication: Fast Algorithms for Geometric Traveling Salesman Problems
