Integrated optimization of planning and operation of a shared automated electric vehicle system considering the trip selection and opportunity cost

1.   Introduction

The shared vehicle system (SVS) is an emerging and environmentally friendly mode of transportation that bridges the gap between public transit and private cars. It effectively reduces private car usage, vehicle emissions and mitigates traffic congestion ^[1]. Some research suggests that the market for SVS services is expected to reach 38.61 billion dollars by 2030 ^[2].

However, as a novel mode of transportation, SVS faces numerous challenges. From the demand side, the prevalent station-based, one-way SVS suffers from uneven user demand. Over time, this results in vehicles becoming concentrated in certain zones, leading to a spatial and temporal imbalance that diminishes vehicle utilization throughout the day. This reduces the overall service level and undermines potential profits for SVS operators ^[3]. On the supply side, the uneven distribution of vehicles results in congestion at certain stations and scarcity at others ^[4]. These issues hinder the system's ability to promptly and effectively respond to user reservations.

With the rapid advancement of technology, autonomous driving has become increasingly mature. By integrating autonomous vehicles (AVs) into the system, shared autonomous vehicle system (SAVS) can transition from a "people look for vehicles" model to a "vehicles find people" model, enabling an efficient response to user demand ^[5].

Furthermore, electric vehicle (EV) technology has matured significantly, and nearly all major vehicle manufacturers offer their own electric vehicle models ^[6]. EVs operate in a more environmentally friendly manner, producing zero direct tailpipe emissions. Electrified drive is expected to be the dominant mode for AVs. However, due to the limitations of current battery technology, electric vehicles often require significant time for recharging at stations before they can meet the energy requirements for subsequent trips ^[7].

Consequently, the integration of SVS, AVs and EVs has garnered significant attention from scholars, leading to the emergence of the shared autonomous electric vehicle system (SAEVS) ^[8].

1.1.   Literature review

In the last few years, SVS have attracted considerable attention. Several strategies have been proposed to enhance the overall efficiency of CSSs over the past few years and can be classified into the following two categories: (ⅰ) Operational levels and (ⅱ) planning levels.

1.1.1.   Operational level

At the operational level, operators aim to alleviate the supply-demand imbalance and enhance the overall profitability of the SVS. To this end, they need to adopting appropriate relocation strategy or other operational strategies, taking into account the SVS characteristics ^[9,10].

The relocation strategy necessitates the SVS operator to draw up vehicle relocation plans, specifying the time and stations for vehicles to transit between different stations. Nair and Miller-Hooks ^[11] proposed a mixed-integer programming model with joint chance constraints to generated partial redistribution plans based on each station's current inventory level to satisfy user demand. Nourinejad et al. ^[12] developed a model based on two integrated multi-traveling salesman problems to address the joint optimization problem of vehicle relocation and staff rebalancing. Repoux et al. ^[13] introduced a new proactive relocation policy based on Markov chain dynamics that utilizes reservation information to predict the stations' future states and make a relocation decision.

For an electric sharing vehicle system (ESVS), the relocation problem is more complex because the vehicle movement is restricted to the battery capacity. Boyaci et al. ^[14] proposed a simulation-optimization framework to optimize the vehicle and personnel relocation in an ESVS. The optimization module was adopted to generate relocation solutions. The simulation module was used to check the battery level feasibility of the solution and then update the charging constraint if infeasible. Zhao et al. ^[15] developed a time-space network model for an integrated EV rebalancing and staff relocation problem. Then, a Lagrangian relaxation-based algorithm was designed to solve this problem.

Although operator relocation can alleviate the imbalance of the SVS, it is limited by the number of vehicles, relocation cost and other factors. Therefore, some studies have introduced trip selection to improve the efficiency of the SVS ^[16]. Trip selection refers to the process of choosing a specific trip or journey from the available options within a transportation system. Trip selection helps SVS serve beneficial trips (to increase one-rental income or balance supply and demand) based on forecasted or known needs ^[17].

Furthermore, SVS as an emerging mode of transportation, are chosen by users as a means of travel. The choice behavior is influenced by factors such as travel time, price and transportation convenience, leading users to select between shared cars, private cars and public transportation. Huang et al. ^[18] and Xu et al. ^[7] employed a binary Logit model to quantify user choice behavior between conventional fuel-powered or electric shared autonomous vehicles and private cars. However, there is a lack of literature that considers user choice behavior and analyzes from the standpoint of opportunity cost. For example, if the user demand is not met, it may lead users to permanently switch from SVS to other modes of transportation.

1.1.2.   Planning level

In this stream, the relevant studies mainly focus on the fundamental design of the SVS, planning including strategic and tactical levels ^[19]. The strategic planning involves the determination of the locations and capacity (size) of parking/charging facilities. The tactical problems are related to optimize the fleet size and distribution of vehicles. The main goal of the planning problems is to minimize the cost of infrastructure and to maximize the revenue obtained from satisfied user requests to the greatest extent possible ^[20].

For the planning problem of the SVS, Hu and Liu ^[21] introduced a hybrid queuing network model to depict the network of a carsharing system. Building upon this model, they proposed an optimization framework that takes into account road congestion to determine the station capacities and fleet size. Brandstatter et al. ^[22] proposed a two-stage, stochastic programming model based on random user demand to optimize the station location. Xu et al. ^[23] assumed that vehicles can only be used once they are fully charged and based on the concept of aggregation modeling. They established a nonlinear integer programming model to determine the fleet size of a shared car system. Hua et al. ^[24] jointly optimized the infrastructure planning (e.g., charging station location and initial fleet distribution) and dynamic fleet operations (e.g., vehicle assignment and relocation) under time-varying uncertain demand. Then, an algorithm based on the Lagrangian relaxation and stochastic dual dynamic programming method was proposed to solve the multistage stochastic model.

A few studies have also paid attention to the aspects of SAEVSs, Miao et al. ^[6] developed a two-stage multi-objective optimization methodology with a non-dominated sorting genetic algorithm to design the service area and the allocation of charging infrastructures. Chen et al. ^[25] considered different demand scenarios and utilized a three-dimensional spatio-temporal state network to describe the variation of vehicle battery levels while operating between stations. They established a two-stage stochastic integer programming model to make decisions regarding fleet size and charging station configuration in a SAEVS.

1.2.   Focus of this study

In summary, the introduction of autonomous electric vehicles (AEVs) in shared vehicle systems can effectively address user demands and promote environmental sustainability. Despite this, existing research on station-based SAEVS is limited, as it primarily focuses on maximizing system profits from the supply side and does not sufficiently consider trip selection. Moreover, there is a notable gap in the literature when it comes to studying opportunity cost loss in the carsharing system.

Opportunity cost, a concept in economics, refers to the loss of potential gain from other alternatives when one particular alternative is chosen. Essentially, it is the cost of forgoing the next best option (Mohammad and Pierluigi ^[26]; Krishna ^[27]). In carsharing services, the operator's opportunity cost loss stems from the SAEVS's inability to respond to customer demand in a timely manner. This leads to customer attrition as they turn to other modes of transportation.

To address these issues, this paper tackles the integrated optimization problem of planning and operation strategy in large-scale SAEVS environments. It encompasses trip selection and opportunity cost considerations, with the objective of maximizing comprehensive profits. By employing a spatio-temporal state network modeling approach, an integer linear programming (ILP) model is developed to jointly determine vehicle relocation strategy, number of charging facilities and vehicle fleet size and its distribution. Additionally, a Lagrangian relaxation method is designed to solve the model. The efficiency of the proposed model and algorithm is validated through numerical experiments, and the impacts of various parameters, such as the opportunity cost loss coefficient, charging station power and cost, on system performance, are analyzed.

The major contributions of this paper are as follows:

1) Introducing the concepts of trip selection and opportunity cost. Trip selection ensures the allocation of vehicles to high-quality user reservation trips, thereby enhancing the operational efficiency and economic viability of SAEVS, and opportunity cost considers the potential cost of unsatisfied user demands.

2) Developing a ILP model for integrated planning and operation strategy optimization of SAEVS based on the spatio-temporal state network representation. This model accurately captures the vehicle spatio-temporal paths and battery level of vehicles during SAEVS operations. The planning level covers charging facility sizing, distribution and vehicle fleet considerations, while the operational level includes vehicle relocation and trip selection strategies.

3) Introducing a Lagrangian relaxation framework to address the curse of dimensionality in solving large-scale instances of the problem. This approach efficiently solves large-scale linear programming problems, provides upper and lower bounds on the duality gap, evaluates the quality of the current solution and ensures solution quality while achieving fast computation.

4) Real-world instances of the Chengdu are performed, showing the effectiveness of the proposed algorithm and further analyses the impact of different demand scenarios.

The remainder of this paper is organized as follows: The problem statement and spatio-temporal state network modeling method are provided in Section 2. The ILP model of the SAEVS is introduced in Section 3. Section 4 presents a Lagrangian relaxation framework for solving the developed model. In Section 5, we conduct a series of numerical examples to test the performance of the proposed model and solution approach. Finally, conclusions and further studies are presented in Section 6.

2.   Problem statement

2.1.   Description of SAEVS

In this study, we consider the network of a SAEVS with predetermined stations where each station is initially assigned a specific number of vehicles. During the operational phase, users can visit any station to pick up a vehicle and drop it at another one. Due to unbalanced demand, it is necessary for the SAEVS to dynamically relocate vehicles to parking stations experiencing higher demand, thereby ensuring a balanced distribution of vehicles throughout the network.

An illustrative example is shown in Figure 1, which presents an SAEVS consisting of three stations. There are 7 charging facilities, 5 electric autonomous vehicles (EVAs) and 10 reserved demands in the entire network. In the scenario of SAEVS without vehicle relocation and trip selection is not considered (see Figure 1(a)), if the initial vehicle allocation is unsatisfactory, only 3 reservations will be met under the limited vehicles and parking capacities. To address this problem, the operators need to assign vehicles to execute relocation tasks. Figure 1(b) shows that more reserved orders (9 orders) will be serviced when the vehicles are relocated. Furthermore, let us consider the trip selection strategy combined with the vehicle relocation, all reserved demand can be satisfied, resulting in a higher satisfaction (see Figure 1(c)). Therefore, considering vehicle relocation and trip selection has a significant impact on improving the operational efficiency of SAEVS.

The planning and operation strategy decision problem of SAEVS in our study aims to answer the following question: How many charging facilities and vehicles are required in each station of SAEVS. How to carry out vehicle relocation strategy to respond to customer demand.

2.2.   Graph representation

In this study, we formulate the dynamics of the SAEVS based on a spatio-temporal network. Spatio-temporal networks are widely used in the transportation network modeling ^{[28,29,30,31]}. Given all of that, the SAEVS can be represented by a spatio-temporal directed multigraph denote as G$\in$(S, L), where S represents a set of stations in the SAEVS, and each station $i, j\in S = \{\mathrm{1, 2}, \dots , n\}$. ${\bf L}$ represents links connecting station $i$ and station $j$, and each link ($i, j$) $\in {\bf L}$. Then, we extend the traffic network into a spatio-temporal network. Let ${\bf T} = ({t}_{0}, {t}_{0}+\delta , .., {t}_{0}+N\delta )$ represent a set of discretized time period of the whole operating time horizon. $\delta$ represent the time slices of two adjacent timestamp. In general, the smaller the time slices, the better it can reflect the actual operational conditions. However, considering the scale of the variables, we often cannot set the time slices too small as it may affect computational efficiency. Vertex ($i, t)$ represents the state of corresponding parking station $i$ at the current timestamp $t$. Spatio-temporal arc ($i, t$, $j, k$) represents a trip from origin station $i$ to origin station $j$ starting at time $t$ and ending at time $k$.

The example shown in Figure 2 demonstrates the spatio-temporal network of a vehicle relocation process presented in Figure 1(c). The traveling arcs in the constructed spatio-temporal network can be divided into two types: User reservation arcs and vehicle traveling arcs. Furthermore, to ensure spatio-temporal network flow balance, we introduce the (${i}_{\mathrm{O}}, {t}_{\mathrm{O}})$ and (${i}_{\mathrm{D}}, {t}_{\mathrm{D}})$ as the dummy origin and dummy destination in the spatio-temporal network.

The user reservation arcs represent that the users reserve vehicles from the origin station to the destination station at certain time (e.g., (1, ${t}_{0}$, 2, ${t}_{0}+2\delta$)). These arcs are according to the dynamic user demand that as the input date. The vehicle traveling arcs involve usage arcs, relocation arcs and waiting arcs. The usage arcs represent the vehicle are drive by users from one station to another (e.g., (1, ${t}_{0}$, 2, ${t}_{0}+2\delta$)). The relocation arcs represent the vehicle move from one station to another based on the relocation strategy (e.g., (3, ${t}_{0}$, 1, ${t}_{0}+\delta$)). The waiting arcs represents the vehicle dwell in stations (e.g., (1, ${t}_{0}+\delta$, 1, ${t}_{0}+2\delta$)).

Next, we expand the spatio-temporal network into a spatio-temporal-energy three-dimensional network. Let ${\bf E} = (0, {\rm{ \mathsf{ ε} }}, .., 2{\rm{ \mathsf{ ε} }}, {\mathrm{E}}_{max})$ represent a set of discrete battery level of the EVAs. ${\rm{ \mathsf{ ε} }}$ represents discrete battery levels between adjacent battery states, and ${\mathrm{E}}_{max}$ represents maximum capacity of the battery. Similarly, considering the spatio-temporal network parameters, we define the spatio-temporal- energy network vertex ($i$, $t$, $e$) to represent a vehicle at station $i$ at time $t$ battery state as $e$. The spatio-temporal- energy arcs ($i$, j, $t, k, e$, ${e}^{{{'}}}$) represent vehicles from origin station $i$ starting at time $t$ with battery level $e$ to origin station $j$ ending at time $k$ with battery level ${e}^{{{'}}}$. When EVAs, are operating within the system, their battery levels undergo changes. Then we set the ED represent the battery consumption rate per time slices. EC represent the represents the battery charging rate per time slice. $\Delta {E}_{(i, j, e)}$ represents the change of battery when EVA moves from station $i$ to station $j$ with battery level of $e$. If $i = j$, which represent the EVA is staying at a station for charging. During the charging process, the vehicle's battery level cannot exceed the maximum capacity ${\mathrm{E}}_{max}$.

The relationship expressing the variation in vehicle battery during changes in the spatio-temporal- energy network can be represented by Eqs (1) and (2). ${T}_{(i, j)}$ represent the traveling time of vehicle from station $i$ to station $j$.

The example shown in Figure 3 demonstrates the spatio-temporal-energy network formulation of a vehicle relocation process presented in Figure 1(c). The two-dimensional projection of the vehicle's spatio-temporal-energy traveling arcs in Figure 3 corresponds to the spatio-temporal trajectory arc of the EVAs in Figure 2.

3.   Model formulation

This section formulates a MILP to address the integrated optimization of the planning and operation strategy problems for SAEVS considering the opportunity cost and trip selection.

3.1.   Assumptions

1) The user demands reservations between different stations at different time periods are given, meaning the potential user demands is given;

2) When the SAEVS fails to meet user demands, the demand will shift from SAEVS to other public transportation modes, resulting in potential profit loss. Here, a coefficient for opportunity cost loss is given here. When the system fails to meet user demands, the opportunity cost loss incurred is equal to the potential profit associated with the unmet demand multiplied by the loss coefficient.

3) The shared vehicles in the SAEVS are AEV. The battery consumption of the vehicles is directly proportional to the travel time on the route, while the charging rate at the stations is directly proportional to the time the vehicles dwell at the station. Additionally, no dispatcher is required as the vehicles can autonomously schedule and move;

4) The capacity of a station is equivalent to the number of charging facilities available. When there are idle charging facilities at a station, vehicles returning to the station will directly charge at those facilities;

5) At the beginning of operations, vehicles park next to the charging facilities at the stations. In other words, the scale of charging facilities configured at each station is guaranteed to be greater than the initial number of vehicles stationed at the station.

3.2.   Symbol and description

The primary notation used throughout this paper is presented in Table 1 below.

3.3.   Mathematical model

3.3.1.   Objective function

In our study, we aim to construct an objective function for the SAEVS with the comprehensive profit of its operations as the primary goal. The objective function of SAEVS consists of two major components. The first part is revenue from the SAEVS which includes AEV rental income. In order to specify whether AEVs are operated by users or accept the relocation strategy to move autonomously, we introduce the user reservation satisfied arcs ${z}_{(i, t, j, k)}^{h}$, if ${z}_{(i, j, t, k)}^{h} = 1$, vehicle $h$ is picked up by a user from station $i$ at time $t$. The second parts include operation cost, opportunity cost and investment cost of the SAEVS. The operation cost represents the travel cost of AEVs, opportunity cost represents the economic loss caused by the potential shift of user demand to other transportation modes due to the absence of user demand, the amortized cost represent the amortized cost of AEVs and rental cost of charging facility.

The objective of the model is to maximize the operators' comprehensive profits considering opportunity costs. The objective function is as follows:

Furthermore, for the convenience of model solving we can transform the original problem to the minimization problem as shown below:

3.3.2.   Model constraints

Constraints (4) is used to keep the spatio-temporal network flow balance of the AEVs, ensuring a feasible spatio-temporal path ${x}_{\left(i, j, t, k, e, {e}^{{{'}}}\right)}^{h}$ for each vehicle $h$ in the spatio-temporal network. The constraints (5) represent the relationships between the number of initially allocated AEVs ${\mathrm{n}H}_{i}$ in the station $i$ and their traveling acres at the dummy origin nodes ${x}_{({i}_{O}, j{, t}_{O}, {t}_{0}, {e}_{O}, {E}_{max})}^{h}$; The constraints (6) represent the number of initial vehicles $\sum _{i\in \mathrm{S}}{\mathrm{n}H}_{i}$ in the SAEVS can't exceed the maximum number of fleet size ${H}_{max}$. The constraints (7) ensure that all AEVs satisfies reservation arcs ${z}_{(i, j, t, k)}^{h}$ at spatio-temporal arc $(i, j, t, k)$ is less than the reservations ${D}_{(i, t, j, k)}$. Constraints (8) indicate the relationship between variables X and Z, that is the user reservation arcs cannot exceed the number of vehicle traveling arcs. During the optimization process, constraints (7) and (8) are related to trip selection. Constraints (9) ensure that the number of EVs at the station is limited by the number of available charging facilities. The constraints (10) indicate the decision variable of the station capacity ${\mathrm{n}C}_{i}$ is not greater than the maximum station capacity ${C}_{max}$. Constraints (11) and (12) define the domains for the binary and integer variables.

4.   Model formulation

The ILP model proposed to address the integrated planning and operation strategy optimization problem is essentially a multi-commodity flow problem, which is an NP-hard problem ^[32,33,34]. It leads to computational challenges for large-scale real-world data sets. To tackle this computational challenge, we introduce a Lagrangian relaxation (LR) approach to solve the problem.

LR is a mathematical optimization technique used to solve complex optimization problems with multiple constraints. It is particularly effective for solving large-scale problems where finding an exact solution is computationally challenging ^{[35,36,37,38]}.

4.1.   Lagrangian relaxation model

In the proposed ILP model, constraints (8) and (9) are related to multiple decision variables, which increases the difficulty and time of calculation, so it is called complicating constraints. In particular, the constraints (8) are related to the variable ${x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h}$ and ${z}_{(i, t, j, k)}^{h}$. The constraints (9) are related to the variable ${x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h}$ and ${\mathrm{n}C}_{i}$.

Thus, we need relax these complicating constraints into the objective function (3b) and get the lower bound of the primal problem. In this subsection, we introduce two Lagranian multipliers $\boldsymbol{\alpha }$:{${\alpha }_{(i, t, j, k)}^{h}\ge 0{\}}_{\left(i, t, j, k\right)\in {{\bf A}}^{{{'}}}}$, $\boldsymbol{\beta }$:{${\beta }_{(i, t)}^{h}\ge 0{\}}_{\left(i, t\right)\in {\bf V}}$, by relaxed constraints (8) and (9) to construct the dualized Lagrangian function L (X, Z, nH, nC, $\boldsymbol{\alpha }$, $\boldsymbol{\beta }$) as follows:

To simplify Eq (13) and obtain the dual relaxation problem of the primal problem:

Subject to constraints (1), (2), (4)–(7) and (10)–(12), the complicating constraints are relaxed variables $\overline{\boldsymbol{X}}$, $\overline{\boldsymbol{Z}}$, $\overline{\boldsymbol{n}\boldsymbol{H}}$, $\overline{\boldsymbol{n}\boldsymbol{C}}$, are separated from each other in the relaxed problem. Then, the primal problem is essentially divided into three sub-problems (${F}_{h}, {F}_{z}, {F}_{c}$) that respectively determine the AEV routing, AEV-user assignment plans, station charging facility configuration.

Subproblem 1.

The first set of subproblems is related to vehicle traveling arc ${x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h}$ for all $h\in {\bf H}$, as follows:

Subject to constraints (1), (2), (4)–(6), (11) and (12), by analyzing Subproblem 1, the constraints relevant to this problem include the auxiliary decision variable Eqs (1) and (2), the spatio-temporal flow balance constraint (4), the initial vehicle constraints (5) and (6) and the variable value constraints (12) and (13). Therefore, Subproblem 1 can be transformed into a set of $\left|{\bf H}\right|$ secondary subproblems, where each secondary subproblem can be viewed as a resource constrained shortest path problems.

Each secondary subproblem consists of two parts. The first part is the amortized cost that is fixed for each given vehicle $h\in {\bf H}$. The second part is the generalized traveling cost related to the routing paths of the AEVs in the constructed spatio-temporal network. Furthermore, to capture the EV battery charging and consumption dynamics, we extend the spatio-temporal-energy network by adding the charge-status dimension of battery levels. Then this problem can be solved to the optimum by some exact solution approaches. (e.g., dynamic programming, Mahmoudi and Zhou ^[38]).

We define ${C}_{(i, t, j, k)}^{h}:{CT}_{\left(i, j\right)}+{\beta }_{\left(i, t\right)}^{h}-{\alpha }_{(i, t, j, k)}^{h}$. ${C}_{(i, t, j, k)}^{h}$ represents the cost of vehicle $h$ traveling through spatio-temporal arcs $\left(i, t, j, k\right)\in {{\bf A}}^{{{'}}}$. Then, we let ${L}_{ite}^{h}$ record the traveling cost state of $h$ at spatio-temporal-energy vertex ($i, t, e$); ${PS}_{ite}^{h}$, ${PT}_{ite}^{h}$, ${PE}_{ite}^{h}$ record previous station, previous time and previous battery level on the shortest path from origin nodes to the given vertex spatio-temporal-energy vertex $(i, t, e)\in {\bf V}$ for vehicle $h\in$ H, respectively. Besides, set ${\boldsymbol{R}}_{h}$ record the spatio-temporal arcs that least-cost routing with least ${L}_{it\mathrm{e}}^{h}$ value. Then, we proposed a dynamic programming algorithm to solve this problem descript in Algorithm 1.

Subproblem 2.

The second set of subproblems is related to the demand satisfied reservations arc ${z}_{(i, j, t, k)}^{h}$ for all $h\in {\bf H}$ as follow:

Subject to constraints (7) and (12), the structure of Subproblem 2 is very simple that the exact optimal solution can be easily obtained as follows. For each spatio-temporal arc $\left(i, t, j, k\right)\in {{\bf A}}_{D}$, where ${{\bf A}}_{D} = \{\left(i, t, j, k\right)\in {\bf A}|{D}_{(it, jk)}\ne 0\}$, we define a set ${{\bf H}}_{\left(i, t, j, k\right)}^{\mathrm{*}} = \{{h}_{1}, {h}_{2}, \dots , {h}_{{D}_{(i, t, j, k)}}\}$ to denote the first ${D}_{(it, jk)}$ vehicles sorted by the values of their corresponding Lagrangian multipliers. The vehicles set ${{\bf H}}_{\left(i, t, j, k\right)}^{\mathrm{*}}$ include EVs $\forall eh\in {\bf E}{\bf H}$ and GVs $\forall gh\in {\bf G}{\bf H}$. We first sort the set of Lagrangian multipliers ${\alpha }_{\left(i, t, j, k\right)}^{eh}$ for $\forall h\in H$ from the smallest to the largest. Then, we pick the smallest ${D}_{(i, t, j, k)}$ multipliers and let the corresponding ${z}_{(i, t, j, k)}^{h}$ equal to 1. Repeating the process above for all the spatio-temporal arcs $\left(i, t, j, k\right)\in {\bf A}$, the optimal solution ${z}_{(i, t, j, k)}^{h}$ to Subproblem 2 can be represented as:

Subproblem 3.

The third set of subproblems is related to the station capacity ${\mathrm{n}C}_{i}$, as follows:

Subject to constraints (10) and (11), through analysis of the structure of Subproblem 3, it can be determined that the problem is a simple assignment problem. The exact optimal solution can be easily obtained as follows. If $CC-{\beta }_{\left(i, t\right)}^{h} < 0$, ${\mathrm{n}C}_{i} = {C}_{max}$, else if $CC-{\beta }_{\left(i, t\right)}^{h} > 0$, ${\mathrm{n}C}_{i} = 0$, then we can obtain the optimal solution of the Subproblem 3.

We can get the optimal value of the lower bound in the Lagrangian dual problem for the primal problem to solving the subproblem (13)–(18), the optimal objective of the relaxed problem (19) for a set of $\boldsymbol{\alpha }$, $\boldsymbol{\beta }$ can be obtained as follows:

Then, we can obtain the optimal value $\overline{\boldsymbol{X}}$, $\overline{\boldsymbol{Z}}$, $\overline{\boldsymbol{n}\boldsymbol{H}}$, $\overline{\boldsymbol{n}\boldsymbol{C}}$ of the relaxed problem, which can serve as the lower bound solution $LB\left(\alpha , \beta , \gamma \right)$ to the optimal value of the primal problem.

4.2.   Feasible solution

If the optimal solution of relaxation model is feasible for the primal problem, we have obtained the optimal solution to the primal problem. Otherwise, we apply a set of algorithms to find an upper bound for the primal solution. Specifically, a heuristic algorithm based on the greedy approach is introduced to adjust the three types of decision variables, thereby obtaining feasible solutions for the original problem. In simple terms, the algorithm first removes the vehicle traveling arcs that do not satisfy the constraints or result in negative profit. Then, it adds these vehicle traveling arcs back into the spatio-temporal network with the objective of maximizing operational profit, aiming to maximize the overall system profit as much as possible. The feasible process is as follows.

Step 1. Initialization

First, set the lower bound relaxation solution ${LB}^{k}(\alpha , \beta , \gamma )$ as the decision variable of initial solution. Then, we introduce the auxiliary variables ${UD}_{\left(i, t, j, k\right)}$, ${Lc}_{\left(i, t\right)}$, ${w}_{(i, t, j, k)}^{h}$ and ${P}_{h}$. ${UD}_{\left(i, t, j, k\right)}$ represent number of unfinished user reservation demand in space time arcs $\left(i, t, j, k\right)$. The initial set ${UD}_{\left(i, t, j, k\right)} = {D}_{(i, t, j, k)}$, $\forall \left(i, t, j, k\right)\in {{\bf A}}^{{{'}}}$. ${Lc}_{\left(i, t\right)}$ represent the station resource occupancy at the spatio-temporal node $\left(i, t\right)\in {{\bf V}}^{{{'}}}$. It denotes the total number of vehicle travel arcs passing through station $i$ at time $t$, initializing by setting ${Lc}_{\left(i, t\right)}$ = ${\sum }_{\forall h\in {\bf H}:\left(j, k\right)\in {\bf V}, e, {e}^{{{'}}}\in {\bf E}:(i, j, t, k, e, {e}^{{{'}}})\in {\bf A}}{\overline{x}}_{(i, j, t, k, e, {e}^{{{'}}})}^{h}$, $\forall \left(i, t\right)\in {{\bf V}}^{{{'}}}$. ${w}_{(i, t, j, k)}^{h}$ represent the potential profit that vehicle $h$ may generate by traversing spatio-temporal arc, $\forall \left(i, t, j, k\right)\in {{\bf A}}^{{{'}}}$. ${P}_{h}$ represent the profit generated by vehicle during the operational period, initializing by setting ${P}_{h} = 0$, $h\in {\bf H}$. Furthermore, we introduce the auxiliary set SH and UH, the SH represents the set of selected schedules of vehicle, when $h\in {\bf S}{\bf H}$, ${\sum }_{(i, j, t, k, e, {e}^{{{'}}})\in {\bf A}}{x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h} > 0$. UH represents the set of unselected schedules of vehicle, when $h\in {\bf U}{\bf H}$, ${\sum }_{(i, j, t, k, e, {e}^{{{'}}})\in {\bf A}}{x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h} = 0$. Initializing by setting SH = $\sum _{i\in {\bf S}}\overline{{nH}_{i}}$, UH = H / SH.

Step 2. Remove vehicle schedule that violate capacity constraints

For each spatio-temporal nodes $\left(i, t\right)\in {{\bf V}}^{{{'}}}$, when ${Lc}_{\left(i, t\right)}\ge {C}_{max}$, we select |${C}_{max}$ – ${Lc}_{\left(i, t\right)}$| vehicles $h\in {\bf H}$ and set the ${w}_{(i, t, j, k)}^{h}$ = M, $\forall \left(i, t, j, k\right)\in {{\bf A}}^{{{'}}}$. M is a very large number. When ${Lc}_{\left(i, t\right)}$ < ${C}_{max}$, if ${UD}_{\left(i, t, j, k\right)} = 0$, let ${w}_{(i, t, j, k)}^{h} = {CT}_{ij}$, $h\in {\bf H}$; otherwise ${UD}_{\left(i, t, j, k\right)}\ge 0$, let ${w}_{(i, t, j, k)}^{h} = {CT}_{ij}-(1+\eta ){TP}_{ij}$.Then based on the potential profit ${w}_{(i, t, j, k)}^{h}$, for $h\in {\bf H}$, calculating the ${P}_{h}$, ∀(i, t, j, k)∈A′profit ${P}_{h}$, if ${P}_{h} < 0$, remove vehicle $h$, SH$\to {\bf S}{\bf H}/h$, UH$\to {\bf U}{\bf H}\cup h$. The corresponding vehicle travel arcs and demand satisfaction ${x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h} = 0$, ${z}_{(i, t, j, k)}^{h} = 0$, ${Lc}_{\left(i, t\right)}\to {Lc}_{\left(i, t\right)}-\sum _{\left(j, k\right)\in {\bf V}, e, {e}^{{{'}}}\in {\bf E}:(i, j, t, k, e, {e}^{{{'}}})\in {\bf A}}{x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h}$, $\forall \left(i, t, j, k\right)\in {{\bf A}}^{{{'}}}, \left(i, t, j, k, e, {e}^{{{'}}}\right)\in {{\bf A}}^{{{'}}}, h\in {\bf H}$. If ${P}_{h} < 0$, ${UD}_{\left(i, t, j, k\right)}\to {UD}_{\left(i, t, j, k\right)}-{\sum }_{\left(i, j, t, k, e, {e}^{{{'}}}\right)\in {\bf A}:e, {e}^{{{'}}}\in {\bf E}}{x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h}$.

Step 3. Vehicle reassigning procedure

In this step, we reassign new vehicle to the SAEVS. For each $h\in$ UH, if ${UD}_{\left(i, t, j, k\right)} =$0, ${w}_{(i, t, j, k)}^{h} = {CT}_{ij}$, else if ${UD}_{\left(i, t, j, k\right)}\ge 0$, let ${w}_{(i, t, j, k)}^{h} = {CT}_{ij}-(1+\eta ){TP}_{ij}$. Furthermore, if ${Lc}_{\left(i, t\right)}\ge {C}_{max}$, ${w}_{(i, t, j, k)}^{h} = \mathrm{M}$, updating ${UD}_{\left(i, t, j, k\right)}\to {UD}_{\left(i, t, j, k\right)}-1$.Then, adjusting this vehicle routing plan to cover as many reserved trips as possible with the least traveling cost based on DPG algorithm in Algorithm 1. Then, obtain a new ${\stackrel{-}{{\bf X}}}^{h}$, and calculate the profit ${L}_{h}$ generated by vehicle $h$ based on Eq (20). If ${L}_{h} > 0$, retaining this vehicle schedule, updating ${z}_{\left(i, t, j, k\right)}^{h}$. If ${\sum }_{\left(i, j, t, k, e, {e}^{{{'}}}\right)\in {\bf A}:e, {e}^{{{'}}}\in {\bf E}}{x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h} = 1$ and ${z}_{\left(i, t, j, k\right)}^{h} = 1$, then updating ${{\bf U}{\bf D}}_{\left(i, t, j, k\right)} = max\left\{0, {{\bf U}{\bf D}}_{\left(it, jk\right)}-{\sum }_{\left(i, j, t, k, e, {e}^{{{'}}}\right)\in {\bf A}:e, {e}^{{{'}}}\in {\bf E}}{x}_{(i, j, t, k, e, {e}^{{{'}}})}^{h}\right\}$ and ${Lc}_{\left(i, t\right)}\to {Lc}_{\left(i, t\right)}+{\sum }_{\left(j, k\right)\in {\bf V}, e, {e}^{{{'}}}\in {\bf E}:(i, j, t, k, e, {e}^{{{'}}})\in {\bf A}}{\overline{x}}_{(i, j, t, k, e, {e}^{{{'}}})}^{h}$. If ${L}_{h} > 0$, the reassigning process break. In this case, when reassigning new vehicles, the profits generate with these vehicles are all less than 0.

Step 4. Initial Station capacity expand process

For each station $i\in$ S, let the station capacity ${\mathrm{n}C}_{i} = \mathrm{m}\mathrm{a}\mathrm{x}\{{Lc}_{\left(i, t\right)}{\}}_{t\in {\bf T}}$ and obtain the feasible capacity of each station.

Eventually, the feasible objective value is obtained as the upper bound UP, the $\stackrel{-}{{\bf X}}$, $\stackrel{-}{{\bf Z}}$ and $\stackrel{-}{{\bf n}{\bf H}}$ is obtained by the Step 3 and the $\stackrel{-}{{\bf n}{\bf C}}$ obtained by the Step 4.

4.3.   Updating Lagrangian multipliers

If the lower bound is equal to the upper bound, we can return the corresponding feasible solution. Otherwise, we used the subgradient algorithm to optimize the solution by updating the values of the Lagrangian multipliers $\boldsymbol{\alpha }$, $\boldsymbol{\beta }$. The subgradient algorithm is a widely used approach for updating Lagrangian multipliers, The Lagrangian relaxation approach framework is shown in Figure 4.

In this research, we give a set of initial Lagrangian multipliers ${\boldsymbol{\alpha }:\left\{\right({\alpha }_{(i, t, j, k)})}^{k}{\}}_{(i, t, j, k)\in {{\bf A}}^{\boldsymbol{{'}}}}$, ${\boldsymbol{\beta }:\left\{\right({\beta }_{(i, t)}^{h})}^{k}{\}}_{\left(i, t\right)\in {\bf V}, h\in {\bf H}} = \;0$, in which $k$ represents the number of iterations. The Lagrangian multipliers update process is as follow:

The ${\boldsymbol{x}}^{k}$, ${\boldsymbol{y}}^{k}$, ${\boldsymbol{z}}^{k}$ and $\boldsymbol{n}{\boldsymbol{C}}^{k}$ represent the optimal solutions of relaxed models in the k th iteration, the ${t}_{k}$ is the step size of the subgradient algorithm can be obtain using Eq (23).

where the ${UB}^{k}$ and ${LB}^{k}(\alpha , \beta )$ are the upper bound and lower bound up to iteration $k$, the ${\tau }^{k}$ is the step parameter in the subgradient algorithm. The ${\boldsymbol{A}}^{k}$, ${\boldsymbol{B}}^{k}$ and ${\boldsymbol{C}}^{k}$ is represent as (24) and (25)

We set the maximum iteration number of the Lagrangian relaxation approach as K. When the iteration reaches K, or if the relative gap percentage between LB and UB becomes less than a predefined gap (i.e., 5%), return the current feasible solution as the near-optimum solution, and calculate the gap between the upper and lower bounds using Eq (26).

5.   Computational experiments

In this section, we apply the optimization model of planning and operation strategy of SAEVS, along with the Lagrangian relaxation algorithm, to real-world instances based on taxi data in Chengdu, China on May 28^th. The taxi data used in our study is comprehensive and includes several details, which includes information such as the pick-up and drop-off locations of each trip, the start and end time of each trip, the distance traveled. Finally, we perform a parameter sensitivity analysis focusing on trip selection, opportunity cost coefficient and charging rate. This analysis is crucial to understanding how changes in these parameters affect the overall performance and optimization results. All experiments are conducted on a personal computer with 3.6 GHz CPU and 16 GB RAM.

5.1.   Experimental setting

The distribution of taxi pick-up and drop-off points reflects the allocation of users' travel demands. We determine candidate stations by mining travel demand points. The distribution of stations is shown in Figure 5.

Considering the service range of the SAEVS stations as a circle with a radius of 0.5 km centered at each station, real-time travel origin-destination (OD) data between stations is obtained. The operating period is set from 7:00 to 21:00 and divided into 42 time slices at 20 minutes. Then, travel trips within the operating hours of 7:00–21:00 are considered as input data for the SAEVS. The total demand for SAEVS is determined to be 6206. Figure 6(a) shows the total demand of a day. The actual travel times between stations are obtained using the Baidu API and processed to obtain the travel times slice ${T}_{(i, j)}$ for the input of this paper's model, as shown in Figure 6(b). The user demands at each time period presented in Figure 7.

We set the $TP$ as the SAEVS unit-time travel rental price, ${TP}_{ij} = TP\cdot {T}_{(i, j)}$, in this experiment, and $TP = 10\mathrm{\$}/\mathrm{h}$. Similarly, we set $CT$ as the SAEVS unit-time travel cost, ${CT}_{ij} = CT\cdot {T}_{(i, j)}$, travel cost of AEV $CT = 1\mathrm{\$}/\mathrm{h}$, amortized cost of a AEV $AC = 120\mathrm{\$}/\mathrm{d}\mathrm{a}\mathrm{y}$, amortized cost of a charging facility $CC = 30\mathrm{\$}$. Maximum number of AEVs ${H}_{max}$ = 500, maximum number of charging facility in the station ${C}_{max} =$30, the opportunity cost loss coefficient $\eta$ = 0.5, maximum capacity of the battery ${E}_{max}$ = 15, the battery charging rate per unit of time at a charging station $E$ C = 2, the battery discharging rate per unit of time when a AEV is in motion $E$ D = 1. For the Lagrangian relaxation approach, the step parameter in the subgradient algorithm $\tau$ = 2.

5.2.   Computational performance

In this section, we test small-scale case with 5 stations using Gurobi and LR. Then, we introduce a large-scale real-world case and solved it using the Lagrangian relaxation method, followed by an analysis of the solution results.

To provide a deeper understanding of the SAEVS, we introduce two indicators: average EVA revenue and acceptance rate. The Average EVA revenue represents the mean income generated by the vehicles over the operational period, not accounting for the amortized costs of the vehicle and charging station. The acceptance rate, on the other hand, is the ratio of completed demands to total user demands throughout the operation cycle. This rate indicates the SAEVS's ability to meet user demands during its operational period, thereby providing a measure of its effectiveness and efficiency.

5.2.1.   Comparison of algorithms in small-scale experiments

In this section, we used the small-scale case of 294 travel demands from 5 stations provided in Section 5.1 as the benchmark case for LR approach validation. The maximum fleet size was set to 30 vehicles. Based on this benchmark case, we test the computational time and accuracy of the Lagrangian relaxation algorithm and the Gurobi commercial solver for different demand and fleet sizes, aiming to validate the effectiveness of the Lagrangian relaxation algorithm.

By applying the Lagrangian relaxation algorithm with 5000 iterations and using the Gurobi commercial solver for 1 hour on the small-scale case, the results obtained are shown in Table 2. The gap values between the solutions obtained by the Lagrangian relaxation algorithm and the Gurobi solver were 7.60–8.87% and 5.83–39.09%, respectively. By comparing the results, we can observe that for the small-scale case, the difference in solution accuracy between the two methods is relatively small, with the Gurobi commercial solver slightly outperforming the Lagrangian relaxation algorithm. However, as the user demand and maximum fleet size increase, the computational time and accuracy of the Gurobi commercial solver for precise calculations decrease rapidly. On the other hand, although the Lagrangian relaxation algorithm shows a declining trend in solution quality, it still maintains good efficiency and accuracy compared to the Gurobi commercial solver. Therefore, it can be concluded that the Lagrangian relaxation algorithm performs better overall than the Gurobi commercial solver when solving larger-scale real-world problems.

5.2.2.   Results analysis in large-scale experiments

In this section, we solved the large-scale case by inputting the 20-station case and related parameters into the LR. We performed 5000 iterations and obtained the upper and lower bounds as well as the convergence curve and error rate, as shown in Figure 8(a), (b). The algorithm demonstrated good convergence performance.

The upper and lower bounds obtained were -57,446 and -45,583, respectively, resulting in an error rate of 20.7%. Considering that the objective function (3b) represents the conversion of a maximization problem into a minimization problem, we set the negative value of the feasible upper bound as the output result. When considering the potential opportunity cost, the comprehensive profit of SAEVs was 45,583 ＄. Without considering the opportunity cost, the profit was 48,238 ＄. The total number of relocations was 283, and the total fleet size was 405 vehicles. The initial distribution of vehicles and charging facility at each station is shown in Figure 9.

Then, we analyzed the relocation process of the SAEVS based on the solution results. Figure 10 illustrates the number of relocations in each time period. We then conducted a detailed analysis of the relocation process during the time periods of 7:00–8:00, 10:00–11:00, 14:00–15:00 and 19:00–20:00. The corresponding relocation diagrams for these time periods are shown in Figure 11.

By observing the total user demand in each time period in Figure 6, along with the corresponding relocation diagrams in Figure 11, it can be observed that compared to off-peak periods, the number of relocations decreases during the morning and evening peak periods. After the evening peak period, the user demands decreases and operations cease, resulting in a sharp decline in the number of relocations. The maximum number of relocations occurs during the 10:00–11:00 time period. This is because during the morning peak period, the increased vehicle usage leads to an imbalance in vehicle distribution. The SAEVS needs to conduct concentrated scheduling to maintain the balance of vehicles and meet user demands.

In conclusion, the SAEVs should focus on relocating vehicles after periods of high demand to alleviate the imbalance in vehicle distribution within the SAEVS.

5.3.   Sensitive analysis with different parameter settings

In this section, we perform a series of numerical experiments to verify how the key parameters affect the optimal SAEVS objectives based on the real-world case (instance 1) in Section 5.2, including trip selection, opportunity cost coefficient and charging rate.

5.3.1.   Impact analysis of trip selection

In this section, we further analyze the impact of trip selection on the performance of the SAEVS. When the SAEVS is not adopted trip selection, the SAEVS will not satisfy all user demand. During the computation using the LR, the vehicle reassigning procedure in the feasibility process, specifically step 3, is modified. The modification involves not terminating the reassigning procedure regardless of whether ${L}_{h} > 0$. Instead, the reassigning procedure continues until all demands are satisfied.

According to Table 3, when the SAEVS does not adopt trip selection, the profit considering opportunity cost decreases from 45,583 to 39,349, a decline of 13.67%. The average profit per vehicle decreases from 112.5 to 79.5, a decline of 29.3%. The number of relocations increases from 283 to 392, an increase of 27.8%. The fleet size of SAEVS increases from 405 to 495, an increase of 18.18%.

In summary, trip selection can effectively improve the carsharing system's profit, reduce the number of relocations and increase the overall system efficiency by selectively choosing high-quality user reservation demands, though the user satisfaction rate may decrease.

5.3.2.   Impact analysis of opportunity cost coefficient

Opportunity cost represents the potential profit loss for the operator of the SAEVS due to the inability to meet user demands, resulting in potential users shifting to other public transportation modes. This section analyzes the impact of different opportunity cost coefficients $\eta$ on the performance of the SAEVS. When $\eta$ = 0, it indicates that even if the SAEVS does not accept user demands during operation, potential users will not switch to other public transportation modes.

From Table 4, it can be observed that as $\eta$ increases from 0 to 2, the profit considering opportunity cost and average profit per vehicle of the SAEVS decrease. The profit decreases from 48,407 ＄ to 34,075 ＄, a decrease of 29.6%. The average revenue per vehicle decreases from 123.8 ＄ to 73.0 ＄, indicating a decrease of 41.0%. On the other hand, the total demand acceptance rate, number of relocations, idle rate and fleet size consistently increase. The acceptance rate increases from 92.8% to 96.6%. The number of relocations increases from 227 to 353, an increase of 55.5%. The fleet size increases from 391 to 467, an increase of 19.4%.

In conclusion, an increase in the opportunity cost coefficient leads to a greater penalty for unmet demand, making the system more inclined to satisfy user demands. As a result, the fleet size increases to meet user demands as much as possible, and the number of autonomous vehicle relocation increases. However, as the fleet size increases, the marginal benefit of adding vehicles to satisfy user demands decreases, leading to a decrease in average vehicle profit Therefore, operators need to conduct in-depth research on user behavior and develop an appropriate planning and operation strategy for SAEVS. This strategy should be based on thorough research into user demand sensitivity, ensuring that the balance between cost-effectiveness and customer satisfaction is maintained, while optimizing system performance and profitability.

5.3.3.   Impact analysis of charging rate

Different charging rates correspond to the speed at which electric vehicles are charged, with these rates determined by charging facilities with various power levels. Generally, higher charging power equates to higher costs, and this cost increase tends to be exponential. In this study, we consider charging rates of 1, 2, 3, 4 and 5, with corresponding average charging station costs of 5, 10, 20, 30 and 45 respectively. This leads to average deployment costs for charging facilities of 25, 30, 40, 50 and 65 respectively. Observations from Table 5 are as follows:

With the increase in charging rate and charging facilities costs from 1 to 5, 25–65 respectively. The profits of the SAEVS and average EVA revenue first initially increase and then decrease. When the charging rate is at 2, both the SAEVS's profit and the average EVA revenue reach their peak. Acceptance rate and number of relocations consistently increase, rising from 88.2% to 96.3% and from 239 to 412, respectively. The fleet size decrease from 434 to 386.

In conclusion, increasing the charging rate reduces the instances where vehicles cannot meet user demands and relocation tasks due to insufficient battery level. This leads to higher demand fulfillment rates and increased number of relocations, while reducing the required fleet size. However, as the charging rate continues to increase, the marginal benefits of the SAEVs decrease, while the costs of charging facilities keep rising, resulting in a decrease in SAEVs comprehensive profits. Therefore, operators should deploy charging facilities with appropriate power levels based on the actual operational conditions of the SAEVS.

6.   Conclusions

In this study, we address the planning and operation strategy decision problem of the shared electric automated vehicle system (SAEVS), taking into account trip selection and the potential demand loss's opportunity cost. The dynamics of the SAEVS are described using a spatio-temporal-state network modeling approach, which accurately captures vehicle trajectories and changes in battery levels during operations. An integer linear programming (ILP) model is subsequently developed, aimed at maximizing total profits by integrating the optimization of design planning (including charging facilities, vehicle fleet sizing and distribution) and operational decisions (such as vehicle relocation and trip selection strategy) within the SAEVS. The established spatio-temporal-state network and integer linear programming model are a particular case of the multi-commodity flow model, which has been proved as a NP-hard problem and cannot be solved in polynomial time. To address this, we introduce the Lagrangian relaxation (LR) approach, which allows for obtaining near-optimal solutions within an acceptable time frame. Through validation and analysis of the model and algorithm, the results indicate:

1) The LR algorithm approach in this study exhibits small differences in solution accuracy compared to the commercial solver Gurobi for small-scale problems. However, as the problem size increases, the time and accuracy of exact solutions using Gurobi decrease rapidly. On the other hand, although the LR algorithm shows a deteriorating trend in solution quality, it maintains good efficiency and accuracy compared to Gurobi.

2) Regarding planning decisions, SAEVS operators should distribute vehicles to stations with concentrated user demand during early peak hours and allocate charging facilities to stations with high total demand throughout the day. For operational decisions, vehicle relocation post-peak demand periods are recommended to alleviate imbalances within the SAEVS.

3) The introduction of trip selection can enhance the overall efficiency of SAEVS compared to satisfying all user demands. As the opportunity cost loss coefficient increases, yielding greater profit penalties due to unmet demand, the SAEVS is more inclined to satisfy user demands. However, this comes at a cost to the overall profitability of the system. Therefore, operators should study user demand sensitivity and formulate precise operational strategies. As the charging rate escalates, the marginal benefits derived from the SAEVS diminish, while the costs associated with the charging facilities continuously rise. Thus, it is crucial for operators to implement charging facilities with suitable power levels, taking into account the real-world operational conditions of the SAEVS.

The model proposed in this study has certain limitations that need to be addressed and improved in future research. One limitation is that the planning and operation optimization model for SAEVS developed in this study assumes fixed user demands and does not account for the stochastic nature of user demand and arrival patterns. To overcome this limitation, future research can focus on optimizing the planning and operation aspects of SAEVS in random environments, considering the uncertainty in user demand and arrival patterns. This would provide a more realistic and robust framework for SAEVS planning and operation.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (52372296), National Natural Science Foundation of China (72371209), National key research and development program of China (2022YFC3803700 Changsha Science and Technology Major Specific Projects, kh2301004).

Conflict of interest

The authors declare that there are no conflicts of interest.