TRAVELING SALESMAN PROBLEM (TSP)

In section 13B of the textbook the traveling salesman problem is introduced.  The author states that the only known way to find the the best solution for the problem is to test all possibilities, an enormous task with as few as 50 cities.  In the textbook the Nearest Neighbor Method is offered as one way to find a nearly optimal solution for the traveling salesman problem.  At the site below two alternative techniques are suggested. Check out the web site and try the applet provided then complete the worksheet below.

     http://www.painsley.org.uk/mathsmirror/java/travel/travel.htm


TRAVELING SALESMAN PROBLEM

WORKSHEET

NAME__________________________________________

 Locate problem #20 in the text on page 728.

1. Use the data from the table to create a complete graph of order 5. (Draw graph below)
 
 
 
 
 
 
 

2. Apply the Nearest Neighbor Algorithm to the network 5 times (each time start at a different city), record and compare your results.

START/COST
AVILA (A) /
BARILA (B) /
CAMILLA (C) /
DORRITO (D) /
ELDORADO (E) /

How do these results confirm the fact that the nearest neighbor algorithm can not guarantee the optimal solution for the TSP?
 
 
 

3.  Apply the scheme used at the site above through five steps (your instructor can show you how this works) and fill in the table to show your progress.

The START column includes distances for the edges that we will include as we begin.

For each successive step do the following:
 i.) Select two random cities.
ii.) Interchange the two cities predecessors .
iii.) Calculate the new total distance (on scrap paper).
iv.) If you have saved mileage ( on chart, fill in distances for edges in the new circuit and new total distance) then go to i) to start the next step.  If you have not saved mileage go to i) and repeat the step.
v.) Stop after five steps or when you can no longer find improvement.

Example:  ( NOTE: IT WILL BE HELPFUL IF YOU DRAW THE CIRCUIT FOR EACH STEP ON SCRAP PAPER.)
 In STEP 1 the cities chosen randomly were A and B.  A, originally connected to E, now connects to C, while B, originally connected to C, now connects to E.  In STEP 2 - STEP 5 the cities chosen are listed in the last row of the table.
 

EDGE

DISTANCE

START

STEP 1

STEP 2

STEP 3

STEP 4

STEP 5

AB

12

12

12

*

*

*

*

AC

9

*

9

*

*

*

*

AD

5

*

*

*

*

*

*

AE

7

7

*

*

*

*

*

BC

10

10

*

*

*

*

*

BD

2

*

*

*

*

*

*

BE

6

*

6

*

*

*

*

CD

15

15

15

*

*

*

*

CE

8

*

*

*

*

*

*

DE

9

9

9

*

*

*

*

TOTAL

***********

53

51

*

*

*

*

CHANGE

***********

***********

-2

*

*

*

*

RND CITIES

***********

***********

AB

CD

BE

AD

DE

4.  Compare the results you found in the table with the Nearest Neighbor Method and the method used in #3 above.
 
 
 

5.  EXTRA:  On a separate sheet do an exhaustive search to find the optimal solution for this problem.