The rapid proliferation of distributed renewable energy sources has introduced significant uncertainty and operational pressure on modern power systems. Effectively harnessing the flexibility of demand-side resources has become a critical pathway to accommodate the inherent variability of renewable generation. Among these resources, the battery electric vehicle (EV) stands out as a highly flexible, mobile load. Its charging demand, often concentrated and time-variant, presents both a challenge and an opportunity for grid stability. The growing fleet of battery EV cars on highways creates a complex interplay between transportation networks and power grids. Therefore, intelligently guiding the charging behavior of these battery electric vehicle clusters is paramount for supporting power system operations and maximizing renewable energy utilization in the context of highway travel, where range anxiety and concentrated demand are most pronounced.
Demand Response (DR) is a cornerstone of modern grid management, defined as changes in electric usage by end-use customers from their normal consumption patterns in response to changes in the price of electricity over time, or to incentive payments designed to induce lower electricity use at times of high wholesale market prices or when system reliability is jeopardized. Traditional DR mechanisms for battery EV cars can be categorized into several types: reducing consumption during high-price periods, shifting consumption to off-peak periods, or even injecting power back to the grid via Vehicle-to-Grid (V2G) technology. While V2G offers significant potential, this paper focuses on price-based mechanisms—specifically, dynamic pricing and discount schemes offered by Charging Station Operators (CSOs). By adjusting the charging price, CSOs can incentivize battery electric vehicle users to modify their charging schedules or locations, thereby balancing supply and demand and alleviating congestion at specific nodes in both the power and transportation networks.
For individual battery electric vehicles embarking on long-distance highway journeys, the charging decision is not trivial. It involves a trade-off between several factors: travel time to a charging station, expected queuing time upon arrival, the time required for charging, and the associated economic cost. Unlike short urban trips where charging can often be deferred, highway travel necessitates mid-journey charging, making the choice of where and when to charge a critical component of trip planning. The user’s objective is typically to minimize the total cost of the journey, which can be expressed as a combination of time and monetary expenses.
To model this decision-making process, we construct a State-of-Charge (SOC) Layered Road Network Model. The highway network with its charging stations is represented as a directed, weighted graph $$R = (V_R, E_R, F_R)$$. Each node $$v \in V_R$$ is a two-dimensional state vector $$v = (s_v, c_v)$$, where $$s_v \in \{1, …, S\}$$ denotes the charging station location and $$c_v \in \{c_{v,dn}, …, c_{v,up}\}$$ denotes the discrete SOC level of the battery EV car, with $$c_{v,up}$$ and $$c_{v,dn}$$ being the upper and lower SOC bounds. The SOC is discretized into levels with an interval of $$\Delta c$$. The edge set $$E_R$$ is partitioned into two subsets: $$E_{road,R}$$ representing travel between stations (which decreases SOC), and $$E_{cha,R}$$ representing charging at a station (which increases SOC).
The weight $$f(v, w)$$ of an edge represents the generalized cost for a battery electric vehicle to transition from state $$v$$ to state $$w$$. For a travel edge $$(v, v’) \in E_{road,R}$$, the weight is simply the road travel time:
$$f(v, v’) = t_{road}^{v,v’}$$
For a charging edge $$(v, v”) \in E_{cha,R}$$ at station $$s_v$$, the weight incorporates charging time, queuing time, and the monetary cost converted into equivalent time using a user-specific value-of-time parameter $$\pi$$ (the inverse of income per unit time) and a price sensitivity factor $$\tau$$:
$$f(v, v”) = \frac{c_{v”} – c_{v}}{r_{s_v}} + t_{q, s_v} + \tau \cdot \pi \cdot \zeta \cdot \alpha_{s_v} \cdot (c_{v”} – c_{v})$$
Here, $$r_{s_v}$$ is the charging rate at station $$s_v$$, $$\zeta$$ is the base electricity price, $$\alpha_{s_v}$$ is the discount multiplier (where $$\alpha=1$$ means no discount), and $$t_{q, s_v}$$ is the estimated queuing time. The term $$\kappa_{s_v} = \tau \cdot \pi \cdot \zeta \cdot \alpha_{s_v}$$ can be considered the price-equivalent time cost per unit of energy charged.
| Edge Type | Weight Components | Mathematical Expression |
|---|---|---|
| Travel Edge \((v, v’)\) | Road Travel Time | $$t_{road}^{v,v’}$$ |
| Charging Edge \((v, v”)\) | Charging Time | $$\frac{c_{v”} – c_{v}}{r_{s_v}}$$ |
| Queuing Time | $$t_{q, s_v}$$ | |
| Equivalent Cost Time | $$\kappa_{s_v} \cdot (c_{v”} – c_{v})$$ |
This modeling framework transforms the battery EV car’s charging strategy problem into a shortest path problem on the graph $$R$$. The objective for a single EV traveling from an origin state $$o$$ to a destination state $$p$$ (e.g., reaching the final station with an SOC above a required threshold) is to find the path $$P^*(o,p)$$ that minimizes the sum of the edge weights:
$$\min_{P(o,p)} \sum_{l \in P(o,p)} f(l, t_l)$$
where $$t_l$$ is the time at which the vehicle reaches edge $$l$$. Under static traffic conditions (constant travel and queuing times), this can be solved efficiently using standard algorithms. Under this model, we can prove an important property regarding the influence of CSO discounts. For a simplified three-station highway segment, as the discounts $$\alpha_B$$ and $$\alpha_C$$ at two candidate charging stations vary continuously, the optimal charging strategy for a battery EV car (e.g., “charge fully at B” or “charge fully at C”) changes in a discrete manner. There exists a clear boundary in the discount parameter space defined by:
$$\alpha_C = \frac{\kappa_C}{\kappa_B} \alpha_B + \frac{t_{q,C} – t_{q,B}}{R_{SOC} \cdot \kappa_B}$$
where $$R_{SOC}$$ is the required charging energy. This boundary separates the regions where one strategy is dominant over the other, demonstrating that user behavior exhibits a threshold response to price incentives.
To address realistic conditions, we extend the model to dynamic traffic flow, where travel times and queuing times are time-dependent. The network is now represented as $$G = [V, E, F(t)]$$, with weights updated at discrete time intervals $$\Delta t$$. Solving the shortest path problem in this time-dependent graph requires an adapted algorithm. We employ an improved Dijkstra’s algorithm that incorporates the arrival time at each node to evaluate the appropriate time-dependent weight for outgoing edges. The core of this adapted algorithm involves continuously updating the estimated travel time and queuing time based on the projected arrival time at each subsequent node and charging station.
When considering a large cluster of battery electric vehicles, their collective charging decisions create interdependencies, primarily through the queuing time $$t_{q, s}(t)$$ at each charging station $$s$$ and time $$t$$. The queuing time becomes a function of the charging demand from other battery EV cars. To model this system-wide interaction, we propose a socio-physical-information systems framework involving four agents:
- Traffic Highway Operator (THO): Provides real-time road travel time information.
- Charging Station Operator (CSO): Manages charging stations, sets dynamic discounts $$\alpha_s(t)$$, and provides real-time queuing estimates.
- Information Exchange Center (IEC): A neutral platform that collects data from THO and CSO. Upon receiving a trip and charging request from a battery EV car, the IEC computes the optimal charging strategy using the improved time-dependent model and issues a charging reservation to the recommended station.
- Battery Electric Vehicle Users: Send trip requests to the IEC and follow the recommended charging navigation.
The queuing process at a charging station is modeled as an event-driven dynamic system. We define three logical queues: Queue 1 for vehicles currently charging, Queue 2 for vehicles physically waiting at the station, and Queue 3 (a virtual queue) for vehicles that have a reservation and are en route. Events include Request ($$Rq$$), Arrival ($$Ar$$), Start Charging ($$St$$), and Leave ($$Le$$). The evolution of queue lengths $$N_{q1}, N_{q2}, N_{q3}$$ is tracked over the sorted set of all event times $$T = \{T_1, T_2, …, T_n\}$$. The queuing time for a new reservation is estimated based on the projected state of these queues at the vehicle’s estimated time of arrival.
This leads to a two-stage optimization problem for guiding the cluster of battery EV cars. In the first stage, from the CSO’s perspective, the objective is to maximize total profit over a planning horizon by setting the discount factors $$\alpha_s(t)$$ for all stations $$s$$ and times $$t$$. The profit is the revenue from selling electricity to battery electric vehicle users minus the cost of purchasing electricity from the grid at real-time prices $$\rho(t)$$:
$$\max_{\alpha_s(t)} \sum_{t \in T} \sum_{s \in C_s} \left[ \sum_{j \in N_{q1,s}(t)} \left( \alpha_s(t) \zeta – \rho(t) \right) \cdot (c’_{j,s,t} – c_{j,s,t}) \right]$$
subject to the behavior of the EV cluster.
In the second stage, for the cluster of battery electric vehicle users, each individual EV $$i$$, upon receiving the current discounts and queuing estimates from the IEC, solves its own real-time minimization problem to choose a path $$\eta_i$$ and charging decisions $$\beta_{i,s}$$ (a binary variable indicating if charging occurs at station $$s$$):
$$\min_{\eta_i \in L, \beta_{i,s}} \sum_{s \in C_s} \left[ \beta_{i,s} \cdot \left( \frac{c’_{i,s} – c_{i,s}}{r_s} + t_{q,s}(t_{i,s}^a) + \kappa_{i,s} \cdot (c’_{i,s} – c_{i,s}) \right) \right] + t_{od,\eta_i}$$
where $$t_{i,s}^a$$ is the estimated arrival time at station $$s$$ and $$t_{od,\eta_i}$$ is the total road travel time on path $$\eta_i$$.
These two stages are coupled and solved iteratively. The CSO’s discount decisions influence the battery EV cars’ choices, which in turn determine the queuing times and thus the CSO’s profit landscape. To solve the CSO’s optimization problem, which is non-convex due to the discrete nature of EV responses, we employ a Tabu Search (TS) metaheuristic. The TS algorithm explores the space of discount vectors, using a memory structure (the tabu list) to avoid cycling and escape local optima, seeking the configuration that maximizes profit given the simulated response of the EV cluster.
| Scenario | Solution Metric | Classical MILP Model | Proposed Layered Network Model |
|---|---|---|---|
| With Queuing | Station Chosen | D | D |
| Generalized Cost (s) | 226.72 | 224.96 | |
| Computation Time (s) | 1.96 | 0.01 | |
| With Discount at Station F | Station Chosen | F | F |
| Generalized Cost (s) | 222.38 | 221.11 | |
| Computation Time (s) | 1.80 | 0.01 |
We validate the proposed models and framework through numerical simulations based on real highway data from an Eastern China region, featuring 7 geographical nodes (6 being charging stations) over a 3-hour period. First, the validity and efficiency of the SOC-layered network model and the improved Dijkstra’s algorithm are confirmed. As shown in Table 2, our model produces nearly identical optimal charging strategies as a classical Mixed-Integer Linear Programming (MILP) formulation but with computation times that are orders of magnitude faster (0.01 seconds vs. ~1.9 seconds), demonstrating its superior scalability for real-time navigation.
Next, we investigate the influence of dynamic discounts on the charging strategy space for a single battery electric vehicle. By varying the discount combinations at three candidate stations (C, D, F) using Monte Carlo sampling and mapping the resulting optimal strategies, we observe that the strategy regions in the 3D discount parameter space form distinct, adjacent polyhedrons. This empirically extends our earlier theoretical proof: in dynamic traffic flow, the optimal charging strategy for a battery EV car still changes discretely with continuous discount variation, and the boundaries between different strategy regions (e.g., “charge at D” vs. “charge at F”) can be complex, multi-faceted surfaces. The strategy switch is not always between directly related choices; for instance, as the discount at station C increases, the optimal choice might jump directly from “charge at D” to “split charge between C and E,” bypassing other intermediate strategies.
The core of the study is the simulation of the two-stage framework for a cluster of battery electric vehicles. We compare three market scenarios:
- Scenario 1 (Real-Time Pricing): The price paid by the battery EV car user fluctuates with the real-time grid electricity price.
- Scenario 2 (Uniform Pricing): The CSO sets a fixed retail price (e.g., 1.6 CNY/kWh) with no discounts.
- Scenario 3 (Optimal Discount Pricing): The CSO employs the proposed two-stage model to dynamically set station-specific discounts on the uniform price to maximize profit.
The key performance indicators are CSO profit, average queuing time for battery EV cars, and the load difference (a measure of imbalance) across charging stations. Table 3 summarizes the results.
| Scenario | CSO Profit (CNY) | Avg. EV Queuing Time (min) | Station Load Difference (kWh) |
|---|---|---|---|
| 1: Real-Time Price | – | 13.99 | 210 |
| 2: Uniform Price, No Discount | 176.43 | 11.26 | 200 |
| 3: Uniform Price with Optimal Discount | 181.35 | 11.35 | 170 |
The results demonstrate the effectiveness of the proposed discount mechanism. Compared to the real-time pricing scenario (Scenario 1), both Scenarios 2 and 3 significantly reduce average queuing times for battery EV cars by stabilizing price signals and reducing herding behavior. Most importantly, Scenario 3 (Optimal Discount Pricing) achieves the highest profit for the CSO while simultaneously achieving the most balanced load across charging stations, as indicated by the lowest load difference. The discount strategy successfully entices a portion of battery electric vehicles to charge at stations or times that are more profitable for the CSO (e.g., when grid electricity prices are lower) or less congested, creating a win-win situation: the CSO increases its profit margin, and the system benefits from reduced station congestion and more spatially balanced demand.
In conclusion, this research presents a comprehensive framework for studying and optimizing the charging behavior of battery electric vehicle clusters on highways. By constructing a novel SOC-layered road network model, we effectively translate the EV charging strategy problem into a computationally efficient pathfinding problem solvable under dynamic traffic conditions. We theoretically and empirically demonstrate the existence of discrete boundaries in user strategy selection in response to continuous price discount changes. The proposed two-stage, socio-physical-information framework, integrating a CSO profit-maximizing discount model solved via Tabu Search with an IEC-mediated real-time navigation system for battery electric vehicles, demonstrates significant systemic benefits. Simulation results confirm that a strategically designed dynamic discount mechanism can effectively guide the charging decisions of battery EV car users, leading to increased operational profit for the CSO, a more balanced load distribution across the charging network, and a reduction in overall and individual queuing times. This work provides a valuable market-based tool for harmonizing the needs of battery electric vehicle users, charging infrastructure operators, and the broader power grid, paving the way for more efficient and sustainable electric mobility on highways.