Solving the Traveling Salesman Problem Using Ordered Lists
Abstract
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 in a different space than the tour space and demonstrates some intriguing properties. While computationally more demanding than its tour space counterpart, the solution quality advantages, as well as a possibly higher proportion of optimal occurrences, when optimality is achievable via the ordered-list space, warrants further investigation of the space. Three meta-heuristics that leverage the ordered-list space are introduced. Testing results indicate that while at a severe iteration disadvantage, these methodologies benefit from using the ordered-list space which yields a higher per iteration improvement rate.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 21, 2019
- Accession Number
- AD1077397
Entities
People
- Peter D. Jackovich
Organizations
- Air Force Institute of Technology