A Group Theoretic Tabu Search Approach to the Traveling Salesman Problem [Spiral-bound]

Shane N. Hall (Author)

Available from these sellers.

Book Description

Publication Date: 2000

This is a AIR FORCE INST OF TECH WRIGHT-PATTERSONAFB OH SCHOOL OF ENGINEERING report procured by the Pentagon and made available for public release. It has been reproduced in the best form available to the Pentagon. It is not spiral-bound, but rather assembled with Velobinding in a soft, white linen cover. The Storming Media report number is A123873. The abstract provided by the Pentagon follows: The traveling salesman problem (TSP) is a combinatorial optimization problem that is mathematically modeled as a binary integer program. The TSP is a very important problem for the operations research academician and practitioner. This research demonstrates a Group Theoretic Tabu Search (GTTS) Java algorithm for the TSP. The tabu search metaheuristic continuously finds near-optimal solutions to the TSP under various different implementations. Algebraic group theory offers a more formal mathematical setting to study the TSP providing a theoretical foundation for describing tabu search. Specifically, this thesis uses the Symmetric Group on n letters, S(n), which is the set of all n! permutations on n letters whose binary operation is permutation multiplication, to describe the TSP solution space. Thus, the TSP is studied as a permutation problem rather than an integer program by applying the principles of group theory to define the tabu search move and neighborhood structure. The group theoretic concept of conjugation (an operation involving two group elements) simplifies the move definition as well as the intensification and diversification strategies. Conjugation in GTTS diversifies the search by allowing large rearrangement moves within a tour in a single move operation. Empirical results are presented along with the theoretical motivations for the research.

#outer_postBodyPS { display: none; } #psGradient { display: none; } #psPlaceHolder { display: none; } #psExpand { display: none; } This is a AIR FORCE INST OF TECH WRIGHT-PATTERSONAFB OH SCHOOL OF ENGINEERING report procured by the Pentagon and made available for public release. It has been reproduced in the best form available to the Pentagon. It is not spiral-bound, but rather assembled with Velobinding in a soft, white linen cover. The Storming Media report number is A123873. The abstract provided by the Pentagon follows: The traveling salesman problem (TSP) is a combinatorial optimization problem that is mathematically modeled as a binary integer program. The TSP is a very important problem for the operations research academician and practitioner. This research demonstrates a Group Theoretic Tabu Search (GTTS) Java algorithm for the TSP. The tabu search metaheuristic continuously finds near-optimal solutions to the TSP under various different implementations. Algebraic group theory offers a more formal mathematical setting to study the TSP providing a theoretical foundation for describing tabu search. Specifically, this thesis uses the Symmetric Group on n letters, S(n), which is the set of all n! permutations on n letters whose binary operation is permutation multiplication, to describe the TSP solution space. Thus, the TSP is studied as a permutation problem rather than an integer program by applying the principles of group theory to define the tabu search move and neighborhood structure. The group theoretic concept of conjugation (an operation involving two group elements) simplifies the move definition as well as the intensification and diversification strategies. Conjugation in GTTS diversifies the search by allowing large rearrangement moves within a tour in a single move operation. Empirical results are presented along with the theoretical motivations for the research.

Product Details

Spiral-bound: 108 pages
Publisher: Storming Media (2000)
Language: English
ISBN-10: 1423538196
ISBN-13: 978-1423538196
Amazon Best Sellers Rank: #9,128,467 in Books (See Top 100 in Books)

Would you like to update product info or give feedback on images?

Customer Reviews

There are no customer reviews yet.

Create your own review

Video reviews

Amazon now allows customers to upload product video reviews. Use a webcam or video camera to record and upload reviews to Amazon.

Tag this product

(What's this?)

Think of a tag as a keyword or label you consider is strongly related to this product.
Tags will help all customers organize and find favorite items.

Sell a Digital Version of This Book in the Kindle Store

If you are a publisher or author and hold the digital rights to a book, you can sell a digital version of it in our Kindle Store. Learn more

.jsOffDisplayBlock { display: block; } .jsOffDisplayInline { display: inline; } .jsOffVisibility { visibility: visible; } .jsOnDisplayBlock { display: none; } .jsOnDisplayNoneBlock { display: block; } .jsOnDisplayNoneInline { display: inline; } .jsOnDisplayInline { display: none; } .jsOnVisibility { visibility: hidden; } .jqOnDisplayBlock { display: none; } .jqOnDisplayInline { display: none; } .jqOnVisibility { visibility: hidden; } .jqOnDisplayNoneBlock { display: block; } .jqOnDisplayNoneInline { display: inline; }