Mathematical Analysis of Electric Vehicle Movement With Respect To Multiple Charging Stops

Set up in two dimensions, the model assumes $|O|$ = trip start points (origins) $O\in (1,\dots ,o,\dots ,|O|)$; $|D|$ = trip end points (destinations) $D\in (1,\dots ,d,\dots ,|D|)$ and $|K|$ = EV charge stations $K\in (1,\dots ,k,\dots ,|K|)$. It further assumes that $T_{od}$ EVs travel from an origin ($o$) to a destination ($d$) within the origin destination (OD) matrix. The maximum cruising distance of the EVs is $L$. The EVs that are unable to travel from $o$ to $d$ without charging their batteries must use one of several charge stations. Under these assumptions, the number of EVs arriving at each charge station will be derived.

Now, a directed graph $G=(V,E)$ connecting paths (i) through (iv) is introduced, where the distance between two points is $L$ or less ($V=O\oplus D\oplus K$):

All conceivable paths of EVs traveling from the origin to destination in this network are expressed on the directed graph $G$, and path(s) that can be expressed on the directed graph $G$ are the only feasible paths. An example of an EV routing network is shown in Fig. 1.

Given the previous conditions and assumptions, an EV moving from an origin ($o$) to destination ($d$) on the directed graph $G$ is considered. Many paths linking $o$ to $d$ are available, including one that utilizes the shortest travel time. Understandably, the path of shortest travel time will be used most frequently, and the longer the travel time of a path, the less frequently it will be used. To incorporate this concept into the model, the probability that an EV moving from $o$ to $d$ will use the $r$th path is specified. On the basis of the multinomial logit model, the probability is defined aswhere $\gamma$ = cost-decay parameter; $C_r^{od}$ = cost of traveling the $r$th path from $o$ to $d$; and ${\mathrm{\varphi }}^{od}$ = set of paths from $o$ to $d$. In this study, $C_r^{od}$ = sum of link costs, and is expressed as

Here, the $r$th path is the following route from $o$ to $d$: $o\to k_1\to k_2\to \cdots \to k_{\mathrm{\Lambda }}\to d$, $d_{**}$ is the distance between two points, $v$ is the speed of the EV, and $T$ is the time required for rapid battery charging. The definition of Eq. (2) assumes that EV drivers can refuel the EVs at their origin and always refuel when they reach EV station nodes. In addition, it assumes that the travel speed is constant, regardless of traffic volume.

There are a number of rationalities to introduce the logit model when describing routing behavior. First, in the field of traffic engineering, the logit model and its extensions are the main method to describe a driver’s route choice. Indeed, the stochastic user equilibrium traffic assignment model internally assumes the logit model in route decision behavior (Brilon et al. 2011). Some might consider that long-distance drivers usually use major highways and have few choices in their routes. However, Japanese highway networks mainly develop in a north-south direction, so drivers tend to use other roads, which have many alternative routes. Moreover, access-egress routing behavior for highway networks is also an important factor because drivers do use highways.

How to define the alternative set ${\mathrm{\varphi }}^{od}$ is now discussed. In the simple definition, the alternative set consists of simple paths. In this study, however, all possible paths which connect origin and destination are considered. This strategy has the possibility of generating very long detours that would not be selected in real-world routes. Furthermore, it seems difficult to calculate the probability for large-scale networks.

On the contrary, this definition is made to enhance computational feasibility. As discussed in later sections of this paper, this definition makes it possible to perform stochastic assignment in large-scale networks.

To determine the value of $p(j|i)$, $W_{id}$, which is included in $p(j|i)$, must be calculated. The native approach is not feasible because the summation in $W_{id}$ means considering all paths from node $i$ to $d$.

Consider matrix $\mathbf{A}$ of $N\times N$, whose $[i,j]$ element is given as follows:

The element of ${\mathit{A}}^2$ yieldswhere ${\mathrm{\varphi }}_L^{ij}$ = set of paths that connect nodes $i$ and $j$ in $L$ steps. Similarly, the typical element of ${\mathit{A}}^L$ is given by

From the definitionis derived. Consequently, the value of $W_{id}$ can be obtained as follows ($\mathit{I}$ is the identity matrix):where the element of matrix $\mathit{W}$ is

Furthermore, if matrix $\mathit{A}$ satisfies the Hawkins-Simon condition (Hawkins and Simon 1949; Seneta 2006), the following formula is obtained:

Therefore, the value of $W_{ij}$ is obtained as follows:

As indicated previously, determining the link-weighted matrix $\mathit{A}$ yields the transition probability $p(j|i)$ in a straightforward manner. This means that all EV movements will be calculated only by setting matrix $\mathit{A}$. This is feasible because Eq. (16) is just one calculation for the matrix inverse.

Note that the EV travel can be described by the Markov model. Next, the Markov process that reaches destination ($d$) is investigated. When the transition matrix between nodes in the Markov process is defined by Eq. (18), the number ($N_{id}$) of EVs entering each node (while traveling toward the destination) is determined by Eq. (19):where $T_{od}$ = number of EV movements from origin ($o$) to destination ($d$). Thus, the number ($N_k$) of EVs arriving at charge station $k$ can be derived as follows (independent of destination):

This is one of the most important pieces of information to calculate in this paper.

At the end of the formulation, the average cost from origin ($o$) to destination ($d$) is also calculated.

Now, focusing on the movement from origin ($o$) to destination ($d$), the probability of pass-through link $(i,j)$ is described as $q_{ij}^{od}$. Through the formula stated previously, the average cost $⟨C_{od}⟩$ can be written as

In order to calculate Eq. (21), it is necessary to derive $q_{ij}^{od}$. Here, focusing on the fact that EV movements can be described as a Markov model, the Markov process to destination node $d$ is considered again. Then, for the movement from origin ($o$) to destination ($d$), the probability of passing each node $Q_i^{od}$ is calculated aswhere ${\mathit{e}}_o^T$ = unit vector in which only the $o$th element is 1 and 0 otherwise. Consequently, the probability $q_{ij}^{od}$ that passes through link $(i,j)$ iswhere $\mathrm{diag}(·)$ = diagonal matrix with the applicable component as a diagonal element.

Eq. (23) is basically the same as the Akamatsu model (Akamatsu 1996), and thus, there are minor contributions to theoretical aspect. Rather, the key finding of this paper is to show that the Akamatsu model can clearly apply to EV routing behavior and the arrangement of mathematical expressions for EV routing, such as average travel cost calculation. Thus, it is also very important to show that the formulation is applicable for practical use. For this purpose, the quite large-scale problem with realistic data is calculated in the next section.

The model described in the previous sections is applied to the movement of traveling passengers in Japan (excluding Hokkaido and Okinawa) to estimate the number of EVs arriving at the charge station. In the following calculation, it is assumed that the vehicles driving in the target region were all replaced with EVs.

First, how to prepare OD data is explained. From the Third Interregional Travel Survey (MLIT 2010b) issued by the Japanese Ministry of Land, Infrastructure, Transport, and Tourism, there are several OD flow data that focus o,nvarious transportation methods and trip purposes. In this study, the OD data of “vehicle,” “weekday,” and “all purpose” is extracted. This OD data is aggregated between 207 zone movements. Thus, the 10-km mesh population data of national population census 2010 (MLIT 2010a) is also used, and OD data is proportionally allocated to each mesh. Using the previous calculation, the OD data between 3,460 mesh movements is created. The centers of each mesh are set as origin and destination points. Mesh population data is shown in Fig. 2.

Next, the EV charge-station data is prepared. According to CHAdeMO Association, 2,151 EV-charging stations have rapid chargers currently installed (CHAdeMO 2013). The locations of these 2,151 EV stations are used as the distribution.

Finally, the travel cost between two arbitrary points based on the real road network is calculated. In this study, the detailed road network data, which are also used for car navigation systems (Sumitomo 2005), is prepared, and the shortest distance path is calculated. Furthermore, the distance is converted to travel time (= cost) under the assumption that EV travel speed $v=80\mathrm{km}/\mathrm{h}$ on highways, $v=60\mathrm{km}/\mathrm{h}$ on metropolitan expressways, and $v=30\mathrm{km}/\mathrm{h}$ on ordinary roads. Fig. 3 shows the detailed road network data, and Table 1 is the size of this data.

Using this geographic information science (GIS) data, the EV routing network, which was explained in the formulation, is constructed. Fig. 4 shows the EV routing network in this study, and Table 2 shows the size of this network. It is assumed that the time for rapid battery charging ($T$) is 40 min and the maximum cruising distance of the EV ($L$) is 120 km.

The number of EV arrival to each station is first analyzed based on the mathematical model. It is assumed that parameter $\gamma$ is 0.1. Based on the previous network, the calculation results are shown in Fig. 5 (indicating the number of EVs arriving at the charge station per hour).

From the figure, it can be confirmed that the stations located around large cities and near arterial roads are the most frequently used. It can be seen precisely that the number of EVs arriving at stations near metropolitan areas, such as Tokyo, Nagoya, Osaka, and Fukuoka, evidently increases. In addition, the regions connecting Tokyo, Nagoya, and Osaka, known as the Higashi-Meihan regions, have been confirmed to have a significant number of arriving EVs. The previously mentioned results can be properly understood because the number of arriving EVs must be proportional, to some extent, to the passing traffic at that spot from a general perspective. Meanwhile, rural areas such as Tohoku, Chugoku, and Sanyo do not have as many EVs as metropolitan areas. Generally, these rural areas have a number of stations, where approximately 100 EVs are estimated to use. Therefore, a certain amount of EV stations must be installed even in rural areas, which are low-demand areas. From this viewpoint, it is suggested that infrastructure improvements are important on a nationwide scale. The most important point when planning the strategy of infrastructure improvements is appropriate allocation based on EV arrivals.

Fig. 6 is a histogram of the number of EVs arriving at the charge station per hour. Approximately 72.6% of the 2,151 stations are visited by 100 EVs per hour or less (average number of EV visits is $95.7\mathrm{cars}/\mathrm{h}$). In contrast, the number of EVs arriving at the busiest station is $\mathrm{3,793}\mathrm{cars}/\mathrm{h}$, suggesting that many chargers will be needed in that station.

The queuing theory (Haviv 2013) is introduced here. An EV-charging station can follow the typical M/M/s queuing model. Therefore, $\lambda /s\mu <1$ must be satisfied; here, $\lambda$ = arrival rate of EV per hour; $\mu$ = service rate of EV quick charger per hour; and $s$ = number of EV quick chargers in an EV-charging station. This equation means that the number of arrivals to the queuing system cannot exceed the total service potential of the system. Therefore, this equation must be satisfied in any queuing model. Now, it is assumed that each EV occupies the charging station for approximately 40 min on average (considered storing, charging, and retrieving) and the number of EV chargers is two (most stations only have one charger at present), and the actual diffusion rate of EVs is $\alpha$. Thenare derived. Thus, in the actual situation, this can be managed if the actual diffusion rate of EVs is less than 0.079%.

However, the condition $\lambda /s\mu <1$ only assures that the waiting queue would not increase infinitely. In a practical sense, queue length (and waiting time) infinitely diverges when $\alpha$ is close to the limit stated in Eq. (25). Fortunately, by the formula of $M/M/$$s$ queuing model, the waiting time at EV stations can be also calculated. For example, to set the average waiting time to less than 5 min, $\alpha <0.026\%$ should be satisfied from M/M/s formula. In any case, the most important point is to calculate the arrival number of EVs, which is shown in Fig. 5.

Next the average travel time from origin to destination is examined. It is also a very important factor to evaluate the convenience for EV users. The average travel time by EVs can be derived as well, using the previously mentioned formulas.

Fig. 7 is a histogram of the average travel time (including charging time) on an EV routing network. Approximately 63% of EVs travel 6 h or less (average number of EV visits $242.15/\min$). In contrast, the maximum travel time is near 50 h.

By calculating the time of shortest distance, which supposes gasoline cars, both times are now compared to evaluate the inconvenience of EV usage. Fig. 8 is a scatter diagram of the EV time and the gasoline car time. From the figure, it can be confirmed that EV users are obligated at a maximum 1.4-fold time. This is mainly because of the need for detouring to charge the battery.

To illustrate the regional difference in terms of EV trips, the following index is calculated:where $⟨C_{od}⟩$ = average travel time by EVs; and $C_{od}^{\min }$ = time of the shortest distance by gasoline cars. As is clear from the definition, $R_o$ = average ratio, which indicates the proportion of EV and gasoline cars. If $R_o$ is large, the region would be disadvantaged by the conversion from gasoline car to EV. The calculation result of $R_o$ is shown in Fig. 9. From the figure, it can be confirmed that the Kyushu regions, and Ibaraki prefecture have large $R_o$ which means the “EV refugee.” Therefore, in terms of the development of EV infrastructure, the Kyushu region and Ibaraki prefecture are very important for investment. In parallel, controlling the diffusion rate of EVs may be another important way to cope with the lack of infrastructure in such areas.

Note that the result $R_o$ is not weighted by OD data and population. Obviously, it is easy to incorporate the weighted average of $⟨C_{od}⟩/C_{od}^{\min }$ by OD data. However, if the weighted average were introduced, it would be apparent that the ratio of rural areas tends to be worse than that of metropolitan areas. This is because $⟨C_{od}⟩/C_{od}^{\min }$ generally increases with the increasing distance between origin and destination. Such analysis is not the authors’ intention. By not taking account of OD data and populations, it is possible to illustrate the inconvenience caused by the location of EV stations.