Evacuation Transportation Planning Under Uncertainty: A Robust Optimization Approach

Abstract

This paper considers evacuation via surface transportation networks in an uncertain environment. We focus on demand uncertainty which can lead to significant infeasibility cost during evacuation, where loss of life or property may appear. We develop a robust linear programming model based on a robust optimization approach where hard constraints are guaranteed within an appropriate uncertainty set. The robust counterpart solutions have been shown tractable. We show that the robustness in evacuation is important and a robust solution outperforms a nominal deterministic solution in both quality and feasibility.

1 Introduction

Evacuation in extreme events based on large-scale transportation systems is of critical importance. It is challenging to model evacuation in real world transportation network due to the inherent complexity and uncertainty. Moreover, distinct from typical transportation network, transportation network for evacuation bears significant infeasibility cost, resulting from the potential loss of life and property in excrement events. The infeasibility cost refers to the cost incurred when the routing policy is rendered infeasible due to uncertain demand. In a general traffic assignment scenario, the infeasibility cost under uncertain demand is much smaller as compared to an evacuation scenario. Therefore, robust solutions play a major role in evacuation transportation planning.

This paper develops a robust linear programming model based on a robust optimization (RO) approach aiming to provide a robust and tractable framework for evacuation management in large-scale network. The focus is on uncertainty associated with significant infeasibility cost.

In recent years we have experienced dramatic development in the RO approach, in which truly workable and scalable methodologies in both theory and practice have been proposed to deal with optimization under uncertainty. Such tractability progress has been responsible for the blooming success of RO in a broad array of application areas (Ben-Tal et al. 2007; Bertsimas et al. 2007). Specifically, in a departure from the typical nominal optimization where all data are assumed to be known deterministically, the RO approach focuses on data uncertainty related with hard constraints: those that are guaranteed for data within an appropriate prescribed set. It is intuitively clear that there is a “price of robustness”, which is related to the trade-off between robustness and conservativeness (Bertsimas and Sim 2004). In this paper, we show that a robust solution outperforms a nominal deterministic solution in both quality and feasibility in an environment with high infeasibility cost.

While infeasibility costs have been ignored in many transportation studies, our paper provides a new modeling framework based on RO and innovative insights for evacuation management. Our results can be generalized to general decision making under uncertainty settings where significant infeasibility impacts exist.

1.1 Literature review

The evacuation planning problem has enjoyed most attention in the emergency operations literature. Typically, the region to be evacuated is represented as a transportation network, where nodes correspond to the regions and arcs represent the roads. The evacuation plan consists of a flow over time on the transportation network which satisfies the evacuee demand from source nodes to sink nodes. Therefore, the approaches for evacuation planning may come from variety of fields such as dynamic network flows (see Ahuja et al. (2003) for a complete survey on network flow theory), Dynamic Traffic Assignment (DTA) (see Peeta and Ziliaskopoulos (2001) for a review) and simulation (see Mahmassani (2001) for a survey).

In the DTA literature many studies use link performance to propagate traffic. Such functions often tend to overestimate the time required to travel as they are convex functions of flow on the links. An attractive alternative to using link performance functions is Cell Transmission Model (CTM). This model was originally proposed by Daganzo (1994, 1995) to simulate traffic flow based on hydrodynamic flow. The transportation network is decomposed into cells whose length corresponds to the maximum distance that can be traveled in a unit time and given speed. The direction of traffic flow is represented by the connectors. The complete formulation of CTM using a system optimal criterion was presented by Ziliaskopoulos (2000). One of the main advantages of CTM is that it can be formulated as a linear program and therefore computationally tractable. Li et al. (2003) proposed an effective decomposition scheme to reduce computational complexity. Chiu et al. (2007) applied this model to the evacuation problem. Tuydes (2005) has extended standard formulations to include the lane reversibility and temporary capacity increments (also called as “contra-flow”). Although practical significance of CTM has not been explored, the analytical models have a great advantage of using the existing theory on Linear Programming (LP).

Most research in DTA has assumed deterministic input parameters. There has been sparse literature on the inherent stochastic nature of parameters. This is surprising because demand uncertainty, capacity reductions and implementation errors of the optimal solution may have a drastic impact on the optimality and even the feasibility of the solution. Peeta and Zhou (1999) subjected the deterministic model to a number of randomly generated demand samples so as to gain insights. But such a sampling approach may be prohibitively expensive as a large number of samples are required to establish any statistical significance. Waller and Ziliaskopoulos (2006) applied chance constrained programming and assumed a known distribution of the demand. Karoonsoontawong and Waller (2007) consider a scenario-based robust optimization (Mulvey et al. 1995) by modeling the trade-off between optimality robustness and model robustness. Ukkusuri and Waller (2008) describe a two stage stochastic programming with recourse model. These approaches provide a relaxation of constraints and treat actually soft constraints (Ben-Tal and Nemirovski 1999).

In this paper, we focus on evacuation under uncertainty associated with hard constraints. These constraints must be satisfied and can lead to significant infeasibility cost during evacuation, where loss of life or property may appear. We develop a robust linear programming model based on a RO approach.

The idea of RO is not new, as Soyster (1973) first studied it. His paper considers a linear programming case where the column vectors from the constraint coefficient matrix are within prescribed convex sets. Unfortunately, the column-wise uncertainty case is extremely conservative which means that too much optimality has been traded off to guarantee robustness. The issue of robustness was relatively silent in the optimization community until the recent works of Ben-Tal and Nemirovski (1998, 1999, 2000), Ghaoui et al. (1997, 2003) and Bertsimas and Sim (2003, 2004). These papers make a significant step forward and propose less conservative models by considering tractable robust counterparts for nominal problems (Ben-Tal and Nemirovski 2002). These works, with the development of efficient interior point algorithms for convex optimization and improvements in computation technology, have provided computational tractability for RO in both theory and practice, and hence have reinvigorated a sudden burst of interest in the RO field. For applications of RO to the problems of transportation systems, refer to Ordonez and Zhao (2007), Atamturk and Zhang (2007), Mudchanatongsuk et al. (2008) and Erera et al. (2007)

In the remaining of this paper, we will develop a deterministic linear programming (DLP) evacuation model in the line of CTM by incorporating the infeasible cost (Section 2). We then present and analyze a robust solution by developing the robust counterpart formulation of the DLP to consider data uncertainty (Section 3). To overcome the conservativeness of the robust solution, inequality flow control constraint is proposed in section 4. We present numerical examples in section 5 and conclude in section 6.

2 Cell transmission model for evacuation planning

In this section we present the deterministic evacuation planning model. Our focus is on the importance of robustness by analyzing the impact of infeasibility of an evacuation model. The DLP formulation will be a generalization of the traditional CTM model (Chiu et al. 2007; Ziliaskopoulos 2000). A typical CTM objective is a measure of the total time taken for all evacuees to reach a safe destination. But, in an evacuation scenario not all places are equally prone to the disaster. For example, the direction of hurricane determines the areas of evacuation region which have to be evacuated before any other. In addition, as the hurricane changes direction, the threat level faced by evacuees changes across time. We introduce a measure called, coefficient of threat level, which is an estimate of the susceptibility of an area to disaster at a particular time. Such a generalization allows us to capture spatial-temporal priorities during evacuation. While this coefficient of threat level is assumed to be constant across space and time in a traditional CTM objective, such a modification provides a natural way to incorporate infeasibility cost into the objective function, hence opens the door to study the significance of robustness. More importantly, such modification presents a unique way to compare robust solution with nominal solution and leads to interesting results discussed in section 5. In this paper, we focus on demand uncertainty, however, this modeling framework can be extended to study the effect of uncertainty in other factors including capacity, cost, or threat levels.

The cell transmission model, named by Daganzo (1994, 1995), models freeway traffic flow using a finite difference approximation of the kinematic wave model. Such a model naturally incorporates congestion effect in traffic flows via shock waves in fluid flow. The finite difference approximation ensures piecewise linear dependence between traffic flow and density on the link which forms the foundation for linear programming based approaches. More formally, let q and k denote the traffic flow and density on a link in a traffic network. The following equation describes the relationship between q and k in terms of v (free flow velocity), k_max (maximum possible density), w (velocity of shock wave) and q_max (maximum allowable flow on the link).

$$ q = \min \left( {vk,q_{{\max }}, w\left( {k_{{\max }} - k} \right)} \right) $$

Based on the free flow velocity and length of discrete time step, a segment of a freeway is decomposed into cells so that traffic can move only to adjacent cells in unit time. The connectors between cells are dummy arcs indicating the direction of flow between cells. Ziliaskopoulos (2000) extends the original CTM model of Daganzo by formulating the DTA problem as a linear program. We introduce an adjacency matrix A = [a_ij], for ease of notation. The adjacency matrix represents the connectivity of the cells in the cell based transmission model. More formally, it is defined as follows

$$ a_{ij} = \left\{ {\begin{array}{*{20}c} 1 & {{\text{cell }}i\,{\text{is}}\,{\text{connected}}\,{\text{to cell}}\,j} \\ 0 & {\text{else}} \ \end{array}} \right. $$

The notations are given as below:

$\Im$ :

set of time intervals, {1,...T}

C:

set of cells, {1,...I}

C_S :

set of sink cells

C_R :

set of source cells

A:

adjacency matrix representing transportation network connectivity.

$c_i^t$ :

weight proportional to the threat level experienced by the evacuees in cell i at time t

$x_i^t$ :

number of evacuees contained in cell i at time t

$y_{ij}^t$ :

number of evacuees flowing from cell i to cell j at time t

$d_i^t$ :

demand generated in cell i at time t

$N_i^t$ :

capacity of cell i at time t

$Q_i^t$ :

inflow/outflow capacity of cell i at time t

$\delta_i^t$ :

traffic flow parameter for cell i at time t

$\hat{x}_i$ :

initial occupancy of cell i

Based on these notations, we present the DLP model:

$$ \begin{array}{*{20}c} {\begin{array}{*{20}c} {\mathop {Min}\limits_{x,y} \sum\limits_{{t \in \Im }} {\sum\limits_{{i \in C\backslash C_s }} {c_i^t x_i^t } } } & {\left( {\text{M - DLP}} \right)} \\ \end{array} } \hfill \\ {subject~to} \hfill \\ {\begin{array}{*{20}c} {x_i^t - x_i^{t - 1} - \sum\limits_{{k \in C}} {a_{ki} y_{ki}^{t - 1} } + \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{t - 1} } = d_i^{t - 1} } & {\forall i \in C\, t \in \Im } \\ \end{array} } \hfill \\ \end{array} \quad $$

(1)

$$\begin{array}{*{20}c}{{{\sum\limits_{k \in C} {a_{{ki}} } }y^{t}_{{ki}} \leqslant Q^{t}_{i} }} & {{\forall i \in C}} & {{t \in {\Im }}} \\ \end{array} $$

(2)

$$\begin{array}{*{20}c} {{{\sum\limits_{k \in C} {a_{{ki}} } }y^{t}_{{ki}} + \delta ^{t}_{i} x^{t}_{i} \leqslant \delta ^{t}_{i} N^{t}_{i} }} & {{\forall i \in C}} & {{t \in {\Im }}} \\ \end{array} $$

(3)

$$\begin{array}{*{20}c} {{{\sum\limits_{j \in C} {a_{{ij}} } }y^{t}_{{ij}} \leqslant Q^{t}_{i} }} & {{\forall i \in C}} & {{t \in {\Im }}} \\ \end{array} $$

(4)

$$\begin{array}{*{20}c} {{{\sum\limits_{j \in C} {a_{{ij}} } }y^{t}_{{ij}} - x^{t}_{i} \leqslant 0}} & {{\forall i \in C}} & {{t \in {\Im }}} \\ \end{array} $$

(5)

$$\begin{array}{*{20}c} {{x^{0}_{i} = \widehat{x}_{i} }} & {{\forall i \in C}} \\ \end{array}$$

(6)

$$ \begin{array}{*{20}c} {y_{ij}^0 = 0} & {\forall \left( {i,j} \right) \in C \times C} \\ \end{array} $$

(7)

$$ \begin{array}{*{20}c} {x_i^t \ge 0} & {\forall i \in C} & {t \in \Im } \\ \end{array} $$

(8)

$$ \begin{array}{*{20}c} {y_{ij}^t \ge 0} & {\forall \left( {i,j} \right) \in C \times C} & {t \in \Im } \\ \end{array} $$

(9)

In the objective function of this model, we minimize the evacuees’ total threat exposure. Equation (1) refers to the flow constraint in cell i at time t. Equation (2) represents that the total inflow into a cell is bounded by the inflow capacity. Equation (3) ensures that the total inflow is bounded by the remaining capacity of the cell. Similarly, total outflow from a cell is bounded by outflow capacity and the current occupancy of that cell which are represented by Eq. (4) and Eq. (5) respectively. The remaining constraints, from (6) to (9), reflect the initial conditions and non-egativity conditions.

The M-DLP can be reduced and reformulated by eliminating state variable $x_i^t$ and redundant constraints such as Eqs. (1), (6) and (8). Since $\sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } - x_i^t \le 0$, $y_{ij}^t \ge 0$ and $a_{ij} \ge 0$, it is evident that $0 \le \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } \le x_i^t$ and, in that reason, the non-negativity constraint of $x_i^t$, Eq. (8), is redundant. Also, in general, $x_i^t$ can be represented as $x_i^t = \hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + d_i^{{t\prime }} } \right)}$by applying the Eqs. (1) and (6) recursively. Thus, we can get the following equivalent DLP formulation:

$$ \begin{gathered} \begin{array}{*{20}c} {\begin{array}{*{20}c} {\mathop {Min}\limits_{y,z} z} \hfill & {\left( {\text{M - DLP2}} \right)} \hfill \\ \end{array} } \hfill \\ {subject~to} \hfill \\ {\sum\limits_{{t \in \Im }} {\sum\limits_{{i \in C\backslash C_s }} {c_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + d_i^{{t\prime }} } \right)} } \right)} } \le z} \hfill \\ \end{array} \hfill \\ \begin{array}{*{20}c} {\begin{array}{*{20}c} {\begin{array}{*{20}c} {\left. {\begin{array}{*{20}c} {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } \le Q_i^t } \hfill \\ {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } + \delta_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + d_i^{{t\prime }} } \right)} } \right) \le \delta_i^t N_i^t } \hfill \\ {\sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } \le Q_i^t } \hfill \\ {\sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } - \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + d_i^{{t\prime }} } \right)} } \right) \le 0} \hfill \\ \end{array} } \right\}} \hfill \\ \begin{gathered} \begin{array}{*{20}c} {y_{ij}^0 = 0} & {\forall \left( {i,j} \right) \in C \times C} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {y_{ij}^t \ge 0} & {\forall \left( {i,j} \right) \in C \times C} & {t \in \Im } \\ \end{array} \hfill \\ \end{gathered} \hfill \\ \end{array} } \hfill \\ \end{array} } \hfill \\ \end{array} \begin{array}{*{20}c} {i \in C} & {t \in \Im } \\ \end{array} \hfill \\ \end{gathered} $$

Note that the capacities of source and sink cells are assumed to be infinite, i.e., $N_i^t = \infty, \forall i \in \left( {C_{{S\,}} \cup C_R } \right)$. Also, demands are zero everywhere except source cells, i.e., $d_i^t = 0,\forall i \in C\backslash C_R$.

In order to account for the infeasibility due to uncertainty in demand, our model incorporates the infeasibility cost in the cost parameter, $c_i^t$. We penalize an evacuation plan which leaves any evacuees behind at the end of time horizon, T, i.e.

$$ c_i^t = \left\{ {\begin{array}{*{20}c} 1 & {i \in C\backslash C_s, t \ne T} \\ M & {i \in C\backslash C_s, t \ne T} \ \end{array}} \right. $$

(10)

where M is assumed to be a positive large number to represent the infeasibility cost. This reformulation provides an appropriate way to analyze the consequences of data uncertainty with a focus on the impact of infeasibility cost.

This introduction of time dependent cost coefficients is distinct from the penalty function proposed by Mulvey et al. (1995). In their paper, the slack variables for each constraint appear in the objective function. A scenario-based robust optimization approach is used, hence the violation of constraints may still be observed. In contrast, we develop a set-based robust optimization approach where feasibility in a prescribed uncertainty set is guaranteed. While Chiu et al. (2007) consider “no-notice evacuation” (Pearce 2008) by focusing on deterministic demand realized at time 0, the present model can also be used for short-notice evacuation (hurricane, wildfire, and flooding) by considering time dependent demand.

In the model shown above, we study the effect of uncertain demand information. Our basic aim is to study the effect of uncertain demand on the value of the objective function. We assume the demand d belong to a prescribed uncertainty set U _d.

To simplify the notation, in order to address demand uncertainty, we can denote the objective function V(y, d), as a function of flow on the links, y, and the demand variable, d.

Given a deterministic demand d∈U _d, the nominal solution

$$ y_N = y_N \left( d \right) \equiv \arg \,\mathop {\min }\limits_y \,V\left( {y,d} \right) $$

(11)

Proposition 1

The nominal solution for a deterministic demand is not necessarily optimal when the demand changes.

Proof

From (11), we have $V\left( {y_N \left( {d_1 } \right),d_1 } \right) \le V\left( {y_N \left( {d_2 } \right),d_1 } \right),\forall d_1, d_2 \in U_d .\, ■$

We would like to show that relatively small uncertainty in demand information can lead to severe sub optimality or even infeasibilities with respect to the nominal solution. For example, if more traffic is allowed between cells then will it lead to infeasibility of the overall solution? We will conduct experiments to verify such hypothesis based on a numerical example suggested by Chiu et al. (2007) in section 5.

3 Robust optimization formulation of CTM

It is clear that uncertainty needs to be taken into account to create a robust evacuation plan. In this paper, we develop a RO methodology to deal with uncertainty and illustrate this approach with demand uncertainty.

Given the defined demand uncertainty set U _d, the RC of the M-DLP2 is formulated as shown below

$$ \begin{gathered} \mathop {Min}\limits_{y,z} z~\left( {\text{M - RC}} \right) \hfill \\ subject~to \hfill \\ \begin{array}{*{20}c} {\sum\limits_{{t \in \Im }} {\sum\limits_{{i \in CC\backslash C_s }} {c_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + d_i^{{t\prime }} } \right)} } \right)} } \le z} & {\forall d_i^t \in U_d } \\ \end{array} \hfill \\ \left. \begin{gathered} \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } \le Q_i^t ~ \hfill \\ \begin{array}{*{20}c} {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } + \delta_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + d_i^{{t\prime }} } \right)} } \right) \le \delta_i^t N_i^t } & {\forall d_i^t \in U_d } \\ \end{array} ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } \le Q_i^t ~ \hfill \\ \begin{array}{*{20}c} {\sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } - \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + d_i^{{t\prime }} } \right)} } \right) \le 0} & {\forall d_i^t \in U_d } \\ \end{array} ~ \hfill \\ \end{gathered} \right\}i \in C~t \in \Im \hfill \\ \begin{array}{*{20}c} {y_{ij}^0 = 0} & {\forall \left( {i,j} \right) \in C \times C} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {y_{ij}^t \ge 0} & {\forall \left( {i,j} \right) \in C \times C} & {t \in \Im } \\ \end{array} ~ \hfill \\ \end{gathered} $$

We note that M-RC is a semi-infinite problem and has infinitely many constraints. The following theorems show that it can be converted into a tractable equivalent deterministic problem.

Theorem 1

Given that U _d is polyhedral set $\left\{ {\bar{d} + \theta d:Ad \le b,d \ge 0} \right\}$ where $\bar{d} \in R^{{\left( {I \times T} \right)}}$ , $d \in R^{{\left( {I \times T} \right)}}$ , $\theta \in R^{{\left( {I \times T} \right)}}$ , $A \in R^{{m \times \left( {I \times T} \right)}}$ and b∈R ^m, the robust counterpart with uncertain demand data is equivalent to the following deterministic problem.

$$ \begin{gathered} \mathop {Min}\limits_{{y,\lambda, z}} z~\left( {\text{M - RC1}} \right) \hfill \\ subject~to \hfill \\ \sum\limits_{{t \in \Im }} {\sum\limits_{{i \in CC\backslash C_s }} {c_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} } \right)} } \right)} } + \sum\limits_{{m\prime = 1}}^m {\lambda_{{m\prime }}^1 \beta_{{m\prime }} } \le z~ \hfill \\ \begin{array}{*{20}c} {\sum\limits_{{m\prime = 1}}^m {\lambda_{{m\prime }}^1 \alpha_{{m\prime, \left( {i\prime, t\prime } \right)}} } \ge \sum\limits_{{t \in \Im }} {c_{{i\prime }}^t \theta_{{i\prime }}^{{t\prime }} } } & {\forall i\prime \in C,t\prime \in \Im } \\ \end{array} \hfill \\ \begin{array}{*{20}c} {\lambda_{{m\prime }}^1 \ge 0} & {\quad \quad \quad \quad \quad \quad \forall m\prime \in \left\{ {1,..,m} \right\}} \\ \end{array} \hfill \\ \left. \begin{gathered} \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } \le Q_i^t ~ \hfill \\ \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } + \delta_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} } \right)} } \right) + \sum\limits_{{m\prime = 1}}^m {\lambda_{{m\prime it}}^2 \beta_{{m\prime }} } \le \delta_i^t N_i^t \hfill \\ \begin{array}{*{20}c} {\sum\limits_{{m\prime = 1}}^m {\lambda_{{m\prime i}}^{2t} \alpha_{{m\prime, (i\prime, t\prime )}} } \ge \sum\limits_{{t \in \Im }} {\delta_i^t \theta_i^{{t\prime }} } } & {\forall i\prime \in C,t\prime \in \Im, i\prime = i} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {\sum\limits_{{m\prime = 1}}^m {\lambda_{{m\prime i}}^{2t} \alpha_{{m\prime, (i\prime, t\prime )}} } \ge 0} & {\quad \quad \,\,\,\forall i\prime \in C,t\prime \in \Im, i\prime \ne i} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {\lambda_{{m\prime i}}^{2t} \ge 0\,} & {\quad \quad \quad \quad \quad \quad \,\,\forall m\prime \in \left\{ {1,..,m} \right\}} \\ \end{array} ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } \le Q_i^t ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } - \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} } \right)} } \right) + \sum\limits_{{m\prime = 1}}^m {\lambda_{{m\prime it}}^3 \beta_{{m\prime }} } \le 0~ \hfill \\ \begin{array}{*{20}c} {\sum\limits_{{m\prime = 1}}^m {\lambda_{{m\prime i}}^{3t} \alpha_{{m\prime, (i\prime, t\prime )}} } \ge \sum\limits_{{t \in \Im }} { - \delta_i^t \theta_i^{{t\prime }} } } & {\forall i\prime \in C,t\prime \in \Im, i\prime = i} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {\sum\limits_{{m\prime = 1}}^m {\lambda_{{m\prime i}}^{3t} \alpha_{{m\prime, (i\prime, t\prime )}} } \ge 0} & {\quad \quad \quad \forall i\prime \in C,t\prime \in \Im, i\prime \ne i} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {\lambda_{{m\prime i}}^{3t} \ge 0} & {\quad \quad \quad \quad \quad \quad \,\,\,\,\,\forall m\prime \in \left\{ {1,..,m} \right\}} \\ \end{array} \hfill \\ \end{gathered} \right\}i \in C~t \in \Im \hfill \\ \begin{array}{*{20}c} {y_{ij}^0 = 0} & {\forall \left( {i,j} \right) \in C \times C} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {y_{ij}^t \ge 0} & {\forall \left( {i,j} \right) \in C \times C} & {t \in \Im } \\ \end{array} \hfill \\ \end{gathered} $$

where α_{m′,(i′,t′)} and β _m′ are entries of A and b respectively.

Proof

For notational simplicity, the each constraint affected by the demand uncertainty of M-RC can be generalized by $\sum\limits_{i = 1}^I {c_i d_i } \le \alpha$ for $\forall d_i \in U_d = \left\{ {\bar{d} + \theta d:Ad \le b,d \ge 0} \right\}$. The equation is equivalent to $\mathop {Max}\limits_{{d_i }} \left( {\sum\limits_{i = 1}^I {c_i d_i } } \right) \le \alpha$ where $d_i \in U_d = \left\{ {\bar{d} + \theta d:Ad \le b,d \ge 0} \right\}$.

Then, we consider the following primal linear programming (P) and dual linear programming (D).

$$ \begin{gathered} \begin{array}{*{20}c} {\mathop {Max}\limits_d \sum\limits_i {c_j \left( {\bar{d}_j + \theta_j d_j } \right)} } & {\left( {\text{P}} \right)} \ \hfill \\ subject\ to \hfill \\ \sum\limits_j {\alpha_{ij} d_j } \le \beta_i \hfill \\ d_j \ge 0 \hfill \\ \end{array} \end{gathered} $$

$$ \begin{gathered} \begin{array}{*{20}c} {\mathop {Min}\limits_d \sum\limits_j {c_j \bar{d}_j + } \sum\limits_i {\lambda_i \beta_i } } & {\left( {\text{D}} \right)} \ \hfill \\ s.t.\sum\limits_i {\lambda_i \alpha_{ij} } \ge c_j \theta_j \hfill \\ \lambda_i \ge 0 \hfill \\\end{array} \end{gathered} $$

where λ _t is dual variable.

Note that based on the fundamental theorem of duality (Bazaraa et al. 2005), one of the followings is true

• (1) If one problem has an optimal solution, then the other problem also has an optimal solution and two values are equal.

• (2) If one problem has a bounded optimal solution, then the other problem is infeasible.

• (3) Both problems are infeasible.

Therefore, if M-RC has an optimal solution, the dual linear programming M-RC1 has an equal optimal solution. M-RC1 is a linear programming problem, hence is tractable. ■

Below we present similar results for ellipsoid and box uncertainty set.

Theorem 2

Given that U _d is ellipsoid set $\left\{ {d:\left( {d - \bar{d}} \right)S^{- 1} \left( {d - \bar{d}} \right) \le \theta^2 } \right\}$ where $\bar{d} \in R^{{\left( {I \times T} \right)}}$ , $d \in R^{{\left( {I \times T} \right)}}$ , $\theta \in R^1$ and $S \in R^{{\left( {I \times T} \right) \times \left( {I \times T} \right)}}$ , the robust counterpart with uncertain demand data is equivalent to the following deterministic problem

$$ \begin{gathered} \begin{array}{*{20}c} {\mathop {Min}\limits_{y,z} z} & {\left( {\text{M - RC2}} \right)} \\ \end{array} \hfill \\ subject~to \hfill \\ \sum\limits_{{t \in \Im }} {\sum\limits_{{i \in C\backslash C_s }} {c_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} } \right)} } \right)} } + \theta \sqrt {C_1^T SC_1 } \le z~ \hfill \\ \left. \begin{gathered} \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } \le Q_i^t ~ \hfill \\ \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } + \delta_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} } \right)} } \right) + \theta \sqrt {C_{2it}^T SC_{2it} } \le \delta_i^t N_i^t ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } \le Q_i^t ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } - \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} } \right)} } \right) + \theta \sqrt {C_{3it}^T SC_{3it} } \le 0~ \hfill \\ \end{gathered} \right\}i \in C~t \in \Im \hfill \\ \begin{array}{*{20}c} {y_{ij}^0 = 0} & {\forall \left( {i,j} \right) \in C \times C} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {y_{ij}^t \ge 0} & {\forall \left( {i,j} \right) \in C \times C} & {t \in \Im } \\ \end{array} \hfill \\ \end{gathered} $$

where C ₁∈R ^(I×T) is a matrix, of which (i′,t′)th entries are $\sum\limits_{{t \in \Im }} {c_{{i\prime }}^t }$ C _2it ∈R ^(I×T) is a matrix, of which (i′,t′)th entries are $\delta_{{i\prime }}^{{t\prime }}$ if i = i′, otherwise 0, C _3it ∈R ^(I×T) is a matrix, of which (i′,t′)th entries are $- \delta_{{i\prime }}^{{t\prime }}$ if i = i′, otherwise 0.

Proof

Similar to the proof of Theorem 1, an equivalent formulation of the each constraint affected by the demand uncertainty becomes $\mathop {Max}\limits_d \left( {\sum\limits_{i = 1}^I {c_i d_i } } \right) \le \alpha$ where $d \in U_d = \left\{ {\left( {d - \bar{d}} \right)S^{- 1} \left( {d - \bar{d}} \right) \le \theta^2 } \right\}$ and our interest is the optimal solution of the following mathematical programming

$$ \begin{gathered} \mathop {Max}\limits_d \sum\limits_{i = 1}^I {c_i d_i } \hfill \\ subject\ to \hfill \\ \left( {d - \bar{d}} \right)S^{- 1} \left( {d - \bar{d}} \right) \le \theta^2 \hfill \\ \end{gathered} $$

By the Karush-Kuhn-Tucker (KKT) conditions, the solution of the problem is $d = \bar{d} + \frac{\theta }{{\sqrt {C^T SC} }}SC$ and $\mathop {Max}\limits_d \sum\limits_{i = 1}^I {c_i d_i } = \sum\limits_i {c_i \bar{d}_i } + \theta \sqrt {C^T SC} \le \alpha$ where C∈R ^I is a matrix, of which (i)th entries are C _i

Now, we have following relationship and M-RC2 can be formulated.

$$ \sum\limits_{i = 1}^I {c_i d_i } \le \alpha\ \forall d_i \in U_d = \left\{ {\left( {d - \bar{d}} \right)S^{- 1} \left( {d - \bar{d}} \right) \le \theta^2 } \right\} \Leftrightarrow \sum\limits_i {c_i \bar{d}_i } + \theta \sqrt {C^T SC} \le \alpha \, ■ $$

To illustrate the RO approach, let’s consider a box uncertainty set

$$ U_d \equiv \left[ {\bar{d}\left( {1 - \theta } \right),\bar{d}\left( {1 + \theta } \right)} \right] $$

(12)

where $\bar{d}_i^t$ is the nominal demand in cell i at time t. As shown in Theorem 1–2, this simple interval uncertainty set can be extended into more general form of uncertainty set. (see Bertsimas et al. (2007) for a survey).

Theorem 3

Given that U _d is box set $\left\{ {d:\bar{d}\left( {1 - \theta } \right) \le d \le \bar{d}\left( {1 + \theta } \right)} \right\}$ where $\bar{d} \in R^{{\left( {I \times T} \right)}}$ , d∈R ^(I×T) , θ∈R ^(I×T) , the robust counterpart with uncertain demand data is equivalent to the following deterministic problem

$$ \begin{gathered} \begin{array}{*{20}c} {\mathop {Min}\limits_{y,z} z} & {\left( {\text{M - RC3}} \right)} \\ \end{array} \hfill \\ subject~to \hfill \\ \sum\limits_{{t \in \Im }} {\sum\limits_{{i \in C\backslash C_s }} {c_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} \left( {1 + \theta_i^{{t\prime }} } \right)} \right)} } \right)} } \le z \hfill \\ \left. \begin{gathered} \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } \le Q_i^t ~ \hfill \\ \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } + \delta_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} \left( {1 + \theta_i^{{t\prime }} } \right)} \right)} } \right) \le \delta_i^t N_i^t ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } \le Q_i^t ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } - \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ki} y_{ki}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} } + \bar{d}_i^{{t\prime }} \left( {1 + \theta_i^{{t\prime }} } \right)} \right)} } \right) \le 0~ \hfill \\ \end{gathered} \right\}i \in C~t \in \Im \hfill \\ \begin{array}{*{20}c} {y_{ij}^0 = 0} & {\forall \left( {i,j} \right) \in C \times C} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {y_{ij}^t \ge 0} & {\forall \left( {i,j} \right) \in C \times C} & {t \in \Im } \\ \end{array} \hfill \\ \end{gathered} $$

Proof

Note the following relation for any real numbers u_i and v (see Ben-Tal et al. (2004) for more details).

$$ \begin{array}{*{20}c} {\sum\limits_{{\tau \in I_t }} {d_i^{\tau } u_i^{\tau } \le v} } & {\forall d_i^{\tau } \in \left\{ {\bar{d}_i^{\tau } \left( {1 - \theta_i^{\tau } } \right) \le d \le \bar{d}_i^{\tau } \left( {1 + \theta_i^{\tau } } \right)} \right\} \Leftrightarrow \sum\limits_{{\tau \in I_t }} {\bar{d}_i^{\tau } \left( {u_i^{\tau } + \theta_i \left| {u_i^{\tau } } \right|} \right) \le v} } \\ \end{array} $$

(13)

Using the equivalence of equations, we can obtain M-RC3. ■

Robust optimal solution can be interpreted as the solution being feasible for any realization of the uncertain data and achieving best worst case objective value. In other words, the objective value (z ^RC, i.e., z in (M-RC)) of RC is guaranteed for any demand realization within an appropriate uncertainty set. Hence, z ^RCis an upper bound of a realized objective value (z ^R−RC). The realized robust objective value (z ^R−RC) refers to the objective value we can obtain when the robust optimal solution (y _RC) is used and a data scenario (d) is realized i.e. z ^R−RC=V(y _RC, d) (see proposition 1). However, in some cases, RC is only feasible at unrealistic small uncertainty level or generates too conservative solution (Ben-Tal et al. 2004, 2005).

Proposition 2

If the least demand is realized and the ideal solution exists, realized robust objective value (z ^R-RC ) is equal to the ideal objective value (z ^Least ).

Proof

Let us consider the constraints for source nodes.

$$ \begin{array}{*{20}c} {\sum\limits_{{t \in \Im }} {\sum\limits_{{i \in C\backslash C_{s} }} {c_{i}^{t} \left( {\hat{x}_{i} + \sum\limits_{{t\prime = 0}}^{{t - 1}} {\left( {\sum\limits_{{k \in C}} {a_{{ki}} y_{{ki}}^{{t\prime }} } - \sum\limits_{{j \in C}} {a_{{ij}} y_{{ij}}^{{t\prime }} } + \bar{d}_{i}^{{t\prime }} \left( {1 + \theta _{i}^{{t\prime }} } \right)} \right)} } \right)} } \le z} \\ {\begin{array}{*{20}c} {\sum\limits_{{j \in C}} {a_{{ij}} y_{{ij}}^{t} \le Q_{i}^{t} } } & {i \in C_{R} \quad t \in \Im } \\ \end{array} } \\ \end{array} $$

(14)

$$ \begin{array}{*{20}c} {\begin{array}{*{20}c} {\sum\limits_{{j \in C}} {a_{{ij}} y_{{ij}}^{t} } - \left( {\hat{x}_{i} + \sum\limits_{{t\prime = 0}}^{{t - 1}} {\left( {\sum\limits_{{j \in C}} {a_{{ij}} y_{{ij}}^{{t\prime }} } + \bar{d}_{i}^{{t\prime }} \left( {1 + \theta _{i}^{{t\prime }} } \right)} \right)} } \right) \le 0} & {i \in C_{R} \quad t \in \Im } \\ \end{array} } \\ {\begin{array}{*{20}c} {y_{{ij}}^{0} = 0} & {\forall \left( {i,j} \right) \in C \times C} \\ \end{array} } \\ {\begin{array}{*{20}c} {y_{{ij}}^{t} \ge 0} & {\forall \left( {i,j} \right) \in C \times C} & {t \in \Im } \\ \end{array} } \\ \end{array} $$

(15)

Equations (14) and (15) are related to the uncertain demand. The constraint (15) is equivalent to $\sum\limits_{{t\prime = 0}}^t {\sum\limits_{{j \in C}} {a_{ij} y_{ij}^{{t\prime }} \le \hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\bar{d}_i^{{t\prime }} \left( {1 - \theta } \right)} } }$, which means total number of evacuees from a source node i at time t cannot exceed the sum of initial occupancy of the source node and total minimum demands until time t-1. In other words, any additional demand $\varepsilon_i^{{t\prime }} \in \left( {0,2\theta_i^{{t\prime }} } \right)$ exceeding possible minimum demand $\bar{d}_i^{{t\prime }} \left( {1 - \theta_i^{{t\prime }} } \right)$ cannot be controlled by the RC. In that reason, the constraint (14) can be reformulated as $\sum\limits_{{t \in T}} {\sum\limits_{{i \in C\backslash C_s }} {c_i^t \left( {\hat{x}_i + \sum\limits_{{t\prime = 0}}^{t - 1} {\left( {\sum\limits_{{k \in C}} {a_{ij} y_{ij}^{{t\prime }} + } \bar{d}_i^{{t\prime }} \left( {1 - \theta_i^{{t\prime }} } \right)} \right)} } \right)} + \sum\limits_{{t \in {\text{T}}}} {\sum\limits_{{i \in C}} {\sum\limits_{{t\prime = 0}}^{t - 1} {c_i^t \varepsilon_i^{{t\prime }} \le z} } } }$. Finally, we conclude that $z^{RC} = z^{Least} + \sum\limits_{{t \in {\text{T}}}} {\sum\limits_{{i \in C}} {\sum\limits_{{t\prime = 0}}^{t - 1} {2c_i^t \theta_i^{{t\prime }} } } }$ and $z^{R - RC} = z^{Least} + \sum\limits_{{t \in {\text{T}}}} {\sum\limits_{{i \in C}} {\sum\limits_{{t\prime = 0}}^{t - 1} {2c_i^t \varepsilon_i^{{t\prime }} } } }$ when uncertain demand data $\varepsilon_i^{{t\prime }} \in \left( {0,2\theta_i^{{t\prime }} } \right)$ are realized. Also, z ^R−RC becomes z ^Least when the least demands are realized. ■

Proposition 2 also shows that RC is always feasible as long as z ^Least exists. However, as the uncertainty level increases, it becomes too conservative to adopt the solution in the real world. In some sense, the solution may be worthless since we have to give up the evacuation to find the uncertainty immunized solution. In the next section, we will show that an inequality constraint will improve the performance of the robust solution.

4 Robust counterpart of CTM with inequality flow control constraint

Retuning to our CTM based evacuation problem (M-DLP), let’s recall the flow control constraint, Eq. (1). The demand equality constraint Eq. (1) can be written as an inequality constraint $x_i^t - x_i^{t - 1} - \sum\limits_{{k \in C}} {a_{ki} } y_{ki}^{t - 1} + \sum\limits_{{j \in C}} {a_{ij} } y_{ij}^{t - 1} \ge d_i^{t - 1}$ (e.g., Ukkusuri and Waller 2008). Clearly, for a given deterministic demand $d_i^t = \bar{d}_i^t$, the inequality flow control constraint is always binding and therefore becomes an equality based flow constraint. However, the actual realized demand can be lower or higher than the expected anticipated demand, $\bar{d}_i^t$. Intuitively, if the realized demand is lower than expected, the nominal solution should remain feasible by allocating the realized demand proportionally to the planned routes. Therefore, we formulate the flow constraint as an inequality to accommodate for uncertainty in demand. Using the Eq. (13), a tractable robust counterpart is written as

$$ \begin{gathered} \begin{array}{*{20}c} {\mathop {Min}\limits_{x,y} \sum\limits_{{t \in \Im }} {\sum\limits_{{i \in C\backslash C_s }} {c_i^t x_i^t } } } & {\left( {\text{M - RC4}} \right)} \\ \end{array} \hfill \\ subject\,to \hfill \\ \left. \begin{gathered} x_i^t - x_i^{t - 1} - \sum\limits_{{k \in C}} {a_{ki} y_{ki}^{t - 1} } + \sum\limits_{{j \in C}} {a_{ij} y_{ij}^{t - 1} } \ge \bar{d}_i^{t - 1} \left( {1 + \theta_i } \right) \hfill \\ \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } \le Q_i^t ~ \hfill \\ \sum\limits_{{k \in C}} {a_{ki} y_{ki}^t } + \delta_i^t x_i^t \le \delta_i^t N_i^t ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } \le Q_i^t ~ \hfill \\ \sum\limits_{{j \in C}} {a_{ij} y_{ij}^t } - x_i^t \le 0~ \hfill \\ \end{gathered} \right\}i \in C~t \in \Im \hfill \\ \begin{array}{*{20}c} {x_i^0 = \hat{x}_i } & {\forall i \in C} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {y_{ij}^0 = 0} & {\forall \left( {i,j} \right) \in C \times C} \\ \end{array} \hfill \\ \begin{array}{*{20}c} {x_i^t \ge 0} & {\forall i \in C} & {t \in \Im } \\ \end{array} \hfill \\ \begin{array}{*{20}c} {y_{ij}^t \ge 0} & {\forall \left( {i,j} \right) \in C \times C} & {t \in \Im } \\ \end{array} \hfill \\ \end{gathered} $$

Clearly, the robust counterpart corresponds to the case when there is maximum demand at each of the cells. Intuitively, the worst case should correspond to maximum demand at each node.

We can see that the M-RC4 corresponds to a DLP with maximum demand at each of the cells. It is worthwhile to note that our original DLP considers expected demand in all cells. Based on this finding, we can propose the following theorem (similar discussions see Bertsimas and Perakis (2005)).

Theorem 4

The robust counterpart of the Cell Transmission Model with uncertain demand in Eq. (12) corresponds to a deterministic LP (M-RC4) considering maximum possible demand in the uncertainty set.

From Theorem 4, we have the following:

$$ y_{RC4} \equiv \arg \mathop {\min }\limits_y \mathop {\max }\limits_d V\left( {y,d} \right) = y_N \left( {d_M } \right) = \arg \mathop {\min }\limits_y V\left( {y,d_M } \right) $$

where $d_M = \bar{d}_i^t \left( {1 + \theta} \right)$, the maximum possible demand within demand uncertainty set defined in Eq. (12).

We then can have the following proposition.

Proposition 3

In the Cell Transmission Model with uncertain demand in Eq. (12), the robust solution of the robust counterpart has performance better than or same as any nominal solution considering maximum possible demand in the uncertainty set.

Proof

From Proposition 1 and 2, we have

$$ V\left( {y_N \left( d \right),d_M } \right) \ge V\left( {y_N \left( {d_M } \right),d_M } \right) = V\left( {y_R, d_M } \right).\, ■ $$

The implication of Proposition 3 is that a robust solution performs better than any nominal solution under worst scenario demand. A natural question is that, on average, which solution will have better performance. We will conduct numerical experiments in section 5 to investigate this question.

5 Numerical examples

This section presents an illustrative example based on Chiu et al. (2007). The input data consists of topology or connectivity, demand estimates at source nodes and geometric characteristics of the transportation network. The geometric characteristics include length, no. of lanes, speed limits and capacity limits on the road. Using this information, an equivalent cell model is constructed in which length of a cell corresponds to the maximum distance traveled by a vehicle in a unit time interval. The capacity and demand information is appropriately reflected in the cell transmission model. The model parameter, δ, is assumed to be unity, i.e., $\delta_i^t = 1,\forall i \in C,t \in \Im$. The entire data for the CTM is presented in Tables 1 and 2.

Table 1 Time invariant cell properties

Table 2 Time dependent data

Consider the example in Fig. 1 where evacuation needs to be moved out from nodes {A,D,G} to sink nodes {C,F,H}. The equivalent cell transmission model is shown on the right part of Fig. 1. A super sink cell, 14, has been added to convert the multiple source/multiple sink model to a multiple source/ single sink model. The cells (1,5,9) are source cells and 14 is a sink cell.

Fig. 1

Evacuation example (Chiu et al. 2007)

Without loss of generality, let T = 15 (total time periods). All other data regarding expected demand and capacity of the transportation network is adopted from Chiu et al. (2007). The nominal solution is obtained by assuming a deterministic demand, where the realized demand is equal to the expected demand $\bar{d}$. But, the realized demand can be less than or greater than the expected demand and one has to adjust the nominal solution in order to implement it. Waller and Ziliaskopoulos (2006) choose to duplicate extra demand randomly when more realized than expected appear. Mudchanatongsuk et al. (2008) propose artificial arcs with high cost to avoid higher demand. By considering vehicle holding (evacuees may wait in some places as long as not violating the constraints) in evacuation, we choose the following rules to adjust nominal solution:

• 1) If the realized demand is greater than the expected, then the excess demand remains at the source cell. Although this is a restrictive assumption, we expect that this will provide a good starting point for further work. The cost function, as defined in Eq. (10) and presented below for convenience, penalizes evacuees who haven’t reached the sink cell at the end of time horizon

$$ c_i^t = \left\{ \begin{gathered} \begin{array}{*{20}c} 1 & {i \in C,t \ne T} \ \hfill \\\end{array} \begin{array}{*{20}c} M & {i \in C,t = T} \ \hfill \\ \end{array} \end{gathered} \right. $$

• 2) If there is less demand than expected then proportionate demand is allocated to each path.

We assume $\theta _{i} = \overline{\theta } \;\;\forall i \in C$and M = 10. For a given $\bar{\theta }$, 100 random demand samples were generated and the average objective function value ($z_{nom}^{{\bar{\theta }}}$) obtained by implementing the nominal solution. This average value was compared to objective function value ($z_{nom}^0 = 414$) in a deterministic scenario. The average degradation relative to the nominal solution is calculated and plotted as $\bar{\theta }$ is varied from 0% to 30% in intervals of 2%. The degradation is calculated as follows

$$ {\text{degradation}}\left( {\bar{\theta }} \right) = \frac{{\left( {z_{nom}^{{\bar{\theta }}} - z_{nom}^0 } \right)}}{{z_{nom}^0 }} $$

As shown in Table 3 and Fig. 2, an average degradation of 10–15% was observed when the nominal solution was subject to uncertain demand. This may be significant as the increase in objective cost function value corresponds to loss of human life and property. Also, uncertainty in demand seems to be proportional to the degradation in the nominal solution. One can argue that the analysis seems to be dependent on the policy we used to deal with excess/less demand. But, we note that policies used to adjust solutions must be computationally inexpensive and relatively simple for the traffic controllers to implement it in real time. Although different policies can exhibit different results, a similar trend can be expected as seen in Table 3. This experiment provides a clear motivation to consider uncertainty in evacuation problems.

Table 3 Degradation Of nominal solution under uncertain demand

Fig. 2

Consequence of data uncertainty for nominal solution

Similar setting is used to compare the robust solution to the nominal solution. For a given $\bar{\theta }$, 100 random demand samples were generated and the objective function values obtained by implementing the robust ($z_{rob}^{{\bar{\theta }}}$) and the nominal solution ($z_{nom}^{{\bar{\theta }}}$) were compared. The average relative improvement over the nominal solution is calculated and plotted as $\bar{\theta }$ is varied between 0% to 30% in intervals of 2%. The improvement is calculated as follows

$$ improvement(\bar{\theta }) = \frac{{\left( {z_{nom}^{{\bar{\theta }}} - z_{rob}^{{\bar{\theta }}} } \right)}}{{z_{nom}^{{\bar{\theta }}} }} $$

Table 4 and Fig. 3 show that an average improvement of 8–10% is over the nominal solution by the robust solution under varying level of uncertainty. Although, the improvement observed is not monotone, the robust solution seemingly performs better at higher uncertainty levels in demand. Similar non-monotone results were reported by Bertsimas et al. (2007) when RO was applied to an inventory control problem.

Table 4 Improvement of robust solution relative to the nominal solution

Fig. 3

Relative performance of robust solution

Although, the results obtained are based on several assumptions such as excess demand being left at source nodes, we feel that robust solution is conceptually superior to a deterministic solution. In addition, one can see that the robust solution can be conservative as it deals with the worst case scenario which corresponds to maximum demand at each of the source nodes. In reality, there is a small chance of this scenario to occur. We argue that a conservative solution such as a robust solution will provide a guaranteed bound and be preferable to a nominal solution which does not guarantee feasibility or solution quality under all demand realizations. This may be particularly relevant in an evacuation scenario where solution infeasibility may result in loss of life and property. Also, one can restrict the uncertainty set to obtain robust solutions which will provide more realistic guarantees during evacuation. In this section, we tested whether evacuation problem is an appropriate application area for optimization under uncertainty. (see Ben-Tal et al. (2007) for a similar analysis of a drug development example). Clearly, RO is a promising approach to develop evacuation plans which are immune to uncertainty.

6 Conclusion

This paper develops a RO model for evacuation transportation planning in extreme events. The robust counterparts have been shown tractable. Existing optimization softwares like CPLEX can be potentially used to efficiently solve large scale RO solution. By focusing on infeasibility cost, we show the importance of robustness. More interestingly, we find that a robust solution improves both feasibility and quality comparing to a nominal solution.

Our work provides a basis for future analytical and simulation analysis for evacuation management. Additional experiments need to be conducted on variety of transportation networks with different policies to deal with uncertain demand to enhance the findings discussed in this paper. The uncertainty analysis may be extended to include capacity reductions and implementation errors.

The robust solutions obtained are conservative in nature. In order to make the robust solutions less conservation, more realistic demand scenarios which have a higher probability of occurrence may be incorporated into the analysis. Also, a multi-period Adjustable Robust Counterpart (ARC) solution (Ben-Tal et al. 2004) may be developed to reduce the solution conservativeness when sequential decisions are made with information updating over time.