Hello,

I've come across a problem in my research and thought it might be worth it to post here for ideas. Let me set up the situation with a random example.

Imagine we have 5 ambulances and at the same time, there are two car accidents. Accident #1 is requires 3 ambulances and accident #2 is slightly less serious and requires only 2 ambulances. But, the healthcare service is taking financial cutbacks and needs to minimise the amount of fuel required to attend to accidents, etc.

Anyway, suppose we can calculate, beforehand, the cost of each ambulance to get to each accident, and organise them into a table like so:

Ambulance Number Fuel Cost to Accident 1 ($) Ambulance Number Fuel Cost to Accident 2 ($)
1 5 1 3
2 12 2 6
3 13 3 4
4 7 4 11
5 9 5 10

The question, then, is how do you choose which ambulances go to which site in order to minimise the total fuel cost?

My initial thought was just to order both cost columns from lowest to highest, and hope that the obvious solution would pop out to me... but in most cases, when you do that, there'll be some overlap. For example, if we order the table above in that fashion, we get this:

Ambulance Number Fuel Cost to Accident 1 ($) Ambulance Number Fuel Cost to Accident 2 ($)
1 5 1 3
4 7 3 4
5 9 2 6
2 12 4 10
3 13 5 11

And so we see that Ambulance number 1 is in the TOP 3 for accident #1 AND in the TOP 2 for accident #2, so there is some overlap there.

So, does anybody know of any obvious way to solve this problem? Choose 3 ambulances for accident 1 and 2 ambulances for accident 2 which minimises the fuel cost, without having to go through every single permutation? Is there an analytical way of doing it quickly and efficiently?

In my research, the problem isn't about ambulances and accidents, but it's a nice analogy. However, in my research it will get more complex - i.e. what if there's 50 ambulances and 20 crash sites, all with different ambulance requirements? In that case, any method which searches through each permutation will be too computationally expensive to be of any use. Any thoughts?