sebastianlay/tod-eines-handlungsreisenden

An implementation of the Held-Karp algorithm for solving the travelling salesman problem

Tod eines Handlungsreisenden

This is a C# implementation of the Held-Karp algorithm for solving the travelling salesman problem as part of the get int {IT} coding challenge.

Installation

Windows

• Download and install the .NET Core 3.1 Runtime
• Download the Windows version of the application from the releases and extract the content

Linux

• Download and install the .NET Core 3.1 Runtime
• Download the Linux version of the application from the releases and extract the content

Usage

• Open a console or PowerShell and navigate to the folder with the extracted application
• Run the application with the following optional arguments:

tod-eines-handlungsreisenden:
  A program to solve the travelling salesman problem

Usage:
  tod-eines-handlungsreisenden [options]

Options:
  --filepath <filepath>    Path to the CSV file containing the sites [default: msg_standorte_deutschland.csv]
  --brute-force            Use a brute force approach instead of the Held-Karp algorithm [default: False]
  --version                Show version information
  -?, -h, --help           Show help and usage information

Credits

This application uses the following libraries:

• CsvHelper for reading and mapping the content of a CSV file
• BAMCIS GeoCoordinate for calculating the distance between two locations
• System.CommandLine.DragonFruit for parsing the command line arguments

Solution

The Held-Karp algorithm is an obvious choice for this problem since it is way faster than brute forcing and guarantees to get the optimal solution. The solution for this particular CSV file can be found in a separate file.