Assignment 3: Travelling Salesperson

Objectives

• to process command-line arguments
• to use strings
• to use arrays
• to use a provided library
• to implement searching and sorting algorithms
• to use structs

Introduction

The Travelling Salesperson Problem is the problem of, given a list 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 methods to use to calculate the routes and the names (or other labels) of the cities will be given as command-line arguments. For each method, the output should be the method used, the total distance, and the route.

The methods given on the command line will be any number of the following, in any order, and possibly with repeats:

• -direction followed by either east or west, in which case the route should be calculated starting from the first city, and proceeding to the closest remaining city by longitude in the given direction (with longitudes of cities taken to be whatever is given in the provided database, and with ties broken north to south and then arbitrarily), then back to the first city;
• -nearest, in which case the route should be calculated starting from the first city and proceeding to the closest remaining city by distance as determined by the location_distance from the given location library from /c/cs223/hw3 (with ties broken arbitrarily), then back to the first city;
• (pick one) -insert, in which case the route should be determined by starting with a tour from the first city to the farthest city from it, then repeatedly inserting one of the remaining cities to minimize the length of the new tour without changing the order of the cities already in the tour (with ties broken arbitrarily); or
• (pick one) -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 (with ties broken arbitrarily).

Your solution must support at least one of the last two methods.

The names (or other labels) of the cities will be given as command-line arguments after the methods – the first command-line argument that does not begin with a hyphen and does not immediately follow -direction should be considered the first city name and everything after that should also be considered a city name . Each name will be given as a single argument, so New Haven would be a single command-line argument; you would have to quote New Haven on the command line so that it would be passed in as "New Haven" and not two separate arguments "New" and "Haven". The names on the command-line will be unique (that is, there will be no duplicates) and there will be at least two and no more than 1024 of them.

The locations of the cities will be given in the library cities (found in /c/cs223/hw3) which will define two global variables:

• int city_count which is the number of cities whose locations are defined in the libraries;
• city cities[] which is an array of city structures (defined in cities.h) giving the city names and locations, ordered according to the result of strcmp on the city names.

Do not make other assumptions about the contents of cities.c, as the definitions used for grading may differ from those used for testing. The declarations in cities.h will not change, although there may be new declarations added for grading as necessary.

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 east or west for the -direction method), the total distance in kilometers to two places after the decimal point (as computed by location_distance ), and the route, starting with the first city 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 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 then nothing should be written to standard output):

• TSP: invalid method METHOD when an argument before the list of cities begins with a hyphen, does not immediately follow -direction and is not one of -direction, -nearest, -insert, or -optimal (replace METHOD with the offending argument);
• TSP: invalid direction DIRECTION when -direction is followed by an argument that is neither east nor west (replace DIRECTION with the offending argument);
• TSP: missing direction when there is no list of cities and -direction is the last argument;
• TSP: too few cities when there are not at least two cities given after the methods;
• TSP: unknown city CITY when an argument following the methods is not the name of a city in the name field of the structs in the cities array (replace CITY with the offending argument);
• TSP: unsupported method METHOD for the corresponding method if you did not support one of the last two (replace METHOD with the offending argument).

When more than one error message is appropriate, output the one that applies first when considering the command-line arguments from first to last, with "too few cities" considered after the last method and before the first city.

For other invalid input, your program must not crash or hang. Your program will not be tested on invalid cities databases (and think about the extent to which you could test the validity of that data).

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

It may be helpful to know for testing that one degree of longitude is about 111.32km at the equator and about 85.39km at 40 degrees latitude. The cities library used for testing contains locations of many airports, and distances of routes between airports can be checked at gcmap.com.

Example

$ ./TSP -direction east -direction west -nearest -insert -optimal BWI HER JNB DAC CNS
-direction east: 46753.53 BWI HER JNB DAC CNS BWI
-direction west: 46753.53 BWI CNS DAC JNB HER BWI
-nearest       : 47149.47 BWI HER DAC CNS JNB BWI
-insert        : 46753.53 BWI HER JNB DAC CNS BWI
-optimal       : 46753.53 BWI HER JNB DAC CNS BWI

Submissions

Submit your makefile, log file, and source code necessary to build the executable TSP using your makefile. Do not submit the provided libraries cities and location. Your makefile should assume that they have been copied into the current directory.