Location planning for transit-based evacuation under the risk of service disruptions

The effectiveness of transit-based emergency evacuation highly depends on the location of pick-up facilities, resource allocation, and management. These facilities themselves are often subject to service disruptions during or after the emergency. This paper proposes a reliable emergency facility location model that determines both pre-emergency facility location planning and the evacuation operations afterwards, while facilities are subject to the risk of disruptions. We analyze how evacuation resource availability leverages individual evacuees’ response to service disruptions, and show how equilibrium of the evacuee arrival process could be reached at a functioning pick-up facility. Based on this equilibrium, an optimal resource allocation strategy is found to balance the tradeoff between the evacuees’ risks and the evacuation agency’s operation costs. This leads to the development of a compact polynomial-size linear integer programming formulation that minimizes the total expected system cost from both pre-emergency planning (e.g., facility set-up) and the evacuation operations (e.g., fleet management, transportation, and exposure to hazardous surroundings) across an exponential number of possible disruption scenarios. We also show how the model can be flexibly used to plan not only pre-disaster evacuation but also post-disaster rescue actions. Numerical experiments and an empirical case study for three coastal cities in the State of Mississippi (Biloxi, Gulfport, and D’lberville) are conducted to study the performance of the proposed models and to draw managerial insights.     

Optimizing path query performance: graph clustering strategies

Path queries over transportation networks are operations required by many Geographic Information Systems applications. Such networks, typically modeled as graphs composed of nodes and links and represented as link relations, can be very large and hence often need to be stored on secondary storage devices. Path query computation over such large persistent networks amounts to high I/O costs due to having to repeatedly bring in links from the link relation from secondary storage into the main memory buffer for processing. This paper is the first to present a comparative experimental evaluation of alternative graph clustering solutions in order to show their effectiveness in path query processing over transportation networks. Clustering optimization is attractive because it does not incur any run-time cost, requires no auxiliary data structures, and is complimentary to many of the existing solutions on path query processing. In this paper, we develop a novel clustering technique, called spatial partition clustering (SPC), that exploits unique properties of transportation networks such as spatial coordinates and high locality. We identify other promising candidates for clustering optimizations from the literature, such as two-way partitioning and approximate topological clustering. We fine-tune them to optimize their I/O behavior for path query processing. Our experimental evaluation of the performance of these graph clustering techniques using an actual city road network as well as randomly generated graphs considers variations in parameters such as memory buffer size, length of the paths, locality, and out-degree. Our experimental results are the foundation for establishing guidelines to select the best clustering technique based on the type of networks. We find that our SPC performs the best for the highly interconnected city map; the hybrid approach for random graphs with high locality; and the two-way partitioning based on link weights for random graphs with no locality.     

The representation and implementation of time-dependent inundation in large-scale microscopic evacuation simulations

Multi-agent simulation has increasingly been used for transportation simulation in recent years. With current techniques, it is possible to simulate systems consisting of several million agents. Such multi-agent simulations have been applied to whole cities and even large regions. In this paper it is demonstrated how to adapt an existing multi-agent transportation simulation framework to large-scale pedestrian evacuation simulation. The underlying flow model simulates the traffic-based on a simple queue model where only free speed, bottleneck capacities, and space constraints are taken into account. The queue simulation, albeit simple, captures the most important aspects of evacuations such as the congestion effects of bottlenecks and the time needed to evacuate the endangered area. In the case of an evacuation simulation the network has time-dependent attributes. For instance, large-scale inundations or conflagrations do not cover all the endangered area at once.These time-dependent attributes are modeled as network change events. Network change events are modifying link parameters at predefined points in time. The simulation framework is demonstrated through a case study for the Indonesian city of Padang, which faces a high risk of being inundated by a tsunami.     

Optimization models to characterize the broadcast capacity of vehicular ad hoc networks

Broadcast capacity of the entire network is one of the fundamental properties of vehicular ad hoc networks (VANETs). It measures how efficiently the information can be transmitted in the network and usually it is limited by the interference between the concurrent transmissions in the physical layer of the network. This study defines the broadcast capacity of vehicular ad hoc network as the maximum successful concurrent transmissions. In other words, we measure the maximum number of packets which can be transmitted in a VANET simultaneously, which characterizes how fast a new message such as a traffic incident can be transmitted in a VANET. Integer programming (IP) models are first developed to explore the maximum number of successful receiving nodes as well as the maximum number of transmitting nodes in a VANET. The models embed an traffic flow model in the optimization problem. Since IP model cannot be efficiently solved as the network size increases, this study develops a statistical model to predict the network capacity based on the significant parameters in the transportation and communication networks. MITSIMLab is used to generate the necessary traffic flow data. Response surface method and linear regression technologies are applied to build the statistical models. Thus, this paper brings together an array of tools to solve the broadcast capacity problem in VANETs. The proposed methodology provides an efficient approach to estimate the performance of a VANET in real-time, which will impact the efficacy of travel decision making.     

Behavior-consistent information-based network traffic control for evacuation operations

The evacuation operations problem aims to avoid or mitigate the potential loss of life in a region threatened or affected by a disaster. It is shaped to a large extent by the evolution of evacuation traffic resulting from the demand–supply interactions of the associated transportation network. Information-based control is a strategic tool for evacuation traffic operations as it can enable greater access to the affected population and more effective response. However, comparatively few studies have focused on the implementation of information-based control in evacuation operations. This study develops a control module for evacuation operations centered on addressing the demand–supply interactions by using behavior-consistent information strategies. These strategies incorporate the likely responses of evacuees to the information provided in the determination of route guidance information. The control module works as an iterative computational process involving an evacuee route choice model and a control model of information strategies to determine the route guidance information to direct evacuation traffic so as to approach a desired network traffic flow pattern. The problem is formulated as a fuzzy logic based optimization framework to explicitly incorporate practical concerns related to information dissemination characteristics and social equity in evacuation operations. Numerical experiments highlight the importance of accounting for the demand–supply interactions, as the use of behavior-consistent information strategies can lead evacuee route choices to approach the operator-desired proportions corresponding to the desired traffic pattern. The results also indicate that while a behavior-consistent information strategy can be effective, gaps with the desired route proportions can exist due to the discrete nature of the linguistic messages and the real-world difficulty in accurately modeling evacuees’ actual route choice behavior.     

Leveraging social networks for efficient hurricane evacuation

One of the important factors affecting evacuation performance is the departure time choices made by evacuees. Simultaneous departures of evacuees can lead to overloading of road networks causing congestion. We are especially interested in cases when evacuees subject to little or no risk of exposure evacuate along with evacuees subject to higher risk of threat (also known as shadow evacuation). One of the reasons for correlated evacuee departures is higher perceived risk of threat spread through social contacts. In this work, we study an evacuation scenario consisting of a high risk region and a surrounding low risk area. We propose a probabilistic evacuee departure time model incorporating both evacuee individual characteristics and the underlying evacuee social network. We find that the performance of an evacuation process can be improved by forcing a small subset of evacuees (inhibitors) in the low risk area to delay their departure. The performance of an evacuation is measured by both average travel time of the population and total evacuation time of the high risk evacuees. We derive closed form expressions for average travel time for ER random network. A detailed experimental analysis of various inhibitor selection strategies and their effectiveness on different social network topologies and risk distribution is performed. Results indicate that significant improvement in evacuation performance can be achieved in scenarios where evacuee social networks have short average path lengths and topologically influential evacuees do not belong to the high risk regions. Additionally, communities with stronger ties improve evacuation performance.     

Profit-based maritime container assignment models for liner shipping networks

We propose the problem of profit-based container assignment (P-CA), in which the container shipment demand is dependent on the freight rate, similar to the “elastic demand” in the literature on urban transportation networks. The problem involves determining the optimal freight rates, the number of containers to transport and how to transport the containers in a liner shipping network to maximize the total profit. We first consider a tactical-level P-CA with known demand functions that are estimated based on historical data and formulate it as a nonlinear optimization model. The tactical-level P-CA can be used for evaluating and improving the container liner shipping network. We then address the operational-level P-CA with unknown demand functions, which aims to design a mechanism that adjusts the freight rates to maximize the profit. A theoretically convergent trial-and-error approach, and a practical trial-and-error approach, are developed. A numerical example is reported to illustrate the application of the models and approaches.     

Analysis of hurricane evacuee mode choice behavior

The purpose of this study is to explain the evacuee mode choice behavior of Miami Beach residents using survey data from a hypothetical category four hurricane to reveal different evacuees’ plans. Evacuation logistics should incorporate the needs of transit users and car-less populations with special attention and proper treatment. A nested logit model has been developed to explain the mode choice decisions for evacuees’ from Miami Beach who use non-household transportation modes, such as special evacuation bus, taxi, regular bus, riding with someone from another household and another type of mode denoted and aggregated as other. Specifically, the model explains that the mode choice decisions of evacuees’, who are likely to use different non-household transportation modes, are influenced by several determining factors related to evacuees’ socio-demographics, household characteristics, evacuation destination and previous experience. The findings of this study will help emergency planners and policy-makers to develop better evacuation plans and strategies for evacuees depending on others for their evacuation transportation.     

Network-oriented household activity pattern problem for system optimization

The recently emerging trend of self-driving vehicles and information sharing technologies, made available by private technology vendors, starts creating a revolutionary paradigm shift in the coming years for traveler mobility applications. By considering a deterministic traveler decision making framework at the household level in congested transportation networks, this paper aims to address the challenges of how to optimally schedule individuals’ daily travel patterns under the complex activity constraints and interactions. We reformulate two special cases of household activity pattern problem (HAPP) through a high-dimensional network construct, and offer a systematic comparison with the classical mathematical programming models proposed by Recker (1995). Furthermore, we consider the tight road capacity constraint as another special case of HAPP to model complex interactions between multiple household activity scheduling decisions, and this attempt offers another household-based framework for linking activity-based model (ABM) and dynamic traffic assignment (DTA) tools. Through embedding temporal and spatial relations among household members, vehicles and mandatory/optional activities in an integrated space-time-state network, we develop two 0–1 integer linear programming models that can seamlessly incorporate constraints for a number of key decisions related to vehicle selection, activity performing and ridesharing patterns under congested networks. The well-structured network models can be directly solved by standard optimization solvers, and further converted to a set of time-dependent state-dependent least cost path-finding problems through Lagrangian relaxation, which permit the use of computationally efficient algorithms on large-scale high-fidelity transportation networks.     

Model and a solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation

Allocating movable resources dynamically enables evacuation management agencies to improve evacuation system performance in both the spatial and temporal dimensions. This study proposes a mixed integer linear program (MILP) model to address the dynamic resource allocation problem for transportation evacuation planning on large-scale networks. The proposed model is built on the earliest arrival flow formulation that significantly reduces problem size. A set of binary variables, specifically, the beginning and the ending time of resource allocation at a location, enable a strong formulation with tight constraints. A solution algorithm is developed to solve for an optimal solution on large-scale network applications by adopting Benders decomposition. In this algorithm, the MILP model is decomposed into two sub-problems. The first sub-problem, called the restricted master problem, identifies a feasible dynamic resource allocation plan. The second sub-problem, called the auxiliary problem, models dynamic traffic assignment in the evacuation network given a resource allocation plan. A numerical study is performed on the Dallas–Fort Worth network. The results show that the Benders decomposition algorithm can solve an optimal solution efficiently on a large-scale network.     

Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing

Emerging transportation network services, such as customized buses, hold the promise of expanding overall traveler accessibility in congested metropolitan areas. A number of internet-based customized bus services have been planned and deployed for major origin-destination (OD) pairs to/from inner cities with limited physical road infrastructure. In this research, we aim to develop a joint optimization model for addressing a number of practical challenges for providing flexible public transportation services. First, how to maintain minimum loading rate requirements and increase the number of customers per bus for the bus operators to reach long-term profitability. Second, how to optimize detailed bus routing and timetabling plans to satisfy a wide range of specific user constraints, such as passengers’ pickup and delivery locations with preferred time windows, through flexible decision for matching passengers to bus routes. From a space-time network modeling perspective, this paper develops a multi-commodity network flow-based optimization model to formulate a customized bus service network design problem so as to optimize the utilization of the vehicle capacity while satisfying individual demand requests defined through space-time windows. We further develop a solution algorithm based on the Lagrangian decomposition for the primal problem and a space-time prism based method to reduce the solution search space. Case studies using both the illustrative and real-world large-scale transportation networks are conducted to demonstrate the effectiveness of the proposed algorithm and its sensitivity under different practical operating conditions.     

Distributed model predictive control for railway traffic management

Every day small delays occur in almost all railway networks. Such small delays are often called “disturbances” in literature. In order to deal with disturbances dispatchers reschedule and reroute trains, or break connections. We call this the railway management problem. In this paper we describe how the railway management problem can be solved using centralized model predictive control (MPC) and we propose several distributed model predictive control (DMPC) methods to solve the railway management problem for entire (national) railway networks. Furthermore, we propose an optimization method to determine a good partitioning of the network in an arbitrary number of sub-networks that is used for the DMPC methods. The DMPC methods are extensively tested in a case study using a model of the Dutch railway network and the trains of the Nederlandse Spoorwegen. From the case study it is clear that the DMPC methods can solve the railway traffic management problem, with the same reduction in delays, much faster than the centralized MPC method.     

Managing evacuation networks

This paper proposes a non-anticipative, adaptive, decentralized strategy for managing evacuation networks. The strategy is non-anticipative because it does not rely on demand forecasts, adaptive because it uses real-time traffic information, and decentralized because all the information is available locally. It can be used with a failed communication network.The strategy pertains to networks in which no links backtrack in the direction of increased risk. For these types of networks, no other strategy exists that can evacuate more people in any given time, or finish the evacuation in less time. The strategy is also shown to be socially fair, in the sense that the time needed to evacuate all the people exceeding any risk level is, both, the least possible, and the same as if less-at-risk individuals did not participate in the evacuation. The strategy can be proven optimal even when backflows happen due to driver gaming.     

Analyzing trade-offs between transportation,inventory and production costs on freight networks

The purpose of this paper is to determine optimal shipping strategies (i.e. routes and shipment sizes) on freight networks by analyzing trade-offs between transportation, inventory, and production set-up costs. Networks involving direct shipping, shipping via a consolidation terminal, and a combination of terminal and direct shipping are considered. This paper makes three main contributions. First, an understanding is provided of the interface between transportation and production set-up costs, and of how these costs both affect inventory. Second, conditions are identified that indicate when networks involving direct shipments between many origins and destinations can be analyzed on a link-by-link basis. Finally, a simple optimization method is developed that simultaneously determines optimal routes and shipment sizes for networks with a consolidation terminal and concave cost functions. This method decomposes the network into separate sub-networks, and determines the optimum analytically without the need for mathematical programming techniques.     

Potential-based dynamic pedestrian flow assignment

This study proposes a potential-based dynamic pedestrian flow assignment model to optimize the evacuation time needed for all pedestrians to leave an indoor or outdoor area with internal obstacles and multiple exits, e.g., railway station, air terminal, plaza, and park. In the model, the dynamic loading of pedestrian flows on a two-dimensional space is formulated by a cell transmission model, the movement of crowds is driven by space potential, and the optimization of evacuation time is solved by a proportional swapping process. In this way, the proposed model can be applied to not only efficiently optimize the evacuation process of a crowd with large scale but also recognize local congestion dynamics during crowd evacuation. Finally, a set of numerical examples are presented to show the proposed model’s effectiveness for optimizing crowd evacuation process and its application to design a class of variable guide sign systems.     

Consistent formulation of network equilibrium with stochastic flows

Traffic flows in real-life transportation systems vary on a daily basis. According to traffic flow theory, such variability should induce a similar variability in travel times, but this “internal consistency” is generally not captured by existing network equilibrium models. We present an internally-consistent network equilibrium approach, which considers two potential sources of flow variability: (i) daily variation in route choice and (ii) daily variation in origin–destination demand. We particularly aspire to a flexible formulation that permits alternative statistical assumptions, which allows the best fit to be made to observed variability data in particular applications. Joint probability distributions of route—and therefore link—flows are derived under several assumptions concerning stochastic driver behavior. A stochastic network equilibrium model with stochastic demands and route choices is formulated as a fixed point problem. We explore limiting cases which allow an equivalent convex optimization problem to be defined, and finally apply this method to a real-life network of Kanazawa City, Japan.     

Genetic algorithms approach to the problem of the automated vehicle identification equipment locations

The automated vehicle identification (AVI) equipment location problem entails determination of the best locations for the automated vehicle identification equipment. The paper attempts to solve the AVI equipment location problem as a multi‐objective optimization problem, thus determining the best locations on the basis of several criteria. The developed model is based on genetic algorithms. Testing of the model developed on the greater transportation networks is certainly one of the most important directions for the future research, as much as the development of models based on other metaheuristic approaches (Simulated Annealing, Taboo Search). The results obtained in this stage of the research are promising.     

The treatment of uncertainty in the dynamic origin–destination estimation problem using a fuzzy approach

Regardless of existing types of transportation and traffic model and their applications, the essential input to these models is travel demand, which is usually described using origin–destination (OD) matrices. Due to the high cost and time required for the direct development of such matrices, they are sometimes estimated indirectly from traffic measurements recorded from the transportation network. Based on an assumed demand profile, OD estimation problems can be categorized into static or dynamic groups. Dynamic OD demand provides valuable information on the within-day fluctuation of traffic, which can be employed to analyse congestion dissipation. In addition, OD estimates are essential inputs to dynamic traffic assignment (DTA) models. This study presents a fuzzy approach to dynamic OD estimation problems. The problems are approached using a two-level model in which demand is estimated in the upper level and the lower level performs DTA via traffic simulation. Using fuzzy rules and the fuzzy C-Mean clustering approach, the proposed method treats uncertainty in historical OD demand and observed link counts. The approach employs expert knowledge to model fitted link counts and to set boundaries for the optimization problem by defining functions in the fuzzification process. The same operation is performed on the simulation outputs, and the entire process enables different types of optimization algorithm to be employed. The Box-complex method is utilized as an optimization algorithm in the implementation of the approach. Empirical case studies are performed on two networks to evaluate the validity and accuracy of the approach. The study results for a synthetic network and a real network demonstrate the robust performance of the proposed method even when using low-quality historical demand data.     

On the flexibility of using marginal distribution choice models in traffic equilibrium

Traffic equilibrium models are fundamental to the analysis of transportation systems. The stochastic user equilibrium (SUE) model which relaxes the perfect information assumption of the deterministic user equilibrium is one such model. The aim of this paper is to develop a new user equilibrium model, namely the MDM-SUE model, that uses the marginal distribution model (MDM) as the underlying route choice model. In this choice model, the marginal distributions of the path utilities are specified but the joint distribution is not. By focusing on the joint distribution that maximizes expected utility, we show that MDM-SUE exists and is unique under mild assumptions on the marginal distributions. We develop a convex optimization formulation for the MDM-SUE. For specific choices of marginal distributions, the MDM-SUE model recreates the optimization formulation of logit SUE and weibit SUE. Moreover, the model is flexible since it can capture perception variance scaling at the route level and allows for modeling different user preferences by allowing for skewed distributions and heavy tailed distributions. The model can also be generalized to incorporate bounded support distributions and discrete distributions which allows to distinguish between used and unused routes within the SUE framework. We adapt the method of successive averages to develop an efficient approach to compute MDM-SUE traffic flows. In our numerical experiments, we test the ability of MDM-SUE to relax the assumption that the error terms are independently and identically distributed random variables as in the logit models and study the additional modeling flexibility that MDM-SUE provides on small-sized networks as well as on the large network of the city of Winnipeg. The results indicate that the model provides both modeling flexibility and computational tractability in traffic equilibrium.     

Cooperative traffic control of a mixed network with two urban regions and a freeway

Currently most optimization methods for urban transport networks (i) are suited for networks with simplified dynamics that are far from real-sized networks or (ii) apply decentralized control, which is not appropriate for heterogeneously loaded networks or (iii) investigate good-quality solutions through micro-simulation models and scenario analysis, which make the problem intractable in real time. In principle, traffic management decisions for different sub-systems of a transport network (urban, freeway) are controlled by operational rules that are network specific and independent from one traffic authority to another. In this paper, the macroscopic traffic modeling and control of a large-scale mixed transportation network consisting of a freeway and an urban network is tackled. The urban network is partitioned into two regions, each one with a well-defined Macroscopic Fundamental Diagram (MFD), i.e. a unimodal and low-scatter relationship between region density and outflow. The freeway is regarded as one alternative commuting route which has one on-ramp and one off-ramp within each urban region. The urban and freeway flow dynamics are formulated with the tool of MFD and asymmetric cell transmission model, respectively. Perimeter controllers on the border of the urban regions operating to manipulate the perimeter interflow between the two regions, and controllers at the on-ramps for ramp metering are considered to control the flow distribution in the mixed network. The optimal traffic control problem is solved by a Model Predictive Control (MPC) approach in order to minimize total delay in the entire network. Several control policies with different levels of urban-freeway control coordination are introduced and tested to scrutinize the characteristics of the proposed controllers. Numerical results demonstrate how different levels of coordination improve the performance once compared with independent control for freeway and urban network. The approach presented in this paper can be extended to implement efficient real-world control strategies for large-scale mixed traffic networks.