Advanced Algorithms for Solving Travelling Salesman Problem

• Advanced Algorithms for Solving Travelling Salesman Problem
  • 1 Introduction
  • 2 Compile, Run & Delete
    • 2.1 Compile
    • 2.2 Run
    • 2.3 Delete
  • 3 Project Structure
  • 4 Outcomes
    • 4.1 Solution File
    • 4.2 Trace File
  • 5 Possible Exceptions/Errors
    • 5.1 FileNotFoundException
  • 6 Team Members

1 Introduction

This project implemented four advanced algorithms to solve the famous NP-Problem Travelling Salesman Problem. The four advanced algorithms are:

• Branch and Bound
• Farthest Insertion
• Interated Local Search
• Simulated Annealing

2 Compile, Run & Delete

2.1 Compile

• Make sure all the java files and the DATA folder are in the same directory.
• Type "javac Main.java" in the command line to compile.

2.2 Run

• Type "java Main" in the command line to run the project.

2.3 Delete

• Type "make clean" in the command line to delete all the class files.

3 Project Structure

• Entry point -> Main.java
  • File handling
    • Read input file -> FileInput.java
    • Create city instances -> City.java
  • Implementing algorithm -> Algorithm.java
    • Brach & Bound algorithm -> BranchAndBound.java
    • Farthest Insertion algorithm -> FarthestInsert.java
    • Iterated Local Search algorithm -> Iteratedlocalsearch.java
    • Simulated Annealing algorithm -> SimulatedAnnealing.java
  • Unit test -> ProjectTest.java

4 Outcomes

Both the solution file and the trace file will be generated by the program. The filenames will include the name of the city to implement the algorithm, the abbreviation of the algorithm's name and the cut-off time.

4.1 Solution File

Solution file will include the resulting path of travelling each location exactly once in the city and the corresponding total distance travelled.

4.2 Trace File

Trace file will include the total distance calculated corresponding to the program running time.

5 Possible Exceptions/Errors

5.1 FileNotFoundException

• Reason: the DATA folder is not correctly put in the root directory of the project workspace.
• Solution: put the DATA folder in the root directory of the project workspace.

6 Team Members

Hezijian Xiao, Ruoyu Ji