Implementation of a linear time algorithm for certain generalized traveling salesman problems

DOI10.1007/3-540-61310-2_24MaRDI QIDQ4645932zbMATH OpenOpenAlexFDO

Authors Neil Simonetti, E. Balas

Publication date 11 January 2019

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61310-2_24

zbMATH Keywords

generalized traveling salesman problemprecedence constraintproblem instancetime windowtraveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints
• New classes of efficiently solvable generalized traveling salesman problems
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study
• Exact And Heuristic Procedures For The Traveling Salesman Problem With Precedence Constraints, Based On Dynamic Programming

Cites work

• A generalized insertion heuristic for the travelling salesman problem with time windows
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Local Search for the Asymmetric Traveling Salesman Problem
• New classes of efficiently solvable generalized traveling salesman problems
• Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem

Cited in

(16)

• A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Domination analysis of some heuristics for the traveling salesman problem
• Large multiple neighborhood search for the clustered vehicle-routing problem
• Solving the traveling salesman problem with time windows through dynamically generated time-expanded networks
• Scheduling for multi-robot routing with blocking and enabling constraints
• Simple algorithms for gilmore-gomory's traveling salesman and related problems
• Solution of real-world postman problems
• Large multiple neighborhood search for the soft-clustered vehicle-routing problem
• Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study
• scientific article; zbMATH DE number 1486639 (Why is no real title available?)
• Construction heuristics for the asymmetric TSP.
• TSP tour domination and Hamilton cycle decompositions of regular digraphs
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• A survey of very large-scale neighborhood search techniques

This page was built for publication: Implementation of a linear time algorithm for certain generalized traveling salesman problems

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