5

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.

Improve this question
6
  • 3
    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
    Commented May 16, 2012 at 21:07
  • 5
    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
    Commented May 16, 2012 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
    Commented May 16, 2012 at 23:14
  • See my udpated question please.
    – seth
    Commented May 21, 2012 at 18:50
  • 1
    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
    Commented May 21, 2012 at 19:55

1 Answer 1

Reset to default
1

Here's a couple of solutions to the knapsack problem, which seems like the best fit for your allocation problem, as FrustratedWithFormsDesigner mentions above.

  1. University of Glasgow - Knapsack problem - includes algorithm discussion, pseudocode and java source.

  2. Princeton - Knapsack.java - using a dynamic programming approach, by Robert Sedgewick and Kevin Wayne.

Improve this answer
1
  • See my updated question please.
    – seth
    Commented May 21, 2012 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.