/TS-OI

Experimental project solving Travelling Salesman Problem via genetic algorithm, hungarian method, etc. University project for class Operations Research.

Primary LanguagePython

Traveling Salesman Problem

This repository contains a Python implementation of several algorithms to solve the Traveling Salesman Problem (TSP).

Problem Description

The Traveling Salesman Problem is a classic problem in computer science and optimization. Given a list of cities and the distances between each pair of cities, the problem is to find the shortest possible route that visits each city exactly once and returns to the starting city.

Algorithms

This project implements the following algorithms to solve the TSP:

  • Brute Force Algorithm
  • Nearest Neighbor Algorithm
  • Hungarian Algorithm
  • Genetic Algorithm
  • Branch and Bound Algorithm

Each algorithm is implemented as a separate Python module.

Usage

To use the algorithms, simply run the <algorithm_name>.py script. Functions within each algorithm's python file can be imported and used with custom matrices that represent a travelling salesman problem.

Requirements

This project requires Python 3.8+ and the following package:

  • NumPy