Problem : Missouri S&T Evacuation Plan (from Midterm 1 of Spring 2014)
Recently, there was a gas line break in the Missouri S&T campus. Dr. Konur got very scared of the alerts while he was working in his office a lot for his students in the EMGT 365 class. Thus, he decided to come up with an evacuation plan in a case of an emergency. He first downloaded the campus map using the following link: http://www.mst.edu/map/ (Campus Map PDF or Campus Map JPG).
If an emergency happens in the campus, Dr. Konur will immediately leave his office in the Engineering-Management-Building (facility # 5) and he thinks he will be safe if he either reaches to Allgood-Bailey-Stadium (facility # 34) or Rock-Mechanics-and-Explosive-Research-Center (facility # 14). He wants to go to one of these facilities from his office as fast as he can in case of an emergency. However, since in case of an emergency there will be a chaos, he cannot directly go to Allgood-Bailey-Stadium (facility # 34) or Rock-Mechanics-and-Explosive-Research-Center (facility # 14). He has the following possible walks between the facilities:
- From Engineering-Management-Building (facility # 5), he can go to either Chancellor's-Residence (facility # 40) or Kummer-Student-Design-Center (facility # 47).
- From Chancellor's-Residence (facility # 40), he can go to Kummer-Student-Design-Center (facility # 47) or Allgood-Bailey-Stadium (facility # 34) or Miner-Dome-Indoor-Practice-Facility (facility # 48).
- From Kummer-Student-Design-Center (facility # 47), he can go to Allgood-Bailey-Stadium (facility # 34).
- From Miner-Dome-Indoor-Practice-Facility (facility # 48), he can go to Allgood-Bailey-Stadium (facility # 34) or Rock-Mechanics-and-Explosive-Research-Center (facility # 14).
In one of his off-days, Dr. Konur calculated how fast he can go between these facilities. The table below shows the time to reach from a facility to another in seconds.
Dr. Konur wants to find the path with the shortest time to one of the safe facilities, i.e., either Allgood-Bailey-Stadium (facility # 34) or Rock-Mechanics-and-Explosive-Research-Center (facility # 14).
a) Represent Dr. Konur's shortest time path problem on a network by drawing the nodes and explain what they represent, drawing the arcs, and what they represent, arc costs if any, arc capacities if any, node values if any. State the shortest path problem on the network you have created similar to "Find the shortest path from node A to node B on the network".
(Hint: you will need to define a dummy destination node and connect your original destinations to your dummy destination so that you have a single destination). Mathematically formulate the shortest path problem you have defined as a minimum cost flow problem.
After solving his shortest path problem, Dr. Konur realizes that he was being selfish, he was not thinking about the people in the Engineering-Management-Building (facility # 5). Therefore, he decided to find the maximum number of people he can evacuate from Engineering-Management-Building (facility # 5) to the safe facilities. However, there is a limit on the number of people who can simultaneously be evacuated on each possible link defined above. The table below shows the maximum number of people that can reach from a facility to another.
b) Mathematically formulate a maximum-flow problem that will determine the maximum number of people that can travel to the safe facilities, i.e., Allgood-Bailey-Stadium (facility # 34) and Rock-Mechanics-and-Explosive-Research-Center (facility # 14), from Engineering-Management-Building (facility # 5).