New classes of efficiently solvable generalized traveling salesman problems

DOI10.1023/A:1018939709890zbMATH Open0922.90138MaRDI QIDQ1290165FDOQ1290165

Publication date: 10 June 1999

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

Recommendations

Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study
scientific article; zbMATH DE number 34438
On Some Generalizations of the Travelling-Salesman Problem
scientific article; zbMATH DE number 1947373
Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood

linear time algorithms \(n\)-city traveling salesman neuristics price collecting TSP shortest source-sink path

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

Cited In (36)

New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP
Local search for string problems: brute-force is essentially optimal
Sequential and parallel local search for the time-constrained traveling salesman problem
Title not available (Why is that?)
Fast local search algorithms for the handicapped persons transportation problem
Solving the traveling circus problem by branch \& cut
On Some Generalizations of the Travelling-Salesman Problem
A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem
A general variable neighborhood search for the traveling salesman problem with time windows under various objectives
New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem
Implementation of a linear time algorithm for certain generalized traveling salesman problems
Single-machine scheduling with release times, deadlines, setup times, and rejection
A fresh look at the traveling salesman problem with a center
Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows
Large multiple neighborhood search for the clustered vehicle-routing problem
MIP modelling of changeovers in production planning and scheduling problems
Job shop scheduling with setup times, deadlines and precedence constraints
A beam search for the equality generalized symmetric traveling salesman problem
A heuristic for cumulative vehicle routing using column generation
The two-stripe symmetric circulant TSP is in P
Large multiple neighborhood search for the soft-clustered vehicle-routing problem
Solving the time dependent minimum tour duration and delivery man problems with dynamic discretization discovery
Scheduling for multi-robot routing with blocking and enabling constraints
A TSP (1,2) application arising in cable assembly shops
Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
Dynamic programming in the routing problem: decomposition variant
An exact algorithm with linear complexity for a problem of visiting megalopolises
An efficient implementation of local search algorithms for constrained routing problems
The multi-stripe travelling salesman problem
Title not available (Why is that?)
On solving travelling salesman problem with vertex requisitions
The parameterized complexity of local search for TSP, more refined
Title not available (Why is that?)
An Insert/Delete Heuristic for the Travelling Salesman Subset-Tour Problem with One Additional Constraint
New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization
A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane

This page was built for publication: New classes of efficiently solvable generalized traveling salesman problems

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