# Firefighting allocation problem

I'm trying to develop a model to work on an assignment problem in the firegifhter area. Given n firefighters, m trucks and z ongoing fires, each with a danger level, try and allocate the resources in the best way.

Is there some work on this i can read to try and understand how should i formulate my problem (costs, and so on)?

EDIT:

I have more details on the model. For each danger level there is a minimum number of firefighter that should be guaranteed, giving priority to the higher levels. Trucks have capacity and firefighters can only be allocated if there is a truck to take them to the fire. There's also a constraint saying that a fire can be abandoned if one with 2 or more levels above doesn't have the minimum number. Does this look like knapsack?

EDIT 2:

I am adding this because it might be of help to someone facing a similar problem. I opted to solve this using a tree. If you would like details feel free to contact and i can explain the algorithm in detail.

Disclaimer: i am familiar with assignment algorithms, like the Hungarian, for instance, and what i am looking here is not help with the algorith per se but with the formulation.

• I guess the first thing to define is what is the "best" allocation? Do you want the firefighters to focus on the most dangerous fire? Or do you want them to spread out and deal with many low-priority fires? – FrustratedWithFormsDesigner May 16 '12 at 21:07
• This sounds like a version of the knapsack problem, which is known to be NP-hard. It simplifies down to the problem, if you treat the sum of the fires' danger level as the capacity of the knapsack, and one combination of the firefighters to their respective trucks (e.g. 5 firefighters to each firetruck and 2 to the leftover firetruck). – Casey Kuball May 16 '12 at 21:34
• What's the problem here? You already have the allocation algorithms, what's the problem with translating them to code? – Loren Pechtel May 16 '12 at 23:14
• See my udpated question please. – seth May 21 '12 at 18:50
• It might not be a knapsack problem, but it's definitely a generic optimization problem. The minimum number of firefighters per priority translates into a constraint, same goes with the firefighters needing a truck. Your cost or target function might be tricky, but I would try something like `for fire in fires { cost += fire.priority * fire.number_of_assigned_firefighters }`. – sebastiangeiger May 21 '12 at 19:55