skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Conflict-Free Evacuation Route Planner
Given a transportation network with node and edge capacity constraints, initial node occupancy, destination locations, and the conflict resolution parameter k, the Conflict-Free Evacuation Route Planner (CF-ERP) problem finds evacuation routes that can minimize the evacuation time and the number of movement conflicts along the routes. CF-ERP is important for many societal applications, such as evacuation management and preparation in case of natural or man-made disasters. The problem is computationally challenging due to the large size of the transportation network and the constraints. Related work has considered the evacuation routing problem either solely as a network flow optimization problem or a conflict minimization problem, but not both. In this paper, we propose novel approaches that can produce evacuation routes to minimize the evacuation time and the number of movement conflicts. Experiments and a case study on real-world datasets from Florida show the effectiveness and efficiency of the proposed approaches.  more » « less
Award ID(s):
1844565
PAR ID:
10125879
Author(s) / Creator(s):
;
Date Published:
Journal Name:
27th SIGSPATIAL/GIS 2019: Chicago, IL, USA
Page Range / eLocation ID:
480 to 483
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, IEEE International Conference on Big Data)
    null (Ed.)
    Abstract—Evacuation planning methods aim to design routes and schedules to relocate people to safety in the event of natural or man-made disasters. The primary goal is to minimize casualties which often requires the evacuation process to be completed as soon as possible. In this paper, we present QueST, an agent-based discrete event queuing network simulation system, and STEERS, an iterative routing algorithm that uses QueST for designing and evaluating large scale evacuation plans in terms of total egress time and congestion/bottlenecks occurring during evacuation. We use the Houston Metropolitan Area, which consists of nine US counties and spans an area of 9,444 square miles as a case study, and compare the performance of STEERS with two existing route planning methods. We find that STEERS is either better or comparable to these methods in terms of total evacuation time and congestion faced by the evacuees. We also analyze the large volume of data generated by the simulation process to gain insights about the scenarios arising from following the evacuation routes prescribed by these methods. 
    more » « less
  2. ; (, International Conference on Smart Communities: Improving Quality of Life using AI, Robotics and IoT (HONET))
    Given a transportation network, a source node s, a destination node t , and the number of maximum possible turnings b , the Turn-Constrained Shortest Path (TCSP) problem is to find the route that minimizes the travel distance and meets the turn-constraint. The TCSP problem is important for societal applications such as shipping and logistics, emergency route planning, and traffic management services. We propose novel approaches for TCSP to meet the turn-constraint while minimizing the travel distance for the vehicle route. Experiments using real-world datasets demonstrated that the proposed algorithms can minimize the travel distance and meet the turn-constraint; furthermore, it has comparable solution quality to the unconstrained shortest path and significantly reduces the computational cost. 
    more » « less
  3. ; ; ; ; (, Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems)
    ABSTRACT Evacuation plans are designed to move people to safety in case of a disaster. It mainly consists of two components: routing and scheduling. Joint optimization of these two components with the goal of minimizing total evacuation time is a computationally hard problem, specifically when the problem instance is large. Moreover, often in disaster situations, there is uncertainty regarding the passability of roads throughout the evacuation time period. In this paper, we present a way to model the time-varying risk associated with roads in disaster situations. We also design a heuristic method based on the well known Large Neighborhood Search framework to perform the joint optimization task. We use real-world road network and population data from Harris County in Houston, Texas and apply our heuristic to find evacuation routes and schedules for the area. We show that the proposed method is able to find good solutions within a reasonable amount of time. We also perform agent-based simulations of the evacuation using these solutions to evaluate their quality and efficacy. 
    more » « less
  4. ; ; ; ; (, International Conference on Autonomous Agents and Multiagent Systems)
    Link prediction is one of the fundamental problems in computational social science. A particularly common means to predict existence of unobserved links is via structural similarity metrics, such as the number of common neighbors; node pairs with higher similarity are thus deemed more likely to be linked. However, a number of applications of link prediction, such as predicting links in gang or terrorist networks, are adversarial, with another party incentivized to minimize its effectiveness by manipulating observed information about the network. We offer a comprehensive algorithmic investigation of the problem of attacking similarity-based link prediction through link deletion, focusing on two broad classes of such approaches, one which uses only local information about target links, and another which uses global network information. While we show several variations of the general problem to be NP-Hard for both local and global metrics, we exhibit a number of well-motivated special cases which are tractable. Additionally, we provide principled and empirically effective algorithms for the intractable cases, in some cases proving worst-case approximation guarantees. 
    more » « less
  5. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Kumar, Amit; Ron-Zewi, Noga (Ed.)
    While much of network design focuses mostly on cost (number or weight of edges), node degrees have also played an important role. They have traditionally either appeared as an objective, to minimize the maximum degree (e.g., the Minimum Degree Spanning Tree problem), or as constraints that might be violated to give bicriteria approximations (e.g., the Minimum Cost Degree Bounded Spanning Tree problem). We extend the study of degrees in network design in two ways. First, we introduce and study a new variant of the Survivable Network Design Problem where in addition to the traditional objective of minimizing the cost of the chosen edges, we add a constraint that the 𝓁_p-norm of the node degree vector is bounded by an input parameter. This interpolates between the classical settings of maximum degree (the 𝓁_∞-norm) and the number of edges (the 𝓁₁-degree), and has natural applications in distributed systems and VLSI design. We give a constant bicriteria approximation in both measures using convex programming. Second, we provide a polylogarithmic bicriteria approximation for the Degree Bounded Group Steiner problem on bounded treewidth graphs, solving an open problem from [Guy Kortsarz and Zeev Nutov, 2022] and [X. Guo et al., 2022]. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email