Emergency Planning with OR

One recent talk that stood out to me was given by Marc Goerigk and talked about how operational research can be used to help improve evacuation planning for emergencies. For example unexploded WWII era bombs, Lancaster floods or terrorist incidents.

The ideas I will talk about are to do with using an optimisation approach to give a good lower bound on the evacuation time. Simulation techniques on the other hand are more useful for finding an upper bound on the evacuation time.

A clever thing to do when we are trying to model real world places is to try and represent the place in a network. Essentially we can take a map and represent it in a graph network using nodes and arcs. Arcs generally represent paths or roads and nodes the intersection of these paths and roads. This allows us to simplify tricky features such as curved roads into nice straight lines.

flatnetwork

Transforming a map of my flat into a network diagram

When an emergency happens we will have to move people to a safe place. Often there will be area where we have to evacuate from (think of a radius). This is shown below with some times to travel to between places in the flat when a fire has broken out in the kitchen.

flatnetworktimes

Network with travelling times. When there is a fire, we need to evacuate people to a.

Generally we have a set of nodes that represent safe points or evacuation shelters rather than the 1 safe point in the example above. Also in real life these shelters each have their own finite capacity, think of hotels or schools. What we need to do is move all the people in danger into the shelters as fast as we can. The question is can we work out the way to do this in the shortest possible evacuation time?

The Maths Version

As you might have guessed a way to tackle this problem is through formulating it as a linear programming problem. This is the formulation given in this paper by Marc. He defines x_{ij} as the number of evacuees moving along edge i-j. d_{ij} is the time to travel along edge i-j. There are also b evacuees that need to escape from a particular node to any subset of shelters t_i that each have their own capacity u_i in turn.

(1)

(2)

(3)

(4)

 

The No-Maths Version

The key constraints of the mathematical model are,

  1. All evacuees leave the starting node s, i.e everyone must escape
  2. Evacuees entering a node must also leave it, i.e. evacuees can only stop at a shelter
  3. Each shelter has a capacity, i.e everybody can’t go in the same shelter.

Possible extensions to the problem to consider:

  • people walk at different speeds
  • terrain will vary
  • some people will be familiar with the area
  • fitness of people will vary
  • age of people will vary
  • direction of doors affects travelling times
  • people are irrational (people might go back inside to save stuff, rather than get out!)
  • people don’t always follow instructions
  • people might travel in groups (families stick together)

Alternative measures to consider:

  1. Minimise the total evacuation time of all people
  2. Minimise the evacuation time of the last person leaving the building
  3. Minimise the number of shelters needed to be opened & evacuation time
  4. Minimise the cost of opening shelters & evacuation time

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s