Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Other Mathematics
Solving The Traveling Salesman Problem Using Ordered-Lists, Petar D. Jackovich
Solving The Traveling Salesman Problem Using Ordered-Lists, Petar D. Jackovich
Theses and Dissertations
The arc-greedy heuristic is a constructive heuristic utilized to build an initial, quality tour for the Traveling Salesman Problem (TSP). There are two known sub-tour elimination methodologies utilized to ensure the resulting tours are viable. This thesis introduces a third novel methodology, the Greedy Tracker (GT), and compares it to both known methodologies. Computational results are generated across multiple TSP instances. The results demonstrate the GT is the fastest method for instances below 400 nodes while Bentley's Multi-Fragment maintains a computational advantage for larger instances. A novel concept called Ordered-Lists is also introduced which enables TSP instances to be explored …