How to design and scale sales territory?

Question

My first naive approach is:

• Given N number of salesmen. Cluster an area to be N clusters with almost equal number of clients [1] with some kind of same-size clustering/facility location algorithm
• Assign 1 salesman to 1 territory (one-to-one assignment)

The question is:

• How should we divide the territory gracefully if the number of salesmen increase/decrease from N=10 to N=9, N=11, or N=20?
• Is one-to-one assignment is doomed to fail? What are the alternatives for designing and scaling sales territory?

Because:

• the location of centroids could be very different between N=9, N=10, N=11. It can make the territories very different.
• increase of salesman from N=10 to N=20 will shrink the area of previous territory

Out of scope for this question:

• Routing (TSP/VRP). TSP with Time Window would be done after sales territory, but it's out of this question scope. This question is more about designing/scaling the sales territory itself.

Notes:

[1] We could use equal expected sales amount, but for argument sake let's use number of clients.

Answer 1

An approach sometimes used in other contexts is to start with an "optimal" assignment. If the number of sales people increases by one or two, solve a separate model (say a MIP model) that selectively reallocates some territories to the new sales people with constraints on how many they get, how much territory their clientele span, and how many clients each original sales person loses. (One of those likely becomes your objective function, with limits on the others.) Similarly, if the number of salespeople decreases, you solve yet another MIP model to reallocate portions of their territories to remaining sales people, again with "equity" constraints and some criterion.

The key here is that after a few reallocations, you go back to the original model and start over, getting an "optimal" solution for the new landscape. How often you start fresh will likely depend on how ragged the tweaked former solution gets and how grumpy people are about reallocations.