Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem

DOI10.1287/mnsc.26.7.736zbMath0445.90089OpenAlexW2140784080MaRDI QIDQ3890444

Paolo Toth, Giorgio Carpaneto

Publication date: 1980

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.26.7.736

zbMATH Keywords

computational resultsassignment problemasymmetric travelling salesman problemrandom problemsbreadth-first branch and bound algorithmcomputation of partial lower boundssubtour elimination approach

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05)

Related Items (49)

A heuristic solution to the warehouse location-routing problem ⋮ A shortest augmenting path algorithm for dense and sparse linear assignment problems ⋮ A lift-and-project cutting plane algorithm for mixed 0-1 programs ⋮ Darts and hoopla board design ⋮ DB2 and DB2A: Two useful tools for constructing Hamiltonian circuits ⋮ Generalized travelling salesman problem through n sets of nodes: The asymmetrical case ⋮ Vehicle routing with full loads ⋮ A survey of models and algorithms for winter road maintenance. IV: Vehicle routing and fleet sizing for plowing and snow disposal ⋮ Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs ⋮ Cluster analysis to minimize sequence dependent changeover times ⋮ An inexact algorithm for the sequential ordering problem ⋮ Discrete optimization in public rail transport ⋮ Modeling and solving several classes of arc routing problems as traveling salesman problems ⋮ Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem ⋮ A combinatorial column generation algorithm for the maximum stable set problem ⋮ A note on the complexity of the asymmetric traveling salesman problem ⋮ Incremental SAT-Based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem ⋮ On path ranking in time-dependent graphs ⋮ A study of complexity transitions on the asymmetric traveling salesman problem ⋮ Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems ⋮ Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots ⋮ Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times ⋮ On the stochastic complexity of the asymmetric traveling salesman problem ⋮ Infinite mixtures of infinite factor analysers ⋮ The pickup and delivery problem with time windows ⋮ An additive bounding procedure for the asymmetric travelling salesman problem ⋮ Travelling salesman problem tools for microcomputers ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems ⋮ An exact method for scheduling a yard crane ⋮ Tolerance-based branch and bound algorithms for the ATSP ⋮ Lower tolerance-based branch and bound algorithms for the ATSP ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ Iterative state-space reduction for flexible computation ⋮ Cluster based branching for the asymmetric traveling salesman problem ⋮ Block clustering with collapsed latent block models ⋮ Vehicle routing with stochastic demands and restricted failures ⋮ New edges not used in shortest tours of TSP ⋮ Algorithm for the solution of the assignment problem for sparse matrices ⋮ Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups ⋮ Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems ⋮ An enhanced lower bound for the time-dependent travelling salesman problem ⋮ A review of TSP based approaches for flowshop scheduling ⋮ New Imperialist Competitive Algorithm to solve the travelling salesman problem ⋮ An efficient genetic algorithm for the traveling salesman problem with precedence constraints ⋮ IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem ⋮ A Variable Neighborhood Search Algorithm for Cost-Balanced Travelling Salesman Problem ⋮ A useful transform of standard input data for a classical NP-complete problem ⋮ Methods for routing with time windows

This page was built for publication: Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem