Take a look at the Floyd-Warshall algorithm and the Merge Sort algorithm.
Given that the number of locations to visit (vertices) is V and the number of travellers is T, if you apply the Floyd-Warshall algorithm, it should give you shortest paths between pairs of vertices in your graph, with O(V^3) complexity.
You can then sort the lengths of the shortest paths in ascending order, which is going to be an operation with O(V lg V) complexity.
Since you are applying these algorithms in sequence, you're still at an overall complexity of O(V^3).
You will have to perform this second stage K times where K is ceiling(V / T), because in the first iteration, you would have visited T vertices, but V is greater than T so you have some more vertices to visit. In your next iteration, you will remove the visited vertices from the calculation and sort the remaining distances (which you have already found in the previous step) and then proceed to visit them from the new locations of the T travellers.
You could probably achieve a better result by picking the smallest distance for each vertex, so the next vertex you select is the closest one on offer.
Therefore your overall complexity will start to look like O(V^3) + K x O(V lg V), which I think tends to approach O(V^3).
These are just some ideas to get you started.