Electric Vehicle Assignment Considering Users’ Waiting Time

Abstract

A one-way electric-car-sharing system is an environmentally friendly option for urban transportation systems, which can reduce air pollution and traffic congestion with effective vehicle assignment. However, electric vehicle assignment usually faces a dilemma where an insufficient battery level cannot fulfill the requests of users. It greatly affects assignment choices and order fulfillment rates, resulting in the loss of platform profit. In this study, with the assumption that the users agree to wait for a period of time during which electric vehicles can be charged to fulfill trip demands, we proposed a waiting-time policy and introduced users’ utility to measure user retention. Then, we set up a bi-level electric-vehicle assignment model with a waiting-time policy to optimize the assignment and waiting decisions. The numerical results show that under the waiting-time policy, we can achieve more profits, a higher trip fulfillment rate, and a significant improvement in vehicle utilization. It not only generates more profits for the platform but also provides a better service for users and lays a user foundation for the future development and operation.

1. Introduction

While people’s living standards and the growth of population keep increasing, people are increasingly demanding comfortable, convenient, fast, and safe travel modes. Private cars have naturally become the first choice, which has also led to a substantial increase in the amount of private cars. According to the statistics provided by URORA [1], the amount of private cars in China has exceeded 200 million. It causes a significant amount of social and environmental issues including traffic congestion, air pollution, higher accident rates, etc. In order to encourage people to choose a more environmentally friendly travel mode, local and regional governments have proposed some measures like license-plate restrictions and increased purchase taxes. However, private car traveling still accounts for most of the travel market share.

Consideration must be taken in both user travel experience and traffic and environmental problems. The car-sharing system (CSS) was originally developed in Switzerland in 1948 and was grown rapidly all over the world during the 1990s [2]. It allows users to pay a rental fee to get the experience of private vehicles rather than to buy a car. The CSS can significantly decrease the amount of vehicles in cities while increasing the vehicle utilization rate, saving land resources and reducing the traffic pressure [3]. Nevertheless, it does not completely solve the above dilemma. The CSS needs many cars to maintain operational stability, and fuel cars not only cost high in maintenance and traveling but also consume gasoline, which will cause environmental pollution. It causes the platform to face a high operating stress, and users need to pay higher rents.

However, the rapid development of electric vehicles (EVs) such as by Tesla brings new ideas to CSS in recent years. EVs not only have low travel costs but also solve problems such as environmental pollution and noise effectively, so CSS has absorbed more EVs for further sustainability. At the same time, countries also regard EVs as a solution to environmental pollution problems. They subsidize EVs, hoping to contribute to sustainable development [4]. Moreover, the concept of the Internet of Things drives the integration between the mobile internet and EVs, so the electric car-sharing system (ECSS) is trending to intellectualization. That is, users can locate themselves and book EVs online in time instead of going offline to book in person. Therefore, we considered the ECSS in our study and proposed a new operation method with a waiting-time policy to improve the performance of the electric vehicle assignment.

The ECSS can be divided into two main modes: the round-trip car-sharing, where vehicles must be retrieved and dropped off at the same station, and the one-way car-sharing, in which vehicles can be picked up at one station and returned at an another one [5]. The outstanding advantages of one-way car-sharing in flexibility make it more attractive to users so that more and more platforms enable this mode. Thus, one-way car-sharing occupies a large proportion of the market. Due to the unique characteristic of EVs, battery constraints must be taken into consideration. Though the technology is developing quickly, trips of EVs are still restricted by its battery capacities [6]. For example, EVs can only be allocated to a trip if the battery is capable of meeting the trip’s needs. When a user reaches a station, his trip cannot be fulfilled if the battery of an EV is not sufficient for the trip even when there are many EVs in the station; then, the user may leave and choose other travel modes.

In our research, the user’s time flexibility was considered to help the platform make the best assignment in the above situation. In the traditional case, users will leave the platform when they find that none of the EVs can meet their needs. However, sometimes, users agree to wait for a period of time due to various reasons. During the waiting time, if there is an EV being charged that meets the requirements of the user’s trip, then the user’s needs can be met, and the order fulfillment rate and the total profit of the platform will improve. From the perspective of the platform, if it proactively provides corresponding subsidies to users who are willing to wait, then users can decide whether to leave the platform based on the subsidies and their actual waiting time.

Based on the above consideration, we proposed a waiting time policy. Under the waiting-time policy, when the platform finds that an EV’s battery is insufficient to meet the need of a user’s trip, it will provide a certain subsidy to the user so that the user can decide whether to wait for a period of time or just go away based on his own utility. Then, the platform makes the optimal EV assignment plan with the recalculated user’s trip demands and the EV’s conditions. We formulated this problem as a bi-level model and developed a new vehicle-assignment policy.

User time flexibility is often mentioned in vehicle-assignment problems, but it rarely involves the relationship between user waiting time and shared EV battery level. This study first considered the influence among the user’s waiting time, the user’s utility, and the EV battery level. A waiting-time policy was proposed for ECSS. In order to verify it, we generated data to illustrate an assignment between EVs and trips with our waiting-time policy. ILOG CPLEX 12.10 was used as the platform in our study, and all numerical experiments were executed on the computer configured with an Intel Core i7-10710U CPU and 16 GB memory. The numerical experiments confirmed the performance superiority of the ECSS with the waiting-time policy.

The rest of the article is arranged as follows. Relevant research in related areas is presented in Section 2. We dedicate Section 3 to describing our mathematical problem and proposing an EV assignment model without waiting time. Then, we introduce the user’s utility to describe the user retention and then propose an EV assignment model with waiting time. Section 4 shows the numerical results of the evaluation of the EV assignment model with the waiting policy or not. We conclude our article with our results and some directions for future studies in Section 5.

2. Literature Review

For the one-way CSS, the existing studies mainly focused on its model, target, and solution approach. The decision-making problems related to it were mainly divided into strategic, tactical, and operational types. In the ECSS, the platform mainly plays a role in matching user trip needs with the operating EVs in the platform. Users send trip demands to the platform, and the platform assigns these trip demands to viable operating EVs based on certain rules.  Furuhata et al. [7] outlined the main features of different aspects of car-sharing systems and divides the existing systems into some categories based on matching conditions and optimization targets. Decisions related to one-way CSS can be divided into three groups [8]. Strategic decisions include optimizing volumes, locations, and parking spots. Indicative decisions include determining the fleet size and the amount of operators. Operational decisions include assigning vehicles to trip requests and assigning users to vehicles. The content of this section mainly involves the decisions regarding ECSS and corresponding characteristics. Since the waiting-time policy proposed in our study involves user flexibility, the literature associated with the spatial and temporal flexibility is also reviewed.

2.1. Decision Problem

 Su et al. [9] proposed a two-stage multi-period policy to decide which charging station the EV should be assigned to and then recommends the best driving route for each EV taking into account traffic congestion.  Boyacı et al. [10] developed a multi-objective MILP programming considering EV relocation and charging requests in ECSS.  Boyacı et al. [11] presented a discrete simulation model to make operational decisions of vehicle and staff relocation in a CSS and determines the feasibility of vehicle assignment based on available battery levels. Xue et al. [12] developed a comprehensive evaluation framework that shows that vehicle availability and relocation management are the most important factors affecting the performance of ECSS in China. Bruglieri et al. [13] presented the vehicle relocation problem in a station-based one-way ECSS. Movement between stations is performed using bicycles, and then vehicle relocation is performed among stations. The predicted trip requests were considered, and all of them were assumed to be met. Liu et al. [14] proposed a bi-level optimization model that maximizes profit and minimizes operating cost by considering demand-side management for EVs’ distribution and station capacity and location. Liu et al. [15] first determined the optimal physical charging power of the EV fleet and then constructed a decision model to describe whether users accept the scheduling. Based on the optimal scheme of the time-sharing subsidy, the EV fleet size considering users’ subjective decisions was obtained. Ref. [16] addressed the imbalance of vehicles by using a simulation to make prices change dynamically to influence trip demands, while Chow and Yu [17] provided a bidding-based vehicle-sharing model. The fleet-size and trip-pricing problems were combined in [18], taking into account the dynamic changes of trips and the relocation of people and vehicles.

2.2. Optimization Model

In order to solve the problems arising from demand fluctuations and the time-varying state of charge of EVs, Huang et al. [19] presented two decision problems at the strategic and operational levels and proposed a MINLP model to maximize the profit of operators in one-way ECSS. Lu et al. [20] proposed a bi-level nonlinear model to study the pricing and relocation problem. Combinations of different pricing strategies and relocation schemes were analyzed through case studies. Xu et al. [21] used reinforcement learning technology to study the order-scheduling problem, and the goal was to maximize instant rewards and future profit. Lyu et al. [22] studied the multi-period multi-objective online ride-matching problem. They developed an efficient online matching policy to balance the trade-offs among multiple goals. Özkan and Ward [23] proposed a linear-programming-based matching policy that especially accounts for passenger patience, with the goal to maximize the total number of total passengers being served. Hu and Zhou [24] studied the dynamic matching where, if the driver or passenger waits for too long, either of them may leave the platform.

The matching time interval and matching distance are two important factors affecting results in an online matching system. More orders will be fulfilled if the platform extends the matching time interval, but some users may leave the platform if the matching time interval exceeds their patience. Meanwhile, the pick-up distance will be reduced with a shorter match radius, but the matching rate may decrease as well. Bian and Liu [25] considered the individual requirements of users for different inconvenient factors, including waiting times, to determine the optimal matching between passengers and vehicles. Yang et al. [26] proposed to segment the various stages of the online matching process in the ride-sharing market. Abdolmaleki et al. [27] proposed an optimization problem with consistency constraints to synchronize the schedules in the transportation network so that the total waiting time for users’ transferring is minimized.

2.3. User Flexibility

User flexibility was also considered in our one-way ECSS. Correia et al. [28] proposed a model measuring the impact of user flexibility on the vehicle-assignment problem in a one-way CSS. Stiglic et al. [29] replaced the original target point with meeting points where the user can get on and off the vehicle within a certain distance from the original target point. A combination of spatial and temporal flexibility was considered to optimize the vehicle assignment at the same time [30]. A time window was set at the beginning and end of the trip, while locations within a certain radius of the original target point were considered as acceptable. The effect of flexibility on the car-sharing system can be summarized in some parts: increasing the number of matched users, improving vehicle utilization and the number of requests fulfilled, and reducing costs and the fleet size [8].

Taking the key factor that an EV’s trip mileage is limited by battery level, Zhang et al. [31] enabled users to finish longer trips through driving two vehicles in sequence. A new time–space–battery network flow model was proposed to find the best vehicle assignment and relaying decisions so as to achieve higher vehicle utilization.

As far as we know, there are few works on researching the influence of user waiting time on EV assignment. In this study, an EV assignment model with a waiting-time policy was proposed. When a user enters the platform, he provides his own maximum waiting time. The platform will offer corresponding subsidies to users who are agree to wait for a period of time. We enabled EVs to be charged during the waiting time so that more EVs are feasible to the user. Then, the platform makes an assignment between users and EVs. We introduced user utility to indicate whether users will accept the real departure time given by the platform and proposed a bi-level model to solve it taking into account the subsidies and the length of the waiting time.

3. Methodology

A one-way ECSS was considered in our study, especially with the waiting-time policy. For every trip, one EV can only be picked up at the original station and dropped at the destination station. The platform provides a certain subsidy to a user if an EV cannot meet his need. The user decides whether to wait or leave based on the utility influenced by his actual waiting time and subsidies. In the initial condition, all EVs were assumed to be charged at stations. Some assumptions are provided as follows:

• The short and equal time intervals were chosen in our ECSS model. The trips between two time intervals were calculated into the later time point. For example, if the time interval is 15 min, it means that trips between 10:01 and 10:14 are classified as the trips at 10:15.
• The platform only makes operation decisions at the end of each time interval, and the time at which trips and an EV’s status change during this time interval was set to the end of the interval.
• There is a fixed number of parking spots in a station, and all of them are equipped with the same charging equipment. For each station, the amount of EVs must be smaller than the number of its parking spot capacity.
• A user provides the information of the origin station, the destination station, and the expected departure time to the platform. We assumed all trip demands are known in advance before daily operation.
• The journey time between two stations was assumed to be unchanging, symmetric, and only determined by the origin and destination stations throughout the day.

In this section, the EV assignment model is proposed at first. Then, when we consider user flexibility, users’ waiting time and utility are introduced in the EV assignment model with the waiting-time policy. A bi-level programming was proposed to seek the optimal assignment considering the platform profit and users’ utility with the waiting-time policy.

3.1. The EV Assignment Model

The EV assignment model is considered at first. In the basic situation, when the platform gets total trip demands before operations, it becomes a question of how to assign the available EVs to the users. Only when the battery level of the EV can meet the minimum power consumption of the user’s trip can the EV can be allocated to the user; otherwise, the user’s trip demand will be rejected.

Let N be the set of stations, R the set of trip demands, and V the set of EVs. For every $n\in N$, there are some $r\in R$ and $v\in V$ that are located in n. An optimization problem was formulated to maximize the total profit of the platform so as to solve the EV-assignment problem, Let $\mathrm{\Theta }=\{1,2,\dots ,T\}$ be the discrete time points over a day. Referring to the method in [31], the battery levels were discretized by mapping any battery level $l\in [ka,(k+1\left)a\right)$ to $ka$ where a is the battery unit, so we took $\mathcal{L}=\{0,a,2a,\dots ,1\}$ as the discrete battery level. We defined $R_t$ as the set of trips with actual departure time t and $V_t$ as the set of EVs at time t. It was assumed that the platform and users can schedule and make decisions in a very short time, so the time difference can be ignored. For each trip r, $h_r$ was defined as the time at which the user schedules the request. Based on the assumptions mentioned earlier in this section, trips generated between $t_1$ and $t_2$ were attributed to trips at time $t_2$. So, we could get $h_r$ as shown in (1), where $t_r$ is the time at which trip r is generated.

$$h_r=t_2,if{t}_r\in [t_1,t_2),\forall r\in R,\forall t_1,t_2=1,2,\dots ,T$$

(1)

For each $v\in V_t$, there were two corresponding parameters, which were its battery level $l_v^t$ and its station $s_v^t$ at time t. Besides, we used $c_v^t$ to denote the charging state of v at time t. If $c_v^t=1$, it means v is in the charging state. We assumed that EVs will be charged as soon as they reach the destination station. If $c_v^t=0$, it means v is not in the charging state; that is, v is in use for a trip. We defined the $\Delta$ as the charging rate, $\eta$ as the consumption rate, and $\zeta$ as the length between two time intervals. Then, the battery level $l_v^t$ can be expressed as follows.

$$\begin{array}{cc}{l}_v^t=\{\begin{array}{cc}\min (1,l_v^{t-1}+\Delta ·\zeta ),\hfill & \hfill \mathrm{if}{c}_v^t=1\\ l_v^{t-1}-\eta ·\zeta ,\hfill & \hfill \mathrm{if}{c}_v^t=0\end{array} ,\hfill & \hfill \forall t=1,2,\dots ,T\end{array}.$$

(2)

For each trip r, there will be an origin station $o_r$ and a destination station $d_r$. For each $v\in V_t$, we can record its last served trip $r_v^f$. Thus, the dynamic change of the station of EV can be expressed in (3).

$$\begin{array}{cc}{s}_v^t=\{\begin{array}{cc}{s}_v^{t-1},\hfill & \mathrm{if}{c}_v^t=1\mathrm{and}{c}_v^{t-1}=1\hfill \\ d_{r_v^f},\hfill & \mathrm{if}{c}_v^t=1\mathrm{and}{c}_v^{t-1}=0\hfill \\ \mathrm{null},\hfill & \mathrm{if}{c}_v^t=0\hfill \end{array}\hfill & \hfill , \forall v\in V,\forall t=1,2,\dots ,T\end{array}.$$

(3)

We used the EV-charging state to analyze the station of the EV. When the EV was in the charging state at time t, if it was also in the charging state at time $t-1$, its station remained unchanged; if not, it means that the EV completed its last trip at time t so that its station is the destination station of the last trip.

For each $t\in \mathrm{\Theta }$, $r\in R_t$, and $v\in V_t$, we used $x_t^{r,v}$ to denote the decision of whether to match trip r with EV v at time t. Meanwhile, considering the limit of parking spots, we defined the ${\kappa }_n^t$ as the used spots of station n at time t. ${\mathrm{\Lambda }}_n^t$ was defined as the set of trips with completion time t and destination station n, where $f{t}_r$ is the completion time of trip r. Thus, the dynamics of the station spots is shown in (5).

$${\mathrm{\Lambda }}_n^t=\{r\in R|d_r=n,f{t}_r=t\}$$

(4)

$${\kappa }_n^t={\kappa }_n^{t-1}+\mathrm{card}\left({\mathrm{\Lambda }}_n^t\right)-\sum _{\begin{array}{c}v\in V_t\\ v_s^t=n\end{array}}{x}_t^{r,v},\forall n\in N$$

(5)

In the base situation, $R_t$ equals to the set of all trips collected in the time interval of time t. Let ${\mathrm{\Gamma }}_t\subseteq {\mathbb{R}}^{|R_t|\times |V_t|}$ be the available matching set between trips and EVs at time t. A trip r can be matched to EV v only if the battery level $l_v^t$ minus the battery consumption $l_r$ is greater than safety threshold $\tau$. The set ${\mathrm{\Gamma }}_t$ can be formulated in (6).

$$\begin{array}{c}{\mathrm{\Gamma }}_t=\left\{(r,v)\left|\begin{array}{cc}{l}_r+\tau \le l_v^t,\hfill & \forall r\in R_t,\forall v\in V_t\hfill \\ s_v^t=o_r,\hfill & \forall r\in R_t,\forall v\in V_t\hfill \end{array}\right.\right\},\forall t=1,2,\dots ,T\hfill \end{array}$$

(6)

The first constraint in (6) shows the battery constraint of matching between EVs and trips. The second constraint requires the EV to be in the same station as the trip’s origin station. Therefore, the matching set ${\chi }_t$ at time t can be formulated as in (7).

$$\begin{array}{cc}{\chi }_t=\left\{x_t^{r,v}\in {\mathbb{R}}^{|R_t|\times |V_t|}\left|\begin{array}{cc}\sum _{v\in V_t}{x}_t^{r,v}\le 1,\hfill & \forall r\in R_t\hfill \\ \sum _{r\in R_t}{x}_t^{r,v}\le 1,\hfill & \forall v\in V_t\hfill \\ {\kappa }_n^t\le {\kappa }_n,\hfill & \forall n\in N\hfill \\ x_t^{r,v}\in \{0,1\},\hfill & \forall (r,v)\in {\Gamma }_t\hfill \\ x_t^{r,v}=0,\hfill & \forall (r,v)\notin {\Gamma }_t\hfill \end{array}\right.\right\},\hfill & \hfill \forall t=1,2,\dots ,T\end{array}$$

(7)

The first set constraint requires that one trip can be assigned to at most one EV, and the second one requires that one EV can be assigned to at most one trip. The third one constrains the relationship between the assignment and parking spots for every station. The decision variables and parameters used in our study are listed in

Table 1. The notations.

Sets	Definition
N	Sets of stations.
R	Sets of trips.
V	Sets of EVs.
$\mathrm{\Theta }$	Sets of discrete time points.
$\mathcal{L}$	Sets of discrete battery levels.
$R_t$	Sets of trips with actual departure time t.
$V_t$	Sets of EVs at time t.
${\mathrm{\Lambda }}_n^t$	Sets of trips with completion time t and destination station n.
${\mathrm{\Gamma }}_t$	Sets of available matching at time t.
${\mathrm{\chi }}_t$	Sets of actual matching at time t.
${\mathrm{\Psi }}_t$	Sets of available matching with waiting time at time t.
${\mathsf{\Pi }}_t$	Sets of actual matching with waiting time at time t.
Parameters	Definition
$l_r$	Battery consumption of trip r.
$l_v^t$	Battery level of EV v at time t.
$c_v^t$	Charging state of v at time t.
${\kappa }_n^t$	The used spots of station n at time t.
$h_r$	The time at which the user schedules the request.
$l_v^t$	The battery level of EV v at time t.
$s_v^t$	The station of EV v at time t.
$\tau$	Safety battery level.
$\alpha$	Profit rate.
$s_r$	Subsidy to trip r.
$\beta$	Loss rate.
$\Delta$	Charging rate.
$\eta$	Consumption rate.
$\zeta$	Length between two time intervals.
Decision Variables	Definition
$x_t^{r,v}$	Decision of whether to assign trip r to EV v at time t.
$w_r$	Waiting time of trip r.

. The platform has the following assignment problem in the base case.

The EV assignment model (EVAM)

$$\max \sum _{t=1}^T\sum _{r\in R}\sum _{v\in V}{x}_t^{r,v}·p_{r,v}$$

(8)

subject to:

$$x_t^{r,v}\in {\chi }_t,\forall t=1,2,\dots ,T$$

(9)

The objective function (8) is the total profit of the ECSS. The original profit of the trip was determined by the information of trip demand and EVs. It can be obtained from the platform as known information in actual numerical experiments. The key of EVAM is how to assign trips and EVs to maximize the total profits of the platform. We regarded $p_{r,v}$ as the original profit of if EV v was assigned to trip r. According to the characteristics of EVs, the profit of a trip is a proportional function of the travel time. Thus, the profit of a trip from the original station to the destination station is $p_{r,v}=\alpha ·m_r^v$, where $m_r^v$ is the trip duration of EV v and $\alpha > 0$ is the profit rate. Constraint (9) requires that the decision variables must be in the available matching set.

3.2. The EV Assignment Model with Waiting Time

It is a significant problem that the EV’s battery cannot meet the need of the user’s trip sometimes, resulting in user churn. We proposed a new kind of operation policy considering the user’s waiting time. In this section, we introduce the user’s utility to indicate whether users wait or leave. If a user agrees to wait for a period of time, then the platform will offer subsidies to him. Considering the actual departure time and subsidies provided by the platform, the user can weigh his own utility to make the decision whether to accept the assignment or not. The EV assignment model with the waiting time was proposed.

To measure the user’s acceptance of the waiting time, the user’s utility is introduced in this article. The utility function is a concept in microeconomics that is usually used to represent the association between the utility gained by a consumer and the goods consumed. It shows the satisfaction degree that consumers obtain from the consumption of goods. In this study, we defined the user’s utility as a function of the user’s actual waiting time and subsidies from the platform. The general form of the utility function is shown in (10) to demonstrate the variation of utility with time, where $w_r=(t-h_r)$ is the waiting time of trip r till time t and $\beta$ is the loss rate to measure the the loss of users per unit of waiting time. It is the user’s utility that decides whether to accept the assignment or not.

$$U_r^t=s_r-\beta ·(t-h_r),\forall r\in R,\forall t\ge h_r$$

(10)

Let us take a simple case for an example as shown in Figure 1. There are three EVs at a station: EV A with battery level $L_A=40\%$, EV B with $L_B=50\%$, and EV C with $L_C=70\%$. The charging rate of all three EVs is 2% per minute. So, it is easy to obtain that $T_A=10\min$ and $T_B=5\min$. A user requests a trip that requires a battery consumption of 60%. It is obvious that EV A and EV B cannot meet the need of the user while EV C is available for the user.

Under the waiting-time policy, the platform offers the subsidy to users who agree to wait for a certain time. Users can weigh their own utility considering the income from the subsidy and the loss from the waiting time arranged by the platform. For one user, if the utility of two options are the same, we believe the user will choose to stay on the platform. Besides, if there are multiple EVs that are same for the user, an EV will be randomly selected and assigned to him. If the user still chooses to stay in the platform, the EVs will be continuously charged during the waiting time. Then, after the user’s waiting time, some EVs can meet the user’s needs.

We regarded the maximum waiting time of the user as $T_1$. If $T_1=6\min$, it means that the user agrees to wait for 5 min. It is obvious that $T_B<T_1$, so EV B is able to serve the user. If the user agrees to wait for 12 min, then EV A and EV B are both available to the user. At this time, all three EVs are available to the user. If the platform decides to assign EV A or EV B to the user, it needs to provide the user with certain subsidies, then the user will calculate his own utility based on the subsidy and the actual waiting time. If the utility is less than 0, the user will leave the platform, leading to the loss of users. If the platform decides to assign EV C to the user, it does not need to provide subsidies to the user, and there is no need to worry about users leaving. If the platform assigns an EV with a higher battery level to the user, when other users with more battery consumption enter the platform, the left EVs with lower battery level either cannot meet their needs or users are unwilling to wait too long to leave the platform, which results in greater loss of total profit.

Let us formulate the problem of EV assignment with waiting time. With the waiting-time policy, $R_t$ consists of two parts: one for trips that are assigned without waiting collected in the time interval of time t and the other for previous waiting trips that are assigned to depart at time t. We denoted $s_r$ as the subsidy to the trip r provided by the platform. Suppose that every user has a maximum acceptable waiting time and that users are homogeneous. For the convenience of calculation, we regarded the users’ maximum acceptable waiting time as obeying the uniform distribution $w_r^{max}\sim U(0,\sigma )$, where $\sigma$ is the upper limit of the maximum waiting time. We extended the EVAM model to a bi-level model of which we recalculated the feasible assignment between trips and EVs and then assigned EVs to users.

We denoted ${\mathrm{\Psi }}_t$ to show the dynamics of availability between EVs at stations and trips, and it is formulated in (11). In the first constraint, the utility function (10) was used to demonstrate the dynamics of user request under the waiting policy. If $U_r\ge 0$, the user request will stay on the platform, otherwise it will disappear from the platform. The right side of the second constraint $l_v+\Delta ·(t-h_r)$ shows the the dynamics of the battery state of EVs during the waiting time.

$$\begin{array}{c}{\mathrm{\Psi }}_t=\left\{(r,v)\left|\begin{array}{ccc}{U}_r\ge 0,\hfill & \forall r\in R_t\hfill & \\ l_r+\tau \le l_v^t+\Delta ·(t-h_r),\hfill & \forall r\in R_t,\forall v\in V_t\hfill \\ s_v^t=o_r,\hfill & \forall r\in R_t,\forall v\in V_t\hfill \end{array}\right.\right\},\forall t=1,2,\dots ,T\hfill \end{array}$$

(11)

From the platform side, we believe that all EVs at the same station can be assigned to users whose travel starts at that station, so the shortest waiting time of the user is the charging time required to meet the travel need by the vehicle with the largest power at that station.

The EV assignment model with waiting time (EVAMT)

(Upper Level)

$$\max \sum _{t=1}^T\sum _{r\in R}\sum _{v\in V}{x}_t^{r,v}·(p_{r,v}-s_r)$$

(12)

subject to:

$$x_t^{r,v}\in {\mathsf{\Pi }}_t,\forall t=1,2,\dots ,T$$

(13)

$$\begin{array}{c}\hfill \mathrm{where}{\mathsf{\Pi }}_t=\left\{x_t^{r,v}\in {\mathbb{R}}^{|R_t|\times |V_t|}\left|\begin{array}{cccccc}& \sum _{v\in V_t}{x}_t^{r,v}\le 1,\hfill & & \forall r\in R_t\hfill & & \\ & \sum _{r\in R_t}{x}_t^{r,v}\le 1,\hfill & & \forall v\in V_t\hfill & & \\ & {\kappa }_n^t\le {\kappa }_n,\hfill & & \forall n\in N\hfill & & \\ & x_t^{r,v}\in \{0,1\},\hfill & & \forall (r,v)\in {\mathsf{\Psi }}_t\hfill & & \\ & x_t^{r,v}=0,\hfill & & \forall (r,v)\notin {\mathsf{\Psi }}_t\hfill & & \end{array}\right.\right\}\end{array}$$

(14)

(Lower Level)

$$\max \sum _{t=1}^T\sum _{r\in R_t}[s_r-\beta ·(t-h_r)]$$

(15)

subject to:

$$\begin{array}{cc}{l}_r+\tau \le l_v^{t,max}+\Delta ·(t-h_r),\hfill & \hfill \forall r\in R_t,\forall v\in V_t^r\end{array}$$

(16)

$$\begin{array}{cc}t-h_r\le w_r^{max},\hfill & \hfill \forall r\in R_t\end{array}$$

(17)

$$\begin{array}{cc}0\le t-h_r,\hfill & \hfill \forall r\in R_t\end{array}$$

(18)

The objective function (15) is the sum of utilities of all trips. It consists of the difference between platform subsidies and the loss caused by the waiting time. We assumed there is no competition among different users for EVs. The optimization was done from the platform perspective, so the utility of the whole user group should be maximized rather than the utility of each user. Constraint (16) requires that after being charged for the user’s waiting time, the EV in the start station of trip r with the highest power $l_v^{t,max}$ can meet the trip battery consumption. It indicates the lower limit of the waiting time, where $\Delta$ is the charging rate. Constraint (17) requires that the waiting time of the user’s trip r cannot exceed the maximum waiting time accepted by the user. Constraint (18) makes sure that the waiting time is non-negative.

When we find the best waiting time for each trip, users will weigh their utility considering the subsidy and waiting time. If it is negative, the user will leave the platform. If it is positive, the user will wait for a certain time and accept the assignment. The set (14) presents the feasible matching set between trips and EVs, where ${\mathrm{\Psi }}_t$ is the set of trips with positive utility after its waiting time. Then, we decided how to assign trips to EVs. The objective function (12) is the total profit of EVAMT. Constraint (13) requires that the decision variables must be in the feasible matching set.

4. Numerical Experiments

In this section, we evaluate the performance of EVAM and EVAMT through numerical experiments. We refer to some settings of the platform called EVCard (https://www.evcard.com/, accessed on 27 March 2021), an EV car-sharing company in China, so that a more practical numerical study can be designed. The time window was set from 4:00 to 24:00 every day, and the rest of time was left for vehicles’ relocation; thus, we obtained 80 fifteen-minute intervals in our model.

4.1. Settings of Numerical Experiments

On the perspective of EV, we took $\mathcal{L}=\{0,0.1,0.2,\dots ,1\}$ as the battery discrete points. When fully charged, an EV can last for 150 min continuously at an average speed of 60 km per hour. The battery consumption was assumed to be stable and constant, so the battery consumption of the trip increased as the trip time increased and was in a proportional function. With reference to the setting in [31], we also assumed that an EV’s battery can be charged from 0% to 100% in 150 min through a normal charging outlet. At the start of the daily operation, four EVs were available at parking spots for every station, and the initial power of an EV obeyed the uniform distribution between 50% to 100% considering the usage.

We used an EVCard station distribution for reference and selected some stations in Jiading district and Pudong district, Shanghai, China. We simulated the EV battery demands for intra-regional trips and inter-regional trips according to the distance. As for trip demands, since we could not obtain the real trip demand data from EVCard, the data of EVO, a one-way car-sharing company in Canada, were used in our study to imitate the trip demands. However, since EVO is a hybrid and since the EVO site locations are not known, we used the location of stations of the EVCard. Ref. [32] gathered the data of EVO in Vancouver (Canada) and nearby urban area for more than one year. We selected the EVO trip demands data in a certain area and a month. We divided them according to a certain period of time; then, we obtained the following pie chart.

It can be seen from Figure 2 that the travel demands were mainly concentrated in the two time intervals of 11:00–16:00 and 17:00–20:00, while there was less travel demand in the early morning and night. This distribution corresponds to our knowledge that users usually drive EVs during the day. As for stations, we first aggregated trips of the stations in a certain area and then we took the weighted sum of trips from nearby stations to station n as the attractiveness of station n. Based on the above trip distribution, the roulette wheel selection scheme [33] was used to generate our trip demands. The basic flow of the our algorithm in this study is shown in Algorithm 1.

Algorithm 1: Bi-level programming solution

1: Generate all trips (i,j,$l_r$,$w_r^{max}$) for $i,j\in N$, $l_r\in \mathcal{L}$ and $w_r^{max}$∈ (0,$\sigma$). 2: Generate all EVs (n,$l_v$) for $n\in N$ and $l_v\in \mathcal{L}$. 3: Randomly give a feasible solution for the lower-level programming. 4: The solution given by the lower-level programming is used as the input of the upper-level programming so as to obtain the optimal solution of the upper-level programming. 5: Bring the EV assignment solutions of the upper-level programming into the lower-level to get the optimal solution of user utilities in the lower-level programming. 6: If the result meets the termination condition of the iteration, then terminate; otherwise, go to step 4.

In our study, the profit rate was set to be $\alpha =1$ and the loss rate for waiting time to be $\beta =1.2$. In order to eliminate the influence of different units of measure, we recalculated the profit of travels in proportion to the maximum value of ten. The subsidy of the platform to users $s_r$ is a piecewise function of the user waiting time $w_r$. We assumed that $\sigma =4$, and when the user’s waiting time was between 0 and 1, the platform subsidized $s_1$; when between 1 and 2, then $s_2$; when between 2 and 3, then $s_3$; when between 3 and 4, then $s_4$. In our numerical experiments, we set $s_1=0,s_2=1,s_3=2, \mathrm{and} s_4=3$.

4.2. Assessment of EV Assignment and Waiting Time

In our bi-level programming model, the lower-level model aimed to maximize the user’s utility and obtain the user’s real waiting time. The upper-level model maximizes the total profits of the platform to obtain vehicle-assignment results. To measure the performance of the EV assignment model with the waiting-time policy more clearly, we defined several indicators.

⋄

Total profit: Although the policy was to provide users with a better experience, its essence is to increase the total profit of the platform.

⋄

Trip fulfillment rate: Trips that are assigned to any EVs are regarded as fulfilled. We denoted this indicator as trips fulfilled divided by all trip demands.

⋄

Utilization per EV: We took this indicator as the average travel time of an EV during one-day operation. It was used to measure the truly used situation of EVs.

We considered some situations with different stations, EVs, and trips under the two polices of EVAM and EVAMT. Some numerical experiments were conducted, and the results are shown in

Table 2. Performance of two assignment polices.

Station	EV	Trip	EVAM			EVAMT
			Profit	Fulfillment	Utilization	Profit	Fulfillment	Utilization
3	12	328	503	68.64%	44.75	536	72.57%	51.66
10	40	833	1463	54.50%	40.23	1609	58.96%	46.98
20	80	1676	3415	52.68%	41.44	3715	57.33%	47.51
30	120	2447	4579	53.82%	40.95	4914	55.28%	46.07

.

We considered four different numbers of stations, and it is obvious that EVAMT takes advantage in all three indicators in all the cases. For the platform, it is the total profit that it is most directly concerned with. Compared with EVAM, the total profit of EVAMT improved significantly. Meanwhile, the average usage time of an EV raised significantly, reducing the loss caused by parking at stations. Moreover, the order fulfillment rate also increased, which improves the user experience, enhances user stickiness, and brings more possibilities for future platform operations.

Take the situation with 30 stations as an example. Under the waiting policy, the EVAMT can bring a 7.32% increase in profit, a 2.71% increase in the trip-fulfillment rate, and a 12.50% increase in EV utilization. The results of the above numerical experiments give us an insight that EVAMT has a better performance than EVAM in different station scales.

5. Conclusions

In this study, we studied the vehicle-assignment problem in one-way ECSS. We proposed two EV assignment models to make the best vehicle assignment and waiting decision. Based on actual observations and research, we found that the battery level of EVs greatly limits the vehicle-assignment policy. For the platform, when EVs at the user’s departure station cannot meet his travel need, none of the EVs are available to him. It not only affects the platform’s profit but also leads to a decline in the user experience. However, in the actual situation, some users are willing to wait. We focused on this situation in this study and proposed a waiting-time policy. The platform will provide the actual departure time and certain subsidies to the users who are willing to wait, and the users decide whether to accept based on the their own utility. Then, the platform assigns EVs to users.

Based on the feasibility constraints of EVs and trips, we performed the allocation of EVs in the EVAM model for the base case. In the EVAMT model, we introduced the user’s utility and take waiting time into consideration. A bi-level programming was proposed in EVAMT, where the upper level aims at maximizing platform profit from the perspective of the platform, and the goal of the lower level is to maximize users’ utilities from the user’s perspective. As far as we know, it is the first time that the number of available EVs varying with the user’s waiting time was taken into consideration. Moreover, the user utility was also included in our model to decide the optimal waiting time.

Through numerical experiments, we demonstrated that the proposed EVAMT model has a more satisfactory assignment in various situations. With optimized EV assignment and a waiting-time policy, the platform achieved a higher total profit, trip fulfillment rate, and EV utilization, which further confirms its superiority. In the various scenarios set in this study, compared with EVAM, the total profit of the platform increased by 8.2% on average; the order fulfillment rate increased by 6.4%; and the average vehicle usage time increased by 14.8% in EVAMT.

The improvement of these indicators not only brings more profits to the platform but also shows a better experience for users in general. It lays a user foundation for the future development and operation of the platform. However, this study mainly considered the waiting-time policy in the base case. The waiting-time policy involving the relocation case can be considered in the future. We can also study the spatial flexibility of users’ trips and add the time from the user’s current location to the start station to the charging time of the assigned EV.