Date of Award

3-21-2019

Document Type

Thesis

Degree Name

Master of Science in Operations Research

Department

Department of Operational Sciences

First Advisor

Bruce A. Cox, PhD

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.

AFIT Designator

AFIT-ENS-MS-19-M-127

DTIC Accession Number

AD1077397

Download

Share

COinS