1 Introduction

In recent years, the climate change and energy supply are two major issues facing the world. The 2022 State of the Global Climate report shows that the global average temperature in 2022 is 1.15 °C higher than the 1850–1900 average. Climate change has brought about harmful socio-economic and environmental impacts such as sea level rise, drought, food insecurity, refugee displacement. Carbon dioxide emissions from fossil fuels are the main driver of climate change. To achieve the goal of net-zero emissions by 2050, the International Energy Agency (IEA) sees electricity as a key element of a successful energy transition. The share of electricity in final energy consumption will rise from current 20 to 52% in 2050. The share of fossil fuels in the global energy mix will drop from current 80 to 60% in 2050. EVs as an alternative transportation solution play a huge role in achieving the net zero emission goal in 2050 (Varshosaz et al. 2019), as every 1% reduction in fuel consumption can reduce carbon dioxide emissions by nearly 7.5 million tons. In China, there is expected to be about 100 million EV owners in 2030. However, the experience of electric replenishment is still not as smooth as that of gasoline vehicles. At present, most EV users cannot be recharged timely with facing the charging troubles, such as no available charging piles and long charging waiting time (Sun et al. 2020).

In response to the charging issues, the government has strengthened the construction of charging infrastructure. By the end of June 2023, the cumulative number of charging infrastructure in China is 6.652 million units, a year-on-year increase of 69.8%. At the same time, EV companies are actively implementing many substantive solutions. For example, Tesla has established a super charging station (Huanqiu 2022), and a new service mode known as valet charging was first proposed by NIO Corporation (NIO), a worldwide manufacturer of intelligent EVs founded in 2014 and went public in the U.S. in 2018. The user can directly call the service on the specific mobile application, and the charging staff will drive the car from the user to the charging station and return it after it is fully charged (Nio 2023). By July 2022, the number of registered users of the application of NIO Power has exceeded 3 million, and NIO has provided a total of 821,350 valet charging services. The valet charging service will alleviate users’ recharging anxiety, free up users’ recharging time to focus on urgent matters, and promote to attracting new users of EVs.

From the perspective of overall operating costs, both tactical charging infrastructures planning and operational charging demands allocation are pivotal for launching valet charging services. The site of the charging station will determine the travel distance of the charging staffs, which will affect the allocation of demand, and vice versa. Besides, due to the limited charging capacities, charging waiting is inevitable. These pose challenges for the company to obtain efficient plans and motivate us to investigate the integrated optimization problem of EVs charging location and allocation for valet charging service. Therefore, two decisions on where to locate charging stations and how many charging demands at each node to be allocated to each station are optimized jointly. The charging system is modeled as a queuing system to derive the average charging waiting time. The total cost, including the construction of charging facilities and valet charge service launching (i.e., charging staffs’ road service, round-trip time, and the charging waiting time), is minimized.

1.1 Literature review

In the last few years, researchers and decision-makers in the transportation filed have paid close attention to the EV charging infrastructures planning problem (Zhang et al. 2015; Rogge et al. 2018; Kunith et al. 2017; Mirchandani et al. 2014; Rahman et al. 2016; Shen et al. 2019). The charging facility locating problem considers different optimization objectives from the viewpoints of EV users or charging service providers. Zhang et al. (2017) at the minimum comprehensive cost of land cost, construction cost and operation cost. Li et al. (2016a) minimize the overall cost of new charging stations and relocation within a finite planning horizon. From the perspective of users, Wu and Sioshansi (2017) consider the uncertainty of demand and establish a random traffic flow capture model. Zhu et al. (2016) comprehensively consider the user’s travel cost and entering the charging station. He et al. (2015) assume that the EV driver determines the driving route and charging plan at the same time, so as to minimize the trip and charging time, while ensuring that the battery will not be depleted before the trip is completed. According to the characteristics of urban residents’ travel behavior, Sun et al. (2020) aim at maximizing the coverage area of EV flow by charging stations. Using a two-layer simulated annealing algorithm, Ouyang and Xu (2022) deploy the optimal location for both fast and slow charging stations. They set the goal of maximizing covered traffic flows within a constrained budget, incorporating EV customers’ partial charging habits and elastic demand.

A group of studies apply mathematical modelling approach and optimization theories to study the EV charging infrastructure planning problem (Kim and Kuby 2012, 2013; Huang et al. 2015; Chung and Kwon 2015; Chung and Kwon 2015; Zhang et al. 2017; Chen et al. 2016; Liu and Wang 2017; Asamer et al. 2016). Li et al. (2016b) combine the ideas of multi-path and multi-period to formulate the dynamical public charging stations locating problem. The proposed heuristic based on a genetic algorithm solves the formulated mixed-integer linear model. Tu et al. (2016) construct a location model with spatial–temporal demand coverage and propose a genetic algorithm to determine the electric taxi charging stations locations using real massive taxi GPS data. Guo et al. (2022) simultaneously optimize charging station location and routing problem for EVs and propose a three-phase hybrid heuristic algorithm to solve the problem. Bao and Xie (2021) study the charging station location problem allowing en-route charges as many times as needed for electric vehicles. They propose the branch-and-bound algorithm and the nested partitions algorithm to find the optimal set of locations. Aghalari et al. (2023) investigate EV location–routing decisions under climate and customer demand variability by proposing a progressive hedging-based heuristic algorithm. Wang et al. (2021) jointly optimize the charging location and road capacity allocation considering path choice, departure time choice and en-route charging behavior. Faustino et al. (2023) introduce and determine charging zones to achieve high utilization rates for electric vehicles chargers. Unlike the traditional charging process, swapping the battery at the station takes less than 10 min, which is comparable to refueling a conventional vehicle. The location-routing issue for EV battery swapping stations is a topic of study for some researchers. For example, Mahoor et al. (2019), Yang et al. (2017a), Yang and Sun (2015), and Hof et al. (2017) all model the problem as a mixed-integer linear programming. They explore smart heuristics, such as adaptive large neighborhood search, four-phase sweep heuristic, and Tabu search, to solve optimization models for such problems. Moreover, there are studies focusing on the charging stations location planning (Li et al. 2016b; Brandstätter et al. 2017), assigning charging stations and distributing the fleet optimally (Li et al. 2016b; Hua et al. 2019) for shared EVs. The station-based carsharing mode is studied in Brandstätter et al. (2017), Li et al. (2016b), and Hua et al. (2019). The mode of free-floating carsharing is also studied by researchers. For instance, Roni et al. (2019) develop an integer programming model to simultaneously optimize the locations of charging stations and the allocation of SEVs to charging stations.

To capture the characteristic of charging demands’ behaviors, literature such as Cavadas et al. (2015), Xi et al. (2013), Dong et al. (2014), and Cocca et al. (2019a) employ the simulation-based optimization approach to address the problem of EV charging infrastructure planning. Cavadas et al. (2015) address the issue of where to place EV charging stations in an urban scenario. To maximize satisfied demand within a set budget, a mixed-integer mathematical model is created that introduces demand transference with traveller activities. Cocca et al. (2019a) present a simulator driven by discrete events and based on millions of data to assess the location of charging stations for free-floating shared EVs. Data-driven approaches are also employed by Yang et al. (2017b), Li et al. (2017), Chen et al. (2017), Cocca et al. (2019b) to locate charging stations. Yang et al. (2017b), Li et al. (2017), and Chen et al. (2017) investigate the problem of locating and planning the size of electric taxi charging stations using actual taxi travel data. Cocca et al. (2019b) simultaneously determine the decisions of the locations of charging stations, whether or not customers were required to place rented SEVs back at the charging locations, and the quantity of chargers by proposing a data-driven optimization method. Kłos and Sierpiński (2023) develop a charging station siting method that uses a GIS-based approach to properly distribute charging stations throughout a given urban area considering the distances between charging stations. Li et al. (2023) use reinforcement learning to solve a three-layer model for EV charging station location and dynamic pricing. Lai and Li (2022) propose an economic equilibrium model for on-demand valet charging to investigate how the planning of the charging infrastructure and regulatory action will impact the market outcome.

1.2 Contributions

The following is a summary of the study’s contributions. First, we consider a new service mode named the valet charging service for joint decisions of charging station location and charging demand allocation. Scholars have carried out few studies in EVs infrastructure planning based on the characteristics of valet charging service. The objectives, including the building cost of charging facilities, the road service cost, round-trip time, and the charging waiting time of the charging staff, are minimized all simultaneously. Second, a new modelling approach of EVs’ charging system with the valet charging service is proposed based on an infinite-source queuing model. We also propose an improved genetic algorithm to resolve the joint optimisation problem rigorously. Third, the proposed model and algorithm are validated and applied with real data on valet charging service. New deployment plans of charging station location and charging demand allocation are provided for a real case with the valet charging service.

1.3 Paper organization

The remainder of the article is organized as follows. The EVs’ charging station location and charging demand allocation problem is modeled based on the queuing theory in Sect. 2. In Sect. 3, an improved genetic algorithm is proposed and designed according to the features for the optimization problem. Numerical studies related to a real case are conducted to evaluate the effectiveness of the developed model and algorithm in Sect. 4. Finally, Sect. 5 concludes by presenting some findings.

2 Problem formulation

To formulate a tractable model without losing crucial problem features, we set a few key modeling assumptions before building the model. Some of them are carried over from earlier research, while others are specific to our model. First, within our transportation networks, we assume that there are only battery-powered automobiles and there is only one type of EV in the study, that is, all are pure EVs. This assumption has been recognized by the research community (see, for example, Bao and Xie 2021). Second, all EV charging users are valet charging service users to simplify modeling as adopted by Li et al. (2021) and Lai and Li (2022), which could help us to focus on exploring the impact of valet charging service on the charging station locations and allocations. Third, the shortest path from the electric vehicle at each demand node to each charging station candidate node in the network is assumed to be known, and a vehicle always selects the shortest transportation route (Bao and Xie 2021; Sun et al. 2020). Forth, it is assumed that the difference in land price at different nodes has an impact on the construction cost of charging facilities. This assumption brings our model closer to practical applications. Fifth, we overlook other potential operational costs, such as charging fee, maintenance, electricity prices, and environmental impact. Our current model assumes that the service capacity of the charging staff is infinite, and there are no time window requirements for charging demand. If the variable electricity price is introduced, the model needs to output the time-accurate charging staff assignment and charging planning solutions that considers time-varying electricity price and meet the constrictions of the time window. In addition, if we jointly optimize the maintenance decision of charging facilities, it will inevitably lead to some unexpected modeling and solution challenges. Sixth, we assume that the charging demand is known and determined, and there is no traffic congestion.

The process of valet charging service can be regarded as a queuing system, as used by Lai and Li 2022, Xiao et al. (2020), and Kumar et al. (2022), for example. In this queuing system, the EVs that arrive at the charging station are the input sources of the system. The user uses the mobile application to call the valet charging service. Then, the charging staff picks up the car and arrives at the charging station to queue up for charging. The whole process is quite random, so we assume that the time interval for an electric car to arrive at a charging pile follows the negative exponential distribution with parameter \(\lambda\). That is, the arrival process of EVs is a Poisson flow, and the average arrival rate of EVs at the charging station is \(\lambda\). In addition, there are multiple charging piles at a charging station. So, the charging system is a multi-server system and the service rule is first come first service. A charging station is set to accommodate b charging piles. Each charging pile operates separately from the others. The service time of the fast charging pile follows the negative exponential distribution with the parameter \(\mu\), that is, the average service rate of one charging pile is \(\mu\). It is assumed that the service efficiency of charging piles at different charging stations is the same as following the assumption in Bao and Xie (2021). Therefore, the \(M/M/b\) queuing system for the valet charging service can be summarized as follows: each charging station has b charging piles. The process of EVs arriving at the charging station for charging is a Poisson flow, and the average arrival rate is \(\lambda\). EVs receive charging services based on the first-come-first-served principle, and the charging time follows the negative exponential distribution with parameter \(\mu\). Each charging pile can only provide services for one EV. Once a vehicle occupies a charging pile, other EVs will not occupy the charging pile.

Due to the randomness of the EV arrival process, we assume that both the source of EVs and the capacity of the queuing system are infinite, as recognized in Lai and Li (2022). Let \(n\) represent the number of arriving EVs. When \(n < b\), it indicates that there are \(n\) charging piles in a certain charging station charging EVs at this time, and \(b - n\) charging piles in the system do not provide charging services. When \(n > b\), it means that the quantity of EVs arriving at this time is larger than the number of charging piles. All b charging piles are charging EVs, and there are \(n - b\) EVs waiting in line for charging. When the EV has finished charging, the charging staff leaves the charging station and sends the vehicle back. Then the EV behind begins to charge.

To continuously improve the user experience level and the resource utilization efficiency of the valet charging service, while ensuring that the capacity of charging stations can meet all charging demands, an optimization model for charging station location and demand allocation is proposed. Before establishing the mathematical model, the following definitions are given:

Definition 1

(The cost of the entire charging system). These include the construction cost of charging facilities, and the road service cost of the charging staff.

$$O_{1} = \sum\limits_{i = 1}^{m} {X_{i} \cdot C_{i} } + \sum\limits_{i = 1}^{m} {\sum\limits_{j = 1}^{n} {D_{j} \cdot f_{ji} \cdot d_{ij} \cdot c} }$$

Definition 2

(User experience level). The user experience level is quantified as the round-trip time and the average waiting time of the charging staff at the charging station, and the spent time is costed.

$$O_{2} = \sum\limits_{i = 1}^{m} {\sum\limits_{j = 1}^{n} {\left( {D_{j} f_{ji} \cdot 2d_{ij} \frac{1}{v} + D_{j} f_{ji} \cdot W_{qi} } \right)} }$$

This is in line with the status quo of EV valet charging service in NIO. The current valet charging service is gradually being upgraded. Through model optimization, the charging system cost and user service experience level can be balanced, and the valet charging demand can be completed in a short time at the lowest cost. In this context, we consider two optimization objectives: minimizing the cost of the entire charging system and minimizing the round-trip time and the time spent queuing up for charging of the charging staffs. Further, we combine the two sub-objectives into one objective through the “value of unit time” coefficient. Table 1 includes a list of notations that are used to formulate the practical problem studied in this paper into mathematical model. The corresponding model is established as follows:

$$\min O_{1} + \beta \cdot O_{2}$$
(1)
$$s.t. \, W_{qi} = \left( {\frac{{r_{i}^{b} }}{{b!(b\mu )(1 - \rho_{i} )^{2} }}} \right)P_{0}^{i} \,\, \forall \, i = 1,2,...,m$$
(2)
$$P_{0}^{i} = \left( {\frac{{r_{i}^{b} }}{{{{b!(1 - \rho_{i} )}} }} + \sum\limits_{{a_{i} = 0}}^{b - 1} {\frac{{r_{i}^{{a_{i} }} }}{{a_{i} !}}} } \right)^{ - 1} \quad \forall \, i = 1,2,...,m$$
(3)
$$r_{i} = \frac{{\lambda_{i} }}{\mu } = \frac{{\sum\nolimits_{j \in J} {D_{j} \cdot f_{ji} } }}{\mu }\quad \forall \, i = 1,2,...,m$$
(4)
$$\rho_{i} = \frac{{r_{i} }}{b}\quad \forall \, i = 1,2,...,m$$
(5)
$$X_{i} \in \left\{ {0,1} \right\}\quad \forall \, i = 1,2,...,m$$
(6)
$$\sum\limits_{i = 1}^{m} {f_{ji} } = 1\quad \forall \, j = 1,2,...,n$$
(7)
$$0 \le f_{ji} \le X_{i} \quad \forall \, i = 1,2,...,m,\;j = 1,2,...,n$$
(8)
$$\rho_{i} = \frac{{r_{i} }}{b} = \frac{{\sum\nolimits_{j \in J} {D_{j} \cdot f_{ji} } }}{b\mu } < 1\quad \forall i = 1,2,...,m$$
(9)
Table 1 Model notations
Full size table

A series of relevant parameters of the charging queuing system can be obtained from the queuing theory. Equation (2) obtain the average waiting time spent by the charging staff in the charging station. Equation (3) represent the steady-state probability of the charging queuing system. Equation (5) indicate the service intensity of charging service facilities.

The objective function (1) minimizes the overall cost, including the construction cost of charging facilities, the charging staff’s road service cost, the round-trip time cost, and the average waiting time cost in charging queues, where \(\beta\) is the value coefficient per unit time. Constraints (6) define that \(X_{i}\) is a binary variable. Constraints (7) ensure that all vehicles at the demand node will be assigned to a charging station for charging, and all demands are fully satisfied. Constraints (8) ensure that only when a charging station is constructed at the location i, vehicles will be allocated to location i for charging. Constraints (9) are the conditions that the system has a steady-state solution. That is, the average arrival rate of the system must be less than the average service rate.

3 Solution approach

The problem of EVs’ charging location and allocation belongs to NP-hard problem as the objective function in the model is nonlinear. It is hard to obtain the exact solution. Due to the genetic algorithm’s powerful random search capability, an improved genetic algorithm is developed to optimize the location of the charging station and the allocation ratio of the demand at each demand node to the charging station. The proposed framework of the improved genetic algorithm is as the following Fig. 1, where mainly including the steps of chromosome encoding, elitist selection, crossover and mutation, and convergence. Next, each step will be described in detail.

Fig. 1
figure 1

The proposed framework for the improved genetic algorithm

Full size image

3.1 Chromosome encoding

The encoding operation refers to converting the phenotype into a genotype that can be processed by the genetic algorithm to match the practical problem with the genetic algorithm. This paper adopts the natural number coding method. There are m candidate locations for the charging station, and the numbers of the candidate locations are represented by natural numbers \(1,2,...,m\). The gene string is in the form of \(a_{1} a_{2} a_{3} \cdots a_{m}\), its length is m, and \(a_{i} ,\forall i = 1,2, \cdots ,m\) is a natural number from 1 to m. In this study, we first generate an initial population of charging station candidate locations. There are 15 coding bits representing 15 genes on each chromosome. 30 chromosomes are randomly generated, representing an initial population of 30 individuals. Then we generate the initial population of the allocation ratio of the demand at each node to the charging station. It is two-dimensionally encoded, that is, each chromosome is a \(30 \times 8\) matrix. 30 matrices, that is, the initial population is 30 individuals, are generated. Each row of the matrix is normalized to satisfy the constraints.

3.2 Elitist selection

The fitness function in this study is determined according to the objective function in the model, taking the cost of the entire charging system and the value of user time occupied as the fitness function, as shown in formula (10). Another name for the fitness function is the evaluation function. The selection of the fitness function is related to the convergence speed of the genetic algorithm and whether the optimal solution can be searched.

$$f(x) = \left( {\sum\limits_{i = 1}^{m} {X_{i} \cdot C_{i} } + \sum\limits_{i = 1}^{m} {\sum\limits_{j = 1}^{n} {D_{j} \cdot f_{ji} \cdot d_{ij} \cdot c} } } \right) + \beta \cdot \left( {\sum\limits_{i = 1}^{m} {\sum\limits_{j = 1}^{n} {(D_{j} f_{ji} \cdot 2d_{ij} \frac{1}{v}} } + D_{j} f_{ji} \cdot W_{q} )} \right)$$
(10)

We use sorting method for individual selection operation. Sorting selection is a commonly used selection method in genetic algorithm. The sorting method is efficient and easy to implement. The basic idea of the sorting method is: calculate the fitness value of each individual in the population based on the fitness function, and arrange all the individual fitness values from large to small. The individual with the largest fitness value is chosen as the parent generation and copied to the children generation. Then, new children generations are generated after crossover and mutation operations, and the individual with the largest fitness value is selected to be copied. Therefore, in the problem, we calculate the fitness values of individuals in the children and the parent generations respectively, and sort them from small to large. We select 30 chromosomes with the top 30 target values as the new generation. Then repeat the above steps to form a new parent generation.

3.3 Crossover and mutation

The sequential crossover strategy is adopted to crossover 30 chromosomes according to a certain crossover probability to form children chromosomes. The implement steps of the sequential crossover method are as follows:

  • Step 1: Select the same gene start and end positions on the two parent chromosomes.

  • Step 2: Inherit the genes selected in the first step to the children generation, and ensure that the gene positions remain unchanged.

  • Step 3: Find out the position of the gene selected by Parent 2 in Parent 1, and delete them to obtain Child2-1. In the same way, find out the position of the gene selected by Parent 1 in Parent 2, and delete them to get Child2-2.

  • Step 4: Put the genes in Child2-2 into Child1-1 in order. Similarly, put the genes in Child2-1 into Child1-2 in order. Finally, we get the cross children generation.

An illustration example of the sequential crossover method is as Fig. 2. First, we randomly select a substring code “6 2 3 1” from Parent 1, and put it in the corresponding position of Child 1, as shown “Child1-1” in Step 2. Then, the vacant position of child 1 is selected from parent 2 in the order of parent 2 (with the existing code not repeated). For example, put the substring code “5 7 9 4 8” of parent 2 in Step 3 into the vacant position of “Child 1–1”, and finally get “Child 1” as shown in Step 4. Child 2 can be obtained in the same way.

Fig. 2
figure 2

The specific steps of the sequential crossover method

Full size image

Using a two-point mutation strategy, we select a chromosome and two mutation points on the chromosome to mutate with a certain mutation probability. The specific steps of the two-point mutation are as follows: first, two genes are selected on a parent chromosome, and the positions are represented by X and Y, respectively. Then the two selected genes are exchanged to obtain the final mutant children generation. Figure 3. demonstrates an example of the two-point mutation strategy. We exchange the position of code “9” and code “8” in the Parent and keep the other codes unchanged to obtain the Child.

Fig. 3
figure 3

The two-point mutation strategy

Full size image

The children chromosomes generated by mutation and crossover together constitute the children population.

3.4 Convergence

This study adopts the convergence criterion of the maximum number of iterations. When the number of genetic algorithm iterations reaches the previously set threshold, the iteration is terminated. The individual with the largest fitness value at this time is output, and the ideal resolution to the actual issue is attained through decoding. At the same time, the number of iterations and the change trend graph of the optimal solution of each iteration are output to analyze the effectiveness of the algorithm.

4 Case study

4.1 Input data

We choose the real case of Yangpu District, Shanghai as the research case. The Yangpu District, as shown in Fig. 4, which spans a total area of 60.61 square kilometers and carries a permanent population of over 123,000 by the end of 2021, is situated in the northeast of Shanghai’s downtown area.

Fig. 4
figure 4

The considered case area of Yangpu district, Shanghai

Full size image

Without loss of generality, we construct a simulation case that closely resembles the real case. The values that were chosen for the parameters of the developed case study are described in detail in Table 2. The data provided by NIO, EV operations literature, the EV charging facility planning literature, and pertinent online sources were used to develop the adopted parameter values (Li et al. 2021; Lai and Li 2022; Aghalari et al. 2023). Eight locations will be selected from fifteen candidate locations for charging station construction. 30 demand nodes are to be served. According to the scale in the map and combined with the scope of the whole region, the simulation area of Yangpu District, Shanghai is represented by the \(11 \times 12\) plane in MATLAB. Among them, 15 charging station candidate nodes and 30 demand nodes are randomly generated and their locations in the plane are determined. As shown in Fig. 5, the red square points represent candidate charging station nodes with coordinates listed in Table 3, and the blue dots represent demand nodes with coordinates listed in Table 4. Considering practical situation of each candidate location with varying land price, Table 3 summarizes varying unit construction cost of a charging pile and total charging station construction cost in each target area. According to the historical order data provided by NIO, the total daily charging demand \(D_{j}\) at each demand node j are estimated and determined, as shown in Table 4. The average arriving rate of EVs \(\lambda_{i}\) is equal to the demand per hour at each demand node in Table 5, which can be obtained by averaging the daily demand to each hour. According to the coordinates of each candidate location and demand node, we use MATLAB to calculate the Euclidean distance between each candidate location and each demand node.

Table 2 Data setting for the case study
Full size table
Fig. 5
figure 5

Distribution simulation of demand nodes and candidate sites in Yangpu District, Shanghai

Full size image
Table 3 Location and construction cost of candidate sites in Yangpu District, Shanghai
Full size table
Table 4 Locations of demand nodes and associated total demands in Yangpu District, Shanghai
Full size table
Table 5 Demand per hour at each demand node in Yangpu District, Shanghai
Full size table

According to the price information provided by NIO, if the customer who is a NIO car owner has not applied for the “Energy Worry-Free” package, the unit price for enjoying the valet charging service is 180 CNY per time. Or if they apply for a package of 980 CNY, which includes 15 services per month, equivalent to 65.3 CNY per service. Non-NIO car owners can only purchase services in units of times, and each time of service costs 380 CNY. The service cost of the charging staff per kilometer between demand nodes and charging stations is 10 CNY/km. According to the average distance \(\overline{d}_{ij}\) between nodes and the average once service time of 118 min provided by NIO, we determine that the average service rate of one charging pile is \(\mu\) = 2 per hour. According to the data provided in the document “Shanghai Electric Vehicle Charging Infrastructure Special Planning”, we can set that the quantity of charging piles built at a candidate location is b = 106. The unit user time value is \(\beta\) = 100 CNY/h.

4.2 Solution results

Based on the actual data and the real situation, we conduct numerical analysis to examine the effectiveness of the mathematical model and proposed methodology. We code the genetic algorithm designed in Sect. 3 in MATLAB. We set the fixed initial population size \(N\) to be 30, the maximum number of iterations to be 7, 10, 100 and 1000, respectively. The crossover probability \(p_{c}^{1}\) and mutation probability \(p_{m}^{1}\) of solving \(X_{i}\) are taken as 0.15 and 0.2, respectively. The crossover probability \(p_{c}^{2}\) of solving \(f_{ji}\) is set as 0.95, 0.15. The mutation probability \(p_{m}^{2}\) is set to be 0.35, 0.2 respectively. To investigate how different parameter combinations impact the performance of the designed genetic algorithm, we design test instances under the above-mentioned different parameter combinations. All numerical experiments are run on a personal computer with Intel Core i7-7500U CPU 2.70 GHz and 4 GB memory. Figure 6 illustrates the convergence of the optimal fitness value obtained by the genetic algorithm with the increase of the number of iterations under different parameter combinations (hereafter referred to as Combo). Table 6 summarizes the optimal objective values generated from genetic algorithm under different parameter Combos.

Fig. 6
figure 6

Convergence of the proposed genetic algorithm

Full size image
Table 6 Comparison results of the solution performances under different parameter combinations
Full size table

We can conclude from the solution results of different parameter Combos that the number of evolution generation has a great impact on the algorithm optimization performance. With the increase of the evolution generations, the optimal objective value tends to decrease gradually and the algorithm performs better. Under parameter Combo 4, the obtained solution quality is the best with the minimal optimal objective value. The optimal charging station location scheme is to build the charging stations in serial numbers 10, 11, 7, 13, 8, 5, 3, and 4, and the associated target areas are Yinhang, Shiguang, Wujiaochang, Yangpu Park, Yangpu District Government, and New Jiangwan City Times Garden, Fudan University (Jiangwan New Campus), New Jiangwan City Capital. The demand ratio of each demand node allocated to each charging station is presented as the following Table 7. The solution can ensure that all the demands of each demand node among the 30 demand nodes are fully satisfied.

Table 7 The solution result of demand allocation ratio
Full size table

4.3 Sensitivity analysis

In this section, we investigate the impact of key parameters, including charging demand level, charging capacity (e.g., the number of charging piles to be built for each charging station), and value of time, on planning decision and system cost. Different scenarios are generated by varying the key parameters based on basic value.

  1. (1)

    Charging demand level.

The current customer demand is set based on a conservative estimation that may not accurately represent the reality. In particular, with the development of battery charging and swapping technology and the improvement of charging facilities, the volume of electric vehicle users will continue to grow. Table 8 illustrates the impact of customer demand level on the overall cost. When customer demand is set to the double- and four-times quantity of the basic value, the overall cost increases 1.2759 (106 CNY), and 11.9623 (106 CNY), respectively. Figure 7 visualizes the charging station location and allocation decisions under different demand levels. If the demand level increases, then half of the locations of the selected charging stations remain unchanged, with location number 4, 5, 10, and 13. The other half of the number of charging stations to be built has a change in siting decision. Demand allocation decisions have undergone major changes. The results clearly demonstrate that the charging station location and allocation decisions under the valet charging service are highly sensitive to the demand level.

Table 8 Results under different charging demands
Full size table
Fig. 7
figure 7

Results of demand allocation ratio under a Basic demand level, b Double the basic demand level, c Four times of the basic demand level

Full size image
  1. (B)

    Charging capacity.

Table 9 indicates the impact of the number of charging piles to be built for each charging station on the charging station location decisions and the overall system cost under the valet charging service. To run the experiments, we set the number of charging piles per charging station to 53 (half of the basic level) and 159 (1.5 times of the basic value). The results in Table 9 reveal that the charging station locations with number 3, 4, 5, 7, 10, 13 are always selected to be constructed, as the number of charging piles to be built in each charging station increases. The overall system cost is much more sensitive to the number of charging piles. For instance, when the number of charging piles increases from 53 to 159, the the overall cost increases approximately 2.8185 (106 CNY), and 7.2869 (106 CNY), respectively. For presentation brevity, we do not list the demand allocation decisions here. This experiment shows that demand allocation decisions are also susceptible to the variabilities of the number of charging piles.

Table 9 Results under different charging capacities
Full size table
  1. (C)

    Value of time.

We conduct the final set of experiments to investigate the impact of the value of time on the charging station location and allocation decisions and the overall cost. To generate the instances, we change the value of time to 150 and 200 CNY/h, respectively, while the other parameters are kept fixed to their basic values. The experimental results indicate the demand allocation decisions and the overall cost are much more sensitive to the value of time than charging station location to that. For instance, when the value of time increases from low to high values, the overall system cost increase 1.9499 and 6.061, respectively, while 6 of the 8 charging station locations selected for construction remain unchanged with charging station location number 3, 4, 5, 7, 10, 13 (see Table 10).

Table 10 Results under different value of time
Full size table

4.4 Discussions

This study’s main contribution is to use an improved genetic algorithm to locate charging stations and allocate demands for valet charging service by taking charging wait times and staff travel costs into account. This study lays the groundwork for intelligent transportation while promoting the use of EVs. We give company employees the smart decision-making tools and effective deployment plans they need to perform valet charging services. However, the model simplifies some practical issues when interpreting the findings and drawing to conclusions. There are many possible directions for future research on the decision model. First, the routes planning problem can be optimized jointly when multiple charging staffs are providing services simultaneously. Other potential costs, such as maintenance cost of charging infrastructures and electricity prices, can be incorporated into the decision model and can fully evaluate the operational cost. Another extension to our model pertains to considering the environmental impact of the valet charging service. According to the remaining mileage of the vehicle, the surrounding charging resources and the grid load, using the model to make the optimal decision to dispatch orders for the charging staffs, and to plan the optimal charging strategy (determining specified charging time to achieve the purpose of peak-shaving and valley-filling, and planning the shortest route), to help save energy and reduce emissions. Second, the paper assumes that each link’s travel time and each node’s charging demand are known and deterministic, while in reality, traffic congestion may make the travel time uncertain. The stochastic charging demand and travel time of charging staff can be considered in the model to portray EV customers’ demands and travel costs more accurately. It is helpful to develop multi-period deployment models with random demand since it might not be possible to finish building charging stations quickly due to a variety of reasons, involving the restricted budget and the current low level of demand. Third, the proposed valet charging service could be compared with other alternative solutions (e.g., conventional self-charging approaches, battery swapping mode, etc.) to fully evaluate its advantages, limitations, and cost-effectiveness. Such comparisons would contribute to the broader discussion on the future of EV charging infrastructure. Another perspective of this research is to model user acceptance and behavioral considerations. Investigating user acceptance, preferences, and behavioral aspects of the valet charging service and how to adopt this service could provide valuable insights for further improvement and refinement. The user preferences or choices for different charging approaches, such as valet charging, self-charging, and battery swapping, can be set to be exogenous with fixed proportions of different types of users. The user preferences or choices can also be regarded endogenous. In this way, the utility functions and choice model of users for different charging approaches can be incorporated into the model.

Exploring other advanced optimization algorithms (e.g., new types of hybrid heuristics and metaheuristics, adaptive algorithms, self-adaptive algorithms, island algorithms, polyploid algorithms, etc.) to solve the charging stations location and allocation problem for valet charging service addressed in this study remains an open problem. The aforementioned different types of advanced optimization algorithms have been applied as solution approaches in many different domains such as online learning, scheduling, multi-objective optimization, transportation, medicine, data classification, and others. Many researchers have proved the effectiveness of the proposed advanced optimization algorithms in the applications of aforementioned fields, especially for the more realistic large-scale problems. Zhao and Zhang (2020) proposed a learning-based algorithm that can learn to adjust strategies based on the problem features. In the case of multi-objective optimization, the proposed algorithm was found superior to compared algorithms on most of the test cases. Dulebenets (2021) explored a new Adaptive Polyploid Memetic Algorithm for the trucks scheduling of at the cross-docking terminal. The results had proved the better effectiveness of the proposed algorithm compared to the well-known state-of-the-art metaheuristics. Gholizadeh et al. (2021) proposed a scenario-based genetic algorithm for the flexible flowshop scheduling and showed its superiority over an exact optimization method and a canonical genetic algorithm. For the berth scheduling in marine container terminals, Dulebenets (2017) and Kavoosi et al. (2019) developed a novel memetic algorithm and an island-based metaheuristic algorithm, respectively. The results in Dulebenets (2017) showed that the performance of the developed memetic algorithm was better than the results reported by previous berth scheduling literature using a memetic algorithm that does not apply the deterministic parameter control strategy, typical evolutionary algorithm, simulated annealing and variable neighborhood search. Kavoosi et al. (2019) found the proposed algorithm outperformed evolutionary algorithm, particle swarm optimization, estimation of distribution algorithm and differential evolution conducted in isolation, and other metaheuristic algorithms including variable neighborhood search, tabu search and simulated annealing. Rabbani et al. (2022) developed Non-dominated Sorting Genetic Algorithm II and Multi-Objective Particle Swarm Optimization which can solve the ambulance routing problem in a short time. Even with the acquisition of high-quality solutions, exact methodologies can be very time-consuming for practical applications. Advanced optimization algorithms (including heuristics, hybrid heuristics, metaheuristics, etc.) are of great importance for real-world large-scale problems to obtain satisfactory solutions in a quite shorter computational time as compared to exact methods. In previous literature, a variety of advanced optimization algorithms have been applied to address EV charging stations planning problem, such as genetic based algorithm (Li et al. 2016b; Tu et al. 2016), hybrid heuristic (composed of the modified Sweep heuristic, the Iterated Greedy, and the Adaptive Large Neighborhood Search algorithm in Aghalari et al. 2023; combining of Clarke and Wright saving algorithm, an iterative greedy algorithm, and an adaptive large neighborhood search with simulated annealing in Guo et al. 2022), neighborhood search heuristic (Wang et al. 2019), etc. Future research extensions may be to develop other new advanced optimization approaches such as hybrid heuristic for the decision problem addressed in this study and to conduct performance comparison of the developed improved genetic algorithm against these algorithms.

5 Conclusion

This study examines how to deploy charging stations and allocate the charging demands of the valet charging service optimally. We develop a mixed-integer nonlinear program considering the characteristic of valet charging service. Based the queueing theory, we formulate the charging queuing system as queuing system, and the average charging waiting time is derived. The charging facilities construction cost (i.e., the charging piles construction cost) and service cost of charging staff (i.e., the cost of road service, round-trip time and charging waiting time) are balanced. We propose an improved heuristic using a genetic algorithm framework as the foundation to find superior station deployment and allocation plans efficiently. Numerical studies are conducted to examine the effectiveness of the proposed improved genetic algorithm in the Yangpu District of Shanghai, China. The results indicate that the modeling formulation and solution heuristic can converge efficiently and generate satisfactory deployment plans. It is necessary to conduct additional research to consider the practical limitations such as uncertainty and routes planning.