In the image below, the line is a trail and the point is an existing restroom. I would like to find the rough locations of 2 additional restrooms that minimize the maximum distance along trail from anywhere on the trail to the closest of the 3 restrooms.

The trail was GPS-collected in segments and connected with Edit Vertices in ArcMap. The dataset comprises 1 line shp for the trail and 1 point shp for the restroom. I have no idea how to proceed.

I have posted a simplified version of this question in stackoverflow.

Hints will be appreciated as well. Thanks.

enter image description here

  • 2
    Welcome to GIS.SE. What data (format, detail) do you have? What have you already tried? What happened? What worked, and for what didn't work, what happened instead? What research have you done?
    – BradHards
    Nov 27 '13 at 1:42
  • Are you using ArcGIS Online, ArcGIS for Desktop or another product from the ArcGIS Platform? Also, which version?
    – PolyGeo
    Nov 27 '13 at 4:22

Fascinating problem! While we humans are good at estimating optimality at sight and this problem is appropriate for that, a general solution would be much more interesting.

I only came up with a brute force heuristic though. Split the paths into smaller segments and precompute the route distances between all the nodes. Then go over all the combinations of toilet placements on the nodes, computing the maximum distance to a toilet (max of both) and comparing the combinations with the running minimum. You could reduce the number of combinations by adding a minimum toilet-to-toilet distance constraint. Of course, the better result you want, the longer this will take and it would fail for larger problems, as the number of combinations skyrockets.

Toilets are often at intersections, so if you added that as a constraint, the problem space would shrink significantly.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.