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 Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
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
Additional Information
  • description.provenance : Made available in DSpace on 2013-09-17T19:27:59Z (GMT). No. of bitstreams: 1 StarrRobertW1981.pdf: 348239 bytes, checksum: ad2b00848854887b7b4ce3d8d37ea567 (MD5) Previous issue date: 1980-07-11
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-08-30T21:03:39Z (GMT) No. of bitstreams: 1 StarrRobertW1981.pdf: 348239 bytes, checksum: ad2b00848854887b7b4ce3d8d37ea567 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-09-17T19:27:59Z (GMT) No. of bitstreams: 1 StarrRobertW1981.pdf: 348239 bytes, checksum: ad2b00848854887b7b4ce3d8d37ea567 (MD5)
  • description.provenance : Submitted by Sergio Trujillo (jstscanner@gmail.com) on 2013-08-29T18:15:46Z No. of bitstreams: 1 StarrRobertW1981.pdf: 348239 bytes, checksum: ad2b00848854887b7b4ce3d8d37ea567 (MD5)

Relationships

Parents:

This work has no parents.

In Collection:

Items