Excel Formula for optimizing a route where each row represents a different "station" that can do different things

Question

I was unsure about how to frame this question.

Here is a minimum viable example:

• Jane can do A, B, D. Shes 1km away.
• Jack can do B, D, F. He is 1.5km away.
• Marshal can do E, F, A. He is 20km away.
• Polly can do E, D, C. She is 10km away.
• James can do C, F, B. He is 15km away.

The sheet has rows for each person, and columns for each action, A-F.

I want to find what combination of people I have to go to complete A, C, F with the minimum number of people visited. If two combinations are valid, I'd like the one with the smallest distance.

(So the solution to the above is Jane and James)

On my first row, I have checkboxes for each thing: A, B, C, D, E, F. I have selected A, C, F.

What formula would I use to highlight or colour code the people I should visit? If this can't be done in excel, what would an algorithm for solving this be called so I could implement it using a programming language?

Answer 1

Its done!

Concept

Brute force. Calculate the route distance for every combination of persons to visit. Ignore the combinations that doesn't offer all the required tasks (A-F). Select the route with the lowest route distance.

Implementation

The idea is to use binary representation to reduce the maths required. Lets say each person is assigned 1 bit in an integer number e.g. 1001 means visit person 1 and person 4. So if we have 8 people, we have 2^8-1 = 255 combinations of people to visit. We'll make combinations in rows numbered 1..255.

Now we do the same for every person's assigned tasks. Task A is bit 1, B is bit 2... etc. So if person 010 offers tasks with a task mask (TM) of 0101, then person 2 offers A and C, and person 001 with TM 1000 offers only D.

If we plan to visit persons 011 (001 AND 010), then the combined tasks on offer are

=BITOR("TM for 001", "TM for 010") which will result in TM 1101 (tasks A, C, D)

The combined tasks on offer for everyone are

=BITOR("TM for 001", BITOR("TM for 010", BITOR("TM for 100",... "TM for 10000000"))))))))

So in order to tell what tasks are offered by some random combination of persons x, we need to BITOR together only the relevant TMs:

=BITOR("TM for 001" * x0, BITOR("TM for 010" * x1, BITOR("TM for 100" * x2,... "TM for 10000000" * x7))))))))

where xi is the i'th bit in x

=BITAND(1,BITRSHIFT(x,i))

Likewise to determine the total distance for person combination / route x

"Person 1 distance" * x0 + "Person 2 distance" * x1 +... "Person 8 distance" * x7

Now to determine if, for persons x with TM y, all the required tasks z can be done (i.e. a valid route):

=IF(BITAND(y,z) = z, "All tasks offered by x", "All tasks cannot be done")

And the distance for valid routes only

=IF(BITAND(y,z) = z, *distance calc above*,"") so invalid routes are blank ""

Now calculate this for every possible combination e.g. (1..255) and look for the minimum valid route distance with MIN(...), then find the best route x with MATCH(MIN(...), route distances column, 0) that matches that minimum route distance. Break x apart into bits x0.. x7 and use conditional formatting to highlight each person in the best route.