A branch and bound algorithm for symmetric 2-peripatetic salesman problems

DOI10.1016/0377-2217(93)90041-KzbMath0799.90114OpenAlexW2086714760MaRDI QIDQ1310005

Jeroen B. J. M. De Kort

Publication date: 6 January 1994

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(93)90041-k

zbMATH Keywords

branch-and-boundsymmetric 2-peripatetic salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (17)

Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph ⋮ Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services ⋮ A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ Safe and secure vehicle routing: a survey on minimization of risk exposure ⋮ Lower and upper bounds for the \(m\)-peripatetic vehicle routing problem ⋮ An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution ⋮ Well-solved cases of the 2-peripatetic salesman problem ⋮ Probabilistic analysis of an approximation algorithm for the \(m\)-peripatetic salesman problem on random instances unbounded from above ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ The undirected \(m\)-capacitated peripatetic salesman problem ⋮ Branch-and-cut algorithms for the undirected \(m\)-Peripatetic Salesman Problem ⋮ A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem ⋮ The multiple shortest path problem with path deconfliction ⋮ Heuristiques pour le Problème du Vendeurm-Péripatétique ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP ⋮ Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2 ⋮ A polynomial algorithm with approximation ratio 2/3 for the Asymmetric Maximum 2-Peripatetic Salesman Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classification of travelling salesman problem formulations
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Bounds for the symmetric 2-peripatetic salesman problem
• A Method for Solving Traveling-Salesman Problems
• Computer Solutions of the Traveling Salesman Problem
• Branch-and-Bound Methods: A Survey
• Minimum partition of a matroid into independent subsets
• Lower bounds for symmetricK-peripatetic salesman problems

This page was built for publication: A branch and bound algorithm for symmetric 2-peripatetic salesman problems