An Algorithm for the Traveling Salesman Problem

DOI10.1287/opre.11.6.972zbMath0161.39305OpenAlexW2123241324WikidataQ56271119 ScholiaQ56271119MaRDI QIDQ5543949

C. Karel, John Little, D. W. Sweeney, Katta G. Murty

Publication date: 1963

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.11.6.972

zbMATH Keywords

operations research

Related Items

A branch-and-bound algorithm for a class of mixed integer linear maximum multiplicative programs: a bi-objective optimization approach ⋮ An efficient envelope-based branch and bound algorithm for non-convex combined heat and power production planning ⋮ The facility layout problem ⋮ Genetic algorithms applied to the solution of hybrid optimal control problems in astrodynamics ⋮ A planning and scheduling model for onsertion in printed circuit board assembly ⋮ A travelling salesman approach to solve the \(F\)/no-idle/\(C_{max}\) problem ⋮ Avoiding spurious submovement decompositions. II: A scattershot algorithm ⋮ Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem ⋮ Branch-and-bound and parallel computation: A historical note ⋮ The UMP exact test and the confidence interval for person parameters in IRT models ⋮ Dynamic programming and board games: a survey ⋮ A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ On estimating workload in interval branch-and-bound global optimization algorithms ⋮ Deterministic global optimization in ab-initio quantum chemistry ⋮ Methods of multiextremal optimization under constraints for separably quasimonotone functions ⋮ A MILP model for then-job,M-stage flowshop with sequence dependent set-up times ⋮ A mathematical model for supply chain management of blood banks in India ⋮ Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem ⋮ The traveling salesman problem with backhauls ⋮ Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics ⋮ Optimizing the planning of the observation of a catalog of objects by a mobile observer, taking the implicated limitations into account ⋮ Arbitrarily tight \(\alpha \mathrm{BB}\) underestimators of general non-linear functions over sub-optimal domains ⋮ Time-cost tradeoff in a three-dimensional assignment problem ⋮ Choosing optimal road trajectory with random work cost in different areas ⋮ Multiple and bicriteria scheduling: A literature survey ⋮ Optimal strategies in the fighting fantasy gaming system: influencing stochastic dynamics by gambling with limited resource ⋮ A study of complexity transitions on the asymmetric traveling salesman problem ⋮ A GROUPING GENETIC ALGORITHM FOR THE MULTIPLE TRAVELING SALESPERSON PROBLEM ⋮ The assembly line balancing and scheduling problem with sequence-dependent setup times: problem extension, model formulation and efficient heuristics ⋮ Dominance rules in combinatorial optimization problems ⋮ Multiobjective network scheduling with efficient use of renewable and nonrenewable resources ⋮ Heuristics and their design: A survey ⋮ A survey of scheduling methods for multiprocessor systems ⋮ A new approach to solving the multiple traveling salesperson problem using genetic algorithms ⋮ A branch and bound algorithm for minimizing the expected cost of testing coherent systems ⋮ Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations ⋮ A heuristic procedure for solving the quadratic assignment problem ⋮ Probabilistic analysis of solving the assignment problem for the traveling salesman problem ⋮ An extremal constrained routing problem with internal losses ⋮ A discrete cross aisle design model for order-picking warehouses ⋮ Extremal values of global tolerances in combinatorial optimization with an additive objective function ⋮ Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm ⋮ The use of state space relaxation for the dynamic facility location problem ⋮ Problem of successive megalopolis traversal with the precedence conditions ⋮ Experience of multilevel parallelizing of the branch and bound method in discrete optimization problems ⋮ Reducing reexpansions in iterative-deepening search by controlling cutoff bounds ⋮ An exact algorithm for the clustered travelling salesman problem ⋮ The travelling salesman problem with precedence constraints. ⋮ A travelling salesman problem (TSP) with multiple job facilities. ⋮ Optimality conditions to the acyclic travelling salesman problem. ⋮ Order batching algorithms and travel-time estimation for automated storage/retrieval systems ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Integer programming approaches to the travelling salesman problem ⋮ Personnel assignment by multiobjective programming ⋮ An improved branch and bound algorithm for minimum concave cost network flow problems ⋮ Time-dependent travelling salesman problem. ⋮ Repulsive assignment problem ⋮ A survey of the operational use of ILP models ⋮ Broadening the integer programming audience, the LINDO perspective ⋮ Implementing vehicle routing algorithms ⋮ Probabilistic subproblem selection in branch-and-bound algorithms ⋮ Probabilistic Analysis of Assignment Ranking: The Traveling Salesman Problems ⋮ An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem ⋮ A diagonal completion and 2-optimal procedure for the travelling salesman problem ⋮ On the identifiability of Bayesian factor analytic models ⋮ Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs ⋮ Probabilistic time-dependent vehicle routing problem ⋮ Probabilistic prediction of the complexity of traveling salesman problems based on approximating the complexity distribution from experimental data ⋮ A continuous variable representation of the traveling salesman problem ⋮ An approach for solving a class of transportation scheduling problems ⋮ The seriation problem and the travelling salesman problem ⋮ A characterization of linear admissible transformations for the m- travelling salesmen problem: A result of Berenguer ⋮ Procedures for travelling salesman problems with additional constraints ⋮ A characterization of linear admissible transformations for the m- travelling salesmen problem ⋮ Feasibility pump algorithm for sparse representation under Laplacian noise ⋮ Computational comparison on the partitioning strategies in multiple choice integer programming ⋮ Heuristically guided search and chromosome matching ⋮ The symmetric clustered traveling salesman problem ⋮ A branch and bound algorithm for the traveling purchaser problem ⋮ Research on a novel minimum-risk model for uncertain orienteering problem based on uncertainty theory ⋮ On the problem of sequential traversal of megalopolises with precedence conditions and cost functions depending on a list of tasks ⋮ An empirical study of a new metaheuristic for the traveling salesman problem ⋮ The optimum assignments and a new heuristic approach for the traveling salesman problem ⋮ The heuristic search under conditions of error ⋮ A scheduling problem in the baking industry ⋮ The influence of problem specific neighborhood structures in metaheuristics performance ⋮ SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS ⋮ The paired many-to-many pickup and delivery problem: an application ⋮ Efficiency considerations in the implementation of parallel branch-and- bound ⋮ Set-up saving schemes for printed circuit boards assembly ⋮ An integer programming application to solve sequencer mix problems in printed circuit board production ⋮ PARSSSE: AN ADAPTIVE PARALLEL STATE SPACE SEARCH ENGINE ⋮ An algorithm for the traveling salesman problem with pickup and delivery customers ⋮ An upper bound for the speedup of parallel best-bound branch-and-bound algorithms ⋮ Recursive branch and bound ⋮ A two-dimensional mapping for the traveling salesman problem ⋮ A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem ⋮ Ein lexikographischer Suchalgorithmus zur Lösung allgemeiner ganzzahliger Programmierungsaufgaben ⋮ Index Matrices as a Cost Optimization Tool of Resource Provisioning in Uncertain Cloud Computing Environment ⋮ Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm ⋮ One task of routing jobs in high radiation conditions ⋮ A model variant of the problem about radiation sources utilization (iterations based on optimization insertions) ⋮ Two-stage dynamic programming in the routing problem with decomposition ⋮ Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems ⋮ A 3/4 differential approximation algorithm for traveling salesman problem ⋮ Unnamed Item ⋮ Minimax routing problem with a system of priority tasks ⋮ On the Application of the Minimax Traveling Salesman Problem in Aviation Logistics ⋮ An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading ⋮ Optimizing multi-inserts in routing problems with constraints ⋮ On the question of the optimization of permutations in the problem with dynamic constraints ⋮ Bi-Objective Flow Shop Scheduling with Equipotential Parallel Machines ⋮ On one routing task with the optimization of the start-finish point ⋮ THE TRAVELING SALESMAN PROBLEM: APPROXIMATE ALGORITHM BY BRANCH-AND-BOUND METHOD WITH GUARANTEED PRECISION ⋮ To the question of optimization of the starting point in the routing problem with restrictions ⋮ Routing order pickers in a warehouse with a middle aisle ⋮ On the complexity of discrete programming problems ⋮ Auction-based approach to resolve the scheduling problem in the steel making process ⋮ Convergence rate of a simulated annealing algorithm with noisy observations ⋮ Solving a Routing Problem with the Aid of an Independent Computations Scheme ⋮ On one routing problem modeling movement in radiation fields ⋮ Оptimization of the Start Point in the Gtsp with the Precedence Conditions ⋮ Preventing redundant solutions in partial enumeration algorithms ⋮ ON ROUTING PROBLEM WITH STARTING POINT OPTIMIZATION ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exact Solution of Two Location Problems via Branch-and-Bound ⋮ Trivial integer programs unsolvable by branch-and-bound ⋮ Optimal expansion of an existing network