Search

Given a directed graph (representing a social network), the influence maximization problem is to find k nodes which, when influenced (or activated), would maximize the number of remaining nodes that get activated. In this paper, we consider a more general version of the problem that includes an additional set of nodes, termed as physical nodes, such that a node in the social network is covered by one or more physical nodes. A physical node exists in one of two states at any time, opened or closed, and there is a constraint on the maximum number of physical nodes that can be opened. In this setting, an inactive node in the social network becomes active if it has enough active neighbors in the social network and if it is covered by at least one of the opened physical nodes. This problem arises in disaster recovery, where a displaced social group decides to return after a disaster only after enough groups in its social network return and some infrastructure components in its neighborhood are repaired. The general problem is NP-hard to approximate within any constant factor and thus we characterize optimal and approximation algorithms for special instances of the problem.

We consider a scenario where multiple infrastructure components have been damaged after a disaster and the health value of each component continues to deteriorate if it is not being targeted by a repair agency, until it fails irreversibly. There are multiple agencies that seek to repair the components and there is an authority whose task is to allocate the components to the agencies within a given budget, so that the total number of components that are fully repaired by the agencies is maximized. We characterize the optimal policy for allocation and repair sequencing when the repair rates are sufficiently larger than the deterioration rates. For the case when the deterioration rates are larger than or equal to the repair rates, the rates are homogeneous across the components, and the costs charged by the entities for repair are equal, we characterize a policy for allocation and repair sequencing that permanently repairs at least half the number of components as that by an optimal policy.

We examine a control problem where the states of the components of a system deteriorate after a disruption, if they are not being repaired by an entity. There exist a set of dependencies in the form of precedence constraints between the components, captured by a directed acyclic graph (DAG). The objective of the entity is to maximize the number of components whose states are brought back to the fully repaired state within a given time. We prove that the general problem is NP-hard, and therefore we characterize near-optimal control policies for special instances of the problem. We show that when the deterioration rates are larger than or equal to the repair rates and the precedence constraints are given by a DAG, it is optimal to continue repairing a component until its state reaches the fully recovered state before switching to repair any other component. Under the aforementioned assumptions and when the deterioration and the repair rates are homogeneous across all the components, we prove that the control policy that targets the healthiest component at each time-step while respecting the precedence and time constraints fully repairs at least half the number of components that would be fully repaired by an optimal policy. Finally, we prove that when the repair rates are sufficiently larger than the deterioration rates, the precedence constraints are given by a set of disjoint trees that each contain at most k nodes, and there is no time constraint, the policy that targets the component with the least value of health minus the deterioration rate at each time-step while respecting the precedence constraints fully repairs at least 1/k times the number of components that would be fully repaired by an optimal policy.

We consider a scenario where a system experiences a disruption, and the states (representing health values) of its components continue to reduce over time, unless they are acted upon by a controller. Given this dynamical setting, we consider the problem of finding an optimal control (or switching) sequence to maximize the sum of the weights of the components whose states are brought back to the maximum value. We first provide several characteristics of the optimal policy for the general (fully heterogeneous) version of this problem. We then show that under certain conditions on the rates of repair and deterioration, we can explicitly characterize the optimal control policy as a function of the states. When the deterioration rate (when not being repaired) is larger than or equal to the repair rate, and the deterioration and repair rates as well as the weights are homogeneous across all the components, the optimal control policy is to target the component that has the largest state value at each time step. On the other hand, if the repair rates are sufficiently larger than the deterioration rates, the optimal control policy is to target the component whose state minus the deterioration rate is least in a particular subset of components at each time step.

Hurricanes are costly natural disasters periodically faced by households in coastal and to some extent, inland areas. A detailed understanding of evacuation behavior is fundamental to the development of efficient emergency plans. Once a household decides to evacuate, a key behavioral issue is the time at which individuals depart to reach their destination. An accurate estimation of evacuation departure time is useful to predict evacuation demand over time and develop effective evacuation strategies. In addition, the time it takes for evacuees to reach their preferred destinations is important. A holistic understanding of the factors that affect travel time is useful to emergency officials in controlling road traffic and helps in preventing adverse conditions like traffic jams. Past studies suggest that departure time and travel time can be related. Hence, an important question arises whether there is an interdependence between evacuation departure time and travel time? Does departing close to the landfall increases the possibility of traveling short distances? Are people more likely to depart early when destined to longer distances? In this study, we present a model to jointly estimate departure and travel times during hurricane evacuations. Empirical results underscore the importance of accommodating an inter-relationship among these dimensions of evacuation behavior. This paper also attempts to empirically investigate the influence of social ties of individuals on joint estimation of evacuation departure and travel times. Survey data from Hurricane Sandy is used for computing empirical results. Results indicate significant role of social networks in addition to other key factors on evacuation departure and travel times during hurricanes.

Non-recurrent congestion is a major problem in traffic networks that causes unexpected delays during travels. In such a scenario, it is preferable to use adaptive paths or policies where next link decisions on reaching junctions are continuously adapted based on the information gained with time. In this paper, we study a traffic assignment problem in stochastic time-dependent networks. The problem is modeled as a fixed-point problem and existence of the equilibrium solution is discussed. We iteratively solve the problem using the method of successive averages (MSA). A novel network loading model inspired from Link transmission model is developed that accepts policies as inputs for solving the problem. This network loading model is different from the existing network loading models that take predefined paths for input flows. We demonstrate through numerical tests that solving traffic assignment problem with the proposed loading modeling scheme is more efficient as compared to solving the problem using path-based network loading models.

Congestion pricing has become an effective instrument for traffic demand management on road networks. This paper proposes an optimal control approach for congestion pricing for day-to-day timescale that incorporates demand uncertainty and elasticity. Travelers make the decision to travel or not based on the experienced system travel time in the previous day and traffic managers take tolling decisions in order to minimize the average system travel time over a long time horizon. We formulate the problem as a Markov decision process (MDP) and analyze the problem to see if it satisfies conditions for conducting a satisfactory solution analysis. Such an analysis of MDPs is often dependent on the type of state space as well as on the boundedness of travel time functions. We do not constrain the travel time functions to be bounded and present an analysis centered around weighted sup-norm contractions that also holds for unbounded travel time functions. We find that the formulated MDP satisfies a set of assumptions to ensure Bellman's optimality condition. Through this result, the existence of the optimal average cost of the MDP is shown. A method based on approximate dynamic programming is proposed to resolve the implementation and computational issues of solving the control problem. Numerical results suggest that the proposed method efficiently solves the problem and produces accurate solutions.