Sangho Kim, Betsy George and Shashi Shekhar. Evacuation Route Planning: Scalable Heuristics, 15th ACM International Symposium on Advances in Geographic Information Systems (ACMGIS'07), Seattle, WA, 2007.

Betsy George, Sangho Kim, and Shashi Shekhar. Spatio-temporal Network Databases and Routing Algorithms: A Summary of Results. 10th International Symposium on Advances in Spatial and Temporal Databases (SSTD'07), 460-477, Boston, MA, 2007

Sangho Kim, Shashi Shekhar, and Jeffrey Wolff. Software Tools to Compare Transportation Modes for Car-less Evacuation. National Conference on Disaster Planning for the Carless Society, New Orleans, LA, 2007.

Sangho Kim. Contra-flow (Lane Reversal Scheme), Plane Sweep Algorithm, and Traveling Salesman Problem. articles in the Encyclopedia of Geographic Information Science, Springer, 2007.

Jinsoung Yoo, Shashi Shekhar, Sangho Kim, and Mete Celik. Discovery of Co-evolving Spatial Event Sets. In Proceedings of SIAM International Conference on Data Mining (SDM'06), Bethesda, MA, 2006.

Sangho Kim and Shashi Shekhar. Contraflow Network Reconfiguration for Evacuation Planning: A Summary of Results, 13th ACM International Symposium on Advances in Geographic Information Systems (ACMGIS'05), Bremen, Germany, 2005.

Eil Kwon and Sangho Kim. Evaluation of Route-based Signal Preemption Strategies for Emergency Vehicle Operations. Intelligent Transportation Systems America Conference (ITSAC'03), Minneapolis, MN, 2003.

Eil Kwon and Sangho Kim. Route-based Dynamic Preemption of Traffic Signals for Emergency Vehicles. Transportation Research Board (TRB), Washington, D.C., 2003.

Eil Kwon, Sangho Kim, and Takmoo Kwon. Pseudo Real-time Evaluation of Adaptive Traffic Control Strategies using Hardware-in-Loop Simulation. in Proceedings of IEEE Industrial Electronics Society 27th Annual Conference (IECON 2001), Denver, CO, 2001.


Presentations
Evacuation Route Planning: Scalable Heuristics. Presented at 15th ACM International Symposium on Advances in Geographic Information Systems, Seattle, Washington, November 7-9, 2007.

Software Tools to Compare Transportation Modes for Car-less Evacuation. Presented at the National Conference on Disaster Planning for the Carless Society, New Orleans, LA, February 8-9, 2007.

Capacity Constrained Route Solver with Network Analyst Framework. Presented at ESRI as a summary of internship work, July 31, 2006

Contraflow Network Reconfiguration for Evacuation Planning: A Summary of Results. Presented at 13th ACM International Symposium on Advances in Geographic Information Systems, Bremen, Germany, November 4-5, 2005.

Research on Evacuation Planning / Contraflow Problems. Presented at Spatial Databases Research Group Meetings, Minneapolis, Minnesota, each semester from 2003 to 2007.

Evaluation of Route-based Signal Preemption Strategies for Emergency Vehicle Operations. Presented at the 2003 Intelligent Transportation Systems America Conference, Minneapolis, Minnesota, May 2003.

Contraflow Transportation Network Reconfiguration for Evacuation Route Planning
Given a transportation network having source nodes with evacuees and destination nodes, we want to find a contraflow network configuration, i.e., ideal direction for each edge, to minimize evacuation time. Contraflow is considered a potential remedy to reduce congestion during evacuations in the context of homeland security and natural disasters (e.g., hurricanes). This problem is computationally challenging because of the very large search space and the expensive calculation of evacuation time on a given network. To our knowledge, this paper presents the first macroscopic approaches for the solution of contraflow network reconfiguration incorporating road capacity constraints, multiple sources, congestion factor, and scalability. We formally define the contraflow problem based on graph theory and provide a framework of computational structure to classify our approaches. A Greedy heuristic is designed to produce high quality solutions with significant performance. A Bottleneck Relief heuristic is developed to deal with large numbers of evacuees. We evaluate the proposed approaches both analytically and experimentally using real world datasets. Experimental results show that our contraflow approaches can reduce evacuation time by 40% or more.

Software Tools to Compare Transportation Modes for Car-less Evacuation
Software tools to compare transportation modes for car-less evacuation plans are important in the event of man-made (e.g. terrorism) and natural disasters (e.g., hurricanes). Traditional evacuation plans often relied on private cars. However, hurricanes Katrina and Rita showed significant limitations of such plans, including severe traffic congestion and vulnerability of people who either did not have a vehicle available for transportation or were physically unable to drive. The limitations of car-based evacuation plans highlight the critical need for evacuation software tools to evaluate alternative transportation modes such as walking and alternative evacuation schemes such as contra-flow. We propose a graph-based evacuation model to simulate situations of road network for car-based and car-less evacuation. Heuristic algorithms are presented to simulate the movement of evacuees and apply intelligent contra-flow schemes. These algorithms are effectively implemented as evacuation software tools to meet the needs of emergency practitioners. A remarkable finding from our experiments suggests that car-less evacuation without contra-flow may take less time to evacuate vulnerable people to safety than car-based evacuation with contra-flow.

Metro Evacuation Traffic Management Plan
With the nation at heightened concern about security, it is imperative that the Minneapolis/St. Paul Metropolitan Area establish evacuation plans/procedures for a safe as well as efficient movement of civilians and emergency response resources in case of an emergency. While many municipalities and counties have already developed evacuation plans, these plans are not coordinated and often use common arterials and highways. This project focused on coordinating existing local plans and minimizing the potential for congestion on interstates or major highways that could slow an evacuation and decrease safety for citizens during events that require multi-jurisdictional, coordinated evacuation. The plan addresses possible scenarios and impacts; identifies resources, actions, and roles; identifies routes for most timely evacuation; addresses traffic management strategies; and identifies information sharing and coordination. The plan also increases knowledge of what each agency’s role is, in order to make coordinated and effective decisions during an evacuation and focuses on ideas for increasing capacity on the current transportation infrastructure.

Application of Model-Oriented Formal Method to the Efficient Development of Signal Preemption Strategies of Emergency Vehicle
Current infrastructure systems are heavily dependent on computer software. In case of critical infrastructure systems, the robustness of system software becomes a critical issue. For example, if the infrastructure systems are related to human life, no failures can be allowed. Such system reliability, a product of a series of system development processes, can be affected by early development stages, such as system specification and design. We attempted to apply the model-oriented formal method to critical infrastructure systems in transportation: Emergency Vehicle Preemption (EVP) systems. The EVP system allows emergency vehicle to go to the emergency destination as quickly as possible by the preemption of traffic signals. We chose the Vienna Development Method Specification Language (VDM-SL) as the model-oriented formal method, since it is possible to develop a set of precise and complete software specifications by the formal notation.

Pseudo Real-Time Evaluation of Adaptive Traffic Control Strategies using Hardware-in-Loop Simulation
A pseudo real-time simulation system that can be used for evaluating intersection control strategies is presented. For this research, a microscopic traffic simulator and an interface device, which connects the simulator to a 2070 traffic controller, was developed. The interface device consists of a commonly available 8255 digital I/O card, the newly developed signal converter for two-way translation between TTL level signals and the open-collector outputs, and a software module to link the traffic simulator to the I/O card. The resulting virtual-intersection system makes it possible to directly implement new control strategies into the advanced traffic controller and evaluate their performance in a pseudo real-time environment. In this study, the operational feasibility of a new adaptive control strategy, which is based on a direct control approach with link-wide congestion index, was evaluated using the proposed system. The results from the pseudo real-time simulation using a sample intersection indicate that the adaptive algorithm can be operational with the current control hardware with significantly improved efficiency in managing intersection traffic.