New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization

DOI10.1016/S0166-218X(01)00271-2zbMath0996.90062OpenAlexW2059981036MaRDI QIDQ1602710

Santosh N. Kabadi

Publication date: 24 June 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00271-2

zbMATH Keywords

traveling salesman problemrural postman problemspecial caseminimum cost connected multi-digraph problemnode-deficiency requirementswallpaper cutting problemwarehouse order-picking problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Solution algorithms for synchronous flow shop problems with two dominating machines, A new asymmetric pyramidally solvable class of the traveling salesman problem, On Eulerian extensions and their application to no-wait flowshop scheduling, Traveling salesman games with the Monge property

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The unit capacity pickup and delivery problem on a one-way loop
• Gilmore-Gomory type traveling salesman problems
• Nonpreemptive Ensemble Motion Planning on a Tree
• Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem
• Combinatorial Optimization with Rational Objective Functions
• Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• Dynamic programming and the graphical traveling salesman problem
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• An Optimal Drum Scheduling Algorithm
• Polyhedral sets having a least element