A MODIFIED VERSION OF THE METRIC TSP PROBLEM

This project solves a metric TSP problem on incomplete graphs with approximation factor of 2.0 (usually better empirically), by deploying an MST based approach.

• Link to project spec: - read section "Problem Statement" before importing

Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.

Type

git clone https://github.com/StefStroke/Metric-Travelling-Sellsman-Solver.git

in your local repository. Then you should have the project source code fully clone on your computer. There is no starter branch, and no unauthorized contributers can change the remote branch.

Prerequisites

Interpreter you need to deploy

Python 3.7.0 or higher

Packages and libraries you need to install

pip/pip3
Python 3.7.0 or higher
NetworkX 2.4 or higher
HeapDict 1.0.1 or higher
Numpy 1.17.4 or higher
Decorator 4.4.1. or higher

The below instructions are narrated in terms of PyCharm CE 2019.1.3 functionalities. So it would only make sense if you have

PyCharm 2019.1.3 (Community Edition)

installed on your local machine, or its professional counterpart.

Running the tests

The "meat" of our solver is in solver.py file, prims.py file, and graph.py file.

Whereas generator.py is primarily concerned with generating input files located in inputs/, specifically

inputs/325_50.in
inputs/325_100.in
inputs/325_200.in

is generated by this file

So to run the tests, first open the project with PyCharm, then go to "Edit Configuration" tag in "Run" drop down on top of the interface. In text box "Name:_____", type in as below:

Name: solver
     --------

and in text box Parameters:______" type in as below

Parameters: --all inputs outputs
          --------------------------

To run it on the command line directly, type

python solver.py --all inputs outputs
          --------------------------

As a result, the program will run all .in files in inputs/ directory and put corresponding results in outputs/ directory in .out format by executing the main function in solver.py.

You can then run output_validator.py to validate the result and it will print out the driving cost and walking cost respectively

To this point, you should be able to interpret the data in outputs/ freely

Authors

• Jinting Li - StefStroke

• Boyuan Ma - jerrymby

See also the list of contributors - CS170 UC Berkeley Course Stuff and instrcutors