1. Homepage
  2. Programming
  3. MIE250: Fundamentals of object oriented programming - Project 5: Traveling salesman problem

MIE250: Fundamentals of object oriented programming - Project 5: Traveling salesman problem

Engage in a Conversation
TorontoMIE250Fundamentals of object oriented programmingTraveling salesman problemTSPJava

Project 5: Traveling salesman problem v3
CourseNana.COM

Contents CourseNana.COM

  1. 1  Overview 1 1.1 TSPasagraph............................................ 1 1.2 TSPsolutionpaths.......................................... 2 1.3 Loadinggraphs............................................ 2 CourseNana.COM

  2. 2  Program description 2 CourseNana.COM

  3. 3  Algorithm descriptions 3 3.1 Nearestneighbor(NN)heuristic .................................. 3 3.2 Nearestneighborfirst-last(NN-FL)heuristic ........................... 3 3.3 Nodeinsertion(NI)heuristic .................................... 3 CourseNana.COM

  4. 4  Menu options 3 CourseNana.COM

  5. 5  Error messages 4 CourseNana.COM

  6. 6  Required elements 4 6.1 Variables ............................................... 4 6.2 Classes................................................. 5 6.3 Functions ............................................... 8 CourseNana.COM

  7. 7  Helpful hints 8 CourseNana.COM

New concepts: Inheritance CourseNana.COM

1 Overview CourseNana.COM

This project builds upon the previous project, where a program was built to load and store many graphs and test solutions to the traveling salesman problem (TSP) using a simple nearest-neighbor heuristic. TSP is defined as follows. Say we have a set of cities that a traveling salesman needs to visit, and it takes a certain amount of time to travel between each city; what is the cheapest route to visit all cities exactly once? CourseNana.COM

The remainder of this section provides an overview of TSP from the previous project. CourseNana.COM

1.1 TSP as a graph CourseNana.COM

TSP is represented using a graph, where nodes are cities and undirected arcs between them indicate if it is possible to travel between two cities directly, and if so, the cost (distance). Each city (node) will contain the following information: CourseNana.COM

Name
latitude 2 [90, 90]
longitude 2 [180, 180] CourseNana.COM

The cost to travel from node i to node j is the distance between the two cities’ coordinates, calculated using the Haversine formula: CourseNana.COM

a = sin2 (x/2) + cos (xi) (xj ) sin2 (y/2) b = 2 atan2 pa, p1 a CourseNana.COM

cij =Rb CourseNana.COM

where
xi and xj are the latitudes of nodes i and j, respectively, in radians x is the latitude dierence in radians
y is the longitude dierence in radians
R = 6371, the diameter of Earth in km
atan2 is the Math.atan2() function CourseNana.COM

(Haversine Formula) CourseNana.COM

Costs are not input by the user; instead, they are calculated automatically by the program. Costs cij are stored in cost matrix C, where cij = 0 if nodes i and j are not connected. CourseNana.COM

An adjacency matrix is a common method to store arcs in a graph. An adjacency matrix A has size n n (where n is the number of nodes), and each element aij is 1 if nodes i and j are connected, and 0 otherwise. Similarly, C is the same as the adjacency matrix, but with costs cij instead of ones. Note that because arcs are undirected, A and C will always be symmetric. CourseNana.COM

1.2 TSP solution paths CourseNana.COM

A TSP solution path (formally called a Hamiltonian cycle) is a sequence of n + 1 nodes, satisfying the following requirements: CourseNana.COM

1. Start and end cities match
2. Sequential cities are connected by an arc
3. Cities (other than the home city, the first city in the path) are visited exactly once 4. All cities are visited
CourseNana.COM

1.3 Loading graphs CourseNana.COM

Graphs are read from text files, formatted as described in previous projects. Files may contain multiple graphs, and multiple files may be loaded by the user. CourseNana.COM

2 Program description CourseNana.COM

In this project, you will compare the performance of three dierent variations of the nearest neighbor heuristic to find TSP solutions: CourseNana.COM

Nearest neighbor (NN), exactly the heuristic you previously wrote Nearest neighbor first-last (NN-FL)
Node insertion (NI) CourseNana.COM

Your program will allow the user to load graphs, run all of the heuristics on all of the graphs, and then compare the performance of the heuristics to try to determine which algorithm performs best. Algorithm performance will be compared using three metrics: CourseNana.COM

1. Average cost of solution paths found
CourseNana.COM

2. Average computation time 3. Success rate CourseNana.COM

The performance comparison will not only be useful to indicate which algorithm you might want to use if you have to solve TSP in the future, but it will also illustrate how sensitive greedy heuristics can be, since the only dierence between the three algorithms is where the nearest neighbor is inserted into the TSP path. CourseNana.COM

3 Algorithm descriptions CourseNana.COM

As previously stated, each of the three algorithms is a variation of the same basic idea: Add the nearest neighbor to the existing path until the path is complete. After the last node is selected, the starting node is added to the end of the path. If at any time there is no valid node to add, or if there is no arc between the last node and the starting node, then the heuristic failed to find a TSP path. CourseNana.COM

Since the only dierence between the algorithms is where the nearest neighbor is put into the path, it makes sense to create a single basic algorithm class, and then have each algorithm inherit from that algorithm class, only changing the next node selection and insertion behavior. CourseNana.COM

3.1 Nearest neighbor (NN) heuristic CourseNana.COM

NN is a greedy algorithm that constructs a path by starting at node 1 (the home city) and adding the nearest neighbor to the last node in the path. CourseNana.COM

3.2 Nearest neighbor first-last (NN-FL) heuristic CourseNana.COM

NN-FL builds on NN by adding cheapest nearest neighbors to the beginning or end of the path. In each iteration, NN-FL checks the first node’s nearest neighbor (f) and the last node’s nearest neighbor (`), and adds whichever is cheaper. If arc (1,f) has a cheaper cost than arc (n,`), then node f is added to the front of the path. Otherwise, node ` is added to the end of the path. CourseNana.COM

3.3 Node insertion (NI) heuristic CourseNana.COM

NI builds on NN-FL by adding the cheapest nearest neighbor to any node in the path, not just the first or last node. There are three possible scenarios: CourseNana.COM

  • The first node has the cheapest nearest neighbor: Add the new node to the front of the path. CourseNana.COM

  • The last node has the cheapest nearest neighbor: Add the new node to the end of the path. CourseNana.COM

  • An internal node i has the cheapest nearest neighbor: Insert the new node after node i in the path, but only if an arc exists between the new node and the node that comes after node i. CourseNana.COM

    Note that if the new node already exists in the path, it cannot be inserted into the path. CourseNana.COM

4 CourseNana.COM

• • • • CourseNana.COM

Menu options CourseNana.COM

L - Load graphs from file

Read in graphs from a user-specified file. CourseNana.COM

I - Display graph info

Display summary info for each graph, and allow user to select graphs to see detailed info. CourseNana.COM

C - Clear all graphs

Clear all graphs. CourseNana.COM

R - Run nearest neighbor algorithm

D - Display algorithm performance
CourseNana.COM

Display algorithm performance for each graph, and provide a statistical summary. CourseNana.COM

X - Compare average algorithm performance

Compare the average performance of each algorithm variation on the three metrics (cost, computation time, success rate) and identify the best performer in each category and the overall best performer. Ties in best performance are broken in this order: NN, NN-FL, NI. CourseNana.COM

Q-Quit CourseNana.COM

Quit the program. CourseNana.COM

Error messages CourseNana.COM

ERROR: Invalid menu choice!

when the user enters an invalid menu choice. CourseNana.COM

ERROR: No graphs have been loaded!

when the user attempts to do anything with the graphs before graphs have been loaded. CourseNana.COM

ERROR: Results do not exist for all algorithms!

when the user attempts to display algorithm performance when all algorithms have not been run. CourseNana.COM

ERROR: File not found!

when the user enters a file name that is not found. CourseNana.COM

ERROR: <name> did not find a TSP route for Graph <i>! when the algorithm <name> fails to find a TSP route for Graph i. CourseNana.COM

ERROR: Input must be an integer in [<LB>, <UB>]!
where LB and UB are lower and upper bounds. If UB is equal to the maximum storable value of an int, then “infinity” is displayed instead of the actual UB value. Similarly, if LB is equal to the negative of the maximum storable value of an int, then “-infinity” is displayed instead of the actual LB value. CourseNana.COM

ERROR: Input must be a real number in [<LB>, <UB>]!
where LB and UB are lower and upper bounds. If UB is equal to the maximum storable value of a double, then “infinity” is displayed instead of the actual UB value. Similarly, if LB is equal to the negative of the maximum storable value of a double, then “-infinity” is displayed instead of the actual LB value. CourseNana.COM

Required elements CourseNana.COM

Your project must use the each of the elements described in this section. You can have more functions, variables, and objects if you want, but you must at least use the elements described in this section. CourseNana.COM

Failure to correctly implement any of the elements in this section may result in a zero on the project. CourseNana.COM

6.1 Variables CourseNana.COM

A single NNSolver object, as defined in Section 6.2
A single NNFLSolver object, as defined in Section 6.2
A single NISolver object, as defined in Section 6.2
A single ArrayList or array of Graph objects, as defined in Section 6.2 CourseNana.COM

Global public static BufferedReader as the only BufferedReader object in the entire program for reading user input CourseNana.COM

Although your programs will compile and run just fine on your own computer with multiple BufferedReader objects, they will not run correctly on a web server with multiple BufferedReader objects. Since your programs will be graded on a web server, please don’t have more than one BufferedReader for reading input from the console. CourseNana.COM

6.3 Functions CourseNana.COM

Function prototypes and short descriptions are provided below. It is your job to determine exactly what should happen inside each function, though it should be clear from the function and argument names and function descriptions. You can write more functions (and are strongly recommended to), but you must at least implement the functions defined in this section. CourseNana.COM

• • • • • • • • CourseNana.COM

CourseNana.COM

public static void displayMenu()

Display the menu. CourseNana.COM

public static boolean loadFile(ArrayList<Graph> G)

Read in graphs from a user-specified file. CourseNana.COM

public static void displayGraphs(ArrayList<Graph> G)

Display summary info for each graph, and allow user to select graphs to see detailed info. CourseNana.COM

public static void resetAll(NNSolver NN, NNFLSolver FL, NISolver NI)

Reset all solvers. CourseNana.COM

public static void runAll(ArrayList<Graph> G, NNSolver NN, NNFLSolver FL, NISolver NI)

Run all solvers on all graphs. CourseNana.COM

public static void printAll(NNSolver NN, NNFLSolver FL, NISolver NI)

Print the detailed results and statistics summaries for all algorithms. CourseNana.COM

public static void compare(NNSolver NN, NNFLSolver FL, NISolver NI)

Compare the performance of the algorithms and pick winners. CourseNana.COM

public static int getInteger(String prompt, int LB, int UB)

Get an integer in the range [LB, UB] from the user. Prompt the user repeatedly until a valid value is entered. CourseNana.COM

public static double getDouble(String prompt, double LB, double UB)

Get a real number in the range [LB, UB] from the user. Prompt the user repeatedly until a valid value is entered. CourseNana.COM

Helpful hints CourseNana.COM

All the hints from the previous project are still useful. CourseNana.COM

Get in Touch with Our Experts

QQ QQ
Wechat WeChat
Whatsapp Whatsapp
Toronto代写,MIE250代写,Fundamentals of object oriented programming代写,Traveling salesman problem代写,TSP代写,Java代写,Toronto代编,MIE250代编,Fundamentals of object oriented programming代编,Traveling salesman problem代编,TSP代编,Java代编,Toronto代考,MIE250代考,Fundamentals of object oriented programming代考,Traveling salesman problem代考,TSP代考,Java代考,Torontohelp,MIE250help,Fundamentals of object oriented programminghelp,Traveling salesman problemhelp,TSPhelp,Javahelp,Toronto作业代写,MIE250作业代写,Fundamentals of object oriented programming作业代写,Traveling salesman problem作业代写,TSP作业代写,Java作业代写,Toronto编程代写,MIE250编程代写,Fundamentals of object oriented programming编程代写,Traveling salesman problem编程代写,TSP编程代写,Java编程代写,Torontoprogramming help,MIE250programming help,Fundamentals of object oriented programmingprogramming help,Traveling salesman problemprogramming help,TSPprogramming help,Javaprogramming help,Torontoassignment help,MIE250assignment help,Fundamentals of object oriented programmingassignment help,Traveling salesman problemassignment help,TSPassignment help,Javaassignment help,Torontosolution,MIE250solution,Fundamentals of object oriented programmingsolution,Traveling salesman problemsolution,TSPsolution,Javasolution,