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 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 produces tours of cities by applying various heuristic algorithms. The hope is that the result of those heuristics is something reasonably close to the shortest possible tour, which is very time consuming to find. The name of the file containing the cities and their locations, and which algorithms to use to calculate the routes will be given as command-line arguments. For each algorithm, the program should output the algorithm used, the total distance of the resulting route, and the order of the cities in the route produced by the algorithm (see below for the exact format).

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, which will be no greater than 10000; 2) on the second line, a list of distinct three-character labels, one for each city, 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, where the latitude is between -90.0 and 90.0 (inclusive) and the longitude is between -180.0 (inclusive) and 180.0 (exclusive), and no two cities with have both the same latitude and the same longitude.

Which algorithms should be used 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.

• -given, in which case the route is created by starting at the first city in the input file and continuing with the cities in the order they appear in the file, and then returning to the first city.
• -farthest, in which case the route should be created by starting from the first city listed in the input file, putting the farthest of the other cities last in the tour (right before returning to the first city), the farthest city from that last city among those remaining as the second city in the tour, the farthest city from that second among the remaining cities as the next-to-last city, and so on until all the cities have been added to the tour. "Farthest" is based on the results of the location_distance function. Ties may be broken arbitrarily.

  Formally, we select a sequence of cities $c_1, ..., c_n$ where $n$ is the number of cities in the input file, $c_1$ is the first city in the input file, and for $1 \lt i \le n$, $c_i$ is farther from city $c_{i-1}$ than all the other cities $c_{i+1}, \ldots, c_n$ are from $c_{i-1}$. The resulting tour is then $c_1, c_3, c_5, \ldots, c_6, c_4, c_2, c_1$.

  For example, for input HVN PBI RSW TPA FLL MCO (and corresponding coordinates), RSW is farthest from HVN, MCO is farthest from RSW from among the remaining four cities, FLL is farthest from MCO from among the remaining three cities, TPA is farthest from FLL from among the remaining two cities, and PBI is the last city. The sequence of selected cities HVN RSW MCO FLL TPA PBI is then reordered into HVN MCO TPA PBI FLL RSW, with HVN added at the end to return the tour to its starting point.

• -exchange followed by either adjacent or any, in which case the route should be constructed by starting with the cities in the order they are given in the input file and switching the positions of two of the cities to produce the largest possible decrease in the total distance of the tour (which is always closed by returning to the city currently first in the ordering), and repeating until no reduction can be made by a single swap. Again, ties may be broken arbitrarily.

  Which pairs of cities to consider swapping is determined by the argument that follows -exchange: for adjacent, the algorithm only considers cities that are adjacent in the current ordering (with the last city considered adjacent to the first); for any, the algorithm considers any two cities.

  We want the output to start with the first city in the input. But both versions of the exchange algorithm may swap the first input city out of the first spot in the tour. However, where you start a closed tour doesn't affect the distance: if you start in the middle, proceed to the end, wrap around to the beginning, and proceed back to the middle, then the total distance will remain the same. So if the first input city has been swapped so it is not the first city in the tour, your program should output the tour starting from where the first input city ended up. For example, if HVN was the first city in the input and the final tour is PBI RSW TPA MCO HVN FLL PBI, then we reorder the tour to HVN FLL PBI RSW TPA MCO HVN. Furthermore, since a tour and its reverse have the same distance, we reverse the output when the second city in the computed tour appears in the input before the penultimate city (the one before returning to the starting point). So if MCO had appeared in the input before FLL then the final output would be HVN MCO TPA RSW PBI FLL HVN. (Only do these two reordering steps for the exchange algorithms.)

  To demonstrate the exchange algorithm when considering swaps only of adjacent cities, suppose the input is HVN RSW PBI TPA FLL MCO. Then, when considering swaps of adjacent cities, swapping TPA and FLL results in the largest decrease in total distance, leaving HVN RSW PBI FLL TPA MCO. In that list, swapping PBI and FLL gives the largest decrease, resulting in HVN RSW FLL PBI TPA MCO. Subsequent swaps of MCO and HVN, then TPA and HVN, then TPA and MCO results in TPA RSW FLL PBI HVN MCO. No swap of adjacent cities in that sequence results in a reduction in the distance. We adjust to start the tour at HVN since that was the first city in the input to get HVN MCO TPA RSW FLL PBI HVN, and then reverse the tour since MCO appeared in the input after PBI to get output HVN PBI FLL RSW TPA MCO HVN.

  When considering any pair of cities to swap, there are two possible sequences of swaps depending on how ties are broken: TPA/FLL, HVN/TPA, then PBI/FLL; or TPA/FLL, RSW/FLL, then FLL/PBI. Either way, after reordering, the result will be HVN PBI FLL RSW TPA MCO HVN (in general, the output of for -exchange adjacent will not be the same as the output for -exchange any).

Output

When the input is valid, the output must be written to standard output and must consist of one line per algorithm on the command line, where each line contains: 1) the algorithm (including adjacent or any for the -exchange algorithm); 2) the total distance in kilometers (as computed by summing the values returned by location_distance for each leg), rounded to the nearest hundredth of a kilometer and displayed with two digits after the decimal point even if the last one or both are zero, and right-justified so the decimal points line up in the same column as in the example shown below; and 3) the route, starting with the first city in the input and ending with that city again.

Output for multiple algorithms must be given in the order the algorithms 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. Algorithms 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 algorithms 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 (either invalid command-line arguments or invalid status or contents of the input file), 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 algorithm arguments for any problem with the command-line arguments aside from a missing filename (and the algorithm names should be considered case sensitive, so -FARTHEST would be considered invalid)

When more than one error message is appropriate, output the one that appears first in the list above. For other invalid input, your program must not crash or hang, but the output can be anything or nothing.

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.

Grading and Testing

Your program must not produce any errors when run with valgrind, regardless of whether the input is valid or not.

Some consideration will be given to time efficiency, with particuarly efficient implementations earning a few points more than typical implementations. Grossly inefficient but otherwise correct implementations may fail to complete in the time bounds enforced by the grading scripts and will incur more substantial penalties.

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 avelo_east.in -given -farthest -exchange adjacent -exchange any
-given            :      4490.78 HVN RSW PBI TPA FLL MCO HVN
-farthest         :      4089.15 HVN MCO TPA PBI FLL RSW HVN
-exchange adjacent:      3907.75 HVN PBI FLL RSW TPA MCO HVN
-exchange any     :      3907.75 HVN PBI FLL RSW TPA MCO HVN

Where the file avelo_east.in contains

6
HVN RSW PBI TPA FLL MCO
41.263889 -72.886944
26.536111 -81.755278
26.683056 -80.095556
27.975556 -82.533333
26.072500 -80.152778
28.429444 -81.308889

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 the files for the location library have been copied into the current directory; they may not still exist in their original locations when the final grading scripts run.