Graduate Thesis Or Dissertation
 

A multi-tour heuristic for the traveling salesman problem

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/1c18dj84d

Descriptions

Attribute NameValues
Creator
Abstract
  • This paper demonstrates the effectiveness of a heuristic for the Traveling Salesman Problem based purely on the efficient storage of multiple partial sub-tours. The heuristic is among the best available for the solution of large scale geometric Traveling Salesman Problems. Additionally, a version of the heuristic can be used to prove optimality of modest size problems (about 30 cities). The heuristic gives an alternative to the standard technique of backtracking and starting over, by using main memory for alternate paths. It gives insight into the magnitudes of sub-tour sizes in a tour generation process, and gives a potential "assist" heuristic, to be used along with a more standard method in reaching very large scale Traveling Salesman Problems.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details StarrRobertW1981.pdf 2017-08-17 Public Download