You may try a few more things:
If you have 10.2.2 installed, you can set some registry key in registry editor to generate better clustering result when dynamic seed points are in use:
You can also try Location-Allocation solver to partition the regions, and then use VRP solver to generate routes in each region:
Here is document for Location-Allocation solver: ArcGIS Help (10.2, 10.2.1, and 10.2.2) . To model your problem:
Hope it can solve your problem!