A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem

DOI10.1287/OPRE.45.3.378zbMATH Open0893.90164OpenAlexW2018269848MaRDI QIDQ4367232FDOQ4367232

Paolo Toth, Matteo Fischetti, Juan-José Salazar-González

Publication date: 1 September 1998

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

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

Recommendations

• The symmetric generalized traveling salesman polytope
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A branch-and-cut algorithm for the generalized traveling salesman problem with time windows
• Generalized travelling salesman problem through n sets of nodes: The asymmetrical case
• Some Applications of the Generalized Travelling Salesman Problem

zbMATH Keywords

branch-and-cutpolytopeslocation-routingfacial structureinteger linear programsymmetric traveling salesmangeneralized traveling salesmanclustered notesheuristic separation procedures

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Cited In (only showing first 100 items - show all)

• The probabilistic orienteering problem
• The mixed capacitated general routing problem under uncertainty
• A two-stage vehicle routing model for large-scale bioterrorism emergencies
• Solving the Job Sequencing and Tool Switching Problem as a nonlinear least cost Hamiltonian cycle problem
• The generalized minimum edge-biconnected network problem: Efficient neighborhood structures for variable neighborhood search
• New mathematical models of the generalized vehicle routing problem and extensions
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• The generalized covering salesman problem
• A new class of cutting planes for the symmetric travelling salesman problem
• The production routing problem: a review of formulations and solution algorithms
• Layered graph approaches for combinatorial optimization problems
• Optimal capacitated ring trees
• An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem
• The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm
• The set orienteering problem
• Solving the family traveling salesman problem
• Efficient elementary and restricted non-elementary route pricing
• A heuristic procedure for the capacitated \(m\)-ring-star problem
• Particle swarm optimization-based algorithms for TSP and generalized TSP
• The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances
• An integer linear programming based heuristic for the capacitated \(m\)-ring-star problem
• Branch-and-cut algorithms for the undirected \(m\)-Peripatetic Salesman Problem
• Computational Evaluation Of A Transformation Procedure For The Symmetric Generalized Traveling Salesman Problem
• The clustered team orienteering problem
• Exact and heuristic algorithms for solving the generalized vehicle routing problem with flexible fleet size
• Integer programming models and branch-and-cut approaches to generalized \(\{0,1,2\}\)-survivable network design problems
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• Modeling and solving the mixed capacitated general routing problem
• A memetic algorithm for the generalized traveling salesman problem
• A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem
• Revisiting the Hamiltonian \(p\)-median problem: a new formulation on directed graphs and a branch-and-cut algorithm
• Eulerian location problems
• An improved hybrid ant-local search algorithm for the partition graph coloring problem
• A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem
• The traveling purchaser problem with stochastic prices: exact and approximate algorithms
• Transformations of generalized ATSP into ATSP.
• On the minimum corridor connection problem and other generalized geometric problems
• A pure proactive scheduling algorithm for multiple Earth observation satellites under uncertainties of clouds
• The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm
• A tabu search heuristic for the generalized minimum spanning tree problem
• Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem
• A branch-and-cut algorithm for the maximum covering cycle problem
• Solving a generalized traveling salesperson problem with stochastic customers
• An efficient transformation of the generalized vehicle routing problem
• The generalized fixed-charge network design problem
• Solving the asymmetric traveling purchaser problem
• Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm
• The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm
• A branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool
• Generalized network design problems.
• A random-key genetic algorithm for the generalized traveling salesman problem
• Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm
• A pattern recognition lexi search approach to generalized time-dependent travelling salesman problem
• Multiple depot ring star problem: a polyhedral study and an exact algorithm
• GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem
• Locating median cycles in networks
• A variable neighborhood search and its application to a ring star problem generalization
• Randomized gravitational emulation search algorithm for symmetric traveling salesman problem
• Facets of the \(p\)-cycle polytope
• Title not available (Why is that?)
• An integer programming-based local search for the covering salesman problem
• A new relaxation method for the generalized minimum spanning tree problem
• A biased random-key genetic algorithm for the set orienteering problem
• Liner shipping network design
• The capacitated arc routing problem with intermediate facilities
• An effective hybrid evolutionary algorithm for the clustered orienteering problem
• A comprehensive survey on the generalized traveling salesman problem
• The multicolored graph realization problem
• A branch-and-cut algorithm for the soft-clustered vehicle-routing problem
• Branch-and-bound for the precedence constrained generalized traveling salesman problem
• Shore hydrogen deployment problem in green ports
• A Sensitive Metaheuristic for Solving a Large Optimization Problem
• Variable neighborhood search for the set orienteering problem and its application to other orienteering problem variants
• Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout
• Exact solution of the soft-clustered vehicle-routing problem
• A two-level metaheuristic for the all colors shortest path problem
• A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem
• New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem
• A note on the generalized Steiner tree polytope
• Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
• Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
• Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem
• The generalized minimum branch vertices problem: properties and polyhedral analysis
• A Discrete State Transition Algorithm for Generalized Traveling Salesman Problem
• A granular iterated local search for the asymmetric single truck and trailer routing problem with satellite depots at DHL Group
• The cumulative school bus routing problem: Polynomial‐size formulations
• Mixed integer programming formulations for the generalized traveling salesman problem with time windows
• The undirected \(m\)-capacitated peripatetic salesman problem
• A branch-and-cut algorithm for the generalized traveling salesman problem with time windows
• A learn‐and‐construct framework for general mixed‐integer programming problems
• MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration
• Cluster-level operations planning for the out-of-position robotic arc-welding
• Large multiple neighborhood search for the clustered vehicle-routing problem
• An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search
• New path elimination constraints for multi-depot routing problems
• An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem
• Large multiple neighborhood search for the soft-clustered vehicle-routing problem
• On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms

Uses Software

• TSPLIB

This page was built for publication: A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4367232)