Grouping postcodes in a way that minimises the sum geographical distance between them

[Hazel_needs_excel_help]

Hello,

This is my problem:

I have a list of postcodes. Half of them belong to girls, and half of them belong to guys. I have the distances between each postcode in a matrix. I need to put these postcodes into groups of 6, where 3 of the postcodes belong to girls and 3 to guys, in a way that minimises the sum distance between all the houses in every group. I want each group to contain houses that are as close together as possible.

I'd be grateful for any advice on this problem. This is my first post and thanks so much in advance!

Hazel

 

[Col Delane]

Hi Hazel and welcome to the Forum

This is an interesting puzzle.

Can you please clarify/expand upon the following:

1. how your matrix of post codes is laid out. (e.g. does have PCs for girls down the left hand column, and PCs for guys across the top row, with the distance between the row/column combo at the intersection?)
2. what exactly you mean by

   in a way that minimises the sum distance between all the houses in every group. I want each group to contain houses that are as close together as possible.

   Perhaps provide an example or two.​

 

[Hazel_needs_excel_help]

Hi Hazel and welcome to the Forum

This is an interesting puzzle.

Can you please clarify/expand upon the following:

1. how your matrix of post codes is laid out. (e.g. does have PCs for girls down the left hand column, and PCs for guys across the top row, with the distance between the row/column combo at the intersection?)
2. what exactly you mean by
   Perhaps provide an example or two.​

Thanks for your interest!

The matrix is actually just the distances between the postcodes and doesnt separate boys and girls.
I want to put them into groups of 6, 3 girls and 3 boys, so that each group consists of houses that are as geographically close together as possible.

My approach so far has been to try to use the solver function. I can get solver to put the postcodes into a set total number of groups that are as close together as possible- but I do not know how to make solver ensure that the groups are the same size.

Any help would be much appreciated!

Hazel

 

[Col Delane]

Hi Hazel

How/where are you designating postcodes as belonging to a girl or boy?
How are you getting Solver to group the postcodes - I didn't think it could do that.
Can you not add a constraint (or multiple constraints > one for each group) that the count of PCs in the group (perhaps returned by formulae linked to each group) = 6

HTH

 

[Hazel_needs_excel_help]

Hi Hazel

How/where are you designating postcodes as belonging to a girl or boy?
How are you getting Solver to group the postcodes - I didn't think it could do that.
Can you not add a constraint (or multiple constraints > one for each group) that the count of PCs in the group (perhaps returned by formulae linked to each group) = 6

HTH

1. I already have the information of which postcode belongs to which gender. I do not know how to let excel know this though!
2. I have a separate table of postcodes, group number and distances from that postcode to other postcodes in its group (from sumif to the matrix). I ask solver to change the group numbers for each postcode so that it finds an answer with the smallest possible sum distance in every group.
3. I tried adding the constraint this morning that each group must total 6 postcodes, but then solver instantly gets stuck as it tries each permutation one at a time, so as soon as it tries to move one postcode to another group, the groups do not all equal 6. It cannot try out its combinations with these restrictions. Due to this I think I cannot solve this problem user solver - do you agree? I've been thinking about looking into k-means clustering (I currently have no idea how to do this )What are your thoughts?

 

[Col Delane]

Seeing there is no point matching boy post codes with boy post codes, when I first tackled this problem I created a dummy matrix of codes with boy codes on one axis and girl codes on the other. The intersection of each code in the matrix was the distance between them. Of course this only works if each code is related to no more than one of each gender. Is this the demographic of your population?

I then identified the code on each row and each column (separately) that returned the minimum distance, and returned the code that matched that value to create a couple. The problem was then how to allocate a code that was returned twice to just one code of the other gender, and select the next shortest distance instead for the other one. Some type of "seat filling" methodology is required.

I need to put these postcodes into groups of 6, where 3 of the postcodes belong to girls and 3 to guys, in a way that minimises the sum distance between all the houses in every group

I expect this does NOT necessarily mean grouping the 3 couples that have the shortest distances between each pair, then the next shortest, and so on until the last group are the 3 with the greatest distance between each couple, because mixing short and long distances may reduce the sum distance for multiple groups for a more optimised result??

What on earth is "k-means clustering"? (Beyond my statistical expertise, which is not great in the first place!)

There's no doubt this is a real doozy!

 

[Hazel_needs_excel_help]

Seeing there is no point matching boy post codes with boy post codes, when I first tackled this problem I created a dummy matrix of codes with boy codes on one axis and girl codes on the other. The intersection of each code in the matrix was the distance between them. Of course this only works if each code is related to no more than one of each gender. Is this the demographic of your population?

I then identified the code on each row and each column (separately) that returned the minimum distance, and returned the code that matched that value to create a couple.

If you've managed to match each boy postcode to its closest girl then I think we've solved the problem!

1. I have managed to put all the boys into groups of 3 that are as geographically close together as possible. I have done this by using the longitudinal and latitudinal coordinates of each postcode and using k-means clustering that constrains each group to being the same size (i used this great website! https://code.google.com/p/ekmeans/)

2. if i can now match every girl to their closest boy, then those girls will become part of each boys groups. Giving me groups of 6 that are geographically close, half boys and half girl! HURRAH!

Could you explain again in detail how you managed to match each girl postcode to their closest boy postcode?

....and many thanks for all your help!

Hazel

 

[Col Delane]

Hi Hazel

If you've managed to match each boy postcode to its closest girl then I think we've solved the problem!

I'd be glad for you if I have, but is this really the required/optimal solution? As I wrote in my last post, I expect your following statement does NOT necessarily mean grouping the 3 couples that have the shortest distances between each pair, then the 3 next shortest, and so on until the last group are the 3 with the greatest distance between each couple, because a combo of couples separated by short and long distances may reduce the sum distance for a number of groups for a more optimised result.

I need to put these postcodes into groups of 6, where 3 of the postcodes belong to girls and 3 to guys, in a way that minimises the sum distance between all the houses in every group.

How to match each girl postcode to their closest boy postcode:

1. I created a simple matrix with boy codes across the top and girl codes down the page. (Say boy codes in B1:Z1, girl codes in A2:A26)
2. Populate (either by formula or hard coded input) the intersection between each code in the matrix (B2:Z26) with the distance between the two locations. (As I didn't have distances, I just used the absolutedifference between the code numbers as a proxy.)
3. In a column to the right of the matrix I then entered a formula in each row (of girl codes) that identified the minimum distance value in the row, and returned the corresponding boy code.
4. =Index($B$1:$Z$1,Match(Min($B?:$Z?),$B?:$Z?,1)) where =index([boy codes], match([Distance to nearest boy code (i.e. min in row) for this girl code],[all distances to boy codes for this girl code],[exact match]))
5. In a row beneath the matrix I then entered a formula in each column that identified the minimum distance value in the column, and returned the corresponding girl code. (A transposition of the above formula)

That's as far as I got - the point where:

• I had the same boy code for several girl codes (not an acceptable outcome, but good for that boy!!) - and not knowing how to allocate the code to one girl, and make it unavailable to the others, and
• was wondering whether you had more than one of each gender in the same code.

Cheers
Col