New classes of efficiently solvable generalized traveling salesman problems
From MaRDI portal
Publication:1290165
DOI10.1023/A:1018939709890zbMath0922.90138MaRDI QIDQ1290165
Publication date: 10 June 1999
Published in: Annals of Operations Research (Search for Journal in Brave)
linear time algorithms\(n\)-city traveling salesmanneuristicsprice collecting TSPshortest source-sink path
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items
Job shop scheduling with setup times, deadlines and precedence constraints, An exact algorithm with linear complexity for a problem of visiting megalopolises, Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows, The parameterized complexity of local search for TSP, more refined, 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, Dynamic programming in the routing problem: decomposition variant, New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem, A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane, A general variable neighborhood search for the traveling salesman problem with time windows under various objectives, The multi-stripe travelling salesman problem, Local search for string problems: brute-force is essentially optimal, New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP, Implementation of a linear time algorithm for certain generalized traveling salesman problems, Large multiple neighborhood search for the clustered vehicle-routing problem, A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem, Single-machine scheduling with release times, deadlines, setup times, and rejection, Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters, Scheduling for multi-robot routing with blocking and enabling constraints, MIP modelling of changeovers in production planning and scheduling problems, Fast local search algorithms for the handicapped persons transportation problem, A heuristic for cumulative vehicle routing using column generation
