How to divide a graph into several smaller graphs, in which the shortest paths to bypass all vertices would be approximately the same?

Question

Counts

In other words, if there are 100 stores and 10 couriers, how do you distribute the stores among the couriers so that each of them walks about the same distance?

Answer 1

The traveling salesman problem, supplemented by several couriers. Don't expect to find fast, beautiful solutions to an NP-complete problem.
But, to some extent, they could help you:
-search for approaches to choosing a courier for a point based on dynamic programming.
-preliminary division of the graph into communities by distance.
-any admissible simplifications of the initial data (I don't know your specifics).