Operations Research, Systems Engineering and Industrial Engineering Commons^™

Comparing Greedy Constructive Heuristic Subtour Elimination Methods For The Traveling Salesman Problem, Petar Jackovich, Bruce A. Cox, Raymond R. Hill

Faculty Publications

Purpose — This paper aims to define the class of fragment constructive heuristics used to compute feasible solutions for the traveling salesman problem (TSP) into edge-greedy and vertex-greedy subclasses. As these subclasses of heuristics can create subtours, two known methodologies for subtour elimination on symmetric instances are reviewed and are expanded to cover asymmetric problem instances. This paper introduces a third novel subtour elimination methodology, the greedy tracker (GT), and compares it to both known methodologies. Design/methodology/approach — Computational results for all three subtour elimination methodologies are generated across 17 symmetric instances ranging in size from 29 vertices to 5,934 …