0

I am trying to calculate Hamiltonian paths, paths that visit every node in a graph once, by a range of desired total costs or total edge lengths. There are various algorithms for the Traveling Salesman problem that calculate the shortest path, but I have not come across a solution that does so by desired total cost.

As a result I resorted to a brute-force solution that works for a few nodes, but is impossible to calculate for the 50 nodes I have.

import itertools
import numpy as np
from numpy import std

dist_matrix = np.array([[0.0,484.5434935135364,632.0078925008858,735.0398352819755,493.16148400859885],[484.5434935135364,0.0,425.69916384832044,525.3371082385308,322.51794796977657],[632.0078925008858,425.69916384832044,0.0,109.91947970385735,143.67555771554203],[735.0398352819755,525.3371082385308,109.91947970385735,0.0,252.8369873480788],[493.16148400859885,322.51794796977657,143.67555771554203,252.8369873480788,0.0]])

size=len(dist_matrix)
tours = []

for tour in itertools.permutations(list(range(0,size))):
    distances = [dist_matrix[i][j] for i, j in list(zip(tour, tour[1:]))]
    length = sum(distances)
    tours.append([tour, distances, length, std(distances)])

Note that I also return the standard deviation so I can filter by the desired tour length and lowest standard deviation (to get somewhat equal distances between nodes), eg:

best_tours = [i for i in tours if int(i[2]) in range(1800, 2100) and i[3] < 120]

The use case is an urban game for which I want to give participants somewhat equal-distanced personalized routes to avoid them mingling (Covid-restrictions). The total length of the routes depends on the duration of the game, hence the need to filter by total cost.

Are there any algorithms or solutions that allow for this type of computation, or are there any possibilities to improve the efficiency of my code to make it work for 50 nodes in a reasonable time?

RJ Adriaansen
  • 9,131
  • 2
  • 12
  • 26

2 Answers2

0

I don't know such an algorithm as you described. Thus you didn't append your brute force solution - many times you can use several methods to significantly reduce the computation time. using methods from the branch "Dynamic Programing" and in particular "memoization" for recursive algorithms.

Added a link for a great video that demonstrates the concept

MajoRoth
  • 1
  • 2
0

You may want to have a look at: https://github.com/potassco/guide/releases/tag/v2.2.0 Chapter: 6.2. It is a logical description of the TSP Problem, that can directly be solved by an ASP-solver like clingo.

Using these tools (https://potassco.org/) you can easily modify your objective function to anything you need and they are quite good at solving NP-complete problems.

Max Ostrowski
  • 575
  • 1
  • 3
  • 15