Tracy Orton
Lan Tran

Meeting Name

1st Annual UMR Undergraduate Research Symposium (1991: Apr., Rolla, MO)

Abstract

A book published in Germany in 1852 said of the successful traveling salesman: "The most important aspect is to cover as many locations as possible without visiting the same location twice." This quote is the earliest mention of the "Traveling Salesman Problem" (TSP). There are many algorithms to solve the TSP, the one we implemented was the Branch and Bound algorithm. The TSP graph G is completely connected by a set of edges E, with a non-negative cost Cij associated with each edge. A tour of the graph is a cycle containing all vertices once and only once, starting and ending at the same vertex. A graph with N vertices has (N-l)! possible tours through the graph. A 50 city graph would require 1047 years to solve on a computer running at 109 additions per second.

The Branch and Bound algorithm consists of starting at a given vertex and calculating the cost of the edge from V to all of the other vertices in the graph. There are three main heuristics that describe how to choose the next vertex in the cycle, they are breadth-first, depth-first, and best-first? we implemented the best-first algorithm.

To implement the B&B algorithm in parallel, we used a distributed list, with and without load balancing. In the distributed list algorithm, the supervisor creates N initial nodes and sends them to the N workers, where N is the number of processors. Each worker has it own separate list. A worker expands the nodes from its list. It also puts the children back on the same list. When a worker finds a new best cost, it updates its best cost and broadcasts the new best to others. Each worker will stop when its list is empty. The algorithm terminates when all the workers have finished.

In the load balancing algorithm, we used the nearest neighbor method. The worker asks its nearest neighbors for work when it is finished. The neighbors then share their loads with the requester.

Our results were not quite what we had expected. The best speed up that we accomplished was 1.56 times when we increase the number of processors from 2 to 4. This is less than the ideal 2.0. in other cases, we did not achieve much speed up. When increasing the number of processors from 2 to 16, we only achieve 2.6 times speed up, which is much less than the expected 8.0.

Research Category

Improving Technology Through Computer Modeling

Document Type

Presentation

Award

1st Place

Presentation Date

April 1991

Comments

Title "Parallel Algorithms for the Traveling Salesman Problem" in the Table of Contents

Download

Share

COinS