Do you have the
start,
end coordinates for each race in a convenient machine readable format? 150 vertices is few enough to at least approximate a solution to traveling salesman.
I was looking at
traveling salesman solvers recently. (Even though it turned out not to be necessary for the problem I was looking at.) For this problem, you set up a directed graph over 150 vertices. The weight of the edge between vertex
i and vertex
j is the distance from the end of race
i to the start of race
j.
wij = distance(
Ri.
end,
Rj.
start)
To take resets in to account, you'll need to figure out some conversion factor from distance on the map to time (i.e., seconds), and measure the
reset_time in seconds. Then the weight between vertex
i and vertex
j is the smaller of the no-reset option (the one above) and the reset option.
wij = min(
distance_to_time × distance(
Ri.
end,
Rj.
start),
distance_to_time × distance(
Ri.
start,
Rj.
start) +
reset_time
)
Here's an example of approximating a solution using
NetworkX in Python. I used the pixel coordinates of the first few races from the map you posted. You'll have to fill in the full table of coordinates. There's documentation on
traveling_salesman_problem and
simulated_annealing_tsp.
Language: python
import collections
import math
import random
import networkx
import networkx.algorithms.approximation.traveling_salesman as TSP
Point = collections.namedtuple("Point", ("x", "y"))
Race = collections.namedtuple("Race", ("label", "start", "end"))
RACES = (
Race(1, Point(1263, 1724), Point(6888, 556)),
Race(2, Point(1400, 1775), Point(7555, 979)),
Race(3, Point(1477, 1798), Point(1728, 1715)),
# ...
)
def distance(p_1, p_2):
return math.sqrt((p_2.x - p_1.x)**2 + (p_2.y - p_1.y)**2)
G = networkx.DiGraph()
for j in range(len(RACES)):
r_j = RACES[j]
for i in range(len(RACES)):
if i == j:
continue
r_i = RACES[i]
G.add_edge(r_i.label, r_j.label, weight = distance(r_i.end, r_j.start))
print(G)
path = TSP.traveling_salesman_problem(
G,
cycle = False,
method = lambda g, weight: TSP.simulated_annealing_tsp(g, "greedy"),
)
print("path", path)
print("weight", networkx.path_weight(G, path, "weight"))
For me this outputs
DiGraph with 3 nodes and 6 edges
path [3, 1, 2]
weight 6086.839929148261
So, every race has a start point and an end point - the path the race actually takes doesn't matter. Ideally, you do not perform any race resets, and the path between the end of a race and the start of its subsequent one should be as short as possible.
