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

DOI10.1007/3-540-61310-2_24zbMath1415.90108OpenAlexW1562721326MaRDI QIDQ4645932

Egon Balas, Neil Simonetti

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

traveling salesman problemtime windowprecedence constraintgeneralized traveling salesman problemproblem instance

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Large multiple neighborhood search for the soft-clustered vehicle-routing problem, Large multiple neighborhood search for the clustered vehicle-routing problem, Construction heuristics for the asymmetric TSP., Solution of real-world postman problems, A survey of very large-scale neighborhood search techniques, TSP tour domination and Hamilton cycle decompositions of regular digraphs, Scheduling for multi-robot routing with blocking and enabling constraints, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number, Domination analysis of some heuristics for the traveling salesman problem

Cites Work

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