Software Requirements Specification for TSPSoft

Version 1.4

Company: TSPSoft of the University of Washington, Tacoma

System under Development: TSPSoft

Development Team Members: (removed by JT)

Table of Contents

1.0 Purpose & Scope:

1.1 Purpose:

The software requirements specification will give and overview of requirements and functionality of the System under Development(SuD) also to be called "TSPSoft". Both the terms SuD and TSPSoft will be used interchangeably throughout this document. The audience to be addressed are the clients /users who are interested in solving Traveling Salesman Problems (TSP) to find optimal tours.

1.2 Scope:

The overall scope and goal of the System under Development (SuD) is to implement a Java application that solves the symmetric TSP. The solutions by the SuD for the TSP will be derived by implementing three different algorithms including Greedy, Double Minimum Spanning Tree (Double MST), and 2-OPT using either Double MST or Greedy for the starting tour. The application allows two modes of operation, animation and computation mode. The computational mode will have various options that the user of the SuD will supply at the command-line to solve TSP. Those options define an input file, an output file, an algorithm, and a graphical display. The animation mode will also give the user different options but in the Graphical User Interface(GUI) and the SuD will generate nodes randomly based on the number of nodes specified by the user to execute the chosen algorithm. In both cases, the system will be able to display the final tour result both graphically and numerically. The application will run on a Java enabled computer with sufficient memory to store and execute the application.

2.0 Text Description:

The main functionality of the SuD is to provide the user with a Java application that will produce an optimal tour by solving TSP, implementing three algorithms: Greedy, Double Minimum Spanning Tree (Double MST) and 2-OPT. The user will select one of these three algorithms to solve symmetric Traveling Salesman Problems and each algorithm will be discussed briefly later in this section. The understood user will have the knowledge similar to a student at the level of completion of TCSS 343.

The TSP can be described as follows:

Find a path through a weighted graph which starts and ends at the same vertex, includes every other vertex exactly once, and minimizes the total cost of edges.[1]

Another helpful definition:

The traveling salesman problem, or TSP for short, is this: given a finite number of 'cities' along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. [2]

Although there are many variations of TSP, the SuD will strictly address the symmetric TSP. The word symmetric in regards to TSP implies that the cost for city A to city B is the same as it is from city B to city A. Ahead are brief descriptions of the algorithms to be implemented in the SuD.

The first algorithm Greedy, is based upon Kruskal's algorithm and gives a suboptimal solutions on a completed graph, a graph being nodes (cities) connected by edges(paths/routes). The process of the Greedy algorithm is to sort edges weights from cheapest to most expensive and then selecting the next cheapest edge as long as two rules are not violated. The two rules are:

1. It does not cause a nodes to have a degree more than two.
2. It does not complete a cycle unless the number of edges is equal to the number of nodes.

As stated before, greedy algorithms in some problems do not produce optimal solutions and often produce suboptimal solutions. However, using the Greedy algorithm in the SuD, the user can compare the resulting tour with the results of Double MST and 2-OPT algorithms.

The second algorithm is the Double Minimum Spanning Tree(Double MST) algorithm will produce a resulting tour that is no more than two times the optimal tour and is described as follows:

Double Minimum Spanning Tree (Double MST). Construct a multigraph consisting of two copies of a minimum spanning tree for the cities. This graph must have an Eulerian cycle, i.e., a (not necessarily simple) cycle that includes every edge exactly once. Construct one and convert it into a Hamiltonian cycle by taking shortcuts to avoid visiting cities more than once. [3]

Thirdly, the 2-OPT algorithm introduces the concept of "local optimization" to attempt to improve the tours done with the above algorithms. This algorithm produces a locally optimal solution and is not needed to be globally optimal with the TSP tour. The 2-OPT can execute the subroutine of eliminating and reconnecting either by random or deterministic means here is a more detailed explanation of the subroutine:

A 2-opt move consists of eliminating two edges and reconnecting the two resulting paths in a different way to obtain a new tour. There is only one way to reconnect the paths that yield a different tour. Among all pairs of edges whose 2-opt exchange decreases the length we choose the pair that gives the shortest tour. This procedure is then iterated until no such pair of edges is found. The resulting tour is called 2-optimal. [4]

The above algorithms will provide the user choices to run some known optimal TSP solutions and to solve random TSP in the SuD. Below will describe the TSPSoft's approach to present the user with two different types of system interfaces to execute those algorithms.

The SuD will provide the user with two modes of operation, which are the computation mode and animation mode. The user will initiate the TSPSoft wiht a set of command-line arguments that will be explained in the user's manual and below in the Data Dictionary and Validation (Section 5). These arguments will specify what flags the user will set before the program starts up. The first flag will determine the mode being either computation or animation (the first flag is optional - if the user specifies no flag, the default will be executed). The second flag will tell the application if there is an input file to be loaded and which input file to be used ( i.e. source path or if no flag is provided the default file will be loaded). The third flag will be the name of the output file from the resulting tour when the algorithm completes. If user does not set the flag, the TSPSoft will create the default output file. The fourth flag will specify which algorithm will be run on the input file. Finally, the fifth flag will allow the computation mode to display the processed data in graphical manner similar to animation mode's "run" option. Flags from the second to fifth will exclusively define the computation mode. If the user specifies no flags at the command-line, the application will automatically enter the animation mode. Also, if user does not properly enter the collect syntax of these arguments, the SuD will display the error-handling prompts to inform the user what he or she has done wrong.

The computation mode will run without any user interaction after the command-line arguments have been set by the user. The both input and output file of the TSP will be standard forms of the TSPLIB. Briefly describing, these files specify the number of nodes and the Euclidean geometry coordinates in the NODE_COORD_SECTION format of the TSPLIB( node, x-coordinate, y-coordinate). Using this format the SuD will implement the user selected algorithm(Greedy, Double MST or 2-OPT) to produce a solution and return the result in an output file. The output file will give the resulting tour length and tour path in the standard TSPLIB form. This form is described as the TOUR_SECTION in the TSPLIB as a list of integers given in a sequence to show which node number to start at and continue to the next node until the end of the tour.(Please see Section 5.0 for greater details of the TSP file format). The user will be able to create an input file at their discretion using a external text editor. The computation mode will provide an option to the users who have a understanding of scripting to run large sets of data through the SuD for a period time. The termination of the SuD will happen after the SuD has processed and finished the algorithm. For the computation mode, the SuD exits automatically after the completion, while the animation mode will give the user a control to either continue or exit.

In animation mode the SuD will present the user the GUI that will give the user options to execute the random TSPs. The user will determine the number of nodes in the range of from 10-25 in integers. The user also will select one of three algorithms (Greedy, Double MST or 2-OPT) to run on the random TSP. The GUI will display a screen with the nodes in their randomly generated positions and the SuD will give the user the option to either "step" through the chosen algorithm systematically or "run" the algorithm with no further interaction. In both options, the user will see the edges drawn between nodes (iteratively or consecutively) on the display screen as the algorithm proceeds the execution on the random TSP. Also, the SuD will have the options to completely "start over" at any given time and generate another random TSP or "exit" the program. The operation of this mode should be intuitive and simple to use and will be designed to provide the user with fail-safe options to limit the error occurrence.

3.0 Glossary & Terms Used

4.0 Use Case Models

   1. See Use Case Number 1
   2. See Use Case Number 2

 

Use Case Number 1 (Animation Mode)

Use Case Name: Find an optimal tour using the animation mode.

Context of use: A user finds one or more optimal tour using the animation mode of TSPSoft.
Software Product Name: TSPSoft
Primary Actor: User
Precondition: User has an access to a java enabled computer system.
Trigger: User opens TSPSoft with a command-line argument.

Main Success Scenario:
1. User opens software with command-line argument of animation mode option.
2. TSPSoft displays the main screen.
3. User chooses number of nodes.
4. User chooses 1 of 3 algorithms to carry out the execution.
5. TSPSoft randomly chooses position of nodes.
Steps 6 - 7 repeat until the algorithm finishes or user chooses a different option
6. User selects a "step" option.
7. TSPSoft displays the step.
8. TSPSoft displays a graphic of the optimal tour.
9. User terminates TSPSoft.
10. TSPSoft exits.

Extensions:
1a. User enters invalid argument.
   1a1. TSPSoft prompts user with "invalid argument".
   1a2. TSPSoft returns user to command-line prompt.
   1a3. Continue at 1 above.
2a. User enters incorrect number of nodes.
   2a1. TSPSoft prompts user to enter valid number of nodes 10-25.
   2a2. User enters a valid number of nodes.
   2a3. Continue at 3 above.
3a. User enters incorrect algorithm.
   3a1. TSPSoft prompts user to enter valid algorithm.
   3a2 User enters a valid algorithm.
   3a3. Continue at 4 above.
6a. User selects "run" option.
   6a1. TSPSoft executes algorithm to completion without user interaction
   6a2. Continue at 6 above.
6b. User selects "start over" option.
   6b1. Continue at 5 above.
9a. User continues TSPSoft program.
   9a1. Continue at 2.

Use Case Number 2(Computation Mode)

Use Case Name: Find an optimal tour using the computation mode
Context of use: A user finds one or more optimal tour using the computation mode of TSPSoft, specifying all possible command flag options except graphic option.
Software Product Name: TSPSoft
Primary Actor: User
Precondition: User has an access to a java enabled computer system. In addition, the input file exists.
Trigger: User opens TSPSoft with a command-line argument.

Main Success Scenario:
1. User opens software with command-line argument of computation mode option.
2. TSPSoft executes the algorithm.
3. TSPSoft outputs the tour results to the specified output file.
4. TSPSoft exits.

Extensions:
1a. User enters invalid argument
   1a1. TSPSoft prompts user with "invalid argument".
   1a2. TSPSoft returns user to command-line prompt.
   1a3. Continue at 1 above.
1b. User enters an invalid input file name.
   1b1. TSPSoft prompts user with "file not found".
   1b2. TSPSoft exits.
1c. User does not specify an input file name.
   1c1. TSPSoft uses the default input file.
   1c2. Continue at 2 above.
1d. User does not specify an output file name.
   1d1. TSPSoft executes the algorithm.
   1d2 TSPSoft outputs the tour results to standard output.
   1d3. Continue at 4 above.
1e. User does not specify an algorithm.
   1e1. TSPSoft uses the default algorithm.
   1e2. Continue at 2 above.
3a. Use chooses graphic option at the command-line argument
   3a1. TSPSoft displays a graphic of the optimal tour.
   3a2. Continue at 4 above.

5.0 Data Dictionary and Validations

1. See Data Object Table
2. See Command-line Specifications
3. See Command-line Argument Specifications

The user chooses if the program runs in animation mode or computation mode by providing the command-line flag (see table 5.2). If the user provides -a or no argument (default), the program runs in the animation mode. In the animation mode, the program displays GUI for user to specify the algorithm and number of nodes. The choice of algorithm is Greedy, Double MST, and 2-OPT where the number of nodes ranges from 10 to 25. The user goes to the computation mode by selecting -c for the command-line argument along with the -i [input filename], -o [output filename], and -1, -2, or -3 for each algorithm (see table 5.2). The user also has an option to display the result tour graphically. If user does not specify the input, output file names and/or algorithm, the program uses the default file for input file and the standard output for displaying the output, and greedy algorithm as default algorithm.

On the graphical display of an optimal tour, besides the graphical presentation of the tour the program displays the optimal tour length, algorithm used, time it took to find the tour, and number of nodes of the tour. In addition, the program indicates whether it found the optimum tour or not, and the current state whether it finished or not.

If the user provides the input filename for the computation mode, the program uses the file to execute the chosen algorithm. The user can use the existing input file whose extension is .tsp and format is what TSPLIB specifies in the TSPLIB 95 (see under "Description" on the web site). Alternatively, the user can create an input file using the same extension and format. When the user creates own input file, (s)he must include the six fields specified in TSPLIB guideline, which are NAME, COMMENT, TYPE, DIMENSION, EDGE-WEIGHT-TYPE, and NODE_COORD-SECTION. The TYPE field always has to be "TSP" since TSPSoft is a program to solve specifically Symmetric Traveling Salesman problem. The DIMENSION is the number of nudes to solve the TSP. For the EDGE-WEIGHT-TYPE, the program is capable just for EUC_2D although TSPLIB defines more types. The program allows only integer for all of the values in the NODE_COORD-SECTION, and it should contain the actual data with the format of: <node> <x-coordinate> <y-coordinate>.

The program displays the output again according to the TSPLIB guideline, TSPLIB 95 regardless either displaying on a file or to a standard output (default). The fields that program uses are NAME, COMMENT, TYPE, DIMENSION, and TOUR_SECTION. The format of all fields except COMMENT and TOUR_SECTION should be the same as that of the input file. The COMMENT field indicates the optimal tour (if found), where the TOUR_SECTION shows the nodes of optimal tour. The tour termination in the TOUR_SECTION is indicated by a -1.

5.1 Data Object Table

Command-line Flag Specification Table

To run the program with animation mode:

1. prompt: java TSPSoft [-a]

or

2. prompt: java TSPSoft

To run the program with computation mode:

prompt: java TSPSoft [-c] [-i][input_filename] [-o][output_fileneme] [-1, -2, -3] [-g] *

*note that [] means option.

6.0 Non-functional Requirements

6.1 Security and Access

The SuD is accessible to any user as long as the operating system allows the user to access the TSPSoft files and the Java SDK. The SuD contains no user, application, or operating system level security of its own. However, user can access to the application both locally and remotely.

6.2 Users and Usability

The user must have familiarity with a command-line interface on either DOS or UNIX, and a Graphical User Interface (GUI) similar to that of Microsoft Windows or X Windows. The user needs to know how to execute the application and how to pass parameters using a command-line interface. The user also needs to know how to use the mouse to make option box selections, menu selections, manipulate windows, and other essential GUI operations. The SuD contains no ADA (Americans with Disabilities Act) features and assumes user interaction with a US 101-keyboard and a PS2, serial, or USB mouse. However, the SuD may or may not function on systems that have proprietary input devices such as touch screens, voice activation, and etc.

7.0 The Technology Used

7.1 Technology Requirements

The main technology requirement on the system is the ability to execute a Java SDK 1.3 application. This encompasses all hardware and software systems that contains a Java interpreter that can execute Java SDK 1.3 bytecode. The system must have sufficient memory to store and execute the application, including input files, output files, data structures, and other application related overhead.

The SuD interfaces with no other server, service, device, or application. The SuD is a standalone application running locally on a single computer system.

8.0 References

1. http://www.nist.gov/dads/HTML/travelingSalesman.html

2. http://www.math.princeton.edu/tsp

3.http://www.research.att.com/~dsj/papers/stspchap.ps

4.http://odysseus.nat.uni-magdeburg.de/~mertens/TSP

Course Reading,"Local Optimization and the Traveling Salesman Problem" Johnson, David- Murray Hill, NJ

Data Structures and Algorithms in Java, 2nd Edition. Goodrich, Michael and Tamassia, Roberto. John Wiley & Sons, INC

Change Log

• January 24, 2002. Version 1.5 - Final edits, modified HTML codes, fixed links and format, and prepared for final turn-in by X.
• January 24, 2002. Version 1.4 - Final edits, added links and prepared for final turn-in by Y.
• January 24, 2002. Version 1.3 - HTML code and sections modified (changed to proper tags) by Z.
• January 24, 2002. Version 1.2 - Glossary added and text description modified by X.
• January 23, 2002. Version 1.1 - Text description modified by X.
• January 23, 2002. Version 1.0 - Original Version done by Y, X.