# A Continuous Deviation-Flow Location Problem for an Alternative-Fuel Refueling Station on a Tree-Like Transportation Network

Authors: Sang Jin Kweon; Seong Wook Hwang; Jose A. Ventura
Journal: Journal of Advanced Transportation
 (2017)

---

## Abstract

Due to the increasing popularity of alternative-fuel (AF) vehicles in the last two decades, several models and solution techniques have been recently published in the literature to solve AF refueling station location problems. These problems can be classified depending on the set of candidate sites: when a (finite) set of candidate sites is predetermined, the problem is called discrete; when stations can be located anywhere along the network, the problem is called continuous. Most researchers have focused on the discrete version of the problem, but solutions to the discrete version are suboptimal to its continuous counterpart. This study addresses the continuous version of the problem for an AF refueling station on a tree-type transportation network when a portion of drivers are willing to deviate from their preplanned simple paths to receive refueling service. A polynomial time solution approach is proposed to solve the problem. We first present a new algorithm that identifies all possible deviation options for each travel path. Then, an efficient algorithm is used to determine the set of optimal locations for the refueling station that maximizes the total traffic flow covered. A numerical example is solved to illustrate the proposed solution approach.


---

## Body

## 1. Introduction

The US national highway system significantly contributes to the country’s economic development. In particular, it plays a major role in providing mobility for goods and services. Using highways, trucks carry the largest shares by value, tons, and ton-miles for shipments moving 750 or fewer miles in the US [1]. As concerns over climate change are increasingly becoming a global issue, logistics companies are interested in replacing their diesel trucks by alternative-fuel (AF) trucks [2]. However, to introduce AF trucks to logistics companies successfully, a well-designed refueling infrastructure in the highway system is a prerequisite. The rest of this section highlights the relevance of tree networks in transportation, the significance of the single station location problem for a new AF refueling infrastructure, and the continuous version of the problem and summarizes the main contributions of this research work.


### 1.1. Tree Structure in Transportation Networks

While the US national highway system consists of a set of circuit networks, if it is partitioned into local highway systems by operating authority, then many of them form trees or tree-like networks. Table1 displays the local highway systems in the US along with their operating authorities that have tree or tree-like network structures. As shown in this table, 10 turnpikes and 8 portions of interstate highways within certain states constitute tree structures [3]. Furthermore, if we consolidate beltways and cycles within metro areas into single vertices, then 11 more portions of interstate highways within certain states can also be considered as tree-like structures [4, 5]. In addition, we can observe that toll roads and highways in other countries, such as Chile, Croatia (southern and northeast regions), Indonesia, Ireland (excluding the Dublin region), Malaysia, Norway (northern region), Philippines, Slovakia, Spain (excluding the Catalan region), and Serbia, to name a few, have tree or tree-like network structures. Note also that road networks in sparsely settled areas are generally trees, since tree road networks are the cheapest to construct.Table 1
Tree network structures in the US highways.
State
Roadtype∗
Type of network structure
Component highways
Operating authority
AL
I
Tree-like, including Birmingham beltway
I-20, I-22, I-59, I-65, I-85
AL Department of Transportation (DOT)
AK
S
Tree in Southcentral area
AK-1, AK-3
AK DOT and Public Facilities
AZ
I
Tree-like, including Phoenix beltway
I-8, I-10, I-15 I-17, I-19, I-40
AZ DOT
AR
I
Tree-like, including Little Rock beltway
I-30, I-40, I-49, I-55, I-530, I-555
AR Highway and Transportation Department
CO
I
Tree-like, including Denver beltway
I-25, I-70, I-76
CO DOT
GA
I
Tree-like, including beltways in Atlanta, Augusta, Columbus, and Macon
I-16, I-20, I-59, I-75, I-85, I-185, I-285, I-675, I-985
GA DOT
ID
I
Tree
I-15, I-84, I-86, I-90
ID Transportation Department
IN
T
Tree
I-80, I-90
IN Finance Authority/ ITR Concession Company LLC
KS
T
Tree
I-35, I-70, I-335, I-470
KS Turnpike Authority
ME
T
Tree
I-95
ME Turnpike Authority
MA
T
Tree
I-90
MA DOT
MN
I
Tree-like, including Minneapolis beltway
I-35, I-90, I-94
MN DOT
MS
I
Tree
I-20, I-22, I-55, I-59
MS DOT
MT
I
Tree
I-15, I-90, I-94
MT DOT
NE
I
Tree-like, including Omaha beltway
I-76, I-80
NE Department of Roads
NV
I
Tree-like, including Las Vegas beltway
I-15, I-80, I-515
NV DOT
NH
T
Tree
I-93, I-95, NH-3, NH-16
NH DOT
NM
I
Tree
I-10, I-25, I-40
NM DOT
NY
T
Tree
I-87, I-90
NY State Thruway Authority
ND
I
Tree
I-29, I-94
ND DOT
OH
T
Tree
I-76, I-80, I-90
OH Turnpike Commission
OK
T
Tree
I-35, I-40, I-44, US-66, US-165, US-177, US-412, OK-1, OK-51, OK-66, OK-165
OK Turnpike Authority
OR
I
Tree-like, including Portland beltway
I-5, I-84
OR DOT
PA
T
Tree
I-70, I-76, I-276, I-376, I-476, PA-43, PA-60, PA-66, PA-576
PA Turnpike Commission
SD
I
Tree
I-29, I-90
SD DOT
UT
I
Tree-like, including Salt Lake City beltway
I-15, I-70, I-80, I-84
UT DOT
VT
I
Tree
I-89, I-91, I-93
VT Agency of Transportation
WV
T
Tree
I-64, I-77
WV Parkways Authority
WY
I
Tree
I-25, I-80, I-90
WY DOT
I
∗: interstate highway, S: state highway, and T: turnpike.Trees are central to the structural understanding of networks and graphs and often occur with additional attributes such as roots and vertex-ordering. They have a wide range of applications, including data storage, searching, information processing, and facility location [6]. Because it is easier to get insights into tree network problems, numerous articles in classical facility location problems on transportation networks without cycles are available in the literature ([7–9] and others).


### 1.2. Setting Up an AF Refueling Station on Toll Roads

Building an AF refueling station usually requires a substantial investment. For example, it takes $1.8 million to $4.7 million to construct a natural gas refueling station on the Pennsylvania Turnpike without including the land value [10]. Due to the financial risk, it is unusual to build multiple AF refueling stations on the same road network simultaneously. Instead, an operating authority may be more inclined in setting up a single station first in a high traffic area and planning the gradual future construction of additional stations with the goal of maximizing the coverage of traffic flow. For example, the Pennsylvania Turnpike Commission opened the first refueling station at New Stanton Service Plaza in 2014 to serve compressed natural gas (CNG) vehicles and it currently remains as the only CNG station on the turnpike [11]. As a second example, the Oklahoma Turnpike Authority opened the first CNG station at Stroud Travel Plaza on the turnpike in 1991, which was renovated in 2014, and then 23 years later, the authority opened the second CNG station at McAlester Travel Plaza on the turnpike in 2014 [12–14]. Note that both of these turnpikes form tree networks.Several articles have been published regarding the classical single facility location problem on tree networks ([7, 15–17] and others). Three versions of the problem exist depending on the main objective: the objective of the 1-median problem is to minimize the total travel distance from the new facility to existing facilities; in the 1-center problem, the objective is to minimize the maximum travel distance; and the covering problem finds the location of a facility that can reach (cover) the maximum number of existing facilities within a given travel distance. Francis et al. ([5], Chapter 7) describe motivating applications of location problems on trees, as well as properties and solution algorithms for the three versions of the problem. None of the algorithms developed to solve classical single facility location problems on tree networks, however, is suitable for locating an AF refueling station on tree-like road networks because of the differences in the objective function. In the location of an AF station, the objective of maximizing the total traffic flow covered by the station is more desirable by operating authorities. Furthermore, locating an AF refueling station requires a different strategy to deal with demand. Note that the classical single facility location problem regards demand as a weight at vertices. Instead, drivers (demand) on toll roads and highways usually stop by the refueling station on the way to their final destination. Considering that this refueling activity for a driver is a unit of demand, a path-based demand model, in which the demand on the travel path can be covered by a facility located on the path, is more appropriate for solving the AF refueling station location problem.


### 1.3. Continuous Refueling Station Location Problem

We can classify refueling station location problems into two types depending on the set of candidate sites: when a preliminary (finite) set of candidate sites is given, this problem is calleddiscrete; when the station can be located anywhere along the network, the problem is calledcontinuous. Ventura et al. [18] introduced the continuous version of the refueling station location problem. Since an optimal solution to the discrete version of the problem is always a feasible solution to the continuous version, an optimal solution to the continuous refueling station location problem can achieve a considerable improvement in terms of demand coverage. The continuous version of the problem is, however, more challenging than its discrete counterpart due to the size of the search space.


### 1.4. Contribution

In this study, we consider the continuous version of an AF refueling station location problem on a tree network, where a portion of drivers have the option of selecting a deviation path if the refueling station is not located along their preplanned routes. We believe that this is the first research work on the continuous version of the problem where the deviation option is considered. This option is expected to be very common for drivers with AF vehicles during the introductory period of these vehicles to the market since AF refueling infrastructures are usually nonexistent or underdeveloped. The deviation option is also available to drivers of conventional fossil-fuel vehicles (powered by gasoline and diesel engines) when they cannot find a refueling station on their routes. Thus, considering deviation will make the problem more practical in deciding the potential location for the refueling station.Compared with the original continuous refueling station location problem [18], the theoretical contribution of this study is twofold. First, we derive a number of properties to identify the deviation options for each origin/destination (O/D) pair considering the length of the simple path, the minimum fuel tank levels at the origin and destination, and the vehicle driving range. Then, we develop a novel algorithm that finds all deviation paths for each O/D pair in polynomial time. Using the original path in the tree network and the corresponding deviation options, we construct the subtree that contains all the potential station locations that cover the traffic flow of the corresponding O/D pair. Second, we derive a mathematical property that characterizes the set of optimal station locations that do not require Ventura et al. [18] assumption that the intersection vertices in all used simple paths must have positive traffic flow in at least one short trip. This property is essential in the development of the algorithm that finds the complete set of optimal station locations for the entire network.By allowing vehicle deviation in the continuous refueling station location problem, the solution approach proposed in this article is capable of finding all possible alternative paths for any O/D pair and improving suboptimal solutions obtained by the existing models in the literature. To best of our knowledge, all the existing models that consider vehicle deviation solve discrete versions of the problem, and therefore, they choose locations from a predetermined set of candidate sites (vertices) and enable deviation only if such vertices can be reached within the vehicle driving range. Therefore, their solutions may not be optimal [19]. On the other hand, this study considers all possible deviation paths in the network regardless of the location of vertices on detours and the station can be located anywhere along any detour edge. Thus, the proposed solution approach can improve any possible suboptimality produced by the existing models and generate the entire set of optimal points.To verify the performance of our proposed solution approach, a numerical example is used in Section7.3 to compare the solution obtained by our method with those from the Kim and Kuby [20] model and the Ventura et al. [18] algorithm. Table 2 provides a detailed comparison of these three methodologies. Note that these three methodologies have the same objective function, that is, maximizing the total traffic flow covered by the station, but different settings. Section 7.3 uses a numerical example to compare the quality of the solutions obtained by these three methods.Table 2
Comparison among three methodologies for solving an AF refueling station location problem.
Kim and Kuby [20]
Ventura et al. [18]
Proposed solution approach
Objective function
Maximizing the total traffic flow covered by the station
Maximizing the total traffic flow covered by the station
Maximizing the total traffic flow covered by the station
Set of candidate sites
(i) Predetermined(ii) Finite (vertices only)
(i) Transportation network(ii) Infinite (anywhere in the network)
(i) Transportation network(ii) Infinite (anywhere in the network)
Deviation
Yes
No
Yes
Deviation paths
Endpoints of deviation paths must be vertices
N/A
One endpoint of a deviation path must be a vertex and the other can be any point along the network
Main constraints
(i) Number of refueling stations(ii) Vehicle driving range(iii) Distance decay functions for traffic flow rate on deviation paths
(i) Setting up an initial refueling station(ii) Vehicle driving range(iii) Positive traffic flow rate for some short trips
(i) Setting up an initial refueling station(ii) Vehicle driving range(iii) Portion of drivers who select the deviation option
Global optimum
No
Yes
Yes
Computational complexity
NP-hard
Polynomial (On4)∗
Polynomial (On5)∗
n
∗ = number of vertices.The rest of this article is organized as follows. Section2 briefly reviews literature related to refueling station location problems. Section 3 includes the problem statement and derives a property related to the deviation option. Section 4 identifies a set of candidate points for potential locations of the refueling station. Section 5 determines optimal points from the set of candidate points for the refueling station that covers the maximum traffic flow when a portion of drivers select the deviation option. Section 6 builds the complete set of optimal solutions by identifying additional optimal points located in the interior of paths whose endpoints belong to the preliminary set of optimal points. Section 7 provides a numerical example to illustrate the proposed solution approach, examine the coupled effects of deviation portion and vehicle driving range on the set of optimal locations and the maximum traffic flow covered, and analyze its performance. Lastly, Section 8 presents a summary of this study and a list of topics for future research.


## 1.1. Tree Structure in Transportation Networks

While the US national highway system consists of a set of circuit networks, if it is partitioned into local highway systems by operating authority, then many of them form trees or tree-like networks. Table1 displays the local highway systems in the US along with their operating authorities that have tree or tree-like network structures. As shown in this table, 10 turnpikes and 8 portions of interstate highways within certain states constitute tree structures [3]. Furthermore, if we consolidate beltways and cycles within metro areas into single vertices, then 11 more portions of interstate highways within certain states can also be considered as tree-like structures [4, 5]. In addition, we can observe that toll roads and highways in other countries, such as Chile, Croatia (southern and northeast regions), Indonesia, Ireland (excluding the Dublin region), Malaysia, Norway (northern region), Philippines, Slovakia, Spain (excluding the Catalan region), and Serbia, to name a few, have tree or tree-like network structures. Note also that road networks in sparsely settled areas are generally trees, since tree road networks are the cheapest to construct.Table 1
Tree network structures in the US highways.
State
Roadtype∗
Type of network structure
Component highways
Operating authority
AL
I
Tree-like, including Birmingham beltway
I-20, I-22, I-59, I-65, I-85
AL Department of Transportation (DOT)
AK
S
Tree in Southcentral area
AK-1, AK-3
AK DOT and Public Facilities
AZ
I
Tree-like, including Phoenix beltway
I-8, I-10, I-15 I-17, I-19, I-40
AZ DOT
AR
I
Tree-like, including Little Rock beltway
I-30, I-40, I-49, I-55, I-530, I-555
AR Highway and Transportation Department
CO
I
Tree-like, including Denver beltway
I-25, I-70, I-76
CO DOT
GA
I
Tree-like, including beltways in Atlanta, Augusta, Columbus, and Macon
I-16, I-20, I-59, I-75, I-85, I-185, I-285, I-675, I-985
GA DOT
ID
I
Tree
I-15, I-84, I-86, I-90
ID Transportation Department
IN
T
Tree
I-80, I-90
IN Finance Authority/ ITR Concession Company LLC
KS
T
Tree
I-35, I-70, I-335, I-470
KS Turnpike Authority
ME
T
Tree
I-95
ME Turnpike Authority
MA
T
Tree
I-90
MA DOT
MN
I
Tree-like, including Minneapolis beltway
I-35, I-90, I-94
MN DOT
MS
I
Tree
I-20, I-22, I-55, I-59
MS DOT
MT
I
Tree
I-15, I-90, I-94
MT DOT
NE
I
Tree-like, including Omaha beltway
I-76, I-80
NE Department of Roads
NV
I
Tree-like, including Las Vegas beltway
I-15, I-80, I-515
NV DOT
NH
T
Tree
I-93, I-95, NH-3, NH-16
NH DOT
NM
I
Tree
I-10, I-25, I-40
NM DOT
NY
T
Tree
I-87, I-90
NY State Thruway Authority
ND
I
Tree
I-29, I-94
ND DOT
OH
T
Tree
I-76, I-80, I-90
OH Turnpike Commission
OK
T
Tree
I-35, I-40, I-44, US-66, US-165, US-177, US-412, OK-1, OK-51, OK-66, OK-165
OK Turnpike Authority
OR
I
Tree-like, including Portland beltway
I-5, I-84
OR DOT
PA
T
Tree
I-70, I-76, I-276, I-376, I-476, PA-43, PA-60, PA-66, PA-576
PA Turnpike Commission
SD
I
Tree
I-29, I-90
SD DOT
UT
I
Tree-like, including Salt Lake City beltway
I-15, I-70, I-80, I-84
UT DOT
VT
I
Tree
I-89, I-91, I-93
VT Agency of Transportation
WV
T
Tree
I-64, I-77
WV Parkways Authority
WY
I
Tree
I-25, I-80, I-90
WY DOT
I
∗: interstate highway, S: state highway, and T: turnpike.Trees are central to the structural understanding of networks and graphs and often occur with additional attributes such as roots and vertex-ordering. They have a wide range of applications, including data storage, searching, information processing, and facility location [6]. Because it is easier to get insights into tree network problems, numerous articles in classical facility location problems on transportation networks without cycles are available in the literature ([7–9] and others).


## 1.2. Setting Up an AF Refueling Station on Toll Roads

Building an AF refueling station usually requires a substantial investment. For example, it takes $1.8 million to $4.7 million to construct a natural gas refueling station on the Pennsylvania Turnpike without including the land value [10]. Due to the financial risk, it is unusual to build multiple AF refueling stations on the same road network simultaneously. Instead, an operating authority may be more inclined in setting up a single station first in a high traffic area and planning the gradual future construction of additional stations with the goal of maximizing the coverage of traffic flow. For example, the Pennsylvania Turnpike Commission opened the first refueling station at New Stanton Service Plaza in 2014 to serve compressed natural gas (CNG) vehicles and it currently remains as the only CNG station on the turnpike [11]. As a second example, the Oklahoma Turnpike Authority opened the first CNG station at Stroud Travel Plaza on the turnpike in 1991, which was renovated in 2014, and then 23 years later, the authority opened the second CNG station at McAlester Travel Plaza on the turnpike in 2014 [12–14]. Note that both of these turnpikes form tree networks.Several articles have been published regarding the classical single facility location problem on tree networks ([7, 15–17] and others). Three versions of the problem exist depending on the main objective: the objective of the 1-median problem is to minimize the total travel distance from the new facility to existing facilities; in the 1-center problem, the objective is to minimize the maximum travel distance; and the covering problem finds the location of a facility that can reach (cover) the maximum number of existing facilities within a given travel distance. Francis et al. ([5], Chapter 7) describe motivating applications of location problems on trees, as well as properties and solution algorithms for the three versions of the problem. None of the algorithms developed to solve classical single facility location problems on tree networks, however, is suitable for locating an AF refueling station on tree-like road networks because of the differences in the objective function. In the location of an AF station, the objective of maximizing the total traffic flow covered by the station is more desirable by operating authorities. Furthermore, locating an AF refueling station requires a different strategy to deal with demand. Note that the classical single facility location problem regards demand as a weight at vertices. Instead, drivers (demand) on toll roads and highways usually stop by the refueling station on the way to their final destination. Considering that this refueling activity for a driver is a unit of demand, a path-based demand model, in which the demand on the travel path can be covered by a facility located on the path, is more appropriate for solving the AF refueling station location problem.


## 1.3. Continuous Refueling Station Location Problem

We can classify refueling station location problems into two types depending on the set of candidate sites: when a preliminary (finite) set of candidate sites is given, this problem is calleddiscrete; when the station can be located anywhere along the network, the problem is calledcontinuous. Ventura et al. [18] introduced the continuous version of the refueling station location problem. Since an optimal solution to the discrete version of the problem is always a feasible solution to the continuous version, an optimal solution to the continuous refueling station location problem can achieve a considerable improvement in terms of demand coverage. The continuous version of the problem is, however, more challenging than its discrete counterpart due to the size of the search space.


## 1.4. Contribution

In this study, we consider the continuous version of an AF refueling station location problem on a tree network, where a portion of drivers have the option of selecting a deviation path if the refueling station is not located along their preplanned routes. We believe that this is the first research work on the continuous version of the problem where the deviation option is considered. This option is expected to be very common for drivers with AF vehicles during the introductory period of these vehicles to the market since AF refueling infrastructures are usually nonexistent or underdeveloped. The deviation option is also available to drivers of conventional fossil-fuel vehicles (powered by gasoline and diesel engines) when they cannot find a refueling station on their routes. Thus, considering deviation will make the problem more practical in deciding the potential location for the refueling station.Compared with the original continuous refueling station location problem [18], the theoretical contribution of this study is twofold. First, we derive a number of properties to identify the deviation options for each origin/destination (O/D) pair considering the length of the simple path, the minimum fuel tank levels at the origin and destination, and the vehicle driving range. Then, we develop a novel algorithm that finds all deviation paths for each O/D pair in polynomial time. Using the original path in the tree network and the corresponding deviation options, we construct the subtree that contains all the potential station locations that cover the traffic flow of the corresponding O/D pair. Second, we derive a mathematical property that characterizes the set of optimal station locations that do not require Ventura et al. [18] assumption that the intersection vertices in all used simple paths must have positive traffic flow in at least one short trip. This property is essential in the development of the algorithm that finds the complete set of optimal station locations for the entire network.By allowing vehicle deviation in the continuous refueling station location problem, the solution approach proposed in this article is capable of finding all possible alternative paths for any O/D pair and improving suboptimal solutions obtained by the existing models in the literature. To best of our knowledge, all the existing models that consider vehicle deviation solve discrete versions of the problem, and therefore, they choose locations from a predetermined set of candidate sites (vertices) and enable deviation only if such vertices can be reached within the vehicle driving range. Therefore, their solutions may not be optimal [19]. On the other hand, this study considers all possible deviation paths in the network regardless of the location of vertices on detours and the station can be located anywhere along any detour edge. Thus, the proposed solution approach can improve any possible suboptimality produced by the existing models and generate the entire set of optimal points.To verify the performance of our proposed solution approach, a numerical example is used in Section7.3 to compare the solution obtained by our method with those from the Kim and Kuby [20] model and the Ventura et al. [18] algorithm. Table 2 provides a detailed comparison of these three methodologies. Note that these three methodologies have the same objective function, that is, maximizing the total traffic flow covered by the station, but different settings. Section 7.3 uses a numerical example to compare the quality of the solutions obtained by these three methods.Table 2
Comparison among three methodologies for solving an AF refueling station location problem.
Kim and Kuby [20]
Ventura et al. [18]
Proposed solution approach
Objective function
Maximizing the total traffic flow covered by the station
Maximizing the total traffic flow covered by the station
Maximizing the total traffic flow covered by the station
Set of candidate sites
(i) Predetermined(ii) Finite (vertices only)
(i) Transportation network(ii) Infinite (anywhere in the network)
(i) Transportation network(ii) Infinite (anywhere in the network)
Deviation
Yes
No
Yes
Deviation paths
Endpoints of deviation paths must be vertices
N/A
One endpoint of a deviation path must be a vertex and the other can be any point along the network
Main constraints
(i) Number of refueling stations(ii) Vehicle driving range(iii) Distance decay functions for traffic flow rate on deviation paths
(i) Setting up an initial refueling station(ii) Vehicle driving range(iii) Positive traffic flow rate for some short trips
(i) Setting up an initial refueling station(ii) Vehicle driving range(iii) Portion of drivers who select the deviation option
Global optimum
No
Yes
Yes
Computational complexity
NP-hard
Polynomial (On4)∗
Polynomial (On5)∗
n
∗ = number of vertices.The rest of this article is organized as follows. Section2 briefly reviews literature related to refueling station location problems. Section 3 includes the problem statement and derives a property related to the deviation option. Section 4 identifies a set of candidate points for potential locations of the refueling station. Section 5 determines optimal points from the set of candidate points for the refueling station that covers the maximum traffic flow when a portion of drivers select the deviation option. Section 6 builds the complete set of optimal solutions by identifying additional optimal points located in the interior of paths whose endpoints belong to the preliminary set of optimal points. Section 7 provides a numerical example to illustrate the proposed solution approach, examine the coupled effects of deviation portion and vehicle driving range on the set of optimal locations and the maximum traffic flow covered, and analyze its performance. Lastly, Section 8 presents a summary of this study and a list of topics for future research.


## 2. Literature Review

While classical facility location problems regard demand as a weight at vertices representing number of customers that need to receive service at the new facilities or number of trips to these facilities, refueling station location problems require a different strategy to deal with demand. Drivers (demand) on toll roads and highways are able to refuel their vehicles if they pass by a refueling station on their preplanned paths. Considering that this refueling activity for a driver is a unit of demand, Hodgson [21] and Berman et al. [22] introduced the flow-capturing location model (FCLM) to find the facility locations with the objective of maximizing the traffic flow covered. Kuby and Lim [23] extended the FCLM and suggested the flow refueling location model (FRLM) that incorporates a driving range. Since the concept of this model is well suited for identifying optimal refueling station sites for AF vehicles, many subsequent studies have been published using the idea of the FRLM. In particular, Kim and Kuby [20] proposed the deviation-flow refueling location model (DFRLM), which is an extension of the FRLM considering driver deviation behavior when searching for potential sites for the refueling stations. Later, Kim and Kuby [24] suggested two heuristics to solve the DFRLM efficiently.Recently, refueling station location models have been extended to more general forms considering specific applications, including a multiperiod planning formulation for the allocation of electric charging stations over time [25]; a two-stage stochastic station location model, where the first stage locates permanent stations and the second locates portable stations [26]; a new model that considers multiple deviation paths between each of the O/D pairs when searching for station locations [27]; novel station location formulations for symmetric transportation networks that consider both single- and dual-access candidate sites [28, 29]; a biobjective model to estimate the greenhouse gases emissions reduction as a function of the refueling infrastructure budget [10]; and models that consider capacitated stations and traffic deviations over multiple time periods [30], and traffic deviation considering route choice and demand uncertainty [31], under the assumption that vehicles only require one refueling stop for intracity trips.While most refueling station location problems and extensions assume that the station can be located only either on the vertices of the network or within a finite set of candidate sites, Ventura et al. [18] considered the continuous version of the problem for a single station, where the station can be located anywhere along a tree-type transportation network, and developed a polynomial time algorithm to find the set of optimal location points.


## 3. Problem Statement

Now, we address the continuous deviation-flow location problem on a tree network. Considering that a portion of drivers are willing to deviate from their paths, the objective of this problem is to determine the set of locations for an AF refueling station that maximizes the total traffic flow covered (in round trips per time unit) by the station. To simplify but accurately formulate and solve the problem, we consider the following assumptions. First, an uncapacitated refueling station can provide service to all vehicles driving through both directions of the road segment where it is located. It assures that all vehicles passing through the refueling station in either direction of the road segment can be refueled at the station. Second, all vehicles have the same fuel tank size, and fuel consumption is a linear function of the driving distance. This means that all vehicles have the same driving range per refueling, denoted asR, regardless of road conditions, climate, congestion, or any other variables. Third, vehicles perform a complete round trip between their origin and destination points on the network. A complete round trip in this assumption ensures that every vehicle goes back to its origin after arriving at its intended destination. A trip from origin to destination is called an original trip, and a trip from destination to origin is called a return trip. A round trip consists of an original trip and a return trip. Fourth, each vehicle enters and exits the network with a fuel tank that is at least half-full. This assumption was first suggested by Kuby and Lim [23] and since then has been followed by most of the researchers on this type of problems, considering that information about the actual fuel tank level of vehicles at origins and destinations is difficult to obtain or likely to be inaccurately estimated. The purpose of this assumption is to make sure that the same round trip can be repeated many times without running out of fuel along the path. This assumption assures that if a vehicle can access the last refueling station on the original trip and reach the destination along the path with at least a half-full tank, then this vehicle can also make the return trip from the destination starting with a half-full tank and reaching the same refueling station without running out of fuel. Similarly, if a vehicle at the last station on the return trip can reach the origin along the path with at least a half-full tank, then this vehicle can also make the original trip from the origin with a half-full tank and safely arrive at the same station. Fifth, the deviation option from a simple path is available to all drivers for their refueling service. However, only a certain portion α of the drivers selects this option, where 0≤α≤1. This implies that α×100% of traffic flow deviates from their simple paths for refueling service. We call this flow the deviation-flow.LetTV,E be an undirected tree network consisting of a set V with n vertices and a set E with n-1 edges, where n≥2; otherwise, the network is trivial. An edge vi,vj∈E is defined if vi∈V and vj∈V are directly connected. We also denote Pvi,vj as the unique simple path between vi and vj for i<j, for all vi,vj∈V. Set L is defined as the set of all possible paths in T; that is, L=Pvi,vj∣i<j,forallvi,vj∈V. The average traffic flow along Pvi,vj is denoted as f(vi,vj). We note that f(vi,vj) refers to the average of traffic flow of the original trip from vi to vj and the return trip from vj to vi and is defined only for i<j. We use f(vi,vj) to represent the round trips per time unit between vi and vj. The length of Pvi,vj is denoted as dvi,vj, and dvi,vj=dvj,vi. Similarly, Pvi,x denotes the unique simple path between vi∈V and any point x∈T, and the length of this path is denoted as dvi,x=dx,vi.To address the continuous deviation-flow location problem, we distinguish between the traffic flow and the deviation-flow on a path. The traffic flow betweenvi and vj is “covered” by a refueling station if the station is located at some point x along Pvi,vj within a distance R/2 from vi and vj. Then, the set of paths with positive traffic flow covered by a point x∈T, denoted as Sx, is defined as follows:(1)Sx=Pvi,vj∣x∈Pvi,vj,fvi,vj>0,dvi,x≤R2,dx,vj≤R2,i<j,∀vi,vj∈V.Alternatively, the deviation-flow originating in path Pvi,vj is covered by the station if it is placed at a point x somewhere in the network within a distance R/2 from vi and vj, but not along path Pvi,vj. Then, the set of paths with positive deviation-flow covered by a point x∈T, denoted as SDx, is defined as follows:(2)SDx=Pvi,vj∣x∈T\Pvi,vj,α×fvi,vj>0,dvi,x≤R2,dx,vj≤R2,i<j,∀vi,vj∈V.Now, the total traffic flow (in round trips per time unit), including fvi,vj and α×fvi,vj, for all vi,vj∈V, covered by a refueling station at x∈T, denoted as F(x), is calculated as follows:(3)Fx=∑Pvi,vj∈Sxfvi,vj+∑Pvi,vj∈SDxα×fvi,vj.Thus, an optimal point x∗ that covers the maximum traffic flow (in round trips per time unit) in tree T can be obtained by comparing the values of Fx for all x∈T; that is, x∗∈arg⁡max⁡Fx∣x∈T.When a refueling station is not located in a simple path, vehicles traveling along this path can deviate to a separate subpath for their refueling service. In a deviation path, this separate subpath is called a symmetric cycle, because the subpath begins at a vertex in the simple path, reaches the station location, and returns to the same vertex using the same subpath in the opposite direction. This closed walk includes at least one repeating vertex. Since we consider a refueling station to be located on the tree network, vehicles can take a symmetric cycle originating at a vertex located on their simple path and the entire path is called a simple deviation path. That is, each simple deviation path consists of a simple path and a symmetric cycle.Figure1 shows an example of an undirected tree network to help understand the concept of simple deviation path, as well as sets Sx and SDx. The numerical value next to each edge of the network indicates the distance between the two vertices or between a vertex and a point. In this example, let us assume R=80 and α=0.20. If drivers make a round trip between v1 and v3 with fv1,v3=100, the simple path is Pv1,v3, the vertex visitation sequence between v1 and v3 is v1,v2,v3, and 100 round trips (per time unit) use that vertex visitation sequence. However, if a refueling station is located at point r in the middle of edge v4,v6, 20 round trips from fv1,v3 deviate to a symmetric cycle with vertex visitation sequence v2,v4,r,v4,v2. Thus, the entire vertex visitation sequence for the simple deviation path between v1 and v3 is v1,v2,v4,r,v4,v2,v3. If there exists another traffic flow fv4,v6=400, then Sr=Pv4,v6 and SDr=Pv1,v3. Thus, the total traffic flow covered by a refueling station located at r is calculated as Fr = ∑Pvi,vj∈Srfvi,vj + ∑Pvi,vj∈SDrα×fvi,vj=fv4,v6+0.20×fv1,v3 = 420 round trips (per time unit).Figure 1
Simple deviation path.If there exists an edge in the network whose length is greater thanR, no traffic flow going through the edge can be covered by a single refueling station due to the half-full tank assumption of vehicles at the origin and destination vertices in their round trips. Furthermore, no deviation-flow going through this edge can be covered by a station located in any symmetric cycle. Thus, we need to split the tree network into subtrees by removing all edges whose distance is greater than R and solve the station location problem in each subtree separately. Let E^=vi,vj∣dvi,vj>R,forvi,vj∈E. Then, we eliminate all edges in E^ from TV,E to form a forest FVF,EF with VF=V and EF=E\E^, such that FVF,EF=⋃q=1tTqVq,Eq, where Tq is the qth subtree that consists of a set of vertices Vq and a set of edges Eq, and t=E^+1 is the total number of subtrees Tq in forest FVF,EF.Now, for subtreeTq,q=1,…,t, if there exists a symmetric cycle originating at a vertex located on a simple path in Tq that can reach some segments in the removed edges in E^, the corresponding deviation-flow can be covered by a point located on one of the segments in these edges. In this case, we need to construct an expanded subtree T^q from Tq by adding these reachable edges into Tq. Thus, for each subtree Tq, we first need to identify all vertices in Vq that are endpoints of the edges in E^. Let vk be one of the vertices in Vq that is adjacent to vl∈V\Vq by vk,vl∈E^. Then, the set of vertices vk in Vq is defined as Vq′=VE^∩Vq, where VE^ is the set of vertices in E^. After identifying Vq′, the set of edges in E^ that are connected to vk in Vq′ is defined as Evk=vk,vl∈E^∣vl∈V\Vq. In addition, the set of vertices vl∈V\Vq that are adjacent to vk in Vq′ is defined as Vvk=VEvk\vk, where VEvk is the set of vertices in Evk. For vk∈Vq′, if any positive deviation-flow α×fvi,vj from path Pvi,vj in Tq can be covered by some point x located on one of the edges in Evk, then we add the edge in Evk into Eq and the corresponding end point (vertex) in Vvk into Vq. That is, for subtree TqVq,Eq, q=1,…,t, we first initialize set V-q as an empty set, where V-q is used to collect all vk∈Vq′ such that α×fvi,vj,vi,vj∈Vq, can be covered by some point x located on one of the edges in Evk. Next, for vk∈Vq′, if we find at least one α×fvi,vj>0, for Pvi,vj∈L in Tq, such that max⁡dvi,vk,dvj,vk<R/2, then we add vk into V-q. Finally, we construct expanded subtree T^qV^q,E^q, such that V^q=Vq∪⋃vk∈V-qVvk and E^q=Eq∪⋃vk∈V-qEvk. Based on the expanded subtree T^q constructed above for each subtree Tq, we can derive the following property.Property 1 (expanded subtree property).
Letx∗ denote an optimal point to the continuous deviation-flow location problem for an AF refueling station on T. Regarding the number of expanded subtrees from T and the location of x∗ as well as the value of Fx∗, we consider the following two cases:(a)
Iffvi,vj=0, for all Pvi,vj∈L such that dvi,vj≤R, then the number of expanded subtrees t≤n,  x∗ can be located anywhere in T, and Fx∗=0.(b)
Otherwise, the number of expanded subtreest<n, and x∗ has to be placed on an expanded subtree T^q that contains some path Pvi,vj∈L such that fvi,vj>0 and dvi,vj≤R. In this case, Fx∗>0.Proof.
In case (a), ifdvi,vj>R, for all vi,vj∈E, then E^=E. This implies that n expanded subtrees T^q are created, where each T^q is composed of an isolated vertex. Otherwise, at least an edge vi,vj∈E such that dvi,vj≤R exists. Thus, there exists an expanded subtree T^q that contains edge vi,vj∈E^q. This implies that T^q includes at least two vertices; that is, vi,vj∈V^q; thus, the number of expanded subtrees t<n. Besides, since fvi,vj=0, for all Pvi,vj∈L such that dvi,vj≤R, Sx=SDx=∅, and Fx=0, for all x∈T. Thus, for any point x∈T, Fx=0, which means that x∗ can be located anywhere in T and Fx∗=0.
In case (b), there exists at least one pathPvi,vj∈L, such that fvi,vj>0 and dvi,vj≤R. Thus, there exists an expanded subtree T^q that contains Pvi,vj and at least two vertices vi,vj∈V^q. This means that the number of expanded subtrees t<n. If the refueling station is located at a point x at an isolated vertex in T^q, then Sx=SDx=∅, and Fx=0. If the station is located at a point x along a symmetric cycle of Pvi,vj, then Pvi,vj∈SDx; that is, SDx≠∅, and Fx≥α×fvi,vj≥0. If the station is in the middle point x of Pvi,vj, then Pvi,vj∈Sx, which indicates that Sx≠∅, and therefore, Fx≥fvi,vj>0. Since x∗ is an optimal point, Fx∗≥Fx≥fvi,vj≥α×fvi,vj≥0. Hence, x∗ has to be placed on an expanded subtree T^q that contains a path Pvi,vj∈L such that fvi,vj>0 and dvi,vj≤R. Then, Fx∗>0.Note that, for any expanded subtreeT^qV^q,E^q,q=1,…,t, a path Pvi,vj∈T^q such that dvi,vj>R cannot be covered by a single station; in addition, a path Pvi,vj∈T^q without flow, that is, fvi,vj=0, does not need to be considered to maximize traffic flow coverage. Thus, the set of paths that need to be considered for coverage in T^q is defined as L^q=Pvi,vj∈T^q∣dvi,vj≤R,f(vi,vj)>0,andi<j,forallvi,vj∈V^q. Then, by definition of Sx, for x∈T^q, x covers any path Pvi,vj, for vi,vj∈V^q, such that dvi,vj≤R and fvi,vj>0. Thus, Sx⊆L^q. Similarly, by definition of SDx, for x∈T^q\Pvi,vj, x covers every path Pvi,vj, for vi,vj∈V^q, such that dvi,vj≤R and α×fvi,vj>0. Therefore, SDx⊆L^q as well.


## 4. Set of Candidate Points

In this section, we establish a set of candidate points for each expanded subtreeT^q to locate an AF refueling station on a tree network when a portion of drivers are willing to deviate to be able to refuel their vehicles. Then, we prove that this set includes at least one optimal location for the continuous deviation-flow location problem for an AF refueling station. In addition, if multiple optimal locations exist, these candidate points can be used to generate the entire set of optimal locations.The rest of this section is organized as follows. For pathPvi,vj∈L^q, q=1,…,t, Section 4.1 defines a segment that includes all potential locations for an AF refueling station to cover the traffic flow in the path. Based on each segment identified in Section 4.1, Section 4.2 searches for points where a symmetric cycle can start. Given any point found in Section 4.2, Section 4.3 introduces an algorithm that identifies the farthest point for each symmetric cycle. By integrating the theoretical background regarding the deviation option suggested in Sections 4.1 to 4.3, Section 4.4 determines the set of candidate points when α×100% of drivers select the deviation option. Lastly, Section 4.5 proves that this set contains at least one optimal location.


### 4.1. Refueling Segment

In order to obtain the set of candidate points, the first step we need to do is to identify the segment for each simple pathPvi,vj∈L^q that contains all station locations that cover the round trips in the path when the deviation option is not considered. This segment is called the refueling segment of path Pvi,vj and is denoted as RSvi,vj. Since vehicles have a driving range R, based on Assumption (ii), drivers have to refuel the vehicles within a distance of R/2 from the origin and destination vertices during their round trips by Assumption (iv). Thus, RSvi,vj must contain all the points that are within R/2 from vi and vj. That is,(4)RSvi,vj=x∈Pvi,vj∣dvi,x≤R2,dx,vj≤R2.Depending on the value of dvi,vj, RSvi,vj includes one or two endpoints, denoted as wi,jk, for k=1,2. If dvi,vj<R, RSvi,vj has two different endpoints, wi,j1 and wi,j2; otherwise, wi,j1=wi,j2. Then, the set of endpoints of RSvi,vj, denoted as EPvi,vj, is defined as follows:(5)EPvi,vj=wi,jk∣wi,jk,fork=1,2,are  endpoints  of  RSvi,vj.In the example of the round trip betweenv1 and v3 in Figure 1, RSv1,v3 is identical to Pv1,v3 since dv1,v3<R/2. Thus, the two endpoints of RSv1,v3, w1,31 and w1,32, are located exactly at v1 and v3; that is, EPv1,v3=v1,v3. Since RSv1,v3=Pv1,v3, a station located at any point x∈Pv1,v3 can cover round trips between v1 and v3.


### 4.2. Cycle Starting Vertex

As a next step to build the set of candidate points forT^q, q=1,…,t, considering the deviation option, in this subsection, we determine a vertex at which a symmetric cycle begins its deviation from a simple path. This vertex is called a cycle starting vertex and denoted as vs. A cycle starting vertex is the only common point (vertex) between the simple path and the symmetric cycle.In order to identify a cycle starting vertex of a pathPvi,vj, we examine the minimum remaining travel distance of vehicles at a vertex within Pvi,vj, as well as the degree of this vertex. First, the minimum remaining travel distance of vehicles at a cycle starting vertex vs is denoted as δvi,vj;vs and computed as follows:(6)δvi,vj;vs=R2-max⁡dvi,vs,dvj,vs.Intuitively, δvi,vj;vs measures the minimum remaining travel distance at vs that vehicles can drive up when they enter the network either at vi in the original trip or at vj in the return trip. δvi,vj;vs is calculated by subtracting the maximum distance between dvi,vs and dvj,vs from R/2 because any point within a symmetric cycle must be reachable from both vi and vj in order for vehicles to make a complete round trip between vi and vj in the network. In order for vehicles in path Pvi,vj∈L^q to start a symmetric cycle originating at vs, the value of δvi,vj;vs must be positive; otherwise, the deviation option is not available at vs. The value of δvi,vj;vs depends on the location of vs and the value of dvi,vj. In case of vs∈Pvi,vj\RSvi,vj, δvi,vj;vs<0, for any value of dvi,vj; thus, no deviation is available. In case of vs∈RSvi,vj, if R/2≤dvi,vj≤R, then δvi,vj;vs>0 for vs in the interior of RSvi,vj, and δvi,vj;vs=0 for vs at the endpoint of RSvi,vj. If dvi,vj<R/2, then δvi,vj;vs>0 for vs∈VRSvi,vj, where VRSvi,vj is the set of vertices in RSvi,vj.Next, the degree of a cycle starting vertexvs is denoted as deg⁡vs. If vs of a path Pvi,vj is placed at either origin vi or destination vj, that is, vs∈vi,vj, then vs can be a cycle starting vertex if and only if deg⁡vs≥2. This implies that vs has at least one adjacent edge that does not belong to path Pvi,vj and a portion of this edge or the entire edge can form a subpath for a symmetric cycle. If vs is placed at neither origin vi nor destination vj, that is, vs∉vi,vj, then vs can only be a cycle starting vertex if deg⁡vs≥3. That is, besides the two subpaths from vs to vj in the original trip and from vs to vi in the return trip, at least one more separate subpath connected to vs exists to initiate a symmetric cycle.Since there can exist multiple cycle starting vertices for a pathPvi,vj∈L^q, we define CSVvi,vj as the set of cycle starting vertices in path Pvi,vj. Based on the observations of a cycle starting vertex discussed above, CSVvi,vj is determined as follows:(7)CSVvi,vj=vs∈VRSvi,vj∣δvi,vj;vs>0;deg⁡vs≥2ifvs∈vi,vj,ordeg⁡vs≥3ifvs∉vi,vj.Now, let us recall thatRSv1,v3=Pv1,v3 in the example of the round trip between v1 and v3 in Figure 1. Thus, VRSv1,v3=v1,v2,v3, and by using Expression (6), δv1,v3;v1=2, δv1,v3;v2=20, and δv1,v3;v3=2. However, v1 and v3 cannot be cycle starting vertices of Pv1,v3 because deg⁡v1=deg⁡v3=1. In contrast, v2 is a cycle starting vertex of Pv1,v3 because deg⁡v2=3. Thus, CSVv1,v3=v2.


### 4.3. Cycle Returning Point

In this subsection, for each symmetric cycle originating atvs∈CSVvi,vj, we identify the farthest point vehicles can reach before returning to vs. This point is called a cycle returning point and denoted as r. Given that the purpose of deviation from a simple path is to refuel vehicles, the cycle returning point is regarded as the farthest feasible site for the refueling station; that is, drivers that are willing to deviate can travel up to the cycle returning point, refuel their vehicles at the refueling station, return to their simple path, and continue to their destination.The cycle returning point has distinct characteristics compared to the cycle starting vertex. First, the cycle returning point is defined for0<α≤1, while the cycle starting vertex is defined for 0≤α≤1. Next, the cycle returning point belongs to the symmetric cycle but does not belong to the simple path, while the cycle starting vertex is the only common point between the simple path and the symmetric cycle. In addition, the cycle returning point can be a vertex or any point on an edge, whereas the cycle starting vertex is always a vertex literally.Multiple symmetric cycles can begin at the same cycle starting vertex according to the network structure. This implies that one cycle starting vertex may lead to multiple cycle returning points. LetCRPvi,vj;vs be the set of all cycle returning points r arising from a given vs∈CSVvi,vj. Then, CRPvi,vj;vs is the number of cycle returning points corresponding to a given vs∈CSVvi,vj, or equivalently, the number of symmetric cycles originating at a given vs∈CSVvi,vj. In addition, the number of all cycle returning points of path Pvi,vj can be computed as ∑vs∈CSVvi,vjCRPvi,vj;vs.The location of a cycle returning pointr∈CRPvi,vj;vs is determined by comparing the value of δvi,vj;vs to the length of the separate subpath originating at vs. If the value of δvi,vj;vs is less than the length of the separate subpath, then the cycle returning point r is located at a distance δvi,vj;vs from vs since drivers at cycle starting vertex vs can travel up to this distance from vs before refueling their vehicles; otherwise, the cycle returning point r is located at the leaf (end vertex) of the separate subpath because that vertex is the farthest point from vs in the symmetric cycle originating at vs.From the observation above regarding the location of a cycle returning point, we propose a novel algorithm, called the Cycle Returning Point Algorithm, to identify the locations of all cycle returning pointsr∈CRPvi,vj;vs for a given cycle starting vertex vs∈CSVvi,vj. This algorithm systematically explores the edges along separate subpaths originating at vs and computes the minimum remaining travel distance at each reachable vertex.When exploring an edgevu,vr along a separate subpath such that dvi,vu<dvi,vr or dvj,vu<dvj,vr, we call vu the parent of vr and vr the child of vu. To establish a parent and child relationship between vertices in the course of scanning the edges, we let PARENTvr be the set of parents of vr and CHILDRENvu the set of children of vu. In a tree network, every child vr has a single parent vu, that is, PARENTvr=vu. In contrast, every parent vu can have several children vr according to the tree network structure. Thus, set CHILDRENvu is determined as follows:(8)CHILDRENvu=Nvu\VPvi,vj,ifvu=vs,Nvu\PARENTvu,otherwise,where Nvu is the set of vertices adjacent to vu, or equivalently, the neighborhood of vu, and VPvi,vj is the set of vertices within Pvi,vj. In Expression (8), if vu=vs, CHILDRENvu is obtained by removing the vertices within Pvi,vj from the vertices adjacent to vu; otherwise, CHILDRENvu is generated by eliminating the parent of vu from the vertices adjacent to vu.The algorithm iterates to explore each edgevu,vr along separate subpaths originating at a given vertex vs∈CSVvi,vj until all cycle returning points r∈CRPvi,vj;vs are identified. At a particular iteration exploring an edge vu,vr, the minimum remaining travel distance of vehicles at vu, denoted as δvi,vj;vu, is known. That is, if vu=vs, the value of δvi,vj;vu is given by Expression (6); otherwise, this value is given from the previous iteration. Then, we can compute the minimum remaining travel distance of vehicles at vr as δvi,vj;vr=δvi,vj;vu-dvu,vr. If δvi,vj;vr<0, a cycle returning point r is located along edge vu,vr such that dvu,r=δvi,vj;vu. If δvi,vj;vr=0 or if δvi,vj;vr>0 and deg⁡vr=1, then r is placed exactly at vr. If δvi,vj;vr>0 and deg⁡vr≥2, then the drivers that are willing to deviate can travel further along the separate subpath; in this case, the algorithm assigns a child vr of the current iteration to a new parent vu at the next iteration and determines a new child vr using Expression (8) to proceed the next iteration.In order to keep track of a childvr from a prior iteration that may become a parent in a subsequent iteration on the search for cycle returning points, this algorithm uses a (infinite) first-in, first-out queue Q consisting of vr such that δvi,vj;vr>0 and deg⁡vr≥2. Two functions are used to manage Q. The first function named enqueue(Q;vr) places vr at the tail of queue Q. Conversely, the second function named dequeue(Q) selects the vertex at the head of queue Q and eliminates it from Q. The details of the Cycle Returning Point Algorithm are provided below.Algorithm 2 (Cycle Returning Point Algorithm).
Step  1. For a given vs∈CSVvi,vj, initialize CRPvi,vj;vs=∅. If α=0, terminate the algorithm; otherwise, compute δvi,vj;vs using Expression (6).
Step  2. Initialize Q=∅.
Step  3. Enqueue(Q;vs).
Step  4. Repeat the following substeps as long as there remain vertices in Q:
Sub-Step  4.1. vu=dequeue(Q).
Sub-Step  4.2. Determine CHILDRENvu using Expression (8).
Sub-Step  4.3. For each vr∈CHILDRENvu, perform the following steps:
Sub-Step  4.3.1. Compute δvi,vj;vr=δvi,vj;vu-dvu,vr.
Sub-Step  4.3.2. According to the sign of δvi,vj;vr, perform one of the following procedures:(a)
Ifδvi,vj;vr<0: r is located along edge vu,vr, such that dvu,r=δvi,vj;vu. Also, add r into CRPvi,vj;vs.(b)
Ifδvi,vj;vr=0 or if δvi,vj;vr>0 and deg⁡vr=1: r is located exactly at vr. Also, add r into CRPvi,vj;vs.(c)
Ifδvi,vj;vr>0 and deg⁡vr≥2: enqueue(Q;vr) and set PARENTvr=vu.Theorem 3 (complexity of the Cycle Returning Point Algorithm).
The complexity of the Cycle Returning Point Algorithm isOn, where n=V.Proof.
Step1 includes initialization of CRPvi,vj;vs, checking the value of α, and computation of δvi,vj;vs, which takes O1. Initialization of Q in Step 2 and enqueuing vs to Q in Step 3 also take O1. Step 4 consists of three substeps to identify all r∈CRPvi,vj;vs for a given vs∈CSVvi,vj. Sub-Steps  4.1 and 4.2 dequeue vu from Q and generate set CHILDRENvu. Sub-Step  4.3 computes δvi,vj;vr for vr∈CHILDRENvu, and then according to the sign of δvi,vj;vr, it locates a cycle returning point within edge vu,vr or enqueues vr to Q for the next iteration. Step 4 iterates until queue Q is empty. Since every vertex can be enqueued and dequeued at most once for a given vs∈CSVvi,vj, the operations in Step 4 can be applied to every vertex at most once; thus, the total time devoted to the operations in Step 4 is On. Therefore, the computational complexity of the Cycle Returning Point Algorithm is On.Now, we apply the Cycle Returning Point Algorithm to the example in Figure1 to determine all cycle returning points of Pv1,v3; that is, we need to identify CRPv1,v3;vs, for all vs∈CSVv1,v3. Recall that R=80, α=0.20, and vs∈CSVv1,v3=v2. In Step 1 of the algorithm, for a given cycle starting vertex v2, we set CRPv1,v3;v2=∅ and, by Expression (6), compute δv1,v3;v2=40-max⁡dv1,v2,dv3,v2=20. In Step 2, we set Q=∅. In Step 3, we place v2 at the tail of queue Q; that is, Q={v2}. Now, we repeat Step 4 until finding all cycle returning points r∈CRPv1,v3;v2. In Sub-Step  4.1, we set vu=v2 and eliminate v2 from Q. In Sub-Step  4.2, since vu=v2=vs, by Expression (8), CHILDRENv2=Nv2\VPv1,v3=v1,v3,v4\v1,v2,v3=v4. For vr=v4, we perform Sub-Step  4.3. In Sub-Step  4.3.1, δv1,v3;v4=δv1,v3;v2-dv2,v4=5. Since δv1,v3;v4>0 and deg⁡v4=3, we select Procedure (c) in Sub-Step  4.3.2; that is, Q={v4} and PARENTv4=v2. Since Q≠∅, we repeat Step  4. Now, in Sub-Step  4.1, vu=v4 and v4 is removed from Q. In Sub-Step  4.2, by Expression (8), CHILDRENv4=Nv4\PARENTv4=v2,v5,v6\v2=v5,v6. For vr∈v5,v6, we implement Sub-Step  4.3. For vr=v5, in Sub-Step  4.3.1, δv1,v3;v5=δv1,v3;v4-dv4,v5=-5. As δv1,v3;v5<0, we select Procedure (a) in Sub-Step  4.3.2; that is, we locate r1 along edge v4,v5, such that dv4,r1=δv1,v3;v4=5, and add r1 to CRPv1,v3;v2, where r1 indicates the first cycle returning point r∈CRPv1,v3;v2. By repeating the same process for vr=v6, we locate r2 along edge v4,v6, such that dv4,r2=5, and add r2 to CRPv1,v3;v2, where r2 refers to the second r∈CRPv1,v3;v2. Now, Q=∅, so we end the algorithm with CRPv1,v3;v2={r1,r2}.


### 4.4. Refueling Subtree

In this subsection, we determine the refueling subtree for each pathPvi,vj∈L^q that includes all possible locations for an AF refueling station when a portion of drivers select the deviation option. Then, we identify candidate points in this subtree.First, let us define symmetric cycleSCvi,vj;vs,r as the segment consisting of all station locations that cover the deviation-flow of path Pvi,vj originating at cycle starting vertex vs∈CSVvi,vj and ending at cycle returning point r∈CRPvi,vj;vs; that is, SCvi,vj;vs,r=Pvs,r. Note that any point x in SCvi,vj;vs,r\{vs} covers deviation-flow α×fvi,vj, while cycle starting vertex vs covers traffic flow fvi,vj since vs∈SCvi,vj;vs,r∩RSvi,vj.Now, for any pathPvi,vj∈L^q, we can construct the refueling subtree, denoted as RSTvi,vj, which consists of refueling segment RSvi,vj and all symmetric cycles SCvi,vj;vs,r of Pvi,vj. This refueling subtree contains all potential locations for an AF refueling station when a portion of drivers are willing to deviate from the preplanned route Pvi,vj to be able to refuel their vehicles. That is,(9)RSTvi,vj=⋃vs∈CSVvi,vj⋃r∈CRPvi,vj;vsSCvi,vj;vs,r∪RSvi,vj.In RSTvi,vj, the cardinality of RSvi,vj is one, but the cardinality of SCvi,vj;vs,r is ∑vs∈CSVvi,vjCRPvi,vj;vs, because the number of symmetric cycles in RSTvi,vj is equal to the number of cycle returning points r∈CRPvi,vj;vs, for vs∈CSVvi,vj.The amount of traffic flow inPvi,vj covered by x∈RSTvi,vj depends on the value of α. If α=1, any point x in RSTvi,vj covers fvi,vj. If 0<α<1, any point x in RSTvi,vj\RSvi,vj covers α×fvi,vj, while any point x in RSvi,vj covers fvi,vj. If α=0, then CRPvi,vj;vs=∅ by the Cycle Returning Point Algorithm; thus, RSTvi,vj=RSvi,vj, and any point x in RSTvi,vj covers fvi,vj.The endpoints ofRSvi,vj indicate the boundary points defining the segment containing all station locations that can cover the positive traffic flow in path Pvi,vj. Similarly, the endpoints of SCvi,vj;vs,r, which are vs and r, represent the boundary points for the segment encompassing all station locations that can cover the positive deviation-flow in path Pvi,vj originating at cycle starting vertex vs∈CSVvi,vj and ending at cycle returning point r∈CRPvi,vj;vs. In RSTvi,vj, the endpoints of RSvi,vj and all the endpoints of SCvi,vj;vs,r are called the candidate points because these points indicate the boundaries for potential station locations that cover path Pvi,vj with positive traffic flow or deviation-flow. The set of candidate points of RSTvi,vj, denoted as CPRSTvi,vj, is defined as follows:(10)CPRSTvi,vj=⋃vs∈CSVvi,vjCRPvi,vj;vs∪CSVvi,vj∪EPvi,vj,where CSVvi,vj∪⋃vs∈CSVvi,vjCRPvi,vj;vs is the set of endpoints of all symmetric cycles and EPvi,vj is the set of endpoints of the refueling segment of Pvi,vj. The kth candidate point of RSTvi,vj is denoted as ci,jk, k=1,…, ∑vs∈CSVvi,vjCRPvi,vj;vs+CSVvi,vj+EPvi,vj.In Expression (10), note that CRPvi,vj;vs=∅ when there is no deviation option α=0, while CSVvi,vj and EPvi,vj are defined for 0≤α≤1. Note that the vertices in CSVvi,vj still need to be considered although the deviation option is not available, that is, for α=0, because some of these points are intersection vertices that may cover traffic flows from multiple paths [32]. Since an intersection vertex within a refueling segment has the same characteristics of a cycle starting vertex, we construct set CSVvi,vj for α=0 to identify this type of intersection vertices even though the deviation option is not available.By using Expression (10), the set of candidate points in expanded subtree T^q,q=1,…,t, denoted as CPq, can be defined as follows:(11)CPq=⋃Pvi,vj∈L^qCPRSTvi,vj.Now, we determine the refueling subtree for pathPv1,v3 in Figure 1. Recall that CSVv1,v3 = v2 and CRPv1,v3;v2 = r1,r2. Then, symmetric cycles of Pv1,v3 are SCv1,v3;v2,r1 and SCv1,v3;v2,r2. Thus, RSTv1,v3=SCv1,v3;v2,r1∪SCv1,v3;v2,r2∪RSv1,v3. If we assume L^q=Pv1,v3, since α=0.20, then any point x∈RSTv1,v3\RSv1,v3 covers 20% of fv1,v3, and any point x∈RSv1,v3 covers fv1,v3. In addition, by Expression (11), CPq=CRPv1,v3;v2∪CSVv1,v3∪EPv1,v3=r1,r2∪v2∪v1,v3.


### 4.5. Candidate Point Optimality Theorem

In this subsection, we prove that the set of candidate points,CP=⋃q=1tCPq, contains at least one optimal location to the problem.Lemma 4.
Consider a pointx∈T^q,  for some q=1,…,t, such that x∉CPq. Then,(a)
ifx∉⋃P(vi,vj)∈L^qRSTvi,vj, then Sx=SDx=∅ and Fx=0;(b)
ifx∈⋃P(vi,vj)∈L^qRSTvi,vj, then there exists a candidate point c∈CPq such that Sx⊆Sc, SDx⊆SDc∪Sc, and Fx≤Fc.Proof.
In case (a), by definition of refueling subtree,x does not cover any path in L^q. Thus, the result holds. In case (b), x is in the interior of all the refueling subtrees determined by all paths in Sx and SDx. Thus, x has at least one candidate point on each side. Let c1 and c2 be the two closest candidate points on each side of x. Because no candidate point is located between x and ci,i=1,2, the paths with positive traffic flow covered by x are the same paths with positive traffic flow covered by both c1 and c2; that is, Sx=Sc1∩Sc2, and thus, Sx⊆Sci,i = 1, 2. On the other hand, any path with positive deviation-flow covered by x must either be a path with positive deviation-flow covered by both c1 and c2 or be a path with positive traffic flow covered by one of the two candidate points (c1 and c2) and with positive deviation-flow covered by the other candidate point; that is, SDx = SDc1∩SDc2∪Sc1∩SDc2∪SDc1∩Sc2. This implies SDx⊆SDci∪Sci,i=1,2. Thus, for 0≤α≤1, ∑Pvi,vj∈Sxfvi,vj+∑Pvi,vj∈SDxα×fvi,vj≤∑P(vi,vj)∈S(ci)fvi,vj+∑P(vi,vj)∈SD(ci)α×fvi,vj, or equivalently, Fx≤Fci,i=1,2.Theorem 5 (Candidate Point Optimality Theorem).
For the continuous deviation-flow location problem for an AF refueling station on treeT, there exists at least one optimal location x∗∈CP.Proof (by contradiction).
Suppose that none of the candidate points in CP is an optimal solution. Letx∗ be an optimal point that covers Fx∗ round trips per time unit. Since x∗ is an optimal location, by case (a) of Lemma 4, x∗ must belong to ⋃P(vi,vj)∈L^qRSTvi,vj, for some q=1,…,t. If x∗∈⋃P(vi,vj)∈L^qRSTvi,vj, then by case (b) of Lemma 4, there exists a candidate point c∈CPq such that Fx∗≤Fc. This contradicts the initial hypothesis that none of the candidate points in CP is an optimal solution. Thus, there exists at least one candidate point in CP that is an optimal location to the problem.


## 4.1. Refueling Segment

In order to obtain the set of candidate points, the first step we need to do is to identify the segment for each simple pathPvi,vj∈L^q that contains all station locations that cover the round trips in the path when the deviation option is not considered. This segment is called the refueling segment of path Pvi,vj and is denoted as RSvi,vj. Since vehicles have a driving range R, based on Assumption (ii), drivers have to refuel the vehicles within a distance of R/2 from the origin and destination vertices during their round trips by Assumption (iv). Thus, RSvi,vj must contain all the points that are within R/2 from vi and vj. That is,(4)RSvi,vj=x∈Pvi,vj∣dvi,x≤R2,dx,vj≤R2.Depending on the value of dvi,vj, RSvi,vj includes one or two endpoints, denoted as wi,jk, for k=1,2. If dvi,vj<R, RSvi,vj has two different endpoints, wi,j1 and wi,j2; otherwise, wi,j1=wi,j2. Then, the set of endpoints of RSvi,vj, denoted as EPvi,vj, is defined as follows:(5)EPvi,vj=wi,jk∣wi,jk,fork=1,2,are  endpoints  of  RSvi,vj.In the example of the round trip betweenv1 and v3 in Figure 1, RSv1,v3 is identical to Pv1,v3 since dv1,v3<R/2. Thus, the two endpoints of RSv1,v3, w1,31 and w1,32, are located exactly at v1 and v3; that is, EPv1,v3=v1,v3. Since RSv1,v3=Pv1,v3, a station located at any point x∈Pv1,v3 can cover round trips between v1 and v3.


## 4.2. Cycle Starting Vertex

As a next step to build the set of candidate points forT^q, q=1,…,t, considering the deviation option, in this subsection, we determine a vertex at which a symmetric cycle begins its deviation from a simple path. This vertex is called a cycle starting vertex and denoted as vs. A cycle starting vertex is the only common point (vertex) between the simple path and the symmetric cycle.In order to identify a cycle starting vertex of a pathPvi,vj, we examine the minimum remaining travel distance of vehicles at a vertex within Pvi,vj, as well as the degree of this vertex. First, the minimum remaining travel distance of vehicles at a cycle starting vertex vs is denoted as δvi,vj;vs and computed as follows:(6)δvi,vj;vs=R2-max⁡dvi,vs,dvj,vs.Intuitively, δvi,vj;vs measures the minimum remaining travel distance at vs that vehicles can drive up when they enter the network either at vi in the original trip or at vj in the return trip. δvi,vj;vs is calculated by subtracting the maximum distance between dvi,vs and dvj,vs from R/2 because any point within a symmetric cycle must be reachable from both vi and vj in order for vehicles to make a complete round trip between vi and vj in the network. In order for vehicles in path Pvi,vj∈L^q to start a symmetric cycle originating at vs, the value of δvi,vj;vs must be positive; otherwise, the deviation option is not available at vs. The value of δvi,vj;vs depends on the location of vs and the value of dvi,vj. In case of vs∈Pvi,vj\RSvi,vj, δvi,vj;vs<0, for any value of dvi,vj; thus, no deviation is available. In case of vs∈RSvi,vj, if R/2≤dvi,vj≤R, then δvi,vj;vs>0 for vs in the interior of RSvi,vj, and δvi,vj;vs=0 for vs at the endpoint of RSvi,vj. If dvi,vj<R/2, then δvi,vj;vs>0 for vs∈VRSvi,vj, where VRSvi,vj is the set of vertices in RSvi,vj.Next, the degree of a cycle starting vertexvs is denoted as deg⁡vs. If vs of a path Pvi,vj is placed at either origin vi or destination vj, that is, vs∈vi,vj, then vs can be a cycle starting vertex if and only if deg⁡vs≥2. This implies that vs has at least one adjacent edge that does not belong to path Pvi,vj and a portion of this edge or the entire edge can form a subpath for a symmetric cycle. If vs is placed at neither origin vi nor destination vj, that is, vs∉vi,vj, then vs can only be a cycle starting vertex if deg⁡vs≥3. That is, besides the two subpaths from vs to vj in the original trip and from vs to vi in the return trip, at least one more separate subpath connected to vs exists to initiate a symmetric cycle.Since there can exist multiple cycle starting vertices for a pathPvi,vj∈L^q, we define CSVvi,vj as the set of cycle starting vertices in path Pvi,vj. Based on the observations of a cycle starting vertex discussed above, CSVvi,vj is determined as follows:(7)CSVvi,vj=vs∈VRSvi,vj∣δvi,vj;vs>0;deg⁡vs≥2ifvs∈vi,vj,ordeg⁡vs≥3ifvs∉vi,vj.Now, let us recall thatRSv1,v3=Pv1,v3 in the example of the round trip between v1 and v3 in Figure 1. Thus, VRSv1,v3=v1,v2,v3, and by using Expression (6), δv1,v3;v1=2, δv1,v3;v2=20, and δv1,v3;v3=2. However, v1 and v3 cannot be cycle starting vertices of Pv1,v3 because deg⁡v1=deg⁡v3=1. In contrast, v2 is a cycle starting vertex of Pv1,v3 because deg⁡v2=3. Thus, CSVv1,v3=v2.


## 4.3. Cycle Returning Point

In this subsection, for each symmetric cycle originating atvs∈CSVvi,vj, we identify the farthest point vehicles can reach before returning to vs. This point is called a cycle returning point and denoted as r. Given that the purpose of deviation from a simple path is to refuel vehicles, the cycle returning point is regarded as the farthest feasible site for the refueling station; that is, drivers that are willing to deviate can travel up to the cycle returning point, refuel their vehicles at the refueling station, return to their simple path, and continue to their destination.The cycle returning point has distinct characteristics compared to the cycle starting vertex. First, the cycle returning point is defined for0<α≤1, while the cycle starting vertex is defined for 0≤α≤1. Next, the cycle returning point belongs to the symmetric cycle but does not belong to the simple path, while the cycle starting vertex is the only common point between the simple path and the symmetric cycle. In addition, the cycle returning point can be a vertex or any point on an edge, whereas the cycle starting vertex is always a vertex literally.Multiple symmetric cycles can begin at the same cycle starting vertex according to the network structure. This implies that one cycle starting vertex may lead to multiple cycle returning points. LetCRPvi,vj;vs be the set of all cycle returning points r arising from a given vs∈CSVvi,vj. Then, CRPvi,vj;vs is the number of cycle returning points corresponding to a given vs∈CSVvi,vj, or equivalently, the number of symmetric cycles originating at a given vs∈CSVvi,vj. In addition, the number of all cycle returning points of path Pvi,vj can be computed as ∑vs∈CSVvi,vjCRPvi,vj;vs.The location of a cycle returning pointr∈CRPvi,vj;vs is determined by comparing the value of δvi,vj;vs to the length of the separate subpath originating at vs. If the value of δvi,vj;vs is less than the length of the separate subpath, then the cycle returning point r is located at a distance δvi,vj;vs from vs since drivers at cycle starting vertex vs can travel up to this distance from vs before refueling their vehicles; otherwise, the cycle returning point r is located at the leaf (end vertex) of the separate subpath because that vertex is the farthest point from vs in the symmetric cycle originating at vs.From the observation above regarding the location of a cycle returning point, we propose a novel algorithm, called the Cycle Returning Point Algorithm, to identify the locations of all cycle returning pointsr∈CRPvi,vj;vs for a given cycle starting vertex vs∈CSVvi,vj. This algorithm systematically explores the edges along separate subpaths originating at vs and computes the minimum remaining travel distance at each reachable vertex.When exploring an edgevu,vr along a separate subpath such that dvi,vu<dvi,vr or dvj,vu<dvj,vr, we call vu the parent of vr and vr the child of vu. To establish a parent and child relationship between vertices in the course of scanning the edges, we let PARENTvr be the set of parents of vr and CHILDRENvu the set of children of vu. In a tree network, every child vr has a single parent vu, that is, PARENTvr=vu. In contrast, every parent vu can have several children vr according to the tree network structure. Thus, set CHILDRENvu is determined as follows:(8)CHILDRENvu=Nvu\VPvi,vj,ifvu=vs,Nvu\PARENTvu,otherwise,where Nvu is the set of vertices adjacent to vu, or equivalently, the neighborhood of vu, and VPvi,vj is the set of vertices within Pvi,vj. In Expression (8), if vu=vs, CHILDRENvu is obtained by removing the vertices within Pvi,vj from the vertices adjacent to vu; otherwise, CHILDRENvu is generated by eliminating the parent of vu from the vertices adjacent to vu.The algorithm iterates to explore each edgevu,vr along separate subpaths originating at a given vertex vs∈CSVvi,vj until all cycle returning points r∈CRPvi,vj;vs are identified. At a particular iteration exploring an edge vu,vr, the minimum remaining travel distance of vehicles at vu, denoted as δvi,vj;vu, is known. That is, if vu=vs, the value of δvi,vj;vu is given by Expression (6); otherwise, this value is given from the previous iteration. Then, we can compute the minimum remaining travel distance of vehicles at vr as δvi,vj;vr=δvi,vj;vu-dvu,vr. If δvi,vj;vr<0, a cycle returning point r is located along edge vu,vr such that dvu,r=δvi,vj;vu. If δvi,vj;vr=0 or if δvi,vj;vr>0 and deg⁡vr=1, then r is placed exactly at vr. If δvi,vj;vr>0 and deg⁡vr≥2, then the drivers that are willing to deviate can travel further along the separate subpath; in this case, the algorithm assigns a child vr of the current iteration to a new parent vu at the next iteration and determines a new child vr using Expression (8) to proceed the next iteration.In order to keep track of a childvr from a prior iteration that may become a parent in a subsequent iteration on the search for cycle returning points, this algorithm uses a (infinite) first-in, first-out queue Q consisting of vr such that δvi,vj;vr>0 and deg⁡vr≥2. Two functions are used to manage Q. The first function named enqueue(Q;vr) places vr at the tail of queue Q. Conversely, the second function named dequeue(Q) selects the vertex at the head of queue Q and eliminates it from Q. The details of the Cycle Returning Point Algorithm are provided below.Algorithm 2 (Cycle Returning Point Algorithm).
Step  1. For a given vs∈CSVvi,vj, initialize CRPvi,vj;vs=∅. If α=0, terminate the algorithm; otherwise, compute δvi,vj;vs using Expression (6).
Step  2. Initialize Q=∅.
Step  3. Enqueue(Q;vs).
Step  4. Repeat the following substeps as long as there remain vertices in Q:
Sub-Step  4.1. vu=dequeue(Q).
Sub-Step  4.2. Determine CHILDRENvu using Expression (8).
Sub-Step  4.3. For each vr∈CHILDRENvu, perform the following steps:
Sub-Step  4.3.1. Compute δvi,vj;vr=δvi,vj;vu-dvu,vr.
Sub-Step  4.3.2. According to the sign of δvi,vj;vr, perform one of the following procedures:(a)
Ifδvi,vj;vr<0: r is located along edge vu,vr, such that dvu,r=δvi,vj;vu. Also, add r into CRPvi,vj;vs.(b)
Ifδvi,vj;vr=0 or if δvi,vj;vr>0 and deg⁡vr=1: r is located exactly at vr. Also, add r into CRPvi,vj;vs.(c)
Ifδvi,vj;vr>0 and deg⁡vr≥2: enqueue(Q;vr) and set PARENTvr=vu.Theorem 3 (complexity of the Cycle Returning Point Algorithm).
The complexity of the Cycle Returning Point Algorithm isOn, where n=V.Proof.
Step1 includes initialization of CRPvi,vj;vs, checking the value of α, and computation of δvi,vj;vs, which takes O1. Initialization of Q in Step 2 and enqueuing vs to Q in Step 3 also take O1. Step 4 consists of three substeps to identify all r∈CRPvi,vj;vs for a given vs∈CSVvi,vj. Sub-Steps  4.1 and 4.2 dequeue vu from Q and generate set CHILDRENvu. Sub-Step  4.3 computes δvi,vj;vr for vr∈CHILDRENvu, and then according to the sign of δvi,vj;vr, it locates a cycle returning point within edge vu,vr or enqueues vr to Q for the next iteration. Step 4 iterates until queue Q is empty. Since every vertex can be enqueued and dequeued at most once for a given vs∈CSVvi,vj, the operations in Step 4 can be applied to every vertex at most once; thus, the total time devoted to the operations in Step 4 is On. Therefore, the computational complexity of the Cycle Returning Point Algorithm is On.Now, we apply the Cycle Returning Point Algorithm to the example in Figure1 to determine all cycle returning points of Pv1,v3; that is, we need to identify CRPv1,v3;vs, for all vs∈CSVv1,v3. Recall that R=80, α=0.20, and vs∈CSVv1,v3=v2. In Step 1 of the algorithm, for a given cycle starting vertex v2, we set CRPv1,v3;v2=∅ and, by Expression (6), compute δv1,v3;v2=40-max⁡dv1,v2,dv3,v2=20. In Step 2, we set Q=∅. In Step 3, we place v2 at the tail of queue Q; that is, Q={v2}. Now, we repeat Step 4 until finding all cycle returning points r∈CRPv1,v3;v2. In Sub-Step  4.1, we set vu=v2 and eliminate v2 from Q. In Sub-Step  4.2, since vu=v2=vs, by Expression (8), CHILDRENv2=Nv2\VPv1,v3=v1,v3,v4\v1,v2,v3=v4. For vr=v4, we perform Sub-Step  4.3. In Sub-Step  4.3.1, δv1,v3;v4=δv1,v3;v2-dv2,v4=5. Since δv1,v3;v4>0 and deg⁡v4=3, we select Procedure (c) in Sub-Step  4.3.2; that is, Q={v4} and PARENTv4=v2. Since Q≠∅, we repeat Step  4. Now, in Sub-Step  4.1, vu=v4 and v4 is removed from Q. In Sub-Step  4.2, by Expression (8), CHILDRENv4=Nv4\PARENTv4=v2,v5,v6\v2=v5,v6. For vr∈v5,v6, we implement Sub-Step  4.3. For vr=v5, in Sub-Step  4.3.1, δv1,v3;v5=δv1,v3;v4-dv4,v5=-5. As δv1,v3;v5<0, we select Procedure (a) in Sub-Step  4.3.2; that is, we locate r1 along edge v4,v5, such that dv4,r1=δv1,v3;v4=5, and add r1 to CRPv1,v3;v2, where r1 indicates the first cycle returning point r∈CRPv1,v3;v2. By repeating the same process for vr=v6, we locate r2 along edge v4,v6, such that dv4,r2=5, and add r2 to CRPv1,v3;v2, where r2 refers to the second r∈CRPv1,v3;v2. Now, Q=∅, so we end the algorithm with CRPv1,v3;v2={r1,r2}.


## 4.4. Refueling Subtree

In this subsection, we determine the refueling subtree for each pathPvi,vj∈L^q that includes all possible locations for an AF refueling station when a portion of drivers select the deviation option. Then, we identify candidate points in this subtree.First, let us define symmetric cycleSCvi,vj;vs,r as the segment consisting of all station locations that cover the deviation-flow of path Pvi,vj originating at cycle starting vertex vs∈CSVvi,vj and ending at cycle returning point r∈CRPvi,vj;vs; that is, SCvi,vj;vs,r=Pvs,r. Note that any point x in SCvi,vj;vs,r\{vs} covers deviation-flow α×fvi,vj, while cycle starting vertex vs covers traffic flow fvi,vj since vs∈SCvi,vj;vs,r∩RSvi,vj.Now, for any pathPvi,vj∈L^q, we can construct the refueling subtree, denoted as RSTvi,vj, which consists of refueling segment RSvi,vj and all symmetric cycles SCvi,vj;vs,r of Pvi,vj. This refueling subtree contains all potential locations for an AF refueling station when a portion of drivers are willing to deviate from the preplanned route Pvi,vj to be able to refuel their vehicles. That is,(9)RSTvi,vj=⋃vs∈CSVvi,vj⋃r∈CRPvi,vj;vsSCvi,vj;vs,r∪RSvi,vj.In RSTvi,vj, the cardinality of RSvi,vj is one, but the cardinality of SCvi,vj;vs,r is ∑vs∈CSVvi,vjCRPvi,vj;vs, because the number of symmetric cycles in RSTvi,vj is equal to the number of cycle returning points r∈CRPvi,vj;vs, for vs∈CSVvi,vj.The amount of traffic flow inPvi,vj covered by x∈RSTvi,vj depends on the value of α. If α=1, any point x in RSTvi,vj covers fvi,vj. If 0<α<1, any point x in RSTvi,vj\RSvi,vj covers α×fvi,vj, while any point x in RSvi,vj covers fvi,vj. If α=0, then CRPvi,vj;vs=∅ by the Cycle Returning Point Algorithm; thus, RSTvi,vj=RSvi,vj, and any point x in RSTvi,vj covers fvi,vj.The endpoints ofRSvi,vj indicate the boundary points defining the segment containing all station locations that can cover the positive traffic flow in path Pvi,vj. Similarly, the endpoints of SCvi,vj;vs,r, which are vs and r, represent the boundary points for the segment encompassing all station locations that can cover the positive deviation-flow in path Pvi,vj originating at cycle starting vertex vs∈CSVvi,vj and ending at cycle returning point r∈CRPvi,vj;vs. In RSTvi,vj, the endpoints of RSvi,vj and all the endpoints of SCvi,vj;vs,r are called the candidate points because these points indicate the boundaries for potential station locations that cover path Pvi,vj with positive traffic flow or deviation-flow. The set of candidate points of RSTvi,vj, denoted as CPRSTvi,vj, is defined as follows:(10)CPRSTvi,vj=⋃vs∈CSVvi,vjCRPvi,vj;vs∪CSVvi,vj∪EPvi,vj,where CSVvi,vj∪⋃vs∈CSVvi,vjCRPvi,vj;vs is the set of endpoints of all symmetric cycles and EPvi,vj is the set of endpoints of the refueling segment of Pvi,vj. The kth candidate point of RSTvi,vj is denoted as ci,jk, k=1,…, ∑vs∈CSVvi,vjCRPvi,vj;vs+CSVvi,vj+EPvi,vj.In Expression (10), note that CRPvi,vj;vs=∅ when there is no deviation option α=0, while CSVvi,vj and EPvi,vj are defined for 0≤α≤1. Note that the vertices in CSVvi,vj still need to be considered although the deviation option is not available, that is, for α=0, because some of these points are intersection vertices that may cover traffic flows from multiple paths [32]. Since an intersection vertex within a refueling segment has the same characteristics of a cycle starting vertex, we construct set CSVvi,vj for α=0 to identify this type of intersection vertices even though the deviation option is not available.By using Expression (10), the set of candidate points in expanded subtree T^q,q=1,…,t, denoted as CPq, can be defined as follows:(11)CPq=⋃Pvi,vj∈L^qCPRSTvi,vj.Now, we determine the refueling subtree for pathPv1,v3 in Figure 1. Recall that CSVv1,v3 = v2 and CRPv1,v3;v2 = r1,r2. Then, symmetric cycles of Pv1,v3 are SCv1,v3;v2,r1 and SCv1,v3;v2,r2. Thus, RSTv1,v3=SCv1,v3;v2,r1∪SCv1,v3;v2,r2∪RSv1,v3. If we assume L^q=Pv1,v3, since α=0.20, then any point x∈RSTv1,v3\RSv1,v3 covers 20% of fv1,v3, and any point x∈RSv1,v3 covers fv1,v3. In addition, by Expression (11), CPq=CRPv1,v3;v2∪CSVv1,v3∪EPv1,v3=r1,r2∪v2∪v1,v3.


## 4.5. Candidate Point Optimality Theorem

In this subsection, we prove that the set of candidate points,CP=⋃q=1tCPq, contains at least one optimal location to the problem.Lemma 4.
Consider a pointx∈T^q,  for some q=1,…,t, such that x∉CPq. Then,(a)
ifx∉⋃P(vi,vj)∈L^qRSTvi,vj, then Sx=SDx=∅ and Fx=0;(b)
ifx∈⋃P(vi,vj)∈L^qRSTvi,vj, then there exists a candidate point c∈CPq such that Sx⊆Sc, SDx⊆SDc∪Sc, and Fx≤Fc.Proof.
In case (a), by definition of refueling subtree,x does not cover any path in L^q. Thus, the result holds. In case (b), x is in the interior of all the refueling subtrees determined by all paths in Sx and SDx. Thus, x has at least one candidate point on each side. Let c1 and c2 be the two closest candidate points on each side of x. Because no candidate point is located between x and ci,i=1,2, the paths with positive traffic flow covered by x are the same paths with positive traffic flow covered by both c1 and c2; that is, Sx=Sc1∩Sc2, and thus, Sx⊆Sci,i = 1, 2. On the other hand, any path with positive deviation-flow covered by x must either be a path with positive deviation-flow covered by both c1 and c2 or be a path with positive traffic flow covered by one of the two candidate points (c1 and c2) and with positive deviation-flow covered by the other candidate point; that is, SDx = SDc1∩SDc2∪Sc1∩SDc2∪SDc1∩Sc2. This implies SDx⊆SDci∪Sci,i=1,2. Thus, for 0≤α≤1, ∑Pvi,vj∈Sxfvi,vj+∑Pvi,vj∈SDxα×fvi,vj≤∑P(vi,vj)∈S(ci)fvi,vj+∑P(vi,vj)∈SD(ci)α×fvi,vj, or equivalently, Fx≤Fci,i=1,2.Theorem 5 (Candidate Point Optimality Theorem).
For the continuous deviation-flow location problem for an AF refueling station on treeT, there exists at least one optimal location x∗∈CP.Proof (by contradiction).
Suppose that none of the candidate points in CP is an optimal solution. Letx∗ be an optimal point that covers Fx∗ round trips per time unit. Since x∗ is an optimal location, by case (a) of Lemma 4, x∗ must belong to ⋃P(vi,vj)∈L^qRSTvi,vj, for some q=1,…,t. If x∗∈⋃P(vi,vj)∈L^qRSTvi,vj, then by case (b) of Lemma 4, there exists a candidate point c∈CPq such that Fx∗≤Fc. This contradicts the initial hypothesis that none of the candidate points in CP is an optimal solution. Thus, there exists at least one candidate point in CP that is an optimal location to the problem.


## 5. Deviation-Flow Optimal Candidate Point Algorithm

Based on the Candidate Point Optimality Theorem, in this section the Deviation-Flow Optimal Candidate Point Algorithm is proposed to find the optimal set of candidate points for an AF refueling station that covers the maximum traffic flow (in round trips per time unit) when a portion of drivers select the deviation option. The central idea of this algorithm can be summarized in three steps. Step1 constructs expanded subtrees T^q, for q=1,…,t, from the original tree network T, as discussed in Section 3. Step 2 determines the set of local maximum candidate points for each T^q. As shown in Theorem 5, at least one local optimal candidate point is global optimal. Step 3 finds the set of global maximum candidate points of T by comparing the local maximum candidate points.This algorithm is a generalization of the Single Refueling Point Algorithm that finds the set of optimal locations for a refueling station when vehicle deviation is not available [18]. A distinct feature of the proposed algorithm is that it generates the deviation options for all O/D pairs with positive flows when 0<α≤1, which usually produces a larger set of candidate points and consequently a different set of optimal locations. In addition, by changing the value of α between 0 and 1 in the algorithm, we can analyze the effect of the portion of drivers choosing the deviation option on the optimal set of station locations and traffic flow covered. The steps of the algorithm are specified below.Algorithm 6 (Deviation-Flow Optimal Candidate Point Algorithm).
Step  1. Construct expanded subtrees T^qV^q,E^q, for q=1,…,t, from original tree network TV,E.
Sub-Step  1.1. Establish set E^=vk,vl∈E∣dvk,vl>R and eliminate vk,vl∈E^ from E.
Sub-Step  1.2. Determine forest FVF,EF that consists of subtrees TqVq,Eq, for q=1,…,t, such that VF=⋃q=1tVq=V and EF=⋃q=1tEq=E\E^, where t=E^+1.
Sub-Step  1.3. For subtree TqVq,Eq,q=1,…,t, determine expanded subtree T^qV^q,E^q.
Sub-Step  1.3.1. Initialize V-q=∅ and generate Vq′=VE^∩Vq.
Sub-Step  1.3.2. For vk∈Vq′, if there exists at least one α×fvi,vj>0, for Pvi,vj∈L in Tq, such that max⁡dvi,vk,dvj,vk<R/2, then add vk into V-q.
Sub-Step  1.3.3. Construct expanded subtree T^qV^q,E^q such that V^q=Vq∪⋃vk∈V-qVvk and E^q=Eq∪⋃vk∈V-qEvk, where Evk=vk,vl∈E^∣vl∈V\Vq, Vvk=VEvk\vk, and VEvk is the set of vertices in Evk.
Step  2. For each expanded subtree T^q,q=1,…,t, with V^q>1, identify the set of local optimal candidate points, denoted as CPq∗, in CPq (note that, for T^q with V^q=1, set CPq∗=xq∗ and Fxq∗=0, where xq∗ is located at the only vertex in T^q):
Sub-Step  2.1. Construct L^q=Pvi,vj∣dvi,vj≤R,fvi,vj>0,andi<j,forallvi,vj∈V^q.
Sub-Step  2.2. Determine the set of candidate points, CPq, using Expression (11).
Sub-Step  2.3. For all c∈CPq, construct S(c)=Pvi,vj∈L^q∣c∈P(vi,vj),f(vi,vj)>0,dvi,c≤R/2,anddc,vj≤R/2 and SDc=Pvi,vj∈L^q∣c∈Tq\Pvi,vj,α×f(vi,vj)>0,dvi,c≤R/2,anddc,vj≤R/2.
Sub-Step  2.4. Calculate Fc=∑P(vi,vj)∈S(c)fvi,vj+∑P(vi,vj)∈SD(c)α×fvi,vj, for all c∈CPq, then determine the local optimal set of candidate points, CPq∗, in CPq: (12)CPq∗=arg⁡maxFc∣c∈CPq.
Step  3. Find the global optimal set of candidate points, denoted as CP∗, for the original tree T and the corresponding maximum total traffic flow in round trips per time unit F∗:(13)CP∗=arg⁡max⁡Fxq∗∣xq∗∈CPq∗,q=1,…,t,F∗=Fx∗,forx∗∈CP∗.Theorem 7 (complexity of the Deviation-Flow Optimal Candidate Point Algorithm).
The Deviation-Flow Optimal Candidate Point Algorithm runs inOn5 time, where n=V.Proof.
Step1 of the algorithm contains three substeps to generate expanded subtrees T^qV^q,E^q, for q=1,…,t, from original tree TV,E. Sub-Step  1.1 takes On to find and remove edges vk,vl∈E^ from E. To construct forest FVF,EF containing subtrees TqVq,Eq, for q=1,…,t, in Sub-Step  1.2, we start with a forest where each vertex forms its own tree. Then, for each edge vi,vk∈E\E^, two trees connected by an edge vi,vk are merged into a single tree. We repeat this iteration for all edges in E\E^, thus we obtain the final set of subtrees in On time. To build expanded subtree T^q from Tq,q=1,…,t, Sub-Step  1.3 takes On3 to identify Vq′ and compute max⁡dvi,vk,dvj,vk for vk∈Vq′ and Pvi,vj∈L in Tq. Step 2 consists of four substeps to find the set of local optimal candidate points CPq∗ for each T^q. Sub-Step  2.1 takes On2 to measure dvi,vj, for all vi,vj∈V^q, and build set L^q,q=1,…,t. To determine CPq,q=1,…,t, Sub-Step  2.2 first builds RSvi,vj and EPvi,vj for Pvi,vj∈L^q, which takes On2. Next, for each RSvi,vj, Sub-Step  2.2 identifies CSVvi,vj, which takes On. Lastly, for each vs∈CSVvi,vj, Sub-Step  2.2 finds CRPvi,vj;vs, which takes On by Theorem 3. Thus, the total time devoted to Sub-Step  2.2 is On4. Since we can find On candidate points for each path Pvi,vj∈L^q, and furthermore, there exist On2 paths in each L^q, the number of candidate points in CPq is On3. Therefore, Sub-Step  2.3 takes On5 to generate the sets of paths with positive traffic flow and deviation-flow covered by all candidate points c∈CPq,q=1,…,t. Similarly, Sub-Step  2.4 takes On5 to compute the total traffic flow covered by all candidate points, compare the total traffic flows covered by candidate points in T^q,q=1,…,t, and determine the local optimal set of candidate points for each T^q. Step 3 takes On2 to compare the local optimal solutions and determine the global optimal set of candidate points in T. The algorithm performs each step once. Thus, the total time devoted to operations in the algorithm is On5.


## 6. Convex Combination Property

This section consists of two subsections to identify additional optimal points that can be generated as convex combinations of certain pairs of optimal candidate points. First, a condition is identified in Section6.1 under which any point on the line segment between two consecutive optimal candidate points is also optimal. Then, based on this condition, the complete set of optimal solutions for the problem is determined in Section 6.2.


### 6.1. Optimality Conditions for a Convex Combination of Consecutive Optimal Candidate Points

In this subsection, given any pair of consecutive optimal candidate points,c1∗,c2∗∈CP∗, we identify conditions under which any point that can be written as a convex combination of c1∗ and c2∗ is also optimal.To simplify the proof process to derive the conditions, we first partitionSc1∗, SDc1∗, Sc2∗, and SDc2∗ into newly defined subsets as shown below. Since there exists no candidate point between c1∗ and c2∗, Sc1∗ is partitioned into S1c1∗ and S1,2c1∗, where S1c1∗ denotes the subset of paths with positive traffic flow covered by c1∗ but not covered by c2∗, and S1,2c1∗ denotes the subset of paths with positive traffic flow covered by both c1∗ and c2∗. We also partition SDc1∗ into SD1c1∗ and SD1,2c1∗, where SD1c1∗ denotes the subset of paths with positive deviation-flow covered by c1∗ but not covered by c2∗, and SD1,2c1∗ denotes the subset of paths with positive deviation-flow covered by both c1∗ and c2∗. SD1c1∗ can also be partitioned into SD1\2c1∗ and SD1c1∗\SD1\2c1∗, where SD1\2c1∗ denotes the subset of paths with positive deviation-flow covered by c1∗ and positive traffic flow not covered by c2∗, and SD1c1∗\SD1\2c1∗ denotes the subset of paths with positive traffic flow covered by c2∗ and positive deviation-flow covered by c1∗. Similarly, we can partition Sc2∗ and SDc2∗, such that Sc2∗=S2c2∗∪S1,2c2∗, SDc2∗=SD2c2∗∪SD1,2c2∗, and SD2c2∗=SD2\1c2∗∪SD2c2∗\SD2\1c2∗. Then, by using these terms, Fc1∗ and Fc2∗ can be written as follows:(14)Fc1∗=∑Pvi,vj∈S1c1∗fvi,vj+∑Pvi,vj∈S1,2c1∗fvi,vj+α∑Pvi,vj∈SD1\2c1∗fvi,vj+∑Pvi,vj∈SD1c1∗\SD1\2c1∗fvi,vj+∑Pvi,vj∈SD1,2c1∗fvi,vj,Fc2∗=∑Pvi,vj∈S2c2∗fvi,vj+∑Pvi,vj∈S1,2c2∗fvi,vj+α∑Pvi,vj∈SD2\1c2∗fvi,vj+∑Pvi,vj∈SD2c2∗\SD2\1c2∗fvi,vj+∑Pvi,vj∈SD1,2c2∗fvi,vj.Note also that, by definition,S1,2c1∗=S1,2c2∗ and SD1,2c1∗=SD1,2c2∗. Similarly, SD2c2∗\SD2\1c2∗⊆S1c1∗ and SD1c1∗\SD1\2c1∗⊆S2c2∗.The following theorem establishes optimality conditions for points that can be written as convex combinations of consecutive optimal candidate points.Theorem 8 (optimality conditions for the line segment joining consecutive optimal candidate points).
Given a pair of consecutive optimal candidate points,c1∗,c2∗∈CP∗, let lc1∗,c2∗ denote the line segment joining c1∗ and c2∗; that is, lc1∗,c2∗=x∣x=βc1∗+1-βc2∗,0≤β≤1. Then, any point x∈lc1∗,c2∗ is also optimal if and only if one of the following conditions is satisfied:(a)
Sc1∗=Sc2∗, for α=0.(b)
Sc1∗=Sc2∗ and SDc1∗=SDc2∗, for 0<α<1.(c)
Sc1∗∪SDc1∗=Sc2∗∪SDc2∗, for α=1.Proof.
⇒ Assume that any point x∈lc1∗,c2∗ is also optimal. This implies Fc1∗=Fx=Fc2∗, or equivalently, Fc1∗-Fx=Fc2∗-Fx=0. Since c1∗ and c2∗ are the two closest candidate points on each side of x, Sx=S1,2c1∗ and SDx=SD1,2c1∗∪SD1c1∗\SD1\2c1∗∪SD2c2∗\SD2\1c2∗. Thus, Fx can be written as follows:(15)Fx=∑Pvi,vj∈S1,2c1∗fvi,vj+α∑Pvi,vj∈SD1,2c1∗fvi,vj+∑Pvi,vj∈SD1c1∗\SD1\2c1∗fvi,vj+∑Pvi,vj∈SD2c2∗\SD2\1c2∗fvi,vj.We recall that S1,2c1∗=S1,2c2∗ and SD1,2c1∗=SD1,2c2∗. Thus, Fc1∗-Fx and Fc2∗-Fx can be expressed as follows:(16)Fc1∗-Fx=∑Pvi,vj∈S1c1∗fvi,vj+∑Pvi,vj∈SD1\2c1∗α×fvi,vj-∑Pvi,vj∈SD2c2∗\SD2\1c2∗α×fvi,vj,Fc2∗-Fx=∑Pvi,vj∈S2c2∗fvi,vj+∑Pvi,vj∈SD2\1c2∗α×fvi,vj-∑Pvi,vj∈SD1c1∗\SD1\2c1∗α×fvi,vj.
In case (a), sinceα=0, SDc1∗=SDc2∗=∅. Then, the equalities Fc1∗-Fx = Fc2∗-Fx = 0 can only be satisfied if S1c1∗=S2c2∗=∅. This means that Sc1∗=S1,2c1∗=Sc2∗.
In case (b),0<α<1. Recall that SD2c2∗\SD2\1c2∗⊆S1c1∗ and SD1c1∗\SD1\2c1∗⊆S2c2∗. This means that ∑Pvi,vj∈S1c1∗fvi,vj-∑Pvi,vj∈SD2c2∗\SD2\1c2∗α×fvi,vj>0 in Fc1∗-Fx and ∑Pvi,vj∈S2c2∗fvi,vj-∑Pvi,vj∈SD1c1∗\SD1\2c1∗α×fvi,vj>0 in Fc2∗-Fx if S1c1∗ and S2c2∗ are not empty. Thus, to satisfy equalities Fc1∗-Fx = Fc2∗-Fx = 0, it is necessary to have S1c1∗=S2c2∗=SD1\2c1∗=SD2\1c2∗=∅. Note also that if S1c1∗=S2c2∗=∅, then SD2c2∗\SD2\1c2∗=SD1c1∗\SD1\2c1∗=∅ because SD2c2∗\SD2\1c2∗⊆S1c1∗ and SD1c1∗\SD1\2c1∗⊆S2c2∗. Therefore, Sc1∗=S1,2c1∗=Sc2∗ and SDc1∗=SD1,2c1∗=SDc2∗.
In case (c), sinceα=1 and SD2c2∗\SD2\1c2∗⊆S1c1∗, to satisfy Fc1∗-Fx=0, it is necessary to have SD1\2c1∗=∅ and SD2c2∗\SD2\1c2∗=S1c1∗. Similarly, Fc2∗-Fx=0 can only be satisfied if SD2\1c2∗=∅ and SD1c1∗\SD1\2c1∗=S2c2∗. These results also imply that Sc1∗∪SDc1∗=S1c1∗∪S1,2c1∗∪SD1,2c1∗∪S2c2∗ and Sc2∗∪SDc2∗=S2c2∗∪S1,2c2∗∪SD1,2c2∗∪S1c1∗. Since S1,2c1∗=S1,2c2∗ and SD1,2c1∗=SD1,2c2∗, we can finally conclude that Sc1∗∪SDc1∗=Sc2∗∪SDc2∗.
⇐ In case (a), we assume Sc1∗=Sc2∗. This implies that S1c1∗=S2c2∗=∅. Also, since α=0, SDc1∗=SDc2∗=∅. Thus, Fc1∗-Fx = Fc2∗-Fx = 0.
In case (b), we assume thatSc1∗=Sc2∗ and SDc1∗=SDc2∗. This implies that S1c1∗=S2c2∗=∅ and SD1\2c1∗=SD2\1c2∗=∅. Note also that SD2c2∗\SD2\1c2∗=SD1c1∗\SD1\2c1∗=∅ because SD2c2∗\SD2\1c2∗⊆S1c1∗, SD1c1∗\SD1\2c1∗⊆S2c2∗, and S1c1∗=S2c2∗=∅. Thus, Fc1∗-Fx = Fc2∗-Fx = 0.
In case (c), we assume thatSc1∗∪SDc1∗=Sc2∗∪SDc2∗. This implies that S1c1∗∪SD1\2c1∗∪SD1c1∗\SD1\2c1∗=S2c2∗∪SD2\1c2∗∪SD2c2∗\SD2\1c2∗. Since SD2c2∗\SD2\1c2∗⊆S1c1∗ and SD1c1∗\SD1\2c1∗⊆S2c2∗, to satisfy S1c1∗∪SD1\2c1∗∪SD1c1∗\SD1\2c1∗=S2c2∗∪SD2\1c2∗∪SD2c2∗\SD2\1c2∗, it is necessary to have SD1\2c1∗=SD2\1c2∗=∅, S1c1∗=SD2c2∗\SD2\1c2∗, and S2c2∗=SD1c1∗\SD1\2c1∗. As a result, Fc1∗-Fx = Fc2∗-Fx = 0.
Since the conditions in cases (a), (b), and (c) lead toFc1∗=Fx=Fc2∗, and furthermore c1∗,c2∗∈CP∗, any point x∈lc1∗,c2∗ is optimal.


### 6.2. Complete Set of Optimal Solutions

In this subsection, we determine the complete set of optimal solutions, denoted asCS∗, for the continuous deviation-flow location problem for an AF refueling station.As an intermediate step toward determiningCS∗, we first construct the set pairs of consecutive candidate points in CP∗ that satisfy the conditions stated in Theorem 8, denoted as set CP-∗. Then, by Theorem 8, the line segments defined by these pairs of candidate points in CP-∗ are also optimal. Consequently, the complete set of optimal solutions, denoted as CS∗, can be defined as follows:(17)CS∗=⋃c1∗,c2∗∈CP-∗lc1∗,c2∗∪CP∗\VCP-∗,where VCP-∗ is the set of optimal candidate points in CP-∗. The optimality of set CS∗ is proved in the following theorem.Theorem 9 (optimality of the complete set of optimal solutions).
SetCS∗, defined in Expression (17), contains all optimal solutions for the problem.Proof (by contradiction).
Suppose that there exists an optimal pointx∗ that does not belong to CS∗. Because CS∗ includes all optimal candidate points in CP∗ and x∗∉CS∗, x∗ should be a point in T that is not a candidate point. First, suppose that x∗∉⋃P(vi,vj)∈L^qRSTvi,vj. Then, by case (a) of Lemma 4, Fx∗=0. This contradicts the hypothesis that x∗ is optimal. Thus, x∗ must belong to ⋃P(vi,vj)∈L^qRSTvi,vj. Since x∗∈⋃P(vi,vj)∈L^qRSTvi,vj, by case (b) of Lemma 4, there exist two closest candidate points, c1 and c2, on each side of x∗, such that Sx∗⊆Sci, SDx∗⊆SDci∪Sci, and Fx∗≤Fci,i=1,2. Because x∗ is optimal, c1 and c2 are also optimal, and therefore, Theorem 8 holds for the convex combination of c1 and c2. This means that x∗∈lc1,c2∈CS∗. This contradicts the initial hypothesis that there exists an optimal point x∗ that does not belong to CS∗. Thus, CS∗ contains all the optimal solutions.


## 6.1. Optimality Conditions for a Convex Combination of Consecutive Optimal Candidate Points

In this subsection, given any pair of consecutive optimal candidate points,c1∗,c2∗∈CP∗, we identify conditions under which any point that can be written as a convex combination of c1∗ and c2∗ is also optimal.To simplify the proof process to derive the conditions, we first partitionSc1∗, SDc1∗, Sc2∗, and SDc2∗ into newly defined subsets as shown below. Since there exists no candidate point between c1∗ and c2∗, Sc1∗ is partitioned into S1c1∗ and S1,2c1∗, where S1c1∗ denotes the subset of paths with positive traffic flow covered by c1∗ but not covered by c2∗, and S1,2c1∗ denotes the subset of paths with positive traffic flow covered by both c1∗ and c2∗. We also partition SDc1∗ into SD1c1∗ and SD1,2c1∗, where SD1c1∗ denotes the subset of paths with positive deviation-flow covered by c1∗ but not covered by c2∗, and SD1,2c1∗ denotes the subset of paths with positive deviation-flow covered by both c1∗ and c2∗. SD1c1∗ can also be partitioned into SD1\2c1∗ and SD1c1∗\SD1\2c1∗, where SD1\2c1∗ denotes the subset of paths with positive deviation-flow covered by c1∗ and positive traffic flow not covered by c2∗, and SD1c1∗\SD1\2c1∗ denotes the subset of paths with positive traffic flow covered by c2∗ and positive deviation-flow covered by c1∗. Similarly, we can partition Sc2∗ and SDc2∗, such that Sc2∗=S2c2∗∪S1,2c2∗, SDc2∗=SD2c2∗∪SD1,2c2∗, and SD2c2∗=SD2\1c2∗∪SD2c2∗\SD2\1c2∗. Then, by using these terms, Fc1∗ and Fc2∗ can be written as follows:(14)Fc1∗=∑Pvi,vj∈S1c1∗fvi,vj+∑Pvi,vj∈S1,2c1∗fvi,vj+α∑Pvi,vj∈SD1\2c1∗fvi,vj+∑Pvi,vj∈SD1c1∗\SD1\2c1∗fvi,vj+∑Pvi,vj∈SD1,2c1∗fvi,vj,Fc2∗=∑Pvi,vj∈S2c2∗fvi,vj+∑Pvi,vj∈S1,2c2∗fvi,vj+α∑Pvi,vj∈SD2\1c2∗fvi,vj+∑Pvi,vj∈SD2c2∗\SD2\1c2∗fvi,vj+∑Pvi,vj∈SD1,2c2∗fvi,vj.Note also that, by definition,S1,2c1∗=S1,2c2∗ and SD1,2c1∗=SD1,2c2∗. Similarly, SD2c2∗\SD2\1c2∗⊆S1c1∗ and SD1c1∗\SD1\2c1∗⊆S2c2∗.The following theorem establishes optimality conditions for points that can be written as convex combinations of consecutive optimal candidate points.Theorem 8 (optimality conditions for the line segment joining consecutive optimal candidate points).
Given a pair of consecutive optimal candidate points,c1∗,c2∗∈CP∗, let lc1∗,c2∗ denote the line segment joining c1∗ and c2∗; that is, lc1∗,c2∗=x∣x=βc1∗+1-βc2∗,0≤β≤1. Then, any point x∈lc1∗,c2∗ is also optimal if and only if one of the following conditions is satisfied:(a)
Sc1∗=Sc2∗, for α=0.(b)
Sc1∗=Sc2∗ and SDc1∗=SDc2∗, for 0<α<1.(c)
Sc1∗∪SDc1∗=Sc2∗∪SDc2∗, for α=1.Proof.
⇒ Assume that any point x∈lc1∗,c2∗ is also optimal. This implies Fc1∗=Fx=Fc2∗, or equivalently, Fc1∗-Fx=Fc2∗-Fx=0. Since c1∗ and c2∗ are the two closest candidate points on each side of x, Sx=S1,2c1∗ and SDx=SD1,2c1∗∪SD1c1∗\SD1\2c1∗∪SD2c2∗\SD2\1c2∗. Thus, Fx can be written as follows:(15)Fx=∑Pvi,vj∈S1,2c1∗fvi,vj+α∑Pvi,vj∈SD1,2c1∗fvi,vj+∑Pvi,vj∈SD1c1∗\SD1\2c1∗fvi,vj+∑Pvi,vj∈SD2c2∗\SD2\1c2∗fvi,vj.We recall that S1,2c1∗=S1,2c2∗ and SD1,2c1∗=SD1,2c2∗. Thus, Fc1∗-Fx and Fc2∗-Fx can be expressed as follows:(16)Fc1∗-Fx=∑Pvi,vj∈S1c1∗fvi,vj+∑Pvi,vj∈SD1\2c1∗α×fvi,vj-∑Pvi,vj∈SD2c2∗\SD2\1c2∗α×fvi,vj,Fc2∗-Fx=∑Pvi,vj∈S2c2∗fvi,vj+∑Pvi,vj∈SD2\1c2∗α×fvi,vj-∑Pvi,vj∈SD1c1∗\SD1\2c1∗α×fvi,vj.
In case (a), sinceα=0, SDc1∗=SDc2∗=∅. Then, the equalities Fc1∗-Fx = Fc2∗-Fx = 0 can only be satisfied if S1c1∗=S2c2∗=∅. This means that Sc1∗=S1,2c1∗=Sc2∗.
In case (b),0<α<1. Recall that SD2c2∗\SD2\1c2∗⊆S1c1∗ and SD1c1∗\SD1\2c1∗⊆S2c2∗. This means that ∑Pvi,vj∈S1c1∗fvi,vj-∑Pvi,vj∈SD2c2∗\SD2\1c2∗α×fvi,vj>0 in Fc1∗-Fx and ∑Pvi,vj∈S2c2∗fvi,vj-∑Pvi,vj∈SD1c1∗\SD1\2c1∗α×fvi,vj>0 in Fc2∗-Fx if S1c1∗ and S2c2∗ are not empty. Thus, to satisfy equalities Fc1∗-Fx = Fc2∗-Fx = 0, it is necessary to have S1c1∗=S2c2∗=SD1\2c1∗=SD2\1c2∗=∅. Note also that if S1c1∗=S2c2∗=∅, then SD2c2∗\SD2\1c2∗=SD1c1∗\SD1\2c1∗=∅ because SD2c2∗\SD2\1c2∗⊆S1c1∗ and SD1c1∗\SD1\2c1∗⊆S2c2∗. Therefore, Sc1∗=S1,2c1∗=Sc2∗ and SDc1∗=SD1,2c1∗=SDc2∗.
In case (c), sinceα=1 and SD2c2∗\SD2\1c2∗⊆S1c1∗, to satisfy Fc1∗-Fx=0, it is necessary to have SD1\2c1∗=∅ and SD2c2∗\SD2\1c2∗=S1c1∗. Similarly, Fc2∗-Fx=0 can only be satisfied if SD2\1c2∗=∅ and SD1c1∗\SD1\2c1∗=S2c2∗. These results also imply that Sc1∗∪SDc1∗=S1c1∗∪S1,2c1∗∪SD1,2c1∗∪S2c2∗ and Sc2∗∪SDc2∗=S2c2∗∪S1,2c2∗∪SD1,2c2∗∪S1c1∗. Since S1,2c1∗=S1,2c2∗ and SD1,2c1∗=SD1,2c2∗, we can finally conclude that Sc1∗∪SDc1∗=Sc2∗∪SDc2∗.
⇐ In case (a), we assume Sc1∗=Sc2∗. This implies that S1c1∗=S2c2∗=∅. Also, since α=0, SDc1∗=SDc2∗=∅. Thus, Fc1∗-Fx = Fc2∗-Fx = 0.
In case (b), we assume thatSc1∗=Sc2∗ and SDc1∗=SDc2∗. This implies that S1c1∗=S2c2∗=∅ and SD1\2c1∗=SD2\1c2∗=∅. Note also that SD2c2∗\SD2\1c2∗=SD1c1∗\SD1\2c1∗=∅ because SD2c2∗\SD2\1c2∗⊆S1c1∗, SD1c1∗\SD1\2c1∗⊆S2c2∗, and S1c1∗=S2c2∗=∅. Thus, Fc1∗-Fx = Fc2∗-Fx = 0.
In case (c), we assume thatSc1∗∪SDc1∗=Sc2∗∪SDc2∗. This implies that S1c1∗∪SD1\2c1∗∪SD1c1∗\SD1\2c1∗=S2c2∗∪SD2\1c2∗∪SD2c2∗\SD2\1c2∗. Since SD2c2∗\SD2\1c2∗⊆S1c1∗ and SD1c1∗\SD1\2c1∗⊆S2c2∗, to satisfy S1c1∗∪SD1\2c1∗∪SD1c1∗\SD1\2c1∗=S2c2∗∪SD2\1c2∗∪SD2c2∗\SD2\1c2∗, it is necessary to have SD1\2c1∗=SD2\1c2∗=∅, S1c1∗=SD2c2∗\SD2\1c2∗, and S2c2∗=SD1c1∗\SD1\2c1∗. As a result, Fc1∗-Fx = Fc2∗-Fx = 0.
Since the conditions in cases (a), (b), and (c) lead toFc1∗=Fx=Fc2∗, and furthermore c1∗,c2∗∈CP∗, any point x∈lc1∗,c2∗ is optimal.


## 6.2. Complete Set of Optimal Solutions

In this subsection, we determine the complete set of optimal solutions, denoted asCS∗, for the continuous deviation-flow location problem for an AF refueling station.As an intermediate step toward determiningCS∗, we first construct the set pairs of consecutive candidate points in CP∗ that satisfy the conditions stated in Theorem 8, denoted as set CP-∗. Then, by Theorem 8, the line segments defined by these pairs of candidate points in CP-∗ are also optimal. Consequently, the complete set of optimal solutions, denoted as CS∗, can be defined as follows:(17)CS∗=⋃c1∗,c2∗∈CP-∗lc1∗,c2∗∪CP∗\VCP-∗,where VCP-∗ is the set of optimal candidate points in CP-∗. The optimality of set CS∗ is proved in the following theorem.Theorem 9 (optimality of the complete set of optimal solutions).
SetCS∗, defined in Expression (17), contains all optimal solutions for the problem.Proof (by contradiction).
Suppose that there exists an optimal pointx∗ that does not belong to CS∗. Because CS∗ includes all optimal candidate points in CP∗ and x∗∉CS∗, x∗ should be a point in T that is not a candidate point. First, suppose that x∗∉⋃P(vi,vj)∈L^qRSTvi,vj. Then, by case (a) of Lemma 4, Fx∗=0. This contradicts the hypothesis that x∗ is optimal. Thus, x∗ must belong to ⋃P(vi,vj)∈L^qRSTvi,vj. Since x∗∈⋃P(vi,vj)∈L^qRSTvi,vj, by case (b) of Lemma 4, there exist two closest candidate points, c1 and c2, on each side of x∗, such that Sx∗⊆Sci, SDx∗⊆SDci∪Sci, and Fx∗≤Fci,i=1,2. Because x∗ is optimal, c1 and c2 are also optimal, and therefore, Theorem 8 holds for the convex combination of c1 and c2. This means that x∗∈lc1,c2∈CS∗. This contradicts the initial hypothesis that there exists an optimal point x∗ that does not belong to CS∗. Thus, CS∗ contains all the optimal solutions.


## 7. Numerical Example and Analysis of Results

In this section, a numerical example is provided to illustrate the proposed solution approach and verify its performance. Figure2 shows the undirected tree TV,E with n=11 vertices, and Table 3 provides the average traffic flows fvi,vj, for all vi,vj∈V such that i<j. Note that although we use a small-size network to show the step-by-step application of the proposed procedure to find the optimal set of station locations, the procedure can also be applied for the large-scale problems due to its polynomial time complexity. In addition, since the actual portion of drivers who select the deviation portion α is difficult to find in practice, in this example, we change α from 0 to 1 to analyze its effect on the optimal set of location sites.Table 3
Traffic flowsfvi,vj (in round trips per time unit) corresponding to all simple paths Pvi,vj in T.
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
v
1
—
80
40
30
20
0
10
8
5
3
0
v
2
—
—
70
60
30
15
20
17
14
9
1
v
3
—
—
—
90
60
50
10
9
6
5
0
v
4
—
—
—
—
100
30
155
100
80
50
15
v
5
—
—
—
—
—
10
20
16
14
15
12
v
6
—
—
—
—
—
—
6
5
1
3
0
v
7
—
—
—
—
—
—
—
90
85
82
80
v
8
—
—
—
—
—
—
—
—
140
0
0
v
9
—
—
—
—
—
—
—
—
—
0
0
v
10
—
—
—
—
—
—
—
—
—
—
80
v
11
—
—
—
—
—
—
—
—
—
—
—Figure 2
Structure of undirected treeT.The remainder of this section is organized as follows. In Section7.1, for a given value of the vehicle driving range R, we apply the Deviation-Flow Optimal Candidate Point Algorithm to solve the numerical example. In Section 7.2, we further examine the coupled effects of deviation portion and vehicle driving range on the set of optimal locations and the maximum traffic flow covered. In Section 7.3, we compare the results of the proposed solution approach with the existing models to verify its performance.


### 7.1. Numerical Example for a Given Vehicle Driving Range

In this subsection, we fix the driving rangeR=80 and solve the numerical example to illustrate the Deviation-Flow Optimal Candidate Point Algorithm in detail.To construct the expanded subtrees fromT in Step 1, Sub-Step  1.1 finds dv7,v8>R; thus, E^=v7,v8. By removing v7,v8 from T, Sub-Step  1.2 forms forest FVF,EF containing two subtrees T1V1,E1 and T2V2,E2, where V1=v1,v2,v3,v4,v5,v6,v7, E1=v1,v2,v2,v3,v3,v4,v4,v5,v3,v6,v4,v7, V2=v8,v9,v10,v11, and E2=v8,v9,v8,v10,v10,v11. For T1, Sub-Step  1.3 sets V-1=∅ and generates V1′=VE^∩V1=v7. For vk∈V1′, even if α>0, there is no α×fvi,vj>0, for vi,vj∈V1, such that max⁡dvi,vk,dvj,vk<R/2. Thus, V-1 remains empty, and expanded subtree T^1V^1,E^1 = T1V1,E1. For T2, Sub-Step  1.3 sets V-2=∅ and forms V2′=VE^∩V2=v8. For vk∈V2′, if α>0, there exists α×fv8,v9>0, such that max⁡dv8,vk,dv9,vk = 15 <R/2. Thus, v8 is added to V-2, and expanded subtree T^2V^2,E^2 is such that V^2=V2∪Vv8 and E^2=E2∪Ev8, where Ev8=v7,v8 and Vv8=VEv8\v8=v7.Now, for expanded subtreeT^q, q=1,2, Step 2 determines the set of local optimal candidate points. For T^1, Sub-Step  2.1 builds set L^1 that consists of Pvi,vj in T^1 such that dvi,vj≤80 and fvi,vj>0; that is, L^1=Pv1,v2,Pv1,v3,Pv2,v3,Pv3,v4,Pv3,v6,Pv4,v5, Pv4,v7. By using Expression (11), Sub-Step  2.2 establishes CP1, which refers to the set of candidate points of the refueling subtrees corresponding to the paths in L^1. For Pv2,v3, since CSVv2,v3=v2,v3, α×100% of traffic flow in Pv2,v3 can select the deviation option that starts from v2 or v3. By applying the Cycle Returning Point Algorithm to v2 and v3, three cycle returning points, r1,  r2, and r3, are obtained such that r1∈CRPv2,v3;v2 and r2,r3∈CRPv2,v3;v3. Thus, RSTv2,v3, consisting of RSv2,v3, SCv2,v3;v2,r1, SCv2,v3;v3,r2, and SCv2,v3;v3,r3, has seven candidate points c2,3k, for k=1,…,7, such that c2,31,c2,32∈EPv2,v3, c2,33,c2,34∈CSVv2,v3, c2,35∈CRPv2,v3;v2, and c2,36,c2,37∈CRPv2,v3;v3. Note that there are no cycle starting vertices in any path Pvi,vj∈L^1\Pv2,v3; that is, the deviation option is not available. Thus, RSTvi,vj=RSvi,vj, and each RSTvi,vj has one or two candidate points depending on the value of dvi,vj. Then, CP1 includes eighteen candidate points, that is, CP1=c1,21,c1,22,c1,31,c2,31,c2,32,c2,33,c2,34,c2,35,c2,36,c2,37,c3,41,c3,42,c3,61,c3,62, c4,51,c4,52,c4,71,c4,72. Figure 3(a) illustrates the locations of RSvi,vj, SCvi,vj;vs,r, and the corresponding c∈CP1 in T^1, for Pvi,vj∈L^1, vs∈CSVvi,vj, r∈CRPvi,vj;vs. For c∈CP1, Sub-Step  2.3 constructs S(c) and SD(c) to identify all positive traffic flows covered by c. The left and middle sides of Table 4 summarize the results. Based on the paths covered by each candidate point c∈CP1, Sub-Step  2.4 first calculates Fc, for c∈CP1. The right side of this table shows the calculation processes. Sub-Step  2.4 next compares Fc, for c∈CP1, and determines the local optimal set of candidate points CP1∗ in T^1, for 0≤α≤1, as follows:(18)CP1∗=arg⁡max⁡Fc1,21,Fc1,22,Fc1,31,Fc2,31,Fc2,32,Fc2,33,Fc2,34,Fc2,35,c2,36,Fc2,37,Fc3,41,Fc3,42,Fc3,61,Fc3,62,Fc4,51,Fc4,52,Fc4,71,Fc4,72=arg⁡max⁡80,120+70α,120+70α,70,70,70,70,120+70α,70α,70α,90,90,50,50,100,100,155,155=c1,22,c1,31,c2,35,c4,71,c4,72.This result implies that if α≥0.5, then c1,22,  c1,31, and c2,35 are the local optimal locations to T^1; otherwise, c4,71 and c4,72 are the local optimal locations that cover the maximum traffic flow (in round trips per time unit) in T^1.Table 4
Sets of paths and the traffic flows (in round trips per time unit) covered byc∈CP1 in T^1.
c
S
(
c
)
S
D
c
F
c
c
1,2
1
S
c
1,2
1
=
P
v
1
,
v
2
S
D
c
1,2
1
=
∅
F
c
1,2
1
=
f
v
1
,
v
2
=
80
c
1,2
2
S
c
1,2
2
=
P
v
1
,
v
2
,
P
v
1
,
v
3
S
D
c
1,2
2
=
P
v
2
,
v
3
F
c
1,2
2
=
f
v
1
,
v
2
+
f
v
1
,
v
3
+
α
f
v
2
,
v
3
=
120
+
70
α
c
1,3
1
S
c
1,3
1
=
P
v
1
,
v
2
,
P
v
1
,
v
3
S
D
c
1,3
1
=
P
v
2
,
v
3
F
c
1,3
1
=
f
v
1
,
v
2
+
f
v
1
,
v
3
+
α
f
v
2
,
v
3
=
120
+
70
α
c
2,3
1
S
c
2,3
1
=
P
v
2
,
v
3
S
D
c
2,3
1
=
∅
F
c
2,3
1
=
f
v
2
,
v
3
=
70
c
2,3
2
S
c
2,3
2
=
P
v
2
,
v
3
S
D
c
2,3
2
=
∅
F
c
2,3
2
=
f
v
2
,
v
3
=
70
c
2,3
3
S
c
2,3
3
=
P
v
2
,
v
3
S
D
c
2,3
3
=
∅
F
c
2,3
3
=
f
v
2
,
v
3
=
70
c
2,3
4
S
c
2,3
4
=
P
v
2
,
v
3
S
D
c
2,3
4
=
∅
F
c
2,3
4
=
f
v
2
,
v
3
=
70
c
2,3
5
S
c
2,3
5
=
P
v
1
,
v
2
,
P
v
1
,
v
3
S
D
c
2,3
5
=
P
v
2
,
v
3
F
c
2,3
5
=
f
v
1
,
v
2
+
f
v
1
,
v
3
+
α
f
v
2
,
v
3
=
120
+
70
α
c
2,3
6
S
c
2,3
6
=
∅
S
D
c
2,3
6
=
P
v
2
,
v
3
F
c
2,3
6
=
α
×
f
v
2
,
v
3
=
70
α
c
2,3
7
S
c
2,3
7
=
∅
S
D
c
2,3
7
=
P
v
2
,
v
3
F
c
2,3
7
=
α
×
f
v
2
,
v
3
=
70
α
c
3,4
1
S
c
3,4
1
=
P
v
3
,
v
4
S
D
c
3,4
1
=
∅
F
c
3,4
1
=
f
v
3
,
v
4
=
90
c
3,4
2
S
c
3,4
2
=
P
v
3
,
v
4
S
D
c
3,4
2
=
∅
F
c
3,4
2
=
f
v
3
,
v
4
=
90
c
3,6
1
S
c
3,6
1
=
P
v
3
,
v
6
S
D
c
3,6
1
=
∅
F
c
3,6
1
=
f
v
3
,
v
6
=
50
c
3,6
2
S
c
3,6
2
=
P
v
3
,
v
6
S
D
c
3,6
2
=
∅
F
c
3,6
2
=
f
v
3
,
v
6
=
50
c
4,5
1
S
c
4,5
1
=
P
v
4
,
v
5
S
D
c
4,5
1
=
∅
F
c
4,5
1
=
f
v
4
,
v
5
=
100
c
4,5
2
S
c
4,5
2
=
P
v
4
,
v
5
S
D
c
4,5
2
=
∅
F
c
4,5
2
=
f
v
4
,
v
5
=
100
c
4,7
1
S
c
4,7
1
=
P
v
4
,
v
7
S
D
c
4,7
1
=
∅
F
c
4,7
1
=
f
v
4
,
v
7
=
155
c
4,7
2
S
c
4,7
2
=
P
v
4
,
v
7
S
D
c
4,7
2
=
∅
F
c
4,7
2
=
f
v
4
,
v
7
=
155Figure 3
Refueling segments, symmetric cycles, and candidate points inT^1 and T^2.
(a)
(b)Similarly, Step2 is repeated for T^2. Sub-Step  2.1 constructs L^2=Pv8,v9,Pv10,v11. Sub-Step  2.2 generates EPv8,v9 = v8,v9, EPv10,v11 = v10,v11, CSVv8,v9 = v8, CSVv10,v11 = v10, CRPv8,v9;v8=r1,r2, and CRPv10,v11;v10 = r3, where r1, r2, and r3 are the three cycle returning points obtained by the Cycle Returning Point Algorithm. Then, by Expression (11), CP2=c8,91,c8,92,c8,93,c8,94,c8,95,c10,111,c10,112,c10,113,c10,114. Figure 3(b) graphically shows the locations of RSvi,vj, SCvi,vj;vs,r, and the corresponding c∈CP2 in T^2, for Pvi,vj∈L^2, vs∈CSVvi,vj, r∈CRPvi,vj;vs. For c∈CP2, Sub-Step  2.3 determines S(c) and SD(c). They are summarized in the left and middle sides of Table 5. Next, Sub-Step  2.4 first computes Fc, for c∈CP2. The calculations are summarized in the right side of the table. Sub-Step  2.4 then compares Fc, for c∈CP2, and identifies the local optimal set of candidate points CP2∗ in T^2, for 0≤α≤1, as follows:(19)CP2∗=arg⁡max⁡Fc8,91,Fc8,92,Fc8,93,Fc8,94,Fc8,95,Fc10,111,Fc10,112,Fc10,113,Fc10,114=arg⁡max⁡140,140,140,220α,140α,80,80,80,220α=c8,91,c8,92,c8,93,c8,94,c10,114.This means that if α≥0.64, then c8,94 and c10,114 are local optimal candidate points in T^2; otherwise, c8,91, c8,92, and c8,93 become local optimal to T^2.Table 5
Sets of paths and the traffic flows (in round trips per time unit) covered byc∈CP2 in T^2.
c
S
(
c
)
S
D
c
F
c
c
8,9
1
S
c
8,9
1
=
P
v
8
,
v
9
S
D
c
8,9
1
=
∅
F
c
8,9
1
=
f
v
8
,
v
9
=
140
c
8,9
2
S
c
8,9
2
=
P
v
8
,
v
9
S
D
c
8,9
2
=
∅
F
c
8,9
2
=
f
v
8
,
v
9
=
140
c
8,9
3
S
c
8,9
3
=
P
v
8
,
v
9
S
D
c
8,9
3
=
∅
F
c
8,9
3
=
f
v
8
,
v
9
=
140
c
8,9
4
S
c
8,9
4
=
∅
S
D
c
8,9
4
=
P
v
8
,
v
9
,
P
v
10
,
v
11
F
c
8,9
4
=
α
f
v
8
,
v
9
+
f
v
10
,
v
11
=
220
α
c
8,9
5
S
c
8,9
5
=
∅
S
D
c
8,9
5
=
P
v
8
,
v
9
F
c
8,9
5
=
α
×
f
v
8
,
v
9
=
140
α
c
10,11
1
S
c
10,11
1
=
P
v
10
,
v
11
S
D
c
10,11
1
=
∅
F
c
10,11
1
=
f
v
10
,
v
11
=
80
c
10,11
2
S
c
10,11
2
=
P
v
10
,
v
11
S
D
c
10,11
2
=
∅
F
c
10,11
2
=
f
v
10
,
v
11
=
80
c
10,11
3
S
c
10,11
3
=
P
v
10
,
v
11
S
D
c
10,11
3
=
∅
F
c
10,11
3
=
f
v
10
,
v
11
=
80
c
10,11
4
S
c
10,11
4
=
∅
S
D
c
10,11
4
=
P
v
8
,
v
9
,
P
v
10
,
v
11
F
c
10,11
4
=
α
f
v
8
,
v
9
+
f
v
10
,
v
11
=
220
αFinally, by comparingFx1∗, for x1∗∈CP1∗, and Fx2∗, for x2∗∈CP2∗, Step 3 derives the global optimal set of candidate points CP∗ for the original tree T that covers the maximum traffic flow in round trips per time unit F∗:(20)CP∗=arg⁡max⁡Fx1∗,Fx2∗∣x1∗∈CP1∗,x2∗∈CP2∗=arg⁡max⁡Fc1,22,Fc1,31,Fc2,35,Fc4,71,Fc4,72,Fc8,91,Fc8,92,Fc8,93,Fc8,94,Fc10,114=arg⁡max⁡120+70α,120+70α,120+70α,155,155,140,140,140,220α,220α=c1,22,c1,31,c2,35,c4,71,c4,72,c8,94,c10,114.The set of optimal candidate pointsCP∗ changes as the deviation portion α varies between 0 and 1. When 0≤α<0.5, the two candidate points in CP∗=c4,71,c4,72 are optimal locations in tree T covering a traffic flow of 155 round trips per time unit. Since c4,71 and c4,72 are consecutive optimal candidate points satisfying the conditions of Theorem 8, all interior points between c4,71 and c4,72 are also optimal, and therefore, the complete set of optimal solutions CS∗=lc4,71,c4,72. If 0.5≤α<0.8, the three candidate points in CP∗=c1,22,c1,31,c2,35 are optimal locations with a traffic flow coverage of 155 to 176 round trips per time unit depending on α. Since these three optimal candidate points are located in the same spot, CS∗=c1,22,c1,31,c2,35. Lastly, if 0.8≤α≤1, the two candidate points in CP∗=c8,94,c10,114 are optimal solutions with a traffic flow coverage of 176 to 220 round trips per time unit. Since c8,94 and c10,114 are located in the same spot, CS∗=c8,94,c10,114. Figure 4 illustrates the change of the optimal solutions in tree T as the value of α changes from 0 to 1.Figure 4
Change of the optimal solutions for treeT as deviation portion α changes.


### 7.2. Sensitivity Analysis for Coupled Effects of Deviation Portion and Vehicle Driving Range

In this subsection, we analyze the coupled effects of deviation portion and vehicle driving range on the set of optimal locations and the maximum traffic flow covered in treeT. The actual deviation portion α, which refers to the portion of drivers willing to deviate from their preplanned paths for refueling service per time unit, is difficult to obtain or likely to be inaccurately estimated. Thus, the values of α used in this analysis range from 0 to 1. The vehicle driving range R, which depends on the fuel consumption, is expected to increase substantially with improving technologies [33]. To reflect about this point, the values of R used in this subsection range from R=40 to R=120, which are ±50% of the value of R=80 used in the previous subsection, in increments of 20.The first and last three columns of Table6 show the complete set of optimal solutions CS∗ and corresponding traffic flow covered F∗ (in round trips per time unit) for five different vehicle driving ranges (R=40, R=60, R=80, R=100, and R=120) and deviation portions between 0 and 1 for the proposed solution approach. In addition, Figure 5 displays the trade-off between deviation portion α and maximum traffic flow covered F∗ for the five different vehicle driving ranges. From these results, we first notice that the maximum traffic flow covered F∗ increases or at least stays the same as the deviation portion α increases for a given vehicle driving range. For example, when the vehicle driving range is fixed to R=80, F∗=155 as α increases from 0 to 0.5; then F∗ increases from 155 to 220 round trips per time unit as α increases from 0.5 to 1. Note also that the value of F∗ increases or stays the same as the vehicle driving range R increases for a given value of α between 0 and 1. For example, when the deviation portion is fixed to α=0.5, F∗=140 for R=40; F∗=155 for R=60 and R=80; F∗=190 for R=100; F∗=435 for R=120.Table 6
Optimal locations and the corresponding traffic flows covered for each vehicle driving range (and deviation portion combination) for three models.
Vehicle driving range (R)
DFRLM [20]
Ventura et al. [18] algorithm
Proposed solution approach
Complete set of optimal solutions (vertices)
Traffic flow covered (F∗)
Complete set of optimal solutionsCS∗
Traffic flow covered (F∗)
Deviation portion (α)
Complete set of optimal solutionsCS∗
Traffic flow covered (F∗)
40
{
v
8, v9}
140
l
c
1
,
c
2
140
0.00
≤
α
<
1.00
l
c
1
,
c
2
140
α
=
1
l
c
1
,
c
2
∪
l
c
1
,
c
3
∪
l
c
1
,
c
4
140
60
{
v
8, v9}
140
c
5
155
0.00
≤
α
≤
1.00
c
5
155
80
{
v
8, v9}
140
l
c
6
,
c
7
155
0.00
≤
α
<
0.50
l
c
6
,
c
7
155
0.50
≤
α
<
0.80
c
8
120
+
70
α
0.80
≤
α
≤
1.00
c
13
220
α
100
{
v
2
}
190
c
11
190
0.00
≤
α
<
0.57
c
11
190
0.57
≤
α
<
1.00
c
12
150
+
70
α
α
=
1
c
12
∪
l
c
9
,
c
10
220
120
{
v
4
}
435
c
14
435
0.00
≤
α
≤
1.00
c
14
435
Note. The locations of candidate points in the complete set of optimal solutions CS∗ are shown in Figure 6.Figure 5
Trade-off between deviation portion and maximum traffic flow covered for the five different vehicle driving ranges (R=40, R=60, R=80, R=100, and R=120).Figure6 graphically presents the locations of the optimal candidate points listed in Table 6. It can be observed that when the maximum traffic flow covered F∗ stays the same, the complete set of optimal solutions CS∗ may expand as the deviation portion α increases and the vehicle driving range R remains constant. For example, when R=40 and α increases from 0 to 1, the maximum traffic flow covered F∗ stays at 140 round trips per time unit, but CS∗ is expanded from lc1,c2, for 0≤α<1, to lc1,c2∪lc1,c3∪lc1,c4, for α=1. Similarly, while F∗ remains constant, CS∗ may enlarge as R increases and α stays the same. For example, given that 0≤α<0.5, as R increases from 60 to 80, F∗ stays at 155 round trips per time unit, but CS∗ is expanded from one candidate point c5 to line segment lc6,c7 including c5.Figure 6
Locations of the optimal candidate points listed in Table6.


### 7.3. Performance Analysis

In this subsection, the optimal solution of the proposed procedure is compared with those of the DFRLM [20] and the Ventura et al. [18] algorithm using the example in this section. The three approaches consider the same objective function, that is, maximizing the total traffic flow covered by the station, but have different assumptions. The main distinctions among these three models can be summarized briefly. First, the DFRLM, like most models published in the literature, assumes that the set of candidate sites is the set of vertices of the network. Therefore, the DFRLM is able to find deviation paths only if such vertices can be reached within the remaining driving range of vehicles. On the other hand, Ventura et al. [18] consider that the station can be located anywhere along the network, but vehicle deviations are not allowed. Lastly, the proposed approach considers the continuous version of the problem and allows vehicle deviations. Table 2 provides a detailed comparison of these three methodologies, including their computational complexity. In spite of the different computational requirements, since the size of the network in this example is small, the three solution approaches solve the example problem very quickly.The first column of Table6 shows the five values of R that are considered. The optimal locations and corresponding traffic flow covered F∗ (in round trips per time unit) for the DFRLM are shown in columns 2 and 3 and for Ventura et al. [18] algorithm are provided in columns 4 and 5. The last three columns include the results of the proposed solution approach as explained in Section 7.2. Figure 7 displays the coupled effects of vehicle driving range and deviation portion on the maximum traffic flow F∗ for the three models: DFRLM, Ventura et al. algorithm, and proposed approach.Figure 7
Coupled effects of vehicle driving range and deviation portion on the maximum traffic flow covered for the three models (DFRLM, Ventura et al. algorithm, and the proposed solution approach).The comparison among the three studies in Table6 and Figure 7 verifies that the proposed solution approach performs better than the other two studies in terms of maximum traffic flow covered and set of optimal locations. First, Figure 7 shows that the maximum traffic flow covered F∗ of the proposed approach is always higher than or equal to those of the other two models for all values of R. For example, when R=80, the proposed approach with α=1.00 finds the optimal locations covering 220 round trips (per time unit), which is 57% and 42% higher than the round trips covered at the suboptimal locations found using the DFRLM and Ventura et al. algorithm, respectively. Next, Table 6 also demonstrates that when all three models find the same value of F∗, the proposed approach may be able to detect more optimal locations than the other two models. For example, when R=40, F∗=140 for all three models, but the set of optimal locations found by the proposed approach, which is CS∗=lc1,c2∪lc1,c3∪lc1,c4, includes the two optimal locations, v8,v9, found by the FRLM and the set of optimal locations, lc1,c2, found by the Ventura et al. algorithm.An interesting point is that the DFRLM fails to find any deviation paths in this example, while the proposed approach finds six deviation paths from simple pathsPv2,v3, Pv8,v9, and Pv10,v11, as shown in Figure 3. In this example, no vertices from these simple paths are reachable within the remaining driving range of vehicles; thus, the DFRLM cannot find any feasible deviation path. On the other hand, the proposed approach explores every point along detour edges in polynomial time, so it finds all possible deviation paths in the network regardless of the location of vertices on detours.


## 7.1. Numerical Example for a Given Vehicle Driving Range

In this subsection, we fix the driving rangeR=80 and solve the numerical example to illustrate the Deviation-Flow Optimal Candidate Point Algorithm in detail.To construct the expanded subtrees fromT in Step 1, Sub-Step  1.1 finds dv7,v8>R; thus, E^=v7,v8. By removing v7,v8 from T, Sub-Step  1.2 forms forest FVF,EF containing two subtrees T1V1,E1 and T2V2,E2, where V1=v1,v2,v3,v4,v5,v6,v7, E1=v1,v2,v2,v3,v3,v4,v4,v5,v3,v6,v4,v7, V2=v8,v9,v10,v11, and E2=v8,v9,v8,v10,v10,v11. For T1, Sub-Step  1.3 sets V-1=∅ and generates V1′=VE^∩V1=v7. For vk∈V1′, even if α>0, there is no α×fvi,vj>0, for vi,vj∈V1, such that max⁡dvi,vk,dvj,vk<R/2. Thus, V-1 remains empty, and expanded subtree T^1V^1,E^1 = T1V1,E1. For T2, Sub-Step  1.3 sets V-2=∅ and forms V2′=VE^∩V2=v8. For vk∈V2′, if α>0, there exists α×fv8,v9>0, such that max⁡dv8,vk,dv9,vk = 15 <R/2. Thus, v8 is added to V-2, and expanded subtree T^2V^2,E^2 is such that V^2=V2∪Vv8 and E^2=E2∪Ev8, where Ev8=v7,v8 and Vv8=VEv8\v8=v7.Now, for expanded subtreeT^q, q=1,2, Step 2 determines the set of local optimal candidate points. For T^1, Sub-Step  2.1 builds set L^1 that consists of Pvi,vj in T^1 such that dvi,vj≤80 and fvi,vj>0; that is, L^1=Pv1,v2,Pv1,v3,Pv2,v3,Pv3,v4,Pv3,v6,Pv4,v5, Pv4,v7. By using Expression (11), Sub-Step  2.2 establishes CP1, which refers to the set of candidate points of the refueling subtrees corresponding to the paths in L^1. For Pv2,v3, since CSVv2,v3=v2,v3, α×100% of traffic flow in Pv2,v3 can select the deviation option that starts from v2 or v3. By applying the Cycle Returning Point Algorithm to v2 and v3, three cycle returning points, r1,  r2, and r3, are obtained such that r1∈CRPv2,v3;v2 and r2,r3∈CRPv2,v3;v3. Thus, RSTv2,v3, consisting of RSv2,v3, SCv2,v3;v2,r1, SCv2,v3;v3,r2, and SCv2,v3;v3,r3, has seven candidate points c2,3k, for k=1,…,7, such that c2,31,c2,32∈EPv2,v3, c2,33,c2,34∈CSVv2,v3, c2,35∈CRPv2,v3;v2, and c2,36,c2,37∈CRPv2,v3;v3. Note that there are no cycle starting vertices in any path Pvi,vj∈L^1\Pv2,v3; that is, the deviation option is not available. Thus, RSTvi,vj=RSvi,vj, and each RSTvi,vj has one or two candidate points depending on the value of dvi,vj. Then, CP1 includes eighteen candidate points, that is, CP1=c1,21,c1,22,c1,31,c2,31,c2,32,c2,33,c2,34,c2,35,c2,36,c2,37,c3,41,c3,42,c3,61,c3,62, c4,51,c4,52,c4,71,c4,72. Figure 3(a) illustrates the locations of RSvi,vj, SCvi,vj;vs,r, and the corresponding c∈CP1 in T^1, for Pvi,vj∈L^1, vs∈CSVvi,vj, r∈CRPvi,vj;vs. For c∈CP1, Sub-Step  2.3 constructs S(c) and SD(c) to identify all positive traffic flows covered by c. The left and middle sides of Table 4 summarize the results. Based on the paths covered by each candidate point c∈CP1, Sub-Step  2.4 first calculates Fc, for c∈CP1. The right side of this table shows the calculation processes. Sub-Step  2.4 next compares Fc, for c∈CP1, and determines the local optimal set of candidate points CP1∗ in T^1, for 0≤α≤1, as follows:(18)CP1∗=arg⁡max⁡Fc1,21,Fc1,22,Fc1,31,Fc2,31,Fc2,32,Fc2,33,Fc2,34,Fc2,35,c2,36,Fc2,37,Fc3,41,Fc3,42,Fc3,61,Fc3,62,Fc4,51,Fc4,52,Fc4,71,Fc4,72=arg⁡max⁡80,120+70α,120+70α,70,70,70,70,120+70α,70α,70α,90,90,50,50,100,100,155,155=c1,22,c1,31,c2,35,c4,71,c4,72.This result implies that if α≥0.5, then c1,22,  c1,31, and c2,35 are the local optimal locations to T^1; otherwise, c4,71 and c4,72 are the local optimal locations that cover the maximum traffic flow (in round trips per time unit) in T^1.Table 4
Sets of paths and the traffic flows (in round trips per time unit) covered byc∈CP1 in T^1.
c
S
(
c
)
S
D
c
F
c
c
1,2
1
S
c
1,2
1
=
P
v
1
,
v
2
S
D
c
1,2
1
=
∅
F
c
1,2
1
=
f
v
1
,
v
2
=
80
c
1,2
2
S
c
1,2
2
=
P
v
1
,
v
2
,
P
v
1
,
v
3
S
D
c
1,2
2
=
P
v
2
,
v
3
F
c
1,2
2
=
f
v
1
,
v
2
+
f
v
1
,
v
3
+
α
f
v
2
,
v
3
=
120
+
70
α
c
1,3
1
S
c
1,3
1
=
P
v
1
,
v
2
,
P
v
1
,
v
3
S
D
c
1,3
1
=
P
v
2
,
v
3
F
c
1,3
1
=
f
v
1
,
v
2
+
f
v
1
,
v
3
+
α
f
v
2
,
v
3
=
120
+
70
α
c
2,3
1
S
c
2,3
1
=
P
v
2
,
v
3
S
D
c
2,3
1
=
∅
F
c
2,3
1
=
f
v
2
,
v
3
=
70
c
2,3
2
S
c
2,3
2
=
P
v
2
,
v
3
S
D
c
2,3
2
=
∅
F
c
2,3
2
=
f
v
2
,
v
3
=
70
c
2,3
3
S
c
2,3
3
=
P
v
2
,
v
3
S
D
c
2,3
3
=
∅
F
c
2,3
3
=
f
v
2
,
v
3
=
70
c
2,3
4
S
c
2,3
4
=
P
v
2
,
v
3
S
D
c
2,3
4
=
∅
F
c
2,3
4
=
f
v
2
,
v
3
=
70
c
2,3
5
S
c
2,3
5
=
P
v
1
,
v
2
,
P
v
1
,
v
3
S
D
c
2,3
5
=
P
v
2
,
v
3
F
c
2,3
5
=
f
v
1
,
v
2
+
f
v
1
,
v
3
+
α
f
v
2
,
v
3
=
120
+
70
α
c
2,3
6
S
c
2,3
6
=
∅
S
D
c
2,3
6
=
P
v
2
,
v
3
F
c
2,3
6
=
α
×
f
v
2
,
v
3
=
70
α
c
2,3
7
S
c
2,3
7
=
∅
S
D
c
2,3
7
=
P
v
2
,
v
3
F
c
2,3
7
=
α
×
f
v
2
,
v
3
=
70
α
c
3,4
1
S
c
3,4
1
=
P
v
3
,
v
4
S
D
c
3,4
1
=
∅
F
c
3,4
1
=
f
v
3
,
v
4
=
90
c
3,4
2
S
c
3,4
2
=
P
v
3
,
v
4
S
D
c
3,4
2
=
∅
F
c
3,4
2
=
f
v
3
,
v
4
=
90
c
3,6
1
S
c
3,6
1
=
P
v
3
,
v
6
S
D
c
3,6
1
=
∅
F
c
3,6
1
=
f
v
3
,
v
6
=
50
c
3,6
2
S
c
3,6
2
=
P
v
3
,
v
6
S
D
c
3,6
2
=
∅
F
c
3,6
2
=
f
v
3
,
v
6
=
50
c
4,5
1
S
c
4,5
1
=
P
v
4
,
v
5
S
D
c
4,5
1
=
∅
F
c
4,5
1
=
f
v
4
,
v
5
=
100
c
4,5
2
S
c
4,5
2
=
P
v
4
,
v
5
S
D
c
4,5
2
=
∅
F
c
4,5
2
=
f
v
4
,
v
5
=
100
c
4,7
1
S
c
4,7
1
=
P
v
4
,
v
7
S
D
c
4,7
1
=
∅
F
c
4,7
1
=
f
v
4
,
v
7
=
155
c
4,7
2
S
c
4,7
2
=
P
v
4
,
v
7
S
D
c
4,7
2
=
∅
F
c
4,7
2
=
f
v
4
,
v
7
=
155Figure 3
Refueling segments, symmetric cycles, and candidate points inT^1 and T^2.
(a)
(b)Similarly, Step2 is repeated for T^2. Sub-Step  2.1 constructs L^2=Pv8,v9,Pv10,v11. Sub-Step  2.2 generates EPv8,v9 = v8,v9, EPv10,v11 = v10,v11, CSVv8,v9 = v8, CSVv10,v11 = v10, CRPv8,v9;v8=r1,r2, and CRPv10,v11;v10 = r3, where r1, r2, and r3 are the three cycle returning points obtained by the Cycle Returning Point Algorithm. Then, by Expression (11), CP2=c8,91,c8,92,c8,93,c8,94,c8,95,c10,111,c10,112,c10,113,c10,114. Figure 3(b) graphically shows the locations of RSvi,vj, SCvi,vj;vs,r, and the corresponding c∈CP2 in T^2, for Pvi,vj∈L^2, vs∈CSVvi,vj, r∈CRPvi,vj;vs. For c∈CP2, Sub-Step  2.3 determines S(c) and SD(c). They are summarized in the left and middle sides of Table 5. Next, Sub-Step  2.4 first computes Fc, for c∈CP2. The calculations are summarized in the right side of the table. Sub-Step  2.4 then compares Fc, for c∈CP2, and identifies the local optimal set of candidate points CP2∗ in T^2, for 0≤α≤1, as follows:(19)CP2∗=arg⁡max⁡Fc8,91,Fc8,92,Fc8,93,Fc8,94,Fc8,95,Fc10,111,Fc10,112,Fc10,113,Fc10,114=arg⁡max⁡140,140,140,220α,140α,80,80,80,220α=c8,91,c8,92,c8,93,c8,94,c10,114.This means that if α≥0.64, then c8,94 and c10,114 are local optimal candidate points in T^2; otherwise, c8,91, c8,92, and c8,93 become local optimal to T^2.Table 5
Sets of paths and the traffic flows (in round trips per time unit) covered byc∈CP2 in T^2.
c
S
(
c
)
S
D
c
F
c
c
8,9
1
S
c
8,9
1
=
P
v
8
,
v
9
S
D
c
8,9
1
=
∅
F
c
8,9
1
=
f
v
8
,
v
9
=
140
c
8,9
2
S
c
8,9
2
=
P
v
8
,
v
9
S
D
c
8,9
2
=
∅
F
c
8,9
2
=
f
v
8
,
v
9
=
140
c
8,9
3
S
c
8,9
3
=
P
v
8
,
v
9
S
D
c
8,9
3
=
∅
F
c
8,9
3
=
f
v
8
,
v
9
=
140
c
8,9
4
S
c
8,9
4
=
∅
S
D
c
8,9
4
=
P
v
8
,
v
9
,
P
v
10
,
v
11
F
c
8,9
4
=
α
f
v
8
,
v
9
+
f
v
10
,
v
11
=
220
α
c
8,9
5
S
c
8,9
5
=
∅
S
D
c
8,9
5
=
P
v
8
,
v
9
F
c
8,9
5
=
α
×
f
v
8
,
v
9
=
140
α
c
10,11
1
S
c
10,11
1
=
P
v
10
,
v
11
S
D
c
10,11
1
=
∅
F
c
10,11
1
=
f
v
10
,
v
11
=
80
c
10,11
2
S
c
10,11
2
=
P
v
10
,
v
11
S
D
c
10,11
2
=
∅
F
c
10,11
2
=
f
v
10
,
v
11
=
80
c
10,11
3
S
c
10,11
3
=
P
v
10
,
v
11
S
D
c
10,11
3
=
∅
F
c
10,11
3
=
f
v
10
,
v
11
=
80
c
10,11
4
S
c
10,11
4
=
∅
S
D
c
10,11
4
=
P
v
8
,
v
9
,
P
v
10
,
v
11
F
c
10,11
4
=
α
f
v
8
,
v
9
+
f
v
10
,
v
11
=
220
αFinally, by comparingFx1∗, for x1∗∈CP1∗, and Fx2∗, for x2∗∈CP2∗, Step 3 derives the global optimal set of candidate points CP∗ for the original tree T that covers the maximum traffic flow in round trips per time unit F∗:(20)CP∗=arg⁡max⁡Fx1∗,Fx2∗∣x1∗∈CP1∗,x2∗∈CP2∗=arg⁡max⁡Fc1,22,Fc1,31,Fc2,35,Fc4,71,Fc4,72,Fc8,91,Fc8,92,Fc8,93,Fc8,94,Fc10,114=arg⁡max⁡120+70α,120+70α,120+70α,155,155,140,140,140,220α,220α=c1,22,c1,31,c2,35,c4,71,c4,72,c8,94,c10,114.The set of optimal candidate pointsCP∗ changes as the deviation portion α varies between 0 and 1. When 0≤α<0.5, the two candidate points in CP∗=c4,71,c4,72 are optimal locations in tree T covering a traffic flow of 155 round trips per time unit. Since c4,71 and c4,72 are consecutive optimal candidate points satisfying the conditions of Theorem 8, all interior points between c4,71 and c4,72 are also optimal, and therefore, the complete set of optimal solutions CS∗=lc4,71,c4,72. If 0.5≤α<0.8, the three candidate points in CP∗=c1,22,c1,31,c2,35 are optimal locations with a traffic flow coverage of 155 to 176 round trips per time unit depending on α. Since these three optimal candidate points are located in the same spot, CS∗=c1,22,c1,31,c2,35. Lastly, if 0.8≤α≤1, the two candidate points in CP∗=c8,94,c10,114 are optimal solutions with a traffic flow coverage of 176 to 220 round trips per time unit. Since c8,94 and c10,114 are located in the same spot, CS∗=c8,94,c10,114. Figure 4 illustrates the change of the optimal solutions in tree T as the value of α changes from 0 to 1.Figure 4
Change of the optimal solutions for treeT as deviation portion α changes.


## 7.2. Sensitivity Analysis for Coupled Effects of Deviation Portion and Vehicle Driving Range

In this subsection, we analyze the coupled effects of deviation portion and vehicle driving range on the set of optimal locations and the maximum traffic flow covered in treeT. The actual deviation portion α, which refers to the portion of drivers willing to deviate from their preplanned paths for refueling service per time unit, is difficult to obtain or likely to be inaccurately estimated. Thus, the values of α used in this analysis range from 0 to 1. The vehicle driving range R, which depends on the fuel consumption, is expected to increase substantially with improving technologies [33]. To reflect about this point, the values of R used in this subsection range from R=40 to R=120, which are ±50% of the value of R=80 used in the previous subsection, in increments of 20.The first and last three columns of Table6 show the complete set of optimal solutions CS∗ and corresponding traffic flow covered F∗ (in round trips per time unit) for five different vehicle driving ranges (R=40, R=60, R=80, R=100, and R=120) and deviation portions between 0 and 1 for the proposed solution approach. In addition, Figure 5 displays the trade-off between deviation portion α and maximum traffic flow covered F∗ for the five different vehicle driving ranges. From these results, we first notice that the maximum traffic flow covered F∗ increases or at least stays the same as the deviation portion α increases for a given vehicle driving range. For example, when the vehicle driving range is fixed to R=80, F∗=155 as α increases from 0 to 0.5; then F∗ increases from 155 to 220 round trips per time unit as α increases from 0.5 to 1. Note also that the value of F∗ increases or stays the same as the vehicle driving range R increases for a given value of α between 0 and 1. For example, when the deviation portion is fixed to α=0.5, F∗=140 for R=40; F∗=155 for R=60 and R=80; F∗=190 for R=100; F∗=435 for R=120.Table 6
Optimal locations and the corresponding traffic flows covered for each vehicle driving range (and deviation portion combination) for three models.
Vehicle driving range (R)
DFRLM [20]
Ventura et al. [18] algorithm
Proposed solution approach
Complete set of optimal solutions (vertices)
Traffic flow covered (F∗)
Complete set of optimal solutionsCS∗
Traffic flow covered (F∗)
Deviation portion (α)
Complete set of optimal solutionsCS∗
Traffic flow covered (F∗)
40
{
v
8, v9}
140
l
c
1
,
c
2
140
0.00
≤
α
<
1.00
l
c
1
,
c
2
140
α
=
1
l
c
1
,
c
2
∪
l
c
1
,
c
3
∪
l
c
1
,
c
4
140
60
{
v
8, v9}
140
c
5
155
0.00
≤
α
≤
1.00
c
5
155
80
{
v
8, v9}
140
l
c
6
,
c
7
155
0.00
≤
α
<
0.50
l
c
6
,
c
7
155
0.50
≤
α
<
0.80
c
8
120
+
70
α
0.80
≤
α
≤
1.00
c
13
220
α
100
{
v
2
}
190
c
11
190
0.00
≤
α
<
0.57
c
11
190
0.57
≤
α
<
1.00
c
12
150
+
70
α
α
=
1
c
12
∪
l
c
9
,
c
10
220
120
{
v
4
}
435
c
14
435
0.00
≤
α
≤
1.00
c
14
435
Note. The locations of candidate points in the complete set of optimal solutions CS∗ are shown in Figure 6.Figure 5
Trade-off between deviation portion and maximum traffic flow covered for the five different vehicle driving ranges (R=40, R=60, R=80, R=100, and R=120).Figure6 graphically presents the locations of the optimal candidate points listed in Table 6. It can be observed that when the maximum traffic flow covered F∗ stays the same, the complete set of optimal solutions CS∗ may expand as the deviation portion α increases and the vehicle driving range R remains constant. For example, when R=40 and α increases from 0 to 1, the maximum traffic flow covered F∗ stays at 140 round trips per time unit, but CS∗ is expanded from lc1,c2, for 0≤α<1, to lc1,c2∪lc1,c3∪lc1,c4, for α=1. Similarly, while F∗ remains constant, CS∗ may enlarge as R increases and α stays the same. For example, given that 0≤α<0.5, as R increases from 60 to 80, F∗ stays at 155 round trips per time unit, but CS∗ is expanded from one candidate point c5 to line segment lc6,c7 including c5.Figure 6
Locations of the optimal candidate points listed in Table6.


## 7.3. Performance Analysis

In this subsection, the optimal solution of the proposed procedure is compared with those of the DFRLM [20] and the Ventura et al. [18] algorithm using the example in this section. The three approaches consider the same objective function, that is, maximizing the total traffic flow covered by the station, but have different assumptions. The main distinctions among these three models can be summarized briefly. First, the DFRLM, like most models published in the literature, assumes that the set of candidate sites is the set of vertices of the network. Therefore, the DFRLM is able to find deviation paths only if such vertices can be reached within the remaining driving range of vehicles. On the other hand, Ventura et al. [18] consider that the station can be located anywhere along the network, but vehicle deviations are not allowed. Lastly, the proposed approach considers the continuous version of the problem and allows vehicle deviations. Table 2 provides a detailed comparison of these three methodologies, including their computational complexity. In spite of the different computational requirements, since the size of the network in this example is small, the three solution approaches solve the example problem very quickly.The first column of Table6 shows the five values of R that are considered. The optimal locations and corresponding traffic flow covered F∗ (in round trips per time unit) for the DFRLM are shown in columns 2 and 3 and for Ventura et al. [18] algorithm are provided in columns 4 and 5. The last three columns include the results of the proposed solution approach as explained in Section 7.2. Figure 7 displays the coupled effects of vehicle driving range and deviation portion on the maximum traffic flow F∗ for the three models: DFRLM, Ventura et al. algorithm, and proposed approach.Figure 7
Coupled effects of vehicle driving range and deviation portion on the maximum traffic flow covered for the three models (DFRLM, Ventura et al. algorithm, and the proposed solution approach).The comparison among the three studies in Table6 and Figure 7 verifies that the proposed solution approach performs better than the other two studies in terms of maximum traffic flow covered and set of optimal locations. First, Figure 7 shows that the maximum traffic flow covered F∗ of the proposed approach is always higher than or equal to those of the other two models for all values of R. For example, when R=80, the proposed approach with α=1.00 finds the optimal locations covering 220 round trips (per time unit), which is 57% and 42% higher than the round trips covered at the suboptimal locations found using the DFRLM and Ventura et al. algorithm, respectively. Next, Table 6 also demonstrates that when all three models find the same value of F∗, the proposed approach may be able to detect more optimal locations than the other two models. For example, when R=40, F∗=140 for all three models, but the set of optimal locations found by the proposed approach, which is CS∗=lc1,c2∪lc1,c3∪lc1,c4, includes the two optimal locations, v8,v9, found by the FRLM and the set of optimal locations, lc1,c2, found by the Ventura et al. algorithm.An interesting point is that the DFRLM fails to find any deviation paths in this example, while the proposed approach finds six deviation paths from simple pathsPv2,v3, Pv8,v9, and Pv10,v11, as shown in Figure 3. In this example, no vertices from these simple paths are reachable within the remaining driving range of vehicles; thus, the DFRLM cannot find any feasible deviation path. On the other hand, the proposed approach explores every point along detour edges in polynomial time, so it finds all possible deviation paths in the network regardless of the location of vertices on detours.


## 8. Conclusions and Future Research

This article has studied the continuous version of an AF refueling station location problem on a tree network considering that a portion of drivers have the option to deviate from their preplanned paths to be able to refuel their vehicles. The objective of the problem is to identify the set of optimal station locations that maximize the total traffic flow covered (in round trips per time unit). To achieve this goal, we have first generated a set of subtrees from the original tree network to reduce the problem size and consider the deviation option. Next, we have identified three sets of candidate points, including endpoints of refueling segments, cycle starting vertices, and cycle returning points, to locate the refueling station. We have proved that there exists at least one optimal solution in these sets of candidate points. Then, we have developed a polynomial time algorithm to determine the set of optimal candidate points that maximizes the total traffic flow covered. Lastly, we have derived conditions under which the line segments defined by certain pairs of consecutive optimal candidate points are also optimal. Our performance analysis demonstrates that the proposed solution approach can significantly improve the suboptimality of the solutions found by the existing refueling station location models. Note that although in this study we have used a small-size numerical example to illustrate and verify the proposed solution approach step by step, this procedure can also be applied for the large-scale problems due to its polynomial time complexity.For future research we have identified three clear extensions to our solution approach. First, some of the assumptions we made in this article can be relaxed. For example, some vehicles may have different fuel tank levels at their origin and destination points, and fuel consumption may be different for some vehicles, which implies that they can have different driving ranges. We also suggest to extend the approach discussed in this article for tree networks to general networks having multiple paths between pairs of vertices. In addition, a multiobjective version of the refueling station location problem can also be considered to identify efficient locations that both maximize the total traffic flow covered by the stations and minimize construction and maintenance costs of the stations, assuming that these costs differ regionally.



---

*Source: 1705821-2017-12-14.xml*