Help with approaching this problem correctly
This problem sounds like an optimization problem , where the goal to find the best solution under constraints. In this case, the solution space would minimize travel times while meeting staff constraints.
Often the most difficult aspect is encoding the raw data into a format that works for the optimization solver. Generally, try a simplest encoding that could possible work. For example, use distance as a proxy for travel times.
PuLP is a linear programming package for Python that could solve the problem once it is properly encoded.