Browsing by Author "Kim, Sangho"

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Contraflow Transportation Network Reconfiguration for Evacuation Route Planning
    (2006-06-01) Shekhar, Shashi; Kim, Sangho
    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.
  • Thumbnail Image
    Item
    Development of Dynamic Route Clearance Strategies for Emergency Vehicle Operations, Phase I
    (2003-06-01) Kwon, Taek Mu; Kim, Sangho
    A route-based signal preemption strategy is developed to provide the most efficient and safe route for an emergency vehicle under a given network and traffic conditions. It combines an on-line route selection procedure and a dynamic sequential preemption method. The on-line route selection module first quantifies the level of congestion for each link on a given network using a congestion index and finds the least congested route for a given origin/destination pair using the well-known Dijkstra's algorithm. Further it also selects the safest signal phase for each intersection for a given travel direction of an EV. Once an emergency route is selected, the dynamic preemption module starts the preemption of the signals on the emergency route sequentially considering the location of the EV and the state of signal phase for each intersection. By sequentially preempting the traffic signals on a route with advance activation, the proposed strategy tries to clear the traffic queue for an EV approaching each intersection. The evaluation results with pre-specified emergency routes show 10 - 16% reduction of the emergency vehicle travel time for relatively long and/or complicated routes compared with the existing intersection-by-intersection preemption method. Further, the network-wide performance measures with the proposed dynamic preemption method were very compatible with those from the existing intersection-by-intersection clearance method.
  • Thumbnail Image
    Item
    Development of Signal Operations Research Laboratory for Testing and Development of Advanced Control Strategies, Phase 1
    (Center for Transportation Studies, University of Minnesota, 2002-07-01) Kwon, Eil; Kim, Sangho; Kim, Dongsoo; Lee, Enha
    A virtual intersection environment consisting of a new microscopic traffic simulator and a 2070 traffic controller was developed to provide a platform for a realistic pseudo real-time evaluation of intersection control strategies. The new simulator is based on an object-oriented modeling approach. In particular, the interface between the simulator and the traffic controller was developed using a commonly available digital input/output card and the Windows NT registry. Further, a signal converter was also developed to transform the format of the emulated detector data from the simulation model into the data format acceptable by the traffic controller. The implementation of the intersection control strategies into the 2070 controller was performed using the field I/O manager module provided by the City of Los Angeles DOT. The resulting Hardware-in-loop simulation system was applied to evaluate different control strategies for an intersection, i.e., pre-timed, actuated and adaptive methods.
  • Thumbnail Image
    Item
    Signal Operations Research Laboratory for Development and Testing of Advanced Control Strategies, Phase II
    (Minnesota Department of Transportation, 2002-09-01) Kwon, Eil; Ambadipudi, Ravi-Praveen; Kim, Sangho
    A corridor simulation environment with the capability of modeling various types of traffic control strategies as external control modules is critically important in developing and improving corridor management strategies. In this research, a microscopic network simulation model, Vissim, is used to develop such an environment. The new stratified Mn/DOT metering algorithm was simulated using the 169 freeway, and its performance was compared with that of the fixed-metering method. Based on that analysis, an alternative approach to determining each entrance ramp's minimum metering rate was developed and coded, as well as an adaptive approach to automatically coordinating a freeway meter with the adjacent intersection signal. The results clearly show the advantage of reducing the overall delay at the ramp-intersection area, while producing higher or compatible total vehicle-miles compared with the conventional intersection-control methods, i.e., pre-timed and actuated, without employing ramp metering. The corridor evaluation environment can be used for future studies, including the continuous enhancement of the stratified metering algorithm to take advantage of the maximum allowable wait time, automatic identification of the most effective metering strategy depending on prevailing traffic conditions, and extension of the adaptive coordination method to multiple intersections adjacent to a freeway entrance ramp.
  • Thumbnail Image
    Item
    Spatio-temporal Network Databases and Routing Algorithms
    (2008-11-17) George, Betsy; Shekhar, Shashi; Kim, Sangho
    Spatio-temporal networks are spatial networks whose topology and parameters change with time. These networks are important for many critical applications such as emergency traffic planning and route finding services and there is an immediate need for models that support the design of efficient algorithms for computing the frequent queries on such networks. This problem is challenging due to the potentially conflicting requirements of model simplicity and support for efficient algorithms. Time expanded networks, which have been used to model dynamic networks, employ replication of the network across time instants, resulting in high storage overhead and algorithms that are computationally expensive. In contrast, the proposed time-aggregated graph (TAG) does not replicate nodes and edges across time; rather it allows the properties of edges and nodes to be modeled as a time series. Since the model does not replicate the entire graph for every instant of time, it uses less memory and the algorithms for common operations (e.g. connectivity, shortest path) are computationally more efficient than those for time expanded networks. One important query on spatio-temporal networks is the computation of shortest paths. Developing efficient algorithms for computing shortest paths in a time varying spatial network is challenging because these journeys do not always display the optimal substructure, making techniques like dynamic programming inapplicable. In addition, shortest paths can be computed either for a given start time or to find the start time and the path that leads to least travel time journeys (best start time journeys). In this paper, we present algorithms for shortest path computations in both contexts using the proposed TAG and arrival time series transformation (ATST). We present the analytical cost models for the algorithms and provide an experimental comparison of performance with existing algorithms.