Abstract
Introduction
All the time, to maintain the sustained and stable power supply worldwide, we have to rely on thermal power consuming fossil fuels. While waterpower depends on natural environment, new energy resources such as solar and wind are growing steadily; nevertheless, they can hardly catch up with the scale of thermal power. Constraints on generating sources also bring regional power shortage, so does excess emission of greenhouse gases, which even becomes a threat to our living planet. 1 Since what we can do with the power generation is limited, the thought of turning to distribution procedure could be reasonable.
Based on high-voltage power grid, traditional electricity transmission infrastructure firmly accounts for the vast majority of power consumption. Large workload and high speed transmitting on power grid actually suffer large percentage energy loss both on the AC/DC rectifier transforming and transmission itself. 2 What’s more, high security risk brings multiple accidents by electric shock which cause huge economic loss and even casualties.
In recent years, in order to deal with some energy problems mentioned above, the concept of energy internet combining the ideas of energy industry and Internet of Things (IoT) starts to attract wide attention. As shown in Figure 1, just like the Internet, energy can be exchanged and shared similarly as information flowing in the Internet. All supply and demand on energy will be integrated into an interconnection network which may notably increase industrial production efficiency and bring convenience to our lives.

A schematic of energy internet.
Inspired by the concept of energy internet, we come up with a thought of designing a power distribution system which can partly play the role of power grid as the carrier of electricity from power plant to urban area. Power storage station can serve as the wayside charger for any electricity usage from mobile devices to electric bicycles or even cars. To approach the target building and sustain the system structure, we need electric vehicles (EVs) and vehicle-to-grid (V2G) technology as the technical support.
EV manufacturing and V2G technology jointly have entered the era of industrial manufacturing for more than 20 years. 3 Vehicles using electric power rely on V2G which allows electricity to flow between batteries in EVs and power storage devices, just as in the gas station. Actually, EVs can be powered in several ways by batteries, fuel cells or gasoline hybrids, here collectively referred to as charging/discharging. With V2G, we can expect more on mobility of EVs to complete the task of power exchange and transportation. 4
In summary, under the prospects of EV manufacturing and V2G technology, there exists the feasibility of designing a power distribution system which may serve as the supplementary of power grid.
In this article, we will focus on the algorithms of placing power storage stations in bus lines. Our main innovation points are as follows:
A designed power distribution system based on bus lines running EVs including the energy sources placed at the departure stations, power storage stations placed at bus stops, and fixed city bus lines as the connections. We want electric buses carrying electric power from energy sources to storage stations placed at some stopover bus stops.
Two branch algorithms for solving the basic storage stations placement problem, use real-world transportation data set of two city bus maps for simulation.
Analyze and compare the results between algorithms and city bus maps, evaluate the performance in solving the placement problem and whether it can confirm the assumption of system design.
There are seven sections in this article to display the overall details of the research. Section “Introduction” gives the introduction. Section “Related works” will present the related research in the past. Section “Problem description” will be the problem of analysis, elaborate process from initial idea to formation of algorithm. Section “Simulation and analysis” will take the main bus lines of Minhang District in Shanghai after collection to analysis and simulation, compare the two kinds of algorithms with random selection in terms of efficiency, robustness, and so on. Section “Practical considerations” will discuss the practical considerations. Section “Conclusion” will summarize the previous work and draws conclusions.
Related works
Thoughts about using EV carrying power to transmit electricity to where it passes actually are not so up-to-date, but there were too many obstacles in the front like the EV itself with defects such as low motor engine and load, also charge/discharge process. At this time, V2G came out and started to earn great attention. Aim at building contacts between EV and power grid, not only to bring convenience for EV owners who can charge cars just like in the gasoline station but also may inspire ideas about transmitting electricity in urban city.
A group led by Dr Willett Kempton in University of Delaware has focused on V2G for more than 10 years. This V2G group has made great contribution in both the blueprint for how an EV market be like in future and cooperation mode with vehicle manufacturing companies like Toyota as well as power department like PJM, which serves as the leading experimental unit in United States.
Other countries such as Japan, Denmark, UK, and South Korea also actively build up infrastructure. Early research paid more attention on the evaluation of how EVs can benefit us 5 or initial concept on V2G. 6 After establishing cooperative relationship with commercial company, some ideas of new attempts can be achieved then.7,8
Actually, there are many studies about V2G and its theoretic elongation. Early in 2012, a paper described a design of energy distribution system while using EV to set up power exchange network 2 which mostly inspired the idea of this article. The group also further focused on deploying energy router, 9 energy transfer route,10–13 energy scheduling, and allocation in the EV energy distribution network.14,15 With the plug-in technology, some new charging strategies can be drawn 16 to help integrating V2G with grid-to-vehicle (G2V) as a whole system, which brought far-reaching significance to follow-up research works.
Problem description
Figure 2 shows an example of the power distribution system based on EVs designed in this article. There are four departure stations which also serve as energy sources, six colored bus lines running electric buses, and three storage stations. The lightning symbols stand for the power supply relations, and all three storage stations, respectively, have three bus lines as supplement.

A power distribution system based on EVs.
As shown in Figure 3, three main parts of this power distribution system are renewable energy sources, power storage stations, and bus lines running EVs. We will design algorithms to place power storage stations at some of bus stops with shortest total distance from multiple energy sources in city bus map.

Setting and modeling.
The choice of quantitative standard was originally to directly use the actual distance between bus stops. However, after some preliminary work, we found many defects such as limited collecting method, difficulty in measuring precision, and soaring complexity in algorithm design. One of the real-world city bus maps, Minhang District of Shanghai, Shanghai, at the time of data collection, no matter where the bus line comes from and goes to, how many stops it contains, the physical distance between two stops always stays in the same numerical interval. Even though in some remote area, distance between two stops can be some extent longer, considering the small proportion and low possibility in traffic jam, time consumption stays the same level. According to the situation above, after some comparative analysis, finally, we decided to use stopover times for electric buses to take which also can express the meaning of physical distance, so as to make up for the defects as far as possible.
Power carried by electric buses is also unitized for facilitating the statistical calculation. A unit quantized value (uqv) will be set as one of the algorithm inputs. One single fully charged electric bus may carry fixed units of power and discharge a unit of power when passing a bus stop chosen to place storage station. Power exchange only at storage stations may reduce the wait time of passengers on bus as well.
There exist some considerations about the meaning of our work on the power storage station placement problem.
It seems like only some marking work on the city map can finish the answering. But after some previous studies, we have found two explanations.
First, the distribution of bus lines themselves. With reference to data collection of Minhang District, Shanghai, the overall distribution mainly considers the stream of people with more bus lines available in places such as shopping centers and leisure venues. Long bus lines including more stops usually locate departure stations at remote area and may not share parking lot with other lines, what’s more, time interval between two shifts can be much longer. In a word, it is unwise to place storage stations near these departure stations since storage stations only can receive power supply from one single bus line. Correspondingly, bus stops in short lines are usually not isolated, that is, even if the short lines themselves canceled, there are still other bus lines to take. Bus lines in this case usually have more often shifts and share departure stations with other lines, therefore high utilization rate can be achieved.
Second, considering the occurrence of congestion. Bus lines with fixed routes suffer a lot from traffic jam, which more likely to happen in area with large stream of people mentioned above. Once traffic was blocked, the power supply of storage station would be cut, therefore we have to make a trade-off on more bus lines and less impact from congestion.
After a comprehensive grasp of the placement problem, with corresponding mathematical model being established, the whole idea of solution can be divided into two, from one of the bus stops/lines to match/select the other. The algorithm steps and related figures are as follows:
Step 1: Sort and retain
Step 2: Each bus stop selects one stopover bus line in one cycle, loop over (e.g. red lines stand for the first cycle and blue stand for the second).
Step 3: Set a counter for each bus line to make sure that any bus line be chosen not more than
Step 1: Sort all of the bus lines according to number of bus stops, and once the number alike, put the one with less average number of stopover bus lines of the stops it contains (the
Step 2: Totally
Step 3: Retain the top
In Algorithm 1,
Two thoughts can be similarly regarded as instances of double-counting in combinatorial mathematics, conceptually in analogy with dual choice relationship between vertexes (power storage stations) and paths (bus lines).
Figures 4–9 also show that the power storage station placement problem is non-deterministic. Although we are trying best to use current available information to look for optimal choice, there may always leave some margins to be fulfilled. For instance, two power storage stations are waiting to be placed, considering the idea of bus stops with more stopover bus lines, the top two share one single stopover bus line with only one time left to be chosen, which means once we choose the top 1 or 2, the other one also lose the possibility to be chosen from. The selection criteria we have set may only stick to the initial status, any decision made in steps will bring some local variation playing a role of indefinite factor. The reselection in Step 3 of Algorithm 2 (Figure 9) aims to reduce the influence from steps ahead, but some of the choices made on the rest bus stops may not find a substitute in the top

Algorithm 1 Step 1.

Algorithm 1 Step 2.

Algorithm 1 Step 3.

Algorithm 2 Step 1.

Algorithm 2 Step 2.

Algorithm 2 Step 3.
Simulation and analysis
At first, we use a city bus map of Manhattan, New York City, 17 which is available to everyone for study usage through the Internet, to help testing and improving two branch algorithms in a data set with dense distribution of bus lines. After some necessary data screening and pretreatment, 18 bus stops and 29 bus lines are collected from the traffic map of Manhattan.
Consider total number of stopover times at all bus stops and average times to get a unit power which stands for the cost on carrying one unit of electric power from energy source to storage stations as metrics for simulation and analysis. Set the number of needed power storage stations from 3 to 10. Simulation environment is MATLAB R2016a.
In Figure 10, three colored broken lines stand for different unit quantized values (uqv) mentioned above. Figure 10(a) shows the total stopover times at bus stops needed by all bus lines to support power storage stations in Algorithm 1 while uqv

Simulation results of Manhattan in two algorithms.
Minhang District in Shanghai is chosen because of the facility and convenience of data collection. After sorting and correction, a total of 62 bus lines (including round trip), 489 bus stops in Minhang District, Shanghai complete the main database. The longest bus line named Minhangshuniu 4 contains 41 stops while the shortest Jiangchuan 7 only has 5. Covered by various kinds of traffic and flow conditions of people in Minhang District, the self-built database can test not only the algorithm performance but also the actual status of various possibilities. Set the number of needed power storage stations from 5 to 30.
Similarly, Figure 11 describes the total stopover times needed to support power storage stations been chosen, and Figure 11(b) shows the average stopover times for one single unit power. The increasing amount of data make more storage stations be chosen at one time possible as well as more precise simulation result, showing more detailed changes. Red, blue, and green broken lines, respectively, stand for the same meaning like before, with the storage station number scope of 5–30. The overall situation corresponds with expectation, as the number of storage stations increases, total stopover times are lower than the linear slope. An explanation could be, in Figure 11(a), total number comes across a pitch point near 15 of horizontal axis which may determine the rapid increase, and then a fixed association pattern between vertexes and lines takes shape.

Simulation results of Minhang in Algorithm 2.
Also, as shown in Figure 11(b), there is a peak near 15 of horizontal axis which means it may take more stopover times to get one unit power than other power station numbers away from 15. It can be judged that the current database used by Algorithm 2 in the selection of power storage stations may just avoid this range.
In order to immediately find out the advantages and disadvantages of the algorithms in terms of performance, there is a comparison among Algorithm 1, Algorithm 2, and random selection. The random selection applied here is designed by replace greedy method by random number generators only in key steps to help making the experimental results more persuasive.
In Figure 12, red, blue, and green broken lines, respectively, stand for average stopover bus stops getting one unit power of Algorithm 1, Algorithm 2, and random selection (uqv

Comparison among three algorithms.
According to the special structure of Algorithm 1, that is, bus lines chosen by potential power storage stations can supply at most

Utilization rate of bus lines in Algorithm 1.
The colorful lines still stand for the same range of
Step back to Figure 12, steady improvement in bus line utilization ratio may guarantee the times of empty choosing motion (bus lines sometimes have
Practical considerations
Although we have proposed a solution to the power storage station placement problem, still a lot more practical considerations can be included. As described in section “Related works,” our assumption is based on the high performance of battery and charging/discharging technology, actually some practical considerations are needed.
Consider a K9 electric transit bus manufactured by BYD with battery capacity of 32 kWh and max power of 100 kW×2. 18 A normal bus line can be 10 km, and to perform the route at a speed of 30 km/h, a K9 may use up 10÷30×200 = 66.67 kWh in max power (100 kW×2), the rest electric power is 324–66.67 = 257.33 kWh. If we set the uqv to 3, which means 257.33÷3 = 85.78 kWh can be carried to one power storage station. With the energy efficiency for a complete charging/discharging process of 90%, 19 about 77 kWh of power can be stored, 20 shifts a day may provide more than 1500 kWh.
However, there still exist other constraints that make real situation far from reaching the measurement above. The charging/discharging time, nowadays, to get an electric bus fully charged may cost more than an hour. Fast charging technology still needs development to deal with large capacity batteries. Extra cost on frequent stop-and-start and aging of batteries as well may affect the stability and robustness.
Another consideration about the connection between power plants and departure stations of bus lines. Imagine that we also use electric buses to carry from power plants to departure stations. To transport 2000 MWh electric power along 100 km, one K9 electric bus can use up 100÷100×200 = 200 kWh itself with the max speed, 18 considering of a round trip, the battery capacity even cannot afford the travel consumption.
Actually, granted that we could transport all the power stored in the battery to destination, to complete the whole target, there can be thousands of (2,000,000 / 324 ≈ 6173) buses waiting for discharging. As a result, we can never wish only electric buses can replace the power grid. To make the designed power distribution system feasible, grid system between power plants and departure stations is still needed at the moment or in the near future.
Runtime data were recorded by the profile timer of MATLAB R2016a for two algorithms using two city bus maps. Algorithm 1 in Manhattan is 3.433 s, and Algorithm 2 in Manhattan is 3.445 s. Algorithm 1 in Minhang is 4.841 s, and Algorithm 2 in Minhang is 432.035 s. Algorithm 2 seems to behave more sensitive to the larger size of data, the reselect step (Figure 9) observably increases the time complexity.
Early since 2004, research group led so far by Dr Willett Kempton from University of Delaware, the development of V2G technology has experienced a number of stages. As shown in Figure 2, histogram shows the cost of batteries, in United States dollars per kilowatt-hour (left vertical axis), been made, nearly 1000 in 2008 and now gradually stabilize at more than 200. Line chart stands for the watt-hour per liter (right vertical axis) of batteries, which rose steadily at first and then surged in and after 2013, and in 2015, a battery of one liter could store 0.3 kWh. China started early in the field of EV, also the global leader in the electric two-wheelers market and almost the only relevant player globally, making a model of energy saving and emission reduction. What else, China is also leading the global deployment of electric bus fleets, with more than 170,000 buses already circulating in 2015. In addition to the capacity part, battery charging and discharging have shrunk. 18 The Ohio’s Nanotek Instruments Company found by experiments that use lithium ion between the graphene electrode surface and rapidly shuttling characteristics to develop a new form of battery, that is, the graphene battery which earns great attention in the field of new energy currently. 19 Compared to the traditional battery, the charging process can be achieved immediately on the small capacity of the electronic equipment. Of course, the technology is not mature and costly, which cannot be directly translated into economic benefits in recent years.
Conclusion
This article proposes a power storage station placement for a designed power distribution system based on EVs to achieve a certain scale of power delivery. In consideration of the energy loss and insecurity factor, we attempt to look for new ideas to deal with energy problems worldwide. However, it is still far away from solution, let power grid transmission alone to take place someday.
Our work also needs further optimization such as different strategies for varied city forms, larger data set with optimization tools to test the runtime of algorithms, and corresponding analyzing treatment, more metrics like charging latency may bring more detailed assessment. In the future, we will identify the difference between security and routing problems in energy internet and traditional internet20–22 or wireless networks.23–25 We will also investigate algorithm efficiency and exception handling like measurement of traffic jam.
