Create Territories

[markoakes]

I have a list of several hundred customers with Latitude and Longitude for each. I need to create sales Territories that have an equal number of customers and are grouped geographically. Any suggestions on the best way to accomplish this using just Excel?

 

[DRSteele]

To begin, you can determine the distances between each customer and the others. Put that in a matrix.

Please peruse this thread and its threads in the Forum for the formula to calculate Latitude and Longitude distances. http://www.mrexcel.com/forum/excel-questions/960529-help-countif-sumif-over-2-columns.html

After you create the matrix, we can try some optimisation techniques using Solver.

 

[DRSteele]

I took the liberty of creating a sample matrix for you.

Copy E7 and I7 down. Copy B15 across and down.

	A	B	C	D	E	F	G	H	I
6		h	m	s	Latitude	h	m	s	Longitude
7	Calgary	51	2	46	51.04611	114	3	24	114.0567
8	Edmonton	53	32	43	53.54528	113	29	21	113.4892
9	Montreal	45	30	6	45.50167	73	34	2	73.56722
10	New York	40	42	46	40.71278	74	0	21	74.00583
11	Seattle	47	36	22	47.60611	122	19	55	122.3319
12	Vancouver	45	38	19	45.63861	122	39	41	122.6614
13
14		Calgary	Edmonton	Montreal	New York	Seattle	Vancouver
15	Calgary	0	281	3019	3259	711	874
16	Edmonton	281	0	2973	3256	908	1098
17	Montreal	3019	2973	0	534	3674	3760
18	New York	3259	3256	534	0	3866	3922
19	Seattle	711	908	3674	3866	0	220
20	Vancouver	874	1098	3760	3922	220	0

<colgroup><col style="width: 25pxpx"><col><col><col><col><col><col><col><col><col></colgroup><thead>
</thead><tbody>
</tbody>

Sheet9​

Worksheet Formulas Cell Formula E7 =B7+C7/60+D7/3600 I7 =F7+G7/60+H7/3600 B15 =ACOS(COS(RADIANS(90-INDEX($E$7:$E$12,MATCH($A15,$A$7:$A$12)))) *COS(RADIANS(90-INDEX($E$7:$E$12,MATCH(B$14,$A$7:$A$12)))) +SIN(RADIANS(90-INDEX($E$7:$E$12,MATCH($A15,$A$7:$A$12)))) *SIN(RADIANS(90-INDEX($E$7:$E$12,MATCH(B$14,$A$7:$A$12)))) *COS(RADIANS(INDEX($I$7:$I$12,MATCH($A15,$A$7:$A$12))-INDEX($I$7:$I$12,MATCH(B$14,$A$7:$A$12)))))*6371 <thead> </thead><tbody> </tbody>

<tbody>
</tbody>

 

[markoakes]

Thank you for your help so far. I understand how to create the matrix but I have not used the Solver add-in before. My matrix has about 10,000 accounts and I need to create 40 Territories with the tightest geography and about the same number of accounts. Any hints on how to do that with the Solver? Thanks again.

 

[DRSteele]

Stay tuned while I think it through. This kind of multi-modal optimisation is vexing.

 

[markoakes]

Thank you once again for your help. I will stay tuned.

 

[DRSteele]

I have made some headway. Forgive the massive amount of data here; I had to create enough data to properly conduct experiments. I made 12 locales and divided them into 3 regions. I see that you wish to divide your 10,000 locales into 40 regions. Notice that I put random numbers in the region field starting in B37.

Copy E7, I7, E41, F41 down. Copy B22 across and down. After that, we will invoke Solver.

	A	B	C	D	E	F	G	H	I	J	K	L	M
6	locale	h	m	s	Latitude	h	m	s	Longitude
7	Calgary	51	2	46	51.046	114	3	24	114.057
8	Edmonton	53	32	43	53.545	113	29	21	113.489
9	Helena	46	35	45	46.596	112	1	37	112.027
10	Salt Lake	40	45	0	40.750	111	53	0	111.883
11	Montreal	45	30	6	45.502	73	34	2	73.567
12	Ottawa	45	25	0	45.417	75	41	0	75.683
13	New York	40	42	46	40.713	74	0	21	74.006
14	Washington	38	54	17	38.905	77	0	59	77.016
15	Seattle	47	36	22	47.606	122	19	55	122.332
16	Spokane	47	39	32	47.659	117	25	30	117.425
17	Vancouver	49	15	0	49.250	123	6	0	123.100
18	Victoria	48	25	43	48.429	123	21	56	123.366
19
20
21	129668	Calgary	Edmonton	Helena	Salt Lake	Montreal	Ottawa	New York	Washington	Seattle	Spokane	Vancouver	Victoria
22	Calgary	0	281	517	1157	3019	2876	3259	3168	711	449	674	729
23	Edmonton	281	0	780	1428	2973	2838	3256	3194	908	711	819	894
24	Helena	517	780	0	650	2941	2785	3096	2957	787	425	875	875
25	Salt Lake	1157	1428	650	0	3124	2960	3166	2965	1128	886	1290	1245
26	Montreal	3019	2973	2941	3124	0	165	534	786	3674	3316	3686	3726
27	Ottawa	2876	2838	2785	2960	165	0	540	732	3524	3164	3539	3578
28	New York	3259	3256	3096	3166	534	540	0	326	3866	3499	3903	3931
29	Washington	3168	3194	2957	2965	786	732	326	0	3738	3370	3791	3812
30	Seattle	711	908	787	1128	3674	3524	3866	3738	0	368	191	119
31	Spokane	449	711	425	886	3316	3164	3499	3370	368	0	454	450
32	Vancouver	674	819	875	1290	3686	3539	3903	3791	191	454	0	93
33	Victoria	729	894	875	1245	3726	3578	3931	3812	119	450	93	0
34
35
36	locale	Region		Regions	3
37	Calgary	1		Locales	12
38	Edmonton	3		Locales per region	4
39	Helena	2
40	Salt Lake	2		region	count	distances
41	Montreal	3		1	4	15225
42	Ottawa	3		2	4	4243
43	New York	1		3	4	14020
44	Washington	1			total:	33489
45	Seattle	2
46	Spokane	2
47	Vancouver	3
48	Victoria	1

<tbody>
</tbody>

latlong2​

Worksheet Formulas Cell Formula E7 =B7+C7/60+D7/3600 I7 =F7+G7/60+H7/3600 A21 =SUM(B22:M33)/2 E37 =COUNTA(A37:A48) E38 =E37/E36 E41 =COUNTIFS($B$37:$B$48,D41) F44 =SUM(F41:F43) <tbody> </tbody>

<tbody>
</tbody>

Array Formulas Cell Formula B22 {=ACOS(COS(RADIANS(90-INDEX($E$7:$E$18,MATCH($A22,$A$7:$A$18,0)))) *COS(RADIANS(90-INDEX($E$7:$E$18,MATCH(B$21,$A$7:$A$18,0)))) +SIN(RADIANS(90-INDEX($E$7:$E$18,MATCH($A22,$A$7:$A$18,0)))) *SIN(RADIANS(90-INDEX($E$7:$E$18,MATCH(B$21,$A$7:$A$18,0)))) *COS(RADIANS(INDEX($I$7:$I$18,MATCH($A22,$A$7:$A$18,0))-INDEX($I$7:$I$18,MATCH(B$21,$A$7:$A$18,0)))))*6371} F41 {=SUM(($B$37:$B$48=D41)*TRANSPOSE($B$37:$B$48=D41)*$B$22:$M$33)/2} <tbody> </tbody> Entered with Ctrl+Shift+Enter. If entered correctly, Excel will surround with curly braces {}. Note: Do not try and enter the {} manually yourself Now invoke Solver using the following settings. Set Objective click on $F$44 Min By changing cells $B$37:$B$48 Subject to constraints: create four of them them by choosing the Add button $B$37:$B$48 <= $E$36 $B$37:$B$48 = integer $B$37:$B$48 >= 1 $E$41:$E$43 = $E$38 remove checkmark from 'Make unconstrained' Select solving method as Evolutionary ignore the other settings for now - the defaults should be adequate click on Solve. Solver should now vibrate around until it comes up with a solution. The outcome which should appear will be one where our first four locales are assigned to one region (one of 1, 2, 3) the second four to another, and the final four to a third. I happen to know that this will be the proper answer. This process should minimize the total distances to one another across the regions. Which, I believe, was our objective. Give it a try and let us know how it goes. I anticipate that 10,000 locales and 40 regions is going to be markedly slower than our 12&3 experiment, if it even works at all. <strike></strike>

<tbody>
</tbody>

 

[markoakes]

Wow, that looks like you spent a lot of time on this. Thank you . I am away from my computer for the weekend but will test this on Monday.