Optimize the locations of 2 additional restrooms on a trail (python)

Question

This image shows a made-up trail with a restroom (cyan point). I would like to add 2 more restrooms where the maximum distance along trail from anywhere on the trail to the closest of the 3 restrooms is minimized.

# Data

# trail is a list of segments between the magenta and/or cyan points (in the image).
# Each of the segments in turn is a list of endpoints.
trail = [[[0, 0], [1, 0]], [[2, 0], [3, 0]], [[3, 0], [4, 0]], [[4, 0], [5, 0]], [[6, 0], [7, 0]], [[5, 1], [6, 1]], [[1, 2], [2, 2]], [[4, 2], [5, 2]], [[1, -1], [2, -1]], [[3, -1], [4, -1]], [[5, -1], [6, -1]], [[4, -2], [5, -2]], [[1, 2], [1, 0]], [[1, 0], [1, -1]], [[2, 2], [2, 0]], [[2, 0], [2, -1]], [[3, 2], [3, 0]], [[4, 2], [4, 0]], [[4, 0], [4, -1]], [[4, -1], [4, -2]], [[5, 2], [5, 1]], [[5, 1], [5, 0]], [[5, 0], [5, -1]], [[5, -1], [5, -2]], [[6, 1], [6, 0]], [[6, 0], [6, -1]], [[3, -1], [4, 0]]]

restroom = [0, 0]

This is a simplified version of this question.

Hints will be appreciated as well. Thanks.

Answer 1

I think this could be effectively tackled with a relaxation approach.

1. Take your graph and place two new mobile toilets at random.
2. Use Dijkstra's algorithm to find the node in the graph that is furthest from any toilet.
3. Move the closest mobile toilet towards that point, again using Dijkstra to find the shortest path on which to move. The toilet should only be moved some fraction of the total distance to the destination point.
4. Repeat steps 2 and 3 until the system stabilises and the mobile toilets stop moving.

The fidelity of the solution will be improved by adding further degenerate nodes such that the maximum distance between nodes is below some threshold.

I wouldn't be at all surprised if there were some local-minima problems with some graphs that meant you wouldn't always get the same solution from different random starting placements, but this technique would at least refine an initial guess at a solution.

Answer 2

It might make a fun interactive graphic game if you drag the restrooms around the trail, and light up the most distant point on the trail, and also show some analog measure of the current maximum distance, and also the minimum maximum distance found so far. A more continuous coloring of the trail, indicating distances to the nearest restroom might give cues to aid in finding the minimax.

Answer 3

Randomly place two new mobile toilets along the trail. Use Dijkstra's algorithm to find the farthest node from any toilet. Gradually move the closest toilet towards the identified node using Dijkstra's algorithm for the shortest path. Repeat steps 2 and 3 until the system stabilizes and toilets stop moving.