# Vehicle Relocation Triggering Thresholds Determination in Electric Carsharing System under Stochastic Demand

Authors: Wanjing Ma; Lei Wang; Lin Li
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

Vehicle unbalance usually occurs in multistation electric carsharing systems. Threshold triggering method is one of the most practicable approaches for vehicle relocation, while determination of thresholds has not been sufficiently studied particularly for electric carsharing system. This paper presents an approach on determining the thresholds considering the stochastic demands and system states. Firstly, we establish a state transition model involving the stochastic variables to capture the dynamics of the number and battery status of vehicles as well as the traffic demands. Consequently, a dual-objective optimization model was developed to determine the proper values of thresholds. The solution algorithm employed the min–max robust optimization to tackle the uncertainty and the Pareto optimum to decide the solution under dual objectives. To test the distribution stochastic variables, we involve the orders data and the supplementary user survey. Comparison is conducted among three methods: the empirical rules, the deterministic method, and the stochastic method, where the results suggest that the stochastic method achieves better solutions on the dual objectives under stochastic demands.


---

## Body

## 1. Introduction

Carsharing mode has obtained extensive attention in either personal-vehicle-oriented or public-transit-oriented cities, including in Europe, North America [1], and some parts of Asia [2]. By 2015, there had been over 1.1 million members and 16,754 vehicles in the US since the first carsharing program launched in 1994 [3]. In China, from the emergence of carsharing services in 2009 to 2015, more than 330,000 people signed up for a carsharing membership, and about 5000 vehicles had been in operation, where half of them were electric vehicles (EV) and five of the eight organizations ran EVs and three of them were EV-only [4].Traditional carsharing models require users to pick up and return vehicles at the same station and with strictly appointed time (as roundtrip carsharing). In order to increase the accessibility, provide better mobility, attract more users, and strengthen competitiveness, carsharing organizations (CSO) introduced flexible pick-up and drop-off location and time (namely, one-way carsharing) that allows users to pick up a vehicle on demand and return it to other stations without a preconcerted arrangement. It is suggested that one-way carsharing is experiencing a rapid worldwide expansion contemporarily [5], new one-way CSOs are emerging (e.g., Car2Go and DriveNow), and existing CSOs are gradually offering one-way capability in major cities (e.g., Zipcar).However, accompanying the improvement of the flexibility, the distribution of fleets in one-way models potentially turns to be imbalanced with demands variation. The unbalance of demands and fleets makes it necessary to relocate vehicles for sustainable operation. On the other hand, the on-demand pick-up and drop-off rule also causes the preplanned relocation to be unfeasible, especially under stochastic demands, which requires the relocation mechanisms to take the randomness into account.The threshold based relocation strategy has been developed to respond to the dynamic system changes [6, 7]. The thresholds are applied to keep the number of vehicles within a proper range in each station (as shown in Figure 1(a)). This mechanism was also concluded into two major steps (as shown in Figure 1(b)): (1) The system monitors the change of the number of vehicles (the state variable) in each station. If the number of vehicles of a station accumulated above an upper threshold, tag the station as which needs moving out cars (overflowing); if the number of vehicles of a station decreased below a lower threshold, tag the station as which needs moving in cars (lacking). (2) Relocation listening: The system monitors the relocation tag of each station and decides the optimum solutions of path to move vehicles from overflowing stations to lacking stations, with the constraints of relocation staff resources.Figure 1
The threshold based relocation approach.
(a)
Thresholds to control the number of vehicles changing within a proper range (b)
Two-step threshold based relocation methodIt should be noted that the thresholds setting is a fundamental work of the threshold based relocation mechanism. To the best of our knowledge, there had been some studies based on designated thresholds, but detailed study towards thresholds determination is still needed to be extended.The main targets of this paper are as follows:(i)
To propose a quantitative method for the triggering thresholds determination(ii)
To capture the uncertainty of demands (the solutions of thresholds are decided through a “min–max” robust optimization to find the best solution in the worst condition)(iii)
To weigh both service quality and the relocation times, applying the Pareto front to find the nondominant sets for both the worst condition stochastic demand sets and the best objectives solution sets(iv)
To involve the battery and charging properties of EV as a major difference with conventional carsharing systems.The rest of the paper is structured as follows: Section2 reviews the literature concerning the carsharing vehicle relocation problem; Section 3 is the modeling of station vehicle changing and the robust optimization of thresholds under stochastic demand; Section 4 presents a solution algorithm; Section 5 presents the analysis and discussion; and the last section concludes the study.


## 2. Literature Review

### 2.1. Study on Vehicle Relocation Problems

Studies on carsharing mode generally fall into two categories: strategy planning level and operating level. Strategy level covers issues of environment and resources benefits [8, 9], market investigation [10, 11], users’ behavior [12, 13], and network design [14, 15]. Operating level problems also received attention, but studies are still not sufficient to support the industrial development, especially for one-way model, which allows users to pick up and drop off vehicles at different stations. As one major difficulty in the system operation, the fleet imbalance problem makes the study on vehicle relocation even more urgent.Vehicle relocation problem had been studied through many approaches, as what we have summarized in Table1. For some preliminary one-way carsharing systems which require users to provide reservation information, mathematical programming approaches can be adopted without many obstacles. With demands known, the problem can be formulated as mixed integer programming and efficiently solved by feasible solvers [14, 16–18].Table 1
Summary of studies on vehicle relocation of carsharing systems.
Types Approaches Representative studies Reservation-based (with demands known) Mathematical planning Nourinejad (2014), Carlier (2015), Zakaria (2014), Boyacı (2015)  On-demand / instant access (with demands unknown) Threshold based Barth (1999), Kek (2009), Cepolina (2012, 2014) Demand prediction & mathematical programming Bruglieri (2014), Repoux (2015) Rolling horizon & mathematical programming Febbraro (2012), Santos (2015) Stochastic programming Briest (2011), Nair (2011), Fan (2013)With the deeper penetration of on-demand/instant access one-way demand systems, which allow users to get access to the system without previous reservation, this policy makes the demands unknown. One approach is to predict demands then apply deterministic mathematical programming model [19, 20] or to collect short-term demands and then model with rolling horizon scheme [21, 22]. Besides optimization, a practical approach is to dynamically detect the number of available vehicles in stations and trigger relocation tactic by judgment of thresholds. This method has been regarded as an easy way to practice and enables fast implementation for carsharing operators [23].


### 2.2. Threshold Based Vehicle Relocation Problem

The concept of thresholds was firstly introduced by Barth (1999) [23], which involved a minimum threshold to judge a vehicle insufficiency condition and generate a request to relocate vehicle in. This threshold enables an intuitive vehicle relocation approach which was named as static relocation by that time. There had not been more detailed explanations on mechanism and setting of thresholds. Based on Barth’s concept, Kek et al. (2006) [6] further discussed the role of thresholds, which are defined as the upper and lower limits on the number of vehicles in a station. When thresholds are reached, there should be an operation to remove or add vehicles at the station. Kek analyzed the effects of different range of thresholds from a logical perspective but did not quantitatively model the dynamics behind the system. Kek et al. (2009) provided more thinking about thresholds and explained more details of the function of different thresholds. However, thresholds were manual settings for triggering relocation requests and were not involved in optimization variables in that study.Cepolina et al. (2012) [24] summarized existing studies intended to address the problem of vehicle relocation and categorized some of the approaches. Threshold based method was clearly organized. The authors deemed that the thresholds answer the question of where and when a relocation is required. The framework of thresholds was based on the proposal of Kek’s paper. Cepolina et al. (2014) [25] applied thresholds to help planning a new urban carsharing system with fully automated personal vehicles, where they involved thresholds as a dependent variable in their model. The solution to this model is programmed as a parallel heuristic approach, which outputs the thresholds as a side product. Note that specific study on thresholds has not been conducted yet. Cepolina et al. (2015) [26] further developed three innovative strategies for urban carsharing systems where two of them were derived from thresholds method. They refer to article [25] when explaining the setting of thresholds. This confirms that the threshold method has potential for being developed for different application scenarios, and it would be valuable to provide further study on threshold determination.Our previous work (2016) had presented a framework of threshold based relocation [27], which is based on the operating practice of EVCARD. We found that optimization methodology can hardly implement and handle operating in large scale networks and with stochastic demands, and threshold based relocation is fast practical and rather flexible to account for complex field circumstances. We model and determine the values of thresholds by a deterministic approach in the previous work. However, the randomness of demands and the property of electric vehicle are ignored at that time.The purpose of this paper is to present a quantitative justification on thresholds determination. Moreover, the uncertainty of demands and trade-off between users’ and operators’ benefits are as well considered in this research.


## 2.1. Study on Vehicle Relocation Problems

Studies on carsharing mode generally fall into two categories: strategy planning level and operating level. Strategy level covers issues of environment and resources benefits [8, 9], market investigation [10, 11], users’ behavior [12, 13], and network design [14, 15]. Operating level problems also received attention, but studies are still not sufficient to support the industrial development, especially for one-way model, which allows users to pick up and drop off vehicles at different stations. As one major difficulty in the system operation, the fleet imbalance problem makes the study on vehicle relocation even more urgent.Vehicle relocation problem had been studied through many approaches, as what we have summarized in Table1. For some preliminary one-way carsharing systems which require users to provide reservation information, mathematical programming approaches can be adopted without many obstacles. With demands known, the problem can be formulated as mixed integer programming and efficiently solved by feasible solvers [14, 16–18].Table 1
Summary of studies on vehicle relocation of carsharing systems.
Types Approaches Representative studies Reservation-based (with demands known) Mathematical planning Nourinejad (2014), Carlier (2015), Zakaria (2014), Boyacı (2015)  On-demand / instant access (with demands unknown) Threshold based Barth (1999), Kek (2009), Cepolina (2012, 2014) Demand prediction & mathematical programming Bruglieri (2014), Repoux (2015) Rolling horizon & mathematical programming Febbraro (2012), Santos (2015) Stochastic programming Briest (2011), Nair (2011), Fan (2013)With the deeper penetration of on-demand/instant access one-way demand systems, which allow users to get access to the system without previous reservation, this policy makes the demands unknown. One approach is to predict demands then apply deterministic mathematical programming model [19, 20] or to collect short-term demands and then model with rolling horizon scheme [21, 22]. Besides optimization, a practical approach is to dynamically detect the number of available vehicles in stations and trigger relocation tactic by judgment of thresholds. This method has been regarded as an easy way to practice and enables fast implementation for carsharing operators [23].


## 2.2. Threshold Based Vehicle Relocation Problem

The concept of thresholds was firstly introduced by Barth (1999) [23], which involved a minimum threshold to judge a vehicle insufficiency condition and generate a request to relocate vehicle in. This threshold enables an intuitive vehicle relocation approach which was named as static relocation by that time. There had not been more detailed explanations on mechanism and setting of thresholds. Based on Barth’s concept, Kek et al. (2006) [6] further discussed the role of thresholds, which are defined as the upper and lower limits on the number of vehicles in a station. When thresholds are reached, there should be an operation to remove or add vehicles at the station. Kek analyzed the effects of different range of thresholds from a logical perspective but did not quantitatively model the dynamics behind the system. Kek et al. (2009) provided more thinking about thresholds and explained more details of the function of different thresholds. However, thresholds were manual settings for triggering relocation requests and were not involved in optimization variables in that study.Cepolina et al. (2012) [24] summarized existing studies intended to address the problem of vehicle relocation and categorized some of the approaches. Threshold based method was clearly organized. The authors deemed that the thresholds answer the question of where and when a relocation is required. The framework of thresholds was based on the proposal of Kek’s paper. Cepolina et al. (2014) [25] applied thresholds to help planning a new urban carsharing system with fully automated personal vehicles, where they involved thresholds as a dependent variable in their model. The solution to this model is programmed as a parallel heuristic approach, which outputs the thresholds as a side product. Note that specific study on thresholds has not been conducted yet. Cepolina et al. (2015) [26] further developed three innovative strategies for urban carsharing systems where two of them were derived from thresholds method. They refer to article [25] when explaining the setting of thresholds. This confirms that the threshold method has potential for being developed for different application scenarios, and it would be valuable to provide further study on threshold determination.Our previous work (2016) had presented a framework of threshold based relocation [27], which is based on the operating practice of EVCARD. We found that optimization methodology can hardly implement and handle operating in large scale networks and with stochastic demands, and threshold based relocation is fast practical and rather flexible to account for complex field circumstances. We model and determine the values of thresholds by a deterministic approach in the previous work. However, the randomness of demands and the property of electric vehicle are ignored at that time.The purpose of this paper is to present a quantitative justification on thresholds determination. Moreover, the uncertainty of demands and trade-off between users’ and operators’ benefits are as well considered in this research.


## 3. Thresholds Determination Modeling

### 3.1. Problem Description

In each station, the number of vehicles is dynamically changing because vehicles would be picked up, dropped off, relocated in, and relocated out. For a single station, the changing range of vehicle amount depends on its own pick-ups and drop-offs, and its proper range is controlled by relocations.As for the coherence with previous relocation-related works [7, 18], in this paper, time series is also discretized into time steps of 1 hour. During a time step, the vehicles dropped off, the vehicles relocated in, and the idle vehicles are all available for picking up and relocating out according to the matching between available state of charge (SOC) of these vehicles and the required travel distance.If the number of vehicles at the station is below the lower threshold at one time step, the station requires vehicles to be relocated in. However, not all the required vehicles can be successfully moved into the station within this time step, and the exact arrivals of vehicles relocated in will endure a time-stepwise delay. For the number exceeding the upper threshold it is similar, and the exact departure of vehicles to be relocated out will also delay due to the availability of relocation staff.Users want to select the vehicle whose battery life is the most suitable for their journey, and users will abandon the system at a proportion if no suitable vehicles are available. Vehicles will be charged immediately when arriving at station. Vehicles variation and depreciation are not concerned; battery charging is linear over time approximately; the battery status is denoted by the available travel distance, km.By modeling the dynamics of the number of vehicles at a station, the proper upper and lower thresholds can be determined under the minimization of the number of relocations and the time ratio where either the vehicles or parking spaces are out of service.


### 3.2. State Transition

#### 3.2.1. Transition of the Number of Vehicles

The number of vehicles at the station in time stept is formulated as (1)xt=xt-1+rt+δt+-dtst-δt-,∀t=1,2,⋯,T


#### 3.2.2. Vehicles to Be Moved In

The number of vehicles required to be moved in att is (2)δtn+=max⁡Slower-xt-1,0For each vehicle vt=1,2,⋯,δtn+ that required to be moved in at t and actually moved in at t+tvt+, the moving tags and the sum of the moving tags of all vts should be (3)vmt,t+tvt++,vt=1(4)∑vt=1δtn+vmt,t+tvt++,vt=δtn+Each vehicle vt∈Vt(n+) should be only moved once, from t to the maximum delay time step: (5)∑vt=1δtn+∑td=0max⁡tvt+vmt,t+td+,vt=δtn+The vehicles that actually moved in at t: (6)∑k=max⁡t-max⁡tvt+,1⁡t∑vk=1δtn+vmk,t+,vk=δt+


#### 3.2.3. Vehicles to Be Moved Out

The number of vehicles required to be moved out att is (7)δtn-=max⁡xt-1-Supper,0For each vehicle vt=1,2,⋯,δt(n-) that required to be moved out at t and actually moved out at t+tvt(-), the moving tags and the sum of the moving tags of all vts should equal δt(n-): (8)vmt,t+tvt--,vt=1(9)∑vt=1δtn-vmt,t+tvt--,vt=δtn-Each vehicle vt∈Vt(n-) should be only moved once, from t to the maximum delay time step: (10)∑vt=1δtn-∑td=0max⁡tvt-vmt,t+td-,vt=δtn-The vehicles that should be actually moved out at t: (11)∑k=max⁡t-max⁡tvt-,1⁡t∑vk=1δtn-vmk,t-,vk=δt∗-


#### 3.2.4. Vehicles Matching according to Battery Status

DenoteBt=Bt-1V(rm)∪Bt(+)∪Bt(R) and Bt(D)=Bt-1D(rm)∪Bt(ge). Supposing demands of pick-ups and requests to relocate vehicles out have equal opportunity to select vehicles, the matching processing should satisfy the following conditions.For each available vehicle, there should be at most one demand matching it:(12)∑bD∈Bt-∪BtDvstb,bD≤1,∀b∈BtFor each demand, there should be at most one available vehicle matching it: (13)∑b∈Btvstb,bD≤1,∀bD∈Bt-∪BtDFor available vehicles and demands matching, we suppose a “best matching” principle that users and relocation staff will get the vehicles with the best utility, leading to a maximum of the total provided and demanded battery of matched vehicles: (14)∑b∈Bt∑bD∈Bt-∪BtDb×bD×vstb,bD-∑b∈Bt∑bD∈Bt-∪BtDb×bD×vs-tb,bD≥0,∀vs-tb,bD∈VSwhere VS denotes a space containing all combinations of vstb,bD.It should be noted that the matching between the demands and the available vehicles according to the desired and the provided battery status is actually even complicated, and further studies on this problem can be derived.Hence, the actual number of vehicles to be relocated out att should be(15)δt-=∑b∈Bt∑bD∈Bt-vstb,bDThe actual number of satisfied demands at t should be(16)dtst=∑b∈Bt∑bD∈BtDvstb,bDThe battery status of the remaining vehicles at the end of time step t consists of a set: (17)BtVrm=min⁡b+l·cv,Bmax∣∀b∈Bt,∑bD∈Bt-∪BtDvstb,bD=0The unsatisfied demand battery status set is (18)BtDus=b∣∀b∈Bt,∑bD∈Bt-∪BtDvstb,bD=0The remaining demand battery status set is (19)BtDrm=b∣∀b∈BtDus,ptb=1


### 3.3. Thresholds Determination

The optimization model of thresholds determination is formulated as follows.Objective 1(CSOs’ perspective)(20)min⁡f1Supper,Slower=-RV·∑t=1Tdtst-CR·∑t=1Tδt-Objective 2(users’ perspective)(21)minf2Supper,Slower=∑t=1Tut++∑t=1Tut-T(22)s.t.Slower≤Supper(23)Supper≤N(24)Slower≥0(25)Slower,Supperare integers,with state transition equations (1) to (19).Objective 1 indicates that the CSOs’ objective is to maximize the profits at the station. Formula (20) is to add up the revenues from all satisfied demands and subtract the costs of all the relocations. Formula (21) describes the ratio of the time that the system is unavailable for both pick-up and drop-off requirement to the total time, which indicates the service quality of the system. The decision variables Supper,Slower are hidden in both objective functions. Formulae (22) to (25) constrain the thresholds where the lower threshold should be equal to or lower than the upper threshold, the upper threshold should not exceed the number of parking space, and the lower threshold should not be below 0. The state transition equations are also constraints to guarantee the dynamics of the system.


## 3.1. Problem Description

In each station, the number of vehicles is dynamically changing because vehicles would be picked up, dropped off, relocated in, and relocated out. For a single station, the changing range of vehicle amount depends on its own pick-ups and drop-offs, and its proper range is controlled by relocations.As for the coherence with previous relocation-related works [7, 18], in this paper, time series is also discretized into time steps of 1 hour. During a time step, the vehicles dropped off, the vehicles relocated in, and the idle vehicles are all available for picking up and relocating out according to the matching between available state of charge (SOC) of these vehicles and the required travel distance.If the number of vehicles at the station is below the lower threshold at one time step, the station requires vehicles to be relocated in. However, not all the required vehicles can be successfully moved into the station within this time step, and the exact arrivals of vehicles relocated in will endure a time-stepwise delay. For the number exceeding the upper threshold it is similar, and the exact departure of vehicles to be relocated out will also delay due to the availability of relocation staff.Users want to select the vehicle whose battery life is the most suitable for their journey, and users will abandon the system at a proportion if no suitable vehicles are available. Vehicles will be charged immediately when arriving at station. Vehicles variation and depreciation are not concerned; battery charging is linear over time approximately; the battery status is denoted by the available travel distance, km.By modeling the dynamics of the number of vehicles at a station, the proper upper and lower thresholds can be determined under the minimization of the number of relocations and the time ratio where either the vehicles or parking spaces are out of service.


## 3.2. State Transition

### 3.2.1. Transition of the Number of Vehicles

The number of vehicles at the station in time stept is formulated as (1)xt=xt-1+rt+δt+-dtst-δt-,∀t=1,2,⋯,T


### 3.2.2. Vehicles to Be Moved In

The number of vehicles required to be moved in att is (2)δtn+=max⁡Slower-xt-1,0For each vehicle vt=1,2,⋯,δtn+ that required to be moved in at t and actually moved in at t+tvt+, the moving tags and the sum of the moving tags of all vts should be (3)vmt,t+tvt++,vt=1(4)∑vt=1δtn+vmt,t+tvt++,vt=δtn+Each vehicle vt∈Vt(n+) should be only moved once, from t to the maximum delay time step: (5)∑vt=1δtn+∑td=0max⁡tvt+vmt,t+td+,vt=δtn+The vehicles that actually moved in at t: (6)∑k=max⁡t-max⁡tvt+,1⁡t∑vk=1δtn+vmk,t+,vk=δt+


### 3.2.3. Vehicles to Be Moved Out

The number of vehicles required to be moved out att is (7)δtn-=max⁡xt-1-Supper,0For each vehicle vt=1,2,⋯,δt(n-) that required to be moved out at t and actually moved out at t+tvt(-), the moving tags and the sum of the moving tags of all vts should equal δt(n-): (8)vmt,t+tvt--,vt=1(9)∑vt=1δtn-vmt,t+tvt--,vt=δtn-Each vehicle vt∈Vt(n-) should be only moved once, from t to the maximum delay time step: (10)∑vt=1δtn-∑td=0max⁡tvt-vmt,t+td-,vt=δtn-The vehicles that should be actually moved out at t: (11)∑k=max⁡t-max⁡tvt-,1⁡t∑vk=1δtn-vmk,t-,vk=δt∗-


### 3.2.4. Vehicles Matching according to Battery Status

DenoteBt=Bt-1V(rm)∪Bt(+)∪Bt(R) and Bt(D)=Bt-1D(rm)∪Bt(ge). Supposing demands of pick-ups and requests to relocate vehicles out have equal opportunity to select vehicles, the matching processing should satisfy the following conditions.For each available vehicle, there should be at most one demand matching it:(12)∑bD∈Bt-∪BtDvstb,bD≤1,∀b∈BtFor each demand, there should be at most one available vehicle matching it: (13)∑b∈Btvstb,bD≤1,∀bD∈Bt-∪BtDFor available vehicles and demands matching, we suppose a “best matching” principle that users and relocation staff will get the vehicles with the best utility, leading to a maximum of the total provided and demanded battery of matched vehicles: (14)∑b∈Bt∑bD∈Bt-∪BtDb×bD×vstb,bD-∑b∈Bt∑bD∈Bt-∪BtDb×bD×vs-tb,bD≥0,∀vs-tb,bD∈VSwhere VS denotes a space containing all combinations of vstb,bD.It should be noted that the matching between the demands and the available vehicles according to the desired and the provided battery status is actually even complicated, and further studies on this problem can be derived.Hence, the actual number of vehicles to be relocated out att should be(15)δt-=∑b∈Bt∑bD∈Bt-vstb,bDThe actual number of satisfied demands at t should be(16)dtst=∑b∈Bt∑bD∈BtDvstb,bDThe battery status of the remaining vehicles at the end of time step t consists of a set: (17)BtVrm=min⁡b+l·cv,Bmax∣∀b∈Bt,∑bD∈Bt-∪BtDvstb,bD=0The unsatisfied demand battery status set is (18)BtDus=b∣∀b∈Bt,∑bD∈Bt-∪BtDvstb,bD=0The remaining demand battery status set is (19)BtDrm=b∣∀b∈BtDus,ptb=1


## 3.2.1. Transition of the Number of Vehicles

The number of vehicles at the station in time stept is formulated as (1)xt=xt-1+rt+δt+-dtst-δt-,∀t=1,2,⋯,T


## 3.2.2. Vehicles to Be Moved In

The number of vehicles required to be moved in att is (2)δtn+=max⁡Slower-xt-1,0For each vehicle vt=1,2,⋯,δtn+ that required to be moved in at t and actually moved in at t+tvt+, the moving tags and the sum of the moving tags of all vts should be (3)vmt,t+tvt++,vt=1(4)∑vt=1δtn+vmt,t+tvt++,vt=δtn+Each vehicle vt∈Vt(n+) should be only moved once, from t to the maximum delay time step: (5)∑vt=1δtn+∑td=0max⁡tvt+vmt,t+td+,vt=δtn+The vehicles that actually moved in at t: (6)∑k=max⁡t-max⁡tvt+,1⁡t∑vk=1δtn+vmk,t+,vk=δt+


## 3.2.3. Vehicles to Be Moved Out

The number of vehicles required to be moved out att is (7)δtn-=max⁡xt-1-Supper,0For each vehicle vt=1,2,⋯,δt(n-) that required to be moved out at t and actually moved out at t+tvt(-), the moving tags and the sum of the moving tags of all vts should equal δt(n-): (8)vmt,t+tvt--,vt=1(9)∑vt=1δtn-vmt,t+tvt--,vt=δtn-Each vehicle vt∈Vt(n-) should be only moved once, from t to the maximum delay time step: (10)∑vt=1δtn-∑td=0max⁡tvt-vmt,t+td-,vt=δtn-The vehicles that should be actually moved out at t: (11)∑k=max⁡t-max⁡tvt-,1⁡t∑vk=1δtn-vmk,t-,vk=δt∗-


## 3.2.4. Vehicles Matching according to Battery Status

DenoteBt=Bt-1V(rm)∪Bt(+)∪Bt(R) and Bt(D)=Bt-1D(rm)∪Bt(ge). Supposing demands of pick-ups and requests to relocate vehicles out have equal opportunity to select vehicles, the matching processing should satisfy the following conditions.For each available vehicle, there should be at most one demand matching it:(12)∑bD∈Bt-∪BtDvstb,bD≤1,∀b∈BtFor each demand, there should be at most one available vehicle matching it: (13)∑b∈Btvstb,bD≤1,∀bD∈Bt-∪BtDFor available vehicles and demands matching, we suppose a “best matching” principle that users and relocation staff will get the vehicles with the best utility, leading to a maximum of the total provided and demanded battery of matched vehicles: (14)∑b∈Bt∑bD∈Bt-∪BtDb×bD×vstb,bD-∑b∈Bt∑bD∈Bt-∪BtDb×bD×vs-tb,bD≥0,∀vs-tb,bD∈VSwhere VS denotes a space containing all combinations of vstb,bD.It should be noted that the matching between the demands and the available vehicles according to the desired and the provided battery status is actually even complicated, and further studies on this problem can be derived.Hence, the actual number of vehicles to be relocated out att should be(15)δt-=∑b∈Bt∑bD∈Bt-vstb,bDThe actual number of satisfied demands at t should be(16)dtst=∑b∈Bt∑bD∈BtDvstb,bDThe battery status of the remaining vehicles at the end of time step t consists of a set: (17)BtVrm=min⁡b+l·cv,Bmax∣∀b∈Bt,∑bD∈Bt-∪BtDvstb,bD=0The unsatisfied demand battery status set is (18)BtDus=b∣∀b∈Bt,∑bD∈Bt-∪BtDvstb,bD=0The remaining demand battery status set is (19)BtDrm=b∣∀b∈BtDus,ptb=1


## 3.3. Thresholds Determination

The optimization model of thresholds determination is formulated as follows.Objective 1(CSOs’ perspective)(20)min⁡f1Supper,Slower=-RV·∑t=1Tdtst-CR·∑t=1Tδt-Objective 2(users’ perspective)(21)minf2Supper,Slower=∑t=1Tut++∑t=1Tut-T(22)s.t.Slower≤Supper(23)Supper≤N(24)Slower≥0(25)Slower,Supperare integers,with state transition equations (1) to (19).Objective 1 indicates that the CSOs’ objective is to maximize the profits at the station. Formula (20) is to add up the revenues from all satisfied demands and subtract the costs of all the relocations. Formula (21) describes the ratio of the time that the system is unavailable for both pick-up and drop-off requirement to the total time, which indicates the service quality of the system. The decision variables Supper,Slower are hidden in both objective functions. Formulae (22) to (25) constrain the thresholds where the lower threshold should be equal to or lower than the upper threshold, the upper threshold should not exceed the number of parking space, and the lower threshold should not be below 0. The state transition equations are also constraints to guarantee the dynamics of the system.


## 4. Solution Algorithm

### 4.1. Solution Principles

The thresholds determination model under stochastic demands is facing three problems:(a)
The stochastic variables make the other parameters and variables uncertain during the state transition and let the definition of the minimization of the objectives be uncertain.(b)
The two objectives are conflicting with each other and hard to achieve at the same time, which is not explicit for decision, and compromises need to be made.(c)
The model is hard to be linearized due to the hidden property of decision variables, the dynamic change of system parameters, and the uncertainty of the stochastic variables and sets.To solve this model, reformations are given as follows.For problem (a), employ the min–max robust optimization to find out the best solutions under the worst conditions of the stochastic variables, and rewrite the objective as(26)minSupper,Slower⁡maxrt,dtge,bt,vtR,bt,vtge,bt,vt+,bt,vt-,tvt+,tvt-,ptb⁡fiSupper,Slower,∀t=1,2,⋯,T,∀i=1,2,∀i=1,2In objective (26), the inner objective is to locate the maximum (worst) metrics and find out the values of the stochastic variables (auxiliary decision variables) under the worst conditions; the outer objective is to judge the minimum (best) metrics among worst conditions of all the Suppers and Slowers and decide the final solutions on Supper and Slower. This strengthens the robustness of the solutions, i.e., ensures the result thresholds to be capable during the worst condition under the stochastic demands.Problem (b) can be addressed by introducing the Pareto optimum, which determines a set of nondominated solutions where improvement of one objective cannot be achieved without sacrifice of the other objective, and the objective metrics of these solutions lie on the Pareto front. To define the Pareto solution set, a decision vectorx→∗ is Pareto optimal solution if there does not exist another x→ such that fix→≤fix→∗, ∀i=1,2 and fjx→<fjx→∗ for at least one j. For both “min” and “max” steps the Pareto optimum creates rational solution sets and Pareto fronts to pick out compromised solutions under both objectives.To construct the solution algorithm and cope with the problem (c), we involve the Monte Carlo approach to generate the stochastic seeds and determine the final solutions according to the previous rules. Detailed solution procedures are illustrated in Section4.2.


### 4.2. Solution Procedure

In the study case of EVCARD, because the maximumN is 10 among all stations, the combinations of Supper and Slower can be enumerated and the random seeds can be generated through Monte Carlo approach, so the enumerative solution procedure is proposed as follows.Step  1. For each Supper and Slower satisfying the constraints, create pairs of Supper and Slower; for each pair of thresholds we have the following.Step  1.1. For stochastic variables rt,dtge,bt,vtR,bt,vtge,bt,vt+,bt,vt-,tvt+,tvt-,ptb, which should follow their own distribution, generate R random seeds.Step  1.2. For each random seed, calculate the two objectives through the state transition equations, denote these solutions as kr,∀r=1,⋯,R, with decision variables Supperkr, Slowerkr and objectives f1kr, f2kr; add kr,∀r=1,⋯,R to a set Ka which includes all stochastic solutions.Step  1.3. From the calculated objectives corresponding to the random seeds, find out the worst-case Pareto front of this pair of Supper and Slower; add these solutions to a set denoted as KSupper,Slowerw.Step  1.4. If every pair of Supper and Slower has been processed, continue to Step 2.Step  2. For all pairs of Supper and Slower, find out the best-case Pareto front in set ⋃Supper,SlowerKSupper,Slowerw, as well as the corresponding nondominated solutions; add these solutions to a set denoted as K.Step  3. Pick out final decision. For solution k∈K with decision variables Supperk, Slowerk and objectives f1k, f2k, since f1k∈[-∞,+∞) and f2k∈[0,1], to judge both objectives fairly, normalize the two objectives as(27)fn1k=f1k-minm∈Ka⁡f1m-minm′∈Ka⁡f1m′-minm∈Ka⁡f1mmaxm′∈Ka⁡f1m′-minm∈Ka⁡f1mfn2k=f2k-minm∈Ka⁡f2mmaxm∈Ka⁡f2mDefine the weighted objective as(28)fk=ω1fn1k+ω2fn1kwhere ω1 and ω2 are weights and ω1+ω2=1, which represent the importance of each objective and could be set by the operators. For the operators that attach more importance to objective 1 over objective 2, ω1 could be set higher than ω2. Find out k∗∈K where fk∗=mink∈K⁡fk, and k∗ is the final decision, where the thresholds are Supperk∗, Slowerk∗, with the objectives of f1k∗, f2k∗.


## 4.1. Solution Principles

The thresholds determination model under stochastic demands is facing three problems:(a)
The stochastic variables make the other parameters and variables uncertain during the state transition and let the definition of the minimization of the objectives be uncertain.(b)
The two objectives are conflicting with each other and hard to achieve at the same time, which is not explicit for decision, and compromises need to be made.(c)
The model is hard to be linearized due to the hidden property of decision variables, the dynamic change of system parameters, and the uncertainty of the stochastic variables and sets.To solve this model, reformations are given as follows.For problem (a), employ the min–max robust optimization to find out the best solutions under the worst conditions of the stochastic variables, and rewrite the objective as(26)minSupper,Slower⁡maxrt,dtge,bt,vtR,bt,vtge,bt,vt+,bt,vt-,tvt+,tvt-,ptb⁡fiSupper,Slower,∀t=1,2,⋯,T,∀i=1,2,∀i=1,2In objective (26), the inner objective is to locate the maximum (worst) metrics and find out the values of the stochastic variables (auxiliary decision variables) under the worst conditions; the outer objective is to judge the minimum (best) metrics among worst conditions of all the Suppers and Slowers and decide the final solutions on Supper and Slower. This strengthens the robustness of the solutions, i.e., ensures the result thresholds to be capable during the worst condition under the stochastic demands.Problem (b) can be addressed by introducing the Pareto optimum, which determines a set of nondominated solutions where improvement of one objective cannot be achieved without sacrifice of the other objective, and the objective metrics of these solutions lie on the Pareto front. To define the Pareto solution set, a decision vectorx→∗ is Pareto optimal solution if there does not exist another x→ such that fix→≤fix→∗, ∀i=1,2 and fjx→<fjx→∗ for at least one j. For both “min” and “max” steps the Pareto optimum creates rational solution sets and Pareto fronts to pick out compromised solutions under both objectives.To construct the solution algorithm and cope with the problem (c), we involve the Monte Carlo approach to generate the stochastic seeds and determine the final solutions according to the previous rules. Detailed solution procedures are illustrated in Section4.2.


## 4.2. Solution Procedure

In the study case of EVCARD, because the maximumN is 10 among all stations, the combinations of Supper and Slower can be enumerated and the random seeds can be generated through Monte Carlo approach, so the enumerative solution procedure is proposed as follows.Step  1. For each Supper and Slower satisfying the constraints, create pairs of Supper and Slower; for each pair of thresholds we have the following.Step  1.1. For stochastic variables rt,dtge,bt,vtR,bt,vtge,bt,vt+,bt,vt-,tvt+,tvt-,ptb, which should follow their own distribution, generate R random seeds.Step  1.2. For each random seed, calculate the two objectives through the state transition equations, denote these solutions as kr,∀r=1,⋯,R, with decision variables Supperkr, Slowerkr and objectives f1kr, f2kr; add kr,∀r=1,⋯,R to a set Ka which includes all stochastic solutions.Step  1.3. From the calculated objectives corresponding to the random seeds, find out the worst-case Pareto front of this pair of Supper and Slower; add these solutions to a set denoted as KSupper,Slowerw.Step  1.4. If every pair of Supper and Slower has been processed, continue to Step 2.Step  2. For all pairs of Supper and Slower, find out the best-case Pareto front in set ⋃Supper,SlowerKSupper,Slowerw, as well as the corresponding nondominated solutions; add these solutions to a set denoted as K.Step  3. Pick out final decision. For solution k∈K with decision variables Supperk, Slowerk and objectives f1k, f2k, since f1k∈[-∞,+∞) and f2k∈[0,1], to judge both objectives fairly, normalize the two objectives as(27)fn1k=f1k-minm∈Ka⁡f1m-minm′∈Ka⁡f1m′-minm∈Ka⁡f1mmaxm′∈Ka⁡f1m′-minm∈Ka⁡f1mfn2k=f2k-minm∈Ka⁡f2mmaxm∈Ka⁡f2mDefine the weighted objective as(28)fk=ω1fn1k+ω2fn1kwhere ω1 and ω2 are weights and ω1+ω2=1, which represent the importance of each objective and could be set by the operators. For the operators that attach more importance to objective 1 over objective 2, ω1 could be set higher than ω2. Find out k∗∈K where fk∗=mink∈K⁡fk, and k∗ is the final decision, where the thresholds are Supperk∗, Slowerk∗, with the objectives of f1k∗, f2k∗.


## 5. Analysis and Discussion

### 5.1. Calibration of Stochastic Distribution

The data bed to calibrate the stochastic variables is based on the order record database of EVCARD during April 2015, which contained 2848 order records as well as the information of 56 stations, and the supplementary user survey conducted in March 2016, which retrieved 138 respondents’ intention.(1) Demand variablesrt and dtge: One day is discretized into 24 time periods by the step width 1h, and each period over a month is independent and follows the same distribution. Poisson distributions are tested for them. Figure 2 displays the comparison between the real data histograms (displayed in blue bars) and the theoretical Poisson distributions (displayed in orange bars) at station No. 44 Jiading campus among all the time steps in one day. Their distribution hypothesis tests are conducted by χ2-test under significance level 0.05, where h = 0 denotes not rejecting the null hypothesis of Poisson and h = 1 means reject.Figure 2
Observed histogram and theoretical distribution of pick-up and return demands.
(a)
Pick-up distribution (b)
Return distribution(2) Continuous variablesbt,vtR, bt,vtge, bt,vt+, bt,vt-: The battery status follows continuous distribution. We investigated the battery status of returned vehicles and relocated vehicles through the orders and the users’ desired battery status by the user survey. The histograms and the hypothesized distribution are illustrated in Figure 3. Under significance level 0.05, K-S tests were conducted to exam the fitness of continuous distribution and all of the four distributions ((a) uniform, (b) log-normal, (c) log-normal, and (d) normal) are not rejected.Figure 3
Distribution of discretized variables.
(a)
Distribution of battery status of returned vehicles (b)
Distribution of users’ desired battery status (c)
Distribution of battery status of relocate-in (d)
Distribution of battery status of relocate-out (e)
Relocate-in time delay (f)
Relocate-out time delay (g)
Demands remaining(3) Discretized variablestvt+, tvt-, ptb: The relocation time delay is inferred from the order data and the demands remaining probability is inferred from the user survey. Figure 3 reveals the distribution of the discretized time delay and rejected demands remaining. Figure 3(e) (or Figure 3(f)) shows the probability of delay for 0 time step, 1 time step, 2 time steps, etc. Figure 3(g) refers to the abandon proportion (denoted by 0) and the remaining proportion (denoted by 1) when the demands are rejected due to the vehicle insufficiency as a 0-1 distribution, where more than a half users prefer to abandon using the system.


### 5.2. Numerical Example

The data of the example came from the station No. 44, Jiading Campus, of the EVCARD system during Apr. 2015. There are seven parking spaces (N=7) at the station; the time step width l=1h; for 30 days’ data there are 720 time steps during the study period (T=720). The general vehicle type can travel at most 100km and will be charged in 5h in AC charging mode (cv=20, Bmax=100).Figure4 shows the generation of the random seeds by the scatters of the two objectives. In the figure, different colors are used to distinguish different pairs of Supper and Slower; dots denote the objective values of all the random seeds, stars denote the worst-case Pareto front of each pair of Supper and Slower, and stars with circles denote the minimum Pareto front in all the worst conditions. Step 1 of the algorithm can be visualized in Figure 4(a) where the random seeds are generated for each pair of thresholds and the worst Pareto fronts of each pair of thresholds are highlighted in stars. Step 2 is visualized in Figure 4(b) which retained the worst-case Pareto fronts and the best-case Pareto front is approximated based on the worst-case Pareto fronts and marked by circles.Figure 4
The visualization of the algorithm of the example station.
(a)
Determination of the worst-case Pareto front (b)
Determination of the best-case Pareto frontThe nondominated solutions of thresholds and corresponding minimum Pareto front are listed in Table1. Thresholds (3,4), (2,5), (3,5), (0,6), (1,6), and (2,6) are all reasonable to guarantee the worst condition caused by the random demands. To decide the final decision for CSOs according to Step 3 of the algorithm, we need to select values of weights. Generally, operators attach equal importance to both of the objectives, like the case of EVCARD in this study. We attached equal importance to both objectives in previous study [27] through deterministic approach (weight ω1=ω2). For comparison, we also choose equal weights here. Under this metric, (2,6) will be selected as the final decision as the thresholds of the station.


### 5.3. Comparison among Determination Methods

Three means of thresholds determination methods are compared. (1) Empirical method: The upper thresholds are set by the number of parking space minus 1 to satisfy the drop-offs, and the lower thresholds are set as 1 to ensure a vehicle available. (2) Deterministic method: The random variables are substituted by the known order data, and optimal solutions of thresholds are calculated aiming to minimize the relocation times as well as the out-of-service rate. (3) Stochastic method is proposed by this paper.Based on the same data bed, we calculated the thresholds of all the 56 stations using the three methods. Figure5 illustrates a comparison among the results of the three methods. The results of the 56 stations using the three methods appear with both differences and indiscrimination, which are concluded in Table 2.Table 2
The nondominated solutions set and the final decision under weighted method.
Lower threshold Slower Upper threshold Supper Profits of the operator f1 out of service Rate f2 Weighted objective f 3 4 -2407 0.001 0.500 2 5 -4343 0.004 0.260 3 5 -5023 0.010 0.187 0 6 -6230 0.193 0.471 0 6 -6339 0.210 0.497 1 6 -6113 0.054 0.155 2 6 -5851 0.028 0.125Figure 5
Result comparison among empirical method, deterministic method, and stochastic method.
(a)
Thresholds determined by empirical method (b)
Thresholds determined by deterministic method (c)
Thresholds determined by stochastic methodNotably, there are 27 in 56 stations where the three methods give all different solutions and six stations where the stochastic method gives different solutions from empirical method and deterministic method (as shown in Table3), which means there are 33 stations (59%) where the stochastic method reaches other solutions. However, for 13 stations (23%) the stochastic method solves out the same solutions as the empirical rules do, and for 7 stations the three methods come to the same results; i.e., empirical method gives identical answer as the stochastic method does in 20 stations (36%). The deterministic method only gives identical results to the stochastic methods in 13 stations (23%).Table 3
Differences and indiscrimination of results from the three methods.
All the same Emp eq. Det Emp eq. Sto Det eq. Sto All different The number of stations 7 6 13 3 27 Note: Emp denotes the empirical method; Det denotes the deterministic method; Sto denotes the stochastic method; eq. denotes equals.Except the 7 stations where the three methods give the same solutions, we extract four representative stations under uncertain demands, respectively, from the condition that the empirical method equals the deterministic method, the condition that the empirical method equals the stochastic method, the condition that the deterministic method equals the stochastic method, and the condition that they are all different, and the scatterplots and histograms of both objective metrics of four stations are shown in Figures6(a), 6(b), 6(c), and 6(d), respectively. In Figure 6, random seeds are denoted by dots, the worst-case Pareto fronts are denoted by color circles and solid links, and the best-case Pareto fronts are denoted by black circles and dash links. For station No. 36 in Figure 6(a) the solution from stochastic method performs better than the solution from the empirical method and deterministic method in out-of-service rate with minor concession on profits. For station No. 34 in Figure 6(b), the stochastic method as well as empirical rules perform obviously better on out-of-service rate. For station No. 29 in Figure 6(c), the stochastic method and the deterministic method achieve absolutely lower out-of-service rate with approximate profits. For station No. 44 in Figure 6(d) the worst condition of stochastic method performs better than the worst condition of other methods, with little sacrificing on profits.Figure 6
Comparison of the profit among the three methods.
(a)
Station 36,N=10 (b)
Station 34,N=4 (c)
Station 29,N=6 (d)
Station 44,N=7


### 5.4. Variable Thresholds during a Day

The above model captures long term characteristics and determined a daily thresholds scheme, which supports day-to-day operation. However, for more specific situation, demands can appear with variation in different period of day. To account for variations depending on time-of-day, we specify the daily thresholds into variable thresholds during a day.The decision variables should be extended to all time steps, and∀t=1,2,⋯,T, we have the following decision variables:Suppert: upper threshold of the station at time step tSlowert: lower threshold of the station at time step t.And the formulae in state transition functions (2) and (7) should be modified as (29)δtn+=max⁡Slowert-xt-1,0(30)δtn-=max⁡xt-1-Suppert,0The constraints regarding upper and lower thresholds should also be (31)Slowert≤Suppert,Suppert≤N,Slowert≥0,Slowert,Suppertare integers,∀t=1,2,⋯,TThe previous model can be fast solved due to the limited combination of two thresholds. In the extended model, more thresholds responding to different time steps significantly enlarge the space of the solutions. There are NN-1/2 combinations of two thresholds but NN-1/2t combinations of t time steps. Supposing there are 24 periods in a day as the research time range, the solution space turns out to be quite huge.Considering the dynamics of the system happens by time step successively, a local optimum can be reached from a dynamic programming approach. We solve one pair of thresholds for one time step fromt=1 to T step by step. Firstly Slower1,Supper1 can be solved. When solving Slowert,Suppert, we deem the previous feasible solution of Slower1,Supper1,…,Slowert-1,Suppert-1 as known variables solved in previous steps. In that case the algorithm in this paper is applicable to solve the variable thresholds problem.Figure7 shows the case to determine the thresholds of station No. 44. Figure 7(a) illustrates the demand pattern in different time steps, where boxplots indicate the randomness of demands. Figure 7(b) shows the result of Slowert,Suppert, ∀t=1,2,⋯,24, during one day, where green triangles denote the upper thresholds and red triangles denote the lower thresholds. The solid line in this figure represents the average possible number of vehicles conserved in the station. The green and red dash line, respectively, indicate the possible maximum and minimum bound of vehicles conserved in the station due to the stochastic demands. The green and red dash lines confine a probable range of the numbers of vehicles at the station.Figure 7
Solution of thresholds for different hours in a day.
(a)
Boxplot of stochastic demand pattern in different time steps (b)
Thresholds in different time stepsThere are some findings from the result shown by the figure. During the wee hours (1:00 ~ 6:00) with low demands, the upper threshold is relatively low, which allows idle vehicles to be moved out, to support other stations which need vehicles to be moved in during the same period (if existing). When demands occur after 7:00, the lower threshold goes up for requiring vehicles to be moved in, accounting for the following peak hours. Until 16:00 demands slightly decrease, and the possible range of vehicle number at station during 16:00 seems to be relatively higher, so that the thresholds accordingly go down to let the vehicles to be moved out. During 18:00 the possible range of vehicle number seems to decrease and the thresholds allow vehicles to be moved in. After 20:00 the number of vehicles turns to be stable and the thresholds are wider to let the number of vehicles change naturally.


## 5.1. Calibration of Stochastic Distribution

The data bed to calibrate the stochastic variables is based on the order record database of EVCARD during April 2015, which contained 2848 order records as well as the information of 56 stations, and the supplementary user survey conducted in March 2016, which retrieved 138 respondents’ intention.(1) Demand variablesrt and dtge: One day is discretized into 24 time periods by the step width 1h, and each period over a month is independent and follows the same distribution. Poisson distributions are tested for them. Figure 2 displays the comparison between the real data histograms (displayed in blue bars) and the theoretical Poisson distributions (displayed in orange bars) at station No. 44 Jiading campus among all the time steps in one day. Their distribution hypothesis tests are conducted by χ2-test under significance level 0.05, where h = 0 denotes not rejecting the null hypothesis of Poisson and h = 1 means reject.Figure 2
Observed histogram and theoretical distribution of pick-up and return demands.
(a)
Pick-up distribution (b)
Return distribution(2) Continuous variablesbt,vtR, bt,vtge, bt,vt+, bt,vt-: The battery status follows continuous distribution. We investigated the battery status of returned vehicles and relocated vehicles through the orders and the users’ desired battery status by the user survey. The histograms and the hypothesized distribution are illustrated in Figure 3. Under significance level 0.05, K-S tests were conducted to exam the fitness of continuous distribution and all of the four distributions ((a) uniform, (b) log-normal, (c) log-normal, and (d) normal) are not rejected.Figure 3
Distribution of discretized variables.
(a)
Distribution of battery status of returned vehicles (b)
Distribution of users’ desired battery status (c)
Distribution of battery status of relocate-in (d)
Distribution of battery status of relocate-out (e)
Relocate-in time delay (f)
Relocate-out time delay (g)
Demands remaining(3) Discretized variablestvt+, tvt-, ptb: The relocation time delay is inferred from the order data and the demands remaining probability is inferred from the user survey. Figure 3 reveals the distribution of the discretized time delay and rejected demands remaining. Figure 3(e) (or Figure 3(f)) shows the probability of delay for 0 time step, 1 time step, 2 time steps, etc. Figure 3(g) refers to the abandon proportion (denoted by 0) and the remaining proportion (denoted by 1) when the demands are rejected due to the vehicle insufficiency as a 0-1 distribution, where more than a half users prefer to abandon using the system.


## 5.2. Numerical Example

The data of the example came from the station No. 44, Jiading Campus, of the EVCARD system during Apr. 2015. There are seven parking spaces (N=7) at the station; the time step width l=1h; for 30 days’ data there are 720 time steps during the study period (T=720). The general vehicle type can travel at most 100km and will be charged in 5h in AC charging mode (cv=20, Bmax=100).Figure4 shows the generation of the random seeds by the scatters of the two objectives. In the figure, different colors are used to distinguish different pairs of Supper and Slower; dots denote the objective values of all the random seeds, stars denote the worst-case Pareto front of each pair of Supper and Slower, and stars with circles denote the minimum Pareto front in all the worst conditions. Step 1 of the algorithm can be visualized in Figure 4(a) where the random seeds are generated for each pair of thresholds and the worst Pareto fronts of each pair of thresholds are highlighted in stars. Step 2 is visualized in Figure 4(b) which retained the worst-case Pareto fronts and the best-case Pareto front is approximated based on the worst-case Pareto fronts and marked by circles.Figure 4
The visualization of the algorithm of the example station.
(a)
Determination of the worst-case Pareto front (b)
Determination of the best-case Pareto frontThe nondominated solutions of thresholds and corresponding minimum Pareto front are listed in Table1. Thresholds (3,4), (2,5), (3,5), (0,6), (1,6), and (2,6) are all reasonable to guarantee the worst condition caused by the random demands. To decide the final decision for CSOs according to Step 3 of the algorithm, we need to select values of weights. Generally, operators attach equal importance to both of the objectives, like the case of EVCARD in this study. We attached equal importance to both objectives in previous study [27] through deterministic approach (weight ω1=ω2). For comparison, we also choose equal weights here. Under this metric, (2,6) will be selected as the final decision as the thresholds of the station.


## 5.3. Comparison among Determination Methods

Three means of thresholds determination methods are compared. (1) Empirical method: The upper thresholds are set by the number of parking space minus 1 to satisfy the drop-offs, and the lower thresholds are set as 1 to ensure a vehicle available. (2) Deterministic method: The random variables are substituted by the known order data, and optimal solutions of thresholds are calculated aiming to minimize the relocation times as well as the out-of-service rate. (3) Stochastic method is proposed by this paper.Based on the same data bed, we calculated the thresholds of all the 56 stations using the three methods. Figure5 illustrates a comparison among the results of the three methods. The results of the 56 stations using the three methods appear with both differences and indiscrimination, which are concluded in Table 2.Table 2
The nondominated solutions set and the final decision under weighted method.
Lower threshold Slower Upper threshold Supper Profits of the operator f1 out of service Rate f2 Weighted objective f 3 4 -2407 0.001 0.500 2 5 -4343 0.004 0.260 3 5 -5023 0.010 0.187 0 6 -6230 0.193 0.471 0 6 -6339 0.210 0.497 1 6 -6113 0.054 0.155 2 6 -5851 0.028 0.125Figure 5
Result comparison among empirical method, deterministic method, and stochastic method.
(a)
Thresholds determined by empirical method (b)
Thresholds determined by deterministic method (c)
Thresholds determined by stochastic methodNotably, there are 27 in 56 stations where the three methods give all different solutions and six stations where the stochastic method gives different solutions from empirical method and deterministic method (as shown in Table3), which means there are 33 stations (59%) where the stochastic method reaches other solutions. However, for 13 stations (23%) the stochastic method solves out the same solutions as the empirical rules do, and for 7 stations the three methods come to the same results; i.e., empirical method gives identical answer as the stochastic method does in 20 stations (36%). The deterministic method only gives identical results to the stochastic methods in 13 stations (23%).Table 3
Differences and indiscrimination of results from the three methods.
All the same Emp eq. Det Emp eq. Sto Det eq. Sto All different The number of stations 7 6 13 3 27 Note: Emp denotes the empirical method; Det denotes the deterministic method; Sto denotes the stochastic method; eq. denotes equals.Except the 7 stations where the three methods give the same solutions, we extract four representative stations under uncertain demands, respectively, from the condition that the empirical method equals the deterministic method, the condition that the empirical method equals the stochastic method, the condition that the deterministic method equals the stochastic method, and the condition that they are all different, and the scatterplots and histograms of both objective metrics of four stations are shown in Figures6(a), 6(b), 6(c), and 6(d), respectively. In Figure 6, random seeds are denoted by dots, the worst-case Pareto fronts are denoted by color circles and solid links, and the best-case Pareto fronts are denoted by black circles and dash links. For station No. 36 in Figure 6(a) the solution from stochastic method performs better than the solution from the empirical method and deterministic method in out-of-service rate with minor concession on profits. For station No. 34 in Figure 6(b), the stochastic method as well as empirical rules perform obviously better on out-of-service rate. For station No. 29 in Figure 6(c), the stochastic method and the deterministic method achieve absolutely lower out-of-service rate with approximate profits. For station No. 44 in Figure 6(d) the worst condition of stochastic method performs better than the worst condition of other methods, with little sacrificing on profits.Figure 6
Comparison of the profit among the three methods.
(a)
Station 36,N=10 (b)
Station 34,N=4 (c)
Station 29,N=6 (d)
Station 44,N=7


## 5.4. Variable Thresholds during a Day

The above model captures long term characteristics and determined a daily thresholds scheme, which supports day-to-day operation. However, for more specific situation, demands can appear with variation in different period of day. To account for variations depending on time-of-day, we specify the daily thresholds into variable thresholds during a day.The decision variables should be extended to all time steps, and∀t=1,2,⋯,T, we have the following decision variables:Suppert: upper threshold of the station at time step tSlowert: lower threshold of the station at time step t.And the formulae in state transition functions (2) and (7) should be modified as (29)δtn+=max⁡Slowert-xt-1,0(30)δtn-=max⁡xt-1-Suppert,0The constraints regarding upper and lower thresholds should also be (31)Slowert≤Suppert,Suppert≤N,Slowert≥0,Slowert,Suppertare integers,∀t=1,2,⋯,TThe previous model can be fast solved due to the limited combination of two thresholds. In the extended model, more thresholds responding to different time steps significantly enlarge the space of the solutions. There are NN-1/2 combinations of two thresholds but NN-1/2t combinations of t time steps. Supposing there are 24 periods in a day as the research time range, the solution space turns out to be quite huge.Considering the dynamics of the system happens by time step successively, a local optimum can be reached from a dynamic programming approach. We solve one pair of thresholds for one time step fromt=1 to T step by step. Firstly Slower1,Supper1 can be solved. When solving Slowert,Suppert, we deem the previous feasible solution of Slower1,Supper1,…,Slowert-1,Suppert-1 as known variables solved in previous steps. In that case the algorithm in this paper is applicable to solve the variable thresholds problem.Figure7 shows the case to determine the thresholds of station No. 44. Figure 7(a) illustrates the demand pattern in different time steps, where boxplots indicate the randomness of demands. Figure 7(b) shows the result of Slowert,Suppert, ∀t=1,2,⋯,24, during one day, where green triangles denote the upper thresholds and red triangles denote the lower thresholds. The solid line in this figure represents the average possible number of vehicles conserved in the station. The green and red dash line, respectively, indicate the possible maximum and minimum bound of vehicles conserved in the station due to the stochastic demands. The green and red dash lines confine a probable range of the numbers of vehicles at the station.Figure 7
Solution of thresholds for different hours in a day.
(a)
Boxplot of stochastic demand pattern in different time steps (b)
Thresholds in different time stepsThere are some findings from the result shown by the figure. During the wee hours (1:00 ~ 6:00) with low demands, the upper threshold is relatively low, which allows idle vehicles to be moved out, to support other stations which need vehicles to be moved in during the same period (if existing). When demands occur after 7:00, the lower threshold goes up for requiring vehicles to be moved in, accounting for the following peak hours. Until 16:00 demands slightly decrease, and the possible range of vehicle number at station during 16:00 seems to be relatively higher, so that the thresholds accordingly go down to let the vehicles to be moved out. During 18:00 the possible range of vehicle number seems to decrease and the thresholds allow vehicles to be moved in. After 20:00 the number of vehicles turns to be stable and the thresholds are wider to let the number of vehicles change naturally.


## 6. Conclusions

This paper presents an approach on determining the thresholds considering the stochastic demands and system states, which provides a quantitative justification for thresholds determination. Firstly, we establish a model to capture the dynamics of the system status involving stochasticity and an optimization tactic is employed to find out proper values of upper and lower thresholds, aiming at minimizing the relocation times and the out-of-service time rate. The solution algorithm is provided to determine the rational solutions for this model, employing the min–max robust optimization to tackle the uncertainty and the Pareto optimum to decide the solution under dual objectives.To calibrate the stochastic variables, the continuous variables and the discretized variables are tested under the significance level of 0.05, which did not reject their hypothesis on their distribution, respectively. A numerical example was given to demonstrate the algorithm. A comparison was conducted among the empirical rules, the deterministic method, and the stochastic method, where the results suggest that the stochastic rules get the identical results with the empirical method at 23% of the stations and deterministic method at 5%. Among the stations where the stochastic method outputs different results from the empirical or deterministic method, the stochastic method achieves better solutions, which confirm that the stochastic method provides more reasonable justification towards uncertain demands.Actually the threshold determination is a fundamental part of the threshold based relocation approach; the entire method considering stochastic demands and system status is not sufficiently studied. Although the threshold based method is an on-demand respond method, the efficiency and effectiveness of this method in practice have not been reported yet. In the future, dynamic control or operation approaches are promising to cope with the real time relocation problem, which will bring more profits to the carsharing system operation.



---

*Source: 3486741-2018-07-29.xml*