Programming Assignment #4

The Traveling Salesman Problem

The Program:

For this assignment, you will write a program in FORTRAN 95 to solve the Minimum Tour problem (aka the Traveling Salesman Problem). The problem may be described as follows: A salesman must leave his home city and visit N cities after which he then returns home. The order in which he visits the cities is unimportant, however he must visit each of the N cities, and he must start and end in his home city. Your task is to find the minimum tour, the shortest possible route from home base through N cities and back home again.

Your project will consist of a single source code file, p4.f95.

You will find the shortest route using the brute force method. You must sum the distance traveled for each possible route, retaining the shortest distance found as your answer. Thus, your program will have to generate all possible routes. This is an NP-complete problem with complexity O(n!). The algorithm to generate all possible routes is somewhat complex. A sample program to generate the permutations, written in pseudocode is provided for the permute subroutine to be written in FORTRAN 95. You may find it easier to digest the pseudocode program and write your own permute subroutine.

Input:

Your program will first prompt the user to enter a filename. This file name is a data file that conforms to the following specifications: The first line of the file is the number of cities, including home base. Following this count, data consists of a two dimensional ‘chart’ giving the distance (in miles) between each pair of cities. The home base city is always the first city listed in the file.

San Diego

Phoenix

Denver

Dallas

San Diego

0

350

950

1100

Phoenix

350

0

560

604

Denver

950

560

0

389

Dallas

1100

604

389

0

To make processing easier, there is only one item per line in the file. The above data would appear in the file this way:

4

SanDiego

0

350

950

1100

Phoenix

350

0

560

604

Denver

950

560

0

389

Dallas

1100

604

389

0

Output:

Your program must print the shortest route found, including the name of each city in the order visited, the distance traveled to get there, and the total number of miles traveled. Sample output from the above data file: DO NOT PRINT INTERMEDIATE DATA WITHIN THE PERMUTE FUNCTION! (The attached sample output for four cities is provided only to verify your function is working.)

Enter filename:

data.txt

San Diego to Phoenix — 350 miles

Phoenix to Dallas — 604 miles

Dallas to Denver — 389 miles

Denver to San Diego — 950 miles

Best distance is: 2293 miles