Managing Overstaying Electric Vehicles in Park-and-Charge Facilities

1 Introduction

As the number of on-road Electric Vehicles (EVs) increases rapidly, lack of adequate charging infrastructure is an area of growing concern. For example, a recent New York Times article reports that in California, scarcity of park-and-charge spots is a chronic problem: "Electric-vehicle owners are unplugging one another's cars, trading insults, and creating black markets and side deals to trade spots in corporate parking lots" [Richtel, 2015]. While investing in a wide-spread deployment of charging stations by both public and private service providers is needed to address the infrastructure problem [Gopalakrishnan et al., 2016] in the long-term, effective use of the existing charging infrastructure can help in significantly reducing this problem. In particular, curbing improper utilization of park-and-charge spots can improve their availability. Two prominent causes of utilization degradation are

(i) the overstaying problem, where an EV continues to occupy a park-and-charge spot even after it is fully charged, and (ii) the "icing" problem, where a gas-powered car (Internal Combustion Engine or ICE vehicle) occupies a parkand-charge spot.

While icing and overstaying in park-and-charge spots are illegal in increasingly many jurisdictions, there is little or no enforcement [Loveday, 2013], as a result of which the frustrated users resort to ad-hoc measures ranging from mild (e.g., leaving courtesy notices) [Blink, 2012; 2015] to drastic (e.g., publicly shaming the violator by posting a picture of the violation showing the violator's license plate on blogs and social media) [Tumblr, 2015; Zapatag, 2015]. Extension cables that can help charge a vehicle parked a few spots away from an occupied park-and-charge spot are available in the market, but are very expensive [Moloughney, 2015]. A longer term solution to these problems, however, will require both enforcement and an appropriate penalty for these events.

While enforcement with heavy penalty may help curb icing, a gentler approach is prudent to manage overstaying EVs. Depending on the demand for charging, overstaying EVs potentially block access to other EVs that might need charging, and so, it is important to discourage such behavior by imposing penalties. But, imposing too high a penalty might turn away EVs from using the park-and-charge facility altogether due to increased risk of a steep fine, since EV users may not exactly know their parking duration beforehand.

Our central contribution in this paper is a novel framework that combines a realistic user behavior model with traditional queueing dynamics to capture this trade-off and study the optimal penalty from the points of view of both utilization and revenue. Next, when the model parameters are unknown, we show how the well known UCB[Auer et al., 2002] learning algorithm can be adapted to learn the optimal penalty over a period of time. Our experiments, based on charging data from London, show that an appropriate penalty results in increased utilization and significantly increased revenue. Also, perhaps surprisingly, we observe that the utilization achieved by imposing the revenue-maximizing penalty is very close to the maximum utilization.

1.1 RelatedWork

Dynamic pricing of parking has been an area of active study in the transportation literature. In [Zoeter et al., 2014;

Rowe and Fiorucci, 2011], the authors present dynamic pricing schemes for regular parking based on estimated demand to reduce both congestion and underuse. On the other hand, significant work has also been done on dynamic pricing of electric vehicle charging. In [Tushar et al., 2012], the authors model the problem as a Stackelberg game between the smart grid as the leader setting the price, and the vehicle owner as the follower deciding their charging strategies. In [Anglin et al., 2013; Gadh et al., 2012; Hafner et al., 2009], dynamic pricing of electricity for charging EVs is proposed based on the usage data in a given location and time. None of the above work, however, consider the problem of overstaying EVs. To the best of our knowledge, this is the first paper to investigate designing penalty schemes for park-and-charge facilities to combat overstaying EVs.

To address the situation where the probability distributions required for modelling user behaviour remain unavailable to the system until the users are actually observed, and the user behaviour needs to be learned over time, we model our problem as a Multi-Armed Bandit (MAB) problem, which has been well studied [Bubeck and Cesa-Bianchi, 2012; Auer et al., 2002; Cesa-Bianchi, 2006; Agrawal, 1995] and applied to a wide variety of domains such as crowdsourcing, online advertising, dynamic pricing, and smart grids. However, we are not aware of any application of MABs to the park-and-charge scenario.

2 Park-and-Charge SystemModel

We adopt a simple three-part model for a parking area: (a) Section 2.1 introduces the pricing function (during charging) and penalty function (during overstaying) for an EV, (b) Section 2.2 models how EV users respond to the posted penalty scheme, i.e., whether they agree to its terms and enter the parking area, and if so, how long they stay, and (c) Section 2.3 models the flow of EV users in and out of the parking area using queueing dynamics. We end the section by defining some performance measures of interest in Section 2.4.

2.1 Pricing and Penalty Functions

Let the price function while actively charging be pc(t) and the penalty function for overstaying at a park-and-charge spot after charging is complete be po(t), where pc(0) = po(0) = 0, and pc(t) and po(t) are continuous, nondecreasing functions. In addition, we assume that po(t) is a strictly increasing function, since we will need its inverse function, p-1 o , to be well defined. 1 To be realistically implementable (easily understandable by an average user), these functions should not be more complicated than simple piecewise linear functions; however, our framework is general and can accommodate arbitrary functions. These functions are illustrated in Figure 1.

2.2 EVUser Behavior

We define the following parameters, for each EV user:

• ÷ Tc, the duration of time it would take to fully charge their electric vehicle from the initial state,

1 The framework can be extended to the case where po(t) is not strictly increasing, by defining p-1 o (x) = sup¶t : po(t) = x♦. This could accommodate, for example, an initial "grace period" (no penalty) after charging is complete.

• ÷ Ta, the length of their appointment, i.e., the EV user's preferred parking duration, and
• ÷ Cmax, the penalty threshold, i.e., the maximum penalty due to overstaying that they would bear for the convenience of an uninterrupted appointment.

Let Tc, Ta, Cmax be independent, nonnegative random variables with cumulative distribution functions Fc↪ Fa↪ Fmax.

Penalty Acceptance Probability: When a user arrives at the parking area and inspects the posted penalty scheme, they know their Tc and Cmax, but they may not know exactly how long their appointment will last; hence Ta is not yet realized. However, the user can still estimate the likelihood that their penalty would not exceed Cmax, as follows:

Thus, we assume that an arriving user will enter the parking lot with probability q. Let q denote its mean, given by:

Actual Parking Duration: If a user decides to enter the parking area, they park their EV at a park-and-charge spot and leave for their appointment. Ta is then realized, and if it exceeds Tc + p-1 o (Cmax), we assume that the user reluctantly interrupts their appointment to avoid paying more than Cmax penalty. Thus, the actual parking duration is given by: 2

and hence, the duration of time the EV overstays is given by:

Revenue Collected: The revenue from an EV's time at the park-and-charge spot (the cost to the EV user) is given by:

2.3 QueueingModel

Since there is a finite number of park-and-charge spots in the parking area, the impact of overstaying depends on the arrival process to the parking lot, e.g., if the inter-arrival times are uniformly distributed with a low arrival rate, a limited amount of overstaying may be harmless, as opposed to a high arrival rate during weekends at a mall. We capture such phenomena using an M/G/N/N queueing model [Kleinrock, 1975], where the EVs that accept the posted penalty scheme and enter the parking lot are the "jobs", and the N park-and-charge spots are the "servers". The parameters and assumptions are:

2 If the realized value of Ta is less than Tc, we assume that the user leaves immediately after Ta time units, without waiting for their EV to finish charging.

• ÷ EVs arrive at the parking area according to a Poisson process with rate λ. However, only those EVs whose users accept the posted penalty scheme (with probability q), and enter the parking area are counted for further analysis. Using the total probability theorem and the well known "Poisson splitting" property, it can be shown [Biswas et al., 2016] that this "filtered" arrival process is still Poisson, with rate λ q.
• ÷ An arriving EV that finds all N park-and-charge spots occupied leaves the system (there is no waiting). Otherwise, the EV stays at a park-and-charge spot for a duration of Tpc; thus, the service times are i.i.d. according to the cumulative distribution function of Tpc. 3

If Npc is the random variable denoting the number of EVs in the parking area, then its steady state distribution is:

where ⇢ = λ q E[Tpc] is the "offered load". Thus, in steady state, the mean number of EVs in the parking area is:

2.4 Performance Measures

We define the following performance measures of interest. Throughout, T > 0 denotes an arbitrary duration of time.

• (a) Throughput: The throughput of the park-and-charge system, denoted by ⌧, is the average rate at which EV users leave the park-and-charge area, given by:

• (b) Overstay: The fraction of time spent overstaying at parkand-charge spots, denoted by γo, is given by:

• (c) Utilization: The utilization, denoted by γu, is defined as the fraction of time the park-and-charge spots were used for charging, and is given by:

• (d) Revenue Rate: The revenue rate R is defined as the average rate at which revenue is accrued from the park-andcharge spots, and is given by:

3 This could be a general distribution; however, in an M/G/N/N system, the stationary distribution of its Markov chain (that tracks the number of EVs) depends on the service time distribution only through its mean.

When Tc, Ta, Cmax are generally distributed, and the price/penalty functions pc(t), po(t) are general, the above quantities do not admit closed form expressions, and we defer their mathematical derivations to the full version [Biswas et al., 2016]. However, in Section 3, we investigate a simple special case where the price/penalty functions are linear, Tc and Ta are Exponentially distributed, and Cmax is a constant, and derive closed form expressions for these performance measures.

Benchmarking Performance: In order to measure the effectiveness of our penalty scheme, we benchmark it against a system with ideal human behavior, one in which the EV users, on their own, do not overstay, i.e., Tpc = min¶Tc↪ Ta♦. Here, q = 1, and the revenue from (5) is simply pc(Tpc).

3 Example Scenario: Linear Functions, Exponential Distributions

In this section, we consider a simplified scenario for which we derive closed form expressions for the performance measures, which allows better analysis of the effectiveness of imposing simple, linear penalties for overstaying. In particular, we assume:

• ÷ Linearity: Let pc(t) = ↵ct and po(t) = ↵ot, where ↵c > 0 and ↵o ≥ 0 are the parameters.
• ÷ Tc and Ta are Exponentially distributed with parameters θc and θa respectively.
• ÷ Cmax is not a random variable, but a constant.

Due to limited space, we defer the often nontrivial intermediate steps in evaluating the expressions to the full version [Biswas et al., 2016].

Under the above assumptions, the acceptance probability q from (1) and its mean q from (2) can be evaluated to obtain q = 1-βe-θaTc and q = 1- βθc θa+θc respectively, where

Conditional Distribution of Tc: While Tc is Exponentially distributed by assumption, given that (with probability q,) an EV accepts the posted penalty and enters the parking lot (call this event E), the conditional random variable Tc♣E need not be Exponential. (Ta remains unchanged, since E does not depend on it.) Thus, we first compute the conditional probability density function, fc♣E, using Bayes's rule, to obtain:

3.1 Distribution andMean of Tpc

The complementary cumulative distribution function of Tpc, defined as Fpc(t) = Prob(Tpc > t), can be evaluated as:

Thus, the mean, given by R 1 0 Fpc(t)dt, can be evaluated as:

3.2 Distribution andMean of To

The complementary cumulative distribution function of To, defined as Fo(t) = Prob(To > t), can be evaluated as:

Thus, the mean, given by R 1 0 Fo(t)dt, can be evaluated as:

3.3 Mean Revenue

When the pricing/penalty functions are linear, the revenue defined in (5) is given by R = ↵c(Tpc - To) + ↵oTo, and by linearity of expectations, its mean can be evaluated to obtain:

3.4 Performance Measures

By inspecting the expressions, it can be seen that β is increasing in ↵o. Hence, with increasing penalty, E[Tpc] increases and E[To] decreases. The other quantities, including performance measures (8)-(11), are more complicated and their behavior is not obvious from inspection. We omit a detailed analysis with plots due to space constraints. As an example, when we set N = 10 slots, λ = 8 EVs per hour, θc = 60 45 per hour, θa = 60 105 per hour, Cmax = $4, ↵c = $2 per hour, we find that setting the penalty rate ↵o = $2▷37 per hour provides the maximum value of utilization (30%), whereas the utilization with no penalty is about 26%. (The ideal utilization when there is no overstaying is 42%.) From the point of view of revenue, setting the penalty rate ↵o = $3▷07 per hour provides the maximum revenue rate of $15▷36 per hour, but the decreased utilization at this penalty rate is only slightly less, at 29▷5%. (The ideal revenue when there is no overstaying is merely $8▷34 per hour.) Thus, the revenue maximizing penalty rate provides increased utilization (by 4%), as well as significantly increased revenue (by 85%).

4 Dynamic Environment

In this section, we consider a real world setting where no prior information about the distributions Fc, Fa, Fmax is known, and thus, the expressions for the performance measures are also unknown to the framework. We assume that these distributions are unknown, but fixed for the day; hence, the utilization and revenue for the day depend only on ↵o.

In our model, on each day, a penalty rate ↵o is declared at the entrance to the parking area. Arriving customers behave according to their Tc, Ta, Cmax values (which are unknown to the system, but known to the customers), and the posted penalty rate ↵o; their behavior is as described in Section 2.2. The system observes the customer behavior only after they enter the parking area. Thus, the performance measures (such as revenue rate, utilization, etc.) corresponding to penalty rate ↵o are only observed at the end of the day. The task is to find an optimal penalty rate ↵⇤ o for each day, such that the total revenue over all days is maximized. 4

This problem is an example of sequential decision making in an unknown and dynamic environment, where the system seeks to optimize the average revenue over all days, while continuously gathering more information about the revenue obtained by using different penalty rates ↵o. This leads to a trade-off between exploration (imposing each penalty rate ↵o sufficiently often to obtain better estimates of the corresponding revenue accumulated) and exploitation (frequently imposing the optimal penalty for which the observed revenue is maximized). Such problems naturally fall into the category of stochastic multi-armed bandit (MAB) problems [Bubeck and Cesa-Bianchi, 2012]. Each penalty rate ↵o is considered as an arm, and the daily revenue obtained by imposing that penalty rate is analogous to the reward obtained by pulling the corresponding arm. The goal in the MAB setting is to determine the arm to be pulled each time in order to maximize the total reward obtained.

4.1 Learning AlgorithmUCB-PC

Let A denote a finite, ordered set of penalty rates, and let Ri denote the expected daily revenue corresponding to penalty rate A[i], which is unknown. The (unknown) optimal penalty rate is thus given by A[i⇤ ], where i⇤ = argmaxi Ri. In order to estimate ¶Ri♦, on each day, we impose a penalty rate and observe the daily revenue, which is the sum of the payments made by the customers who choose to enter the parking area that day. 5 In doing so, we keep track of the observed average daily revenues ¶ ˆRi♦, which are then used to gradually learn the optimal penalty rate A[i⇤ ] for the parking area. Algorithm 1 is based on the techniques used in the UCB1 algorithm [Auer et al., 2002], which is a well known tool for solving stochastic multi-armed bandit problems. However, UCB1 assumes that the system is allowed to run only for a finite number of trials T ("finite horizon multi-armed bandit"), whereas we operate under the assumption that the system runs for infinite time, and must therefore tackle the challenges involved in adapting UCB1 to the infinite horizon setting. 6

Algorithm 1 UCB-PC

• 1: Input: A finite set A of penalty rates
• 2: TRi stores the total observed revenue for A[i]
• 3: Ki stores the number of days A[i] is imposed
• 4: for t 1 to ♣A♣ do
• 5: Choose penalty rate A[t] on tth day; Observe revenue earned r;
• 6: Set TRt r; Set Kt 1;
• 9: Choose penalty rate A[i⇤ ] on tth day; Observe revenue earned r;
• 7: Find i⇤ = argmaxi ⇣TRi + p2 ln ♣A♣⌘; 8: for t ♣A♣ + 1↪ ♣A♣ + 2↪ ▷ ▷ ▷ do
• 10: Update TRi⇤ TRi⇤ + r; Update Ki⇤ Ki⇤ + 1;
• 11: Update ˆRi⇤ TRi⇤ Ki⇤
• 12: Find i⇤ = argmaxi ⇣ ˆRi + q 2 ln t Ki ⌘ for (t + 1)th day;

4 Variants of the technique presented here can be used for other performance measures such as utilization or overstay.

5 We observe, for each customer, whether they choose to enter the parking area or not, and if they do, their charging and overstaying times, as well as their final payment.

6 While UCB1 was our choice to illustrate the technique, we believe that our framework can also accommodate modified versions of other stochastic multi-armed bandit algorithms (such as EXP3).

4.2 Performance Analysis

In this section, we compare the performance of our learning algorithm with an optimal algorithm that knows the expected revenues ¶Ri♦ beforehand, and can therefore choose the optimal penalty A[i⇤ ] every day. The loss incurred by the learning algorithm over K days is termed as the regret LK, and can be written as

where E[Ki(K)] denotes the expected number of days (out of K) that penalty rate A[i] is chosen by our learning algorithm. In the literature, the performance of multi-armed bandit algorithms is measured by obtaining an upper bound on this regret. In [Auer et al., 2002], the authors show that the upper bound on the regret using UCB1 is sublinear within a finite, fixed horizon T; in particular, they show that the regret is bounded above by a term that is ˜O(logT). Next, in Theorem 1, we show that the regret for UCB-PC is upper bounded by ˜O(logK) after the algorithm runs for K days, for all K.

Theorem 1. The expected regret of UCB-

Proof Sketch: The proof follows from [Auer et al., 2002], where the upper bound for regret is obtained by bounding the expected number of times an arm is pulled. In our case, the upper bound on E[Ki(K)] for each i 6= i⇤ is given by:

for any finite positive integer ⌧. Next, in Lemma 1, we show that, for any suboptimal penalty index i 6= i⇤ , the term P (A[i] is imposed on day (t + 1) ^ Ki(t) ≥ ⌧) is decreasing in t after sufficient exploration.

Proof. We begin by writing,

After running UCB-PC for t days, a suboptimal penalty index i 6= i⇤ is chosen only when ˆRi⇤ + q 2 ln t s0  ˆRi + q 2 ln t s . Let this event be denoted by W. Also, let U denote the event ⇣ ˆRi⇤  Ri⇤ - q 2 ln t s0 ⌘, and V denote the event

✓ ˆRi ≥ Ri + q 2 ln t s ◆. Now, the probability of choosing penalty rate A[i] on the (t + 1)th day can be written as:

First, we observe that the events ¯U and ¯ V can be equivalently written as:

Then, we show that if (20) holds and s ≥ 8 ln t (Ri⇤-Ri)2 , then the event W is a contradiction:

which is a contradiction. Finally, substituting the results of the above evaluations in (19), we get P(W)  2 t4 , which in turn, can be substituted in (18) to obtain

This completes the proof.

Using Lemma 1 and substituting ⌧ = l 8 lnK (Ri⇤-Ri)2 m in (17), we obtain the required upper bound on regret that is specified by Theorem 1. It can be shown that LK = ˜O(lnK) for a fixed set of penalty rates. Thus, the average daily regret, given by LK K , vanishes as K !1.

5 Experimental Results

For simulating the behavior of electric vehicles we study real-world data for the city of London, obtained from [www.gov.uk, 2013], which consists of 9961 charging events, including usage data of charge points and the duration of stay for EVs. We find it difficult to fit a single parametric model to these data without any restrictions. 7 Therefore, we only look at data entries that correspond to the "standard" charging point type and a specific duration of parking time (between 30 minutes and 180 minutes), in order to fit them in a single parametric model. We assume that the charging duration data corresponds to Tc and the parking duration data corresponds to Ta, the duration for which customers would park their car in the absence of any penalties. The histogram for the restricted parking duration data and charging duration data are shown in Figures 2 and 3.

7 Mixture models can be effective, since they reveal the hidden heterogeneity that arises from a latent categorical variable such as charging point type, parking duration (very short, standard, long), time of arrival (peak hours and non-peak hours), etc.

Figure 3: Histogram of charging duration data

The distributions that best fit these histograms (using Mathematica) correspond to a uniform distribution between 30 minutes and 180 minutes for Ta, and a generalized Gamma distribution with parameters θ = -1▷35188, scale parameter 33▷7831, and shape parameters 1▷44212 and 1▷19403, for Tc.

We assume that the penalty threshold Cmax is a discrete random variable that takes values $4, $8, $10, $20 with probabilities 0▷4, 0▷3, 0▷2, 0▷1 respectively. We also assume a linear pricing function during charging, with rate ↵c = $2 per hour. We simulate vehicles arriving to a parking area with 10 charging slots for a 6 hour time period, assuming that the arrivals follow a Poisson distribution with rate 10 per hour. We also assume that when all the slots of a parking lot are occupied, arriving users do not wait for a slot to be free and immediately leave the parking area. We perform two sets of experiments, discussed next.

Experiment 1: We simulate the parking area for a 6 hour time period per day for 100 days. Then, we observe the utilization and revenue obtained for each day by employing a linear penalty function po(t) = ↵o ⇤ t with ↵o 2 ¶0↪ 1↪ 2↪ 3↪ 4↪ 5↪ 6♦. Note that ↵o = 0 corresponds to the "no-penalty" scenario. We compare these results against an ideal benchmark where EV users do not overstay at all. Figure 4 shows the results averaged over the 100 days.

Utilization: The utilization of the parking area increases (dark blue line) after imposing a small penalty as compared to when no penalty (red dotted line) is charged. However, when a high penalty is imposed, most of the EV users decide not to enter the parking area, resulting in a steep drop in utilization. With a penalty rate $4 per hour, the utilization is maximum, and also very close to the ideal utilization when there is no overstaying by the EV users (green line). Thus, imposing just a small penalty helps improve the utilization of charging spots in the parking area significantly.

Revenue: The daily revenue from the parking area quickly increases even after imposing a small penalty for overstaying. The daily revenue obtained in the ideal situation of no overstaying is more than when no penalty is imposed (albeit only slightly so), since more customers are served in the former situation than the latter. As the penalty rate increases, the daily revenue follows the same pattern as the utilization, and for the same reasons. It should be noted that the penalty rate $4 per hour also maximizes the daily revenue.

Experiment 2: We simulate the parking area for two different settings: (a) the optimal penalty rate ↵⇤ o is chosen on all days, where ↵⇤ o is calculated by approximately) maximizing the total expected revenue with complete knowledge of all the underlying distributions that are used, and (b) our learning algorithm UCB-PC determines the best ↵o for each day, based on the observed parameters for all previous days. We compare the convergence of the average revenue obtained by our learning method to the average revenue obtained by the (approximately) optimal method. Figure 5 shows the results.

We observe that the penalty rates chosen by our learning algorithm UCB-PC are almost equivalent to that of the optimal algorithm after 15 days in terms of the daily revenue obtained. We also show the difference between the total revenue by the optimal algorithm and UCB-PC averaged over the number of days, along with the theoretical upper bound given in Theorem 1. As expected, it can be seen that the average difference, that is, Lk k , decreases with increase in the number of days after sufficient exploration (15 days).

6 Concluding Remarks

In this paper, we undertake a formal study, for the first time, of the problem of overstaying EVs in park-and-charge spots. We establish a novel framework in which we bring together an interdisciplinary mix of models and techniques: probabilistic user behaviour, queueing dynamics, online learning. This framework can be extended to accommodate different user behaviour models, queueing dynamics, and other learning techniques. One can imagine "instantiating" it for multiple parking areas in a city with a model for the population of EV users and study the interaction at a higher level, e.g., competition between parking lots. When viewed as a comprehensive model for park-and-charge, our framework could serve as a useful tool for future research.