An Octopus Charger-Based Smart Protocol for Battery Electric Vehicle Charging at a Workplace Parking Structure

Abstract

The transportation sector produces a large portion of greenhouse gas emissions in the United States. Meeting ambitious reductions in greenhouse gasses requires large-scale adoption of battery electric vehicles and has led to several policies and laws aimed at incentivizing their sales. While electric vehicles comprise a small percentage of the overall fleets of vehicles, the expected production of electric vehicles is soon expected to be in the millions. This will create challenges in providing an adequate charging infrastructure, as well as the ensuing management of the overall electricity demand at the grid level. In this work, a novel smart-charging protocol for battery electric vehicle charging at workplace parking structures is proposed. The Octopus Charger-based Mixed Integer Linear Programming protocol allows octopus chargers (i.e., charging stations with multiple cables) to independently schedule charging periods for their assigned vehicles. The proposed protocols can manage a parking structure demand load while reducing the number of installed charging stations. Driving patterns from the National Household Travel Survey were used to perform simulations, to verify and quantify the effectiveness of the proposed protocol. The proposed protocol resulted in improved peak load reductions for all simulated smart-charging scenarios when compared with uncontrolled charging. Critically, the assignment algorithm resulted in a number of required chargers close to the theoretical minimum.

1. Introduction

1.1. Motivation

The need to meet ambitious reductions in greenhouse gas emissions and fossil fuel consumption has increased interest in plug-in electric vehicles (PEVs) [1]. PEVs are defined as vehicles that charge from the grid, and encompass both plug-in hybrid electric vehicles (PHEVs) and battery electric vehicles (BEVs). Since PHEVs can be refueled with electricity and fossil fuels, they create less range anxiety, which can be a major impediment for the adoption of BEVs [2]. BEVs, on the other hand, rely solely on electricity, which offers intriguing opportunities and creates significant challenges. Here, our focus is on the fast growing (fully) battery electric vehicles, BEVs. When reviewing references, we try to be consistent with the terminology used in the citations and use the term PEV when the reference dealt with both PHEVs and BEVs.

In 2019, the transportation sector and electricity generation made up 29% and 25% of greenhouse gas emissions, respectively, in the United States [3]. In [4], it was shown that meeting ambitious reductions in greenhouse gasses, such as those planned for California, requires large numbers of PEVs. While recent years have seen significant increases in PEV sales [5], an inadequate charging infrastructure could be a major obstacle for a large-scale adoption of PEVs [6]. A survey [7] found that 71.7% of participants placed a high degree of importance on having charging facilities at work or near businesses they frequent when considering a future PHEV purchase. In [8], it was also found that increases in charging station deployment result in increases in electric vehicle (EV) sales. Employees with access to workplace charging are also six times more likely to own a PEV than those without such access [9].

Generally, PEV charging can be categorized as destination charging and urgent charging [10]. Urgent charging involves charging on the road due to a low state of charge (SOC). Destination charging, however, involves charging at locations where the driver plans to park their vehicle (i.e., home, workplace, etc.). While much of the required charging can be carried out overnight at home, other destination charging locations can provide valuable charging opportunities [11], and shifting charging to periods of high renewable generation can alleviate the curtailment of renewable resources [12]. Workplace parking structures provide a highly effective means for the delivery of electricity due to the extended dwell times of vehicles, high predictability of the dwell times, and trip distances that might be undertaken in the course of a workday. Significant investments in charging infrastructure would, however, be required by property owners to provide such charging opportunities. Programs to provide subsidies for charging infrastructure underline the difficulty associated with securing such investments.

Such infrastructure costs may be difficult to justify since traditional single-cable charging stations go unused for long periods of time. In [13], it is found that losses in potential revenue can be exacerbated when charging stations are occupied by fully charged BEVs. This often causes frustration for drivers that do not have access to an available charging station [14]. In [15], this “overstay” problem is addressed by developing a system to interchange fully charged BEVs with those waiting for service, either automatically by a machine or manually by a human. In [16], it is found that charging needs for most drivers can be met with 1.44 kW charging. Thus, utilization rates for higher kW chargers at non-home charging locations could be quite low. As estimated in [17], for constant 1.92, 3.6, 6.6, and 10 kW charging, BEVs only used traditional single-cable charging stations 11.14%, 6.28%, 3.48%, and 2.30% of the time during a 24-h period, respectively. This corresponds to 33.02%, 18.86%, 10.51%, and 6.97% of the time they are parked, respectively.

In [9,18], “octopus chargers” are proposed as a cost-effective method to increase both access to chargers and utilization rates. Octopus chargers are designed to contain several cables, such that a single octopus charger can charge multiple PEVs. In [17], we proposed a comprehensive smart-charging protocol that can be applied with either traditional single-cable chargers or octopus chargers. Due to this versatility, however, the protocol required a total number of chargers significantly larger than the theoretical minimum in several cases. Thus, smart-charging strategies specifically developed for octopus chargers are needed to minimize the number of chargers and the corresponding infrastructure costs required at parking structures.

Sales of battery electric vehicles have grown significantly in recent years [5], partly due to the emergence of high-range BEVs. Higher ranges, however, require larger battery sizes, which, in turn, require higher charging rates. The pairing of large numbers of BEVs with higher charging rates can result in damaging load increases at both the grid and local levels [19,20]. Such load increases could negatively affect circuitry, increase electricity costs, and exacerbate stress to local electrical components during critical times (e.g., high usage periods on hot days). With the appropriate smart-charging strategies, however, parking structure operators can reduce peak electrical demands while also reducing the number of required chargers.

1.2. Contributions

In this work, a distributed computational approach to address the charging needs of a large number of BEVs at a workplace parking structure is presented. The primary goal is the significant reduction in infrastructure costs, while also shaping the overall demand profile of the parking structure to reduce operational costs. While some of the assumptions and motivations presented here may be more apparent in commercial applications (e.g., buses or delivery vehicles), we focus on private vehicles charging at workplace parking structures. This is primarily due to the availability of non-proprietary high-quality data from the National Household Travel Survey (NHTS) to evaluate the proposed protocols. The approach here is aimed at three objectives, in their order of priority: (i) reducing infrastructure costs associated with providing charging for a large number of BEVs by relying on octopus chargers, (ii) developing load shifting capabilities, in response to extreme grid stress levels or emergencies, and (iii) reducing electricity costs for the parking structure operator by taking the variable cost of electricity from utilities into account.

The proposed approach relies on the following information being available to the processing units at the start of the protocol: (1) The charging power of the BEV and its battery capacity, (2) the state of the charge (SOC) of the battery when entering the structure and the minimum energy required when leaving the structure, and (3) if there are multiple dwell times at the structure, the duration of each exit and the associated travel distance. This information can be known approximately, with currently available technology, as long as some measure of conservatism is incorporated. The burden of making the information available is modest, with the possible exception of a workday with multiple disruptions (lunch breaks, errands, etc.). Note that such information is more easily available in commercial applications.

The following are the main aspects of this work. (1) BEVs are assigned to octopus chargers based on charging flexibility, through the modification of a simple and well-known algorithm. (2) A smart-charging strategy is proposed, that allows octopus chargers to schedule charging for their assigned BEVs via mixed integer linear programming (MILP) methods (Section 4). (3) By allowing octopus chargers to act as individual agents/aggregators, adjustments can be made to accommodate BEVs with unexpected, late arrivals. (4) The computational burden of the protocol is removed from the central node/processor and distributed among the octopus chargers. (5) With the appropriate cost signal, octopus chargers can manage the parking structure demand load in a distributed manner.

A similar problem was studied in [17]. The key difference between the approach presented here and that of [17] is the emphasis on objective (i) above. While the recurring cost of energy can be passed to BEV drivers, the infrastructure costs associated with the requirement of a large number of high-power chargers remains a significant challenge. To address this, the protocol presented here utilizes MILP methods to significantly reduce the total number of required chargers. This, in turn, increases the utilization rates of the installed chargers and automatically limits the maximum power demand of the parking structure. Due to the small number of vehicles assigned to each octopus charger, the proposed protocol can ensure tractable MILP solutions for octopus chargers, that meet the energy needs of all simulated BEVs.

Lastly, the protocol proposed here also assumes that the BEVs have hardware that require charging at a set (i.e., maximum) power level. To accomplish this, MILP is needed. If this limitation on power level is not present, the algorithm can be easily modified to a simpler linear program that is faster but will result in BEVs receiving charge at partial power levels (Section 4.1).

1.3. Literature Review

There is a large body of literature addressing various aspects of BEV charging. Often PHEV protocols are applicable to BEVs with the appropriate modifications. Similarly, while this work is focused on BEVs, it can also accommodate less-constrained PHEVs as well.

Smart-charging strategies, aimed at performing valley filling at the grid level, have been proposed by several research groups. In [21,22], distributed smart-charging strategies that perform valley filling and scale well with large numbers of vehicles are presented. The strategy in [21], however, requires all EVs to participate in the iterative process, which results in significant communication demands. The strategy in [22] reduces these communication demands by only requiring EVs to communicate with their neighbors. In [23], a decentralized smart charging strategy based on the stochastic switching control of on-board chargers is proposed. While these grid-level smart-charging strategies may not necessarily be beneficial for workplace charging [24], some elements of these strategies can be incorporated in workplace smart-charging protocols with minor modifications.

Smart-charging protocols for various destination charging locations have been proposed in several works. In [25,26,27] various vehicle-to-grid (V2G) charging protocols aimed at reducing electricity costs for drivers, while providing power system flexibility, are presented. An energy management system that allows parking lot operators to use aggregated PEVs to participate in demand response programs is proposed in [25]. In [26], a transactive operational model that takes advantage of the long dwell times and predictable departure times associated with airport parking lots is presented. In [27], a three-stage stochastic-based approach to integrate the flexibility of PEVs, parked in large shopping centers, into power systems with high penetration renewable generation is proposed. In this work, however, V2G is not investigated, and focus is given to more readily available technologies (i.e., grid-to-vehicle charging).

Smart charging can alleviate the curtailment of renewable sources (at high penetration levels) by shifting PHEV charging to periods of high renewable generation [12]. For example, the interaction of parking lots in the energy and reserve markets can decrease wind farm spillage in the morning when PEVs are arriving at parking lots [28]. Similar interactions can be applied to solar power generation, which typically peaks during daily working hours. When users have access to workplace and public charging, shifting EV charging to midday hours via time-of-use rates reduces the need for ramping capacity and, thus, advances photovoltaic integration [29]. The energy storage capacity of grid-connected parking lots, however, can vary significantly and depends on operational characteristics and PEV charging patterns [30]. Thus, smart-charging strategies can be developed to lower operational costs to parking structures, while also increasing the utilization of renewable resources [31].

Furthermore, by installing EV chargers at workplace parking structures, employers can provide charging opportunities for long-range commuters and BEV owners without access to home chargers (e.g., apartment dwellers). In [11], it was found that the second most opportune time for PEV charging is at work (behind home charging). While in [32], it was found that residential and office charging sites offer the greatest potential for load reduction, with the lowest impact on customers. Thus, the focus of this work is on workplace parking structure BEV charging. Note, however, that the protocol proposed in this work can be applied to other destination charging locations (Section 7).

In [33], the impact of various centralized smart-charging protocols on workplace transformers were studied. A strong connection between minimizing daily peak loads and transformer’s health was found. It was also found that rate schedules including demand charges or capacity management are best for transformer aging. A centralized scheduling system for EV charging at parking lots is proposed in [34]. The optimization-based approach uses a two-layered framework to handle the effects of random deviations from typical driving patterns. In [35], a modeling method for centralized charging is presented that reduces the computational burden of the optimization algorithm, which does not increase with the number of PEVs. While in [36], a heuristic fuzzy particle swarm optimization algorithm is proposed for scheduling EV charging while minimizing electricity costs. A centralized MILP energy management system that incorporates bidirectional EV energy trading to reduce electricity costs at a university office building is proposed in [37]. In [38], a centralized nonlinear optimization model for an office building, which removes the bidirectional charging assumption from [37], is proposed. Iterative and/or centralized methods, however, are often not suitable for real-world applications due to privacy, communication, and computational requirements.

A two-stage stochastic programming model for planning parking structures equipped with multiple-cable charging stations is proposed in [10]. The centralized approach uses MILP to take the influence of coordinated charging into consideration. In [39], three smart charging strategies based on assigning BEVs to octopus chargers are presented. A demand load is first generated in a centralized manner. BEVs are then assigned to chargers with the aim of replicating the previously generated demand profile, which can result in some BEV charging requests not being served. A charging protocol that allows BEVs to be charged by either single-cable chargers or octopus chargers is presented in [17]. The protocol reduces peak loads, monthly electricity costs, and the number of required chargers. Furthermore, by allowing BEVs to individually generate their charging profiles, the decentralized protocol can guarantee BEV owners a measure of privacy, while participating in smart charging.

1.4. Summary

The key challenges for advancing workplace charging are increasing utilization rates for chargers and reducing infrastructure and operating costs. While some works have addressed these challenges by developing smart charging solutions that utilize octopus chargers, most depend on a central node/processor generating charging profiles for all BEVs in a centralized manner. A key contribution is the circumvention of centralized solutions, which are unlikely to be computationally practical for large parking structures, particularly with unexpected BEV arrivals, each of which would likely require a new centralized solution. We approach this by assigning a small number of BEVs to each octopus charger. Enabling the octopus chargers to act as intermediating agents. This removes the computational burden from the central node/processor and instead distributes it among the octopus chargers.

As a result, our proposed approach (1) can ensure tractable (MILP) solutions for octopus chargers that meet the energy needs of all BEVs, (2) has a distributed computational structure with a modest central processing task that can easily be scaled up for large numbers of vehicles, (3) can accommodate unexpected BEV arrivals, which would require a new solution at the octopus charger level only, (4) treats octopus chargers as independent agents that aggregate the data of their assigned BEVs, thus, providing BEV drivers a measure of privacy, and most importantly, (5) reduces the number of required octopus chargers to a number close to the theoretical minimum, while also creating the ability to manage the overall parking structure demand loads toward solutions with desirable characteristics.

Our article is structured as follows. Section 2 presents an overview of our proposed Octopus Charger-based Smart-Charging Protocol. Section 3 provides the algorithm used to assign BEVs to octopus chargers. The MILP problem formulation solved by each octopus charger, to schedule charging for its assigned BEVs, is presented in Section 4. The parameters, data, and related assumptions used to simulate the proposed smart-charging protocol are provided in Section 5. Simulation results for the proposed protocol are presented in Section 6. Section 7 gives potential extensions of the proposed Octopus Charger-based Smart-Charging Protocol. Finally, Section 8 summarizes the conclusions of this work.

2. Overview of Octopus Charger-Based Optimization Protocol

A flowchart providing an overview of the Octopus Charger-based Optimization Protocol is presented in Figure 1A. For the charging protocol proposed here, it is assumed that a set number of octopus chargers with a set number of cables are installed in the parking structure. Each BEV first shares its charging flexibility (defined in Section 3) with the central node of the parking structure. The central node then assigns each BEV to an octopus charger for the entire workday, based on a modified well-known algorithm (see Section 3). Once assigned, BEVs share their expected driving patterns for the day (along with basic BEV specifications/information) with their assigned octopus chargers. Octopus chargers are organized in a queue, which will dictate the order in which they generate charging profiles for their assigned BEVs. The order of the octopus charger queue is not critical in this protocol and can be arbitrarily chosen by the parking structure operator.

Once each octopus charger is ready to generate the charging profiles of its assigned BEVs, it generates a cost signal based on the desired charging strategy. If the parking structure operator decides to perform the “Early Charging” strategy, then each octopus charger can simply generate its cost signal based on the equations in Section 4.2.1. If the parking structure operator decides to perform the “Valley Filling” or “Augmented Cost Signal” strategies, then each octopus charger first receives an updated parking structure demand load from the central node. Each octopus charger then uses the updated parking structure demand load (an aggregation of the initial parking structure demand load and all previously scheduled BEV charging) to generate its own cost signal (see Section 4.2.2 and Section 4.2.3). The charger then uses a mixed integer linear programming (MILP) algorithm, with a modest number of variables, to generate its assigned BEVs’ charging profiles (see Section 4). The octopus charger then sends its own overall demand profile to the central node of the parking structure to update the parking structure demand load for the next octopus charger in the queue.

In essence, each octopus charger serves a subset of BEVs by acting as an independent aggregator. Doing this ensures that BEV driving patterns are not shared beyond the charger, which allows for a measure of privacy protection to be incorporated. Furthermore, the Octopus Charger-based MILP Protocol above must be executed before the first BEV arrives at work (since each BEV driver needs to know which charger they are assigned to). Thus, each BEV driver inputs their expected driving patterns the night before or in the early morning via a user interface, such as a smartphone app. Once the information is gathered, the protocol is executed. A special case where driving data is not available ahead of time, however, is discussed in Section 7.1. The steps for the protocol can be summarized as follows.

• Based on vehicle data (energy needs, availability), each BEV is assigned to an octopus charger, based on a modified version of the Sorted-Balance algorithm.
• Each charger generates a ”cost signal” based on the goals of the parking structure operator.
• Using MILP and the cost signal, each octopus charger schedules charging for its assigned BEVs and shares the resulting energy profile with the central node/processor for aggregation. The updated, aggregated demand load will be used by the next octopus charger.

3. Octopus Charger Assignment

In order to effectively assign BEVs to octopus chargers, an appropriate assignment algorithm must: (1) minimize the number of octopus chargers needed to accommodate all BEVs, (2) have a reasonably fast computational time, and (3) balance the load among octopus chargers. An algorithm that assigns BEVs to octopus chargers, based on each BEV’s inverse charging flexibility ($F_n^{-1}$), is presented below.

The “Load Balancing Problem” is a well-established assignment problem [40]. The Load Balancing Problem occurs when a set of $N$ jobs must be assigned to $M$ identical machines, such that the workload among the machines is as balanced as possible. The processing time of each job (i.e., workload), $n$, is given by $w_n$. The total workload on the $m^{th}$ machine, $L_m$, is defined as the sum of the processing times ($w_n$) of its assigned jobs. The makespan, $L$, is the maximum workload on any machine (i.e., $L=\max \left(L_1,\dots , L_M\right)$). Thus, the objective of the Load Balancing Problem is to minimize the makespan, $L$.

Acquiring the optimal solution to the Load Balancing Problem is NP-hard, which could lead to long computational times. An estimated lower bound for the optimal solution ($L^{*}$), however, can be determined and is described by the following two characteristics: $L^{*}\ge \frac{1}{M}\sum _n{w}_n$ and $L^{*}\ge \underset{n}{\max }{w}_n$, which correspond to perfect distribution and the largest workload, respectively [40].

Sorted-Balance is a well-known approximation algorithm that runs in polynomial time and finds solutions to the Load Balancing Problem that are guaranteed to be close to the estimated lower bound. Sorted-Balance is guaranteed to find approximated solutions ($\widehat{L}$) such that $\widehat{L}\le \frac{3}{2}{L}^{*}$ (see [40] for details). The Sorted-Balance algorithm (Figure 1B) does this by first sorting jobs in decreasing order of processing time ($w_n$). The algorithm then goes through each job in the queue and assigns it to the machine with the smallest load ($L_m$) [40].

BEVs with long dwell times and low charging needs are flexible when it comes to shifting their charging profile. This characteristic can be quantified by a term referred to as the Flexibility Ratio ($F_n$) in [17]. As a result, a large Flexibility Ratio implies that a number of options/configurations are available for the charging profile, allowing load shifting. A low Flexibility Ratio, on the other hand, implies less flexibility to shift charging. A ratio of one, for example, may force a BEV to be charged throughout the entirety of its dwell time(s). A simplified version of the Flexibility Ratio equation from [17] is presented in Equation (1).

$$F_n=\frac{\left[\mathrm{Total}\mathrm{Length}\mathrm{of}\mathrm{Dwell}\mathrm{Times}\mathrm{for}\mathrm{BEV}\#n\right]}{\left[\mathrm{Time}\mathrm{to}\mathrm{Meet}\mathrm{Desired}\mathrm{Charging}\mathrm{Demands}\mathrm{of}\mathrm{BEV}\#n\right]}$$

(1)

If several BEVs with low Flexibility Ratios ($F_n$) are assigned to the same octopus charger, then scheduling charging for all BEVs may not be feasible. The Sorted-Balance algorithm above can be used to distribute the BEVs’ flexibility among octopus chargers, as evenly as possible, to reduce the chances of incompatible groupings. In this application of Sorted-Balance, the BEVs represent the jobs and the octopus chargers represent the machines. To be compatible with the Sorted-Balance algorithm, the BEVs’ Inverse Flexibility Ratios ($F_n^{-1}$) represent the workloads.

The guarantee that the Sorted-Balance solution is close to the optimal solution ($L\le \frac{3}{2}{L}^{*}$) is maintained only if the octopus chargers are assumed to have an unlimited number of cables. If a limit is placed on the number of cables per octopus charger, then the assignment could result in solutions above the guaranteed limit. For example, an octopus charger could have the lowest total workload ($L_m$) but no more available cables. In this case, the current BEV will be assigned to the octopus charger with the smallest total workload and available cables. The focus of this work is on 4-Cable and 8-Cable octopus chargers.

Note that the Inverse Flexibility Ratio and requested charge ($b_n$) can also be used to limit participation in this protocol. For example, if a BEV has very little flexibility and will be charging for a long period, then the said BEV might be better suited with a single-cable charging station. To test this algorithm under the most conservative/difficult conditions, these mitigating factors are not implemented in this study.

In summary, each vehicle, based on its charging needs, charging power, and dwell time obtains its inverse Flexibility Ratio. It then transmits it to the central node, which assigns each vehicle to an octopus charger based on the modified Sorted-Balance algorithm. The computational cost involved is minimal.

4. Smart Charging: Octopus Charger-Based Optimization

For this strategy, each octopus charger generates the charging profiles of all its assigned BEVs. Thus, it is assumed that each octopus charger has access to the expected driving patterns and basic specifications of all its assigned BEVs. Furthermore, for clarity of exposition, the equations below are given for the case where each BEV has a single, continuous dwell time. BEVs with multiple dwell times, however, can be taken into consideration by including the additional inequality constraints proposed in [17]. To increase the clarity of exposition, these inequality constraints are provided in Appendix A. Note that since this protocol is assumed to be run ahead of time (before the first BEV parks) and BEVs connect to the same charger for the entire workday, these additional inequality constraints do not affect the strategy proposed below.

A key feature of this strategy is that octopus chargers generate identical timeslots for all their assigned BEVs. These timeslots are generated such that they maximize the amount of time that each BEV is available for charging and minimizes the total number of timeslots (to minimize computational time). To do this, each octopus charger first generates timeslots that have a resolution of 1 h and start at the top of the hour. The timeslots are then split up every time that a BEV connects or disconnects to/from an octopus charger, so that BEVs are either available or unavailable to charge during the entirety of each timeslot.

As an illustration, suppose there are three BEVs with arrival times of 6:20, 7:00, and 7:30 a.m., respectively. Their departure times are 9:35, 9:15, and 9:15 a.m., respectively. The octopus charger first generates four one-hour timeslots that start at the top of the hour (e.g., 6:00, 7:00, 8:00, and 9:00). The first timeslot is split up into two timeslots so that the first BEV is unavailable during the entirety of the 6:00 timeslot and available during the entirety of the 6:20 timeslot. The arrival of the second BEV does not affect the 7:00 timeslot. The third BEV’s arrival, however, splits up the 7:00 timeslot into two timeslots at 7:30.

Table 1. Timeslots for sample data of BEVs connected to the same octopus charger. Each sample BEV will be available or unavailable to charge during the entirety of each timeslot.

6:00–6:19

6:20–6:59

7:00–7:29

7:30–7:59

8:00–8:59

9:00–9:14

9:15–9:34

9:35–9:59

below contains the universal timeslots for the sample BEVs above.

Splitting of the timeslots, as described above, will add a maximum of two timeslots for each BEV dwell time. Since this work focuses on 4-cable and 8-cable octopus chargers, however, the total number of timeslots always remains practicable. Furthermore, initializing the octopus charger timeslots at lower resolutions (i.e., 5 or 15 min instead 1 h) allows for more charging flexibility among the assigned BEVs. A one-hour resolution, however, is chosen for all simulations in this work (except for Figure 2B) to adequately compare results with [17] and test the charging strategy under strict conditions. Lastly, various other methods can be implemented to ensure that all BEVs connected to the same octopus charger have identical timeslots. These details, however, are omitted to focus on the main concepts of this work. It suffices to say that this step entails minimal computation time to obtain identical timeslots.

4.1. Octopus Charger-Based Optimization: Mixed Integer Linear Programming

As in [17,41,42], this protocol ensures maximum charging power during a BEV’s scheduled charging times, while achieving an overall demand profile with desirable characteristics. Proof of these characteristics is provided in Section 4.2.1. The simplest objective is Valley Filling, which is used to reduce peaks and variability in the demand load (see Section 4.2.2). Alternatively, as in [41], a modified version of Valley Filling can steer demand away from (or toward) specific times, thus, allowing the parking structure operator to maximize the use of renewable energy, avoid high time-related electricity charges, and/or make octopus chargers available for late BEV arrivals (see Section 4.2.1 and Section 4.2.3).

Let the total number of assigned BEVs and the total number of timeslots, for a given charger be $N$ and $I$, respectively. Equation (2) below gives the objective function for the mixed integer linear programming (MILP) problem. The decision variables, $x_n\left(t_i\right)$, are defined as the energy requested by the $n^{th}$ BEV during timeslot $t_i$. The cost signal for BEV $n$, during timeslot,$t_i$, is given by $C_n\left(t_i\right)$. The cost signal here, is not a true cost, but a signal that helps shape a desirable charging profile. In Section 4.2.1, for example, the cost signal prioritizes BEVs with earlier arrival times. The binary variables, $l_n\left(t_i\right)$, are constrained such that they equal one if and only if $x_n\left(t_i\right)$ is nonzero (see Equation (5) for details). The variable $B$ is the assigned cost associated with charging a BEV during any timeslot and must be a small positive number (such that the second term of Equation (2) does not dictate the cost).

$$min J=min \sum _{n=1}^N\sum _{i=1}^I{C}_n\left(t_i\right)x_n\left(t_i\right)+\sum _{n=1}^N\sum _{i=1}^{I}B{l}_n\left(t_i\right)$$

(2)

The equality constraints in Equation (3) establish the total amount of energy requested by the $n^{th}$ BEV ($b_n$). Here, $b_n$ is dictated by the charge desired at the end of the workday. If the dwell time is too short to obtain the desired charge, the maximum amount possible will be used for $b_n$ (see Appendix A for more details).

$$\begin{array}{c}{h}_1\left(x\right)={\displaystyle \sum _{i=1}^I}{x}_1\left(t_i\right)-b_1=0\\ ⋮\\ h_N\left(x\right)={\displaystyle \sum _{i=1}^I}{x}_N\left(t_i\right)-b_N=0\end{array}\}$$

(3)

The inequality constraints in Equation (4) set charging during each timeslot to be positive (i.e., no vehicle-to-grid or vehicle-to-vehicle charging).

$$\begin{array}{c}{g}_{lb,1}\left(x\right)=\left[\begin{array}{c}-x_1\left(t_1\right)\\ ⋮\\ -x_1\left(t_I\right)\end{array}\right]\le \left[\begin{array}{c}0\\ ⋮\\ 0\end{array}\right]\\ ⋮\\ g_{lb,\mathrm{N}}\left(x\right)=\left[\begin{array}{c}-x_N\left(t_1\right)\\ ⋮\\ -x_N\left(t_I\right)\end{array}\right]\le \left[\begin{array}{c}0\\ ⋮\\ 0\end{array}\right]\end{array}\}$$

(4)

If the $n^{th}$ BEV is charging during timeslot $t_i$, the amount of charge is limited to $r_n\left(t_i\right),$ and $l_n\left(t_i\right)$ equals one. The limit, $r_n\left(t_i\right)$, is based on each BEV’s maximum charging rate and the timeslot length. For example, a BEV with a 3.6 kW charging rate can only charge 1.8 kWh during a 30-min timeslot. If the BEV is not charging during timeslot $t_i$, $l_n\left(t_i\right)$ and $x_n\left(t_i\right)$ are both zero. This is enforced by (5).

$$\begin{array}{c}{g}_{ub,1}\left(x\right)=\left[\begin{array}{c}{x}_1\left(t_1\right)-r_1\left(t_1\right)l_1\left(t_1\right)\\ ⋮\\ x_1\left(t_I\right)-r_1\left(t_I\right)l_1\left(t_I\right)\end{array}\right]\le \left[\begin{array}{c}0\\ ⋮\\ 0\end{array}\right]\\ ⋮\\ g_{ub,N}\left(x\right)=\left[\begin{array}{c}{x}_N\left(t_1\right)-r_N\left(t_1\right)l_N\left(t_1\right)\\ ⋮\\ x_N\left(t_I\right)-r_N\left(t_I\right)l_N\left(t_I\right)\end{array}\right]\le \left[\begin{array}{c}0\\ ⋮\\ 0\end{array}\right]\end{array}\}$$

(5)

To respect the maximum output rate of the octopus charger, $P_{oct}$, a limit must be placed on the amount of power requested by the assigned BEVs during each timeslot, leading to the inequality constraints in (6), where $p_n$ is the charging rate for each BEV.

$$g_{oct}\left(x\right)=\left[\begin{array}{c}{l}_1\left(t_1\right)p_1+\cdots +l_N\left(t_1\right)p_N-P_{oct}\\ ⋮\\ l_1\left(t_I\right)p_1+\dots +l_N\left(t_I\right)p_N-P_{oct}\end{array}\right]\le \left[\begin{array}{c}0\\ ⋮\\ 0\end{array}\right]$$

(6)

Each octopus charger acts as an individual agent when generating the charging profiles for its assigned BEVs. Thus, this strategy is centralized at the octopus charger level for the BEVs assigned to it. It is, however, decentralized at the parking structure level with respect to the octopus chargers. While this strategy can be used by the parking structure to generate the charging profiles of all the BEVs in a centralized manner, it may not scale well in a computational sense, thus, leading to a heavy computational burden on the central node of the parking structure [43]. The decentralized nature of this strategy allows for the computational burden to be distributed among the octopus chargers and results in fast running times.

The number of BEVs assigned to each octopus charger (4 or 8 here) times the number of identical timeslots (as discussed above) defines the order of the decision variables. This, plus a handful of constraints for each timeslot, form a MILP problem that is easily solved with current algorithms. For the numerical results shown here, the time required to resolve an octopus charger MILP problem was, on average, less than 0.02 s in MATLAB.

Variable Charging Rate: Linear Programming

The algorithm using (2), (5), and (6) is based on the assumption that all BEVs charge at their maximum rate, $p_n$. This is enforced in (6) by only allowing BEVs to reserve timeslots where maximum power is possible. This enforcement, however, limits charging during timeslots where the sum of BEV charging is less than the octopus charger’s charging capacity, $R_m\left(t_i\right)$ (i.e., $x_1\left(t_i\right)+x_2\left(t_i\right)+\dots +x_N\left(t_i\right)<R_m\left(t_i\right)$), which could result in a need for additional octopus chargers to satisfy charging for all BEVs. To avoid this, the problem formulation above can be converted into a linear program by (i) removing the second term of Equation (2), (ii) replacing all $r_n\left(t_i\right)l_n\left(t_i\right)$ terms in Equation (5) with $r_n\left(t_i\right)$, and (iii) replacing all $l_n\left(t_i\right)p_n$ and $P_{oct}$ terms with $x_n\left(t_i\right)$ and $R_m\left(t_i\right)$ in Equation (6), respectively. Doing so increases the amount of charging performed by each octopus charger, but results in BEVs receiving charge at partial power levels, which may not be feasible for some BEVs.

4.2. Cost Signal

As in [17], an appropriate cost signal must be chosen in order to develop a final parking structure demand load with desirable characteristics. The cost signals discussed in the following sections can generate demand loads that will charge BEVs as early as possible, reduce the maximum peak load, or prevent charging during certain periods of the day. These cost signals (or variations of them) can be used to reduce electricity costs or to incorporate constraints from local distribution components (as in [44,45]). Early charging does not require communication with the central processor. The other two strategies require an ordering of the chargers. Each charger then sends its overall demand profile to the central processor, which aggregates it with the demand of all prior chargers. The communication and computational burden is minimal.

4.2.1. Early Charging

For the decentralized algorithms in [17,41,42], each BEV generates its own charging profile based on an updated cost signal received from a central node/processor. The cost signal is required to have distinct values (mathematically) for different timeslots, to ensure BEVs charge at their maximum rate, except at possibly one time slot (see [41] for details). For the centralized approach in this work, the cost signal generated by the chargers has a dependency on both time and BEV (i.e., $t_i$ and $n$ in $C_n\left(t_i\right)$). The dependence on $n$ (the order of arrival, with $n=1$ for the first BEV) is used to prioritize some BEVs over others. Here, the objective is to ensure that earlier timeslots are utilized by BEVs with earlier arrival times (i.e., lower values of $n$), thus, increasing the availability of timeslots and chargers for unexpected BEV arrivals (see Section 7.1, for example).

This is accomplished by (i) giving earlier timeslots a lower cost, via Inequality (7) below, and (ii) forming the cost signal such that the earlier BEVs get clear priority, via (8). A cost signal that satisfies Inequality (7) ensures that the BEV will seek to receive maximum power during the least expensive periods (i.e., earlier ones) and Inequality (8) (as explained below) ensures that BEVs charge at maximum capacity during all timeslots (i.e., $x_n\left(t_i\right)=r_n\left(t_i\right)$), except for one. Note, however, that simple modifications can be made to Inequality (8) to change how priority is given. For example, priority could be given to BEVs with earlier departures rather than arrivals.

$$C_n\left(t_i\right)<C_n\left(t_{i+1}\right) \forall i, n$$

(7)

$$\left|C_n\left(t_{i+1}\right)-C_n\left(t_i\right)\right|>\left|C_{n+1}\left(t_j\right)-C_{n+1}\left(t_k\right)\right| \forall i, j, k, n$$

(8)

To see how this works, suppose that feasible solutions exist and the optimal cost of $J^{*}$ is obtained. Now consider two BEVs $n$ and $p$ such that $n<p$. The earlier BEV ($n$) will be assigned the largest possible charge during the earliest available timeslots (i.e., $x_n\left(t_i\right)=r_n\left(t_i\right)$, as long as the equality constraints in Equation (3) are not violated).

Suppose now, however, that an alternate feasible solution can be generated such that any amount of charging, $ϵ$, for BEV $n$ is carried out during timeslot $t_k$ instead of $t_j$, where $j<k$. Given the higher cost at $t_k$ for BEV $n$, this can only be helpful if the power during $t_j$ is used by another later BEV (i.e., BEV $p$) to attempt to reduce the cost. The total charging cost for such an alternate solution will be $J=J^{*}+ϵ\left[\left(C_n\left(t_k\right)-C_n\left(t_j\right)\right)-\left(C_p\left(t_k\right)-C_p\left(t_j\right)\right)\right]$. To ensure this always increases the cost and, thus, prioritizes earlier timeslots for earlier BEVs, Inequality (8) is needed. Thus, higher priority BEVs will always charge as much as possible (i.e., $x_n\left(t_i\right)=r_n\left(t_i\right)$) during the earliest feasible timeslots, except for one, since there can be one timeslot such that $x_n\left(t_i\right)\ne r_n\left(t_i\right)$, so that the equality constraint from (3) can be met. Recall that Inequality (6) ensures that BEVs can only reserve timeslots where maximum power (i.e., $x_n\left(t_i\right)=r_n\left(t_i\right)$) is possible.

Alternatively, suppose that allowing BEV $n$ to charge as much as possible during timeslot $t_j$ prevents a lower priority BEV ($p$) from obtaining its full charge ($b_p$). The solution, in this case, would not be feasible and result in BEV $n$ being reassigned to another timeslot.

For the single timeslot such that $x_n\left(t_i\right)\ne r_n\left(t_i\right)$, the entire timeslot is reserved by the BEV, based on Equation (6). Charging for this timeslot is carried out at full power ($p_n$) during the earliest portion of the timeslot, such that $x_n\left(t_i\right)$ is satisfied. Note that, for clarity of exposition, the equations above are given for the case where each BEV has a single, continuous dwell time. For BEVs with multiple dwell times, there can be one timeslot such that $x_n\left(t_i\right)\ne r_n\left(t_i\right)$ during each dwell time.

A sample cost signal, which satisfies Inequalities (7) and (8), for three BEVs ($N=3$) and with four universal timeslots ($I=4$) is given in Equation (9). Note that the true values of the cost signal are not relevant. Only their values relative to each other are important. For example, multiplying $C_{}$ by a constant will still satisfy Inequalities (7) and (8) above.

$$C=\left[C_1\left(t_i\right)\left|C_2\left(t_i\right)\right|\dots |C_N\left(t_i\right)\right]=\left[18 31 44 57 \left| 5 9 13 17 \right| 1 2 3 4\right]$$

(9)

4.2.2. Valley Filling

By using an appropriate cost signal, (2)–(6) can be used to generate a final demand profile with desirable characteristics (i.e., Valley Filling). In the decentralized algorithm in [17], Valley Filling is performed by using the updated parking structure demand load, $C_{load}\left(t_i\right)$, as the cost signal for each individual BEV’s optimization. Where $C_{load}\left(t_i\right)$ is an aggregation of the initial parking structure baseload and all previously scheduled BEV charging profiles. For the centralized approach in this paper, however, each octopus charger must use the updated parking structure demand load to generate a cost signal ($C_n\left(t_i\right)$) to schedule charging for all of its assigned BEVs.

Inequality (7) above is designed to charge BEVs as early as possible. A similar relationship for the cost signal is defined in Inequality (10), such that the lowest cost timeslots for each BEV (connected to an octopus charger) coincide with the lowest values of $C_{load}\left(t_i\right)$. Doing so forces BEVs to charge during the “valleys” of the updated parking structure demand load. Thus, generating a cost signal that satisfies Inequalities (8) and (10) allows octopus chargers to perform Valley Filling. Note that Inequality (8) is required to charge BEVs at their maximum rate and, thus, prioritizes charging during timeslots with the deepest valleys to BEVs with earlier arrival times.

$$C_n\left(t_j\right)<C_n\left(t_k\right) iff C_{load}\left(t_j\right)<C_{load}\left(t_k\right) \forall j, k, n$$

(10)

Consider the sample parking structure demand load given in (11). A sample cost signal that satisfies Inequalities (8) and (10) is given in (12). Note that all BEVs will charge during timeslot $t_3$, if possible. Inequality (8), however, gives priority to the earliest arrivals.

$$C_{load}\left(t_i\right)=\left[C_{load}\left(t_1\right)C_{load}\left(t_2\right)C_{load}\left(t_3\right) C_{load}\left(t_4\right)\right]=\left[100 90 60 70\right]$$

(11)

$$C=\left[C_1\left|C_2\right|\dots |C_N\right]=\left[57 44 18 31 \left| 17 13 5 9 \right| 4 3 1 2\right]$$

(12)

4.2.3. Augmented Cost Signal

In some cases, it may be beneficial to avoid charging during certain periods of the day. This could be due to high electricity prices, limitations in the local charging infrastructure, or the need to reduce the load during scheduled maintenance. By applying the methods in [17], minor modifications can be made to the initial parking structure demand load so that demand is steered away from (or towards) specific hours. The initial parking structure demand load is artificially increased during On-Peak hours to generate an augmented load (and, thus, augmented cost signal). The artificially-high cost signal discourages BEVs from charging during On-Peak hours and can help parking structure operators reduce electricity costs.

5. Parameters, Data, and Related Assumptions

In this work, it is assumed that the daily driving patterns of all BEVs are known. Sharing of driving patterns, however, can be facilitated by the emergence and advancement of location and calendar information on smart phones (e.g., location reminders). Furthermore, driving patterns are more easily available when considering commercial applications, such as delivery and bus companies.

External factors, such as weather and traffic, can affect driving patterns (and, thus, charging needs). To account for this, an extra reserve of charge or safety factor (as in [17]) can be incorporated into the algorithm. Since such adjustments depend on local and day-to-day conditions, they are not included in the simulations below. Incorporating these modifications into the algorithm, however, is quite trivial (see [17] for example).

The 2017 National Household Travel Survey (NHTS) [46] was used to obtain vehicle travel data for the following simulations. The same filtering parameters from [17] were used to obtain realistic vehicle travel data. The filtering process resulted in travel data for 53,951 vehicles in the United States. This data was used to generate driving patterns for the BEVs in the following simulations. A small percentage of vehicles were found to be at work past midnight.

A charging efficiency ($\eta$) of 0.9 was assumed for all BEVs. It was also assumed that all BEVs were fully charged when they left home. Specifications for the 2017 Nissan Leaf were used for all BEVs. These specifications are as follows: (i) 0.3 kWh/mi fuel economy, (ii) 30 kWh battery, and (iii) 3.6 kW charging rate.

Each charging strategy was tested on 50 different simulated parking structures. All parking structures were simulated with 100 and 500 participating BEVs. A different sample of randomly selected BEVs, from the filtered NHTS data, were used for each of the 50 parking structures. The BEVs included in parking structure #X for 100 BEVs are a random subset of the 500 BEVs used in parking structure #X. In order to test these algorithms, the parking structures sizes from the UC Irvine campus were used. The UC Irvine parking structures contain approximately between 1000 and 2000 parking spaces each. By assuming 100 and 500 participating BEVs, penetration levels from 5–10% and 25–50% are simulated, respectively.

To generalize the results, all simulations were performed with no “initial load” (i.e., no initial parking structure demand load). Modeling parking structures with an initial load, however, is straightforward and omitted for brevity. Simulating parking structures with an initial load did not affect the performance of the algorithm (see [47] for details).

6. Results

Results for the Octopus Charger-based MILP Strategy are presented in this section. The same parking structures and BEVs from [17] were used under the same conditions. The additional inequality constraints proposed in [17] were applied to all BEVs with multiple dwell times (see [17] and/or Appendix A for more details). The Uncontrolled Charging results from [17] are included in Section 6.5 and Section 6.6, to compare simulations for octopus chargers with simulations for single-cable charging stations.

All charging scenarios presented here assume that all BEV drivers attempt to get the highest possible SOC by the end of the day (i.e., they attempt to get a 100% SOC when possible). All BEVs charge at a rate of 3.6 kW. All 4-Cable and 8-Cable octopus chargers have maximum output rates of 3.6 kW and 7.2 kW, respectively; thus, 4-Cable octopus chargers can charge one BEV at a time and 8-Cable octopus chargers can charge two BEVs at a time. The computational costs of the protocol are quite modest. On average, the most demanding part, the optimization task of an octopus charger (using MILP), took less than 0.02 s in MATLAB.

6.1. Octopus Charger Assignment

A modified version of the Sorted-Balance algorithm was used in conjunction with the Octopus Charger-based MILP Strategy to find the minimum number of 4-Cable and 8-Cable octopus chargers needed to satisfy the charging requirements ($b_n$) of all BEVs in the simulated parking structures. We started with the lowest feasible number of chargers. Since a charging cable is needed for each BEV, the lowest feasible number of chargers needed for 100-BEV and 500-BEV parking structures are 25 and 125, respectively, when using 4-cable octopus chargers. If at least one BEV did not receive their requested charge, then the number of octopus chargers was increased by one until the minimum number of chargers was found.

Octopus charger assignment was evaluated for all 50 simulated parking structures. The Inverse Flexibility Ratios of all BEVs were balanced among the octopus chargers. The total number of octopus chargers needed to satisfy charging for all 50 simulated parking structures are presented in

Table 2. Number of octopus chargers needed for all 50 simulated parking structures.

		Min.	Avg.	Max.
Four-Cable	100-BEV Parking Structure	25	25.1	27
	500-BEV Parking Structure	125	125.48	129
Eight-Cable	100-BEV Parking Structure	13	13	13
	500-BEV Parking Structure	63	63	63

. No more than four additional 4-Cable octopus chargers, above the lowest feasible number (25 and 125), were needed to satisfy the charging demands of all simulated BEVs. No additional 8-Cable octopus chargers were needed. This is likely because it is easier for a less flexible BEV (with large charging demands and/or low flexibility) to cause a disruption for a 4-Cable octopus charger than an 8-Cable octopus charger. Thus, if there is a mixture of 4-Cable and 8-Cable octopus chargers, then it is generally better to place less flexible BEVs in 8-Cable chargers.

The 4-Cable octopus charger assignment strategy above outperformed the strategy proposed in [17], in all cases. Furthermore, the 500-BEV simulations in [17] required at least 12 more octopus chargers than the worst case (129) in Table 2. Thus, the charging protocol presented here provides a significant improvement, with respect to octopus charger assignment, over the one presented in [17]. The key is that in [17] BEVs were assigned to octopus chargers after their charging profiles were generated (to reduce electricity costs). By assigning BEVs to octopus chargers first, this protocol can maximize the utility of each octopus charger.

The results in Table 2 represent cases where feasible solutions were found by all octopus chargers. If a feasible solution can be found using one cost signal, then a feasible solution can be found using another cost signal; thus, the same number of octopus chargers will be used for each simulated parking structure, whether we wish to perform the Early Charging, Valley Filling, or Augmented Cost Signal strategies.

Simulations where assignment was based on requested charge ($b_n$), instead of Flexibility Ratio, were also performed. Results for these simulations were typically not as good and are, thus, omitted. Additionally, for practical applications, it is advisable to install a few extra single-cable chargers for BEVs with low charging flexibility.

6.2. Octopus Charger-Based MILP: Early Charging

Simulations were performed to generate the daily load for the 50 simulated parking structures. Representative results from parking structure #2 (out of 50 simulated parking structures) are presented in the following subsections. Cases where either 4-Cable or 8-Cable octopus chargers were installed at the parking structure were studied. The Octopus Charger-based MILP Strategy from Section 4 was used to set charging for BEVs to occur as early as possible. Results for the Early Charging Strategy with a one-hour timeslot resolution are presented in Figure 2A. The maximum load experienced in both cases is slightly above 400 kW. The profile of the demand load has a saw-tooth pattern with peaks at the top of the hour. This is caused by the simple post-processing carried out to charge BEVs at their maximum rate. For example, if a BEV needs 1.2 kWh of charge during its final timeslot, then it will only charge during the first 20 min of the final timeslot (because it will charge as early as possible). This saw-tooth pattern can be reduced by using a finer resolution when generating the timeslots for the octopus charger (see Figure 2B) or by staggering the start time of timeslots for different octopus chargers.

6.3. Octopus Charger-Based MILP: Valley Filling

The Octopus Charger-based MILP Strategy from Section 4 can be used to perform Valley Filling when the cost signal generated by octopus chargers satisfies Inequalities (8) and (10). Results for the Valley Filling strategy are given in Figure 3. There is very little difference between the demand loads generated with 4-Cable and 8-Cable octopus chargers. The maximum peaks experienced when using 4-Cable and 8-Cable octopus chargers were both approximately 190 kW for 500-BEV parking structures. This is comparable to the 184 kW peaks generated when the BEV-based strategy was paired with ordering via Flexibility Ratio in [17].

6.4. Octopus Charger-Based MILP: Augmented Cost Signal

Simulation results for the Augmented Cost Signal Strategy with 2018 On-Peak-Hours (12:00 p.m.–6:00 p.m.) and 2019 On-Peak Hours (4:00 p.m.–9:00 p.m.) are presented in Figure 4. The load during On-Peak Hours is lowered in both cases. The Augmented Cost Signal strategy avoids charging during the 2019 On-Peak hours more effectively than with the 2018 On-Peak hours. This is because 2019 On-Peak hours (4:00 p.m.–9:00 p.m.) occur during declining BEV availability at work. A small dip is seen in Figure 4A as 6:00 p.m. approaches. This occurs because a subset of BEVs that can avoid charging during On-Peak hours shift their charging after 6:00 p.m. The dip for the 8-Cable load is larger, because the 4-Cable octopus charger have less charging flexibility (since they can only charge one BEV at a time).

6.5. Effects on Parking Structure Demand Load

The maximum 24-h loads experienced by 500-BEV parking structures are presented in Figure 5A. The values from the Uncontrolled Charging strategy in [17] are included here, to compare octopus chargers with single-cable charging stations. Single-cable charging stations are defined as chargers that can only have one BEV connected at a time. When performing Uncontrolled Charging, a BEV will start charging at its maximum rate when connected and continue charging until it receives its requested charge (see [17] for details).

Early Charging reduces the maximum load compared to Uncontrolled Charging but has the highest maximum load among the smart-charging strategies. Valley Filling results in the lowest maximum loads in all cases, demonstrating its peak reduction capabilities. In all cases, the Octopus Charger-based MILP Protocol resulted in reduced loads when compared with Uncontrolled Charging. Minor differences are seen when comparing 4-Cable and 8-Cable octopus chargers.

The maximum On-Peak loads experienced by 500-BEV parking structures are given in Figure 5B. The Augmented Cost Signal strategy reduces the maximum On-Peak load most effectively (when compared with all other strategies). Early Charging generates the highest 2018 On-Peak loads (above Uncontrolled Charging). The Valley Filling strategy generates the highest 2019 On-Peak loads by shifting charging regardless of the cost. In some cases, 4-Cable octopus chargers generated higher On-Peak loads (when compared to 8-Cable). This occurs because 8-Cable octopus chargers can charge two BEVs at the same time, while 4-Cable chargers can only charge one BEV at a time. This difference improves compatibility among the connected BEVs (as seen in Table 2), which results in better load shifting capabilities for 8-Cable chargers.

6.6. Effects on Electricity Costs

The methods described in [17] were used to calculate the monthly costs of each simulated parking structure. The generated monthly electricity costs are given in Figure 6. Minor differences are seen when comparing 4-Cable and 8-Cable octopus chargers. The Valley Filling and Augmented Cost Signal strategies reduce monthly electricity costs in all cases with 2018 On-Peak hours. With 2019 On-Peak Hours, however, Valley Filling results in monthly costs that are comparable to those of Early Charging. This occurs because a pure Valley Filling, without any regard to cost, shifts charging to the more expensive On-Peak Hours to reach a flatter profile. Note, however, that Valley Filling is better suited for applications where the objective is to reduce the peak load, which can be beneficial if demand charges are high.

Average monthly savings between 32 and 40% are seen for all cases, except for Early Charging and Valley Filling with 2019 rates (when compared to Uncontrolled Charging). These savings are comparable to those seen when the BEV-based strategy was paired with ordering via Flexibility Ratio (34–38%) in [17].

6.7. Remarks on Influence of Key Parameters

We have used parking structures with either 100 or 500 BEVs. Increasing the number of BEVs will not affect the results significantly, but the added flexibility will improve the results somewhat. Similarly, we used octopus chargers with either 4 cables (charging one BEV at a time) or 8 cables (charging two BEVs at a time). Here, increasing the number of cables leads to noticeable improvement in the results. For clarity of exposition, we only used charging rates of 3.6 kW. Using higher charging rates would improve charging flexibility and, thus, the overall results, particularly compared to Uncontrolled Charging. Lastly, electricity tariffs can influence electricity costs, based on the desired parking structure demand load. For example, Valley Filling, which solely seeks a more level charging profile for the structure, may lead to higher overall costs depending on specific time-of-use charges.

7. Extensions

7.1. Real-Time Octopus Charger-Based Optimization

The Octopus Charger-based MILP Protocol entails modest communication requirements to allow it to be executed in the morning (before the first BEV arrives). While the technology for such communication is readily available, some drivers may be unable or unwilling to share their expected driving patterns ahead of time. In this case, the driving patterns of each BEV would be obtained only at the time when the BEV connects to its assigned octopus charger. To do this, an assignment strategy that requires no data prior to each BEV’s arrival is needed.

Greedy-Balance is another well-known approximation algorithm that can be used to find solutions to the Load Balancing Problem [40]. The structure of Greedy-Balance is generally the same as Sorted-Balance, except that BEVs’ Inverse Flexibility Ratios are not initially sorted. Since there is no sorting ahead of time, the Greedy-Balance algorithm can assign BEVs to octopus chargers as they arrive (i.e., based on arrival time). The Greedy-Balance algorithm is guaranteed to find approximate solutions ($\widehat{L}$) no more than twice the lower bound of the estimated optimal solution (i.e., $\widehat{L}\le 2L^{*}$) [40]; thus, Sorted-Balance outperforms Greedy-Balance. The lack of sorting, however, allows octopus chargers to be installed in various destination-charging besides workplaces (e.g., apartment buildings, shopping malls, universities, etc.).

A Real-Time Octopus Charger-based MILP Protocol for workplace charging is discussed here briefly. As each BEV arrives to the parking structure, it is assigned to the octopus charger with the lowest workload, $L_m$ (i.e., the sum of Inverse Flexibility Ratios of its assigned BEVs). As each driver connects their BEV to the octopus charger, that BEV’s expected driving patterns for the day become available to the octopus charger. If it is the first BEV to connect to the assigned octopus charger, then Octopus Charger-based MILP Strategy (from Section 4) is executed on the lone BEV. If other BEVs were previously connected, then the connected BEVs cancel their charging profile for the rest of the day and a new MILP solution (with the updated information) is found, thus, updating the charging profiles of all BEVs previously connected to said octopus charger. The octopus charger then sends the sum of all the charging profiles (along with the cancelled profiles) to the parking structure operator, where they are aggregated for an updated parking structure demand load. The process is repeated with the next BEV to arrive, until all BEV charging profiles have been generated.

The lack of prior information resulted in modest increases in the number of required 8-Cable octopus chargers. The Early Charging and Augmented Cost Signal strategies required less than 66 octopus chargers for 500-BEV parking structures, on average. The Valley Filling strategy required 79 octopus chargers for 500-BEV parking structures, on average. In several instances, however, the Real-Time Octopus Charger-based MILP Protocol failed to find feasible solutions for a reasonable number of 4-Cable octopus chargers, due to their lack of flexibility. These details are omitted due to space considerations. Refer to [47] for more details.

7.2. Potential Application for Home Charging

The protocol presented here allows octopus chargers to generate charging profiles for their assigned BEVs via MILP. By allowing octopus chargers to act as individual agents, the protocol removes the computational burden from the central node of the parking structure and results in fast running times (when the number of assigned BEVs is modest). The role of the central node is, thus, generally relegated to assigning BEVs to octopus chargers, aggregating charging profiles to the demand load, and broadcasting the updated demand load.

Due to its decentralized nature, at the octopus charger level, the protocol presented here has potential applications in home charging. Since local distribution transformers serve a finite number of BEVs, transformers can take the role of octopus chargers and generate charging profiles for the BEVs they serve. Since BEVs do not need to be assigned to transformers, the role of the central node is reduced to aggregating charging profiles and broadcasting the updated demand load, which can be performed by the Independent System Operator (ISO), as proposed in [41]. Thus, with the proper modifications, the protocol proposed here may be able to reduce distribution transformer aging caused by smart-charging at the grid level, as in [42]. A full treatment, including comparison with alternative home charging protocols, is beyond the scope of this paper and is suggested as a future work.

8. Conclusions

An inadequate charging infrastructure could be a major obstacle for a large-scale adoption of plug-in electric vehicles. A comprehensive mixed integer linear programming protocol that allows octopus chargers to independently generate charging profiles for their assigned BEVs is proposed in this work. By using octopus chargers, the proposed protocol can reduce the infrastructure cost associated with the installation of charging stations and allow flexibility to shape the overall demand load in response to grid conditions, while also reducing electricity costs for parking structure operators. Thus, giving an incentive to parking structure operators to provide charging opportunities to employees at the workplace.

A simple and well-known algorithm is used to assign BEVs to octopus chargers, where the main optimization is performed. Hence, creating a distributed structure for the key computational component, along with a modest and easily scalable role for the central processor. In all cases, no more than five additional octopus chargers (compared to the theoretical minimum) were needed to satisfy the charging demands of all simulated BEVs. A key requirement for this assignment is that all drivers know their driving patterns for the entire workday, with reasonable accuracy. Such information, however, may be easily available for various applications of the proposed strategy, such as delivery trucks and public buses, where this charging strategy can be used to generate the charging schedules for the entire fleet of a bus or delivery company. If driving schedules are not known until each BEV arrives, then the alternate Real-Time Octopus Charger-based Optimization Protocol proposed here can be used instead.

With simple modifications to the cost signal, this smart-charging protocol can be used to charge BEVs as early as possible, reduce parking structure load variation (Valley Filling), or shift charging away from On-Peak hours (Augmented Cost Signal). The Augmented Cost Signal strategy significantly reduced monthly electricity costs in all cases, when compared with the Uncontrolled Charging and the Early Charging strategies presented here. Furthermore, savings from the strategies in this work were comparable to those seen in [17], while significantly reducing the number of required octopus chargers.

While this work is focused on reducing infrastructure and operational costs for workplace parking structures, the protocol proposed here can be used in other applications. For example, by applying the appropriate cost signal, the protocol can be used to increase the utilization of local renewable resources, allow businesses to participate in demand response programs, reduce the demand load during periods of scheduled maintenance, and/or reduce transformer aging. Furthermore, the proposed protocol could be used to help delivery companies meet their goals of converting large portions of their delivery trucks to battery-electric propulsion. With small modifications, the protocol could help eliminate investments to circuitry and local electrical components, which would otherwise be required with Uncontrolled Charging.