Assignment 2: Travelling Salesperson

Objectives

• to process command-line arguments
• to use strings
• to use arrays
• to use files
• to use a provided library

Introduction

The Travelling Salesperson Problem is the problem of, given a set of locations and the distances between every pair of them, determining the shortest tour that starts and ends at the same city and visits each other city exactly once. It is a very common problem in logistics: consider, for example, a delivery driver who needs to make stops at a list of 50 addresses and wants to minimize fuel use along the way.

Assignment

Write a program called TSP that calculates routes between cities by various methods. The file containing the cities and their locations and the methods to use to calculate the routes will be given as command-line arguments. For each method, the output should be the method used, the total distance, and the route.

The name of the file containing the cities and their geographic coordinates will be the first command-line argument. That file will contain the following (and nothing else): 1) on the first line, the number of cities in a format readable by atoi; 2) on the second line, a list of distinct three-character labels separated by single spaces (no label will contain a space or other whitespace character); 3) one line per city containing the latitude and longitude of the city in degrees in a format readable by atof and separated by a single space.

The methods to construct the tours (if any) will be given as the subsequent command-line arguments. They can contain any number of the following, in any order, and possibly with repeats. In all cases, distances should be calculated with the location_distance function in the location library that is provided as header and implementation files in /c/cs223/hw2/Required that you can compile and link with your code.

• -nearest, in which case the route should be calculated starting from the first city listed in the input file and proceeding to the closest remaining city by distance (with ties broken arbitrarily), then back to the first city.
• -insert followed by either nearest or farthest, in which case the route should be constructed by starting with a 2-city tour containing only the nearest or farthest pair of cities, then repeatedly selecting the nearest/farthest remaining city to any city already in the tour (minimize/maximize over all pairs of cities $(i, j)$ the distance from $i$ to $j$, where $i$ is a city not yet in the tour and $j$ is a city already in the tour). Once a city is selected, insert it at the point in the tour that minimizes the total length of the tour after that step. Break ties arbitrarily. Finally, reorder the tour so that it starts and ends at the first city in the input, and then reverse it if necessary so that the second city in the tour appears in the input before the penultimate city. (None of these reorderings will affect the real total length of the tour – DCA-CAK-ABE-ELH-BZN-DCA has the same length as ABE-CAK-DCA-BZN-ELH-ABE, and it is the latter that should be output, assuming that the cities were listed in the input file in alphabetical order. Because of the imprecision of floating point arithmetic, there may be differences of fractions of millimeters in the computed total lengths of the original tour and the one you output, but you should ignore those differences.)
• (Optional) -optimal, in which case the route should be calculated by finding the shortest route that starts at the first city, visits each other city exactly once, and then returns to the first city. As for -insert, reverse the tour if necessary so that the second city appears in the input file before the penultimate city. (If you do not complete this then simply output the tour in the order the cities appeared in the input.)

Output

When the input is valid, the output must be written to standard output and must consist of one line per method giving the method (including nearest or farthest for the -insert method), the total distance in kilometers to two places after the decimal point (as computed by summing the values returned by location_distance for each leg), and the route, starting with the first city in the input and ending with that city again.

Output for multiple methods must be given in the order the methods appeared on the command line. Each line of output must be followed by a single newline character; see the example for other spacing and punctuation. Methods can be repeated and in such cases the output for the repeats must appear in order according to their place on the command line. If no methods are given on the command line but the command-line arguments and input file are otherwise valid then there must be no output.

In addition, for certain invalid inputs, exactly one of the following error messages should be output to standard error followed by a single newline (and it does not matter what is written to standard output):

• TSP: missing filename when there are no command-line arguments;
• TSP: could not open FILENAME when there was an error opening the file whose name is given as the first command-line argument (replace FILENAME with the name of the file);
• TSP: too few cities when the number of cities given on the first line of the file is not at least two;
• TSP: invalid method METHOD when an argument after the first does not immediately follow -insert and is not one of -nearest, -insert, or -optimal (replace METHOD with the offending argument);
• TSP: invalid criterion CRITERION when -insert is followed by an argument that is neither nearest nor farthest (replace CRITERION with the offending argument); and
• TSP: missing criterion when -insert is the last argument.

When more than one error message is appropriate, output the one that applies first when considering the filename and format first, followed by the rest of the command-line arguments from first to last.

For other invalid input, your program must not crash or hang.

You may assume that the distances returned by a single call to location_distance will not exceed the longest possible distance on the largest rocky planet explored in person or robotically by humankind.

Testing

Distances of routes between airports (a convenient source of three-character labels for cities) can be checked at gcmap.com. Beware that the distances computed by gcmap may disagree with the expected values calculated from the input files because the databases may choose different points on airport property to represent the airports, and because of slight differences in the model of the surface of the Earth used.

Example

$ ./TSP 8_cities.in -nearest -insert nearest -insert farthest -optimal
-nearest        :  10067.11 SEA YVR MCI STL DAL IAH DCA BWI SEA
-insert nearest :   9320.21 SEA YVR MCI STL DCA BWI IAH DAL SEA
-insert farthest:   9306.22 SEA YVR MCI STL BWI DCA IAH DAL SEA
-optimal        :   9306.22 SEA YVR MCI STL BWI DCA IAH DAL SEA

Where the file 8_cities.in contains

8
SEA YVR MCI STL BWI DCA IAH DAL
47.450000 -122.311667
49.194722 -123.183889
39.297500 -94.713889
38.748611 -90.370000
39.175278 -76.668333
38.851944 -77.037778
29.984444 -95.341389
32.847222 -96.851667

Submissions

Submit your makefile, log file, and source code necessary to build the executable TSP using your makefile. Do not submit the provided location library. Your makefile should assume that they have been copied into the current directory but not that they are still in their original locations.