Tournament Scheduling Problem

Question

I am trying to design an algorithm to compute the solution to this problem.

Given a list of n tournaments with a name, start_date, end_date, latitude and longitude, find the list of p tournaments in chronological order with the least total travel distance when a person has to travel from one tournament to the next to the next.

A valid list of tournaments (called a tour) is where there are no overlaps in dates. The sports person travels from one tournament to the next along the straight line between the 2 coordinates.

I have a working solution but it uses too much memory.

I start by building a graph where nodes are tournaments and edges are the straight line distances between the coordinates of a node and a child_node. Each node has child nodes representing only tournaments which occur after it.

I then define a tour as a list of these nodes.

I start with a previous_tours list (containing tours of length i) and a current_tours list (containing tours of length i + 1). The previous_tours list is initialised with tours of length 1, which is just n tours each with one of the nodes.

Then to calculate the current_tours list, I loop through the previous_tours list and for each tour (current_tour) I get the last_node in the tour. Then for each child_node in last_node, I copy the current_tour and append the child_node to the end of the tour and add each copy to the current_tours list. This calculates all possible tours of length 2 as nodes only have child nodes occuring after it. The distance between the last_node coordinates and the child_node coordinates is added to the tours total travel distance. I then set previous_tours to current_tours.

I repeat this until I have all possible tours of length p. Then I loop through this list to find the one with the least total travel distance.

This is giving me the correct answer, but I am giving it a list of 120 tournaments and trying to calculate the best tour of length 4 and it uses around 5GB of memory when I implemented it in C++

I was thinking of just adding in a heuristic at each iteration to cut down the number of possible tours.

Does anyone know a more efficient way of getting this result without using a heuristic in that way?

Answer 1

The chronological order constraint actually makes this problem much easier to solve than D.W. thought. It means that we can orient edges in the graph from earlier to later tournaments (reflecting the fact that we cannot travel back in time), and wind up with a DAG (cycle-free directed graph). The problem can be solved optimally in $O(pn^2)$ time and $O(pn)$ space (so, at most a few milliseconds and KB for your problem size) using dynamic programming.

Let $f(v, i)$ be the length of the shortest $i$-vertex path that ends at vertex $v$. The goal is to compute $f(v, p)$ across all vertices, and pick the $v$ that minimises the function among all of them.

The shortest $i$-vertex path ending at vertex $v$ must be the result of extending (by one edge, to $v$) the shortest length-$(i-1)$ path to one of $v$'s predecessors:

$f(v, i) = \min_{u:uv\in E} f(u,i-1)+d_{uv}$

where $E$ is the set of all edges in the graph and $d_{uv}$ is the distance between $u$ and $v$.

Naturally we also have $f(v, 1) = 0$ for all $v$. So, we can compute all these function values and store them in a 2D array as follows:

• Initialise $f[1][v] = 0$ for all $v$.
• For $i$ from 2 to $p$:
  • For each $v$ in $V$:
    • Set $x = \infty$.
    • For each predecessor (in-neighbour) $u$ of $v$:
      • Set $x = \min(x, f[i-1][u] + d_{uv})$.
    • Set $f[i][v] = x$.
• Set $z=v_1$.
• For each $v$ in $V\setminus \{v_1\}$:
  • If $f[p][v] < f[p][z]$ then set $z=v$.

After running this, we know the lengths of all shortest paths of $i$ vertices or less ending at each vertex, and that the shortest overall path of $p$ vertices ends at vertex $z$. To find an actual shortest path ending at vertex $z$, we can trace backwards through the matrix looking for predecessor entries that satisfied the $\min$ condition:

• Set $i=p$.
• While $i>0$:
  • Output the current vertex, $z$.
  • Set $x = \infty$.
  • For each predecessor (in-neighbour) $u$ of $z$:
    • If $f[i-1][u] + d_{uz} = f[i][z]$:
      • $u$ is the previous tournament on some optimal path ending at $z$, so set $z=u$, decrease $i$ by 1 and jump to the top of the while loop.

This will output the tournaments in reverse order, but that can be easily fixed.