Refueling Station Location Model to Support Evacuation of Alternative Fuel Vehicles

Abstract

Alternative fuel vehicles may pose challenges to evacuation planning because of their short driving range and the sparse refueling infrastructure existing on transportation networks. Deployment and strategic siting of emergency refueling stations are needed to support the evacuation of alternative fuel vehicles to reach a shelter. This study proposes a location-routing problem with hop constraints that optimize the placement of emergency refueling stations of each alternative fuel type to support evacuation routing. We develop a Benders-inspired decomposition method with a transformed network to solve the location problem and a matheuristic branch-and-price method to design evacuation routes that minimize travel and refueling time and satisfy the hop constraints of each vehicle type. Our numerical experiments, focusing on the South Florida network, uncover the impacts of alternative fuel vehicle specifications and vehicle heterogeneity on the deployment plan.

Keywords

sustainability and resilience transportation and sustainability alternative transportation fuels and technologies transportation energy emergency evacuation

Despite their sustainability and economic benefits, growth in the market for alternative fuel vehicles is subject to barriers of infrastructure availability ( 1 – 3 ). Compared with gasoline vehicles, alternative fuel vehicles have limited driving ranges, depending on their fuel tank or battery pack sizes, sparse refueling and charging infrastructure networks, and long refueling and charging times. The driving range of an electric vehicle (EV) varies from 58 to 405 miles (median: 234 miles) on a single full battery charge. These driving ranges are shorter than those of gasoline vehicles, whose median range is 418 miles ( 4 ). In addition, the refueling networks for these emerging vehicle technologies remain sparse, including only 48 hydrogen, 832 natural gas, and 49,441 EV charging stations ( 5 ), compared with more than 146,000 registered gasoline stations, in the USA as of 2022 ( 6 ). Like gasoline vehicles, hydrogen fuel cell and natural gas vehicles can refuel in less than 4 min for a 20-gallon-equivalent tank size ( 7 , 8 ). However, charging is time-consuming for battery EVs whose charging rate varies from 5 miles/hour to 240 miles/hour, depending on the charging efficiency and power level ( 9 ).

Vehicle and refueling infrastructure constraints are expected to add new challenges during natural and anthropogenic hazardous events that warrant preemptive evacuations ( 10 , 11 ). The evacuation distance to safety often exceeds the driving range of a single full battery capacity for EVs and may require frequent charging stops. Studies of Hurricanes Katrina and Rita show that the evacuation distance exceeded 388 miles ( 12 , 13 ). With the advent of alternative fuel vehicles and their particular refueling infrastructure dependencies, evacuees traveling in alternative fuel vehicles are susceptible to being stranded during emergencies without sufficient state-of-charge or fuel to reach designated shelters or safe zones ( 14 ).

Strategically placing alternative refueling stations can help reduce the vulnerability of alternative fuel vehicle owners and improve their evacuation clearance times before imminent disasters ( 10 , 15 ). The U.S. Federal Emergency Management Agency ( 14 ) and Federal Highway Administration ( 16 ) suggest evacuating vehicles through respite sites with gasoline stations; however, there is no provision for refueling alternative fuel vehicles. Responding to recent ambitious federal and state programs for accelerating alternative fuel vehicle adoption ( 17 , 18 ), it is essential to consider the deployment of alternative refueling stations to support evacuation planning.

This study aims to develop an optimal placement plan for emergency alternative refueling stations to support a diverse set of vehicle fuel types and their evacuation demand on designated evacuation routes. The emergency refueling stations may be financed and owned by public agencies, in contrast with the current refueling infrastructure network which is owned and operated by industry. The current deployment of alternative refueling stations focuses on enabling habitual travel demand and meeting profit maximization objectives ( 19 – 21 ), not evacuation demands and resilience objectives. The emergency refueling station placement would support the existing refueling stations in covering the evacuation demand. We develop the alternative refueling station location model, based on a location-routing problem, for optimal deployment of emergency refueling stations. We use a Benders-inspired decomposition procedure to solve the location problem and a matheuristic branch-and-price method to design evacuation routes. We apply the proposed framework to the South Florida transportation network: (i) to plan the siting of emergency refueling stations and (ii) to evaluate the role of alternative fuel vehicle specifications and vehicle heterogeneity in the deployment plan. This is the first paper to meet this timely research objective by proposing a new mathematical formulation that describes this problem and its algorithmic solution.

Literature Review

In this study, the facility location problem models the deployment of emergency alternative refueling stations as part of the evacuation logistics of alternative fuel vehicles. Facility location problems are integer programming problems and are commonly applied for the strategic placement of stationary infrastructure. Facility location models for alternative refueling station siting focus on integrating the side constraints associated with the refueling process through functions that describe the relationships between the limited driving range, sparse fuel or power supply, and the long refueling/charging time, for business-as-usual purposes. The flow refueling location model for alternative fuel vehicles and its extensions capture the deviating or detoured flow from refueling requirements ( 22 , 23 ). Network equilibrium models capture the interactions among public charging opportunities, prices of electricity, and route choices of EV drivers ( 21 , 24 ). Bi-level facility location models leverage the network equilibrium for routing choices and capture waiting times associated with EV charging under the assumption of infinite queues ( 25 ), while mixed-integer EV charging infrastructure location problems minimize the investment cost, EV drivers’ delay caused by the detours for recharging, and queue and waiting times during charging ( 20 ).

Evacuation road network operations are subject to non-habitual travel behaviors and additional uncertainties (e.g., unusual route choices, road and facility capacity, and dynamic demand) ( 26 ), as well as complex hierarchical coordination (e.g., from damage to communication lines, involvement of multiple agents like government and industry in emergency response, unavailability of accurate real-time demand information) and limited resources (e.g., supply, people, transportation links’ capacity, fuel constraints) ( 27 ). Such challenges need to be considered in the planning process for refueling facilities that support evacuation. Past evacuation studies on refueling station dependency focused on the deployment and supply planning of refueling stations for gasoline vehicles. Simulation-optimization frameworks were used for optimal deployment of gas stations and their supply for hurricane evacuation ( 28 ) and the so-called “idealized model” manages optimal gasoline supplies and evacuation routing with fuel capacity constraints for hurricane evacuation ( 29 ). Few studies investigated the effect of alternative refueling station location on preemptive evacuation performance. Adderly et al. ( 10 ) provide a comprehensive review of EVs and their policy implications in emergency management. Feng et al. ( 11 ) examine the feasibility of EVs to evacuate during hurricanes using a Florida case study. Both works indicate that the deployment of emergency refueling stations may be needed as the alternative refueling networks remain sparse. MacDonald et al. ( 30 ) develop a queueing model to optimize the electricity supply of existing alternative fuel vehicle charging stations for evacuation demand. Li et al. ( 31 ) design a three-stage framework to design an optimal EV mass evacuation plan with existing charging facilities. Purba et al. ( 15 ) develop novel evacuation route planning considering the existing refueling stations of alternative fuel vehicles in the network, and highlight the importance of refueling station location in supporting evacuation operations. No other work has modeled the optimal deployment of emergency refueling stations to support evacuation planning in addition to existing refueling stations; our paper aims to bridge this knowledge gap.

Problem Formulation

We present the refueling station location model to support preemptive evacuation routing plans for multiple alternative fuel vehicle types. The formulation is structured as a location-routing problem that optimally deploys emergency alternative refueling stations according to demand from alternative fuel vehicles during evacuation. Purba et al. ( 15 ) propose the $| K |$ -evacuation tree routes planning problem that designs evacuation tree paths to safety for every $k \in K$ alternative fuel vehicle type, considering their alternative fuel vehicle driving range limitations and refueling requirements during evacuation. The designated routes have five desirable evacuation attributes: fast and seamless routing, contraflow traffic control, evacuation routes with access to refueling stations, and multiple evacuation route plans that meet these attributes for all fuel types. We use the $| K |$ -evacuation tree routes planning problem to model the evacuation route performance of multiple alternative fuel vehicle types given the locations of their refueling stations in the network.

Our model assumes that every alternative refueling station has enough fuel and parking capacity to serve all necessary vehicles without congestion or queues forming. The assumption is aligned with a preemptive evacuation order, in which case emergency planners are well informed about the evacuation demand. Emergency planners can guarantee that the deployed and operated refueling stations must fulfill the refueling needs of all necessary vehicles during a preemptive evacuation. We further assume that evacuees start with a fully fueled vehicle or with a full state-of-charge and that they are well informed about the mandated evacuation route designation.

In the remainder of this section, we define the notation, provide a formal problem statement, and present the mathematical formulation of the problem.

Definitions and Notations

Let $G = (N, A)$ be a transportation network, where $N$ represents the set of nodes and $A$ the set of links. A shelter node on the transportation network is represented by $s$ . The shelter node represents a safety zone that is suggested by the emergency authorities and not affected by the hazard, such as physical safe havens, assemble points, and Interstate exit gates. We define a set of vehicles $K$ , representing each vehicle fuel type. For example, we may consider $K = {$ gasoline, hydrogen, $electric}$ representing $| K | = 3$ different types.

The set of evacuee origin nodes heading to shelter $s$ is defined as $O$ . For every evacuee’s origin node $o \in O$ in the network, we assume that $q_{o}^{k}$ is the number of vehicles of fuel type $k$ originating from node $o$ that need to be routed to a single shelter node $s$ . In real-world evacuation cases, there may be multiple shelters. Following Purba et al. ( 15 ), we handle multiple shelter nodes by creating a dummy node (“super shelter” node) that serves as $s$ , and each existing shelter node will be directly connected to $s$ with an arc of zero travel time and infinite capacity. A subset of network nodes may host refueling infrastructure. We define $S T_{e} (k) \subseteq N, \forall k \in K$ as the set of all nodes with the current infrastructure of fuel type $k$ that has been installed before the evacuation plan. We assume that existing refueling stations could be utilized during evacuation. Then, we define $S T_{p} (k) \subseteq N, \forall k \in K$ as the set of all candidate nodes to deploy emergency refueling infrastructure of fuel type $k$ to support evacuation. Let ${c_{f}}_{i}^{k}$ be the cost of opening the refueling station of fuel type $k$ at node $i$ and $R_{f}^{k}$ be the total resource limit to opening stations of type $k$ .

We define $r_{c}^{k}$ as the refueling rate of refueling station of type $k$ . Following Purba et al. ( 15 ), the refueling rate is constant for each fuel type. In a real-world application, each vehicle fuel type could have several station types (e.g., for EVs there are different power levels: charging station L1, L2, and DCFC) and each station specification has a unique refueling rate. In this problem, we assume that each alternative fuel station’s hose/connector type is standardized, and that each vehicle fuel type is compatible with the standardized connectors/hoses. This assumption is practical for emergency authorities in maintaining consistent evacuation performance.

Any node that belongs to $S T_{e} (k)$ and $S T_{p} (k)$ may be visited by type $k$ vehicles for either refueling or as a midpoint along the evacuation route. To differentiate between these reasons, we introduce two sets. The first set is $ST (k) \subseteq N, \forall k \in K$ as the set of all nodes with usable refueling infrastructure that is visited to refuel vehicle fuel type $k$ , where $ST (k) = S T_{e} (k) \cup S T_{p} (k), \forall k \in K$ . The second set is $ST' (k), \forall k \in K$ , a duplicate of $ST (k)$ , as the set of refueling station nodes passed as a midpoint in the evacuation route ( 20 ). Thus, the entire set of nodes in the network is $N^{'} = N \cup_{k \in K} ST' (k)$ . For every link $(i, j) \in A$ in the network, the travel time $t_{ij}$ is computed by the Bureau of Public Roads (BPR) function, associating the travel time of a link with its flow to capacity ( $u_{ij}$ ) ratio ( 32 ). Figure 1 illustrates the parameters in our problem and the modified network topology.

Figure 1.

(a) Network topology with an existing refueling station, a candidate emergency refueling station, and multiple shelter nodes, and (b) modified network topology with a super shelter node and dummy refueling nodes.

In our model, each evacuee originating from $o \in O$ would traverse a single usable evacuation path for each vehicle of fuel type $k$ to the shelter. We adapt the definition of a usable path from He et al. ( 24 ): an evacuation path is usable for a vehicle of fuel type $k$ if this vehicle type can evacuate to the shelter with or without refueling.

The driving range constraint for each vehicle of fuel type $k$ is modeled by imposing hop betweenness constraints that define the refueling needs during an evacuation. The number of hops is denoted by $τ_{k}$ . It is a natural number of the transportation network links that a vehicle can at most traverse before refueling; as such, it serves as a proxy to the alternative fuel vehicle’s driving range. Purba et al. ( 15 ) discuss the benefits of implementing hop as generic controlled distance parameters in the evacuation network setting: (i) they integrate heterogeneous fuel types in evacuation plans, and (ii) they account for variability in driving ranges for different vehicle manufacturers. Using the hop betweenness constraints, if a vehicle of fuel type $k$ originates from a node that is located more than $τ_{k}$ hops away from the shelter in the current evacuation plan, such a vehicle needs to stop and refuel at a refueling station in between $τ_{k}$ hops range along its evacuation path. We define $P (k, o)$ as the set of usable evacuation paths between nodes $o$ and $s$ for an evacuee of vehicle type $k$ that satisfy the hop betweenness constraints given every combination of existing and emergency refueling stations in $ST (k)$ .

Figure 2 presents an example network to illustrate the usable evacuation paths with hop betweenness constraints. Consider a network topology with one refueling station located at node $r$ and one shelter located at $s$ . In this example, we consider only one vehicle fuel type with $τ_{k}$ = 3 hops. For evacuees originating from node 1, there are four potential evacuation paths: 1-2-3-r-4-5-s, 1-2-r-4-5-s, 1-2-3-r-4-s, and 1-2-r-4-s. According to the refueling rule, the usable paths for evacuees from node 1 are 1-2-3-r-4-s and 1-2-r-4-s. The other two evacuation paths are unusable because the subpath r-4-5-s does not stop at any refueling station. For evacuees originating from node 4, there are two potential evacuation paths: 4-5-s and 4-s, and all are usable as those are less than $τ_{k}$ hops from the shelter.

Figure 2.

Example of network topology with five evacuee nodes, an existing refueling station, and a shelter node.

There are seven sets of decision variables in this model. The first two are associated with the deployment of emergency refueling stations. We define binary variables ${z_{p}}_{i}^{k}$ to denote whether an emergency refueling station $k$ is open at node $i$ to support the evacuation plan. Then, we define binary variables $z_{i}^{k}$ to denote whether the refueling station of $k$ at $i$ is visited by its vehicles to refuel. The remaining decision variables are associated with the evacuation routing and the flows. Table 1 presents the parameters and decision variables for the problem.

Table 1.

List of Parameters and Decision Variables for the Refueling Station Location Model

Notation	Definition
Parameters
$G$	transportation network
$N$	set of nodes in network $G$
$A$	set of arcs in network $G$
$K$	set of alternative fuel vehicle types in network $G$
$s$	shelter node
$S T_{e} (k)$	set of existing refueling station nodes for vehicle type $k$
$S T_{p} (k)$	set of candidate nodes of emergency refueling station for vehicle type $k$
$ST (k)$	set of usable refueling station nodes for vehicle type $k$ that is visited to refuel
$ST' (k)$	set of usable refueling station nodes for vehicle type $k$ that is visited as midpoint
$O (s)$	set of origin node to shelter $s$
$P (k, o)$	set of usable paths from node $o$ to shelter $s$ using vehicle type $k$
$δ_{ijp}^{ko}$	1 if arc $(i, j)$ is in path $p$ of vehicle type $k$ from node $o$ ; 0 otherwise
$δ_{ip}^{ko}$	1 if node $i$ is in path $p$ of vehicle type $k$ from node $o$ ; 0 otherwise
$ϕ_{p}^{ko}$	length of the usable path $p$ of vehicle type $k$ from node $o$ $ϕ_{p}^{ko} = \sum_{(i, j) \in A} δ_{ijp}^{ko}$
$q_{o}^{k}$	total evacuee demand originating from node $o$ using vehicle type $k$
$t_{ij}$	total travel time on $(i, j)$
$u_{ij}$	capacity of $(i, j)$
${c_{f}}_{i}^{k}$	cost for opening emergency refueling station for vehicle type $k$ in node $i$
$R_{f}^{k}$	resource limit to open emergency refueling station for vehicle type $k$
${z_{e}}_{i}^{k}$	1 if there is an existing refueling station for vehicle type $k$ in node $i$ ; 0 otherwise
$τ_{k}$	hop driving range of vehicle type $k$
$r_{c}^{k}$	fixed refueling rate of refueling station of vehicle type $k$
$S$	set of subtours in the network $G$
$C$	set of all cycles in the network $G$
$M$	arbitrary large constant value
Decision variables
${z_{p}}_{i}^{k}$	1 if open emergency refueling station for vehicle type $k$ at node $i$ ; 0 otherwise
$z_{i}^{k}$	1 if the refueling station fuel type at node $i$ is visited to refuel; 0 otherwise
$λ_{p}^{k, o}$	1 if the evacuation path $p$ is used to evacuate vehicle type $k$ from node $o$ ; 0 otherwise
$x_{ij}^{k}$	1 if arc $(i, j)$ is part of the evacuation tree of vehicle type $k$ ; 0 otherwise
$w_{o}^{k}$	1 if vehicle type $k$ from node $o$ needs to refuel before reaching shelter; 0 otherwise
$v_{ij}$	total flow on arc $(i, j)$
$f_{ij}^{k}$	total flow of vehicle fuel type $k$ on arc $(i, j)$

Mathematical Formulation

We provide the formulation of the problem in Equations 1 through 20.

\begin{matrix} min \sum_{\forall k \in K} \sum_{\forall i \in S T_{p} (k)} {c_{f}}_{i}^{k} {z_{p}}_{i}^{k} + \sum_{(i, j) \in A} t_{ij} (v_{ij}) v_{ij} \\ + \sum_{k \in K} \sum_{o \in O} \sum_{p \in P (k, o)} q_{o}^{k} r_{c}^{k} ϕ_{p}^{ko} w_{o}^{k} λ_{p}^{ko} \\ = min \sum_{\forall k \in K} \sum_{\forall i \in S T_{p} (k)} {c_{f}}_{i}^{k} {z_{p}}_{i}^{k} \\ + \sum_{k \in K} \sum_{o \in O} \sum_{p \in P (k, o)} \sum_{(i, j) \in A} t_{ij} (v_{ij}) δ_{ijp}^{ko} q_{o}^{k} λ_{p}^{ko} \\ + \sum_{k \in K} \sum_{o \in O} \sum_{p \in P (k, o)} q_{o}^{k} r_{c}^{k} ϕ_{p}^{ko} w_{o}^{ko} λ_{p}^{ko} \end{matrix}

(1)

z_{i}^{k} = 0 \forall i \in N \ ST (k), \forall k \in K

(2)

z_{i}^{k} \leq z_{e_{i}}^{k} + z_{p_{i}}^{k} \forall i \in ST (k) \forall k \in K

(3)

\sum_{\forall i \in S T_{p} (k)} {z_{p}}_{i}^{k} \leq R_{f}^{k} \forall k \in K

(4)

v_{ij} = \sum_{k \in K} f_{ij}^{k} \forall (i, j) \in A

(5)

f_{ij}^{k} = \sum_{o \in O} \sum_{p \in P (k, o)} λ_{p}^{ko} δ_{ijp}^{ko} q_{o}^{k} \forall (i, j) \in A, \forall k \in K

(6)

\sum_{p \in P (k, o)} λ_{p}^{ko} = 1 \forall o \in O, \forall k \in K

(7)

\sum_{p \in P (k, o)} λ_{p}^{ko} δ_{ip}^{ko} w_{o}^{k} \leq z_{i}^{k} \forall i \in ST (k), \forall o \in O (s), \forall k \in K

(8)

f_{ij}^{k} \leq M x_{ij}^{k} \forall (i, j) \in A, \forall k \in K

(9)

\sum_{j : (i, j) \in A} x_{ij}^{k} = 1 \forall i \in N ∖ {s}, \forall k \in K

(10)

\sum_{(i, j) \in A : i, j \in S} x_{ij}^{k} \leq | S | - 1 \forall S \in C

(11)

x_{ij}^{k} + x_{ji}^{q} \leq 1 \forall (i, j) \in A, \forall k, q \in K

(12)

ϕ_{p}^{ko} λ_{p}^{ko} - τ_{k} \leq | N^{'} | w_{o}^{k} \forall p \in P (k, o), \forall o \in O, \forall k \in K

(13)

{z_{p}}_{i}^{k} \in {0, 1} \forall i \in S T_{p} (k) \forall k \in K

(14)

z_{i}^{k} \in {0, 1} \forall i \in ST (k) \forall k \in K

(15)

λ_{p}^{ko} \in {0, 1} \forall p \in P (k, o), \forall o \in O, \forall k \in K

(16)

x_{ij}^{k} \in {0, 1} \forall (i, j) \in A, \forall k \in K

(17)

w_{p}^{ko} \in {0, 1} \forall p \in P (k, o), \forall o \in O, \forall k \in K

(18)

v_{ij} \geq 0 \forall (i, j) \in A

(19)

f_{ij}^{k} \geq 0 \forall (i, j) \in A, \forall k \in K

(20)

The objective function (Equation 1) aims to minimize the total cost of opening emergency refueling stations and the total system evacuation time by summing the time spent traversing each link on the evacuation network and the refueling time. Constraints in Equations 2 and 3 identify that a node could host the usable refueling station if either an existing or emergency refueling station is deployed. The next constraints (Equation 4) limit the total emergency refueling stations that can be opened for each fuel type.

The constraints in Equations 5 through 9 are traffic assignment constraints. Constraints 5 and 6 keep track of the total flow of each vehicle type $k \in K$ in $(i, j) \in A$ . Constraints 7 enforce that each evacuee originating from $o$ using vehicle type $k$ would follow one usable path to $s$ . Constraints 8 guarantee that every evacuee vehicle could refuel at its refueling station node along the evacuation path if such a refueling station is open. Constraints 9 allow flow assignment if and only if the corresponding link is part of an evacuation tree. Constraints in Equations 10 and 11 are tree constraints. They restrict the number of outgoing links from each node to be equal to one, as each node should have one path to the shelter. We have subtour elimination constraints for every cycle $S \in C$ , where $C$ is the set of all cycles present in the transportation network. This set grows exponentially in cardinality. Constraints in Equation 12 are conflict and contraflow constraints to prohibit the same link to serve flow in both directions. We enforce contraflow constraints that take full advantage of the network links’ capacities. Constraints in Equation 13 guarantee refueling decisions; a vehicle located $τ_{k}$ or more hops away from the shelter needs to refuel at the refueling station. Finally, the decision variable restrictions, as provided in the “Definitions and Notations” section above, are enforced in the constraints in Equations 14 through 20.

Solution Methods

This section presents a decomposition method inspired by Benders decomposition for solving the refueling station location model. The refueling station location model is formulated as a mixed-integer nonlinear problem, which is compositionally intractable as the size of the network increases. Specifically, our model is structured as a path-based location-routing problem. Benders decomposition has been used to provide both exact and heuristic solutions to the location-routing problem ( 33 – 36 ) and multi-stage problem (relevant to our problem) ( 37 – 40 ) with side constraints.

In our formulation, $P (k, o)$ is a set of usable evacuation paths between nodes $o$ and $s$ for an evacuee of vehicle type $k$ that satisfy the hop betweenness constraints given every combination of existing and emergency refueling stations in $ST (k)$ . The feasible set of $P (k, o)$ depends on the decision variable of emergency refueling stations. Through the current decomposition algorithm, the set size of $P (k, o)$ , the routing subproblem keeps changing for any emergency refueling station solution from the location main problem in each iteration. However, the conventional Benders decomposition strictly handles a fixed feasible set in each iteration ( 34 , 41 , 42 ). Thus, we design a decomposition algorithm inspired by Benders decomposition with a changeable usable evacuation set; we call it Benders-inspired decomposition.

Benders-Inspired Decomposition

The problem is decomposed into two problems: (i) location main problem (MP) to deploy optimally the emergency refueling stations for each alternative fuel type $k$ ; (ii) routing subproblem (SP) to determine the optimal evacuation route planning for each alternative fuel vehicle type $k$ given the emergency refueling station deployment.

Location MP

We define $L$ as the set of cuts generated in the Benders-inspired decomposition algorithm. For each generated cut, we define $Φ^{l} (z_{p}^{*})$ as the lower bound of the minimum total evacuation travel and refueling time in the evacuation route planning. Then, we define the new decision variable, $θ$ , as the total evacuation and refueling time from the optimal evacuation routing planning. We formulate the MP as follows:

\begin{matrix} min \sum_{\forall k \in K} \sum_{\forall i \in S T_{p} (k)} {c_{f}}_{i}^{k} {z_{p}}_{i}^{k} + θ \\ s . t . (2) - (4), (15), (16), \end{matrix}

(21)

θ \geq Φ^{l} (z_{p}^{*}) \forall l \in L

(22)

θ \geq 0

(23)

The objective function (Equation 21) represents the decomposition reformulation for our objective function (Equation 1). Constraints in Equation 22 bound the optimal objective function for each generated cut. We define the cuts formulation in the following section. The constraint in Equation 23 defines the decision variable. The MP structure is a mixed-integer problem, solved using a commercial solver, such as Gurobi ( 43 ).

Routing SP

For every iteration $l \in L$ , we define the SP as:

\begin{matrix} Φ (z^{*}) = min \sum_{k \in K} \sum_{o \in O} \sum_{p \in P (k, o)} \sum_{(i, j) \in A} t_{ij} (v_{ij}) δ_{ijp}^{ko} q_{o}^{k} λ_{p}^{ko} \\ + \sum_{k \in K} \sum_{o \in O} \sum_{p \in P (k, o)} q_{o}^{k} r_{c}^{k} ϕ_{p}^{ko} w_{o}^{k} λ_{p}^{ko} \\ = min \sum_{k \in K} \sum_{o \in O} \sum_{p \in P (k, o)} (\sum_{(i, j) \in A} t_{ij} (v_{ij}) δ_{ijp}^{ko} + r_{c}^{k} ϕ_{p}^{ko} w_{o}^{k}) q_{o}^{k} λ_{p}^{ko} \\ s . t . (5) - (13), (16) - (20) \end{matrix}

(24)

The objective function (Equation 24) minimizes the evacuation time of the total system by summing the time spent traversing each link on the evacuation network and the time spent refueling. This SP is formulated similarly as the $| K |$ -evacuation tree route problem with side constraints (8) that link the decision of refueling station location and the evacuation routing. Purba et al. ( 15 ) develop a branch-and-price with column generation matheuristic algorithm to solve the $| K |$ -evacuation tree route problem. In this study, we adopt branch-and-price algorithm to solve the SP and discuss it briefly in the following section.

Cuts

We derive the cuts formulation for constraints (Equation 22) using the duality of the SP. In the SP, $λ_{p}^{ko}$ and $w_{o}^{k}$ are the decision variables that appear in the objective function (Equation 24). For the given optimal solutions of $λ_{p}^{ko}$ and $w_{o}^{k}$ , the remaining decision variables (that are not in the objective function), that is, $x_{ij}^{k}$ , $f_{ij}^{k}$ , $v_{ij},$ are also optimal. Furthermore, for the given optimal solutions of $λ_{p}^{ko}$ , we could calculate $w_{o}^{k}$ using the constraints in Equation 13 separately. Thus, we construct the dual objective function of the SP only with respect to $λ_{p}^{ko}$ and its associated constraints. Let $π_{ij}^{k}$ , $μ_{o}^{k}$ , and $ψ_{i}^{ko}$ be the dual variables associated with the constraints in Equations 6, 7, and 8, respectively. Then, we formulate the cuts as follows:

\begin{matrix} θ \geq \sum_{\forall k \in K} \sum_{\forall (i, j) \in A} π_{ij}^{kl} f_{ij}^{* kl} + \sum_{\forall k \in K} \sum_{\forall o \in O (s)} μ_{o}^{kl} \\ + \sum_{\forall k \in K} \sum_{\forall o \in O (s)} \sum_{\forall i \in ST (k, o)} ψ_{i}^{kol} z_{i}^{k} \forall l \in L \end{matrix}

(25)

Finally, we solve the Benders-inspired decomposition as shown in Algorithm 1.

Algorithm 1 Bender-Inspired Decomposition Algorithm
Input	A network $G = (N, A)$ , set of vehicle fuel types $K$ , set of evacuee origin nodes $O (s)$ , evacuee demand $q_{o}^{k}$ , set of existing refueling stations $S T_{e} (k)$ , set of potential emergency refueling stations $S T_{p} (k)$ , and a shelter node $s$
Output	Optimum deployment of emergency refueling station, $z_{p}^{k}$ , in the network
1:	Initialization: Set $l = 0, θ^{l} = - \infty, θ_{\min} = \infty$
2:	while $θ^{l} \neq θ_{\min}$ do
3:	Solve the MP problem
4:	Let $z^{l}$ , $z_{p}^{l}$ , and $θ^{l}$ as the optimum solution that satisfies cuts in MP problem
5:	Solve the SP using $z^{l}$ and $z_{p}^{l}$
6:	Let $ϕ^{l}$ as optimum objective value of SP problem
7:	if $ϕ^{l} < \infty$ then
8:	Let ${(π, μ, ψ)}^{l}$ as optimum dual solution of SP problem given $z^{l}$ and $z_{p}^{l}$
9:	if $ϕ^{l} < θ_{\min}$ then
10:	$θ_{\min} \leftarrow Φ^{l}$
11:	${(π, μ, ψ)}^{best}$ $\leftarrow {(π, μ, ψ)}^{l}$
12:	Generate cuts $Φ^{l}$ using ${(π, μ, ψ)}^{l}$
13:	$l \leftarrow l + 1$

Branch-and-Price with Column Generation Matheuristic

We adopt the branch-and-price with column generation ( 15 ) to solve the SP as a $| K |$ -evacuation tree route problem with side constraints. The branch-and-bound handles the integrality of the SP and the matheuristic column generation implementations involve finding the best evacuation tree route, where each path is the usable evacuation path that minimizes the evacuation time and satisfies the hop betweenness constraints.

In this section, we define the restricted routing SP and the pricing SP for the $| K |$ -evacuation tree route problem with side constraints. Then, we apply the branch-and-price with column generation algorithm ( 15 ) directly to solve the SP.

Restricted Routing SP

We define $\hat{P} (k, o)$ as the current subset of usable evacuation path in the iteration, ${\hat{v}}_{ij}$ as the fixed value of the current total link flow in the ongoing traffic assignment process, ${\hat{ϕ}}_{p}^{ko}$ as the fixed value of evacuation distance of path $p$ for evacuees from node $o$ using vehicles of fuel type $k$ in the iteration. For the given $\hat{P} (k, o)$ and fixed value of ${\hat{ϕ}}_{p}^{ko}$ , we could easily identify whether an evacuation path exceeds the driving range and requires access to a refueling station. We could thus pre-determine constraints (Equation 13) and decision variable $w_{o}^{k}$ as parameter. We introduce ${\hat{w}}_{p}^{ko}$ as a fixed binary value that is 1 if ${\hat{ϕ}}_{p}^{ko} \geq τ_{k}$ and 0 otherwise. Given that we fixed the flow assignments in the restricted SP problem, the problem structure changes from a mixed-integer nonlinear problem to a mixed-integer linear problem. Thus:

\begin{matrix} min \sum_{k \in K} \sum_{o \in O} \sum_{p \in \hat{P} (k, o)} (\sum_{(i, j) \in A} t_{ij} ({\hat{v}}_{ij}) δ_{ijp}^{ko} + r_{c}^{k} {\hat{ϕ}}_{p}^{ko} {\hat{w}}_{p}^{ko}) q_{o}^{k} λ_{p}^{ko} \\ s . t . (6), (7), (9) - (12), (16), (17), (20) \end{matrix}

(26)

\sum_{p \in \hat{P} ((k, o)} λ_{p}^{ko} δ_{ip}^{ko} {\hat{w}}_{p}^{ko} \leq z_{i}^{k} \forall i \in ST (k), \forall o \in O (s), \forall k \in K

(27)

Relaxing the integrality of $x_{ij}^{k}$ and $λ_{p}^{ko}$ , we solve the relaxed the restricted SP problem as a linear problem.

Pricing Routing SP

This section describes the pricing SP of the matheuristic column generation algorithm. We only consider the set of usable evacuation paths $P (k, o)$ that comply with the hop betweenness constraints for vehicles of type $k$ . We then formulate the pricing SP as a side-constrained shortest path problem, where hop betweenness constraints serve as the side constraints.

Let $x_{ij}^{ko}$ be the binary decision variable indicating whether the link is part of the usable evacuation path, $Ω (x_{ij}^{ko})$ the set of subpaths from the selected evacuation path for evacuees originating from node $o$ for vehicle of type $k$ , and $w_{o}^{k}$ the binary decision variable indicating whether evacuees from node $o$ need access to a refueling station of fuel type $k$ . As we model the evacuation distance in hop-distance units, we can calculate that $ϕ_{p}^{ko} = \sum_{(i, j) \in A} x_{ij}^{ko}$ . The pricing subproblem is formulated for each origin $o \in O$ and each fuel type $k \in K$ , as follows:

\begin{matrix} min (\sum_{(i, j) \in A} t_{ij} ({\hat{v}}_{ij}) δ_{ijp}^{ko} q_{o}^{k} + q_{o}^{k} r_{c}^{k} {\hat{ϕ}}_{p}^{ko} {\hat{w}}_{p}^{ko}) \\ - \sum_{(i, j) \in A} π_{ij}^{k *} δ_{ijp}^{ko} q_{o}^{k} - μ_{o}^{k *} - \sum_{i \in ST (k)} ψ_{i}^{ko *} δ_{ip}^{ko} {\hat{w}}_{p}^{ko} \\ = min (\sum_{(i, j) \in A} t_{ij} ({\hat{v}}_{ij}) x_{ij}^{ko} q_{o}^{k} + \sum_{(i, j) \in A} r_{c}^{k} x_{ij}^{ko} w_{o}^{k} q_{o}^{k}) \\ - \sum_{(i, j) \in A} π_{ij}^{k *} x_{ij}^{ko} q_{o}^{k} - μ_{o}^{k *} - \sum_{i \in ST (k)} ψ_{i}^{ko *} δ_{ip}^{ko} w_{o}^{k} \\ = min \sum_{(i, j) \in A} (t_{ij} ({\hat{v}}_{ij}) + r_{c}^{k} w_{o}^{k} - π_{ij}^{k *}) x_{ij}^{ko} q_{o}^{k} \\ - \sum_{i \in ST (k)} ψ_{i}^{ko *} δ_{ip}^{ko} w_{o}^{k} - μ_{o}^{k *} \end{matrix}

(28)

\begin{matrix} s . t . \\ \sum_{j : (i, j) \in A} x_{ij}^{ko} = 1 \forall i = o \end{matrix}

(29)

\sum_{j : (i, j) \in A} x_{ij}^{ko} - \sum_{j : (j, i) \in A} x_{ji}^{ko} = 0 \forall i \in N \ {o, s}

(30)

\sum_{j : (j, i) \in A} x_{ji}^{ko} = - 1 \forall i = {s}

(31)

\sum_{(i, j) \in ω} x_{ij}^{ko} - τ_{k} \leq | N | w_{o}^{k} \forall ω \in Ω (x_{ij})

(32)

x_{ij}^{ko} \in {0, 1} \forall (i, j) \in A

(33)

w_{o}^{k} \in {0, 1}

(34)

The objective function (Equation 28) tracks the reduced cost (pricing) for a new improving column, that is, the feasible evacuation path for each evacuee’s demand node and vehicle fuel type. Constraints in Equations 29–31 generate paths originating from an evacuee’s origin node to the shelter. Constraints in Equation 32 enforce the hop betweenness constraints. The constraints guarantee that for every subpath of the evacuation path that is at least $τ_{k}$ or more hops away from the shelter, vehicle type $k$ needs to refuel at the refueling station (see Figure 2). Constraints in Equations 33 and 34 reflect the binary nature of the decision variables.

The pricing subproblem is computationally challenging to solve because of constraints (Equation 32) that could grow exponentially as we explore every subpath of all usable evacuation routes. We therefore develop the “modified label correcting algorithm with hop betweenness constraints” to generate the usable path and solve the pricing routing SP.

Modified Label Correcting Algorithm With Hop Betweenness Constraints

We present the modified label correcting with side constraints to solve the pricing routing SP. We are inspired by the well-known modified label correcting algorithm to find the shortest path ( 44 ). In each iteration, the modified label correcting algorithm visits each adjacent node to find the best route and keeps track of the distance along the route. In this study, the hop betweenness constraints are examined in each iteration of the label correcting algorithm: a vehicle of fuel type $k$ will need to stop and refuel at its refueling station in between $τ_{k}$ hops range along its evacuation path.

In the remainder of this section, we define the notations, label feasibility and dominance, and the algorithm procedure.

Definitions and Notation

We introduce the new network topology setup to apply the modified label correcting algorithm with hop betweenness constraints, on top of those defined above. Let $G_{ko} = (N^{'}, A^{'}), \forall o \in O (s) \forall k \in K$ , be a transportation network with $N'$ as set of nodes and $A'$ as the set of arcs, that consists of the given set of usable refueling stations $ST (k)$ , the set of unused refueling stations $ST' (k)$ , and the current set of $z^{k}$ in the ongoing Benders-inspired decomposition process. We use $G_{ko}$ to provide a usable evacuation path for each vehicle $k$ originating from node $o$ . For every link $(i, j) \in A$ in the network, the travel time is denoted as $t_{ij} ({\hat{v}}_{ij})$ as the travel time with total link flow in the ongoing traffic assignment process. To guarantee feasibility and termination of the algorithm, we introduce a dummy feasibility link that connects the origin node $o$ to the shelter node $s$ with a large value of travel time and one-hop distance to the shelter. Figure 3 presents the modified network $G_{ko}$ and all the parameters used for the modified label correcting algorithm.

Figure 3.

(a) Network topology $G_{ko}$ with existing refueling station and a shelter node and (b) modified network topology $G_{ko}$ with a dummy refueling node and feasibility link.

Furthermore, we define $L_{i}$ as the label of node $i$ in the label correcting algorithm. The label $L_{i}$ carries five parameters, as follows:

L_{i} = {(t_{i}^{m}, l_{i}^{m}, d_{i}^{m}, r_{i}^{m}, pred (i))} \forall i \in N

(35)

where $m$ denotes the label index, $t_{i}^{m}$ denotes the total travel time from node $o$ to node $i$ , $l_{i}^{m}$ denotes the total traveled distance from node $o$ to node $i$ , $d_{i}^{m}$ denotes the total traveled distance from previously visited refueling station to node $i$ , $r_{i}^{m}$ denotes the total refueled distance from previously visited refueling station to node $i$ , and $pred (i)$ stores all the predecessors of node $i$ .

Label Feasibility

The feasibility condition meets the hop betweenness constraints (Equation 32): for every subpath of the evacuation path that is at least $τ_{k}$ or more hops away from the shelter, the vehicle needs to refuel at the refueling station. Label $L_{i}^{m}$ is feasible and generated if $d_{i}^{m} \leq τ_{k}$ .

Label Dominance

The dominance condition informs the optimal usable evacuation path for a vehicle of fuel type $k$ originating from node $o$ . Let us consider $L_{i}^{m} = (t_{i}^{m}, l_{i}^{m}, d_{i}^{m}, r_{i}^{m}, pred (i))$ and $L_{i}^{m 1} = (t_{i}^{m 1}, l_{i}^{m 1}, d_{i}^{m 1}, r_{i}^{m 1}, pred (i))$ . Label $L_{i}^{m}$ is dominated by $L_{i}^{m 1}$ if:

For $i \in N \ {s}$

$t_{i}^{m} > t_{i}^{m 1}$ and $d_{i}^{m} \geq d_{i}^{m 1}$ or $t_{i}^{m} \geq t_{i}^{m 1}$ and $d_{i}^{m} > d_{i}^{m 1}$

For $i = s$

Let $α_{1}, α_{2}$ be the weight of travel time and distance. Then, we introduce the new parameter $g_{i} = α_{1} t_{i} + α_{2} l_{i}$ . Label $L_{i}^{m}$ is dominated by $L_{i}^{m 1}$ if $g_{i}^{m} > g_{i}^{m 1} .$

Finally, we solve the modified label correcting algorithm with hop betweenness constraints following Algorithm 2. For step 3 the node sequence could follow first in, first out (FIFO), last in, first out (LIFO), or best-first search. We use the solution from this algorithm to calculate the pricing objective value (Equation 36).

Algorithm 2 Modified Label Correcting Algorithm with Hop Betweenness Constraints
Input	A network $G_{ko} = (N', A')$ , set of links fixed travel time $t_{ij} ({\hat{v}}_{ij})$ , set of usable refueling station $z^{k}$ , an origin node $o$ , and a shelter node $s$
Output	The usable evacuation path $p \in P (k, o)$
1:	Initialization: Set $L_{s} = (0, 0, 0, 0, s), L_{i} = (\infty, \infty, \infty, \infty, [])$ for all $i \in N \ s$ , and set $OPEN = [s]$
2:	while $OPEN$ is not empty do
3:	Remove node $i$ from $OPEN$
4:	For each arc $(i, j)$ for all $j : (i, j) \in A'$ do
5:	For each non-dominated label $L_{j}$ do
6:	$t_{j} : = t_{i} + t_{ij}$
7:	$l_{j} : = l_{i} + (1 - z_{i})$
8:	$d_{j} : = d_{i} + 1$
9:	$r_{j} : = l_{j} - d_{j}$
10:	$pred (j) \leftarrow pred (j) \cup i$
11:	If $d_{j} \geq τ_{k}$ then
12:	discard new label $L_{j}$ and use old label
13:	else
14:	generate new label $L_{j}$
15:	eliminate all dominated $L_{j}$
16:	Update travel time and distance of all dummy refueling links, $d_{ij} : = - min (d_{i}, τ_{k}) \forall (i, j) : i \in ST (k), j \in S T^{'} (k)$ $t_{ij} : = - r_{c} min (d_{i}, τ_{k}) \forall (i, j) : i \in ST (k), j \in S T^{'} (k)$
17:	If $j \neq s$ then
18:	$OPEN \leftarrow OPEN \cup j$

Numerical Experiments

Experiments illustrate the application of the proposed refueling infrastructure model on the South Florida transportation network. Our analysis uses the South Florida transportation network to show the impact of driving range, the cost of refueling infrastructure, and the heterogeneity of vehicles in the deployment of emergency refueling stations to support alternative fuel vehicle evacuation plans. The optimization problems (MP and restricted routing SP) and solution algorithms are modeled and solved using the commercial solver Gurobi ( 43 ) and its Python interface. The networks and their operations are modeled using NetworkX ( 45 ).

Network Description

The network topology and properties of the South Florida transportation network are obtained from Sun et al. ( 46 ). The South Florida network consists of 82 nodes and 234 links. The total network travel demand is 65,707 vehicles with 83 origin–destination pairs. The total evacuee demand of each evacuee node is the total flow originating from the origin nodes of the habitual origin–destination matrix of the South Florida network ( 15 ). There are 31 nodes with zero evacuee travel demand, called “intersection nodes.” There are 32 nodes that may host alternative refueling stations in the South Florida network, where 30 nodes are obtained from the findings on optimal deployment by Sun et al. ( 46 ), and additional nodes 32 and 34 to cover evacuation demand on the northwest side of the network. We use these nodes to define the set of existing refueling stations and candidate nodes of emergency refueling stations.

We consider five shelters, located at nodes 1, 50, 64, 41, and 81. We added node s as a dummy shelter node and five direct links to node $s$ with zero travel time and infinite capacity. The South Florida numerical experiments would be conducted using the modified transportation network where evacuees are directed to the shelter node s. Figure 4 presents the original South Florida network configuration (Figure 4a) and the modified transportation network (Figure 4b). The South Florida network has a diameter of 100 miles with uniform link distance (on average 5 miles). In our numerical experiments, we scale up every link in the network to 50 miles to capture the refueling needs of alternative fuel vehicles with a driving range of 100 to 400 miles for the numerical experiments. Then, we assume that one hop would represent 50 miles and every link in the network is a one-hop unit as all links have the same distance. We therefore use the South Florida network configuration to conduct the numerical experiment, with distance adjustments commonly employed in electrified transportation networks ( 21 , 24 ).

Figure 4.

(a) The South Florida transportation network with 32 candidates of refueling station nodes and five shelter nodes, (b) the modified South Florida transportation network with a shelter node s.

Impact of Driving Range Constraints on the Deployment of Emergency Refueling Stations

We examine the impact of the driving range of alternative fuel vehicles in the deployment of emergency refueling stations in the evacuation network. In this experiment, we solve the problem where every evacuee uses a vehicle of the same fuel type to highlight the impact of refueling demand without considering the impact of vehicles of multiple fuel types on evacuation routing. We set $| K | = 1$ and the refueling time rate $r_{c}^{k} = 15$ min per hop. We consider nine existing refueling stations located at nodes [4, 10, 21, 48, 59, 65, 67, 74, 77]. Then, we set the remaining 24 nodes as the candidates to open emergency refueling stations, as shown in Figure 4, with ${c_{f}}_{i}^{k} = 100, 000$ for all candidate nodes. We explore the optimal deployment for four different vehicle types with driving range limits of $τ_{k} = {4, 5, 6, 7}$ hops.

Figure 5 presents four optimal deployments of the emergency stations with their corresponding evacuation routes. The emergency refueling stations are deployed to accommodate the longest evacuation path in the evacuation routes and provide access to refueling stations within at most a span of driving range. For instance, in Figure 5a, the emergency refueling station is deployed at node 43, maintaining a span of four hops to accommodate evacuees along paths 28-49-26-48-46-45-44-43-81-s and 22-21-71-73-43-81-s. Similarly, in Figure 5b, we deploy four emergency refueling stations at nodes 32, 63, 17, and 43, resulting in refueling station access with a span of five hops in the network. As we increase the driving range, the emergency refueling stations are located with reduced density, resulting in reduced number of deployed emergency refueling stations.

Figure 5.

Optimal deployment of emergency refueling stations and evacuation tree routes for four cases of vehicle driving range: (a) $τ_{k}$ = 4 hops, (b) $τ_{k}$ = 5 hops, (c) $τ_{k}$ = 6 hops, and (d) $τ_{k}$ = 7 hops.

As shown in Figure 5a, the deployment of seven emergency refueling stations results in lower evacuation time than in Figure 5b with four emergency refueling stations deployed. Note that the objective function of the location model weighs the deployment cost and total system evacuation time equally. The optimal deployment and routing therefore depend on the trade-off between these objective components. As we increase the driving range, the overall objective value decreases, as shown in Table 2.

Table 2.

Optimal Deployment of Emergency Refueling Stations and Evacuation Performance for Different Driving Ranges

Driving range limit, $τ_{k}$	Number of emergency refueling stations	Positions of emergency refueling stations	Objective value	Evacuation performance (hour-vehicle)	Average evacuation time (minute-vehicle)
4	7	5, 32, 62, 63, 58, 66, 43	980,140.06	280,140.06	255.8
5	4	32, 63, 17, 43	726,847.38	326,847.38	298.45
6	4	32, 63, 17, 73	673,333.80	273,333.80	249.59
7	0	-	198,851.47	198,851.47	181.57

For the case of six hops, as shown in Figure 5c, we deploy four emergency refueling stations at nodes 32, 63, 17, and 73, resulting in lower evacuation time compared with the case of Figure 5b, as expected. In Figure 5c, the emergency refueling stations are deployed with a span of fewer than six hops. The optimal deployment also depends on the given potential location of emergency refueling stations. For instance, according to the refueling rule, the evacuation path 20-19-18-17-39-40-41-s must provide refueling access along its route. Through the given potential emergency refueling station set, we could only deploy on node 17, resulting in a span of fewer than six hops.

Figure 5d shows that no additional emergency refueling station is needed; the existing refueling network is sufficient to provide access to the evacuees following the designated routes. The evacuation route is unique and depends on the deployment of refueling stations and the vehicles’ driving range. It can be the case that for a particular driving range, the existing deployment of refueling stations is sufficient to support evacuation planning, and no emergency refueling stations are needed. Emergency planners should account for the vehicles’ driving range to site emergency refueling stations strategically, considering the accessibility of the network farthest from the shelter to meet evacuee demand.

Furthermore, in Figure 5a, we observe that the emergency refueling station at node 66 is located near the existing refueling station at node 67. Evacuees from nodes 72, 69, and 66 refuel at emergency station node 66, while all evacuees originating from nodes 16, 17, 18, 19, and 20 refuel at an existing station in node 67. Similarly, emergency stations are adjacently deployed at nodes 63 and 62. Evacuees originating from nodes 54, 60, and 61 refuel at the emergency station node 62 instead of node 63. We observe some adjacent deployments in Figure 5c. In our model, we follow the $| K |$ -evacuation tree problem ( 15 ) that forms a tree structure to the shelter to accommodate the seamlessness attribute of the evacuation route designation. Such a structure results in concentrated evacuation flow near the shelter. Placing adjacent emergency refueling stations near the shelter may be needed to accommodate concentrated evacuation flow near the shelter.

Impact of Vehicle Heterogeneity on the Deployment of Emergency Refueling Stations

We assume three types of alternative fuel vehicles: vehicle type I represents a gasoline vehicle with a large driving range and a dense existing refueling station network; vehicle type II represents an alternative fuel vehicle with a short driving range and a sparse existing refueling station network; and vehicle type III represents an alternative vehicle fuel type with a medium driving range and a sparse existing refueling network. The vehicle characteristics and refueling station deployment for each type are presented in Table 3. We examine two cases of evacuation route design: in Case A, there are three vehicle types with type I dominating and in Case B, there are three vehicle types with type II dominating the share of alternative fuel technologies.

Table 3.

Vehicle Characteristics and Two Cases of Vehicle Shares in South Florida

Case	Number of vehicles, $\| K \|$	Vehicle type	Population share	Driving range limit, $τ_{k}$	Refueling rate, $r_{c}^{k}$	Number of existing refueling stations	Positions of existing refueling stations
A	3	I	70%	7	5	14	4, 10, 14, 15, 16, 17, 21, 48, 59, 65, 67, 73, 74, 77
		II	15%	4	30	9	4, 10, 21, 48, 59, 65, 67, 74, 77
		III	15%	5	10	9	4, 10, 21, 48, 59, 65, 67, 74, 77
B	3	I	20%	7	5	14	4, 10, 14, 15, 16, 17, 21, 48, 59, 65, 67, 73, 74, 77
		II	55%	4	30	9	4, 10, 21, 48, 59, 65, 67, 74, 77
		III	35%	5	10	9	4, 10, 21, 48, 59, 65, 67, 74, 77

We have already shown the optimal deployment for vehicles of type II only in Figure 5a, and for vehicles of type III in Figure 5b. In Case A, we consider three vehicle types: type I dominates the vehicle market, while types II and III are driven by smaller shares of drivers. Figure 6 presents the deployment plan for each of the vehicle types in Case A. We observe that no emergency refueling stations are needed to support the evacuation routing of type I vehicles because they have a long driving range. We deploy seven emergency refueling stations for type II and six emergency refueling stations for type III vehicles. We require more emergency refueling stations for type III compared with the case in Figure 5b. When vehicles with the largest driving range dominate the market share, more emergency refueling stations are required for vehicles with shorter driving ranges. Following the system optimum, the vehicle type with the largest driving range would dominate the evacuation routing since it is the most prevalent in the market. This condition would create challenges for the other evacuees with minority vehicle types with shorter ranges, which require a greater number of emergency refueling stations to support their evacuation routing.

Figure 6.

Optimal deployment of emergency refueling stations for Case A: (a) type I vehicles, (b) type II vehicles, and (c) type III vehicles.

Figure 7 presents the deployment plan for each vehicle type in Case B, where the evacuation demand of type II vehicles dominates the market. We observe that no emergency refueling stations are needed to support the evacuation of type I vehicles because they have a long driving range. We deploy seven emergency refueling stations for type II vehicles. For the case of type III vehicles, we deploy five emergency refueling stations, which are fewer compared with Case A. When the vehicles with shorter driving ranges dominate the vehicle shares in the network, fewer emergency refueling stations are needed as we can optimize the evacuation routing to better support the vehicles’ range-limiting specifications.

Figure 7.

Optimal deployment of emergency refueling stations for Case B: (a) type I vehicles, (b) type II vehicles, and (c) type III vehicles.

The evacuation routing is the same for the three vehicle types and the case with a single vehicle with range of four hops in Figure 5a. When the population share of type II vehicles is the majority, the evacuation route better accommodates this vehicle type to achieve the system optimum. Since types I and III have larger driving ranges, this evacuation route plan is also feasible for those vehicles, resulting in the same evacuation routing. However, the total system evacuation performance worsens by 80% compared with Case A. The result is expected since vehicle types II and III have shorter ranges and larger population distributions in the network compared with Case A. Note that the optimal deployment for type II vehicles only was already shown in Figure 5a, and for type III only in Figure 5b. From Table 2 it can be seen that the evacuation times for type II vehicles with a range of four hops and type III with five hops have worsened, by on average 260 min per vehicle, because of their limited driving range. For Case B, therefore, total system evacuation performance is expected to worsen significantly compared with Case A because of the limited driving ranges and larger population shares of vehicle types II and III (Table 4).

Table 4.

Optimal Deployment of Emergency Refueling Stations and Evacuation Performance for Cases of Alternate Vehicle Type Shares, Addressing Heterogeneity

Case	Vehicle type	Number of emergency refueling stations	Position of emergency refueling stations	Evacuation performance (hour-vehicle)	Average evacuation time (minute-vehicle)
A	I	0	-	155,720.40	142.19
	II	7	5, 32, 63, 62, 58, 66, 43
	III	6	5, 32, 63, 17, 43, 78
B	I	0	-	280,140.06	255.80
	II	7	5, 32, 63, 62, 58, 17, 43
	III	5	5, 32, 63, 17, 43

Conclusion

The adoption of alternative fuel vehicles has grown rapidly in the USA ( 47 ) with governmental support ( 17 , 18 ) that incentivizes ownership of such vehicles. Their advent challenges conventional evacuation route planning practices ( 10 , 11 ). Strategic placement of alternative refueling stations can help reduce the vulnerability of alternative fuel vehicles and improve their evacuation times before imminent disasters ( 10 , 15 ). To date, very few studies have focused on deploying emergency alternative refueling stations that support the evacuation routing for alternative fuel vehicles.

This paper presents an alternative refueling station location model, based on a location-routing problem, to deploy emergency refueling stations optimally to support evacuation routing. We use a Benders-inspired decomposition procedure to solve the location problem and a matheuristic branch-and-price method to design evacuation routes with hop betweenness constraints. We present the numerical experiments in the South Florida transportation network to evaluate the role of alternative fuel vehicle specifications and vehicle heterogeneity on the deployment plan.

The experiments show that the optimal deployment of emergency refueling stations depends on the bounds of the different vehicles’ driving ranges. The refueling stations in the model are deployed to accommodate the longest evacuation path in the evacuation route. As we increase the driving range of vehicles, the emergency refueling stations can be located with greater distance between them, resulting in a reduced number of deployed stations. Vehicle heterogeneity results in deployment trade-offs. When the vehicle fuel type with a larger driving range dominates in the network, this fuel type will dominate the evacuation route designation based on the system’s optimization. The evacuee population that uses vehicles with lower range specifications would require more emergency refueling stations to support such evacuation routing. When vehicles with a shorter driving range dominate the population share, fewer emergency refueling stations are needed to support their evacuation routing. Emergency planners must strategically deploy emergency refueling stations to support evacuation planning considering the vehicles’ fuel types and their respective shares in the network.

Limitations of this paper that need to be addressed in future studies include accounting for the refueling station capacity, refueling delay, and queueing near stations during the evacuation. The current model assumes that every refueling station has the capacity to serve all incoming vehicles, without any queueing and delaying considerations. However, alternative fuel infrastructure might have a limited number of refueling hoses or charging ports to accommodate evacuees’ vehicles, which could result in queueing at a refueling infrastructure node. Integration with queueing models and balancing fuel demand and supply modeling might fulfill this goal. Furthermore, the current model assumes that the refueling rate for each fuel type depends on the station type and that every vehicle would be compatible with the refueling station provided. However, the refueling rate could depend on the refueling station type, connector/hose type, and vehicle type.

Supplemental Material

sj-pdf-1-trr-10.1177_03611981231171156 – Supplemental material for Refueling Station Location Model to Support Evacuation of Alternative Fuel Vehicles

Supplemental material, sj-pdf-1-trr-10.1177_03611981231171156 for Refueling Station Location Model to Support Evacuation of Alternative Fuel Vehicles by Denissa Sari Darmawi Purba, Simon Balisi and Eleftheria Kontou in Transportation Research Record

Footnotes

Acknowledgements

This research was partially supported by the Illinois-Indiana Sea Grant Faculty Scholar Program.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: E. Kontou, D. S. D. Purba; data collection: D. S. D. Purba, S. Balisi; analysis and interpretation of results: D. S. D. Purba, E. Kontou, S. Balisi; draft manuscript preparation: D. S. D. Purba, E. Kontou. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was partially supported by the Illinois-Indiana Sea Grant Faculty Scholar Program.

ORCID iDs

Denissa Sari Darmawi Purba

Eleftheria Kontou

Supplemental Material

Supplemental material for this article is available online.

The authors confirm their full personal access to all aspects of the writing and research process and take full responsibility for the paper. The opinions expressed in this paper are those of the authors and not those of the sponsors. This paper does not constitute a standard, specification, or regulation.

References

Jacobson

M. Z.

Review of Solutions to Global Warming, Air Pollution, and Energy Security. Energy and Environmental Science, Vol. 2, No. 2, 2009, pp. 148–173. https://doi.org/10.1039/b809990c

Zhang

Wallington

T. J.

Tamor

M. A.

McElroy

M. B.

Zhang

K. M.

Nielsen

C. P.

Hao

Economic and Climate Benefits of Electric Vehicles in China, the United States, and Germany. Environmental Science and Technology, Vol. 53, No. 18, 2019, pp. 11013–11022. https://doi.org/10.1021/acs.est.9b00531

Tessum

C. W.

Hill

J. D.

Marshall

J. D.

Life Cycle Air Quality Impacts of Conventional and Alternative Light-Duty Transportation in the United States. Proceedings of the National Academy of Sciences of the United States of America, Vol. 111, No. 52, 2014, pp. 18490–18495. https://doi.org/10.1073/pnas.1406853111

Vehicle Technologies Office. FOTW #1221, January 17, 2022: Model Year 2021 All-Electric Vehicles Had a Median Driving Range about 60% That of Gasoline Powered Vehicles. U.S. Department of Energy, Office of Energy Efficiency & Renewable Energy. https://www.energy.gov/eere/vehicles/articles/fotw-1221-january-17-2022-model-year-2021-all-electric-vehicles-had-median. Accessed February 20, 2022.

Electric Vehicle Charging Station Locations. U.S. Department of Energy, Alternative Fuels Data Center, https://afdc.energy.gov/fuels/electricity_locations.html#/find/nearest?fuel=ELEC. Accessed July 29, 2022.

American Petroleum Institute. Service Station FAQs, https://www.api.org/oil-and-natural-gas/consumer-information/consumer-resources/service-station-faqs. Accessed July 30, 2022.

Fuel Cell Electric Vehicles. U.S. Department of Energy, Alternative Fuels Data Center. https://afdc.energy.gov/vehicles/fuel_cell.html. Accessed July 13, 2021.

Compressed Natural Gas Fueling Stations. U.S. Department of Energy, Alternative Fuels Data Center. https://afdc.energy.gov/fuels/natural_gas_cng_stations.html. Accessed July 13, 2021.

Developing Infrastructure to Charge Plug-in Electric Vehicles. U.S. Department of Energy, Alternative Fuels Data Center. https://afdc.energy.gov/fuels/electricity_infrastructure.html. Accessed July 12, 2021.

10.

Adderly

S. A.

Manukian

Sullivan

T. D.

Son

Electric Vehicles and Natural Disaster Policy Implications. Energy Policy, Vol. 112, pp. 437–448. https://doi.org/10.1016/j.enpol.2017.09.030

11.

Feng

Lin

Xian

Chester

M. V.

Can We Evacuate From Hurricanes With Electric Vehicles?

Transportation Research Part D: Transport and Environment, Vol. 86, 2020, P. 102458. https://doi.org/10.1016/j.trd.2020.102458

12.

Lindell

M. K.

Murray-Tuite

Wolshon

Baker

E. J.

Large-Scale Evacuation. Routledge, New York, NY, 2019.

13.

Hori

Schafer

M. J.

Bowman

D. J.

Displacement Dynamics in Southern Louisiana After Hurricanes Katrina and Rita. Population Research and Policy Review, Vol. 28, No. 1, 2009, pp. 45–65. https://doi.org/10.1007/s11113-008-9118-1

14.

FEMA. Planning Considerations: Evacuation and Shelter-in-Place. Federal Emergency Management Agency, 2019. https://www.fema.gov/sites/default/files/2020-07/planning-considerations-evacuation-and-shelter-in-place.pdf

15.

Purba

D. S. D.

Kontou

Vogiatzis

Evacuation Route Planning for Alternative Fuel Vehicles. Transportation Research Part C: Emerging Technologies, Vol. 143, 2022, P. 103837. https://doi.org/10.1016/j.trc.2022.103837

16.

Federal Highway Administration. Good Practices in Transportation Evacuation Preparedness and Response – Phase 1 – Preparation and Activation – FHWA Emergency Transportation Operations. Emergency Transportation Operations. https://ops.fhwa.dot.gov/publications/fhwahop09040/phase1.htm. Accessed February 27, 2022.

17.

Fact Sheet: President Biden Announces Steps to Drive American Leadership Forward on Clean Cars and Trucks. The White House Briefing Room: Statements and Releases. https://www.whitehouse.gov/briefing-room/statements-releases/2021/08/05/fact-sheet-president-biden-announces-steps-to-drive-american-leadership-forward-on-clean-cars-and-trucks/. Accessed February 28, 2022.

18.

Illinois Press Release: Gov. Pritzker Signs Transformative Legislation Establishing Illinois as a National Leader on Climate Action. State of Illinois Press Release. https://www.illinois.gov/news/press-release.23893.html. Accessed February 28, 2022.

19.

Gnann

Funke

Jakobsson

Plötz

Sprei

Bennehag

Fast Charging Infrastructure for Electric Vehicles: Today’s Situation and Future Needs. Transportation Research Part D: Transport and Environment, Vol. 62, 2018, pp. 314–329. https://doi.org/10.1016/J.TRD.2018.03.004

20.

Ghamami

Kavianipour

Zockaie

Hohnstadt

L. R.

Ouyang

Refueling Infrastructure Planning in Intercity Networks Considering Route Choice and Travel Time Delay for Mixed Fleet of Electric and Conventional Vehicles. Transportation Research Part C: Emerging Technologies, Vol. 120, 2020, P. 102802. https://doi.org/10.1016/j.trc.2020.102802

21.

Yin

Zhou

Deploying Public Charging Stations for Electric Vehicles on Urban Road Networks. Transportation Research Part C: Emerging Technologies, Vol. 60, 2015, pp. 227–240. https://doi.org/10.1016/J.TRC.2015.08.018

22.

Kuby

Lim

The Flow-Refueling Location Problem for Alternative-Fuel Vehicles. Socio-Economic Planning Sciences, Vol. 39, No. 2, 2005, pp. 125–145. https://doi.org/10.1016/j.seps.2004.03.001

23.

Kim

J. G.

Kuby

The Deviation-Flow Refueling Location Model for Optimizing a Network of Refueling Stations. International Journal of Hydrogen Energy, Vol. 37, No. 6, 2012, pp. 5406–5420. https://doi.org/10.1016/j.ijhydene.2011.08.108

24.

Yin

Lawphongpanich

Network Equilibrium Models with Battery Electric Vehicles. Transportation Research Part B: Methodological, Vol. 67, 2014, pp. 306–319. https://doi.org/10.1016/j.trb.2014.05.010

25.

Chen

Qian

Miao

Ukkusuri

Optimal Charging Facility Location and Capacity for Electric Vehicles Considering Route Choice and Charging Time Equilibrium. Computers and Operations Research, Vol. 113, 2020, P. 104776. https://doi.org/10.1016/j.cor.2019.104776

26.

Balcik

Beamon

B. M.

Facility Location in Humanitarian Relief. International Journal of Logistics Research and Applications, Vol. 11, No. 2, 2008, pp. 101–121. https://doi.org/10.1080/13675560701561789

27.

Sheu

J. B.

Challenges of Emergency Logistics Management. Transportation Research Part E: Logistics and Transportation Review, Vol. 43, No. 6, 2007, pp. 655–659.

28.

Gao

Chiu

Y. C.

Wang

Küçükyavuz

Optimal Refueling Station Location and Supply Planning for Hurricane Evacuation. Transportation Research Record: Journal of the Transportation Research Board, 2010. 2196: 56–64.

29.

Sabbaghtorkan

Batta

On the Analysis of an Idealized Model to Manage Gasoline Supplies in a Short-Notice Hurricane Evacuation. OR Spectrum, Vol. 44, No. 2, 2022, pp. 911–945. https://doi.org/10.1007/s00291-022-00665-0

30.

MacDonald

C. D.

Kattan

Layzell

Modelling Electric Vehicle Charging Network Capacity and Performance During Short-Notice Evacuations. International Journal of Disaster Risk Reduction, Vol. 56, 2021, P. 102093. https://doi.org/10.1016/j.ijdrr.2021.102093

31.

Soleimaniamiri

Optimal Mass Evacuation Planning for Electric Vehicles Before Natural Disasters. Transportation Research Part D: Transport and Environment, Vol. 107, 2022, P. 103292. https://doi.org/10.1016/j.trd.2022.103292

32.

Sheffi

Urban Transportation Networks. Prentice-Hall, Englewood Cliffs, NJ, 1985.

33.

Lee

Han

Benders-and-Price Approach for Electric Vehicle Charging Station Location Problem Under Probabilistic Travel Range. Transportation Research Part B: Methodological, Vol. 106, 2017, pp. 130–152. https://doi.org/10.1016/J.TRB.2017.10.011

34.

Fischetti

Ljubic

Sinnl

Redesigning Benders Decomposition for Large-Scale Facility Location. Management Science, Vol. 63, No. 7, 2016, pp. 2146–2162. https://doi.org/10.1287/MNSC.2016.2461

35.

Bayram

Yaman

Shelter Location and Evacuation Route Assignment Under Uncertainty: A Benders Decomposition Approach. Transportation Science, Vol. 52, No. 2, 2018, pp. 416–436. https://doi.org/10.1287/trsc.2017.0762

36.

Arslan

Karaşan

O. E.

A Benders Decomposition Approach for the Charging Station Location Problem With Plug-in Hybrid Electric Vehicles. Transportation Research Part B: Methodological, Vol. 93, 2016, pp. 1339–1351. https://doi.org/10.1016/j.trb.2016.09.001

37.

Lusby

R. M.

Range

T. M.

Larsen

A Benders Decomposition-Based Matheuristic for the Cardinality Constrained Shift Design Problem. European Journal of Operational Research, Vol. 254, No. 2, 2016, pp. 385–397. https://doi.org/10.1016/j.ejor.2016.04.014

38.

Sherali

H. D.

Adams

W. P.

A Discrete Location-Allocation Problem. Operations Research, Vol. 32, No. 4, 1984, pp. 878–900.

39.

Andreas

A. K.

Smith

J. C.

Decomposition Algorithms for the Design of a Nonsimultaneous Capacitated Evacuation Tree Network. Networks, Vol. 53, No. 2, 2009, pp. 91–103. https://doi.org/10.1002/net.20278

40.

Chitsaz

Cordeau

J. F.

Jans

A Unified Decomposition Matheuristic for Assembly, Production, and Inventory Routing. INFORMS Journal on Computing, Vol. 31, No. 1, 2019, pp. 134–152. https://doi.org/10.1287/ijoc.2018.0817

41.

Geoffrion

Generalized Benders Decomposition. Journal of Optimization Theory and Applications, Vol. 10, No. 4, 1972, pp. 237–260.

42.

Wentges

Accelerating Benders’ Decomposition for the Capacitated Facility Location Problem. Mathematical Methods of Operations Research, Vol. 44, 1996, 267–290.

43.

Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, https://www.gurobi.com.

44.

Bertsekas

D. P.

A Simple and Fast Label Correcting Algorithm for Shortest Paths. Networks, Vol. 23, 1993, pp. 703–709.

45.

Hagberg

P. Swart

Chult

D. S.

Exploring network structure, dynamics, and function using NetworkX. Los Alamos National Lab.(LANL), Los Alamos, NM, 2008

46.

Sun

Chen

Yin

Integrated Planning of Static and Dynamic Charging Infrastructure for Electric Vehicles. Transportation Research Part D: Transport and Environment, Vol. 83, 2020, p. 102331. https://doi.org/10.1016/j.trd.2020.102331

47.

New Plug-in Electric Vehicle Sales in the United States Nearly Doubled from 2020 to 2021. U.S. Department of Energy. https://www.energy.gov/energysaver/articles/new-plug-electric-vehicle-sales-united-states-nearly-doubled-2020-2021. Accessed March 2, 2022.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.10 MB